DS线性表习题参考解答

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试分别用顺序表和单链表

4、作为存储结构，实现将线性表 (a 0,a 1,.a n-1) 就地逆置的操作，所谓 就地 指辅助空间应为 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

5、=t; 链表：可以利用指针的指向转换来达到表逆置的目的。算法是这样的：LinkList *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

6、;head-next=p;return head;return 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

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

8、t(LinkList *A , LinkList *B ) /* 归并两个递增有序表为一个递减有序表 */LNode *pa , *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 中当前元素，

9、 且小于等于 A 中后一元素时， 将此 元素插入到 A 的当前元素之后 */pa=qa; qa=qa-next; /* pb=qb;qb=qb-next; /* a-next=pb; /* pb-next=qa;保存 A 的后保存 B 的后 插入元素 */元素位置 */元素位置 */ else /* 如果 B 中元素总是更大 , 指针移向下一个 A 元素 */pa=qa;qa=qa-next;if (qb )/* 如果 A表已到终端而 B表还有结点未插入 */ /* 将 B 表接到 A 表后面 */pa-next=qb;C= reverselist(A); /*调用前面所设计的逆置函数 */r

10、eturn C; /* 返回新的单链表 C, 已是递减排列 */该算法的时间复杂度分析如下：算法中只有一个 while 循环，在这个循环中，按照最坏的情况是 B 元素既有插到 A 的最前的，也有插到最后的，也就是说需要把 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) L

12、inkList *p,*q,*w;p=head-next;while(p!=NULL) q=p-next;w=p;while(q!=NULL)/* 比较 p 所指节点的值与链表中后续节点的值， 不相等 q 指针后移 , 相等则删除 */if (p-data!=q-data) w=q;q=q-next;else w-next=q-next;w=q;q=q-next;p=p-next;第二部分： 本部分的思路和第一部分类似， 首先构造三个新的链表， 然后遍历原链 表，检测每一个元素，如果是第一类元素，则把该结点从原链表中删除，但是不释放空 间，而是添加到第一个新链表中；同样的，如果是第二类元素，则

13、添加到第二个新链表 中；以此类推，直到所有的节点都检测完毕。具体算法如下：void split(LinkList *ha) LinkList *hb,*hc,*ra,*rb,*rc,*p;char c;hb=(linklist*)malloc(sizeof(linklist);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;elserc-next=p; rc=p;p=p-next; ra-next=ha;rb-next=hb;rc-=next=hc;5 / 67设在长度大于 1 的单循环链表中， 既无头结点也无头指针。 s 为指向链表中某个结点 的指针，试编写算法删除结点 *s 的直接前趋结点。【答】已知指向这个结点的指