2016广工AnyView数据结构 第1-5章答案

/**********【题目】试写一算法，如果三个整数a，b和c的值不是依次非递增的，则通过交换，令其为非递增。***********/voidDescend(int&a,int&b,int&c)/*通过交换，令a=b=c*/{if(c=b&&b=a)return;else{if(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+a2x^2+...+anx^n的值P(x0)，并确定算法中每一语句的执行次数和整个算法的时间复杂度。**********/floatPolynomial(intn,inta[],floatx)/*求一元多项式的值P(x)。*//*数组a的元素a[i]为i次项的系数，i=0,...,n*/{floatanswer=a[0];floattemp=1.0;for(inti=1;i=n;i++){temp*=x;answer+=a[i]*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,int&f)/*求k阶斐波那契序列的第m项的值f*/{if(k=1||m0)returnERROR;elseif(m==k-1)f=1;elseif(m==0)f=0;else{inti,j,sum;int*t;t=(int*)malloc(m*sizeof(int));for(i=0;i=k-2;i++)t[i]=0;t[k-1]=1;for(i=k;i=m;i++){sum=0;for(j=i-k;j=i;j++)sum+=t[j];t[i]=sum;}f=t[m];}returnOK;}/**********【题目】试编写算法，计算i!×2^i的值并存入数组a[0..n-1]的第i-1个分量中(i=1,2,…,n)。假设计算机中允许的整数最大值为MAXINT，则当对某个k(1≤k≤n)使k!×2^kMAXINT时，应按出错处理。注意选择你认为较好的出错处理方法。**********/StatusSeries(inta[],intn)/*求i!*2^i序列的值并依次存入长度为n的数组a；*//*若所有值均不超过MAXINT，则返回OK，否则OVERFLOW*/{intt=1,p=1;for(inti=1;i=n;i++){t*=i;p*=2;a[i-1]=t*p;if(a[i-1]MAXINT)returnERROR;}returnOK;}/**********【题目】假设有A、B、C、D、E五个高等院校进行田径对抗赛，各院校的单项成绩均以存入计算机并构成一张表，表中每一行的形式为：项目名称性别校名成绩得分编写算法，处理上述表格，以统计各院校的男、女总分和团体总分，并输出。**********/voidScores(ResultType*result,ScoreType*score)/*求各校的男、女总分和团体总分,并依次存入数组score*//*假设比赛结果已经储存在result[]数组中,*//*并以特殊记录{,male,'',,0}（域scorce=0）*//*表示结束*/{inti=0;while(result[i].sport!=NULL){switch(result[i].schoolname){case'A':score[0].totalscore+=result[i].score;if(result[i].gender==male)score[0].malescore+=result[i].score;elsescore[0].femalescore+=result[i].score;break;case'B':score[1].totalscore+=result[i].score;if(result[i].gender==male)score[1].malescore+=result[i].score;elsescore[1].femalescore+=result[i].score;break;case'C':score[2].totalscore+=result[i].score;if(result[i].gender==male)score[2].malescore+=result[i].score;elsescore[2].femalescore+=result[i].score;break;case'D':score[3].totalscore+=result[i].score;if(result[i].gender==male)score[3].malescore+=result[i].score;elsescore[3].femalescore+=result[i].score;break;case'E':score[4].totalscore+=result[i].score;if(result[i].gender==male)score[4].malescore+=result[i].score;elsescore[4].femalescore+=result[i].score;break;}i++;}}/**********【题目】试写一算法，对序列S的第i个元素赋以值e。序列的类型定义为：typedefstruct{ElemType*elem;intlength;}Sequence;***********/StatusAssign(Sequence&S,inti,ElemTypee)/*对序列S的第i个元素赋以值e，并返回OK。*//*若S或i不合法，则赋值失败，返回ERROR*/{if(S.length1||iS.length)returnERROR;elseS.elem[i]=e;returnOK;}/**********【题目】试写一算法，由长度为n的一维数组a构建一个序列S。序列的类型定义为：typedefstruct{ElemType*elem;intlength;}Sequence;***********/StatusCreateSequence(Sequence&S,intn,ElemType*a)/*由长度为n的一维数组a构建一个序列S，并返回OK。*//*若构建失败，则返回ERROR*/{if(n1)returnERROR;else{S.elem=(ElemType*)malloc(n*sizeof(ElemType));S.elem[0]=a[0];for(inti=1;in;i++)S.elem[i]=a[i];S.length=n;}returnOK;}/**********【题目】链表的结点和指针类型定义如下typedefstructLNode{ElemTypedata;structLNode*next;}LNode,*LinkList;试写一函数，构建一个值为x的结点。***********/LinkListMakeNode(ElemTypex)/*构建一个值为x的结点，并返回其指针。*//*若构建失败，则返回NULL。*/{LNode*p;p=(LNode*)malloc(sizeof(LNode));if(p==NULL)returnNULL;elsep-data=x;returnp;}/**********【题目】链表的结点和指针类型定义如下typedefstructLNode{ElemTypedata;structLNode*next;}LNode,*LinkList;试写一函数，构建长度为2且两个结点的值依次为x和y的链表。**********/LinkListCreateLinkList(ElemTypex,ElemTypey)/*构建其两个结点的值依次为x和y的链表。*//*若构建失败，则返回NULL。*/{LNode*p;p=(LNode*)malloc(sizeof(LNode));if(p==NULL)returnNULL;else{p-next=(LNode*)malloc(sizeof(LNode));if(p-next==NULL)returnNULL;p-data=x;p-next-data=y;p-next-next=NULL;}returnp;}/**********【题目】链表的结点和指针类型定义如下typedefstructLNode{ElemTypedata;structLNode*next;}LNode,*LinkList;试写一函数，构建长度为2的升序链表，两个结点的值分别为x和y，但应小的在前，大的在后。**********/LinkListCreateOrdLList(ElemTypex,ElemTypey)/*构建长度为2的升序链表。*//*若构建失败，则返回NULL。*/{LNode*p;p=(LNode*)malloc(sizeof(LNode));if(p==NULL)returnNULL;else{p-next=(LNode*)malloc(sizeof(LNode));if(p-next==NULL)returnNULL;p-data=(xy)?x:y;p-next-data=(xy)?x:y;p-next-next=NULL;}returnp;}/**********【题目】试写一算法，实现顺序栈的判空操作StackEmpty_Sq(SqStackS)。顺序栈的类型定义为：typedefstruct{ElemType*elem;//存储空间的基址inttop;//栈顶元素的下一个位置，简称栈顶位标intsize;//当前分配的存储容量intincrement;//扩容时，增加的存储容量}SqStack;//顺序栈***********/StatusStackEmpty_Sq(SqStackS)/*对顺序栈S判空。*//*若S是空栈，则返回TRUE；否则返回FALSE*/{if(S.top==0)returnTRUE;returnFALSE;}/**********【题目】试写一算法，实现顺序栈的取栈顶元素操作GetTop_Sq(SqStackS,ElemType&e)。顺序栈的类型定义为：typedefstruct{ElemType*elem;//存储空间的基址inttop;//栈顶元素的下一个位置，简称栈顶位标intsize;//当前分配的存储容量intincrement;//扩容时，增加的存储容量}SqStack;//顺序栈***********/StatusGetTop_Sq(SqStackS,ElemType&e)/*取顺序栈S的栈顶元素到e，并返回OK；*//*若失败，则返回ERROR。*/{if(S.top==0)returnERROR;e=S.elem[S.top-1];returnOK;}/**********【题目】试写一算法，实现顺序栈的出栈操作Pop_Sq(SqStack&S,ElemType&e)。顺序栈的类型定义为：typedefstruct{ElemType*elem;//存储空间的基址inttop;//栈顶元素的下一个位置，简称栈顶位标intsize;//当前分配的存储容量intincrement;//扩容时，增加的存储容量}SqStack;//顺序栈***********/StatusPop_Sq(SqSta