DS线性表习题参考解答.doc

1、第2章 线 性 表 习题参考解答一、 简答题1试描述头指针、头结点、开始结点的区别、并说明头指针和头结点的作用。【答】头指针：是指向链表中的第一个结点的指针。头结点：在开始结点之前附加上的一个结点。开始结点：链表的第一个结点。 头指针是一个指向地址的变量，用于表示一个链表的开始。引入头结点可以更加方便的进行链表是否为空的判断，同时方便了插入和删除结点。开始结点用于存储链表的第一个数据元素。2何时选用顺序表、何时选用链表作为线性表的存储结构为宜?【答】顺序表中查找元素、获取表长非常容易，但是，要插入或者删除一个元素却需要移动大量的元素；相反，链表中却是方便插入或者删除元素，在查找元素的是，需要进

2、行遍历。因此，当所涉及的问题常常进行查找等操作，而插入、删除相对较少的是，适合采用顺序表；当常常需要插入、删除的时候，适合采用链表。3为什么在单循环链表中设置尾指针比设置头指针更好?【答】在单循环链表中，设置尾指针，可以更方便的判断链表是否为空。4在单链表、双链表和单循环链表中，若仅知道指针p指向某结点，不知道头指针，能否将结点*p从相应的链表中删去?【答】本题分三种情况讨论：1、单链表：当知道指针p指向某结点时，能够根据该指针找到其直接后继，但是不知道头指针，因此不能找到该结点的直接前趋，因此，无法删除该结点。2、双链表：根据指针p可以找到该结点的直接前趋和直接后继，因此，能够删除该结点。3

3、、单循环链表：和双链表类似，根据指针p也可以找到该结点的直接前趋和直接后继，因此，也可以删除该结点。5下述算法的功能是什么? LinkList Demo(LinkList *L) /* L是无头结点单链表*/ LNode *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 */【答】将原来的第一个结点变成末尾结点，原来的第二个结点变成链表的第一个结点。二、算法设计题1试分别用顺序表和单链表作为存储结构，实现将线性表(a0,a1,.an-1)

4、就地逆置的操作，所谓就地指辅助空间应为O(1)。【答】分两种情况讨论如下。 顺序表：要将该表逆置，可以将表中的开始结点与终端结点互换，第二个结点与倒数第二个结点互换，如此反复，就可将整个表逆置了。算法如下：void reverlist(sequenlist *L) datatype t; /* 设置临时空间用于存放data */int i;for (i=0;ilength/2;i+) t=L-datai; /* 交换数据 */L-datai=L-dataL-length-1-i;L-dataL-length-1-i=t; 链表：可以利用指针的指向转换来达到表逆置的目的。算法是这样的：LinkL

5、ist *reverselist(LinkList *head)/* 将head 所指的单链表逆置 */ LNode *p,*q ; /* 设置两个临时指针变量 */ if(head-next!=NULL) & (head-next-next!=NULL) /* 当链表不是空表或单结点时 */ 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; retur

6、n head; /* 如是空表或单结点表，直接返回head */2顺序表L是一个递增有序表，试写一算法，将x插入L中，并使L仍是一个有序表。【答】因已知顺序表L是递增有序表，所以只要从头找起找到第一个比它大（或相等）的结点数据，把x插入到这个数所在的位置就是了。算法如下：void InsertIncreaseList( Sequenlist *L , Datatype x ) int i; for (i=0; ilength & L-datainext ) p=p-next; /* 查找终端结点 */ p-next = q-next ; /* 将L2的开始结点链接在L1之后 */ return

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

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

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

10、到最后的，也就是说需要把A中元素和B中元素全部检查比较过，这时的所费时间就是m+n. 而新链表的长度也是m+n+1 (有头结点)，这样逆置函数的执行所费时间为m+n+1。所以可得整个算法的时间复杂度为：m+n+m+n+1=2(m+n)+1= O(m+n)6试编写一算法将单链表中值重复的结点删除，使所得的结果表中各结点值均不相同。已知由单链表表示的线性表中，含有三类字符的数据元素(如：字母字符、数字字符和其它字符)，试编写算法构造三个以循环链表表示的线性表，使每个表中只含同一类的字符，且利用原表中的结点空间作为这三个表的结点空间，头结点可另辟空间。【答】本题分为两个部分，第一部分是删除重复结点，

11、第二部分链表的分解。首先看第一部分：要删除重复结点，有两种方式，第一种方式：先取开始结点中的值，将它与其后的所有结点值一一比较，发现相同的就删除掉，然后再取第二结点的值，重复上述过程直到最后一个结点。第二种方式：将单链表按值的大小排序，排好后的结点按相同的删除。我们这里给出第一种方式的算法，如下所示：void sc(LinkList *head) LinkList *p,*q,*w;p=head-next; while(p!=NULL) q=p-next; w=p; while(q!=NULL) /*比较p所指节点的值与链表中后续节点的值，不相等q指针后移,相等则删除*/ if (p-data

12、!=q-data)w=q;q=q-next; else w-next=q-next;w=q;q=q-next; p=p-next; 第二部分：本部分的思路和第一部分类似，首先构造三个新的链表，然后遍历原链表，检测每一个元素，如果是第一类元素，则把该结点从原链表中删除，但是不释放空间，而是添加到第一个新链表中；同样的，如果是第二类元素，则添加到第二个新链表中；以此类推，直到所有的节点都检测完毕。具体算法如下：void split(LinkList *ha) LinkList *hb,*hc,*ra,*rb,*rc,*p; char c; hb=(linklist*)malloc(sizeof(l

13、inklist); hc=(linklist*)malloc(sizeof(linklist); p=ha-next; ra=pa; ra-next=NULL; rb=hb; rb-next=NULL; rc=hc; rc-next=NULL; while(p!=ha) c=p-data; if (c=a& c=C & cnext=p;ra=p; else if(c=0 & cnext=p; rb=p;else rc-next=p; rc=p;p=p-next; ra-next=ha;rb-next=hb;rc-=next=hc; 7设在长度大于1的单循环链表中，既无头结点也无头指针。s为指向链表中某个结点的指针，试编写算法删除结点*s的直接前趋结点。【答】已知指向这个结点的指针是*s，那么要删除这个结点的直接前趋结点，就只要找到一个结点，它的指针域是指向*s的，把这个结点删除就可以了。算法如下：void DeleteNode(LinkList *s) /* 删除单循环链表中指定结点的直接前趋结点 */LinkList *p, *q;p=s;while( p-next-next!=s) q=p; /p=p-next;q-next=s; /删除结点free(p); /释放空间