《数据结构(c语言版 严蔚敏)习题集答案第2章 线性表1.docx》由会员分享，可在线阅读，更多相关《数据结构(c语言版 严蔚敏)习题集答案第2章 线性表1.docx（19页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
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
17、链仍为原状 for(p=L;p-next!=L;p=p-next) p-next-pre=p;/reform分析:next链和pre链的调整只能分开进行.如同时进行调整的话，必须使用堆栈保 存偶数结点的指针，否则将会破坏链表结构，造成结点丢失.DuLNode* LOCATE(DuLinkedList &L,int x)带 freq 域的双向循环链表上的查找if(p=L) return NULL; /没找到p-freq+;q=p-pre;while(q-freqfreq) q=q-pre; 查找插入位置 if(q!=p-pre)(p-pre-next=p-next;p-next-pre=p-pr
18、e;q-next-pre=p;p-next=q-next;q-next=p;p-pre=q; 调整位置)return p;/LOCATEfloat GetValue_SqPoly(SqPoly P,int x0)求升幕顺序存储的稀疏多项式的值(PolyTerm *q;sum=0;ex=0;while(q-coef)(while(exexp) xp*=xO;sum+=q-coef*xp;q+；return sum;/GetValue_SqPolyvoid Subtract_SqPoly(SqPoly P1,SqPoly P2,SqPoly &P3)求稀疏多项式 P1 减 P2的差式P3(Poly
19、Term *p,*q,*r;Create_SqPoly(P3); 建立空多项式 P3p=la;while (p-nextNULL & p-next-datanext;q=p；while (q-nextNULL & q-next-datanext;q=q-next;p1=p-next;while (p1q) q1=p1; p1=p1-next; free(q1);p-next=q;/del-lLinkList priou(LinkList la, LinkList q1)返回指向单链表la中结点的指针p1 , p1-next=q1p1=la;while (p1-next!=q1) p1=p1-n
20、ext;return p1;/priouvoid Reverse-List-l(LinkList &la) 就地逆置单链表la (算法1 )if (!la-next) return;p=la-next; q=priou(la, NULL);while (p!=q) p-data q-data;if (p=q) return;q=priou(la, q);while(p-coef&q-coef)if(p-expexp)(r-coef=p-coef;r-exp=p-exp;p+；r+;)else if(p-expexp)r-coef=-q-coef;r-exp=q-exp;q+;r+;)else(
21、if(p-coef-q-coef)!=0) 只有同次项相减不为零时才需要存入P3中(r-coef=p-coef-q-coef;r-exp=p-exp;r+;/ifp+；q+；/else/whilewhile(p-coef) /处理P1或P2的剩余项(r-coef=p-coef;r-exp=p-exp;p+；r+;)while(q-coef)r-coef=q-coef;r-exp=q-exp;q+；r+;)/Subtract_SqPolyvoid QiuDao_LinkedPoly(LinkedPoly &L)对有头结点循环链表结构存储的稀疏 多项式L求导(p=L-next;L-nex仁p-ne
22、xt;p=p-next; /跳过常数项 )while(p!=L)p=p-next;)/QiuDao_LinkedPolyvoid Divide_LinkedPoly(LinkedPoly &L,&A,&B)把循环链表存储的稀疏多项式L拆成只含奇次项的A和只含偶次项的B(p=L-next;A=(PolyNode*)malloc(sizeof(PolyNode);B=(PolyNode*)malloc(sizeof(PolyNode);pa=A;pb=B;while(p!=L)pa-next=p;pa=p;)elsepb-next=p;pb=p;)p=p-next;/whilepa-next=A;
23、pb-next=B;/Divide_LinkedPoly/Reverse-List-l void Reverse-List-l(LinkList &la) 就地逆置单链表la (算法2 )p=priou(la, NULL); last=p;pre=priou(la,p);while (pre!=la) p-next=pre;p=pre;pre=priou(la,p);)p-next=NULL;la-next=last;/Reverse-List-lvoid Reverse-List-l(LinkList &la) 就地逆置单链表la (算法3)if (!la-next) return; 空表p
24、re=la-next; 前if (!pre-next) return;p=pre-next; 中pre-next=NULL;/原来的第一项将被作为最后一项；next=p-next; 后while (p) 当p不指向空地址时；p-next=pre;最终使每一个后项的地址域都指向前一项，实现逆置；pre=p;/后移p=next; 后移if (p) next=p-next; 当p不指向空地址，即原来的next没有被指向空；la-next=pre;/将头指针指向现在的第一项；return;/Reverse-List-lvoid Reverse-List-l(LinkList &la) 就地逆置单链表l
25、a (算法4)p=la-next;if (!p | !p-next) return; 空表或只有一项；pn=p-next; p-next=NULL;while (pn) p=pn; pn=pn-next; /后移;p-next=la-next; 后一项的地址域指向前一项；la-next=p;头指针指向后一项；)return;/Reverse-List-l void MergeList(LinkList &a, LinkList &b, LinkList &c) 已知单链表a和b的元素按值递增有序排列/归并a和b得到新的单链表c , c的元素按值递减有序 c=a; p=a-next; q=b-n
26、ext; c-next=NULL;while (p & q)if (p-datadata) pn=p-next; p-next=c-next;c-next=p; p=pn;else qn=q-next; q-next=c-next;c-next=q; q=qn;)while (p) pn=p-next; p-next=c-next; c-next=p; p=pn; while (q) qn=q-next; q-next=c-next; c-next=q; q=qn; free(b);/MergeList void CutApart-LinkList(LinkList &l, LinkList
27、la, LinkList lb, LinkList lc)单链表I中的元素含有三类字符：字母、数字和其它字符本算法将|分割为la. lb和1c三个循环链表，它们分别只含字母、数字和其它字符la=(LinkList)malloc(sizeof(LNode); la-next=la;lb=(LinkList)malloc(sizeof(LNode); lb-next=lb;lc=(LinkList)malloc(sizeof(LNode); lc-next=lc;pn=l-next;while (pn)p=pn; pn=pn-next;switch case (adata & p-data=*z)
28、|(A,data & p-datanext=la-next; la-next=p; break;case (,0,data & p-datanext=lb-next; lb-next=p; break;default: p-next=lc-next; lc-next=p;/switch/whilefree(l);/CutApart-LinkList typedef struct float coef;int expn;*Poly, ElemType;float Polynomial(Poly &p, int m, float x0)/多项式p的顺序存储结构中依次存放有ci,ei,C2,e2,.
29、,cm,emX0为给定值,本算法计算Pn(X0)的值x=xOApO.expn;pn=p0.coef*x;for (i=1; iB;值为负，表示AB;值为零，表示A=Breturn 0;/ListCompLNode* Locate(LinkList L,int x)链表上的元素查找，返回指针 (for(p=l-next;p&p-data!=x;p=p-next);return p;/Locateint Length(LinkList L)求链表的长度 (for(k=0,p=L;p-next;p=p-next,k+);return k;/Lengthvoid ListConcat(LinkList
30、 ha,LinkList hb,LinkList &hc)把链表 hb 接在 ha 后面开乡 成链表hehc=ha;p=ha;while(p-next) p=p-next;p-next=hb;/ListConcat见书后答案.Status lnsert(LinkList &L,int i,int b)在无头结点链表L的第i个元素之前插入元 素b(p=L;q=(LinkList*)malloc(sizeof(LNode);if(i=1)(else(while(-i1) p=p-next;q-next=p-next;p-next=q; 插入在第i个元素的位置/lnsertStatus Delete
31、(LinkList &L,int i)在无头结点链表L中删除第i个元素(if(i=1) L=L-next; /删除第一个元素else(P=L；while(-i1) p=p-next;p-nexkp-next-next; 册ij除第 i 个元素)/DeleteStatus Delete_Between(Linklist &L,int minkjnt maxk)/册i除元素递增排列的链 表L中值大于mink且小于maxk的所有元素P=L；while(p-next-datanext; /p 是最后一个不大于 mink 的元素 if(p-next) 如果还有比mink更大的元素q=p-next;whi
32、le(q-datanext; /q 是第一个不小于 maxk 的元素 p-next=q;)/Delete_BetweenStatus Delete_Equal(Linklist &L)册U除元素递增排列的链表L中所有值相同的元 素(p=L-next;q=p-next; /p,q 指向相邻两元素while(p-next)if(p-data!=q-data)(p=p-next;q=p-next; 当相邻两元素不相等时,p,q都向后推一步)else(while(q-data=p-data) q=q-next;p-next=q;p=q;q=p-next; /当相邻元素相等时删除多余元素)/while/Delete_Equalvoid reverse(SqList &A)顺序表的就地逆置/reversevoid LinkList_reverse(Linklist &L)链表的就地逆置;为简化算法，假设表长大于2