第二章线性表习题

1、第 2 章 线性表1 .编写一个算法，往单链表里数据为w0 的结点前面插入一个给定值x 的结点。2 .写出将单链表逆置的算法。即若原单链表中存储元素的次序为a0,a1,a2,an-1 ,则单链表逆置后便为an-1,an-2,a1,a0。要求就地逆置，即不再重新开辟存储空间， 只通过调整指针 来完成，并且使用尽可能少的附加单元。3 简述以下算法的功能。(1) Status A(LinkedList L) / L 是无表头结点的单链表if (L && L->next)Q =L; L =L->next; P =L ;while ( P->next) P =P->

2、;next ;P->next =Q; Q->next = NULL; return OK; / A(2) void BB(LNode *s, LNode *q ) p =s ;while (p->next!=q) p =p->next ; p->next =s; /BBvoid AA(LNode *pa, LNode *pb) / pa 和 pb 分别指向单循环链表中的两个结点BB(pa, pb); BB(pb, pa); /AA4 指出以下算法的错误和低效(即费时)之处，并将它改写为一个既正确又高效的算法。Status DeleteK(SqList &a

3、, int i, int k)/本过程从顺序存储结构的线性表a 中删除第i 个元素起的k 个元素if(i<1 | k<0 | i+k>a.length)return INFEASIBLE;/参数不合法elsefor(count=1; count<k; count+)/删除一个元素for(j=a.length; j>=i+1; j-)a.elemj-1= a.elemj; a.length-; returnOK;/DeleteK5 试写一算法在带表头结点的单链表结构上实现线性表操作LOCATE(L,X)。6 试写一算法在带头结点的单链表结构上实现线性表操作Lengt

4、h(L) 。7 已知指针ha 和 hb 分别指向两个单链表的头结点，并且已知两个链表的长度分别为m 和n 。试写一算法将这两个链表连接在一起(即令其中一个表的首结点连在另一个表的最后一个结点之后)， 假设指针hc 指向连接后的链表的头结点，并要求算法以尽可能短的时间完成连接运算。请分析你的算法的时间复杂度。8已知指针la和lb分别指向两个无头结点单链表中的首元结点.下列算法是从表la中删除自第i个元素起共len个元素后，将它们插入到表lb中第j个元素之前，试问此算法是否正确？若 有错,则请改正之。Status DeleteAndInsertSub(LinkedList la,LinkedLis

5、t lb,int i ,int j ,int len)if (i<0|j<0|len<0) return INFEASIBLE;p=la; k=1;while(k<i) p=p->next; k+; q=p;while(k<=len) q=q->next; k+; s=lb; k=1;while(k<j) s=s->next; k+; s->next=p; q->next=s->next; return OK;/DeleteAndInsertSub9写一个算法，实现顺序表的就地逆置，即在原表的存储空间将线性表(a1,a2,

6、.,an)逆置为(an,an-1,.,a1) 。10假设有两个按元素值递增有序排列的线性表A和B,均以单链表作存储结构，请编写算法将 A 表和 B 表归并为一个按元素值递增有序(即非递增有序，允许表中含有值相同的元素)排列的线性表 C,并要求利用原表(即 A表和B表)的结点空间构造C表。第 2 章 答案1 . 编写一个算法，往单链表里数据为w0 的结点前面插入一个给定值x 的结点。Status Insert_List ( LinkList &L, ElemType w0, ElemType x ) LinkList p,r;LNode *s;P=L->next;while( p

7、&& p->data !=w0) r=p; p=p->next; if(p) s=(LNode *) malloc( sizeof(LNode); s->data=x;s->next=p;r->next=s; return OK; return ERROR;2 .写出将单链表逆置的算法。即若原单链表中存储元素的次序为a0,a1,a2,an-1 ,则单链表逆置后便为an-1,an-2,a1,a0。要求就地逆置，即不再重新开辟存储空间，只通过调整指针来完成，并且使用尽可能少的附加单元。void ReversList ( LinkList &L)

8、 LinkList p,q;if(L=NULL) return ERROR;p=L->next;L->next=NULL; while(p) q=p->next; p->next=L; L=p;p=q; return OK;3 简述以下算法的功能。(1) Status A(LinkedList L) / L 是无表头结点的单链表if (L && L->next)Q =L; L =L->next; P =L ;while ( P->next) P =P->next ;P->next =Q; Q->next = NULL;

9、return OK; / A如果存在两个及以上结点，该算法将把第一个结点插入到表尾，原来表中第二个结点变成了第一个结点。(2) void BB(LNode *s, LNode *q ) p =s ;while (p->next!=q) p =p->next ;p->next =s; /BBvoid AA(LNode *pa, LNode *pb) / pa 和 pb 分别指向单循环链表中的两个结点BB(pa, pb);BB(pb, pa); /AA形成两个独立的单循环链表，pa 和 pb 作为首结点4 指出以下算法的错误和低效(即费时)之处， 并将它改写为一个既正确又高效的算

10、法。Status DeleteK(SqList &a, int i, int k)/ 本过程从顺序存储结构的线性表a 中删除第i 个元素起的k 个元素if(i<1 | k<0 | i+k>a.length)return INFEASIBLE;/ 参数不合法elsefor(count=1; count<k; count+)/删除一个元素for(j=a.length; j>=i+1; j-)a.elemj-1= a.elemj;a.length-;returnOK;/DeleteK参数不合法的地方有错i<1 | i>a.length | k<

11、0 | i+k>a.length低效的地方是每次删除一个元素都要逐个移动元素，实际上可以一次移到地方for(j=i;j<=a.length-k;j+)a.elemj=a.elemj+k;a.length-=k;LOCATE(L,X)。5 试写一算法在带表头结点的单链表结构上实现线性表操作int LOCATE(LinkList L, ElemType X) int i=0;LinkList p;p=L->next;while(p && p->data!=X) p=p->next;i+; return i;6 试写一算法在带头结点的单链表结构上实现线性

12、表操作Length(L) 。int Length(LinkList L)int i=0;LinkList p;p=L->next;while(p)p=p->next;i+; return i;7 已知指针ha 和 hb 分别指向两个单链表的头结点，并且已知两个链表的长度分别为m 和 n 。试写一算法将这两个链表连接在一起(即令其中一个表的首结点连在另一个表的最后一个结点之后)， 假设指针hc 指向连接后的链表的头结点，并要求算法以尽可能短的时间完成连接运算。请分析你的算法的时间复杂度。void MergeList ( LinkList ha,LinkList hb,int m,in

13、t n,LinkList &hc)LinkList p,q;if(m<n)hc=ha;p=ha->next;q=p;while(p) q=p;p=p->next;p=hb;q->next=hb->next;free(p);elsehc=hb;p=hb->next;q=p;while(p)q=p;p=p->next;p=ha;q->next=ha->next;free(p);时间复杂度为O(min(m,n)8 已知指针la 和 lb 分别指向两个无头结点单链表中的首元结点.下列算法是从表la 中删除自第 i 个元素起共len 个元素后

14、,将它们插入到表lb 中第 j 个元 b 素之前 ,试问此算法是否正确？若有错,则请改正之。Status DeleteAndInsertSub(LinkedList la,LinkedList lb,int i ,int j ,int len)if (i<0|j<0|len<0) return INFEASIBLE;p=la; k=1;while(k<i) p=p->next; k+; q=p;while(k<=len) q=q->next; k+; s=lb; k=1;while(k<j) s=s->next; k+; s->nex

15、t=p; q->next=s->next;preturn OK;/DeleteAndInsertSubStatus DeleteAndInsertSub(LinkedList la,LinkedList lb,int i ,int j ,int len)LinkList p,q,s;if (i<0|j<0|len<0) return INFEASIBLE;p=la; k=1;while(p&&k<i) p=p->next; k+; if(p=NULL) return INFEASIBLE;q=p;k=0;while(q&&

16、;k<=len) q=q->next; k+;if(q=NULL) return INFEASIBLE;s=lb; k=1;while(s&&k<j) s=s->next; k+; if(s=NULL) return INFEASIBLE;q->next=s->next;s->next=p;return OK;/DeleteAndInsertSub9 写一个算法，实现顺序表的就地逆置，即在原表的存储空间将线性表(a1,a2,.,an )逆置为(an,an-1,.,a1) 。void revers(SqList &L)int i;ElemType t;for(i=0;i<L.length/2;i+) t=L.elemi;elemi=elemL.length-1-i;elemL.length-1-i=t; return OK;10假设有两个按元素值递增有序排列的线性表A和B,均以单链表作存储结构，请编写算法将A 表和 B 表归并为一个按元素值递增有序(即非递减有序，允许表中含有值相同的元素)排列的线性表C,并要求利用原表(即 A表和B表)的结点空间构造C表。Status MergeList(LinkList A,LinkLi