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