嚴蔚敏《數據結構(c語言版)習題集》算法設計題第一章答案

　　說明:

　　 本文是對嚴蔚敏《數據結構(c語言版)習題集》一書中所有算法設計題目的解決方案主要作者為kaoyancom計算機版版主一具以下網友:siice龍抬頭iamkentzamesbirdthinking等為答案的修訂和完善工作提出了寶貴意見在此表示感謝;

　　 本解答中的所有算法均采用類c語言描述設計原則為面向交流面向閱讀作者不保證程序能夠上機正常運行(這種保證實際上也沒有任何意義);

　　 本解答原則上只給出源代碼以及必要的注釋對於一些難度較高或思路特殊的題目將給出簡要的分析說明對於作者無法解決的題目將給出必要的討論目前尚未解決的題目有: ;

　　 請讀者在自己已經解決了某個題目或進行了充分的思考之後再參考本解答以保證復習效果;

　　 由於作者水平所限本解答中一定存在不少這樣或者那樣的錯誤和不足希望讀者們在閱讀中多動腦勤思考爭取發現和糾正這些錯誤寫出更好的算法來請將你發現的錯誤或其它值得改進之處向作者報告: yiju@net

　　第一章 緒論

　　

　　void print_descending(int xint yint 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

　　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

　　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[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);

　　}//polyvalue

From:http://tw.wingwit.com/Article/program/sjjg/201311/23575.html