第2章线性表

第2章线性表教材中练习题及参考答案1.简述线性表两种存储结构各自的主要特点。答：线性表的两种存储结构分别是顺序存储结构和链式存储结构。顺序存储结构的主要特点如下：①数据元素中只有自身的数据域，没有关联指针域。因此，顺序存储结构的存储密度较大。②顺序存储结构需要分配一整块比较大存储空间，所以存储空间利用率较低。③逻辑上相邻的两个元素在物理上也是相邻的，通过元素的逻辑序号可以直接其元素值，即具有随机存取特性。④插入和删除操作会引起大量元素的移动。链式存储结构的主要特点如下：①数据结点中除自身的数据域，还有表示逻辑关系的指针域。因此，链式存储结构比顺序存储结构的存储密度小。②链式存储结构的每个结点是单独分配的，每个结点的存储空间相对较小，所以存储空间利用率较高。③在逻辑上相邻的结点在物理上不一定相邻，因此不具有随机存取特性。④插入和删除操作方便灵活，不必移动结点，只需修改结点中的指针域即可。2.简述单链表设置头结点的主要作用。答：对单链表设置头结点的主要作用如下：①对于带头结点的单链表，在单链表的任何结点之前插入结点或删除结点，所要做的都是修改前一个结点的指针域，因为任何结点都有前驱结点（若单链表没有头结点，则首结点没有前驱结点，在其前插入结点和删除该结点时操作复杂些），所以算法设计方便。②对于带头结点的单链表，在表空时也存在一个头结点，因此空表与非空表的处理是一样的。3.假设某个含有n个元素的线性表有如下运算：Ⅰ.查找序号为i（1≤i≤n）的元素Ⅱ.查找第一个值为x的元素Ⅲ.插入新元素作为第一个元素Ⅳ.插入新元素作为最后一个元素Ⅴ.插入第i（2≤i≤n）个元素2数据结构教程学习指导Ⅵ.删除第一个元素Ⅶ.删除最后一个元素Ⅷ.删除第i（2≤i≤n）个元素现设计该线性表的如下存储结构：①顺序表②带头结点的单链表③带头结点的循环单链表④不带头结点仅有尾结点指针标识的循环单链表⑤带头结点的双链表⑥带头结点的循环双链表指出各种存储结构中对应运算算法的时间复杂度。答：各种存储结构对应运算的时间复杂度如表2.1所示。表2.1各种存储结构对应运算的时间复杂度ⅠⅡⅢⅣⅤⅥⅦⅧ①O(1)O(n)O(n)O(1)O(n)O(n)O(1)O(n)②O(n)O(n)O(1)O(n)O(n)O(1)O(n)O(n)③O(n)O(n)O(1)O(n)O(n)O(1)O(n)O(n)④O(n)O(n)O(1)O(1)O(n)O(1)O(n)O(n)⑤O(n)O(n)O(1)O(n)O(n)O(1)O(n)O(n)⑥O(n)O(n)O(1)O(1)O(n)O(1)O(1)O(n)4.对于顺序表L，指出以下算法的功能。voidfun(SqList*&L){inti,j=0;for(i=1;iL-length;i++)if(L-data[i]L-data[j])j=i;for(i=j;iL-length-1;i++)L-data[i]=L-data[i+1];L-length--;}答：该算法的功能是在顺序表L中查找第一个值最大的元素，并删除该元素。5.对于顺序表L，指出以下算法的功能。voidfun(SqList*&L,ElemTypex){inti,j=0;for(i=1;iL-length;i++)if(L-data[i]=L-data[j])j=i;for(i=L-length;ij;i--)L-data[i]=L-data[i-1];L-data[j]=x;L-length++;第2章线性表3}答：在顺序表L中查找最后一个值最小的元素，在该位置上插入一个值为x的元素。6.有人设计如下算法用于删除整数顺序表L中所有值在[x，y]范围内的元素，该算法显然不是高效的，请设计一个同样功能的高效算法。voidfun(SqList*&L,ElemTypex){inti,j;for(i=0;iL-length;i++)if(L-data[i]=x&&L-data[i]=y){for(j=i;jL-length-1;j++)L-data[j]=L-data[j+1];L-length--;}}答：该算法在每次查找到x元素时，都通过移动来删除它，时间复杂度为O(n2)，显然不是高效的算法。实现同样功能的算法如下：voidfun(SqList*&L,ElemTypex,ElemTypey){inti,k=0;for(i=0;iL-length;i++)if(!(L-data[i]=x&&L-data[i]=y)){L-data[k]=L-data[i];k++;}L-length=k;}该算法（思路参见《教程》例2.3的解法一）的时间复杂度为O(n)，是一种高效的算法。7.设计一个算法，将元素x插入到一个有序（从小到大排序）顺序表的适当位置上，并保持有序性。解：通过比较在顺序表L中找到插入x的位置i，将该位置及后面的元素均后移一个位置，将x插入到位置i中，最后将L的长度增1。对应的算法如下：voidInsert(SqList*&L,ElemTypex){inti=0,j;while(iL-length&&L-data[i]x)i++;for(j=L-length-1;j=i;j--)L-data[j+1]=L-data[j];L-data[i]=x;L-length++;}8.假设一个顺序表L中所有元素为整数，设计一个算法调整该顺序表，使其中所有小于零的元素放在所有大于等于零的元素的前面。解：先让i、j分别指向顺序表L的第一个元素和最后一个元素。当ij时循环：i从前向后扫描顺序表L，找大于等于0的元素，j从后向前扫描顺序表L，找小于0的元素，当ij时将两元素交换（思路参见《教程》例2.4的解法一）。对应的算法如下：4数据结构教程学习指导voidfun(SqList*&L){inti=0,j=L-length-1;while(ij){while(L-data[i]0)i++;while(L-data[j]=0)j--;if(ij)//L-data[i]与L-data[j]交换swap(L-data[i],L-data[j]);}}9.对于不带头结点的单链表L1，其结点类在为LinkNode，指出以下算法的功能。voidfun1(LinkNode*&L1,LinkNode*&L2){intn=0,i;LinkNode*p=L1;while(p!=NULL){n++;p=p-next;}p=L1;for(i=1;in/2;i++)p=p-next;L2=p-next;p-next=NULL;}答：对于含有n个结点的单链表L1，将L1拆分成两个不带头结点的单链表L1和L2，其中L1含有原来的前n/2个结点，L2含有余下的结点。10.在结点类型为DLinkNode的双链表中，给出将p所指结点（非尾结点）与其后继结点交换的操作。答：将p所指结点（非尾结点）与其后继结点交换的操作如下：q=p-next;//q指向结点p的后继结点if(q-next!=NULL)//从链表中删除结点pq-next-prior=p;p-next=q-next;p-prior-next=q;//将结点q插入到结点p的前面q-prior=p-prior;q-next=p;p-prior=q;11.有一个线性表(a1，a2，…，an)，其中n≥2，采用带头结点的单链表存储，头指针为L，每个结点存放线性表中一个元素，结点类型为（data，next），现查找某个元素值等于x的结点指针，若不存在这样的结点返回NULL。分别写出下面3种情况的查找语句。要求时间尽量少。（1）线性表中元素无序。（2）线性表中元素按递增有序。（3）线性表中元素按递减有序。答：（1）元素无序时的查找语句如下：第2章线性表5p=L-next;while(p!=NULL&&p-data!=x)p=p-next;if(p==NULL)returnNULL;elsereturnp;（2）元素按递增有序时的查找语句如下：p=L-next;while(p!=NULL&&p-datax)p=p-next;if(p==NULL||p-datax)returnNULL;elsereturnp;（3）元素按递减有序时的查找语句如下：p=L-next;while(p!=NULL&&p-datax)p=p-next;if(p==NULL||p-datax)returnNULL;elsereturnp;12.设计一个算法，将一个带头结点的数据域依次为a1、a2、…、an（n≥3）的单链表的所有结点逆置，即第一个结点的数据域变为an，第2个结点的数据域变为an-1，…，尾结点的数据域为a1。解：首先让p指针指向首结点，将头结点的next域设置为空，表示新建的单链表为空表。用p扫描单链表的所有数据结点，将结点p采用头插法插入到新建的单链表中。对应的算法如下：voidReverse(LinkNode*&L){LinkNode*p=L-next,*q;L-next=NULL;while(p!=NULL)//扫描所有的结点{q=p-next;//q临时保存p结点的后继结点p-next=L-next;//总是将p结点作为首结点插入L-next=p;p=q;//让p指向下一个结点}}13.一个线性表（a1，a2，…，an）（n3）采用带头结点的单链表L存储。设计一个高效算法求中间位置的元素（即序号为n/2的元素）。解：让p、q首先指向首结点，然后在p结点后面存在两个结点时循环：p后移两个结点，q后移一个结点。当循环结束后，q指向的就是中间位置的结点，对应的算法如下：ElemTypeMidnode(LinkNode*L){LinkNode*p=L-next,*q=p;while(p-next!=NULL&&p-next-next!=NULL){p=p-next-next;q=q-next;}returnq-data;6数据结构教程学习指导}14.设计一个算法在带头结点的非空单链表L中第一个最大值结点（最大值结点可能有多个）之前插入一个值为x的结点。解：先在单链表L中查找第一个最大值结点的前驱结点maxpre，然后在其后面插入值为x的结点。对应的算法如下：voidInsertbeforex(LinkNode*&L,ElemTypex){LinkNode*p=L-next,*pre=L;LinkNode*maxp=p,*maxpre=L,*s;while(p!=NULL){if(maxp-datap-data){maxp=p;maxpre=pre;}pre=p;p=p-next;}s=(LinkNode*)malloc(sizeof(LinkNode));s-data=x;s-next=maxpre-next;maxpre-next=s;}15.设有一个带头结点的单链表L，结点的结构为（data，next），其中data为整数元素，next为后继结点的指针。设计一个算法，首先按递减次序输出该单链表中各结点的数据元素，然后释放所有结点占用的存储空间，并要求算法的空间复杂度为O(1)。解：先对单链表L的所有结点递减排序（思路参见《教程》例2.8），再输出所有结点值，最后释放所有结点的空间。对应的算法如下：voidSort(LinkNode*&L)//对单链表L递减排序{LinkNode*p,*q,*pre;p=L-next-next;//p指向第2个数据结点L-next-next=NULL;while(p!=NULL){q=p-next;pre=L;while(pre-next!=NULL&&pre-next-datap-data)pre=pre-next;p-next=pre-next;//在结点pre之后插入p结点