数据结构作业系统-第二章答案.doc

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

1、Four short words sum up what has lifted most successful individuals above the crowd: a little bit more.-author-date数据结构作业系统-第二章答案数据结构作业系统-第二章答案2.11 设顺序表L中的数据元素递增有序。试写一算法，将x插入到L的适当位置上，并保持该表的有序性。要求实现下列函数：void InsertOrderList(SqList &L, ElemType x)/* 在有序的顺序表 L 中保序插入数据元素 x */顺序表类型定义如下：typedef struct Ele

2、mType *elem; int length; int listsize; SqList;void InsertOrderList(SqList &L, ElemType x)/ 在有序的顺序表 L 中保序插入数据元素 x int i=0,j; while(L.elemixⅈj-) L.elemj=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,

3、y,z)， 在两表中除去最大共同前缀后的子表分别为A=(x,z)和B=(y,x,x,z)）。若A=B=空表，则A=B；若A=空表，而B 空表，或者两者均不为空表，且A的首元小于B的首元，则AB。试写一个比较A和B大小的算法。（注意：在算法中，不要破坏原表A和B，也不一定先求得A和B才进行比较）。要求实现下列函数：char Compare(SqList A, SqList B);/* 比较顺序表A和B, */* 返回, 若A, 若AB */顺序表类型定义如下：typedef struct ElemType *elem; int length; int listsize; SqList;char

4、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) 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

5、 x);/ If x in the linked list whose head node is pointed / by L, then return pointer pointing node x, / otherwise return NULL单链表类型定义如下：typedef struct 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

6、/ 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 试写一算法在带头结点的单链表结构上实现线性表操作Length(L)。实现下列函数：int Length(LinkList L);/ Return the length of the linked list / whose head node is pointed by L单链表类型定义如

7、下：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 by L LinkList p; int i=0; p=L-next; while(p!=NULL) i+; p=p-next; return i;2.17 试写一算法，在无头结点的动态单链表上实现线性表操作INSERT(L,i,b)，并和在带头结点的动态单链表上实现相

8、同操作的算法进行比较。实现下列函数：void Insert(LinkList &L, int i, ElemType b);单链表类型定义如下：typedef struct LNode ElemType data; struct LNode *next; LNode, *LinkList;void Insert(LinkList &L, int i, ElemType 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-nex

9、t; 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 ElemType data; struct LNode *next; LNode, *LinkList;void Delete(LinkList &L, int i) LinkList p,q; int j=2; p=L;

10、 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);单链表类型定义如下：typedef struct LNode ElemType data; struct LNode *next; LNode, *LinkList;void P

11、urge(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 Inverse(SqList &L);顺序表类型定义如下：typedef struct ElemType *elem; int length; int list

12、size; 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) 当mn时；或者 C=(a1,b1,.,an,bn,an+1,.,am) 当mn时。线性表A、B和C均以单链表作存储结构，且C表

13、利用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(LinkList ha, LinkList hb, LinkList &hc)/* 依题意，合并带头结点的单链表ha和hb为hc */ LinkList p,q,k,r;

14、 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，均以单链表作存储结构，请编写算法将A表和B表归并成一个按元素值递减有序（即非递增有序，允许表中含有值相同的元素）排列的线性表C， 并要求利用原表

15、（即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, LinkList lb) LinkList pa=la-next; LinkList pb=lb-next; LinkList pre=NULL;

16、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 = la; lc = la; while( pa & pb ) if( pa-data dat

17、a ) 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为指向链表中某个结点的指针，试编写算法在链表中删

18、除指针s所指结点的前驱结点。实现下列函数：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

19、-next-data; p-next=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, *ne

20、xt; BiNode, *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, LinkLis

21、t ll);单链表类型定义如下：typedef 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; /建立头结点

22、while(s) if(s-data=a&s-datadatadata=A) p-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);双向循环链表类型定义如下：typed

23、ef struct BiNode ElemType data; int freq; / 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;

24、/此时p指向最后一个偶数结点 while(p-prev-prev!=L) p-next=p-prev-prev; 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

25、x);/* pn.datai.coef 存放ai， */* pn.datai.exp存放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

26、;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; -