数据结构题集C语言版答案_严蔚敏吴伟民[1].doc

第一章16void Descend(int &x, int &y, int &z) int t; if(xy) t=x;x=y;y=t; if(xz) t=x;x=z;z=t; if(yz) t=y;y=z;z=t; 17Status Fibonacci(int k, int m, int &f) /* 求k阶斐波那契序列的第m项的值f */ int i,j,sum,temp20; if(k2|m0) return ERROR; if(mk-1) f=0; else if(m=k-1) f=1; else for(i=0;i=k-2;i+) tempi=0; tempk-1=1; for(i=k;i=m;i+) sum=0; for(j=i-k;ji;j+) sum+=tempj; tempi=sum; f=tempm; return OK;/ Fibonacci18void Scores(ResultType *result, ScoreType *score)/* 求各校的男、女总分和团体总分, 并依次存入数组score */* 假设比赛结果已经储存在result 数组中, */* 并以特殊记录 , male, , , 0 （域scorce=0）*/* 表示结束 */ int i=0; char s; while(resulti.sport!=NULL) switch(resulti.schoolname) case A: score0.totalscore+=resulti.score; if(resulti.gender=male) score0.malescore+=resulti.score; else score0.femalescore+=resulti.score; break; case B: score1.totalscore+=resulti.score; if(resulti.gender=male) score1.malescore+=resulti.score; else score1.femalescore+=resulti.score; break; case C: score2.totalscore+=resulti.score; if(resulti.gender=male) score2.malescore+=resulti.score; else score2.femalescore+=resulti.score; break; case D: score3.totalscore+=resulti.score; if(resulti.gender=male) score3.malescore+=resulti.score; else score3.femalescore+=resulti.score; break; case E: score4.totalscore+=resulti.score; if(resulti.gender=male) score4.malescore+=resulti.score; else score4.femalescore+=resulti.score; break; i+; for(s=A;s=E;s+) printf(School %c:n,s); printf(Total score of male:%dn,scorei.malescore); printf(Total score of female:%dn,scorei.femalescore); printf(Total score of all:%dnn,scorei.totalscore); 19Status Series(int ARRSIZE, int a) /* 求i!*2i序列的值并依次存入长度为ARRSIZE的数组a； */* 若所有值均不超过MAXINT，则返回OK，否则返回OVERFLOW */ int last,i;last=1;for (i=1;iMAXINT) return OVERFLOW; last=ai-1; return OK;20float Polynomial(int n, int a, float x)/* 求一元多项式的值P(x)。 */* 数组a的元素ai为i次项的系数，i=0,.,n */ int j,i;float y,s;y=0;for(j=n;j0;j-)y=x*(y+aj);s=y+a0; return(s); 第二章12char Compare(SqList A, SqList B)/ 比较顺序表A和B, / 返回, 若A, 若AB int i;for(i=1;i=A.length&iB.elemi?:B.length?:next)!=NULL;p=p-next,k+); return k;19void DeleteSome(LinkList &L, ElemType mink, ElemType maxk)/* Delete all the elements which value is between mink and */* maxk from the single sorted LinkList with head pointer L.*/ LinkList p,q,pre; pre=L; while(pre-next&pre-next-datanext; p=pre-next; while(p&p-datanext; free(q); pre-next=p; 21 void Inverse(SqList &L) int i,j; ElemType p; for(i=0,j=L.length-1;inext; q=p-next; if(p-next!=NULL&q-next!=NULL) s=q-next;p-next=NULL; while(s-next) q-next=p;p=q;q=s;s=s-next; q-next=p;s-next=q;L-next=s; 31ElemType DeleteNode(LinkList s) /* 删除指针s所指结点的前驱结点，并返回被删结点的元素值 */ LNode *p; int e; p=s; while(p-next-next!=s) p=p-next; e=p-next-data; p-next=s; return e;41void Difference(LinkedPoly &pa)/* 稀疏多项式 pa 以循环链表作存储结构， */* 将此链表修改成它的导函数，并释放无用结点 */ LinkedPoly p,q,t; p=pa-next; t=pa; while(p!=pa) if(p-exp=0) q=p; p=q-next; t-next=p;free(q); p-coef*=p-exp; p-exp-; t=p; p=p-next; 13LinkList 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 LNode*p; for(p=L-next;p&p-data!=x;p=p-next); return p;16Status DeleteAndInsertSub(LinkList &la, LinkList &lb, int i, int j, int len)/ la和lb分别指向两个单链表中第一个结点， */* 本算法是从la表中删去自第i个元素起共len个元素，*/* 并将它们插入到lb表中第j个元素之前， */* 若lb表中只有j-1个元素，则插在表尾。 */ if(i=0 | j=0 | lennext=la; t-next=lb; la=s; lb=t; while(s-next!=NULL & xnext; x+; if(s-next=NULL & xnext; lb=lb-next; free(s); free(t); return INFEASIBLE; r=o=s-next; while(o!=NULL & znext; z+; if(o=NULL | znext; lb=lb-next; free(s); free(t); return INFEASIBLE; while(t-next!=NULL & ynext; y+; if(t-next=NULL & ynext; lb=lb-next; free(s); free(t); return INFEASIBLE; s-next=o-next; o-next=t-next; t-next=r; s=la; t=lb; la=la-next; lb=lb-next; free(s); free(t); return OK; 20void Purge(LinkList &L) LinkList p,t,r; p=L; t=p-next; while(p-next-next!=NULL) p=p-next; t=t-next; while(t-next!=NULL & t-data=p-data) r=t; p-next=t-next; free(r); t=t-next; if(t-next=NULL & p-data=t-data) r=t; p-next=t-next; free(r); 23void Merge(LinkList ha, LinkList hb, LinkList &hc)/* 依题意，合并带头结点的单链表ha和hb为hc */ LNode*p; LNode*q; LNode*s; LNode*t; p=ha-next;q=hb-next;hc=ha; while(p&q) s=p-next;p-next=q; if(s) t=q-next;q-next=s; p=s;q=t; 26void Intersect(LinkList &hc, LinkList ha, LinkList hb) LNode *p,*q,*s,*pc; pc=hc; p=ha-next;q=hb-next; 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; 32void PerfectBiLink(BiLinkList &CL) BiNode*p; for(p=CL;!p-next-prev;p=p-next) p-next-prev=p; 33void Split(LinkList &lc, LinkList &ld, LinkList &lo, LinkList ll) LNode *p,*q,*r,*s; s=ll-next; lc=(LinkList)malloc(sizeof(LNode);p=lc; ld=(LinkList)malloc(sizeof(LNode);q=ld; lo=(LinkList)malloc(sizeof(LNode);r=lo; /建立头结点 while(s) if(s-data=A&s-datadata=a&s-datanext=s;p=s; else if(s-data=0&s-datanext=s;q=s; else r-next=s;r=s; s=s-next; p-next=lc;q-next=ld;r-next=lo; 37void ReverseEven(BiLinkList &L) BiNode *p; p=L-next; if(p-next=L) p-prev=L;L-prev=p; else while(p-next!=L&p-next-next!=L) p-next=p-next-next; p=p-next; if(p-next=L) p-next=L-prev-prev; else p-next=L-prev; p=p-next; while(p-prev-prev!=L) p-next=p-prev-prev; p=p-next; p-next=L; for(p=L;p-next!=L;p=p-next) p-next-prev=p; L-prev=p; 39float Evaluate(SqPoly pn, float x)/* pn.datai.coef 存放ai， */* pn.datai.exp存放ei (i=1,2,.,m) */* 本算法计算并返回多项式的值。不判别溢出。 */* 入口时要求0e1e2.coef!=NULL) while(exexp) xp*=x; ex+; sum+=q-coef*xp; q+; return sum;第三章15Status InitStack(TwoWayStack &tws, int size) tws.elem = (SElemType *)malloc( size * sizeof(SElemType) ); if( !tws.elem ) exit(OVERFLOW); tws.size = size; tws.top0 = 0; tws.top1 = size - 1; return OK;Status Push(TwoWayStack &tws, int i, SElemType x) if( tws.top0 + 1 tws.top1 ) return ERROR; else if( i = 0 ) tws.elemtws.top0+ = x; else tws.elemtws.top1- = x; return OK;Status Pop(TwoWayStack &tws, int i, SElemType &x) if( i = 0 ) if( tws.top0 = 0 ) return ERROR; else x = tws.elem-tws.top0; else if( tws.top1 = tws.size - 1 ) return ERROR; else x = tws.elem+tws.top1; return OK;16void SwitchYard(SqList train, char *s)/* 顺序表train表示列车，其元素取值H或S， */* 分别表示硬席或软席车厢； */* 以U和O分别表示入栈和出栈操作； */* 函数用参数s以UO串的形式，返回对该列车 */* 进行软席在前，硬席在后的编组的操作序列。*/ ElemType *p; int i,count=0,j; p=train.elem; while(*p) if(*p=H) si=U;+count; else if(*p=S) si=U;si+1=O;i=i+1; p+;i+; for(j=1;j=count;j+)si+=O; 19Status MatchCheck(SqList exp)/* 顺序表exp表示表达式； */* 若exp中的括号配对，则返回TRUE，否则返回FALSE */ SElemType p; int i; float j; j=exp.length%2;if(j)return FALSE; SqStack s; if(exp.elem0=)| exp.elem0=|exp.elem0=) return FALSE; InitStack(s); for(i=0;iexp.length;+i) switch(exp.elemi) case (: Push(s,exp.elemi);break; case : Push(s,exp.elemi);break; case : Push(s,exp.elemi);break; case ): GetTop(s,p);if(p=()Pop(s,p);break; case : GetTop(s,p);if(p=)Pop(s,p);break; case : GetTop(s,p);if(p=)Pop(s,p);break; if(StackEmpty(s) return TRUE; else return FALSE;21char *RPExpression(char *e)/* 返回表达式e的逆波兰式 */ int i; char *p,c; p=(char*)malloc(strlen(e)*sizeof(char); Stack s; InitStack(s); for(;*e!=0;e+) if(*e!=+)&(*e!=-)&(*e!=*)&(*e!=/)&(*e!=()&(*e!=) *(p+i)=*e; i+; elseswitch(*e)case(:Push(s,*e);break;case):while(Top(s)!=()Pop(s,c);*(p+i)=c;i+; Pop(s,c);break; case+: case-:while(!(StackEmpty(s)&!(Top(s)=() Pop(s,c); *(p+i)=c; i+; Push(s,*e);break; case*: case/:if(Top(s)=*|Top(s)=/) Pop(s,c); *(p+i)=c; i+; Push(s,*e); else Push(s,*e);break; while(!(StackEmpty(s) Pop(s,c); *(p+i)=c; i+; *(p+i)=0;return p;24int G(int m, int n)/* if m0 or n0 then return -1. */ if(m0|n=0) return 0; else return (n+ G(m-1,2*n);3.28 假设以带头结点的循环链表表示队列，并且只设一个指针指向队尾元素结点(注意不设头指针)，试编写相应的队列初始化、入队列和出队列的算法。实现下列函数：Status InitCLQueue(CLQueue &rear);Status EnCLQueue(CLQueue &rear, ElemType x);Status DeCLQueue(CLQueue &rear, ElemType &x);Status InitCLQueue(CLQueue &rear) rear=(LNode*)malloc(sizeof(LNode); if(!rear) return ERROR; rear-next=rear; return OK;Status EnCLQueue(CLQueue &rear, ElemType x) LinkList p; p=(LNode*)malloc(sizeof(LNode); if(!p) return ERROR; 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来区分，尾指针和头指针值相同时的队列状态是空还是满。试编写与此结构相应的入队列和出队列的算法，并从时间和空间角度讨论设标志和不设标志这两种方法的使用范围（比如，当循环队列容量较小而队列中每个元素占的空间较多时，那一种方法较好？）。实现下列函数：Status EnCQueue(CTagQueue &Q, QElemType x);Status DeCQueue(CTagQueue &Q, QElemType &x);本题的循环队列CTagQueue的类型定义如下：typedef char QElemType;typedef struct QElemType elemMAXQSIZE; int tag; int front; int rear; CTagQueue;Status EnCQueue(CTagQueue &Q, QElemType x) if(Q.tag=1&Q.front=Q.rear)return ERROR; Q.elemQ.rear=x; Q.rear=(Q.rear+1)%MAXQSIZE; if(Q.rear=Q.front)Q.tag=1; return OK;Status DeCQueue(CTagQueue &Q, QElemType &x) if(Q.tag=0&Q.front=Q.rear)return ERROR; x=Q.elemQ.front; Q.front=(Q.front+1+MAXQSIZE)%MAXQSIZE; if(Q.rear=Q.front)Q.tag=0; return OK;30Status EnCQueue(CLenQueue &Q, QElemType x) if( Q.length = MAXQSIZE ) return ERROR; Q.rear = (Q.rear + 1) % MAXQSIZE; Q.elemQ.rear = x; Q.length+; return OK;Status DeCQueue(CLenQueue &Q, QElemType &x) int len; if( Q.length = 0 ) return ERROR; len = (Q.rear - Q.length + 1 + MAXQSIZE) % MAXQSIZE; x = Q.elemlen; Q.length-; return OK; 31Status Palindrome(char *word)/* 利用栈和队列判定字符序列word是否是回文 */ int i = 0; char x, y; Stack S; InitStack( S ); Queue Q; InitQueue( Q ); while( wordi != ) EnQueue( Q, wordi ); Push( S, wordi ); +i; while( !StackEmpty( S ) ) DeQueue( Q, x ); Pop( S, y ); if( x != y ) return ERROR; return OK;20void ChangeColor(GTYPE g, int m, int n, char c, int i0, int j0)/* 在g1.m1.n中，将元素gi0j0 */* 所在的同色区域的颜色置换为颜色c */int x,y,old; Stack s; old=gi0j0; StackInit(s,m*n*2); Push(s,i0); Push(s,j0); while(!StackEmpty(s) Pop(s,y); Pop(s,x); if(x1) if(gx-1y=old) gx-1y=c; Push(s,x-1); Push(s,y); if(y1) if(gxy-1=old) gxy-1=c; Push(s,x); Push(s,y-1); if(xm) if(gx+1y=old) gx+1y=c; Push(s,x+1); Push(s,y); if(yn) if(gxy+1=old) gxy+1=c; Push(s,x); Push(s,y+1); /while25int F(int n)/* if n0 then return -1. */ if (n=1;i-) StrAssign(c,SubString(s,i,1); Concat(r,c ); StrAssign(s,r);12Void pe &S, StringType T, StringType V)/* 以串 v 置换串 s 中出现的所有和串 t 相同的非空串 */ StringType start; StringType tail; int i; for(i=1;i=StrLength(S)-StrLength(T)+1;i+) if(!StrCompare(SubString(S,i,StrLength(T),T) StrAssign(start,SubString(S,1,i-1); StrAssign(tail,SubString(S,StrLength(T)+i,StrLength(S)-StrLength(T)-i+1); Concat(start,V); StrAssign(S,start); Concat(S,tail); i-=1; 13void DelSubString(StringType &scrStr, StringType subStr)/* Remove all substring matching subStr from scrStr. */ int i,a,b; a=StrLength(scrStr); b=StrLength(subStr); StringType h; StringType t; InitStr(h); InitStr(t);for(i=1;i=a-b+1;i+)if(! StrCompare( SubString (scrStr,i,b),subStr) StrAssign(h,SubString(scrStr,1,i-1); StrAssign(t,SubString(scrStr,i+b,a-b+1-i); Concat(h,t); StrAssign (scrStr,h); i-; 17Status Replace(SString& s, SString t, SString v)/* 用串v替换串s中所有和串t匹配的子串。 */* 若有与t匹配的子串被替换，则返回TRUE；*/* 否则返回FALSE */ int i,j,k,l;if(!s0)return FALSE;for(i=1;it0) /找到了与T匹配的子串:分三种情况处理 if(t0=v0) for(l=1;l=t0;l+) /新子串长度与原子串相同时:直接替换 si+l-1=vl; else if(t0=i+t0;l-) sl+v0-t0=sl; for(l=1;l=v0;l+) si+l-1=vl; else /新子串长度小于原子串时:先将后部左移 for(l=i+v0;l=s0+v0-t0;l+) sl=sl-v0+t0; for(l=1;l=v0;l+) si+l-1=vl; s0=s0-t0+v0; i+=v0; /if /for return TRUE;/String_Replace 20Status DelSub(SString &s, SString t)/* 从串s中删除所有和串t匹配的子串。 */* 若有与t匹配的子串被删除，则返回TRUE；*/* 否则返回FALSE */ int i,j,k,n=1,tag; if(!s0)return FALSE; if(s=t)s0=0;return TRUE; while(n=s0) i=1;j=1; while(i=s0&j=t0) if(si=tj)+i;+j; elsei=i-j+2;j=1; if(j=t0+1) for(k=i;k=s0;k+)sk-t0=sk; s0-=t0;tag=1;n+; if(tag)return TRUE; if(!tag)return FALSE; 26.Status StrIns