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

數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)選題

1、校園導(dǎo)游咨詢（為來(lái)訪的客人提供各種信息服務(wù)）

基本要求：

1、設(shè)計(jì)淮陰師范學(xué)院北校區(qū)平面圖，在校園景點(diǎn)不低于10個(gè)。以圖中頂點(diǎn)表示校園內(nèi)各景點(diǎn)，存放景點(diǎn)名稱、代號(hào)、簡(jiǎn)介等信息；以邊表示路徑，存放路徑長(zhǎng)度等有關(guān)信息。

2、為來(lái)訪客人提供圖中任意景點(diǎn)相關(guān)信息的查詢。

3、為來(lái)訪客人提供任意景點(diǎn)的問(wèn)路查詢，即查詢?nèi)我鈨蓚€(gè)景點(diǎn)之間的一條最短路徑。

設(shè)計(jì)等級(jí) B

2、迷宮問(wèn)題

問(wèn)題描述：編寫一個(gè)程序求解迷宮問(wèn)題。迷宮由m行n列的二維數(shù)組設(shè)置，0表示無(wú)障礙，1表示有障礙。設(shè)入口為（1，1），出口為（m，n），每次只能從一個(gè)無(wú)障礙單元移到周圍四個(gè)方向上任一無(wú)障礙單元。編程給出通過(guò)路徑或無(wú)法通行的信息。要求：

1、輸出迷宮的所有路徑

2、篩選出最短路徑。

設(shè)計(jì)等級(jí) A

3、算術(shù)表達(dá)式的求解

問(wèn)題描述：以字符序列的形式從終端輸入語(yǔ)法正確的、不含變量的整數(shù)算術(shù)表達(dá)式，編寫程序求出該表達(dá)式的后綴表達(dá)式；計(jì)算最后的結(jié)果。基本要求：

1、表達(dá)式中至少包含加、減、乘、除四種基本運(yùn)算

2、表達(dá)式中括號(hào)的層次至少為2層

3、能夠判斷算術(shù)表達(dá)式正確與否

4、對(duì)于錯(cuò)誤表達(dá)式給出提示

5、輸出后綴表達(dá)式

6、計(jì)算結(jié)果

設(shè)計(jì)等級(jí) A

4、通訊錄系統(tǒng)設(shè)計(jì)

問(wèn)題描述：采用鏈表結(jié)構(gòu)設(shè)計(jì)一個(gè)通訊錄系統(tǒng)。基本要求：

1)通訊錄鏈表的建立 2)通訊者結(jié)點(diǎn)的插入 3)通訊者結(jié)點(diǎn)的刪除 4)通訊者結(jié)點(diǎn)的查詢 5)通訊錄輸出 6)設(shè)計(jì)退出系統(tǒng)

7)要求鏈表的讀取要在文件中完成。

設(shè)計(jì)等級(jí) A

5、樹(shù)的應(yīng)用

問(wèn)題描述：運(yùn)用二叉鏈表結(jié)構(gòu)存儲(chǔ)一棵高度不低于5的樹(shù)，完成以下操作

1、輸出樹(shù)的高度

2、輸出樹(shù)根到其它任意結(jié)點(diǎn)的路徑

3、輸出該樹(shù)的后序遍歷序列

4、計(jì)算任意結(jié)點(diǎn)的所處的高度

設(shè)計(jì)等級(jí) A

6、文本文件單詞的檢索與計(jì)數(shù)

問(wèn)題描述：要求編程建立一個(gè)文本文件，每個(gè)單詞不包含空格且不跨行，單詞由字符序列構(gòu)成且區(qū)分大小寫； 要求：

1、統(tǒng)計(jì)給定單詞在文本文件中出現(xiàn)的總次數(shù)；

2、檢索輸出某個(gè)單詞出現(xiàn)在文本中的行號(hào)、在該行中出現(xiàn)的次數(shù)以及位置。

設(shè)計(jì)等級(jí) A

7、二叉平衡排序樹(shù)

問(wèn)題描述：創(chuàng)建二叉平衡排序樹(shù) 基本要求：

1、輸入數(shù)據(jù)的數(shù)量不得低于15個(gè)

2、建立二叉平衡排序樹(shù)（要求包括LL型LR型RR型RL型四種調(diào)整方式）

3、完成任意數(shù)據(jù)的查找（要求給出查找執(zhí)行的次數(shù)）

設(shè)計(jì)等級(jí) B

8、構(gòu)造可以使n個(gè)城市連接的最小生成樹(shù)

問(wèn)題描述：給定一個(gè)地區(qū)的n個(gè)城市間的距離網(wǎng)，用Prim算法建立最小生成樹(shù)，并計(jì)算得到的最小生成樹(shù)的代價(jià)。基本要求：

1、城市間的距離網(wǎng)采用鄰接矩陣表示，若兩個(gè)城市之間不存在道路，則將相應(yīng)邊的權(quán)值設(shè)為自己定義的無(wú)窮大值。（要求至少10個(gè)城市，15條邊）

2、最小生成樹(shù)中包括的邊及其權(quán)值，并顯示得到的最小生成樹(shù)的代價(jià)。

設(shè)計(jì)等級(jí) B

9、哈夫曼編/譯碼器

1、問(wèn)題描述：

利用哈夫曼編碼進(jìn)行信息通信可以大大提高信道利用率，縮短信息傳輸時(shí)間，降低傳輸成本。但是，這要求在發(fā)送端通過(guò)一個(gè)編碼系統(tǒng)對(duì)待傳數(shù)據(jù)預(yù)先編碼，在接收端將傳來(lái)的數(shù)據(jù)進(jìn)行譯碼（復(fù)原）。試寫一個(gè)哈夫曼編/譯碼系統(tǒng)。

2、基本要求：

一個(gè)完整的系統(tǒng)應(yīng)具有以下功能：

（1）初始化。從終端讀入字符集大小n，以及n個(gè)字符和n個(gè)權(quán)值，建立哈夫曼樹(shù)，并將它存于文件中。

（2）編碼。利用已建好的哈夫曼樹(shù)對(duì)文件中的正文進(jìn)行編碼，然后將結(jié)果存入文件中。（3）譯碼。利用已建好的哈夫曼樹(shù)將文件中的代碼進(jìn)行譯碼，結(jié)果存入文件中。（4）完成數(shù)據(jù)測(cè)試，要求編碼字符不低于15個(gè)，編碼文件的長(zhǎng)度不低于50個(gè)字符。

(5)計(jì)算平均編碼長(zhǎng)度。

設(shè)計(jì)等級(jí) B

10、二叉樹(shù)的遍歷

問(wèn)題描述：創(chuàng)建二叉樹(shù)并遍歷 基本要求：

1、分別運(yùn)用非遞歸的方式完成對(duì)二叉樹(shù)的先序和后序遍歷

2、輸出二叉樹(shù)的高度

3、輸出每一層的結(jié)點(diǎn)數(shù)

4、查找結(jié)點(diǎn)P 和結(jié)點(diǎn)Q的最近共同祖先

設(shè)計(jì)等級(jí) B

11、尋找舞伴

一班有m個(gè)女生,有n個(gè)男生(m不等于n),現(xiàn)要開(kāi)一個(gè)舞會(huì).男女生分別編號(hào)坐在舞池的兩邊的椅子上.每曲開(kāi)始時(shí),依次從男生和女生中各出一人配對(duì)跳舞, 本曲沒(méi)成功配對(duì)者坐著等待下一曲找舞伴.請(qǐng)?jiān)O(shè)計(jì)一系統(tǒng)模擬動(dòng)態(tài)地顯示出上述過(guò)程,要求如下: 1)輸出每曲配對(duì)情況

2)計(jì)算出任何一個(gè)男生(編號(hào)為X)和任意女生(編號(hào)為Y),在第K曲配對(duì)跳舞的情況。

設(shè)計(jì)等級(jí) A

12、關(guān)鍵路徑和拓?fù)渑判?/p>

問(wèn)題描述：創(chuàng)建一個(gè)AOE網(wǎng)完成如下要求 基本要求：

1、采用鄰接表結(jié)構(gòu)存儲(chǔ)網(wǎng)（結(jié)點(diǎn)數(shù)量不低于10個(gè)，邊的數(shù)量不低于15條）

2、輸出一個(gè)拓?fù)湫蛄?/p>

3、輸出所有關(guān)鍵路徑并計(jì)算路徑長(zhǎng)度。

設(shè)計(jì)等級(jí) B

13、設(shè)計(jì)一個(gè)航空客運(yùn)定票系統(tǒng)。

要求：

1、每條航線所涉及的信息有：終點(diǎn)站名、航班號(hào)、飛機(jī)號(hào)、飛機(jī)周日（星期幾）、乘員定額、余票量、訂定票的客戶名單（包括姓名、訂票量、艙位等級(jí)1，2或3）以及等候替補(bǔ)的客戶名單（包括姓名、所需數(shù)量）。

2、系統(tǒng)能實(shí)現(xiàn)的操作和功能如下：

1）查詢航線：根據(jù)客戶提出的終點(diǎn)站名輸出如下信息：航班號(hào)、飛機(jī)號(hào)、星期幾飛行，最近一天航班的日期和余票額；

2）承辦訂票業(yè)務(wù)：根據(jù)客戶提出的要求（航班號(hào)、訂票數(shù)額）查詢?cè)摵桨嗥鳖~情況，若有余票，則為客戶辦理訂票手續(xù)，輸出座位號(hào)；若已滿員或余票少余訂票額，則需重新詢問(wèn)客戶要求。若需要，可登記排隊(duì)候補(bǔ)；

3）承辦退票業(yè)務(wù)：根據(jù)客戶提出的情況（日期、航班號(hào)），為客戶辦理退票手續(xù)，然后查詢?cè)摵桨嗍欠裼腥伺抨?duì)候補(bǔ)，首先詢問(wèn)排在第一的客戶，若所退票額能滿足他的要求，則為他辦理訂票手續(xù)，否則依次詢問(wèn)其它排隊(duì)候補(bǔ)的客戶。

3、要求：航線、客戶等信息必須存儲(chǔ)在文件中

4、采用鏈表作為數(shù)據(jù)結(jié)構(gòu)

設(shè)計(jì)等級(jí) A

14、醫(yī)院選址

問(wèn)題描述：有n個(gè)村莊，現(xiàn)要從這n個(gè)村莊中選擇一個(gè)村莊新建一所醫(yī)院，使其余的村莊到這所醫(yī)院的距離總和來(lái)說(shuō)較短。（n>6）

設(shè)計(jì)等級(jí) B

15、客戶消費(fèi)積分管理系統(tǒng)

問(wèn)題描述：針對(duì)客戶的消費(fèi)情況，進(jìn)行客戶管理，根據(jù)客戶的消費(fèi)積分對(duì)客戶實(shí)行不同程度的打折優(yōu)惠。基本要求：

1.采用一定的存儲(chǔ)結(jié)構(gòu)進(jìn)行客戶信息的存儲(chǔ)； 2.對(duì)客戶的信息可以進(jìn)行修改、刪除、添加； 3.能夠根據(jù)消費(fèi)情況進(jìn)行客戶積分的計(jì)算； 4.根據(jù)積分情況實(shí)行不同程度的打折優(yōu)惠； 5． 數(shù)據(jù)必須保存到文件中

設(shè)計(jì)等級(jí) A

16、排序綜合

問(wèn)題描述：要求分別采用快速排序、二路歸并排序、堆排序和希爾排序?qū)﹄S機(jī)生成的一組數(shù)據(jù)進(jìn)行排序（數(shù)據(jù)不少于100）； 要求：

1、完成排序的輸入、輸出

2、比較各種排序的性能

3、界面友好，提供操作菜單

設(shè)計(jì)等級(jí) A

17、樹(shù)與二叉樹(shù)的轉(zhuǎn)換

問(wèn)題描述：完成樹(shù)與二叉樹(shù)的轉(zhuǎn)換 基本要求：

1、樹(shù)采用雙親表示法

2、能夠?qū)?shù)轉(zhuǎn)換為二叉樹(shù)

3、對(duì)轉(zhuǎn)換的二叉樹(shù)進(jìn)行算法設(shè)計(jì)統(tǒng)計(jì)人一結(jié)點(diǎn)的孩子數(shù)

4、利用轉(zhuǎn)換的二叉樹(shù)計(jì)算樹(shù)的高度

設(shè)計(jì)等級(jí) B

18、哈希表設(shè)計(jì)

問(wèn)題描述：針對(duì)自己的班集體中的“人名”設(shè)計(jì)一個(gè)哈希表，完成相應(yīng)的建表和查表程序。基本要求

1、人名為中國(guó)姓名的漢語(yǔ)拼音形式

2、待填入哈希表的人名不低于30個(gè)

3、用鏈表法處理沖突

4、完成任意人名的查找并給出查找長(zhǎng)度

設(shè)計(jì)等級(jí) A

19、矩陣應(yīng)用

問(wèn)題描述：完成矩陣的相關(guān)操作

1、創(chuàng)建兩個(gè)普通矩陣完成矩陣的加法和乘法運(yùn)算

2、完成一個(gè)對(duì)稱矩陣的壓縮存儲(chǔ)

3、完成一個(gè)稀疏矩陣的壓縮存儲(chǔ)，并完成矩陣的快速轉(zhuǎn)置

設(shè)計(jì)等級(jí) A 20、圖的遍歷的實(shí)現(xiàn)

問(wèn)題描述：分別創(chuàng)建一個(gè)有相圖和無(wú)向圖完成下面要求 基本要求：

1、進(jìn)行深度優(yōu)先遍歷

2、非遞歸完成深度優(yōu)先遍歷

3、進(jìn)行廣度優(yōu)先遍歷

4、計(jì)算有向圖的入度和出度

5、判斷圖的連通性和是否有回路。

設(shè)計(jì)等級(jí) B

說(shuō)明：每位同學(xué)選擇一題作為自己的課程設(shè)計(jì)題目，其中選擇設(shè)計(jì)等級(jí)為A的同學(xué)，最后成績(jī)不會(huì)超過(guò)“良好”等第

第二篇：2012數(shù)據(jù)結(jié)構(gòu)課程設(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)題我是采取比較笨的辦法在稿紙上寫明白后開(kāi)始進(jìn)行 4

代碼編寫。

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

最后是，前期分析不足開(kāi)始急于寫代碼，中途出現(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ì)開(kāi)發(fā)程序方面有了一定的小經(jīng)驗(yàn)和想法，對(duì)自己以后學(xué)習(xí)其他語(yǔ)言程序設(shè)計(jì)奠定了一定的基礎(chǔ)。

八、指導(dǎo)老師評(píng)語(yǔ)及成績(jī)

附錄：（課程設(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(“請(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->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(“請(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ì)

數(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è)字母），建立哈夫曼樹(shù)；

3)編碼：利用建好的哈夫曼樹(shù)生成哈夫曼編碼；

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)

//建立赫夫曼樹(shù)，進(jìn)行編碼 {

int w,k,j;char c;for(k=1;k<=m;k++){

if(k<=n)

{

printf(“n請(qǐng)輸入權(quán)值和字符(用空格隔開(kāi)): ”);

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]='