第一篇：數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)
河海大學(xué)計(jì)算機(jī)與信息學(xué)院（常州）
數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)
課程設(shè)計(jì)題目：
多 項(xiàng) 式 問(wèn) 題
專業(yè)、年級(jí)：計(jì)算機(jī)科學(xué)與技術(shù)09級(jí) 學(xué)
號(hào)：
0962810226
姓
名：
王
超
目 錄
一、問(wèn)題描述-------------3
二、需求分析-------------4
三、概要設(shè)計(jì)-------------4 1.概要設(shè)計(jì)目的與要求--4 2.概要設(shè)計(jì)內(nèi)容--------4 3.功能算法描述與數(shù)據(jù)結(jié)構(gòu)說(shuō)明-------------------------5
四、詳細(xì)設(shè)計(jì)-------------5
五、系統(tǒng)測(cè)試-------------8
六、使用說(shuō)明-------------9
七、總結(jié)及心得體會(huì)-----10
多項(xiàng)式問(wèn)題
一．問(wèn)題描述
給你九個(gè)整數(shù)，這九個(gè)整數(shù)分別是x的8次方至0次方的系數(shù)，請(qǐng)你按照多項(xiàng)式的一半形式合理地構(gòu)造（去除不必要的）。例如九個(gè)系數(shù)分別是為0,0，0,1,22，-333,0,1，-1，你要構(gòu)造并輸出一行多項(xiàng)式：x^5 + 22x^4 – 333x^3 + x – 1。
它的格式規(guī)則如下：
1.多項(xiàng)式的項(xiàng)必須按其指數(shù)從高到低排列。2.指數(shù)必須跟在符號(hào)“^”后顯示。3.有常數(shù)的只顯示常數(shù)項(xiàng)（無(wú)需跟x^0）。
4.只顯示系數(shù)不為0的項(xiàng)；若系數(shù)全為0，需顯示常數(shù)項(xiàng)。
5.在多項(xiàng)式中唯一需要空格的地方是項(xiàng)與項(xiàng)之間的加號(hào)或減號(hào)的兩邊需加上空格。
6.如果首項(xiàng)的系數(shù)是正數(shù)，則系數(shù)前不加符號(hào)；如果首項(xiàng)的系數(shù)是負(fù)數(shù)，則符號(hào)與數(shù)字之間不加空格，就如：-3x^2 +-2x。
7.系數(shù)為1，指數(shù)為0時(shí)，系數(shù)的1才顯示（推廣到系數(shù)為-1）。
輸入/輸出說(shuō)明
1.輸入/輸出方式為文件方式，輸入文件有一行或多行的系數(shù)，系數(shù)之間有空格分隔。
2.每行共有九個(gè)系數(shù)，每個(gè)系數(shù)的絕對(duì)值為小于1000的整數(shù)。輸出文件包含構(gòu)造完地多項(xiàng)式，每行一個(gè)多項(xiàng)式。
輸入范例
0 0 0 1 22-333 0 1-1 0 0 0 0 0 0-55 5 0
輸出范例
x^5 + 22x^4 – 333x^3 + x – 1-55x^2 + 5x
二．需求分析
2.1可行性研究
該程序主要從技術(shù)的角度來(lái)分析可行性。技術(shù)上的可行性研究主要分析技術(shù)條件能否順利完成開發(fā)工作，硬、軟件能否滿足開發(fā)者的需要等。該系統(tǒng)采用了Windows 7操作系統(tǒng)結(jié)合Visual C++ 6.0等軟件開發(fā)平臺(tái)已成熟可行。硬件方面，科技飛速發(fā)展的今天，硬件更新的速度越來(lái)越快，容量越來(lái)越大，可靠性越來(lái)越高，其硬件平臺(tái)也比較能滿足此系統(tǒng)的需要。
2.2結(jié)構(gòu)與主要功能模塊
從實(shí)現(xiàn)多項(xiàng)式輸出過(guò)程的角度來(lái)分析，至少需要這樣一些子功能模塊。如： 1.多項(xiàng)式創(chuàng)建功能；
2.多項(xiàng)式輸出功能；
3.釋放多項(xiàng)式功能；
4.操作界面顯示功能；
三．概要設(shè)計(jì)
1.概要設(shè)計(jì)目的與要求
通過(guò)多項(xiàng)式程序設(shè)計(jì)，使我們進(jìn)一步掌握和利用C++語(yǔ)言進(jìn)行結(jié)構(gòu)化程序設(shè)計(jì)的能力；進(jìn)一步理解和運(yùn)用結(jié)構(gòu)化程設(shè)計(jì)的思想和方法；初步掌握開發(fā)一個(gè)小型系統(tǒng)程序設(shè)計(jì)的基本方法；學(xué)會(huì)調(diào)試一個(gè)較長(zhǎng)程序的基本方法；以及掌握書寫課程設(shè)計(jì)開發(fā)文檔的能力（書寫課程設(shè)計(jì)報(bào)告）?？傊ㄟ^(guò)本課程設(shè)計(jì)加深對(duì)《C++語(yǔ)言》及《數(shù)據(jù)結(jié)構(gòu)》課程所學(xué)知識(shí)的理解，進(jìn)一步鞏固C++語(yǔ)言語(yǔ)法規(guī)則，在程序中體現(xiàn)出算法的思想，提高程序的運(yùn)行效率。學(xué)會(huì)編制結(jié)構(gòu)清晰、風(fēng)格良好、數(shù)據(jù)結(jié)構(gòu)適當(dāng)?shù)腃++語(yǔ)言程序，從而具備解決綜合性實(shí)際問(wèn)題的能力。
2.概要設(shè)計(jì)內(nèi)容
多項(xiàng)式輸出程序具有以下基本功能：
1．創(chuàng)建多項(xiàng)式。接收輸入的數(shù)據(jù)，并保存到鏈表中。
2．Txt文檔輸入輸出功能。
3． 清除內(nèi)存內(nèi)容，釋放創(chuàng)建的鏈表，退出程序。
3.功能算法描述與數(shù)據(jù)結(jié)構(gòu)說(shuō)明
該多項(xiàng)式程序除了main()函數(shù)外，主要有以下函數(shù)：
node *CreatePolyn()
void firstnode(node *p)
void othernode(node *p)
void PrintPolyn(node *Pa)
void deletechain(node *h)
下面對(duì)這些函數(shù)逐一介紹。①.main（）函數(shù)
main函數(shù)主要調(diào)用其他函數(shù)，用來(lái)實(shí)現(xiàn)輸入、顯示功能。
在main（）函數(shù)中，定義一維數(shù)組p[]用來(lái)保存多項(xiàng)式的系數(shù)，Pa定義程序所需鏈表的頭指針。在程序開始要求輸入多項(xiàng)式的系數(shù)，隨后創(chuàng)建鏈表以保存多項(xiàng)式，再顯示出構(gòu)建的符合要求的多項(xiàng)式。②.node *CreatePolyn()該函數(shù)功能是創(chuàng)建新的多項(xiàng)式鏈表。使用for語(yǔ)句，控制輸入多項(xiàng)式的每一項(xiàng)。
③.void firstnode(node *p)該函數(shù)功能是判斷輸出多項(xiàng)式第一項(xiàng)。對(duì)于第一項(xiàng)的系數(shù)為1或-1，指數(shù)為0或-1等五種情況進(jìn)行討論。④.void othernode(node *p)該函數(shù)功能是判斷輸出多項(xiàng)式除第一項(xiàng)外的其它項(xiàng)。對(duì)于第一項(xiàng)的系數(shù)為1或-1，指數(shù)為0或-1等五種情況進(jìn)行討論。⑤.void PrintPolyn(node *Pa)該函數(shù)功能：顯示構(gòu)造的符合要求的多項(xiàng)式鏈表。在該函數(shù)中調(diào)用③、④函數(shù)，進(jìn)行多項(xiàng)式的輸出。⑥.void deletechain(node *h)該函數(shù)的功能是釋放掉創(chuàng)建的鏈表，釋放內(nèi)存。
四．詳細(xì)設(shè)計(jì)
下面討論重要函數(shù)具體實(shí)現(xiàn)過(guò)程：
1.node *CreatePolyn()定義int i=9計(jì)數(shù)，當(dāng)i>0時(shí)，for語(yǔ)句反復(fù)提示用戶輸入該多項(xiàng)式的每一項(xiàng)的指數(shù)。當(dāng)i=1時(shí)，輸入完畢，該鏈表也創(chuàng)建完畢。詳細(xì)的實(shí)現(xiàn)過(guò)程如下：
node *CreatePolyn(){ node *head,*pa,*s;int i;
pa=head=new node;//創(chuàng)建一個(gè)新的結(jié)點(diǎn)
head->next=NULL;
for(i = 9;i >0;i--)// 依次輸入9項(xiàng)
{
s=new node;
s->next=NULL;
s->coef = p[9-i];
s->exp=i-1;//x指數(shù)從8遞減到0
if(s->coef!=0)//系數(shù)不為零時(shí)，結(jié)點(diǎn)p鏈接s
{
pa->next=s;
pa=s;
} } return head;} 2.void firstnode(node *p)對(duì)多項(xiàng)式第一項(xiàng)輸出可能性進(jìn)行多種分類討論。
void firstnode(node *p)//輸出多項(xiàng)式第一個(gè)結(jié)點(diǎn) { //指數(shù)不為1且不為0,系數(shù)絕對(duì)值不為1（正常的輸出）if(p->exp!=1&&p->exp&&fabs(p->coef)!=1)
{
if(p->coef>0)
{
outfile<
coef<<“X^”<
exp;
}
else
{
outfile<
coef<<“X^”<
exp;
} } if(p->exp==0)//指數(shù)為0，即常數(shù)項(xiàng)
{
if(p->coef>0)
{
outfile<
coef;
}
else
{
outfile<
coef;
} }
//指數(shù)大于0且不為1，系數(shù)絕對(duì)值為1 if(p->exp>0&&fabs(p->coef)==1&&p->exp!=1){
if(p->coef>0)
{
outfile<<“X^”<
exp;
}
else
{
outfile<<“-X^”<
exp;
} } if(p->exp==1&&fabs(p->coef)!=1)//指數(shù)為1且系數(shù)絕對(duì)值不為1 {
if(p->coef>0&&p->coef!=1)
{
outfile<
coef<<“X”;
}
if(p->coef<0&&p->coef!=-1)
{
outfile<
coef<<“X”;
} } if(p->exp==1&&fabs(p->coef)==1)//指數(shù)為1且系數(shù)絕對(duì)值為1 {
if(p->coef==1)
outfile<<“X”;
else
outfile<<“-X”;} }
3.void PrintPolyn(node *Pa)該函數(shù)有一個(gè)參數(shù)，該指針指向多項(xiàng)式鏈表的頭指針，以下是實(shí)現(xiàn)插入的關(guān)鍵代碼： void PrintPolyn(node *Pa){ node *p;if(Pa->next==NULL)//首項(xiàng)判斷，如果首項(xiàng)無(wú)，則顯示“0”
outfile<<“0”;
return;else {
firstnode(Pa->next);} p=Pa->next->next;//定義指針p指向Pa的下下個(gè)指針
while(p!=NULL){
othernode(p);
p=p->next;
//將p指向下個(gè)一個(gè)結(jié)點(diǎn)
}
outfile< 五．系統(tǒng)測(cè)試 該程序在VC6.0中調(diào)試通過(guò)，沒(méi)有錯(cuò)誤和警告，運(yùn)行結(jié)果經(jīng)過(guò)檢驗(yàn)為正確。以下圖為該程序運(yùn)行結(jié)果效果圖： 圖5-1 范例 圖5-2 一行輸出 圖5-3 多行輸出 六．使用說(shuō)明 1．打開1.txt文件，在里面任意輸入9個(gè)整數(shù)，每個(gè)數(shù)字間要有空格，可以輸入一行或者多行，輸入多行的時(shí)候需要換行。 2.編譯運(yùn)行后，打開2.txt文件，即可看到輸出的符合要求的多項(xiàng)式。 七．總結(jié)及心得體會(huì) 通過(guò)這次課程設(shè)計(jì)練習(xí)，使我更深刻地理解了C++語(yǔ)言的精髓-----指針的使用。完成整個(gè)程序設(shè)計(jì)有很大的收獲，對(duì)指針掌握的更加熟練。 同時(shí)通過(guò)直接對(duì)單鏈表的操作，加深了對(duì)數(shù)據(jù)結(jié)構(gòu)的理解和認(rèn)識(shí)。并在完成課程設(shè)計(jì)的過(guò)程作主動(dòng)查閱了相關(guān)資料，學(xué)到了不少課本上沒(méi)有的技術(shù)知識(shí)。 經(jīng)過(guò)這次課程設(shè)計(jì)，我深刻認(rèn)識(shí)到算法在程序設(shè)計(jì)中的重要性，如何讓程序簡(jiǎn)單、易讀是這個(gè)課程設(shè)計(jì)的難點(diǎn)。程序總是由若干個(gè)函數(shù)構(gòu)成的，這些相應(yīng)的函數(shù)體現(xiàn)了算法的基本思想。 編程是一件枯燥乏味工作，但是只要認(rèn)真專研，我們會(huì)從中學(xué)到很多在課本上學(xué)不到或者無(wú)法在課堂上掌握的知識(shí)，同時(shí)也能從中感受到編程的樂(lè)趣。興趣是可以培養(yǎng)的，只要堅(jiān)持下去，面對(duì)困難我們總能夠找到解決問(wèn)題的方法。 計(jì)算多項(xiàng)式的輸出-----該程序雖然不是很大，但是自己獨(dú)立完成這一任務(wù)也遇到不少的困難。另外也需要提出的是，非常感謝老師對(duì)我們的耐心指導(dǎo)，尤其是上機(jī)的時(shí)候給了我很多鍛煉的機(jī)會(huì)。所以這次課程設(shè)計(jì)我才能夠順利的完成。 數(shù) 據(jù) 結(jié) 構(gòu) 課程設(shè)計(jì)報(bào)告 題 目： 一元多項(xiàng)式計(jì)算 專 業(yè)： 信息管理與信息系統(tǒng) 班 級(jí)： 2012級(jí)普本班 學(xué) 號(hào)： 201201011367 姓 名： 左帥帥 指導(dǎo)老師： 郝慎學(xué) 時(shí) 間： 一、課程設(shè)計(jì)題目分析 本課程設(shè)計(jì)要求利用C語(yǔ)言或C++編寫，本程序?qū)崿F(xiàn)了一元多項(xiàng)式的加法、減法、乘法、除法運(yùn)算等功能。 二、設(shè)計(jì)思路 本程序采用C語(yǔ)言來(lái)完成課程設(shè)計(jì)。 1、首先，利用順序存儲(chǔ)結(jié)構(gòu)來(lái)構(gòu)造兩個(gè)存儲(chǔ)多項(xiàng)式A(x)和 B(x)的結(jié)構(gòu)。 2、然后把輸入，加，減，乘，除運(yùn)算分成五個(gè)主要的模塊：實(shí)現(xiàn)多項(xiàng)式輸入模塊、實(shí)現(xiàn)加法的模塊、實(shí)現(xiàn)減法的模塊、實(shí)現(xiàn)乘法的模塊、實(shí)現(xiàn)除法的模塊。 3、然后各個(gè)模塊里面還要分成若干種情況來(lái)考慮并通過(guò)函數(shù)的嵌套調(diào)用來(lái)實(shí)現(xiàn)其功能，盡量減少程序運(yùn)行時(shí)錯(cuò)誤的出現(xiàn)。 4、最后編寫main()主函數(shù)以實(shí)現(xiàn)對(duì)多項(xiàng)式輸入輸出以及加、減、乘、除，調(diào)試程序并將不足的地方加以修改。 三、設(shè)計(jì)算法分析 1、相關(guān)函數(shù)說(shuō)明： (1)定義數(shù)據(jù)結(jié)構(gòu)類型為線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)類型變量 typedef struct Polynomial{} (2)其他功能函數(shù) 插入函數(shù)void Insert(Polyn p,Polyn h) 比較函數(shù)int compare(Polyn a,Polyn b) 建立一元多項(xiàng)式函數(shù)Polyn Create(Polyn head,int m) 求解并建立多項(xiàng)式a+b，Polyn Add(Polyn pa,Polyn pb) 求解并建立多項(xiàng)式a-b，Polyn Subtract(Polyn pa,Polyn pb)2 求解并建立多項(xiàng)式a*b，Polyn Multiply(Polyn pa,Polyn pb) 求解并建立多項(xiàng)式a/b，void Device(Polyn pa,Polyn pb) 輸出函數(shù)輸出多項(xiàng)式，void Print(Polyn P) 銷毀多項(xiàng)式函數(shù)釋放內(nèi)存，void Destroy(Polyn p) 主函數(shù)，void main（） 2、主程序的流程基函數(shù)調(diào)用說(shuō)明(1)typedef struct Polynomial { float coef; int expn; struct Polynomial *next;} *Polyn,Polynomial; 在這個(gè)結(jié)構(gòu)體變量中coef表示每一項(xiàng)前的系數(shù)，expn表示每一項(xiàng)的指數(shù)，polyn為結(jié)點(diǎn)指針類型，屬于抽象數(shù)據(jù)類型通常由用戶自行定義，Polynomial表示的是結(jié)構(gòu)體中的數(shù)據(jù)對(duì)象名。 (2)當(dāng)用戶輸入兩個(gè)一元多項(xiàng)式的系數(shù)和指數(shù)后，建立鏈表，存儲(chǔ)這兩個(gè)多項(xiàng)式，主要說(shuō)明如下： Polyn CreatePolyn(Polyn head,int m)建立一個(gè)頭指針為head、項(xiàng)數(shù)為m的一元多項(xiàng)式 p=head=(Polyn)malloc(sizeof(struct Polynomial));為輸入的多項(xiàng)式申請(qǐng)足夠的存儲(chǔ)空間 p=(Polyn)malloc(sizeof(struct Polynomial));建立新結(jié)點(diǎn)以接收數(shù)據(jù) Insert(p,head);調(diào)用Insert函數(shù)插入結(jié)點(diǎn) 這就建立一元多項(xiàng)式的關(guān)鍵步驟 (3)由于多項(xiàng)式的系數(shù)和指數(shù)都是隨即輸入的，所以根據(jù)要求需要對(duì)多項(xiàng)式按指數(shù)進(jìn)行降冪排序。在這個(gè)程序模塊中，使用鏈表，根據(jù)對(duì)指數(shù)大小的比較，對(duì)各種情況進(jìn)行處理，此處由于反復(fù)使用指針對(duì)各個(gè)結(jié)點(diǎn)進(jìn)行定位，找到合適的位置再利用void Insert(Polyn p,Polyn h)進(jìn)行插入操作。(4)加、減、乘、除、的算法實(shí)現(xiàn)： 在該程序中，最關(guān)鍵的一步是實(shí)現(xiàn)四則運(yùn)算和輸出，由于加減算法原則是一樣，減法可通過(guò)系數(shù)為負(fù)的加法實(shí)現(xiàn)；對(duì)于乘除算法的大致流程都是：首先建立多項(xiàng)式a*b，a/b，然后使用鏈表存儲(chǔ)所求出的乘積，商和余數(shù)。這就實(shí)現(xiàn)了多項(xiàng)式計(jì)算模塊的主要功能。 (5)另一個(gè)子函數(shù)是輸出函數(shù) PrintPolyn（）； 輸出最終的結(jié)果，算法是將最后計(jì)算合并的鏈表逐個(gè)結(jié)點(diǎn)依次輸出，便得到整鏈表，也就是最后的計(jì)算式計(jì)算結(jié)果。由于考慮各個(gè)結(jié)點(diǎn)的指數(shù)情況不同，分別進(jìn)行了判斷處理。 四、程序新點(diǎn) 通過(guò)多次寫程序，發(fā)現(xiàn)在程序在控制臺(tái)運(yùn)行時(shí)總是黑色的，本次寫程序就想著改變一下，于是經(jīng)過(guò)查資料利用system(“Color E0”);可以函數(shù)解決，這里“E0，”E是控制臺(tái)背景顏色，0是控制臺(tái)輸出字體顏色。 五、設(shè)計(jì)中遇到的問(wèn)題及解決辦法 首先是，由于此次課程設(shè)計(jì)里使用指針使用比較多，自己在指針多的時(shí)候易腦子混亂出錯(cuò)，對(duì)于此問(wèn)題我是采取比較笨的辦法在稿紙上寫明白后開始進(jìn)行 4 代碼編寫。 其次是，在寫除法模塊時(shí)比較復(fù)雜，自己通過(guò)查資料最后成功寫出除法模塊功能。 最后是，前期分析不足開始急于寫代碼，中途出現(xiàn)各種問(wèn)題，算是給自己以后設(shè)計(jì)時(shí)的一個(gè)經(jīng)驗(yàn)吧。 六、測(cè)試（程序截圖） 1.數(shù)據(jù)輸入及主菜單 2.加法和減法模塊 3.乘法和除法模塊 七、總結(jié) 通過(guò)本次應(yīng)用C語(yǔ)言設(shè)計(jì)一元多項(xiàng)式基本計(jì)算程序，使我更加鞏固了C語(yǔ)言程序設(shè)計(jì)的知識(shí)，以前對(duì)指針這一點(diǎn)使用是比較模糊，現(xiàn)在通過(guò)此次課程設(shè)計(jì)對(duì)指針理解的比較深刻了。而且對(duì)于數(shù)據(jù)結(jié)構(gòu)的相關(guān)算法和函數(shù)的調(diào)用方面知識(shí)的加深。本次的課程設(shè)計(jì)，一方面提高了自己獨(dú)立思考處理問(wèn)題的能力；另一方面使自己再設(shè)計(jì)開發(fā)程序方面有了一定的小經(jīng)驗(yàn)和想法，對(duì)自己以后學(xué)習(xí)其他語(yǔ)言程序設(shè)計(jì)奠定了一定的基礎(chǔ)。 八、指導(dǎo)老師評(píng)語(yǔ)及成績(jī) 附錄：（課程設(shè)計(jì)代碼） #include float coef;6 int expn; struct Polynomial *next;} *Polyn,Polynomial; //Polyn為結(jié)點(diǎn)指針類型 void Insert(Polyn p,Polyn h){ if(p->coef==0)free(p); //系數(shù)為0的話釋放結(jié)點(diǎn) else { Polyn q1,q2; q1=h;q2=h->next; while(q2&&p->expn { q1=q2;q2=q2->next;} if(q2&&p->expn==q2->expn)//將指數(shù)相同相合并 { q2->coef+=p->coef; free(p); if(!q2->coef)//系數(shù)為0的話釋放結(jié)點(diǎn) { q1->next=q2->next;free(q2);} } else { p->next=q2;q1->next=p; }//指數(shù)為新時(shí)將結(jié)點(diǎn)插入 } 7 } //建立一個(gè)頭指針為head、項(xiàng)數(shù)為m的一元多項(xiàng)式 Polyn Create(Polyn head,int m){ int i; Polyn p; p=head=(Polyn)malloc(sizeof(struct Polynomial)); head->next=NULL; for(i=0;i { p=(Polyn)malloc(sizeof(struct Polynomial));//建立新結(jié)點(diǎn)以接收數(shù)據(jù) printf(“請(qǐng)輸入第%d項(xiàng)的系數(shù)與指數(shù):”,i+1); scanf(“%f %d”,&p->coef,&p->expn); Insert(p,head); //調(diào)用Insert函數(shù)插入結(jié)點(diǎn) } return head;} //銷毀多項(xiàng)式p void Destroy(Polyn p){ Polyn q1,q2; q1=p->next;8 q2=q1->next; while(q1->next) { free(q1); q1=q2;//指針后移 q2=q2->next; } } //輸出多項(xiàng)式p int Print(Polyn P){ Polyn q=P->next; int flag=1;//項(xiàng)數(shù)計(jì)數(shù)器 if(!q)//若多項(xiàng)式為空，輸出0 { putchar('0'); printf(“n”); return; } while(q) { if(q->coef>0&&flag!=1)putchar('+');//系數(shù)大于0且不是第一項(xiàng) 9 if(q->coef!=1&&q->coef!=-1)//系數(shù)非1或-1的普通情況 { printf(“%g”,q->coef); if(q->expn==1)putchar('X'); else if(q->expn)printf(“X^%d”,q->expn); } else { if(q->coef==1){ if(!q->expn)putchar('1'); else if(q->expn==1)putchar('X'); else printf(“X^%d”,q->expn);} if(q->coef==-1){ if(!q->expn)printf(“-1”); else if(q->expn==1)printf(“-X”); else printf(“-X^%d”,q->expn);} } q=q->next; flag++; } printf(“n”);} int compare(Polyn a,Polyn b){ if(a&&b) { if(!b||a->expn>b->expn)return 1; else if(!a||a->expn else return 0; } else if(!a&&b)return-1;//a多項(xiàng)式已空，但b多項(xiàng)式非空 else return 1;//b多項(xiàng)式已空，但a多項(xiàng)式非空 } //求解并建立多項(xiàng)式a+b，返回其頭指針 Polyn Add(Polyn pa,Polyn pb){ Polyn qa=pa->next; Polyn qb=pb->next; Polyn headc,hc,qc; hc=(Polyn)malloc(sizeof(struct Polynomial));//建立頭結(jié)點(diǎn) 11 hc->next=NULL; headc=hc; while(qa||qb){ qc=(Polyn)malloc(sizeof(struct Polynomial)); switch(compare(qa,qb)) { case 1: qc->coef=qa->coef; qc->expn=qa->expn; qa=qa->next; break; case 0: qc->coef=qa->coef+qb->coef; qc->expn=qa->expn; qa=qa->next; qb=qb->next; break; case-1: qc->coef=qb->coef; qc->expn=qb->expn; qb=qb->next; break;12 } if(qc->coef!=0) { qc->next=hc->next; hc->next=qc; hc=qc; } else free(qc);//當(dāng)相加系數(shù)為0時(shí)，釋放該結(jié)點(diǎn) } return headc;} //求解并建立多項(xiàng)式a-b，返回其頭指針 Polyn Subtract(Polyn pa,Polyn pb){ Polyn h=pb; Polyn p=pb->next; Polyn pd; while(p)//將pb的系數(shù)取反 { p->coef*=-1;p=p->next;} pd=Add(pa,h); for(p=h->next;p;p=p->next) //恢復(fù)pb的系數(shù) p->coef*=-1;13 return pd;} //求解并建立多項(xiàng)式a*b，返回其頭指針 Polyn Multiply(Polyn pa,Polyn pb){ Polyn hf,pf; Polyn qa=pa->next; Polyn qb=pb->next; hf=(Polyn)malloc(sizeof(struct Polynomial));//建立頭結(jié)點(diǎn) hf->next=NULL; for(;qa;qa=qa->next) { for(qb=pb->next;qb;qb=qb->next) { pf=(Polyn)malloc(sizeof(struct Polynomial)); pf->coef=qa->coef*qb->coef; pf->expn=qa->expn+qb->expn; Insert(pf,hf);//調(diào)用Insert函數(shù)以合并指數(shù)相同的項(xiàng) } } return hf;} //求解并建立多項(xiàng)式a/b，返回其頭指針 void Device(Polyn pa,Polyn pb){ Polyn hf,pf,temp1,temp2; Polyn qa=pa->next; Polyn qb=pb->next; hf=(Polyn)malloc(sizeof(struct Polynomial));//建立頭結(jié)點(diǎn),存儲(chǔ)商 hf->next=NULL; pf=(Polyn)malloc(sizeof(struct Polynomial));//建立頭結(jié)點(diǎn)，存儲(chǔ)余數(shù) pf->next=NULL; temp1=(Polyn)malloc(sizeof(struct Polynomial)); temp1->next=NULL; temp2=(Polyn)malloc(sizeof(struct Polynomial)); temp2->next=NULL; temp1=Add(temp1,pa); while(qa!=NULL&&qa->expn>=qb->expn) { temp2->next=(Polyn)malloc(sizeof(struct Polynomial)); temp2->next->coef=(qa->coef)/(qb->coef); temp2->next->expn=(qa->expn)-(qb->expn); Insert(temp2->next,hf); pa=Subtract(pa,Multiply(pb,temp2));15 qa=pa->next; temp2->next=NULL; } pf=Subtract(temp1,Multiply(hf,pb)); pb=temp1; printf(“商是:”); Print(hf); printf(“余數(shù)是:”); Print(pf);} void main(){ int choose=1;int m,n,flag=0;system(“Color E0”);Polyn pa=0,pb=0,pc,pd,pf;//定義各式的頭指針，pa與pb在使用前付初值NULL printf(“請(qǐng)輸入A(x)的項(xiàng)數(shù):”);scanf(“%d”,&m);printf(“n”);pa=Create(pa,m);//建立多項(xiàng)式A printf(“n”);printf(“請(qǐng)輸入B(x)的項(xiàng)數(shù):”);16 scanf(“%d”,&n);printf(“n”);pb=Create(pb,n);//建立多項(xiàng)式B printf(“n”);printf(“**********************************************n”);printf(“* 多項(xiàng)式操作菜單 printf(”**********************************************n“);printf(”tt 1.輸出操作n“);printf(”tt 2.加法操作n“);printf(”tt 3.減法操作n“);printf(”tt 4.乘法操作n“);printf(”tt 5.除法操作n“);printf(”tt 6.退出操作n“);printf(”**********************************************n“);while(choose){ printf(”執(zhí)行操作:“); scanf(”%d“,&flag); switch(flag) { case 1: printf(”多項(xiàng)式A(x):“);Print(pa);*n”); printf(“多項(xiàng)式B(x):”);Print(pb); break; case 2: pc=Add(pa,pb); printf(“多項(xiàng)式A(x)+B(x):”);Print(pc); Destroy(pc);break; case 3: pd=Subtract(pa,pb); printf(“多項(xiàng)式A(x)-B(x):”);Print(pd); Destroy(pd);break; case 4: pf=Multiply(pa,pb); printf(“多項(xiàng)式A(x)*B(x):”); Print(pf); Destroy(pf); break; case 5: Device(pa,pb);18 break; case 6: exit(0); break; } } Destroy(pa); Destroy(pb);} 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì) 1.赫夫曼編碼器 設(shè)計(jì)一個(gè)利用赫夫曼算法的編碼和譯碼系統(tǒng)，重復(fù)地顯示并處理以下項(xiàng)目，直到選擇退出為止。要求： 1)將權(quán)值數(shù)據(jù)存放在數(shù)據(jù)文件(文件名為data.txt，位于執(zhí)行程序的當(dāng)前目錄中) 2)初始化：鍵盤輸入字符集大小26、26個(gè)字符和26個(gè)權(quán)值（統(tǒng)計(jì)一篇英文文章中26個(gè)字母），建立哈夫曼樹； 3)編碼：利用建好的哈夫曼樹生成哈夫曼編碼； 4)輸出編碼（首先實(shí)現(xiàn)屏幕輸出，然后實(shí)現(xiàn)文件輸出）； 5)界面優(yōu)化設(shè)計(jì)。 代碼如下： #include typedef struct HTNode //結(jié)構(gòu)體 { int Weight; char ch;int Parent,Lchild,Rchild;}HTNode;typedef char * * HCode; void Save(int n,HTNode *HT) //把權(quán)值保存到文件 { FILE * fp; int i; if((fp=fopen(“data.txt”,“wb”))==NULL) { printf(“cannot open filen”); return; } for(i=0;i if(fwrite(&HT[i].Weight,sizeof(struct HTNode),1,fp)!=1) printf(“file write errorn”); fclose(fp); system(“cls”); printf(“保存成功！”); } void Create_H(int n,int m,HTNode *HT) //建立赫夫曼樹，進(jìn)行編碼 { int w,k,j;char c;for(k=1;k<=m;k++){ if(k<=n) { printf(“n請(qǐng)輸入權(quán)值和字符(用空格隔開): ”); scanf(“%d”,&w); scanf(“ %c”,&c);HT[k].ch=c; HT[k].Weight=w; } else HT[k].Weight=0; HT[k].Parent=HT[k].Lchild=HT[k].Rchild=0;} int p1,p2,w1,w2; for(k=n+1;k<=m;k++){ p1=0;p2=0; w1=32767;w2=32767; for(j=1;j<=k-1;j++) { if(HT[j].Parent==0) { if(HT[j].Weight { w2=w1;p2=p1; w1=HT[j].Weight; p1=j; } else if(HT[j].Weight { w2=HT[j].Weight; p2=j; } } } HT[k].Lchild=p1;HT[k].Rchild=p2;HT[k].Weight=HT[p1].Weight+HT[p2].Weight; HT[p1].Parent=k;HT[p2].Parent=k; } printf(“輸入成功！”);} void Coding_H(int n,HTNode *HT) //對(duì)結(jié)點(diǎn)進(jìn)行譯碼 { int k,sp,fp,p;char *cd;HCode HC; HC=(HCode)malloc((n+1)*sizeof(char *)); cd=(char *)malloc(n*sizeof(char));cd[n-1]='
第二篇：2012數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)
第三篇：數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)