数据结构作业系统答案.doc

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.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,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 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 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/ 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单链表类型定义如下：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)，并和在带头结点的动态单链表上实现相同操作的算法进行比较。实现下列函数：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-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 ElemType 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);单链表类型定义如下：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 Inverse(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) 当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(LinkList 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，均以单链表作存储结构，请编写算法将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, LinkList 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 = la; 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所指结点的前驱结点。实现下列函数：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-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, *next; 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, LinkList 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; /建立头结点 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);双向循环链表类型定义如下：typedef 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; /此时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 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;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; 3.17 试写一个算法，识别依次读入的一个以为结束符的字符序列是否为形如序列1&序列2模式的字符序列。其中序列1和序列2中都不含字符&，且序列2是序列1的逆序列。例如，a+b&b+a是属该模式的字符序列，而1+3&3-1则不是。实现下列函数: Status match(char *str);/* 若str是属该模式的字符序列，*/* 则返回TRUE，否则返回FALSE */Stack是一个已实现的栈。可使用的相关类型和函数：typedef char SElemType; / 栈Stack的元素类型Status InitStack(Stack &s);Status Push(Stack &s, SElemType e);Status Pop(Stack &s, SElemType &e);Status StackEmpty(Stack s);Status GetTop(Stack s, SElemType &e);Status match(char *str)/* 若str是属该模式的字符序列，*/* 则返回TRUE，否则返回FALSE */ Stack s; SElemType e; InitStack(s); while(*str!=&) Push(s,*str); str+; str+; while(*str!=) if(StackEmpty(s) return FALSE; Pop(s,e); if(*str!=e) return FALSE; str+; if(!StackEmpty(s) return FALSE; else return TRUE;3.18 试写一个判别表达式中开、闭括号是否配对出现的算法。实现下列函数：Status MatchCheck(SqList exp);/* 顺序表exp表示表达式； */* 若exp中的括号配对，则返回TRUE，否则返回FALSE */* 注：本函数不使用栈 */顺序表类型定义如下：typedef struct ElemType *elem; int length; int listsize; SqList; / 顺序表Status MatchCheck(SqList exp)/* 顺序表exp表示表达式； */* 若exp中的括号配对，则返回TRUE，否则返回FALSE */* 注：本函数不使用栈 */ int i,j=0; for(i=0;iexp.length;i+) if(exp.elemi=() j+; else if(exp.elemi=)&j=0) return FALSE; else j-; if(j=0) return TRUE; else return FALSE;3.19 假设一个算术表达式中可以包含三种括号：圆括号( 和)，方括号和和花括号和，且这三种括号可按任意的次序嵌套使用（如：()）。编写判别给定表达式中所含括号是否正确配对出现的算法(已知表达式已存入数据元素为字符的顺序表中)。 实现下列函数：Status MatchCheck(SqList exp); /* 顺序表exp表示表达式； */* 若exp中的括号配对，则返回TRUE，否则返回FALSE */顺序表类型定义如下：typedef struct ElemType *elem; int length; int listsize; SqList; / 顺序表Stack是一个已实现的栈。可使用的相关类型和函数：typedef char SElemType; / 栈Stack的元素类型Status InitStack(Stack &s);Status Push(Stack &s, SElemType e);Status Pop(Stack &s, SElemType &e);Status StackEmpty(Stack s);Status GetTop(Stack s, SElemType &e);Status MatchCheck(SqList exp)/* 顺序表exp表示表达式； */* 若exp中的括号配对，则返回TRUE，否则返回FALSE */ Stack s; int i; SElemType e; InitStack(s); for(i=0;i=1&gi0-1j0=color) ChangeColor(g,m,n,c,i0-1,j0); if(j0-1=1&gi0j0-1=color) ChangeColor(g,m,n,c,i0,j0-1); if(i0+1=m&gi0+1j0=color) ChangeColor(g,m,n,c,i0+1,j0); if(j0+1=a&ei=0 g(m,n) = g(m-1,2n)+n 当m0,n=0并根据算法画出求g(5,2)时栈的变化过程。实现下列函数：int g(int m, int n); /* if m0 or n0 then return -1. */int G(int m, int n)/* if m0 or n0 then return -1. */ if(m0|n=0) return 0; else return G(m-1,2*n)+n;3.25 试写出求递归函数F(n)的递归算法，并消除递归： F(n) = n+1 当n=0 F(n) = nF(n/2) 当n0实现下列函数：int F(int n);/* if n0 then return -1. */int F(int n)/* if n0 then return -1. */ if(nnext=rear; return OK;Status EnCLQueue(CLQueue &rear, ElemType x) LinkList p; p=(LinkList)malloc(sizeof(LNode); if(p=NULL)exit(0); else p-data=x; p-next=rear-next; rear-next=p; rear=p; return OK;Status DeCLQueue(CLQueue &rear, ElemType &x) LinkList p; if(rear=rear-next)return ERROR; p=rear-next-next; x=p-data; rear-next-next=p-next; free(p); return OK;3.29 如果希望循环队列中的元素都能得到利用，则需设置一个标志域tag，并以tag的值为0或1来区分，尾指针和头指针值相同时的队列状态是空还是满。试编写与此结构