2016广工AnyView数据结构第1

1、/*【题目】试写一算法，如果三个整数a,bc的值和不是依次非递增的，则通过交换，令其为非递增。*/voidDescendant&a,int&b,int&c)/*通过交换，令a=b=c*/if(c=b&b=a)return;elseif(ab)swap(a,b);if(ac)swap(a,c);if(bc)swap(b,c);voidswap(int&a,int&b)inttemp;temp=a;a=b;b=a;/*【题目】试编写算法求一元多项式P(x)=a0+a1x+a2xA2+.+anxAn的值P(xO)，并确定算法中每一语句的执行次数和整个算法的时间复杂度。floatPolynomial(

2、intn,inta,floatx)/求一元多项式的值P(x)*/*数组a的元素ai为i次项的系数，i=o,n*/floatanswer=a0;floattemp=1.0;for(inti=1;i=n;i+)temp*二x;answer+=ai*temp;returnanswer;/*【题目】已知k阶裴波那契序列的定义为f(0)=0,f(1)=0,f(k-2)=0,f(k-1)=1;f(n)=f(n-1)+f(n-2)+f(n-k),n=k,k+1,试编写求k阶裴波那契序列的第m项值的函数算法，k和m均以值调用的形式在函数参数表中出现。*/StatusFibonacci(intk,intm,in

3、t&f)/求k阶斐波那契序列的m项的f*/*第值if(k=1|m0)returnERROR;elseif(m=k-1)f=1;elseif(m=0)f=0;elseinti,j,sum;int*t;t=(int*)malloc(m*sizeof(int);for(i=0;iv=k-2;i+)ti=0;tk-1=1;for(i=k;i=m;i+)sum=0;for(j=i-k;jv=i;j+)sum+=tj;ti=sum;f=tm;returnOK;/*【题目】试编写算法，计算aO.n-1的第i-1个分量中算机中允许的整数最大值为i!x2Ai的值并存入数组(i=1,2,?,n)。假设计MAXIN

4、T，则当对某个k(1kMAXINT时，应按出错处理。注意选择你认为较好的出错处理方法。* StatusSeries(inta,intn)/求i!*2Ai序列的值并依次存入长度n的数a;*/7组OK,OVERFLOW*/若所有值均不超过MAXINT，则返否则/回、*intt=1,p=1;for(inti=1;iv=n;i+)t*=i;p*=2;ai-1=t*p;if(ai-1MAXINT)returnERROR;returnOK;/*【题目】假设有A、B、C、D、E五个高等院校进行田径对抗赛，各院校的单项成绩均以存入计算机并构成一张表，表中每一行的形式为：项目名称性别校名成绩得分编写算法，处理上

5、述表格，以统计各院校的男、女总分和团体总分，并输出voidScores(ResultType*result,ScoreType*score)求各校的男、女总分和团体总/*分score,并依次存入数组*/*/*假设比赛结果已经储存在并以特殊记录,male,HIVCresult数组中，(域scorce=0)*/*/*/*表示结束inti=0;while(resulti.sport!=NULL)switch(resulti.schoolname)caseA:score0.totalscore+=resulti.score;if(resulti.gender=male)score0.malescore

6、+=resulti.score;elsescore0.femalescore+=resulti.score;break;caseB:score1.totalscore+=resulti.score;if(resulti.gender=male)score1.malescore+=resulti.score;elsescore1.femalescore+=resulti.score;break;caseC:score2.totalscore+=resulti.score;if(resulti.gender=male)score2.malescore+=resulti.score;elsescor

7、e2.femalescore+=resulti.score;break;caseD:score3.totalscore+=resulti.score;if(resulti.gender=male)score3.malescore+=resulti.score;elsescore3.femalescore+=resulti.score;break;caseE:score4.totalscore+=resulti.score;if(resulti.gender=male)score4.malescore+=resulti.score;elsescore4.femalescore+=resulti.

8、score;break;i+;/*【题目】试写一算法，对序列序列的类型定义为：typedefstructElemType*elem;S的i个元素赋以e。第值intlength;Sequence;*/StatusAssign(Sequence&S,inti,ElemTypee)/对序列S的第i个元素赋以值e，并返回OK。*/*若Si不合法，则赋值失败，返回ERROR*/if(S.lengthS.length)returnERROR;elseS.elemi=e;returnOK;/*n的一维数组a构建一个序列S【题目】试写一算法，由长度为序列的类型定义为：typedefstructElemType

9、*elem;intlength;Sequence;*/StatusCreateSequence(Sequence&S,intn,ElemType*a)OK。*/*/由长度为n的一维数组a构建一个序S，并返*列回若构建失败，则返回ERROR/if(n1)returnERROR;elseS.elem=(ElemType*)malloc(n*sizeof(ElemType);S.elem0=a0;for(inti=1;idata=x;returnp;/*【题目】链表的结点和指针类型定义如下typedefstructLNodeElemTypedata;structLNode*next;LNode,*L

10、inkList;试写一函数，构建长度为2且两个结点的值依次为x和y的链表*/LinkListCreateLinkList(ElemTypex,ElemTypey)y的链表。*/*/构建其两个结点的值依次为x*和若构建失败，则返回NULL。/LNode*p;p=(LNode*)malloc(sizeof(LNode);if(p=NULL)returnNULL;elsep-next=(LNode*)malloc(sizeof(LNode);if(p-next=NULL)returnNULL;p-data=x;p-next-data=y;p-next-next=NULL;returnp;/*【题目】

11、链表的结点和指针类型定义如下typedefstructLNodeElemTypedata;structLNode*next;LNode,*LinkList;试写一函数，构建长度为2的升序链表，两个结点的值分别为x和y，但应小的在前，大的在后。*/LinkListCreateOrdLList(ElemTypex,ElemTypey)/构建长度为2的升序链表。*/*若构建失败，则返回NULL。”/*LNode*p;p=(LNode*)malloc(sizeof(LNode);if(p=NULL)returnNULL;elsep-next=(LNode*)malloc(sizeof(LNode);i

12、f(p-next=NULL)returnNULL;p-data=(xnext-data=(xy)?x:y;p-next-next=NULL;returnp;/*【题目】试写一算法，实现顺序栈的判空操作StackEmpty_Sq(SqStackS)。顺序栈的类型定义为：typedefstructElemType*elem;/存储空间的基址inttop;/栈顶元素的下一个位置，简称栈顶位标intsize;/当前分配的存储容量intincrement;/扩容时，增加的存储容量SqStack;/顺序栈*/StatusStackEmpty_Sq(SqStackS)TRUE；否贝y返回*/FALSE*/对

13、顺序栈S判空。*若S是空栈，则返回/if(S.top=0)returnTRUE;returnFALSE;/*【题目】试写一算法，实现顺序栈的取栈顶元素操作GetTop_Sq(SqStackS,ElemType&e)。顺序栈的类型定义为：typedefstructElemType*elem;inttop;intsize;intincrement;SqStack;/存储空间的基址/栈顶元素的下一个位置，简称栈顶位标/当前分配的存储容量/扩容时，增加的存储容量/顺序栈*StatusGetTop_Sq(SqStackS,ElemType&e)OK;*/*/取顺序栈S的栈顶元素到e,并返*若失败，则返回

14、ERROR。回if(S.top=0)returnERROR;e=S.elemS.top-1;returnOK;/*【题目】试写一算法，实现顺序栈的出栈操作Pop_Sq(SqStack&S,ElemType&e)。顺序栈的类型定义为：typedefstructElemType*elem;/存储空间的基址/栈顶元素的下一个位置，简称栈顶位标inttop;/当前分配的存储容量/扩容时，增加的存储容量intsize;/顺序栈intincrement;SqStack;*OK;*/*/StatusPop_Sq(SqStack&S,ElemType&e)/顺序栈S的栈顶元素出栈e，并返*至U回若失败，则返回

15、ERROR。/*if(S.top=0)returnERROR;e=S.elem-S.top;returnOK;/*【题目】若顺序栈的类型重新定义如下。试编写算法，构建初始容量和扩容增量分别为size和inc的空顺序S栈typedefstructElemType*elem;/存储空间的基址ElemType*top;/栈顶元素的下一个位置intsize;/当前分配的存储容量intincrement;/扩容时，增加的存储容量SqStack2;*StatuslnitStack_Sq2(SqStack2&S,intsize,intinc)/*构建初始容量和扩容增量分别为size和inc的空顺序栈S。*/

16、*/若成功，则返0K;否则返ERROR。*回回S.elem=(ElemType*)malloc(sizeof(ElemType);if(S.elem=NULL|size=0|incS.size)p=(ElemType*)realloc(S.elem,(S.size+S.increment)*sizeof(ElemType);if(p=NULL)returnERROR;S.elem=p;S.size+=S.increment;*(S.top+)=e;returnOK;/*【题目】若顺序栈的类型重新定义如下。试编写算法，实现顺序栈的出栈操作typedefstructElemType*elem;/存

17、储空间的基址ElemType*top;/栈顶元素的下一个位置intsize;/当前分配的存储容量intincrement;/扩容时，增加的存储容量SqStack2;*StatusPop_Sq2(SqStack2&S,ElemType&e)ERROR;*/e，返回OK。*/若顺序栈S是空的，则返*回否则将S的栈顶元素出栈/至Uif(S.elem=S.top)returnERROR;e=*(-S.top);returnOK;S1得S2到/*【题目】试写一算法，借助辅助栈，复制顺序栈顺序栈的类型定义为：typedefstructElemType*elem;/存储空间的基址inttop;/栈顶元素的下

18、一个位置，简称栈顶位标intsize;/当前分配的存储容量intincrement;/扩容时，增加的存储容量SqStack;/顺序栈初始化销毁顺序StatusStackEmpty_Sq(SqStackS);StatusPush_Sq(SqStack&S,ElemTypee);/StatusPop_Sq(SqStack&S,ElemType&e);/*/StatusCopyStack_Sq(SqStackS1,SqStack&S2)/S判空，若空则返回TRUE，否栈贝y将元素e压入栈S栈S的栈顶元素出栈到eFALSE*/可调用顺序栈接口中下列函数:StatuslnitStack_Sq(SqSta

19、ck&S,intsize,intinc);/顺序栈SStatusDestroyStack_Sq(SqStack&S);/栈S/*借助辅助栈，复制顺序栈S1得到S2/*若复制成功，则返回TRUE;否则FALSE。if(StackEmpty_Sq(S1)S2.top=0;returnTRUE;S2.elem=S1.elem;S2.top=S1.top;returnTRUE;/*【题目】试写一算法，求循环队列的长度。循环队列的类型定义为：typedefstructElemType*base;/存储空间的基址intfront;/队头位标队尾位标，指示队尾兀素的下位intrear;/置intmaxSiz

20、e;/最大长度SqQueue;*/*/intQueueLength_Sq(SqQueueQ)/*返回队列Q中元素个数，即队列的长度。if(Q.rear-Q.frontvO)returnQ.maxSize-Q.front+Q.rear;returnQ.rear-Q.front;/*【题目】如果希望循环队列中的元素都能得到利用，则可设置一个标志域tag，并以tag值为0或1来区分尾指针和头指针值相同时的队列状态是空还是满。试编写与此结构相应的入队列和出队列的算法。本题的循环队列CTagQueue的类型定义如下:typedefstructElemTypeelemMAXQSIZE;inttag;int

21、front;intrear;CTagQueue;*/StatusEnCQueue(CTagQueue&Q,ElemTypex)/*将元素x加入队列Q,并返回OK;*/*若失败，则返回ERROR。*/if(Q.front=Q.rear&Q.tag=1)returnERROR;if(Q.rear=0)Q.elem0=x;Q.rear+=1;elseQ.elemQ.rear=x;Q.rear=(Q.rear+1)%MAXQSIZE;Q.tag=1;returnOK;OK;*/*/StatusDeCQueue(CTagQueue&Q,ElemType&x)/将队列Q的队头元素退队x，并返*至U回若失败

22、，则返回ERROR。/if(Q.front=Q.rear&Q.tag=0)returnERROR;x=Q.elemQ.front;Q.front=(Q.front+1)%MAXQSIZE;Q.tag=O;returnOK;/*【题目】假设将循环队列定义为：以域变量rear和length分别指示循环队列中队尾元素的位置和内含元素的个数。试给出此循环队列的队满条件，并写出相应的入队列和出队列的算法（在出队列的算法中要返回队头元素）。本题的循环队列CLenQueue的类型定义如下:typedefstructElemTypeelemMAXQSIZE;intlength;intrear;CLenQueu

23、e;*/StatusEnCQueue(CLenQueue&Q,ElemTypex)/将元素x加入队列Q，并返OK;*/回*/若失败，则返回ERROR。/*if(Q.length=MAXQSIZE)returnERROR;Q.rear=(Q.rear+1)%MAXQSIZE;Q.elemQ.rear=x;Q.length+;returnOK;StatusDeCQueue(CLenQueue&Q,ElemType&x)/将队列Q的队头兀素退队x，并返OK;*/*到回*/若失败，则返回ERROR。if(Q.length=0)returnERROR;x=Q.elem(Q.rear+MAXQSIZE-Q

24、.length+1)%MAXQSIZE;Q.length-;returnOK;/*【题目】已知k阶斐波那契序列的定义为f0=0,f1=0,?,fk-2=0,fk-1=1;fn=fn-1+fn-2+?+fn-k,n=k,k+1,试利用循环队列编写k阶斐波那契序列中第n+1项f的算法。n本题的循环队列的类型定义如下：typedefstructElemType*base;/存储空间的基址intfront;/队头位标intrear;intmaxSize;SqQueue;/队尾位标，指示队尾元素的下一位置/最大长度longFib(intk,intn)/求k阶斐波那契序列的n+1fn*/*第项if(k2|

25、n0)returnERROR;if(nk-1)return0;elseif(n=k-1)return1;elseSqQueueS;S.base=(ElemType*)malloc(n+1)*sizeof(ElemType);S.basek-1=1;inti,j,sum;for(i=0;ik-1;i+)S.basei=0;for(i=k;in+1;i+)sum=0;for(j=i-k;jv=i;j+)sum+=S.basej;S.basei=sum;returnS.basen;/*【题目】设A=(a1,?,am)和B=(b1,?,bn)均为有序顺序表，A和B分别为A和B中除去最大共同前缀后的子表

26、(例如，A=(x,y,y,z,x,z),B=(x,y,y,z,y,x,x,z)，贝U两者中最大的共同前缀为(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才进行比较)。顺序表类型定义如下:typedefstructElemType*elem;intlength;intsize;intincrement;SqList;*/charCompare(SqListA

27、,SqListB)/*比较顺序表A和B,*/*返回,若A,若AB*/inti=0;while(iv=A.length-1)&(iv=B.length-1)&(A.elemi=B.elemi)+i;if(i=A.length&i=B.length)return=;elseif(i=A.length&i!=B.length&A.elemivB.elemi)return;elseif(i!=A.length&i!=B.length&A.elemiB.elemi)returnB.elemi)return;elsereturn;/*【题目】试写一算法，实现顺序表的就地逆置，即利用原表的存储空间将线性表(

28、a1,a2,?,an)逆置为(an,an-1,?,a1)。顺序表类型定义如下：typedefstructElemType*elem;intlength;intsize;intincrement;SqList;*/voidlnverse(SqList&L)ElemTypetemp;if(L.elem!=NULL&L.length!=1)for(inti=0;iL.length/2;i+)temp=L.elemi;L.elemi=L.elemL.length-i-1;L.elemLength-i-1=temp;/*【题目】试对一元稀疏多项式Pn(x)采用存储量同多项式项数m成正比的顺序存储结构，编

29、写求Pn(xO)的算法(为给定值)。x0一元稀疏多项式的顺序存储结构typedefstructintcoef;/系数/指数intexp;Term;typedefstructTerm*elem;/存储空间基址intlength;/长度(项数)Poly;*/floatEvaluate(PolyP,floatx)/*P.elemi.coef存放ai，*/*P.elemi.exp存放ei(i=1,2,.,m)*/*本算法计算并返回多项式的值。不判别溢出。/*入口时要求0e1e2v.vem，算法内不对此再作验证floatresult=0;floatx_sum=1;inti,j;*/*/for(i=0;i

30、P.length;i+)for(j=0;jP.elemi.exp;j+)x_sum*=x;result+=(P.elemi.coef*x_sum);x_sum=1;returnresult;/*【题目】假设有两个集合A和B分别用两个线性表LA和LB表示(即：线性表中的数据元素即为集合中的成员),试写一算法，求并集A=AUB。顺序表类型定义如下typedefstructElemType*elem;/存储空间的基址intlength;/当前长度intsize;/存储容量intincrement;/空间不够增加空间大小SqList;/顺序表可调用顺序表的以下接口函数：StatusInitList_S

31、q(SqList&L,intsize,intinc);/初始化顺序表LintListLength_Sq(SqListL);/返回顺序表L中元素个数StatusGetElem_Sq(SqListL,inti,ElemType&e);/用e返回顺序表L中第i个元素的值intSearch_Sq(SqListL,ElemTypee);-1L表尾添加元素/在顺序表L顺序查找元素e,成功时返回该元素在表中第一次出现的位置，否则返/回StatusAppend_Sq(SqList&L,ElemTypee);/在顺序表evoidUnion(SqList&La,SqListLb)intcount=0;for(in

32、ti=O;iListLength_Sq(Lb);i+)if(Search_Sq(La,Lb.elemi)=-1)count+;ElemType*p;p=(ElemType*)realloc(La.elem,La.size+count*sizeof(ElemType);if(p=NULL)return;La.elem=p;for(i=0;inext=S)returnTRUE;returnFALSE;/*【题目】试写一算法，实现链栈的取栈顶元素操作链栈的类型定义为：typedefstructLSNodeElemTypedata;数据域structLSNode*next;/指针域LSNode,*LS

33、tack;/结点和链栈类型*StatusGetTop_L(LStackS,ElemType&e)/取链栈S的栈顶元素到e，并返回OK;*/*若S是空栈，则失败，返回ERROR。*/if(S=NULL|S-next=S)returnERROR;e=S-data;returnOK;/*【题目】试写一算法，实现链队列的判空操作链队列的类型定义为：typedefstructLQNodeElemTypedata;structLQNode*next;LQNode,*QueuePtr;/typedefstructQueuePtrfront;/QueuePtrrear;/结点和结点指针类型队头指针队尾指针LQ

34、ueue;/链队列类型*/StatusQueueEmpty_LQ(LQueueQ)/判定链队列Q是否为空队列。*/*若Q是空队列，则返回TRUE，否FALSE*/则/*if(Q.front!=NULL|Q.front-next!=NULL)returnFALSE;returnTRUE;/*【题目】试写一算法，实现链队列的求队列长度操作。链队列的类型定义为：typedefstructLQNodeElemTypedata;structLQNode*next;LQNode,*QueuePtr;/结点和结点指针类型typedefstructQueuePtrfront;/队头指针QueuePtrrear

35、;/队尾指针LQueue;/链队列类型*/intQueueLength_LQ(LQueueQ)/*求链队列Q的长度并返回其值*/if(Q.front=NULL&Q.front-next=NULL)return0;intlen=0;LQNode*p=Q.front;while(p!=NULL)p=p-next;len+;returnlen;/*【题目】假设以带头结点的循环链表表示队列，并且只设一个指针指向队尾元素结点（注意不设头指针）,试编写相应的队列初始化、入队列和出队列的算法。带头结点循环链队列CLQueue的类型定义为：typedefstructLQNodeElemTypedata;str

36、uctLQNode*next;LQNode,*CLQueue;*/初始化空队列StatuslnitCLQueue(CLQueue&rear)/rear=(CLQueue)malloc(sizeof(LQNode);if(!rear)returnFALSE;rear-next=rear;returnTRUE;入队StatusEnCLQueue(CLQueue&rear,ElemTypex)/CLQueuehead,p;head=rear-next;p=(CLQueue)malloc(sizeof(LQNode);if(!p)returnFALSE;p-data=x;p-next=head;rea

37、r-next=p;rear=p;returnTRUE;出队StatusDeCLQueue(CLQueue&rear,ElemType&x)/CLQueuehead,p;head=rear-next;/头结点if(head=rear)returnFALSE;x赋值给头结点后继p=head-next;/将欲删除的队头结点暂存给px=p-data;/将欲删除的队头结点的值赋给head-next=p-next;/将原队头结点的后继p-nextfree(p);returnTRUE;/*【题目】试写一算法，实现带头结点单链表的判空操作单链表的类型定义为：typedefstructLNodeElemType

38、data;structLNode*next;LNode,*LinkList;II结点和结点指针类型*/StatusListEmpty_L(LinkListL)/*/*判定带头结点单链表L是否为空链表。*/若L是空链表，则返TRUE,否则FALSE。*/回if(L=L-next|!L-next)returnTRUE;returnFALSE;/*【题目】试写一算法，实现带头结点单链表的销毁操作单链表的类型定义为：typedefstructLNodeElemTypedata;structLNode*next;LNode,*LinkList;/结点和结点指针类型*/StatusDestroyList_

39、L(LinkList&L)/*销毁带头结点单链表L，并返回OK。*/if(L=L-next|!L-next)free(L);returnOK;LNode*p=L-next,*pt;while(p!=NULL)pt=p-next;free(p);p=pt;free(L);returnOK;/*【题目】试写一算法，实现带头结点单链表的清空操作单链表的类型定义为：typedefstructLNodeElemTypedata;structLNode*next;LNode,*LinkList;/结点和结点指针类型*/StatusClearList_L(LinkList&L)/将带头结点单链表L置为空表，

40、并返回OK。*/*若L不是带头结点单链表，则返回ERROR。*/*if(L=NULL)returnERROR;LNode*p=L-next,*pt;while(p!=NULL)pt=p-next;free(p);p=pt;L-next=NULL;returnOK;/*【题目】试写一算法，实现带头结点单链表的求表长度操作。单链表的类型定义为：typedefstructLNodeElemTypedata;structLNode*next;LNode,*LinkList;/结点和结点指针类型*/intListLength_L(LinkListL)*/*求带头结点单链表L的长度，并返回长度值。*/*若

41、L不是带头结点单链表，则返回-1。if(L=NULL)return-1;LinkListp=L-next;intcount=0;while(p!=NULL)count+;p=p-next;returncount;L插入i元e。/*【题目】试写一算法，在带头结点单链表带头结点单链表的类型定义为：typedefstructLNodeElemTypedata;structLNode*next;LNode,*LinkList;*/StatusInsert_L(LinkListL,inti,ElemTypee)OK。*/*/在带头结点单链表L插入第i元e，并返*素回若参数不合理，则返回ERROR。/if(i0)returnERROR;intcount=0;LinkListp=L;while(p!=NULL&countnext;count+;if(!p|counti-1)retur