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、顺序表和单链表作为存储结构，实现将线性表(a0,a1,.an-1)就地逆置的操作，所谓"就地"指辅助空间应为O(1)。【答】分两种情况讨论如下。 顺序表：要将该表逆置，可以将表中的开始结点与终端结点互换，第二个结点与倒数第二个结点互换，如此反复，就可将整个表逆置了。算法如下：void reverlist(sequenlist *L) datatype t; /* 设置临时空间用于存放data */int i;for (i=0;i<L->length/2;i+) t=L->datai; /* 交换数据 */L->datai=L->dataL-&g

5、t;length-1-i;L->dataL->length-1-i=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; /*将开

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

7、*L , Datatype x ) int i; for (i=0; i<L->length && L->datai<x; i+) ; /* 查找并比较,分号不能少 */ InsertList (L,x,i ); /* 调用顺序表插入函数 */3顺序表L是一个递减有序表，试写一算法，将x插入其后仍保持L的有序性。【答】类似于第2题，读者可自行完成，这里不在赘述。4知L1和L2分别指向两个单链表的头结点，且已知其长度分别为m和n。试写一算法将这两个链表连接在一起，请分析你的算法的时间复杂度。【答】算法如下：LinkList *Link( LinkList

8、*L1 , LinkList *L2 )/* 将两个单链表连接在一起 */ LNode *p , *q ; p=L1; q=L2; while ( p->next ) p=p->next; /* 查找终端结点 */ p->next = q->next ; /* 将L2的开始结点链接在L1之后 */ return L1 ;本算法的主要操作时间花费在查找L1的终端结点上，与L2的长度无关，所以本算的法时间复杂度为：O(m)5A和B是两个单链表，其表中元素递增有序。试写一算法将A和B归并成一个按元素值递减有序的单链表C，并要求辅助空间为O(1)，请分析算法的时间复杂度。【答】

9、根据已知条件，A和B是两个递增有序表，所以我们可以以A表为基础，按照插入单个元素的办法把B表的元素插入A表中，完成后，将表逆置就得到了一个按元素值递减有序的单链表C了。算法如下：LinkList *MergeSort(LinkList *A , LinkList *B )/* 归并两个递增有序表为一个递减有序表 */LNode *pa , *pb , *qa , *qb ;pa=A;pb=B;qa=A->next;qb=B->next;while (qa &&qb)if(qb->data<qa->data ) /* 当B中的元素小于A中当前元素时，

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

11、b; /* 插入元素 */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的最前的，也有插到最后的，也就是说需要把A中元素和B中元素全部检查比较

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

13、两种方式，第一种方式：先取开始结点中的值，将它与其后的所有结点值一一比较，发现相同的就删除掉，然后再取第二结点的值，重复上述过程直到最后一个结点。第二种方式：将单链表按值的大小排序，排好后的结点按相同的删除。我们这里给出第一种方式的算法，如下所示：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!=q->data)w=

14、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

15、(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<=z)|(c>=C && c<=Z) ra->next=p;ra=p; else if(c>=0 && c<=9 rb->next=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