第二章-线性表----------习题及答案.doc

《第二章-线性表----------习题及答案.doc》由会员分享，可在线阅读，更多相关《第二章-线性表----------习题及答案.doc（12页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、精品文档，仅供学习与交流，如有侵权请联系网站删除第二章 线性表 习题及答案 一、基础知识题2.1 试描述头指针、头结点、开始结点的区别、并说明头指针和头结点的作用。答：始结点是指链表中的第一个结点，也就是没有直接前趋的那个结点。链表的头指针是一指向链表开始结点的指针(没有头结点时)，单链表由头指针唯一确定，因此单链表可以用头指针的名字来命名。头结点是我们人为地在链表的开始结点之前附加的一个结点。有了头结点之后，头指针指向头结点，不论链表否为空，头指针总是非空。而且头指针的设置使得对链表的第一个位置上的操作与在表其他位置上的操作一致(都是在某一结点之后)。2.2 何时选用顺序表、何时选用链表作为

2、线性表的存储结构为宜?答：在实际应用中，应根据具体问题的要求和性质来选择顺序表或链表作为线性表的存储结构，通常有以下几方面的考虑：1.基于空间的考虑。当要求存储的线性表长度变化不大，易于事先确定其大小时，为了节约存储空间，宜采用顺序表；反之，当线性表长度变化大，难以估计其存储规模时，采用动态链表作为存储结构为好。2.基于时间的考虑。若线性表的操作主要是进行查找，很少做插入和删除操作时，采用顺序表做存储结构为宜；反之， 若需要对线性表进行频繁地插入或删除等的操作时，宜采用链表做存储结构。并且，若链表的插入和删除主要发生在表的首尾两端，则采用尾指针表示的单循环链表为宜。2.3 在顺序表中插入和删除

3、一个结点需平均移动多少个结点?具体的移动次数取决于哪两个因素?答：在等概率情况下，顺序表中插入一个结点需平均移动n/2个结点。删除一个结点需平均移动(n-1)/2个结点。具体的移动次数取决于顺序表的长度n以及需插入或删除的位置i。i越接近n则所需移动的结点数越少。2.4 为什么在单循环链表中设置尾指针比设置头指针更好?答：尾指针是指向终端结点的指针，用它来表示单循环链表可以使得查找链表的开始结点和终端结点都很方便，设一带头结点的单循环链表，其尾指针为rear，则开始结点和终端结点的位置分别是rear-next-next 和 rear, 查找时间都是O(1)。若用头指针来表示该链表，则查找终端结

4、点的时间为O(n)。2.5 在单链表、双链表和单循环链表中，若仅知道指针p指向某结点，不知道头指针，能否将结点*p从相应的链表中删去?若可以，其时间复杂度各为多少?答：我们分别讨论三种链表的情况。1. 单链表。当我们知道指针p指向某结点时，能够根据该指针找到其直接后继，但是由于不知道其头指针，所以无法访问到p指针指向的结点的直接前趋。因此无法删去该结点。2. 双链表。由于这样的链表提供双向链接，因此根据已知结点可以查找到其直接前趋和直接后继，从而可以删除该结点。其时间复杂度为O(1)。3. 单循环链表。根据已知结点位置，我们可以直接得到其后相邻的结点位置(直接后继)，又因为是循环链表，所以我们

5、可以通过查找，得到p结点的直接前趋。因此可以删去p所指结点。其时间复杂度应为O(n)。2.6 下述算法的功能是什么?LinkList Demo(LinkList L) / L 是无头结点单链表 ListNode *Q,*P; if(L&L-next) Q=L;L=L-next;P=L; while (P-next) P=P-next; P-next=Q; Q-next=NULL; 答：该算法的功能是：将开始结点摘下链接到终端结点之后成为新的终端结点，而原来的第二个结点成为新的开始结点，返回新链表的头指针。二、算法设计题2.7 设线性表的n个结点定义为(a0,a1,.an-1)，重写顺序表上实现

6、的插入和删除算法：InsertList 和DeleteList.解：算法如下:#define ListSize 100/ 假定表空间大小为100#include #include void Error(char * message)fprintf(stderr,错误:%sn,message);exit(1);/从0开始计， 表空间大小应为101了typedef int Datatype ;/假定Datatype的类型为int型typedef structDatatype dataListSize;/ 向量data用于存放表结点int length; / 当前的表长度 Seqlist;/以上为定

7、义表结构/-以下为要求算法-void InsertList ( Seqlist *L, Datatype x, int i)/将新结点x插入L所指的顺序表的第i个结点ai的位置上int j;if ( i L - length )Error(position error);/ 非法位置，退出if ( L-length=ListSize )Error(overflow);for ( j=L-length-1 ; j = i ; j -)L-dataj+1=L-data j;L-datai=x ;L-length+ ;void DeleteList ( Seqlist *L, int i )/ 从L

8、所指的顺序表中删除第i个结点aiint j;if ( i L- length-1)Error( position error ) ;for ( j = i+1 ; j length ; j+ )L-data j-1 =L-data j; / 结点前移L- length- ; /表长减小/=以下为验证算法而加=void Initlist(Seqlist *L)L-length=0;void main()Seqlist *SEQA=new Seqlist;Initlist(SEQA);int i;for (i=0;idatai);DeleteList (SEQA,99);for (i=0;idat

9、ai);2.8 试分别用顺序表和单链表作为存储结构，实现将线性表(a0,a1,.an-1)就地逆置的操作，所谓就地指辅助空间应为O(1)。解：按题意，为将线性表逆置，但辅助空间不能随表的规模增大。我们分别讨论顺序表和单链表的情况：1. 顺序表：要将该表逆置，可以将表中的开始结点与终端结点互换，第二个结点与倒数第二个结点互换，如此反复，就可将整个表逆置了。算法如下： / 表结构定义同上void ReverseList( Seqlist *L)Datatype t ; /设置临时空间用于存放dataint i;for ( i=0 ; i length/2 ; i+) t = L-datai; /交

10、换数据L - data i = L - data L - length - 1 - i ;L - data L - length - 1 - i = t ; 2. 链表：也是可以用交换数据的方式来达到逆置的目的，但是由于是单链表，数据的存取不是随机的，因此算法效率太低，我们可以利用指针的指向转换来达到表逆置的目的。算法是这样的：/ 结构定义略LinkList ReverseList( LinkList head )/ 将head 所指的单链表逆置ListNode *p ,*q ;/设置两个临时指针变量if( head-next & head-next-next)/当链表不是空表或单结点时p=h

11、ead-next;q=p-next;p - next=NULL; /将开始结点变成终端结点while (q) /每次循环将后一个结点变成开始结点p=q; q=q-next ;p-next = head- next ;head-next = p;return head;return head; /如是空表或单结点表，直接返回head2.9 设顺序表L是一个递增有序表，试写一算法，将x插入L中，并使L仍是一个有序表。解：因已知顺序表L是递增有序表，所以只要从头找起找到第一个比它大(或相等)的结点数据，把x插入到这个数所在的位置就是了。算法如下：void InsertIncreaseList( Se

12、qlist *L , Datatype x )int i;for ( i=0 ; i length & L-data i next & p-next-datax )p=p-next;s=(ListNode *)malloc(sizeof(ListNode);s-data=x;s-next=p-next;p-next=s;return L;2.11 写一算法在单链表上实现线性表的ListLength(L)运算。解：求单链表长只能用遍历的方法了，从头数到尾，总能数出来吧。算法如下：int ListLength ( LinkList L )int len=0 ;ListNode *p;p=L; /设

13、该表有头结点while ( p-next )p=p-next;len+;return len;2.12 已知L1和L2分别指向两个单链表的头结点，且已知其长度分别为m和n。试写一算法将这两个链表连接在一起，请分析你的算法的时间复杂度。解：算法如下:LinkList Link( LinkList L1 , LinkList L2 )/将两个单链表连接在一起ListNode *p , *q ;p=L1;q=L2;while ( p-next ) p=p-next; /查找终端结点p-next = q-next ; /将L2的开始结点链接在L1之后return L1 ;本算法的主要操作时间花费在查找

14、L1的终端结点上，与L2的长度无关，所以本算的法时间复杂度为：m+1=O(m)2.13 设 A和B是两个单链表，其表中元素递增有序。试写一算法将A和B归并成一个按元素值递减有序的单链表C，并要求辅助空间为O(1)，请分析算法的时间复杂度。解：根据已知条件，A和B是两个递增有序表，所以我们可以以A表为基础，按照插入单个元素的办法把B表的元素插入A表中，完成后，将表逆置就得到了一个按元素值递减有序的单链表C了。算法如下：LinkList MergeSort ( LinkList A , LinkList B )/ 归并两个递增有序表为一个递减有序表ListNode *pa , *pb , *qa

15、, *qb ;pa=A;pb=B ;qa=A-next;qb=B-next;while ( qa & qb)if ( qb-data data )/ 当B中的元素小于A中当前元素时，插入到它的前面pb=qb; qb=qb-next ;/ 指向B中下一元素pa-next=pb;pb-next=qa;pa=pb;else if ( qb-data = pa-data & qb-data data)/ 当B中元素大于等于A中当前元素/ 且小于等于A中后一元素时，/ 将此元素插入到A的当前元素之后 pa=qa;qa=qa-next; / 保存A的后一元素位置pb=qb; qb=qb-next; / 保

16、存B的后一元素位置pa-next=pb; /插入元素pb-next=qa;else / 如果B中元素总是更大,指针移向下一个A元素pa=qa;qa=qa-next;if ( qb ) / 如果A表已到终端而B表还有结点未插入/ 将B表接到A表后面pa-next=qb;LinkList C=ReverseList ( A );/ 调用前面2.8题所设计的逆置函数return C; /返回新的单链表C, 已是递减排列该算法的时间复杂度分析如下：算法中只有一个while 循环，在这个循环中，按照最坏的情况是B元素既有插到A的最前的，也有插到最后的，也就是说需要把A中元素和B中元素全部检查比较过，这时

17、的所费时间就是m+n. 而新链表的长度也是m+n+1 (有头结点)，这样逆置函数的执行所费时间为m+n+1.所以可得整个算法的时间复杂度为：m+n+m+n+1=2(m+n)+1= O(m+n)为验证本题设计了一个程序，清单如下：/ListStruct.h 将链表结构存为头文件typedef char DataType; /假设结点的数据类型是字符型typedef struct node /结点类型定义DataType data;struct node *next;/结点的指针域ListNode;typedef ListNode * LinkList;/ 以下是源文件 / 在VC+中运行通过。#

18、include #include #include ListStruct.h#include LinkList CreatList (void) /用尾插法建立带头结点的单链表char ch;LinkList head = (LinkList)malloc(sizeof( ListNode); /生成头结点ListNode *s , *r;r=head;/尾指针亦指向头结点while (ch=getchar()!=n)s=(ListNode *) malloc (sizeof(ListNode);s-data=ch;r-next=s;r=s;r-next=NULL;return head;vo

19、id OutList( LinkList L)ListNode *p;p=L;while (p-next)cout next-data next;cout next & head-next-next) /当链表不是空表或单结点时p=head-next;q=p-next;p - next=NULL; /将开始结点变成终端结点while (q) /每次循环将后一个结点变成开始结点p=q; q=q-next ;p-next = head- next ;head-next = p;return head;return head; /直接返回headLinkList MergeSort ( LinkLi

20、st A , LinkList B )/ 归并两个递增有序表为一个递减有序表ListNode *pa , *pb , *qa , *qb ;pa=A;pb=B ;qa=A-next;qb=B-next;while ( qa & qb)if ( qb-data data )/ 当B中的元素小于A中当前元素时，插入到它的前面pb=qb; qb=qb-next ;/ 指向B中下一元素pa-next=pb;pb-next=qa;pa=pb;else if ( qb-data = pa-data & qb-data data)/ 当B中元素大于等于A中当前元素/ 且小于等于A中后一元素时，/ 将此元素插

21、入到A的当前元素之后 pa=qa;qa=qa-next; / 保存A的后一元素位置pb=qb; qb=qb-next; / 保存B的后一元素位置pa-next=pb; /插入元素pb-next=qa;else / 如果B中元素总是更大,指针移向下一个A元素pa=qa;qa=qa-next;if ( qb ) / 如果A表已到终端而B表还有结点未插入/ 将B表接到A表后面pa-next=qb;LinkList C=ReverseList ( A );/ 调用前面2.8题所设计的逆置函数return C; /返回新的单链表C, 已是递减排列void main()LinkList A, B, C;A

22、=CreatList();OutList (A);B=CreatList();OutList (B);C=MergeSort (A ,B);OutList (C);以下是一位学友鲁周航提供的算法：我的算法思路为：当A、B都不空时，各取A、B表中的第一个结点比较，哪个值小，就把它用头插法插入C表。（利用原来的头结点，始终是取第一个结点比较）继续取值比较。当A表为空，或B表为空，则把剩余结点用头插法插入C表。void LinkList(Nodetype *A,Nodetype *B, Nodetype *C)/假设A和B已建立，C表的头结点已初始化Nodetype *p, *q;p=A-Next;

23、q=B-Next;while(p&q)/两表中都有数if(p-DataData)/如A中的结点值大于B中结点值A-Next=p-Next;/A指向A表的下一个结点p-Next=C-Next;/把P的结点用头插法，插入C表。C-Next=p;p=A-Next;/P指向A表的第一个结点，继续比较elseB-Next=q-Next;/算理同上面q-Next=C-Next;C-Next=q;q=B-Next;if(p)/如A表还有结点，则把剩余结点，用头插法插入C表while(p)A-Next=p-Next;p-Next=C-Next;C-Next=p;p=A-Next;elseif(q)/如B表还有

24、结点，则把剩余结点，用头插法插入B表while(q)B-Next=q-Next;q-Next=C-Next;C-Next=q;q=B-Next;free(A);/释放原头结点空间free(B);你的算法要排表两次，第一次为插入，第二次为逆序。2.14 已知单链表L是一个递增有序表，试写一高效算法，删除表中值大于min 且小于max的结点(若表中有这样的结点)，同时释放被删结点的空间，这里min 和 max是两个给定的参数。请分析你的算法的时间复杂度。解：要解这样的问题，我们首先想到的是拿链表中的元素一个个地与max和min比较，然后删除这个结点，其实因为已知其是有序链表，所以我们只要找到大于m

25、in的结点的直接前趋结点，再找到小于max的结点，然后一并把中间的全部摘掉就可以了。 算法如下：void DeleteList ( LinkList L, DataType min , DataType max )ListNode *p , *q ,*r;p=L-next;while( p & p-data next;while( p & p-data next;free(r);/释放这个结点空间q-next=p; /把断点链上周鲁航的算法：void DeleteList(Nodetype *L,int min,int max)Nodetype *p,*q;if(L-Next=NULL)pri

26、ntf(空表n);exit(0);p=L;while(p-Next!=NULL) /如p的下一个结点值在删除范围内if(p-Next-Datamin&p-Next-DataNext;/q 指向被删结点p-Next=q-Next;/从表中摘下被删结点free(q);/释放空间else/否则不在范围中。if(p-Next-Datamax)/如值已经超出范围，则跳出循环，结束删除break;elsep=p-Next;/当下一个值小于min时，继续查找。2.15 写一算法将单链表中值重复的结点删除，使所得的结果表中各结点值均不相同。解：本题 可以这样考虑，先取开始结点中的值，将它与其后的所有结点值一一

27、比较，发现相同的就删除掉，然后再取第二结点的值，重复上述过程直到最后一个结点。第二种算法是将单链表按值的大小排序，排好后的结点按相同的删除。以下为周鲁航提供的算法void DeleteList(Nodetype *L)Nodetype *p,*q,*s;if(L-Next=NULL|L-Next=NULL)printf(删除错误n);exit(0);p=L-Next;q=p-Next;while(p-Next!=NULL)while(q)s=q;if(q-Data=p-Data)s-Next=q-Next;free(q);q=s-Next;elseq=q-Next;p=p-Next; 2.16

28、 假设在长度大于1的单循环链表中，既无头结点也无头指针。s为指向链表中某个结点的指针，试编写算法删除结点*s的直接前趋结点。解：已知指向这个结点的指针是*s，那么要删除这个结点的直接前趋结点，就只要找到一个结点，它的指针域是指向*s的，把这个结点删除就可以了。算法如下：void DeleteNode( ListNode *s)/删除单循环链表中指定结点的直接前趋结点ListNode *p, *q;p=s;while( p-next!=s) q=p; p=p-next;q-next=s; /删除结点free(p); /释放空间2.17 已知由单链表表示的线性表中，含有三类字符的数据元素(如：字母

29、字符、数字字符和其它字符)，试编写算法构造三个以循环链表表示的线性表，使每个表中只含同一类的字符，且利用原表中的结点空间作为这三个表的结点空间，头结点可另辟空间。解：要解决这样的问题，只要新建三个头结点，然后在原来的单链表中依次查询，找到一类字符结点时，就摘下此结点链接到相应头结点指明的新链表中就是了。算法如下：/设已建立三个带头结点的空循环链表A,B,C./以下是void DivideList( LinkList L, LinkList A, LinkList B, LinkList C)ListNode *p=L-next, *q;ListNode *a=A,ListNode *b=B;L

30、istNode *c=C;while ( p )if ( p-data=a &p-datadata=A &p-datanext;/指向下一结点a-next=q;/将字母结点链到A表中q-next=A;/ 形成循环链表a=a-next; / 指向下一结点else if( p-data=0 & p-datanext;b-next=q;q-next=B;b=b-next;else /分出其他字符结点q=p;p=p-next;c-next=q;q-next=C;c=c-next;2.18 设有一个双链表，每个结点中除有prior、data和next三个域外，还有一个访问频度域freq，在链表被起用之前

31、，其值均初始化为零。每当在链表进行一次LocateNode(L,x)运算时，令元素值为x的结点中freq域的值加1，并调整表中结点的次序，使其按访问频度的递减序排列，以便使频繁访问的结点总是靠近表头。试写一符合上述要求的LocateNode运算的算法。解：给freq域的值加1比较容易。就是每次加1后需进行排序比较麻烦。我们可以这样考虑，每次访问一个值为x的结点后，从表头开始找，根据结点中的freq值，如果找到比它小的结点，就把当前结点摘下，插入到freq值比它小的结点前面，就完成排序了。算法如下：void LocateNode( LinkList L, DataType x)ListNode

32、*p, *q;p=L-next; /带有头结点q=L-next;while( p )if( p-data!=x) p=p-next;else p-freq+;break;while ( q )if( q-freq p-freq) q=q-next;else p-prior-next=p-next; /摘下当前结点p-next=q; /插入到freq不大于它的结点前p-prior=q-prior;(附：双循环链表的相应算法) 2.18 周鲁航算法思路为：当找到要找的值时，freq+计数。比较当前结点前的所有结点的freq，(因为总是把访问次数多的放在前面，因此该结点后的所有结点的freq值一定小

33、于等于它，就不必比较了。所以只要比较前面的就行了)如果X结点的freq值大于等于它，就把当前结点摘下后，插入到它前面位置。void LocateNode(Nodetype *L,char x)Nodetype *p,*q;p=L-Next;while(p!=L&p-Data!=x)/查找值为X的结点位置p=p-Next;if(p-Data=x)/如找到了结点的位置p-freq+;/计数访问的次数q=L-Next;while(q!=p&p-freqfreq)/比较X结点前的所有结点的freq值，当X结点/的freq值大于等于前面结点中freq值时，停止。q=q-Next;if(p-freq=q-freq&q!=p)/如果X结点的freq值大于等于前面结点中freq值/摘下X结点，插入刚才找到的位置前面p-Next-prior=p-prior;/摘下X结点p-prior-Next=p-Next;/把结点插入q所指结点的前面p-Next=q; p-prior=q-prior;q-prior=p;p-prior-Next=p; elseprintf(查无此值n);【精品文档】第 12 页