(完整版)数据结构作业系统_第二章答案.pdf

《(完整版)数据结构作业系统_第二章答案.pdf》由会员分享，可在线阅读，更多相关《(完整版)数据结构作业系统_第二章答案.pdf（15页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、2.11 设顺序表 L 中的数据元素递增有序。试写一算法，将 x 插入到 L 的适当位置上，并保 持该表的有序性。要求实现下列函数：void InsertOrderList(SqList&L,ElemType x)/*在有序的顺序表 L 中保序插入数据元素 x*/顺序表类型定义如下：typedef struct ElemType*elem;int length;int listsize;SqList;void InsertOrderList(SqList&L,ElemType x)/在有序的顺序表 L 中保序插入数据元素 x int i=0,j;while(L.elemixⅈj-)L.e

2、lemj=L.elemj-1;L.elemi=x;L.length+=1;2.12 设 A=(a1,am)和 B=(b1,bn)均为有序顺序表，A和 B分别为 A 和 B 中除去最大共同前缀后的子表（例如，A=(x,y,y,z,x,z)，B=(x,y,y,z,y,x,x,z)，则两者中最大 的共同前缀为(x,y,y,z)，在两表中除去最大共同前缀后 的子表分别为 A=(x,z)和 B=(y,x,x,z)）。若 A=B=空表，则 A=B；若 A=空表，而 B 空表，或者两者均不为空表，且 A的首元小于 B的首元，则 AB。试写一个比 较 A 和 B 大小的算法。（注意：在算法中，不要破坏原表 A

3、 和 B，也不一定先求得 A和 B才进行比较）。要求实现下列函数：char Compare(SqList A,SqList B);/*比较顺序表 A 和 B,*/*返回,若 A,若 AB */顺序表类型定义如下：typedef struct ElemType*elem;int length;int listsize;SqList;char Compare(SqList A,SqList B)/比较顺序表 A 和 B,/返回,若 A,若 AB int i=0;while(A.elemi=B.elemi&iA.length&iB.length)i+;if(i=A.length&i=B.length

4、)return=;else if(A.elemiB.elemi|i=A.length)return B.elemi|i=B.length)return;2.13 试写一算法在带头结点的单链表结构上实现线性表操作 Locate(L,x)。实现下列函数：LinkList Locate(LinkList L,ElemType x);/If x in the linked list whose head node is pointed /by L,then return pointer pointing node x,/otherwise return NULL 单链表类型定义如下：typedef s

5、truct LNode ElemType data;struct LNode*next;LNode,*LinkList;LinkList Locate(LinkList&L,ElemType x)/If x in the linked list whose head node is pointed/by L,then return pointer ha pointing node x,/otherwise return NULL LinkList p;int i=0;p=L-next;while(p-data!=x&p!=NULL)i+;p=p-next;return p;2.14 试写一算法

6、在带头结点的单链表结构上实现线性表 操作 Length(L)。实现下列函数：int Length(LinkList L);/Return the length of the linked list /whose head node is pointed by L 单链表类型定义如下：typedef struct LNode ElemType data;struct LNode*next;LNode,*LinkList;int Length(LinkList L)/Return the length of the linked list /whose head node is pointed b

7、y L LinkList p;int i=0;p=L-next;while(p!=NULL)i+;p=p-next;return i;2.17 试写一算法，在无头结点的动态单链表上实现 线性表操作 INSERT(L,i,b)，并和在带头结点的动态单 链表上实现相同操作的算法进行比较。实现下列函数：void Insert(LinkList&L,int i,ElemType b);单链表类型定义如下：typedef struct LNode ElemType data;struct LNode*next;LNode,*LinkList;void Insert(LinkList&L,int i,El

8、emType b)LinkList p,q;int j=2;p=L;while(jnext;if(i!=0&i!=1)q=(LinkList)malloc(sizeof(LNode);q-data=b;q-next=p-next;p-next=q;if(i=1)q=(LinkList)malloc(sizeof(LNode);q-data=b;q-next=p;L=q;2.18 同 2.17 题要求。试写一算法，实现线性表操作 DELETE(L,i)。实现下列函数：void Delete(LinkList&L,int i);单链表类型定义如下：typedef struct LNode Elem

9、Type data;struct LNode*next;LNode,*LinkList;void Delete(LinkList&L,int i)LinkList p,q;int j=2;p=L;while(jnext;if(i!=0&i!=1)q=p-next;p-next=q-next;free(q);if(i=1)q=L;L=L-next;free(q);2.20 同 2.19 题条件，试写一高效的算法，删除表中所 有值相同的多余元素(使得操作后的线性表中所有元素的 值均不相同)同时释放被删结点空间，并分析你的算法的 时间复杂度。实现下列函数：void Purge(LinkList&L)

10、;单链表类型定义如下：typedef struct LNode ElemType data;struct LNode*next;LNode,*LinkList;void Purge(LinkList&L)LinkList p,q;int i=0;p=L;while(p!=NULL&p-next!=NULL)if(p-data=p-next-data)q=p-next;p-next=q-next;free(q);else p=p-next;2.21 试写一算法，实现顺序表的就地逆置，即利用原表的存储空间将线性表(a1,a2,an)逆置为(an,an-1,a1)。实现下列函数：void Inver

11、se(SqList&L);顺序表类型定义如下：typedef struct ElemType*elem;int length;int listsize;SqList;void Inverse(SqList&L)int i=0,j=0;i=L.length/2;for(j=0;jnext;while(p-next!=NULL)k=q;q=p-next;p-next=q-next;q-next=k;L-next=q;2.23 设线性表 A=(a1,.,am),B=(b1,.,bn)，试写 一个按下列规则合并 A、B 为线性表 C 的算法，即使得 C=(a1,b1,.,am,bm,bm+1,.,bn

12、)当 mn 时；或者 C=(a1,b1,.,an,bn,an+1,.,am)当 mn 时。线性表 A、B 和 C 均以单链表作存储结构，且 C 表利用 A 表和 B 表中的结点空间构成。注意：单链表的长度值 m 和 n 均未 显式存储。实现下列函数：void Merge(LinkList ha,LinkList hb,LinkList&hc)/*依题意，合并带头结点的单链表 ha 和 hb 为 hc */单链表类型定义如下：typedef struct LNode ElemType data;struct LNode*next;LNode,*LinkList;void Merge(LinkLi

13、st ha,LinkList hb,LinkList&hc)/*依题意，合并带头结点的单链表 ha 和 hb 为 hc */LinkList p,q,k,r;p=ha-next;q=hb-next;if(p=NULL)hc=hb;else if(q=NULL)hc=ha;else while(p-next!=NULL&q-next!=NULL)k=p-next;r=q-next;p-next=q;p=k;q-next=p;q=r;if(p-next!=NULL)q-next=p-next;p-next=q;hc=ha;2.24 假设有两个按元素值递增有序排列的线性表 A 和 B，均以单链表作存

14、储结构，请编写算法将 A 表和 B 表 归并成一个按元素值递减有序（即非递增有序，允许表 中含有值相同的元素）排列的线性表 C，并要求利用原 表（即 A 表和 B 表）的结点空间构造 C 表。实现下列函数：void Union(LinkList&lc,LinkList la,LinkList lb);/*依题意，利用 la 和 lb 原表的结点空间构造 lc 表*/单链表类型定义如下：typedef struct LNode ElemType data;struct LNode*next;LNode,*LinkList;void Union(LinkList&lc,LinkList la,Li

15、nkList lb)LinkList pa=la-next;LinkList pb=lb-next;LinkList pre=NULL;LinkList q,pc;while(pa|pb)if(pa-datadata&pa!=NULL)|pb=NULL)pc=pa;q=pa-next;pa-next=pre;pa=q;else pc=pb;q=pb-next;pb-next=pre;pb=q;pre=pc;printf(%s,done);lc=la;la-next=pc;/构造新表头 /*LinkList pa=la-next;LinkList pb=lb-next;LinkList pc=l

16、a;lc=la;while(pa&pb)if(pa-data data)pc-next=pa;pc=pa;pa=pa-next;else pc-next=pb;pc=pb;pb=pb-next;pc-next=pa?pa:pb;free(lb);/将 c 实现就地逆置 LinkList p,q;p=lc-next;while(p-next)q=p-next;p-next=p-next-next;q-next=lc-next;lc-next=q;*/2.31 假设某个单向循环链表的长度大于 1，且表 中既无头结点也无头指针。已知 s 为指向链表中某个 结点的指针，试编写算法在链表中删除指针 s

17、所指结 点的前驱结点。实现下列函数：ElemType DeleteNode(LinkList s);/*删除指针 s 所指结点的前驱结点，并返回被删结点的元素值*/单链表类型定义如下：typedef struct LNode ElemType data;struct LNode*next;LNode,*LinkList;ElemType DeleteNode(LinkList s)/*删除指针 s 所指结点的前驱结点，并返回被删结点的元素值*/LinkList p;p=s-next;while(p-next-next!=s)p=p-next;ElemType e=p-next-data;p-n

18、ext=s;return e;2.32 已知有一个单向循环链表，其每个结点中 含三个域：prev、data 和 next，其中 data 为数据域，next 为指向后继结点的指针域，prev 也为指针域，但它的值为空(NULL)，试编写算法将此单向循环链 表改为双向循环链表，即使 prev 成为指向前驱结点 的指针域。实现下列函数：void PerfectBiLink(BiLinkList&CL);双向循环链表类型定义如下：typedef struct BiNode ElemType data;int freq;/2.38 题用 struct BiNode*prev,*next;BiNode,

19、*BiLinkList;void PerfectBiLink(BiLinkList&CL)BiLinkList p,q,k;k=p=q=CL;while(p-next!=q)p=p-next;p-prev=k;k=p;q-prev=p;2.33 已知由一个线性链表表示的线性表中含有 三类字符的数据元素（如：字母字符、数字字符和其 它字符），试编写算法将该线性链表分割为三个循环 链表，其中每个循环链表表示的线性表中均只含一类 字符。实现下列函数：void Split(LinkList&lc,LinkList&ld,LinkList&lo,LinkList ll);单链表类型定义如下：typede

20、f struct LNode ElemType data;struct LNode*next;LNode,*LinkList;void Split(LinkList&A,LinkList&B,LinkList&C,LinkList L)LinkList s,p,q,r;s=L-next;A=(LinkList)malloc(sizeof(LNode);p=A;B=(LinkList)malloc(sizeof(LNode);q=B;C=(LinkList)malloc(sizeof(LNode);r=C;/建立头结点 while(s)if(s-data=a&s-datadatadata=A)p

21、-next=s;p=s;else if(s-data=0&s-datanext=s;q=s;else r-next=s;r=s;s=s-next;/while p-next=A;q-next=B;r-next=C;/完成循环链表 2.37 设以带头结点的双向循环链表表示的线性 表 L=(a1,a2,.,an)。试写一时间复杂度为 O(n)的 算法，将 L 改造为 L=(a1,a3,.,an,.,a4,a2)。实现下列函数：void ReverseEven(BiLinkList&L);双向循环链表类型定义如下：typedef struct BiNode ElemType data;int fre

22、q;/2.38 题用 struct BiNode*prev,*next;BiNode,*BiLinkList;void ReverseEven(BiLinkList&L)BiLinkList p=NULL;p=L-next;while(p-next!=L&p-next-next!=L)p-next=p-next-next;p=p-next;/此时 p 指向最后一个奇数结点 if(p-next=L)p-next=L-prev-prev;else p-next=L-prev;p=p-next;/此时 p 指向最后一个偶数结点 while(p-prev-prev!=L)p-next=p-prev-p

23、rev;p=p-next;if(p!=L)p-next=L;/按题目要求调整了 next 链的结构,此时 pre 链仍为原状 for(p=L;p-next!=L;p=p-next)p-next-prev=p;L-prev=p;/调整 pre 链的结构,同 2.32 方法 2.39 试对稀疏多项式 Pn(x)采用存储量同多项式项 数 m 成正比的顺序存储结构，编写求 Pn(x0)的算法（x0 为 给定值），并分析你的算法的时间复杂度。实现下列函数：float Evaluate(SqPoly pn,float x);/*pn.datai.coef 存放 ai，*/*pn.datai.exp 存放

24、ei(i=1,2,.,m)*/*本算法计算并返回多项式的值。不判别溢出。*/*入口时要求 0e1e2.em，算法内不对此再作验证*/多项式的顺序存储结构:typedef struct int coef;int exp;PolyTerm;typedef struct PolyTerm*data;int length;SqPoly;float f(float x,int j)int i;float s=1;for(i=0;i j;+i)s*=x;return s;float Evaluate(SqPoly pn,float x)/*pn.datai.coef 存放 ai，*/*pn.datai.exp 存放 ei(i=1,2,.,m)*/*本算法计算并返回多项式的值。不判别溢出。*/*入口时要求 0e1e2.em，算法内不对此再作验证*/int i;float s=0;for(i=0;i next;if(t-exp=0)free(t);pa-next=pa-next-next;p=pa-next;while(p!=pa)p-coef*=p-exp;p-exp-;/if(p-next-exp=0)p-next=p-next-next;p=p-next;