说明 1.本文是对严蔚敏《数据结构(c语言版)习题集》一书中所有算法设计题目的解 决方案,主要作者为一具以下网友 biwier,szm9g,sice,龙抬 头, lament, zames. birdthinking lovebuaa等为答案的修订和完善工作提出了宝贵意 见,在此表示感谢 2.本解答中的所有算法均采用类c语言描述,设计原则为面向交流、面向阅读,作 者不保证程序能够上机正常运行(这种保证实际上也没有任何意义) 3.本解答原则上只给出源代码以及必要的注释对于一些难度较高或思路特殊的 题目将给出简要的分析说明,对于作者无法解决的题目将给出必要的讨论目前尚 未解决的题目有:5.20,10.40 4.请读者在自己已经解决了某个题目或进行了充分的思考之后,再参考本解答, 以保证复习效果; 5.由于作者水平所限本解答中一定存在不少这样或者那样的错误和不足,希望 读者们在阅读中多动脑、勤思考,争取发现和纠正这些错误,写出更好的算法来 请将你发现的错误或其它值得改进之处向作者报告:yiju@263net 第一章绪论 void print descend ing(ntx,inty,ntz)/按从大到小顺序输出三个数 scanf("%d, %d, %d", &x, &y, &z) ixy)x<>y,/>为表示交换的双目运算符,以下同 if(ysz)yZ ifxy)x<>y,/冒泡排序 printf("%d %d%d"x,y, z) i//print descending 1.17 Status fib(int k, int m,int&fy求k阶斐波那契序列的第m项的值f int tempd if(k<2 m<0)return ERROR if(m<k-1)f=0 else if(m==k-1 m=k)f=1 for(i=0; <=k-2; i++)tempi]=C temp[k-1 1; templ}=1;∥初始化
说明: 1. 本文是对严蔚敏《数据结构(c 语言版)习题集》一书中所有算法设计题目的解 决方案,主要作者为一具.以下网友:biwier,szm99,siice,龙抬 头,iamkent,zames,birdthinking,lovebuaa 等为答案的修订和完善工作提出了宝贵意 见,在此表示感谢; 2. 本解答中的所有算法均采用类 c 语言描述,设计原则为面向交流、面向阅读,作 者不保证程序能够上机正常运行(这种保证实际上也没有任何意义); 3. 本解答原则上只给出源代码以及必要的注释,对于一些难度较高或思路特殊的 题目将给出简要的分析说明,对于作者无法解决的题目将给出必要的讨论.目前尚 未解决的题目有: 5.20, 10.40; 4. 请读者在自己已经解决了某个题目或进行了充分的思考之后,再参考本解答, 以保证复习效果; 5. 由于作者水平所限,本解答中一定存在不少这样或者那样的错误和不足,希望 读者们在阅读中多动脑、勤思考,争取发现和纠正这些错误,写出更好的算法来. 请将你发现的错误或其它值得改进之处向作者报告: yi-ju@263.net 第一章 绪论 1.16 void print_descending(int x,int y,int z)//按从大到小顺序输出三个数 { scanf("%d,%d,%d",&x,&y,&z); if(xy; //为表示交换的双目运算符,以下同 if(yz; if(xy; //冒泡排序 printf("%d %d %d",x,y,z); }//print_descending 1.17 Status fib(int k,int m,int &f)//求 k 阶斐波那契序列的第 m 项的值 f { int tempd; if(k<2||m<0) return ERROR; if(m<k-1) f=0; else if (m==k-1 || m==k) f=1; else { for(i=0;i<=k-2;i++) temp[i]=0; temp[k-1]=1;temp[k]=1; //初始化
for(i=k+1<=m计++j+)∥求出序列第k至第m个元素的值 temp[=2*sum-templI f-temp[m return OK i//fib 分析:k阶斐波那契序列的第m项的值fm}m-1}+im2J+.+m-k] m-1+fm-2+……+m-k]+fm-k-1]-m-k-4] =2* fm-1]-fm-k- 所以上述算法的时间复杂度仅为O(m)如果采用递归设计将达到O(k^m)即使 采用暂存中间结果的方法,也将达到O(m^2) 1.18 typedef struct( num male, female) gender; char schoolname;∥校名为'A"B',C"D或E typedef structi int malesco int femalescore int totalscore scoretype, void summary( resulttype result求各校的男女总分和团体总分,假设结果已经储 存在 result[]数组中 scoretype score[MAXSIZE] while(result[]. sport!=NULL) switch(result[]. schoolname) score[ 0].totalscore+=resultiscore if(result[]- gender==0)score[ 0]. malescore+=result iscore else score[ 0 ]. femalescore-+=result[].score B
sum=1; j=0; for(i=k+1;i<=m;i++,j++) //求出序列第 k 至第 m 个元素的值 temp[i]=2*sum-temp[j]; f=temp[m]; } return OK; }//fib 分析: k 阶斐波那契序列的第 m 项的值 f[m]=f[m-1]+f[m-2]+......+f[m-k] =f[m-1]+f[m-2]+......+f[m-k]+f[m-k-1]-f[m-k-1] =2*f[m-1]-f[m-k-1] 所以上述算法的时间复杂度仅为 O(m). 如果采用递归设计,将达到 O(k^m). 即使 采用暂存中间结果的方法,也将达到 O(m^2). 1.18 typedef struct{ char *sport; enum{male,female} gender; char schoolname; //校名为'A','B','C','D'或'E' char *result; int score; } resulttype; typedef struct{ int malescore; int femalescore; int totalscore; } scoretype; void summary(resulttype result[ ])//求各校的男女总分和团体总分,假设结果已经储 存在 result[ ]数组中 { scoretype score[MAXSIZE]; i=0; while(result[i].sport!=NULL) { switch(result[i].schoolname) { case 'A': score[ 0 ].totalscore+=result[i].score; if(result[i].gender==0) score[ 0 ].malescore+=result[i].score; else score[ 0 ].femalescore+=result[i].score; break; case 'B':
score[ 0]. totalscore+=result[j]. score; f(result [. gender=0)score[ 0]. malescore+=result[].score Ise score[ 0 ].femalescore-+=result [].score for(=0;<5;H printf("School %d: n",i); printf("Total score of male: %d\n" score[i]. malescore) printf("Total score of female: %d\ n", score[]. femalescore) printf("Total score of all: %d\nIn" score[i]. totalscore) 1.19 Status algo1 19(inta[ ARRSIZE)求*2个序列的值且不超过 maxint last=1 for(Fl; K<=ARRSIZE; 1++) a**1 if(a[i-1 ]last)!=(2*i)) reurn OVERFLOW last=a[]; return OK. i//algo1 19 分析:当某一项的结果超过了 maxint时,它除以前面一项的商会发生异常 120 void polyvalueo float temp float"p=a printf("Input number of terms: " printf("Input value of x: )3 scanf(%f", &x); printf("Input the %d coefficients from a0 to a%d: \n",n+l, n); p=axp=l,sum=0;/xp用于存放x的i次方 for(=0i<=n;i++)
score[ 0 ].totalscore+=result[i].score; if(result[i].gender==0) score[ 0 ].malescore+=result[i].score; else score[ 0 ].femalescore+=result[i].score; break; …… …… …… } i++； } for(i=0;i<5;i++) { printf("School %d:\n",i); printf("Total score of male:%d\n",score[i].malescore); printf("Total score of female:%d\n",score[i].femalescore); printf("Total score of all:%d\n\n",score[i].totalscore); } }//summary 1.19 Status algo119(int a[ARRSIZE])//求 i!*2^i 序列的值且不超过 maxint { last=1; for(i=1;i<=ARRSIZE;i++) { a[i-1]=last*2*i; if((a[i-1]/last)!=(2*i)) reurn OVERFLOW; last=a[i-1]; return OK; } }//algo119 分析:当某一项的结果超过了 maxint 时,它除以前面一项的商会发生异常. 1.20 void polyvalue() { float temp; float *p=a; printf("Input number of terms:"); scanf("%d",&n); printf("Input value of x:"); scanf("%f",&x); printf("Input the %d coefficients from a0 to a%d:\n",n+1,n); p=a;xp=1;sum=0; //xp 用于存放 x 的 i 次方 for(i=0;i<=n;i++)
canf(%f", &temp) sum+=xp(temp) printf("Value is: %f, sum);
{ scanf("%f",&temp); sum+=xp*(temp); xp*=x; } printf("Value is:%f",sum); }//polyvalue