广工数据结构参考答案全(anyview)

1、广工数据结构anyview 80道上机题 1.void Descend(int &x, int &y, int &z)/* 按从大到小顺序返回x，y和z的值 */ int t; if(xz) t=z; z=x; x=t; if(yx) t=x; x=y; y=t; 2.Status Fibonacci(int k, int m, int &f) /* 求k阶斐波那契序列的第m项的值f */ int *a; int i=1; if(k2|m0) return ERROR; if(mk) if(m=k-1) f=1; else f=0; return OK; a=(int*)malloc(m+1)

2、*sizeof(int); for(i=0;ik-1;i+) ai=0; i=k+1; ak-1=1; ak=1; while(i=m) ai=2*ai-1-ai-k-1; i+; f=am; return OK;3.void Scores(ResultType *result, ScoreType *score)/* 求各校的男、女总分和团体总分, 并依次存入数组score */* 假设比赛结果已经储存在result 数组中, */* 并以特殊记录 , male, , , 0 （域scorce=0）*/* 表示结束 */ int i; for(i=0;resulti.score!=0;i+)

3、 scoreresulti.schoolname-A.totalscore+=resulti.score; if(resulti.gender=male) scoreresulti.schoolname-A.malescore+=resulti.score; else scoreresulti.schoolname-A.femalescore+=resulti.score; 4Status Series(int ARRSIZE, int a) /* 求i!*2i序列的值并依次存入长度为ARRSIZE的数组a； */* 若所有值均不超过MAXINT，则返回OK，否则返回OVERFLOW */ i

4、nt i=1,b=1,na=1; while(iMAXINT) return OVERFLOW; ai-1=na*b; i+; if(iARRSIZE+1) return OVERFLOW; return OK;5float Polynomial(int n, int a, float x)/* 求一元多项式的值P(x)。 */* 数组a的元素ai为i次项的系数，i=0,.,n */ float ans=a0,t=1.0; int i=1; while(ix) L.elemi+1=L.elemi; i-; L.elemi+1=x; L.length+;7char Compare(SqList

5、A, SqList B)/ 比较顺序表A和B, / 返回, 若A, 若AB int i=0; while(A.elemi=B.elemi&iA.length&iB.elemi|i=B.length) return ; return next;/第一个元素 while(p-next!=NULL) if(p-data=x) return p; p=p-next; return NULL;9int Length(LinkList L)/ Return the length of the linked list / whose head node is pointed by L int i=0; wh

6、ile(L-next!=NULL) i+; L=L-next; return i;10void Insert(LinkList &L, int i, ElemType b) int j=1; if(i=0) return ; LinkList p,q; q=L; p=(LinkList)malloc(sizeof(LNode); p-data=b; if(i=1) p-next=L; L=p; else while(jnext!=NULL) j+; q=q-next; if(jnext=q-next; q-next=p; 11void Delete(LinkList &L, int i) in

7、t j=1; LinkList p,q; p=L; if(i=0) return ; if(i=1) L=L-next; return; while(jnext; if(p-next=NULL) return; q=p; p=p-next; q-next=p-next; free(p);12void Purge(LinkList &L) LinkList cur,temp,del;/cur当前结点,temp遍历下一个结点,del删除结点 cur=L-next; temp=cur-next; if(cur=NULL|temp=NULL) return;/空或者只有一个元素,返回 while(cu

8、r-next) temp=cur-next; while(temp) if(cur-data=temp-data) del=temp; temp=temp-next;/temp指向下一个元素 cur-next=temp; /删除后连接 free(del); else temp=temp-next; cur=cur-next; /时间复杂度O(n*n)13void Inverse(SqList &L) int i=0; ElemType t; while(inext; p=p-next; L-next-next=NULL; if(!p) return ; while(p) k=q; q=p; p

9、=p-next; q-next=k; L-next=q;15void Merge(LinkList ha, LinkList hb, LinkList &hc)/* 依题意，合并带头结点的单链表ha和hb为hc */ LinkList pa,pb,pc; hc=ha; pc=hc; pa=ha-next; pb=hb-next; if(!pa) hc=hb;return; if(!pb) hc=ha;return; while(pa|pb) pc-next=pa; if(!pb) return; pc=pc-next; pa=pa-next; pc-next=pb; if(!pa) retur

10、n; pb=pb-next; pc=pc-next; 16void Union(LinkList &lc, LinkList &la, LinkList &lb) LinkList pa,pb,pc; pa=la-next;pb=lb-next; /合并 lc=pc=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; pa=pb=lc-next; /逆置 pa=pa-next; lc-next-next

11、=NULL; if(!pa) return ; while(pa) pc=pb; pb=pa; pa=pa-next; pb-next=pc; lc-next=pb; 17ElemType DeleteNode(LinkList s) /* 删除指针s所指结点的前驱结点，并返回被删结点的元素值 */ LinkList p; ElemType a; p=s-next; while(p-next-next!=s) p=p-next; a=p-next-data; p-next=s; return a;18void PerfectBiLink(BiLinkList &CL) BiLinkList p

12、re,net,t; pre=t=CL; net=t-next; while(net!=t) net-prev=pre; pre=net; net=net-next; t-prev=pre;19void Split(LinkList &lc, LinkList &ld, LinkList &lo, LinkList ll) LinkList itor,pc,pd,po; itor=ll-next; lc=(LinkList)malloc(sizeof(LNode);pc=lc; ld=(LinkList)malloc(sizeof(LNode);pd=ld; lo=(LinkList)mallo

13、c(sizeof(LNode);po=lo; while(itor) if(itor-data=a&itor-datadata=A&itor-datanext=itor; pc=itor; else if(itor-datadata=0) pd-next=itor; pd=itor; else po-next=itor; po=itor; itor=itor-next; pc-next=lc; pd-next=ld; po-next=lo;20void ReverseEven(BiLinkList &L) BiLinkList p1,p2; p1=L-next;p2=L; while(p1-n

14、ext!=L) if(p1-next-next!=L) p1-next=p1-next-next;/接隔一个 p1=p1-next;/去到隔一个处 p2-prev=p1-prev;/p2的前驱为p1前驱 p1-prev=p1-prev-prev; p2-prev-next=p2;/p1的前驱的后继为p2 p2=p2-prev;/p2去到p2前驱 else p2-prev=p1-next; p1-next-next=p2; p2=p2-prev; break; p1-next=p2; p2-prev=p1;21float Evaluate(SqPoly pn, float x)/* pn.dat

15、ai.coef 存放ai， */* pn.datai.exp存放ei (i=1,2,.,m) */* 本算法计算并返回多项式的值。不判别溢出。 */* 入口时要求0e1e2.em，算法内不对此再作验证*/ int i,j; float ans=0.0,s; for(i=0;ipn.length;i+) s=1; for(j=0;jnext; while(p!=pa) if(p-exp=0) pa-next=p-next; free(p); p=pa-next; else p-coef *= p-exp; p-exp-; p=p-next; 23Status match(char *str)/*

16、 若str是属该模式的字符序列，*/* 则返回TRUE，否则返回FALSE */ Stack s; InitStack(s); SElemType e; int i=0; while(stri!=&) Push(s,stri); i+; i+; while(stri!=) GetTop(s,e); if(StackEmpty(s)|e!=stri) return FALSE; Pop(s,e); i+; if(!StackEmpty(s) return FALSE; return TRUE;24Status MatchCheck(SqList exp)/* 顺序表exp表示表达式； */* 若

17、exp中的括号配对，则返回TRUE，否则返回FALSE */* 注：本函数不使用栈 */ int i=0,count=0; while(iexp.length) if(exp.elemi=() count+; if(exp.elemi=) count-; if(count0) return FALSE; i+; if(!count) return TRUE; return FALSE;25Status MatchCheck(SqList exp)/* 顺序表exp表示表达式； */* 若exp中的括号配对，则返回TRUE，否则返回FALSE */ int i=0; Stack s; SElem

18、Type e; InitStack(s); while(iexp.length) if(exp.elemi=(|exp.elemi=|exp.elemi=) Push(s,exp.elemi); else if(exp.elemi=)|exp.elemi=|exp.elemi=) if(StackEmpty(s) return FALSE; else GetTop(s,e); switch(exp.elemi) case ): if(e=() Pop(s,e); break; else return FALSE; case : if(e=) Pop(s,e); break; else retu

19、rn FALSE; case : if(e=) Pop(s,e); break; else return FALSE; default: break; i+; if(StackEmpty(s) return TRUE; return FALSE;26void ChangeColor(GTYPE g, int m, int n, char c, int i0, int j0)/* 在g1.m1.n中，将元素gi0j0 */* 所在的同色区域的颜色置换为颜色c */ char color=gi0j0; gi0j0=c; int dx4=-1,+1,0,0,dy4=0,0,-1,+1,i; for(

20、i=0;i4;i+) if(i0+dxi=m&j0+dyi=1&i0+dxi=1&gi0+dxij0+dyi=color) ChangeColor(g,m,n,c,i0+dxi,j0+dyi); 27char *RPExpression(char *e)/* 返回表达式e的逆波兰式 */ int i,j=0; char *str; str=(char*)malloc(30*sizeof(char); SElemType e1; Stack so; for(i=0;ei!=0;i+) if(ei=0|ei=a&ei=A&ei=Z)/入数字栈 strj+=ei; else if(ei=(|ei=|

21、StackEmpty(so)/入栈 Push(so,ei); else if(ei=) while(Top(so)!=()/将()内的操作符做运算 strj+=Top(so);/操作符入栈 Pop(so,e1); Pop(so,e1); else if(ei=) while(Top(so)!=) strj+=Top(so); Pop(so,e1); Pop(so,e1); else if(ei=+|ei=-) while(Top(so)=*|Top(so)=/|Top(so)=+|Top(so)=-)/优先计算 strj+=Top(so); Pop(so,e1); Push(so,ei); e

22、lse if(ei=*|ei=/) while(Top(so)=*|Top(so)=/) strj+=Top(so); Pop(so,e1); Push(so,ei); while(!StackEmpty(so) strj+=Top(so); Pop(so,e1); strj=0; return str;28int G(int m, int n)/* if m0 or n0 then return -1. */ if(m0|n=0) return 0; if(m0&n=0) return G(m-1,2*n)+n;29int F(int n)/* if n0 then return -1. *

23、/ if(n0) return n*F(n/2);30Status InitCLQueue(CLQueue &rear) rear=(LinkList)malloc(sizeof(LNode); if(!rear) exit(0); rear-next=rear; return 1;Status EnCLQueue(CLQueue &rear, ElemType x) LinkList p; p=(LinkList)malloc(sizeof(LNode); if(!p) exit(0); p-data=x; p-next=rear-next; rear-next=p; rear=p; ret

24、urn 1;Status DeCLQueue(CLQueue &rear, ElemType &x) LinkList p; p=(LinkList)malloc(sizeof(LNode); if(!p) exit(0); if(rear=rear-next) return 0; p=rear-next-next; x=p-data; rear-next-next=p-next; free(p); return 1;31Status EnCQueue(CTagQueue &Q, QElemType x) if(Q.front=Q.rear&Q.tag) return 0; Q.elemQ.r

25、ear=x; Q.rear=(Q.rear+1)%MAXSIZE; return 1;Status DeCQueue(CTagQueue &Q, QElemType &x) if(Q.front=Q.rear&!Q.tag) return 0; x=Q.elemQ.front; Q.front=(Q.front+1)%MAXSIZE; return 1;32Status EnCQueue(CLenQueue &Q, QElemType x) if(Q.length=MAXQSIZE) return ERROR; Q.rear=(Q.rear+1)%MAXQSIZE;/队尾下一个空位置 Q.el

26、emQ.rear=x; Q.length+; return 1;Status DeCQueue(CLenQueue &Q, QElemType &x) if(Q.length=0) return ERROR; x=Q.elem(MAXQSIZE+Q.rear-Q.length+1)%MAXQSIZE; Q.length-; return 1;33Status Palindrome(char *word)/* 利用栈和队列判定字符序列word是否是回文 */ Stack s; Queue que; InitStack(s);InitStack(que); char a,b; int i=0; w

27、hile(wordi!=) Push(s,wordi); EnQueue(que,wordi); i+; while(!StackEmpty(s)&!QueueEmpty(que) Pop(s,a); DeQueue(que,b); if(a!=b) return ERROR; return 1;35void Replace(StringType &S, StringType T, StringType V)/* 以串 v 置换串 s 中出现的所有和串 t 相同的非空串 */ int i=1; StringType st,ss,sm; InitStr(st);InitStr(ss);InitS

28、tr(sm); while(i=StrLength(S) ss=SubString(S,i,StrLength(T); if(StrCompare(ss,T)=0) /剪断再接合 sm=SubString(S,1,i-1); /前半段 st=SubString(S,i+StrLength(T),StrLength(S)-i);/后半段 StrAssign(S,sm); Concat(S,V); Concat(S,st); /接完后还原S i+=StrLength(V)-1;/i移动到I+V的距离 else i+; 36void DelSubString(StringType &scrStr,

29、StringType subStr)/* Remove all substring matching subStr from scrStr. */ int i=1; StringType sp,sn,st; InitStr(sp);InitStr(sn);InitStr(st); while(i=StrLength(scrStr) st=SubString(scrStr,i,StrLength(subStr); if(StrCompare(st,subStr)=0) sp=SubString(scrStr,1,i-1);/前半段 sn=SubString(scrStr,i+StrLength(

30、subStr),StrLength(scrStr)-i);/后半段 StrAssign(scrStr,sp); Concat(scrStr,sn); i-; i+; 37Status Replace(SString& s, SString t, SString v)/* 用串v替换串s中所有和串t匹配的子串。 */* 若有与t匹配的子串被替换，则返回TRUE；*/* 否则返回FALSE */ int i=1,j,tot=0,k=0; SString str; while(i=s0) j=1; while(jt0) tot=1; for(j=1;j=v0;j+) str+k=vj; i=i+t0

31、; else str+k=si; i+; for(i=1;i=k;i+) si=stri; s0=k; if(tot) return TRUE; return FALSE;38Status DelSub(SString &s, SString t)/* 从串s中删除所有和串t匹配的子串。 */* 若有与t匹配的子串被删除，则返回TRUE；*/* 否则返回FALSE */ int i=1,j,tot=0; while(i=s0) j=1; while(jt0) tot=1; for(j=i+t0;j=s0;j+) sj-t0=sj; sj-t0=0; s0-=t0; else i+; if(tot) return TRUE; return FALSE;39Status Concat(HString &S, HString S1, HString S2) /* 用S返回由S1和S2联接而成的新串 */ int i; if(S.ch) free(S.ch); S.ch=(char*)realloc(S