说明:
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(x<y) x<->y; //<->为表示交换的双
目运算符,以下同
if(y<z) y<->z;
if(x<y) x<->y; //冒泡排序
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=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;
评论0