第二章线性表习题课.ppt

1数数据据结结构构主讲人：米晓红主讲人：米晓红2线性表习题课线性表习题课v1)1)在非空的线性表，有且仅有一个开始结点在非空的线性表，有且仅有一个开始结点a a1 1，它没它没 有直接前趋，而仅有一个直接后继有直接前趋，而仅有一个直接后继a a2 2v2)2)有且仅有一个终端结点有且仅有一个终端结点a an n，它没有直接后继，而仅它没有直接后继，而仅 有一个直接前趋有一个直接前趋a an-1n-1；v3)3)其余的内部结点其余的内部结点a ai i(2(2 i i n-1)n-1)都有且仅有一个直接都有且仅有一个直接 前趋前趋a ai-1i-1和一个直接后继和一个直接后继a ai+1i+1。1 1、线性表的逻辑特征、线性表的逻辑特征：一、要点回顾一、要点回顾d1d2d3d4d5d6d732 2、线性表的顺序表示和实现、线性表的顺序表示和实现#defineLIST_INIT_SIZE100#defineLISTINCREMENT10typedefstructElemType*elem;intlength;intlistsize;Sqlist;（1 1）存储结构的定义）存储结构的定义4（2 2）操作的实现）操作的实现StatusListInsert_Sq(SqList&L,inti,ElemTypee)/在顺序表在顺序表L L的第的第 i i 个元素之前插入新的元素个元素之前插入新的元素e eIf(iL.Length+1)returnERROR;if(L.length=L.listsize)newbase=(ElemType*)realloc(L.elem,(L.listsize+LISTINCREMENT)*sizeof(ElemType);if(!newbase)exit(OVERFLOW);L.elem=newbase;L.listsize+=LISTINCREMENT;q=&(L.elemi-1);/q指示插入位置指示插入位置for(p=&(L.elemL.length-1);p=q;-p)*(p+1)=*p;/插入位置及之后的元素右移插入位置及之后的元素右移*q=e;+L.length;/表长增表长增1returnOK;/ListInsert_Sq5StatusListDelete_sq(Sqlist&L，inti，ElemType&e)/在顺序线性表在顺序线性表L中删除第中删除第i个元素，并用个元素，并用e返回其值返回其值if(iL.length)returnERROR;p=&(L.Elemi-1);/p指示删除位置指示删除位置e=*p;q=L.elem+L.length-1;/q指示表尾位置指示表尾位置for(+p；p=q；+p)*(p-1)=*p;/删除位置之后元素前移删除位置之后元素前移L.length-;/表长减表长减1returnOK;/ListDelete_sq6StatusLocateElem_sq(SqListL,ElemTypee)/在顺序表中查找第一个值为在顺序表中查找第一个值为e的元素的位序的元素的位序i=1;p=L.elem;while(i=L.length&（*p+!=e)+i;if(inext;j=1;while(p&jnext;+j;if(!p|ji)returnERROR;e=p-data;returnOK;/GetElem_L9StatusListInsert_L(LinkList&L,inti,ElemTypee)/在带头结点的单链表在带头结点的单链表L中第中第i个位置之前插入元素个位置之前插入元素ep=L;j=0;while(p&jnext;+j;/寻找第寻找第i-1个结点个结点if(!p|ji-1)returnERROR;s=(LinkList)malloc(sizeof(Lnode);s-data=e;s-next=p-next;p-next=s;returnOK;/ListInsert_L10StatusListDelete_L(LinkList&L,inti,ElemType&e)/在带头结点的单链表在带头结点的单链表L中，删除第中，删除第i个元素，并用个元素，并用e返回返回p=L;j=0;while(p-next&jnext;+j;if(!(p-next)|ji-1)returnERROR;q=p-next;p-next=q-next;e=q-data;free(q);returnOK;/ListDelete_L11voidCreateList_L(LinkList&L,intn)/逆位序输入逆位序输入n个元素的值，建立带头结点的单链表个元素的值，建立带头结点的单链表L=(LinkList)malloc(sizeof)(LNode);L-next=NULL;for(i=n;i0;i-)p=(LinkList)malloc(sizeof)(LNode);scanf(&p-data);p-next=L-next;L-next=p;/CreatList_L12StatusInsert_SqList(SqList&va,intx)/把把x插入递增有序表插入递增有序表va中中if(va.length=va.listsize)return(OVERFLOW);for(i=va.length-1;va.elemix&i=0;i-)va.elemi+1=va.elemi;va.elemi+1=x;va.length+;returnOK;/Insert_SqList2.11设顺序表设顺序表va中的数据元素递增有序。试编写一算法，将中的数据元素递增有序。试编写一算法，将x插入到顺序表的适当位置上，以保持该表的有序性。插入到顺序表的适当位置上，以保持该表的有序性。二、作业点评二、作业点评132.14 试写一算法在带头结点的单链表结构上实现线性表操作试写一算法在带头结点的单链表结构上实现线性表操作 LENGTH(L LENGTH(L）。）。intLength(LinkListL)/求链表的长度求链表的长度p=L;k=0;while(p-next)p=p-next;k+;returnk;142.19已知线性表中的元素以值递增有序排列，并以单链表作存储已知线性表中的元素以值递增有序排列，并以单链表作存储结构。试写一高效的算法，删除表中所有值大于结构。试写一高效的算法，删除表中所有值大于minkmink且小于且小于maxkmaxk的元素（若表中存在这样的元素）同时释放被删结点空间，并分的元素（若表中存在这样的元素）同时释放被删结点空间，并分析算法时间复杂度（析算法时间复杂度（minkmink和和maxkmaxk是给定参变量）是给定参变量）StatusDelete_Between(Linklist&L,intmink,intmaxk)/删除递增链表删除递增链表L中值大于中值大于mink且小于且小于maxk的所有元素的所有元素if(L!=NULL)q=L;p=L-next;while(p!=NULL&p-datanext;while(p!=NULL&p-datanext;free(r);q-next=p;returnOK;/Delete_Between15三、习题讲解三、习题讲解例例1 1、已知线性表中元素无序，且采用带头结点的单链表存储结、已知线性表中元素无序，且采用带头结点的单链表存储结构，要求删除所有大于构，要求删除所有大于minmin且小于且小于maxmax的结点。的结点。StatusDelete_Between(Linklist&L,intmink,intmaxk)/删除无序单链表中所有删除无序单链表中所有大于大于minmin且小于且小于maxmax的结点的结点q=L;p=L-next;while(p)if(p-datadata=maxk)q=p;p=p-next;elseq-next=p-next;free(p);p=q-next;returnOK;/Delete_Between16例例2 2、有一单链表（不带头结点）头指针为、有一单链表（不带头结点）头指针为headhead，试设计一算试设计一算法使得单链表插入法使得单链表插入x x后仍递增有序。后仍递增有序。StatusInsert(Linklist&head,Elemtypex)/不带头结点单链表插入不带头结点单链表插入x x后仍递增有序后仍递增有序s=(LinkList)malloc(sizeof(Lnode);s-data=x;s-next=NULL;if(head=NULL|xdata)s-next=head;head=s;elseq=head;p=head-next;while(p!=NULL&p-datanext;s-next=p;q-next=s;returnOK;/Insert17StatusInsert(Linklist&head,Elemtypex)/带头结点单链表插入带头结点单链表插入x x后仍递增有序后仍递增有序s=(LinkList)malloc(sizeof(Lnode);s-data=x;s-next=NULL;q=head;p=head-next;if(p!=NULL&p-datanext;s-next=p;q-next=s;returnOK;/Insert18例例3 3、试分别以不同的存储结构实现线性表的就地逆转算法，、试分别以不同的存储结构实现线性表的就地逆转算法，即在原表的存储空间内将线性表即在原表的存储空间内将线性表 （a1,a2,.,ana1,a2,.,an）逆置为逆置为（an,an-1,.,a1an,an-1,.,a1）。）。（1）顺序存储结构）顺序存储结构/结构类型定义：结构类型定义：#defineLIST_INIT_SIZE100#defineLISTINCREMENT10typedefstructElemType*elem;intlength;intlistsize;Sqlist;19/算法算法voidreverse(SqList&L)/顺序表的就地逆置顺序表的就地逆置for(i=0,j=L.length-1;inext;/指向开始结点指向开始结点head-next=NULL;/逆置后初表为空逆置后初表为空while(p)/p为为NULL，表示已经全部逆置表示已经全部逆置q=p-next;/p指向下一个需要逆置的结点指向下一个需要逆置的结点p-next=head-next;/将需要逆置结点插入头结点后面将需要逆置结点插入头结点后面head-next=p;p=q;returnOK;/convert/算法算法22例例4 4、试在带头结点的单链表中值为、试在带头结点的单链表中值为x x的结点之后插入的结点之后插入m m个结点。个结点。/类型定义：类型定义：typedefstructLNodeElemtypedata;structLNode*next;LNode,*LinkList;23/算法实现算法实现StatusInsert(Linklist&head,Elemtypex,intm)/在在带头结点的单链表中值为带头结点的单链表中值为x x的结点之后插入的结点之后插入m m个结点个结点p=head-next;if(p=NULL)returnERROR;elsewhile(p-data!=x)p=p-next;q=p-next;for(i=1;idata=y;p-next=s;p=s;s-next=q;returnOK;/Insert