第2 章线性表习题练习答案.doc

第2 章线性表习题练习答案2.1 试描述头指针、头结点、开始结点的区别、并说明头指针和头结点的作用。答：开始结点是指链表中的第一个结点，也就是没有直接前趋的那个结点。链表的头指针是一指向链表开始结点的指针(没有头结点时)，单链表由头指针唯一确定，课后答案网 因此单链表可以用头指针的名字来命名。头结点是在链表的开始结点之前附加的一个结点。有了头结点之后，头指针指向头结点，不论链表否为空，头指针总是非空。而且头指针的设置使得对链表的第一个位置上的操作与在表其他位置上的操作一致(都是在某一结点之后)。2.2 何时选用顺序表、何时选用链表作为线性表的存储结构为宜?答：在实际应用中，应根据具体问题的要求和性质来选择顺序表或链表作为线性表的存储结构，通常有以下几方面的考虑：1.基于空间的考虑。当要求存储的线性表长度变化不大，易于事先确定其大小时，为了节约存储空间，宜采用顺序表；反之，当线性表长度变化大，难以估计其存储规模时，采用动态链表作为存储结构为好。2.基于时间的考虑。若线性表的操作主要是进行查找，很少做插入和删除操作时，采用顺序表做存储结构为宜；反之， 若需要对线性表进行频繁地插入或删除等的操作时，宜采用链表做存储结构。并且，若链表的插入和删除主要发生在表的首尾两端，则采用尾指针表示的单循环链表为宜。2.3 在顺序表中插入和删除一个结点需平均移动多少个结点?具体的移动次数取决于哪两个因素?答：在等概率情况下，顺序表中插入一个结点需平均移动n/2 个结点。删除一个结点需平均移动(n-1)/2 个结点。具体的移动次数取决于顺序表的长度n 以及需插入或删除的位置i。i越接近n 则所需移动的结点数越少。2.4 为什么在单循环链表中设置尾指针比设置头指针更好?答：尾指针是指向终端结点的指针，用它来表示单循环链表可以使得查找链表的开始结点和终端结点都很方便，设一带头结点的单循环链表，其尾指针为rear，则开始结点和终端结点的位置分别是rear-next-next 和rear, 查找时间都是O(1)。若用头指针来表示该链表，则查找终端结点的时间为O(n)。课后答案网 2.5 在单链表、双链表和单循环链表中，若仅知道指针p指向某结点，不知道头指针，能否将结点*p从相应的链表中删去?若可以，其时间复杂度各为多少?答：下面分别讨论三种链表的情况。1. 单链表。若指针p 指向某结点时，能够根据该指针找到其直接后继，能够顺后继指针链找到*p 结点后的结点。但是由于不知道其头指针，所以无法访问到p 指针指向的结点的直接前趋。因此无法删去该结点。2. 双链表。由于这样的链表提供双向指针，根据*p 结点的前趋指针和后继指针可以查找到其直接前趋和直接后继，从而可以删除该结点。其时间复杂度为O(1)。3. 单循环链表。根据已知结点位置，可以直接得到其后相邻的结点位置(直接后继)，又因为是循环链表，所以我们可以通过查找，得到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;return L;/ Demo答：该算法的功能是：将开始结点摘下链接到终端结点之后成为新的终端结点，而原来的第二个结点成为新的开始结点，返回新链表的头指针。2.7 设线性表的n个结点定义为(a0,a1,.an-1)，重写顺序表上实现的插入和删除算法：InsertList 和DeleteList.课后答案网 解：算法如下:#define ListSize 100 / 假定表空间大小为100typedef int DataType;/假定DataType 的类型为int 型typedef structDataType dataListSize;/ 向量data 用于存放表结点int length; / 当前的表长度 Seqlist;/以上为定义表结构void InsertList ( Seqlist *L, Datatype x, int i)/将新结点x 插入L 所指的顺序表的第i 个结点ai 的位置上，即插入的合法位置为：0=ilengthint j;if ( i L - length )Error(position error);/ 非法位置，退出，该函数定义见教材P7.if ( L-length=ListSize )Error(“overflow);for ( j=L-length-1 ; j = i ; j -)L-data j+1=L-data j ;L-data i =x ;L-length+ ;void DeleteList ( Seqlist *L, int i )/ 从L 所指的顺序表中删除第i 个结点ai,合法的删除位置为0=ilength-1int j;if ( i= L- length)Error( position error ) ;for ( j = i ; j length ; j+ )L-data j =L-data j+1; /结点前移L- length- ; /表长减小课后答案网 2.8 试分别用顺序表和单链表作为存储结构，实现将线性表(a0,a1,.an-1)就地逆置的操作，所谓就地指辅助空间应为O(1)。答：1. 顺序表：要将该表逆置，可以将表中的开始结点与终端结点互换，第二个结点与倒数第二个结点互换，如此反复，就可将整个表逆置了。算法如下：/ 顺序表结构定义同上题void ReverseList( Seqlist *L)DataType temp ; /设置临时空间用于存放dataint i;for (i=0;ilength/2;i+)/L-length/2 为整除运算 temp = L-datai; /交换数据L - data i = L - data L - length-1-i;L - data L - length - 1 - i = temp;2. 链表：分析：可以用交换数据的方式来达到逆置的目的。但是由于是单链表，数据的存取不是随机的，因此算法效率太低。可以利用指针改指来达到表逆置的目的。具体情况入下：(1)当链表为空表或只有一个结点时，该链表的逆置链表与原表相同。(2)当链表含2 个以上结点时，可将该链表处理成只含第一结点的带头结点链表和一个无头结点的包含该链表剩余结点的链表。然后，将该无头结点链表中的所有结点顺着链表指针，由前往后将每个结点依次从无头结点链表中摘下，作为第一个结点插入到带头结点链表中。这样就可以得到逆置的链表。算法是这样的：结点结构定义如下：typedef char DataType; /假设结点的数据域类型的字符课后答案网 typedef struct node /结点类型定义DataType data; /结点的数据域struct node *next;/结点的指针域ListNode;typedef ListNode *LinkList;ListNode *p;LinkList head;LinkList ReverseList( LinkList head )/ 将head 所指的单链表(带头结点)逆置ListNode *p ,*q ;/设置两个临时指针变量if( head-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; /如是空表或单结点表，直接返回head2.9 设顺序表L是一个递增有序表，试写一算法，将x插入L中，并使L仍是一个有序表。答：课后答案网 因已知顺序表L 是递增有序表，所以只要从顺序表终端结点（设为i 位置元素）开始向前寻找到第一个小于或等于x 的元素位置i 后插入该位置即可。在寻找过程中，由于大于x 的元素都应放在x 之后，所以可边寻找，边后移元素，当找到第一个小于或等于x 的元素位置i 时，该位置也空出来了。算法如下：/顺序表存储结构如题2.7void InsertIncreaseList( Seqlist *L , Datatype x )int i;if ( L-length=ListSize)Error(“overflow);for ( i=L - length ; i0 & L-data i-1 x ; i-)L-data i =L-data i ; / 比较并移动元素L-data i =x;L - length+;2.10 设顺序表L是一个递减有序表，试写一算法，将x插入其后仍保持L的有序性。答：与上题相类似，只要从终端结点开始往前找到第一个比x 大(或相等)的结点数据，在这个位置插入就可以了。（边寻找，边移动）算法如下：void InsertDecreaseList( Seqlist *L, Datatype x )int i;if ( L-length=ListSize)Error(“overflow);for ( i=L - length ; i0 & L-data i-1 data i =L-data i ; / 比较并移动元素L-data i =x;课后答案网 L - length+;2.11 写一算法在单链表上实现线性表的ListLength(L)运算。解：由于在单链表中只给出一个头指针，所以只能用遍历的方法来数单链表中的结点个数了。算法如下：int ListLength ( LinkList L )int len=0 ;ListNode *p;p=L; /设该表有头结点while ( p-next )p=p-next;len+;return len;2.12 已知L1和L2分别指向两个单链表的头结点，且已知其长度分别为m和n。试写一算法将这两个链表连接在一起，请分析你的算法的时间复杂度。解：分析：由于要进行的是两单链表的连接，所以应找到放在前面的那张表的表尾结点，再将后表的开始结点链接到前表的终端结点后即可。该算法的主要时间消耗是用在寻找第一张表的终端尾结点上。这两张单链表的连接顺序无要求，并且已知两表的表长，则为了提高算法效率，可选表长小的单链表在前的方式连接。具体算法如下：LinkList Link( LinkList L1 , LinkList L2，int m,int n )课后答案网 /将两个单链表连接在一起ListNode *p , *q, *s ;/s 指向短表的头结点,q 指向长表的开始结点，回收长表头结点空间if (mnext;free(L2);else s=L2;q=L1-next;free(L1);p=s;while ( p-next ) p=p-next; /查找短表终端结点p-next = q; /将长表的开始结点链接在短表终端结点后return s;本算法的主要操作时间花费在查找短表的终端结点上，所以本算的法时间复杂度为：O(min(m,n)2.13 设A和B是两个单链表，其表中元素递增有序。试写一算法将A和B归并成一个按元素值递减有序的单链表C，并要求辅助空间为O(1)，请分析算法的时间复杂度。解：根据已知条件，A 和B 是两个递增有序表，所以可以先取A 表的表头建立空的C 表。然后同时扫描A 表和B 表，将两表中最大的结点从对应表中摘下，并作为开始结点插入C表中。如此反复，直到A 表或B 表为空。最后将不为空的A 表或B 表中的结点依次摘下并作为开始结点插入C 表中。这时，得到的C 表就是由A 表和B 表归并成的一个按元素值递减有序的单链表C。并且辅助空间为O(1)。算法如下：LinkList MergeSort ( LinkList A , LinkList B )/ 归并两个带头结点的递增有序表为一个带头结点递减有序表ListNode *pa , *pb , *q , *C ;pa=A-next;/pa 指向A 表开始结点C=A;C-next=NULL;/取A 表的表头建立空的C 表pb=B-next;/pb 指向B 表开始结点free(B);/回收B 表的头结点空间课后答案网 while ( pa & pb)if ( pb-data data ) / 当B 中的元素小于等于A 中当前元素时，将pa 表的开始结点摘下q=pa;pa=pa-next;else/ 当B 中的元素大于A 中当前元素时，将pb 表的开始结点摘下q=pb;pb=pb-next;q-next=C-next;C-next=q;/将摘下的结点q 作为开始结点插入C 表/若pa 表非空，则处理pa 表while(pa)q=pa;pa=pa-next;q-next=C-next;C-next=q;/若pb 表非空，则处理pb 表while(pb)q=pb;pa=pb-next;q-next=C-next;C-next=q;return(C);该算法的时间复杂度分析如下：算法中有三个while 循环，其中第二个和第三个循环只执行一个。每个循环做的工作都是对链表中结点扫描处理。整个算法完成后，A 表和B 表中的每个结点都被处理了一遍。所以若A 表和B表的表长分别是m和n，则该算法的时间复杂度O(m+n)2.14 已知单链表L是一个递增有序表，试写一高效算法，删除表中值大于min 且小于max的结点(若表中有这样的结点)，同时释放被删结点的空间，这里min 和max是两个给定的参数。请分析你的算法的时间复杂度。解：课后答案网 要解这样的问题，我们首先想到的是拿链表中的元素一个个地与max 和min 比较，然后删除这个结点。由于为已知其是有序链表，则介于min 和max 之间的结点必为连续的一段元素序列。所以我们只要先找到所有大于min 结点中的最小结点的直接前趋结点*p 后，依次删除小于max 的结点，直到第一个大于等于max 结点*q 位置，然后将*p 结点的直接后继指针指向*q 结点。算法如下：void DeleteList ( LinkList L, DataType min , DataType max )ListNode *p , *q , *s;p=L;while( p-next & p-next-data next;q=p-next;/p 指向第一个不大于min 结点的直接前趋，q 指向第一个大于min 的结点while(q &q-datanext;free(s);/删除结点，释放空间p-next=q;/将*p 结点的直接后继指针指向*q 结点2.15 写一算法将单链表中值重复的结点删除，使所得的结果表中各结点值均不相同。解：本题可以这样考虑，先取开始结点中的值，将它与其后的所有结点值一一比较，发现相同的就删除掉，然后再取第二结点的值，重复上述过程直到最后一个结点。具体算法：void DeleteList ( LinkList L )ListNode *p , *q , *s;课后答案网 p=L-next;while( p-next&p-next-next)q=p;/由于要做删除操作，所以q 指针指向要删除元素的直接前趋while (q-next)if (p-data=q-next-data)s=q-next;q-next=s-next;free(s);/删除与*p 的值相同的结点else q=q-next;p=p-next;2.16 假设在长度大于1的单循环链表中，既无头结点也无头指针。s为指向链表中某个结点的指针，试编写算法删除结点*s的直接前趋结点。解：已知指向这个结点的指针是*s，那么要删除这个结点的直接前趋结点，就只要找到一个结点，它的指针域是指向*s 的直接前趋，然后用后删结点法，将结点*s 的直接前趋结点删除即可。算法如下：void DeleteNode( ListNode *s)/删除单循环链表中指定结点的直接前趋结点ListNode *p, *q;p=s;while( p-next-next!=s)p=p-next;/删除结点q=p-next;p-next=q-next;free(p); /释放空间课后答案网 注意：若单循环链表的长度等于1，则只要把表删空即可。2.17 已知由单链表表示的线性表中，含有三类字符的数据元素(如：字母字符、数字字符和其它字符)，试编写算法构造三个以循环链表表示的线性表，使每个表中只含同一类的字符，且利用原表中的结点空间作为这三个表的结点空间，头结点可另辟空间。解：要解决这样的问题，只要新建三个头结点，然后在原来的单链表中依次查询，找到一类字符结点时，就摘下此结点链接到相应头结点指明的新链表中就是了。算法如下：/设已建立三个带头结点的空循环链表A,B,C 且A、B、C 分别是尾指针.void DivideList( LinkList L, LinkList A, LinkList B, LinkList C)ListNode *p=L-next, *q;while ( p )if ( p-data=a &p-datadata=A &p-datanext;p=p-next;/指向下一结点q-next=A-next;/将字母结点链到A 表中A-next=q;A=q;else if( p-data=0 & p-datanext;p=p-next;/指向下一结点q-next=B-next;/将数字结点链到B 表中B-next=q;B=q;课后答案网 else /分出其他字符结点q=p-next;p=p-next;/指向下一结点q-next=C-next;/将其他结点链到C 表中C-next=q;C=q;/结束2.18 设有一个双链表，每个结点中除有prior、data和next三个域外，还有一个访问频度域freq，在链表被起用之前，其值均初始化为零。每当在链表进行一次LocateNode(L,x)运算时，令元素值为x的结点中freq域的值加1，并调整表中结点的次序，使其按访问频度的递减序排列，以便使频繁访问的结点总是靠近表头。试写一符合上述要求的LocateNode运算的算法。解：LocateNode 运算的基本思想就是在双向链表中查找值为x 的结点，具体方法与单链表中查找一样。找到结点*p 后给freq 域的值加1。由于原来比*p 结点查找频度高的结点都排它前面，所以，接下去要顺着前趋指针找到第一个频度小于或等于*p 结点频度的结点*q 后，将*p 结点从原来的位置删除，并插入到*q 后就可以了。算法如下：/双向链表的存储结构typedef struct dlistnodeDataType data;struct dlistnode *prior,*next;int freq;DListNode;typedef DListNode *DLinkList;void LocateNode( LinkList L, DataType x)课后答案网 ListNode *p, *q;p=L-next; /带有头结点while( p&p-data!=x )p=p-next;if (!p) ERROR(x is not in L);/双链表中无值为x 的结点else p-freq+;/freq 加1q=p-prior;/以q 为扫描指针寻找第一个频度大于或等于*p 频度的结点while(q!=L&q-freqfreq)q=q-prior;if (q-next!=p)/若* q 结点和*p 结点不为直接前趋直接后继关系，/则将*p 结点链到* q 结点后p-prior-next=p-next;/将*p 从原来位置摘下p-next-prior=p-prior;q-next-prior=p;/将*p 插入*q 之后。p-next=q-next;q-next=p;p-prior=q;