数据结构(c语言版 严蔚敏)习题集答案第2章 线性表1.docx
《数据结构(c语言版 严蔚敏)习题集答案第2章 线性表1.docx》由会员分享,可在线阅读,更多相关《数据结构(c语言版 严蔚敏)习题集答案第2章 线性表1.docx(19页珍藏版)》请在得力文库 - 分享文档赚钱的网站上搜索。
1、Status OrderListInsert-sq(SqList va, ElemType x) 将x插入到递增有序的顺序表va中,插入后va仍然递增有序(算法1)pe);if (Inewbase) exit (OVERFLOW);当前存储空间已满,增加分配空间 for*q=x;return OK;/OrderListlnsert-sqStatus OrderListlnsert-sq(SqList va, ElemType x) 将x插入到递增有序的顺序表va中,插入后va仍然递增有序(算法2)newbase=(ElemType *)if (!newbase) exit (OVERFLOW)
2、;当前存储空间已满,增加分配空间*(p+l)=X; return OK;/OrderListlnsert-sq)和B=(b., bn)均为顺序表,A,和B分别为A和B中除去最大共同前缀后的子表。若 A=B=空表,则A=B;若A二空表,而BW空表,或者两者均不为空表,且A的首元小于B的 首元,则否则AB。试写一个比较A, B大小的算法。int Compare-List (SqList a, SqList b)冉b为顺序表,若水b时,返回T; a二b时,返回0; ab时,返回1i=0;switch ,length-1)default : return 1;)/Compare-Liststatus
3、del-l(LinkList &la, int mink, int maxk)/伯为带头结点的单链表的头指针,单链表中的结点以值递增有序排列本算法删除表中所有值大于mink且小于maxk的元素,mink=maxk) return ERRORp=L-next;q=p-next;s=q-next;p-next=NULL;while(s-next)(q-next=p;p=q;q=s;s=s-next; 把L的元素逐个插入新表表头 )q-next=p;s-next=q;A-next=s;/LinkList_reverse分析:本算法的思想是,逐个地把L的当前元素q插入新的链表头部,p为新表表头. vo
4、id merge1(LinkList &A,LinkList &B,LinkList &C)把链表 A 和 B 合并为 C,A 和 B的元素间隔排列,且使用原存储空间(p=A-next;q=B-next;C=A;while(p&q)s=p-next;p-next=q; 将 B 的元素插入 if(t=q-next;q-next=s; /$ A 非空,将 A 的元素插入)P=s;q=t;/while/merge1void reverse_merge(LinkList &A,LinkList &B,LinkList &C)把元素递增排列的链 表A和B合并为C,且C中元素递减排列,使用原空间(pa=A
5、-next;pb=B-next;pre=NULL; /pa 和 pb 分别指向 A,B 的当前元素 while(pa&pb)(if(pa-datadata)(pc=pa;q=pa-next;pa-next=pre;pa=q; / A 的元素插入新表elsepc=pb;q=pb-next;pb-next=pre;pb=q; / B 的元素插入新表)pre=pc;)while(pa)(q=pa-next;pa-next=pc;pc=pa;pa=q; /A A 中余下的元素)while(pb)(q=pb-next;pb-next=pc;pc=pb;pb=q; /插入 B 中余下的元素)C=A;A-n
6、ext=pc; 构造新表头/reverse_merge分析:本算法的思想是,按从小到大的顺序依次把A和B的元素插入新表的头部 pc处,最后处理A或B的剩余元素.void SqList_lntersect(SqList A,SqList B,SqList &C)求元素递增排列的线性表 A 和B的元素的交集并存入C中(i=1;j=1;k=O;i+;j+; 就添加到C中 )/while/SqList_lntersectvoid LinkList_lntersect(LinkList A,LinkList B,LinkList &C)在链表结构上重做上 题(p=A-next;q=B-next;pc=(
7、LNode*)malloc(sizeof(LNode);while(p&q)(if(p-datadata) p=p-next;else if(p-dataq-data) q=q-next;else(s=(LNode*)malloc(sizeof(LNode);s-data=p-data;pc-next=s;pc=s;p=p-next;q=q-next;)/whileC=pc;/LinkList_lntersectvoid SqList_lntersect_True(SqList &A,SqList B)求元素递增排列的线性表 A 和B的元素的交集并存回A中(i=1;j=1;k=O;i+;j+;
8、 且C中没有,就添加到C中 )/while/SqList_lntersect_T ruevoid LinkList_lntersect_True(LinkList &A,LinkList B)在链表结构上重做上题(p=A-next;q=B-next;pc=A;while(p&q)(if(p-datadata) p=p-next;else if(p-dataq-data) q=q-next;else if(p-data!=pc-data)(pc=pc-next;pc-data=p-data;p=p-next;q=q-next;)/while/LinkList_lntersect_Truevoid
9、 SqList_lntersect_delete(SqList &A,SqList B,SqList C)从有序顺序表 A 中删除那些在B和C中都出现的元素else 找到了需要从A中删除的元素/else/while)j+;/for/SqList_lntersect_delete分析:本算法的时间复杂度为O(m),m为表长.思考:你自己的算法时间复杂度是多 少?实际上也可以只用一遍扫描就完成整个操作,且时间复杂度也为0(m),但非常 复杂,你能写出来吗?void LinkList_lntersect_delete(LinkList &A,LinkList B,LinkList C)在链表结构上
10、重做上题(p=B-next;q=C-next;r=A-next;while(p&q&r)(if(p-datadata) p=p-next;else if(p-dataq-data) q=q-next;else(u=p-data; 确定待删除元素uwhile(r-nextdatav(j) r=rnext; 确定最后一个小于u的元素指针r if(r-next-data=u)(s=r-next;while(s-data=u)仁s;s=s-next;free(t); 确定第一个大于u的元素指针s/whiler-next=s; 册i除r和s之间的元素/ifwhile(p-data=u) p=p-next
11、;while(q-data=u) q=q-next;/else/while/LinkList_lntersect_deleteStatus Delete_Pre(CiLNode *s)删除单循环链表中结点s的直接前驱 (P=S;while(p-next-next!=s) p=p-next; 找至! s 的前驱的前驱 p p-next=s;return OK;/Delete_preStatus DuLNode_pre(DuLinkList &L)完成双向循环链表结点的pre域 (for(p=L;!p-next-pre;p=p-next) p-next-pre=p;return OK;/DuLNo
12、de_pre(s=L-next;A=(CiList*)malloc(sizeof(CiLNode);p=A;B=(CiList*)malloc(sizeof(CiLNode);q=B;C=(CiList*)malloc(sizeof(CiLNode);r=C; /建立头结点 while(s)(if(isalphabet(s-data)(p-next=s;p=s;)else if(isdigit(s-data)q-next=s;q=s;)else(r-next=s;r=s;)/whilep-next=A;q-next=B;r-next=C; /完成循环链表/LinkList_dividevoid
13、 Print_XorLinkedList(XorLinkedList L)从左向右输出异或链表的元素值(while(p)printf(d”,p-data);q=XorP(p-LRPtr,pre);pre二p;p=q; 任何一个结点的LRPtr域值与其左结点指针进行异或运算即得 到其右结点指针)/Print_XorLinkedListStatus lnsert_XorLinkedList(XorLinkedList &L,int x,int i)在异或链表 L 的第 i 个 元素前插入元素x(r=(XorNode*)malloc(sizeof(XorNode);r-data=x;if(i=1)
14、当插入点在最左边的情况(r-LRPtr=p;return OK;)j=1;q=p-LRPtr; 当插入点在中间的情况 while(+jLRPtr,pre);pre=p;p=q;/while 在p,q两结点之间插入if(!q) return INFEASIBLE; /i 不可以超过表长p-LRPtr=XorP(XorP(p-LRPtr,q),r);q-LRPtr=XorP(XorP(q-LRPtr,p),r);r-LRPtr=XorP(p,q); 修改指针return OK;/lnsert_XorLinkedListStatus Delete_XorLinkedList(XorlinkedLis
15、t &L,int i)删除异或链表 L 的第 i 个元 素(if(i=1) /删除最左结点的情况(q=p-LRPtr;q-LRPtr=XorP(q-LRPtr,p);return OK;)j=1;q=p-LRPtr;while(+jLRPtr,pre);pre=p;p=q;/while /找到待删结点qif(!q) return INFEASIBLE; /i 不可以超过表长p-LRPtr=XorP(p-LRPtr,q);return OK;)r=XorP(q-LRPtr,p); /q为中间结点的情况,此时p,r分别为其左右结点 p-LRPtr=XorP(XorP(p-LRPtr,q),r);r
16、-LRPtr=XorP(XorP(rLRPtr,q),p); 修改指针free(q);return OK;/Delete_XorLinkedListwhile(p-next!=L&p-next-next!=L)(p-next=p-next-next;p=p-next; 此时p指向最后一个奇数结点if(p-next=L) p-next=L-pre-pre;else p-next=l-pre;p=p-next; 此时p指向最后一个偶数结点while(p-pre-pre!=L)(p-next=p-pre-pre;p=p-next;)p-next=L; /按题目要求调整了 next链的结构,此时pre
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据结构c语言版 严蔚敏习题集答案第2章 线性表 数据结构 语言版 严蔚敏 习题集 答案 线性
限制150内