第一篇：數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)2013

數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)題目（2013年）

一、必做題

1、圖書管理系統(tǒng)（線性表）[問題描述]

設(shè)計(jì)一個(gè)程序，記錄并統(tǒng)計(jì)圖書使用情況。[基本要求]（1）圖書信息包括圖書ID號(hào)，圖書名，出版社名，出版年月，館藏冊數(shù)。（2）學(xué)生信息包括學(xué)號(hào)，姓名，班級，在借冊數(shù)，已還冊數(shù)，違約次數(shù)。

（3）借閱信息包括圖書ID號(hào)，圖書名，學(xué)號(hào)，姓名，借閱日期，應(yīng)還日期，歸還日期。

（4）采用順序存儲(chǔ)線性表表示圖書信息。采用鏈?zhǔn)酱鎯?chǔ)線性表表示學(xué)生信息。采用雙向循環(huán)鏈表表示借閱信息。其中一個(gè)雙向循環(huán)鏈表表示在借的借閱信息，按照圖書ID號(hào)非遞減排序；另一個(gè)雙向循環(huán)鏈表表示已還的借閱信息，按照圖書ID號(hào)非遞減排序。（5）圖書信息，學(xué)生信息、借閱信息采用文件方式輸入。

圖書信息示例如下，每條信息一行：

16000001 數(shù)據(jù)結(jié)構(gòu) 清華大學(xué)出版社 2012.10 30 學(xué)生信息示例如下，每條信息一行： 161340106 張三 1613401 5 10 借閱信息示例如下，每條信息一行：

標(biāo)志位1（1 表示借閱 2表示歸還）16000001 數(shù)據(jù)結(jié)構(gòu) 161340106 張三 2013.9.12（借閱時(shí)表示借閱日期，應(yīng)還日期自動(dòng)生成，根據(jù)借閱日期+60天； 歸還時(shí)表示歸還日期，歸還日期要在借閱日期之后，應(yīng)還日期之前，如果超過應(yīng)還日期，則記錄一次違約次數(shù)）。

例如借閱： 1 16000001 數(shù)據(jù)結(jié)構(gòu) 161340106 張三 2013.9.12 歸還： 2 16000001 數(shù)據(jù)結(jié)構(gòu) 161340106 張三 2013.10.20（6）規(guī)定每位學(xué)生不能同時(shí)借閱同一本書兩本及以上。圖書歸還后，將該條借閱信息從借閱鏈表中轉(zhuǎn)移到歸還鏈表中。

（7）要求模擬數(shù)據(jù)中圖書信息至少30本以上，學(xué)生信息至少20條以上，借閱信息至少50條以上。

（8）能夠統(tǒng)計(jì)每一本圖書被借閱次數(shù)（已還），在借冊數(shù)。查詢每一位學(xué)生的借閱歷史明細(xì)記錄。統(tǒng)計(jì)學(xué)生平均借閱次數(shù)，最大借閱次數(shù)，最少借閱次數(shù)。（9）可在此要求基礎(chǔ)上進(jìn)行功能擴(kuò)展。

2、算術(shù)表達(dá)式求值（棧）[問題描述]

一個(gè)算術(shù)表達(dá)式是由操作數(shù)(operand)、運(yùn)算符(operator)和界限符(delimiter)組成的。假設(shè)操作數(shù)是正實(shí)數(shù)，運(yùn)算符只含加減乘除等四種運(yùn)算符，界限符有左右括號(hào)和表達(dá)式起始、結(jié)束符“#”，如：#（7+15）*（23-28/4）#。引入表達(dá)式起始、結(jié)束符是為了方便。編程利用“算符優(yōu)先法”求算術(shù)表達(dá)式的值。[基本要求]（1）從鍵盤或文件讀入一個(gè)合法的算術(shù)表達(dá)式，輸出正確的結(jié)果。（2）顯示輸入序列和棧的變化過程。

（3）考慮算法的健壯性，當(dāng)表達(dá)式錯(cuò)誤時(shí)，要給出錯(cuò)誤原因的提示。

3、二叉樹的應(yīng)用（二叉樹）[問題描述] 編程實(shí)現(xiàn)二叉樹的建立，先序、中序、后序（遞歸和非遞歸方法）、層序遍歷，二叉樹的高度、繁茂度，交換左右子樹，統(tǒng)計(jì)葉子節(jié)點(diǎn)的數(shù)目，判斷是否為完全二叉樹，按樹的形態(tài)在屏幕上打印輸出。[基本要求]（1）從文件中讀入建樹信息，樹的節(jié)點(diǎn)數(shù)目不小于20個(gè)，樹的高度不小于4。（2）建樹信息采用兩行英文字符表示，每個(gè)英文字符代表一個(gè)結(jié)點(diǎn)，第1行為樹的中序遍歷結(jié)果，第2行為樹的后序遍歷結(jié)果。

4、Huffman編碼與解碼（Huffman編碼、二叉樹）[問題描述] 對一篇英文文章（大于2000個(gè)英文字符），統(tǒng)計(jì)各字符出現(xiàn)的次數(shù)，實(shí)現(xiàn)Huffman編碼，以及對編碼結(jié)果的解碼。[基本要求]（1）輸出每個(gè)字符出現(xiàn)的次數(shù)和編碼，其中求最小權(quán)值要求用堆實(shí)現(xiàn)。

（2）在Huffman編碼后，要將編碼表和英文文章編碼結(jié)果保存到文件中，編碼結(jié)果必須是二進(jìn)制形式，即0 1的信息用比特位表示，不能用字符’0’和’1’表示。（3）提供讀編碼文件生成原文件的功能。

5、關(guān)鍵路徑問題（圖）[問題描述] 設(shè)計(jì)并實(shí)現(xiàn)關(guān)鍵路徑的一種應(yīng)用。[基本要求]（1）實(shí)現(xiàn)拓?fù)渑判蚝完P(guān)鍵路徑的發(fā)現(xiàn)。（2）給出一個(gè)具體的應(yīng)用環(huán)境。

6、排序算法比較（排序）[問題描述] 利用隨機(jī)函數(shù)產(chǎn)生10個(gè)樣本（其中之一已為正序，之一為倒序），每個(gè)樣本有20000隨機(jī)整數(shù)，利用直接插入排序、希爾排序，冒泡排序、快速排序、選擇排序、堆排序，歸并排序（遞歸和非遞歸），基數(shù)排序八種排序方法進(jìn)行排序（結(jié)果為由小到大的順序），并統(tǒng)計(jì)每一種排序所耗費(fèi)的平均時(shí)間 [基本要求]（1）原始數(shù)據(jù)存在文件中，每個(gè)整數(shù)一行，方便讀入。（2）屏幕顯示每種排序所花的比較次數(shù)。

二、選做題

1、迷宮問題（棧與遞歸）[問題描述] 利用棧操作實(shí)現(xiàn)迷宮問題求解。[基本要求]（1）隨機(jī)生成模擬迷宮地圖，不少于10行10列，存在文件中。（2）動(dòng)態(tài)顯示每一步的結(jié)果。（3）可在此基礎(chǔ)上有改進(jìn)方法。

2、家譜管理系統(tǒng)（樹）[問題描述] 實(shí)現(xiàn)具有下列功能的家譜管理系統(tǒng) [基本要求]（1）輸入文件以存放最初家譜中各成員的信息，成員的信息中均應(yīng)包含以下內(nèi)容：姓名、出生日期、婚否、地址、健在否、死亡日期（若其已死亡），也可附加其它信息、但不是必需的。

（2）實(shí)現(xiàn)數(shù)據(jù)的存盤和讀盤。（3）以圖形方式顯示家譜。（4）顯示第n 代所有人的信息。

（5）按照姓名查詢，輸出成員信息（包括其本人、父親、孩子的信息）。（6）按照出生日期查詢成員名單。（7）輸入兩人姓名，確定其關(guān)系。（8）某成員添加孩子。

（9）刪除某成員（若其還有后代，則一并刪除）。（10）修改某成員信息。

（11）按出生日期對家譜中所有人排序。

（12）打開一家譜時(shí)，提示當(dāng)天生日的健在成員。（13）要求建立至少30個(gè)成員的數(shù)據(jù)，以較為直觀的方式顯示結(jié)果，并提供文稿形式以便檢查。

（14）界面要求：有合理的提示，每個(gè)功能可以設(shè)立菜單，根據(jù)提示，可以完成相關(guān)的功能要求。

（15）存儲(chǔ)結(jié)構(gòu)：根據(jù)系統(tǒng)功能要求自行設(shè)計(jì)，但是要求相關(guān)數(shù)據(jù)要存儲(chǔ)在數(shù)據(jù)文件中。測試數(shù)據(jù)：要求使用

1、全部合法數(shù)據(jù)；

2、局部非法數(shù)據(jù)。進(jìn)行程序測試，以保證程序的穩(wěn)定。

3、公交線路提示（圖）[問題描述] 建立南京主要公交線路圖。[基本要求]（1）輸入任意兩站點(diǎn)，給出最佳的乘車線路和轉(zhuǎn)車地點(diǎn)。路線信息：可上網(wǎng)查詢最新的公交線路信息

4、社交網(wǎng)絡(luò)圖實(shí)現(xiàn)（圖）[問題描述] 設(shè)計(jì)并實(shí)現(xiàn)一種簡單的社交網(wǎng)絡(luò)模型圖。[基本要求]（1）每個(gè)人的信息是一個(gè)結(jié)點(diǎn)，人與人的聯(lián)系構(gòu)成邊。個(gè)人信息里要有地理坐標(biāo)信息，以便后續(xù)應(yīng)用中能方便找靠近的人。

（2）根據(jù)輸入的任意兩個(gè)人信息，給出他們之間的聯(lián)系路徑，最少經(jīng)過多少人構(gòu)成聯(lián)系。

（3）根據(jù)位置信息的動(dòng)態(tài)變化，找尋附近能夠聯(lián)絡(luò)的人，能夠通過1次中間人能聯(lián)絡(luò)的人等。

（4）模擬仿真結(jié)點(diǎn)的聯(lián)絡(luò)密切程度，根據(jù)聯(lián)絡(luò)密切程度發(fā)現(xiàn)社交網(wǎng)絡(luò)中的小團(tuán)體。（5）可根據(jù)自己的創(chuàng)意添加更多的功能。

5、營業(yè)窗口隊(duì)列模擬

任務(wù)：實(shí)現(xiàn)具有n（n=3）個(gè)窗口的現(xiàn)實(shí)隊(duì)列模擬，統(tǒng)計(jì)每人的等待時(shí)間。要求：

1).隨機(jī)產(chǎn)生顧客的到達(dá)時(shí)間和服務(wù)時(shí)間存盤。2).利用存盤數(shù)據(jù)實(shí)現(xiàn)隊(duì)列的插入和刪除。2).當(dāng)有顧客離開時(shí)，根據(jù)隊(duì)列長度調(diào)整隊(duì)尾。3).考慮顧客中途離隊(duì)的情況。4).考慮顧客具有優(yōu)先級的情況。

6、電子小字典

任務(wù)：建立一個(gè)微型電子字典，實(shí)現(xiàn)生詞的加入，單詞的查找、刪除，修改等操作。數(shù)據(jù)結(jié)構(gòu)：鍵樹

7、稀疏矩陣相乘

任務(wù)：以三元組形式存儲(chǔ)稀疏矩陣，實(shí)現(xiàn)矩陣相乘

8、平衡二叉樹

任務(wù)：平衡二叉樹的建立、結(jié)點(diǎn)的插入和刪除。

9、B-樹

任務(wù)：3階B-樹的結(jié)點(diǎn)的插入和刪除。

10、編寫?連連看?程序。

11、??（自選合適的題目）

成績評定細(xì)則：

1.正確性：程序是否可以運(yùn)行，結(jié)果是否正確（20分）2.功能的完備性：是否實(shí)現(xiàn)要求的所有子功能（20分）

3.課程設(shè)計(jì)報(bào)告中的算法說明的清晰程度，課程設(shè)計(jì)報(bào)告中總結(jié)的深刻程度（20分）4.獨(dú)立完成情況(40分）總計(jì)：100分

加分項(xiàng)目：

1.工作量和選題難度

2.可讀性：代碼編寫是否規(guī)范，是否便于閱讀。如函數(shù)、變量命名，‘{ }’的縮進(jìn)，關(guān)鍵位置適量注釋等

3.功能的完善：除要求實(shí)現(xiàn)的功能外，完成了其它的功能，實(shí)現(xiàn)了功能的完善 4.健壯性：異常處理的情況

5.界面的設(shè)計(jì)：可視化界面，或者交互良好的DOS界面 6.……（自薦加分項(xiàng)目）

代碼量要求：>=2200行。

代碼總量 = 課設(shè)題目1 代碼量 + 課設(shè)題目2 代碼量…… 若代碼總量低于2200行，則成績按比例打折。

編程語言：C、C++ 或 JAVA 任選其一

檢查方式: 1.一對一上機(jī)檢查

2.總體上檢查程序的代碼量，正確性，可讀性，健壯性，功能的完備性，程序的結(jié)構(gòu)是否合理；根據(jù)實(shí)際情況進(jìn)行詳細(xì)的程序代碼檢查。

時(shí)間安排： 1 上機(jī)時(shí)間安排 課程設(shè)計(jì)報(bào)告上交時(shí)間 3 課程設(shè)計(jì)檢查時(shí)間

課程設(shè)計(jì)報(bào)告要求：

1.課程設(shè)計(jì)報(bào)告封面：包括課題名稱、班級、學(xué)號(hào)、學(xué)生姓名、成績和指導(dǎo)教師； 2.課程設(shè)計(jì)報(bào)告目錄：每部分內(nèi)容所在頁碼； 3.需求分析：給出每道題的需求；

4.概要設(shè)計(jì)：給出每道題采用的數(shù)據(jù)結(jié)構(gòu)，算法設(shè)計(jì)思想，算法的時(shí)間復(fù)雜度； 5.詳細(xì)設(shè)計(jì)：給出每道題的源程序，并在必要的代碼處給出注釋； 6.功能測試：給出每道題的測試數(shù)據(jù)和結(jié)果；

7.完成情況：每道題完成部分和未完成部分，自己最滿意的部分； 8.代碼量：每道題代碼的行數(shù)和總行數(shù)；

9.心得體會(huì)：包括課程設(shè)計(jì)設(shè)中遇到的問題，如何解決，編程的體驗(yàn)，感想和建議； 10.課程設(shè)計(jì)報(bào)告的電子文檔在檢查后一周內(nèi)上交班長。

第二篇：2012數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)

數(shù) 據(jù) 結(jié) 構(gòu)

課程設(shè)計(jì)報(bào)告

題 目： 一元多項(xiàng)式計(jì)算 專 業(yè)： 信息管理與信息系統(tǒng) 班 級： 2012級普本班 學(xué) 號(hào)： 201201011367 姓 名： 左帥帥 指導(dǎo)老師： 郝慎學(xué) 時(shí) 間：

一、課程設(shè)計(jì)題目分析

本課程設(shè)計(jì)要求利用C語言或C++編寫，本程序?qū)崿F(xiàn)了一元多項(xiàng)式的加法、減法、乘法、除法運(yùn)算等功能。

二、設(shè)計(jì)思路

本程序采用C語言來完成課程設(shè)計(jì)。

1、首先，利用順序存儲(chǔ)結(jié)構(gòu)來構(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è)模塊里面還要分成若干種情況來考慮并通過函數(shù)的嵌套調(diào)用來實(shí)現(xiàn)其功能，盡量減少程序運(yùn)行時(shí)錯(cuò)誤的出現(xiàn)。

4、最后編寫main()主函數(shù)以實(shí)現(xiàn)對多項(xiàng)式輸入輸出以及加、減、乘、除，調(diào)試程序并將不足的地方加以修改。

三、設(shè)計(jì)算法分析

1、相關(guān)函數(shù)說明：

(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)用說明(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ù)對象名。

(2)當(dāng)用戶輸入兩個(gè)一元多項(xiàng)式的系數(shù)和指數(shù)后，建立鏈表，存儲(chǔ)這兩個(gè)多項(xiàng)式，主要說明如下：

Polyn CreatePolyn(Polyn head,int m)建立一個(gè)頭指針為head、項(xiàng)數(shù)為m的一元多項(xiàng)式

p=head=(Polyn)malloc(sizeof(struct Polynomial));為輸入的多項(xià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ù)要求需要對多項(xiàng)式按指數(shù)進(jìn)行降冪排序。在這個(gè)程序模塊中，使用鏈表，根據(jù)對指數(shù)大小的比較，對各種情況進(jìn)行處理，此處由于反復(fù)使用指針對各個(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)算和輸出，由于加減算法原則是一樣，減法可通過系數(shù)為負(fù)的加法實(shí)現(xiàn)；對于乘除算法的大致流程都是：首先建立多項(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)

通過多次寫程序，發(fā)現(xiàn)在程序在控制臺(tái)運(yùn)行時(shí)總是黑色的，本次寫程序就想著改變一下，于是經(jīng)過查資料利用system(“Color E0”);可以函數(shù)解決，這里“E0，”E是控制臺(tái)背景顏色，0是控制臺(tái)輸出字體顏色。

五、設(shè)計(jì)中遇到的問題及解決辦法

首先是，由于此次課程設(shè)計(jì)里使用指針使用比較多，自己在指針多的時(shí)候易腦子混亂出錯(cuò)，對于此問題我是采取比較笨的辦法在稿紙上寫明白后開始進(jìn)行 4

代碼編寫。

其次是，在寫除法模塊時(shí)比較復(fù)雜，自己通過查資料最后成功寫出除法模塊功能。

最后是，前期分析不足開始急于寫代碼，中途出現(xiàn)各種問題，算是給自己以后設(shè)計(jì)時(shí)的一個(gè)經(jīng)驗(yàn)吧。

六、測試（程序截圖）

1.數(shù)據(jù)輸入及主菜單

2.加法和減法模塊

3.乘法和除法模塊

七、總結(jié)

通過本次應(yīng)用C語言設(shè)計(jì)一元多項(xiàng)式基本計(jì)算程序，使我更加鞏固了C語言程序設(shè)計(jì)的知識(shí)，以前對指針這一點(diǎn)使用是比較模糊，現(xiàn)在通過此次課程設(shè)計(jì)對指針理解的比較深刻了。而且對于數(shù)據(jù)結(jié)構(gòu)的相關(guān)算法和函數(shù)的調(diào)用方面知識(shí)的加深。本次的課程設(shè)計(jì)，一方面提高了自己獨(dú)立思考處理問題的能力；另一方面使自己再設(shè)計(jì)開發(fā)程序方面有了一定的小經(jīng)驗(yàn)和想法，對自己以后學(xué)習(xí)其他語言程序設(shè)計(jì)奠定了一定的基礎(chǔ)。

八、指導(dǎo)老師評語及成績

附錄：（課程設(shè)計(jì)代碼）

#include #include #include typedef struct Polynomial {

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->expnexpn)//查找插入位置

{

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(“請輸入第%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->expnexpn)return-1;

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(“請輸入A(x)的項(xiàng)數(shù):”);scanf(“%d”,&m);printf(“n”);pa=Create(pa,m);//建立多項(xiàng)式A printf(“n”);printf(“請輸入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ì)

數(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 #include #include #include #define N 200

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請輸入權(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)

//對結(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]='