本文格式為Word版，下載可任意編輯——《數(shù)據(jù)結(jié)構(gòu)》課程設(shè)計(jì)指導(dǎo)書《數(shù)據(jù)結(jié)構(gòu)》課程設(shè)計(jì)指導(dǎo)書

課程設(shè)計(jì)名稱：指導(dǎo)老師：指導(dǎo)方式：課程設(shè)計(jì)教材數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)09102版服務(wù)課程名稱：數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)周數(shù)：1-2周王中華（wangzh@）集體輔導(dǎo)與個別答疑相結(jié)合陳元春等編著的《實(shí)用數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)》，中國鐵道出版社課程設(shè)計(jì)適用班級：BX0805、BX0806課程設(shè)計(jì)授課單位：上海電機(jī)學(xué)院電子信息學(xué)院計(jì)算機(jī)基礎(chǔ)教學(xué)部及主要參考資料：嚴(yán)蔚敏，吳偉民編著的《數(shù)據(jù)結(jié)構(gòu)》，清華大學(xué)出版社一、課程設(shè)計(jì)教學(xué)目的及基本要求

1．了解并把握數(shù)據(jù)結(jié)構(gòu)與算法的設(shè)計(jì)方法，具備初步的獨(dú)立分析和設(shè)計(jì)能力；2．初步把握軟件開發(fā)過程的問題分析、系統(tǒng)設(shè)計(jì)、程序編碼、測試等基本方法和技能；

3．提高綜合運(yùn)用所學(xué)的理論知識和方法獨(dú)立分析和解決問題的能力；4．訓(xùn)練用系統(tǒng)的觀點(diǎn)和軟件開發(fā)一般規(guī)范進(jìn)行軟件開發(fā)，培養(yǎng)軟件工所應(yīng)具備的科學(xué)的工作方法和作風(fēng)。

5．設(shè)計(jì)的題目要求達(dá)到一定工作量，并具有一定的深度和難度。

6．編寫出課程設(shè)計(jì)報(bào)告，報(bào)告正文不得少于10頁（其中正文文字部分不得少于七頁，代碼不算頁數(shù)）。

二、課程設(shè)計(jì)內(nèi)容及安排

1．問題分析和任務(wù)定義：根據(jù)設(shè)計(jì)題目的要求，充分地分析和理解問題，明確問題要求做什么？（而不是怎么做？）限制條件是什么？

2．規(guī)律設(shè)計(jì)：對問題描述中涉及的操作對象定義相應(yīng)的數(shù)據(jù)類型，并依照以數(shù)據(jù)結(jié)構(gòu)為中心的原則劃分模塊，定義主程序模塊和各抽象數(shù)據(jù)類型。規(guī)律設(shè)計(jì)的結(jié)果應(yīng)寫出每個抽象數(shù)據(jù)類型的定義(包括數(shù)據(jù)結(jié)構(gòu)的描述和每個基本操作的功能說明)，各個主要模塊的算法，并畫出模塊之間的調(diào)用關(guān)系圖；3．詳細(xì)設(shè)計(jì)：定義相應(yīng)的存儲結(jié)構(gòu)并寫出各函數(shù)的偽碼算法。在這個過程中，要綜合考慮系統(tǒng)功能，使得系統(tǒng)結(jié)構(gòu)明了、合理、簡單和易于調(diào)試，抽象數(shù)據(jù)類型的實(shí)現(xiàn)盡可能做到數(shù)據(jù)封裝，基本操作的規(guī)格說明盡可能明確具體。詳細(xì)設(shè)計(jì)的結(jié)果是對數(shù)據(jù)結(jié)構(gòu)和基本操作作出進(jìn)一步的求精，寫出數(shù)據(jù)存儲結(jié)構(gòu)的類型定義，寫出函數(shù)形式的算法框架；

4．程序編碼：把詳細(xì)設(shè)計(jì)的結(jié)果進(jìn)一步求精為程序設(shè)計(jì)語言程序。同時(shí)參與一些注解和斷言，使程序中規(guī)律概念明白；

1

5．程序調(diào)試與測試：采用自底向上，分模塊進(jìn)行，即先調(diào)試低層函數(shù)。能夠熟練把握調(diào)試工具的各種功能，設(shè)計(jì)測試數(shù)據(jù)確定疑點(diǎn)，通過修改程序來證明它或繞過它。調(diào)試正確后，認(rèn)真整理源程序及其解釋，形成格式和風(fēng)格良好的源程序清單和結(jié)果；

6．結(jié)果分析：程序運(yùn)行結(jié)果包括正確的輸入及其輸出結(jié)果和含有錯誤的輸入及其輸出結(jié)果。算法的時(shí)間、空間繁雜性分析。7．編寫課程設(shè)計(jì)報(bào)告

三、設(shè)計(jì)報(bào)告的內(nèi)容

設(shè)計(jì)終止后要寫出課程設(shè)計(jì)報(bào)告，以作為整個課程設(shè)計(jì)評分的書面依據(jù)和存檔材料。設(shè)計(jì)報(bào)告以規(guī)定格式的電子文檔書寫、打印并裝訂，排版及圖、表要明白、工整。內(nèi)容及要求如下：

封面：題目、班級、學(xué)號、姓名、指導(dǎo)教師和完成日期。正文包括以下7個內(nèi)容：

1．需求分析：以無歧義的陳述說明程序設(shè)計(jì)的任務(wù)，強(qiáng)調(diào)的是程序要做什么？并明確規(guī)定：

(1)輸入的形式和輸入值的范圍；(2)輸出的形式；

(3)程序所能達(dá)到的功能；

(4)測試數(shù)據(jù)：包括正確的輸入及其輸出結(jié)果和含有錯誤的輸入及其輸出結(jié)

果。

2．概要設(shè)計(jì)：說明本程序中用到的所有數(shù)據(jù)類型的定義、主程序的流程以及各程序模塊之間的層次(調(diào)用)關(guān)系。

3．詳細(xì)設(shè)計(jì)：實(shí)現(xiàn)概要設(shè)計(jì)中定義的所有數(shù)據(jù)類型，對每個操作只需要寫出偽碼算法；對主程序和其他模塊也都需要寫出偽碼算法(偽碼算法達(dá)到的詳細(xì)程度建議為：依照偽碼算法可以在計(jì)算機(jī)鍵盤直接輸入高級程序設(shè)計(jì)語言程序)；可采用流程圖N–S圖或PAD圖進(jìn)行描述，畫出函數(shù)和過程的調(diào)用關(guān)系圖。

4．調(diào)試分析內(nèi)容包括：

(1)調(diào)試過程中遇到的問題是如何解決的以及對設(shè)計(jì)與實(shí)現(xiàn)的回想探討和

分析；

(2)算法的時(shí)間繁雜度和空間繁雜度的分析和改進(jìn)設(shè)想；(3)經(jīng)驗(yàn)和體會等。

5．用戶使用說明：說明如何使用你編寫的程序，詳細(xì)列出每一步的操作步驟。6．測試結(jié)果：列出你的測試結(jié)果，包括輸入和輸出。這里的測試數(shù)據(jù)應(yīng)當(dāng)完整和嚴(yán)格，最好多于需求分析中所列。7．注意：該AOE網(wǎng)為僅有一個起始頂點(diǎn)且僅有一個終止頂點(diǎn)的有向無環(huán)網(wǎng)。提醒：該AOE網(wǎng)的弧代表活動，頂點(diǎn)代表事件。事件發(fā)生，以該頂點(diǎn)為弧尾的所

有活動即可開始；只有指向某頂點(diǎn)的所有?。ɑ顒樱┒纪瓿?，該頂點(diǎn)代表的事件才會發(fā)生。每個事件都有最早發(fā)生時(shí)刻和最晚發(fā)生時(shí)刻；每個活動都有相應(yīng)的最早開始時(shí)間、最晚開始時(shí)間、最早完成時(shí)間和最晚完成時(shí)間?；〉母蛔銜r(shí)間即為該弧在不影響整個工程工期的前提下允許其拖延的最大時(shí)間，富足時(shí)間為零的所有弧即構(gòu)成關(guān)鍵路徑。

3．設(shè)計(jì)要求

?利用C、C++、C#或Java等語言實(shí)現(xiàn)該程序，程序應(yīng)上機(jī)調(diào)試通過并運(yùn)行正確。?假使程序采用C#或Java等語言實(shí)現(xiàn)，則酌情加分；假使主要函數(shù)采用動態(tài)鏈接庫形式實(shí)現(xiàn)，則酌情加分。

?該網(wǎng)的存儲方法要求采用十字鏈表存儲法。

?輸入數(shù)據(jù)，構(gòu)造AOE網(wǎng)的十字鏈表存儲結(jié)構(gòu)，求其關(guān)鍵路徑并輸出。?撰寫課程設(shè)計(jì)報(bào)告，報(bào)告格式按規(guī)范設(shè)置。

?課程設(shè)計(jì)報(bào)告中應(yīng)給出算法過程的具體分析、程序數(shù)據(jù)所采用的存儲結(jié)構(gòu)圖、程序流程圖、測試數(shù)據(jù)及其結(jié)果分析、算法的時(shí)間和空間繁雜度等，另外還可以提出算法的進(jìn)一步改進(jìn)方法。課題A2：求有向圖的極大強(qiáng)連通分量并輸出

1．設(shè)計(jì)目的

?了解圖的非線性特點(diǎn)、遞歸特點(diǎn)和動態(tài)特性。?把握圖或網(wǎng)的十字鏈表存儲結(jié)構(gòu)及其遍歷方法。?把握有向圖極大強(qiáng)連通分量的求法。2．主要內(nèi)容

（1）輸入有向圖的頂點(diǎn)總數(shù)和所有頂點(diǎn)標(biāo)志（每個頂點(diǎn)均用一個大寫英文字母

作為標(biāo)志）；

（2）輸入圖的弧數(shù)，并依次輸入各條弧的信息，建立該圖的十字鏈表存儲結(jié)構(gòu)；（3）輸入一個頂點(diǎn)，求出圖中該頂點(diǎn)所在的極大強(qiáng)連通分量，并輸出。

圖A2-1有向網(wǎng)

將圖A2-1存入十字鏈表中，若輸入A，則輸出頂點(diǎn)A所在的極大強(qiáng)連通分

6

量A,B,C；若輸入F，則輸出F,G。3．設(shè)計(jì)要求

?利用C、C++、C#或Java等語言實(shí)現(xiàn)該程序，程序應(yīng)上機(jī)調(diào)試通過并運(yùn)行正確。?假使程序采用C#或Java等語言實(shí)現(xiàn)，則酌情加分；假使主要函數(shù)采用動態(tài)鏈接庫形式實(shí)現(xiàn)，則酌情加分。

?該圖要求采用鄰接表或十字鏈表作為存儲結(jié)構(gòu)。?撰寫課程設(shè)計(jì)報(bào)告，報(bào)告格式按規(guī)范設(shè)置。

?課程設(shè)計(jì)報(bào)告中應(yīng)給出算法過程的具體分析、程序數(shù)據(jù)所采用的存儲結(jié)構(gòu)圖、程序流程圖、測試數(shù)據(jù)及其結(jié)果分析、算法的時(shí)間和空間繁雜度等，另外還可以提出算法的進(jìn)一步改進(jìn)方法。課題A3：哈希查找的實(shí)現(xiàn)與分析1．設(shè)計(jì)目的

?把握哈希函數(shù)的構(gòu)造原則及哈希表的生成方法，并能在解決實(shí)際問題時(shí)靈活應(yīng)用。

?把握哈希查找的基本過程及其適用場合。

?穩(wěn)定在散列查找時(shí)解決沖突的方法及各種方法的特點(diǎn)。2．主要內(nèi)容

（1）以某班所有同學(xué)的學(xué)號為關(guān)鍵字構(gòu)造一個適合的哈希函數(shù)。

（2）所有同學(xué)信息均從文本文件Hash.txt中讀取（文本文件中的各字段用跳格

鍵分隔）后插入到哈希表。（3）用拉鏈法解決沖突。

圖Hash表中需要從文件讀取的數(shù)據(jù)

7

3．設(shè)計(jì)要求

?利用C、C++、C#或Java等語言實(shí)現(xiàn)該程序，程序應(yīng)上機(jī)調(diào)試通過并運(yùn)行正確。?假使程序采用C#或Java等語言實(shí)現(xiàn)，則酌情加分；假使主要函數(shù)采用動態(tài)鏈接庫形式實(shí)現(xiàn)，則酌情加分。

?所有數(shù)據(jù)從文本文件Hash.txt中讀取。

?根據(jù)實(shí)際問題自行構(gòu)造合理的哈希函數(shù)，要求采用拉鏈法解決Hash表的沖突。?撰寫課程設(shè)計(jì)報(bào)告，報(bào)告格式按規(guī)范設(shè)置。

?課程設(shè)計(jì)報(bào)告中應(yīng)給出算法過程的具體分析、程序數(shù)據(jù)所采用的存儲結(jié)構(gòu)圖、程序流程圖、測試數(shù)據(jù)及其結(jié)果分析、算法的時(shí)間和空間繁雜度等，另外還可以提出算法的進(jìn)一步改進(jìn)方法。

課題A4：Prim或Kruskal算法求最小生成樹[基于鄰接表存儲結(jié)構(gòu)]1．設(shè)計(jì)目的

?把握無向圖的鄰接表存儲結(jié)構(gòu)；

?把握基于鄰接表存儲結(jié)構(gòu)無向圖的遍歷方法。

?進(jìn)一步把握利用Prim或Kruskal算法求解最小生成樹的過程。2．主要內(nèi)容

（1）輸入給定無向網(wǎng)的頂點(diǎn)總數(shù)和所有頂點(diǎn)標(biāo)志（每個頂點(diǎn)均用一個大寫英文

字母作為標(biāo)志）；

（2）輸入圖中邊的總數(shù)，并利用循環(huán)依次輸入各條邊的端點(diǎn)標(biāo)志及權(quán)值，建立

該無向網(wǎng)的鄰接表存儲結(jié)構(gòu)；

（3）用Prim或者Kruskal算法求該無向網(wǎng)最小生成樹。

圖A4-1

3．設(shè)計(jì)要求

?利用C、C++、C#或Java等語言實(shí)現(xiàn)該程序，程序應(yīng)上機(jī)調(diào)試通過并運(yùn)行正確。?假使程序采用C#或Java等語言實(shí)現(xiàn)，則酌情加分；假使主要函數(shù)采用動態(tài)鏈

8

接庫形式實(shí)現(xiàn)，則酌情加分。

?假使有兩個同學(xué)同時(shí)完成該課題，要求分別采用Prim和Kruskal算法求得該無向網(wǎng)的最小生成樹。

?按選取邊的順序輸出最小生成樹的各條邊。?撰寫課程設(shè)計(jì)報(bào)告，報(bào)告格式按規(guī)范設(shè)置。

?課程設(shè)計(jì)報(bào)告中應(yīng)給出算法過程的具體分析、程序數(shù)據(jù)所采用的存儲結(jié)構(gòu)圖、程序流程圖、測試數(shù)據(jù)及其結(jié)果分析、算法的時(shí)間和空間繁雜度等，另外還可以提出算法的進(jìn)一步改進(jìn)方法。課題A5：Dijkstra算法求最短路徑1．設(shè)計(jì)目的

?復(fù)習(xí)圖的存儲結(jié)構(gòu)和遍歷方法。

?進(jìn)一步把握圖的非線性特點(diǎn)、遞歸特點(diǎn)和動態(tài)特性。?把握并實(shí)現(xiàn)Dijkstra算法。2．主要內(nèi)容

（1）輸入圖的頂點(diǎn)總數(shù)和所有頂點(diǎn)標(biāo)志（每個頂點(diǎn)用一個大寫英文字母作為標(biāo)

志）；

（2）輸入圖的各條邊，建立該圖的鄰接表或鄰接矩陣存儲結(jié)構(gòu)；（3）輸入圖中的任意一個頂點(diǎn)的標(biāo)志；

（4）利用Dijkstra算法求出該頂點(diǎn)到其它所有頂點(diǎn)的最短路徑和最短路徑長

度，并輸出。

圖A5-1

3．設(shè)計(jì)要求

?利用C、C++、C#或Java等語言實(shí)現(xiàn)該程序，程序應(yīng)上機(jī)調(diào)試通過并運(yùn)行正確。?假使程序采用C#或Java等語言實(shí)現(xiàn)，則酌情加分；假使主要函數(shù)采用動態(tài)鏈接庫形式實(shí)現(xiàn)，則酌情加分。

?撰寫課程設(shè)計(jì)報(bào)告，報(bào)告格式按規(guī)范設(shè)置。

?課程設(shè)計(jì)報(bào)告中應(yīng)給出算法過程的具體分析、程序數(shù)據(jù)所采用的存儲結(jié)構(gòu)圖、程序流程圖、測試數(shù)據(jù)及其結(jié)果分析、算法的時(shí)間和空間繁雜度等，另外還

9

可以提出算法的進(jìn)一步改進(jìn)方法。課題A6：拼寫檢查器[AVL樹的應(yīng)用]1．設(shè)計(jì)目的

?把握平衡二叉樹（AVL樹）的存儲結(jié)構(gòu)，構(gòu)造方法和查找過程。?進(jìn)一步把握應(yīng)用平衡二叉樹解決實(shí)際問題。2．主要內(nèi)容

現(xiàn)代字處理器最有用的特點(diǎn)之一就是拼寫檢查，就是在文檔中掃描可能的拼寫錯誤。這里說的“可能的〞拼寫錯誤是由于文檔中可能包含合法但不在字典中的單詞。例如，在鍵入文章中使用的單詞“iterator〞和“postorder〞時(shí)，這些單詞就被看作是字處理器所找不到的。

完整的問題是：給出directionaryFile中的一個字典，以及由用戶提供名稱的文件中的一個文檔，輸出在文檔中而在字典里找不到的所有單詞。下面進(jìn)行一些簡單化的假設(shè)：

（1）字典只有小寫字母組成。

（2）文檔中的每個單詞只由字母組成——其中可能有一些或全部是大寫的。（3）文檔中的每個單詞后面跟著0個或更多的標(biāo)點(diǎn)符號，隨后是任意數(shù)量的空

白和行尾標(biāo)志。

（4）字典文件中的單詞是依照字典序法排列的并且將被裝入內(nèi)存，文檔文件中

的單詞不必依照字典序法排列。3．設(shè)計(jì)要求

?利用C、C++、C#或Java等語言實(shí)現(xiàn)該程序，程序應(yīng)上機(jī)調(diào)試通過并運(yùn)行正確。?假使程序采用C#或Java等語言實(shí)現(xiàn)，則酌情加分；假使主要函數(shù)采用動態(tài)鏈接庫形式實(shí)現(xiàn)，則酌情加分。

?從directionaryFile文件中讀入字典中的各個單詞構(gòu)造二叉排序樹。?輸入檢查文檔文件名，輸出檢查文檔中在字典中未查找到的單詞。?撰寫課程設(shè)計(jì)報(bào)告，報(bào)告格式按規(guī)范設(shè)置。

?課程設(shè)計(jì)報(bào)告中應(yīng)給出算法過程的具體分析、程序數(shù)據(jù)所采用的存儲結(jié)構(gòu)圖、程序流程圖、測試數(shù)據(jù)及其結(jié)果分析、算法的時(shí)間和空間繁雜度等，另外還可以提出算法的進(jìn)一步改進(jìn)方法。

課題A7：中綴表達(dá)式轉(zhuǎn)后綴表達(dá)式，并利用后綴表達(dá)式求值[運(yùn)算對象為多位數(shù)]1．設(shè)計(jì)目的

?把握?！昂筮M(jìn)先出〞的特點(diǎn)。

?把握棧的典型應(yīng)用——中綴表達(dá)式轉(zhuǎn)后綴表達(dá)式、后綴表達(dá)式求值。2．主要內(nèi)容

中綴表達(dá)式轉(zhuǎn)換為后綴表達(dá)式的步驟：

10

（1）定義一個運(yùn)算符棧，輸入一個中綴表達(dá)式（運(yùn)算對象為整數(shù)，含有+、-、*、

/、%及括號等運(yùn)算符）。

（2）假使讀入的是運(yùn)算對象，則直接輸出到后綴表達(dá)式。

（3）假使讀入的是運(yùn)算符，則比較該運(yùn)算符和棧頂元素的優(yōu)先級；若該運(yùn)算符

優(yōu)先級高于棧頂元素的優(yōu)先級，則直接進(jìn)棧；若該運(yùn)算符優(yōu)先級低于或等于棧頂元素的優(yōu)先級，則將棧中高于或等于該運(yùn)算符優(yōu)先級的元素先出棧并輸出到后綴表達(dá)式，然后再將該運(yùn)算符進(jìn)棧。

（4）假使讀入的是開括號“（〞則直接進(jìn)棧；假使讀入的是閉括號“）〞則一直

出棧并輸出到后綴表達(dá)式，直到遇到一個開括號“（〞為止，開括號“（〞和閉括號“）〞均不輸入到后綴表達(dá)式。

（5）重復(fù)（2）（3）（4）步，直到讀入中綴表達(dá)式終止符，然后將棧中剩余的所

有運(yùn)算符依次出棧并輸出到后綴表達(dá)式。后綴表達(dá)式求值的步驟：

（1）定義一個double型的運(yùn)算對象棧，將中綴表達(dá)式轉(zhuǎn)換得到的后綴表達(dá)式從

左向右依次讀入。

（2）假使讀入的是運(yùn)算對象，直接進(jìn)入運(yùn)算對象棧。

（3）假使讀入的是運(yùn)算符，馬上從運(yùn)算對象棧中彈出兩個運(yùn)算對象，計(jì)算兩個

運(yùn)算對象運(yùn)算后的值（先彈出的放后面，后彈出的放前面），并將計(jì)算結(jié)果存回運(yùn)算對象棧。

（4）重復(fù)（2）（3）步，直到后綴表達(dá)式終止，最終棧中保存的那個數(shù)即為該后

綴表達(dá)式的計(jì)算結(jié)果

（5）檢驗(yàn)程序運(yùn)行結(jié)果的正確性。

假設(shè)輸入中綴表達(dá)式為：(123?32)/5*2?15*18/(2?4)/15?7

32，?，5，/，2，*，15，18，*，2，4，?，/，15，/，?，7，?轉(zhuǎn)換成的后綴表達(dá)式為：123，后綴表達(dá)式求得的值為：523．設(shè)計(jì)要求

?利用C、C++、C#或Java等語言實(shí)現(xiàn)該程序，程序應(yīng)上機(jī)調(diào)試通過并運(yùn)行正確。?假使程序采用C#或Java等語言實(shí)現(xiàn)，則酌情加分；假使主要函數(shù)采用動態(tài)鏈接庫形式實(shí)現(xiàn)，則酌情加分。?所有運(yùn)算對象為多位整數(shù)。?能夠識別除數(shù)為零的錯誤。

?撰寫課程設(shè)計(jì)報(bào)告，報(bào)告格式按規(guī)范設(shè)置。

?課程設(shè)計(jì)報(bào)告中應(yīng)給出算法過程的具體分析、程序數(shù)據(jù)所采用的存儲結(jié)構(gòu)圖、程序流程圖、測試數(shù)據(jù)及其結(jié)果分析、算法的時(shí)間和空間繁雜度等，另外還可以提出算法的進(jìn)一步改進(jìn)方法。

11

課題A8：哈夫曼編碼器1．設(shè)計(jì)目的

?復(fù)習(xí)二叉樹的存儲結(jié)構(gòu)和遍歷方法。

?把握哈夫曼樹的構(gòu)造過程和哈夫曼編碼的求解方法。?把握文件的基本讀寫方法。2．主要內(nèi)容

（1）從權(quán)值文件weight.txt中讀取權(quán)值數(shù)據(jù)，生成一棵哈夫曼樹。（2）存儲哈夫曼樹采用靜態(tài)鏈表或二叉鏈表。

若采用靜態(tài)鏈表，其數(shù)據(jù)類型為：

typedefstruct//定義結(jié)構(gòu)體

{intweight;//定義一個整型權(quán)值變量intlchild,rchild,parent;//定義左、右孩子及雙親指針}HTNode;

typedefHTNodeHFMT[MAXLEN];//是向量類型的

（3）根據(jù)哈夫曼樹的求其對應(yīng)的哈夫曼編碼，并將編碼寫入結(jié)果文件code.txt。

圖A8-1給定的權(quán)值文件

圖A8-2生成的哈夫曼編碼文件

提醒：最終生成的哈夫曼編碼文件code.txt可能與圖A8-2不一樣（由于生成的哈夫曼樹形態(tài)并不是唯一的），但是所有哈夫曼樹的WPL（帶權(quán)路徑長度）確定是一樣的。3．設(shè)計(jì)要求

?利用C、C++、C#或Java等語言實(shí)現(xiàn)該程序，程序應(yīng)上機(jī)調(diào)試通過并運(yùn)行正確。

12

?假使程序采用C#或Java等語言實(shí)現(xiàn)，則酌情加分；假使主要函數(shù)采用動態(tài)鏈接庫形式實(shí)現(xiàn)，則酌情加分。

?從文件讀入一批權(quán)值，建立一棵哈夫曼樹，求其對應(yīng)的哈夫曼編碼，并將編碼寫入編碼文件。

?撰寫課程設(shè)計(jì)報(bào)告，報(bào)告格式按規(guī)范設(shè)置。

?課程設(shè)計(jì)報(bào)告中應(yīng)給出算法過程的具體分析、程序數(shù)據(jù)所采用的存儲結(jié)構(gòu)圖、程序流程圖、測試數(shù)據(jù)及其結(jié)果分析、算法的時(shí)間和空間繁雜度等，另外還可以提出算法的進(jìn)一步改進(jìn)方法。B類題目[共9題]

課題B1：文件記錄讀取并排序1．設(shè)計(jì)目的

?把握常用排序算法的過程及特點(diǎn)。?把握文件讀寫的基本方法。2．主要內(nèi)容

編寫程序，將Info.txt文件中的數(shù)據(jù)記錄讀出，并按學(xué)分排序后寫入Result.txt文件。

Info.txt文件中的內(nèi)容如下圖所示。

圖B1-1待排序的原始記錄文件

3．設(shè)計(jì)要求

?利用C、C++、C#或Java等語言實(shí)現(xiàn)該程序，程序應(yīng)上機(jī)調(diào)試通過并運(yùn)行正確。?假使程序采用C#或Java等語言實(shí)現(xiàn)，則酌情加分；假使主要函數(shù)采用動態(tài)鏈接庫形式實(shí)現(xiàn)，則酌情加分。

?排序方法要求采用快速排序、堆排序、希爾排序、歸并排序中的一種，假使

13

采用希爾排序，則每趟的增量值依次為（5，3，1）。

?假使有多個同學(xué)同時(shí)完成該課題，要求每個同學(xué)均采用不同的排序方法。?給出具體的算法分析，包括排序算法的穩(wěn)定性、各種不同排序算法的適用條件及性能分析、時(shí)間繁雜度和空間繁雜度等。?撰寫課程設(shè)計(jì)報(bào)告，報(bào)告格式按規(guī)范設(shè)置。課題B2：有向無環(huán)圖的判定及拓?fù)渑判?．設(shè)計(jì)目的

?把握圖的存儲結(jié)構(gòu)和圖的兩種遍歷方法。?把握有向無環(huán)圖的判定方法以及拓?fù)渑判蛩惴ā?．主要內(nèi)容

（1）輸入給定有向圖的頂點(diǎn)總數(shù)和所有頂點(diǎn)標(biāo)志（每個頂點(diǎn)均用一個大寫英文

字母作為標(biāo)志）；

（2）輸入圖中弧的總數(shù)，并利用循環(huán)依次輸入各條弧，建立該有向圖的鄰接表

存儲結(jié)構(gòu)；

（3）從圖中選取一個入度為零的頂點(diǎn)（假使存在多個頂點(diǎn)入度為零，則任選其

中之一即可），標(biāo)記該頂點(diǎn)并刪除以該頂點(diǎn)為弧尾的所有弧，刪除每條弧的同時(shí)更新相應(yīng)弧頭的入度值；

（4）不斷重復(fù)步驟（3），直到找不到入度為零的頂點(diǎn)或者已經(jīng)刪除所有弧為止；（5）假使還有頂點(diǎn)尚未標(biāo)記（尚未標(biāo)記頂點(diǎn)的入度確定均不為零），或者還有弧

結(jié)點(diǎn)未被刪除，則可判定該圖中存在環(huán)；假使可以將圖中所有頂點(diǎn)全部標(biāo)記，則標(biāo)記頂點(diǎn)的順序即為該有向無環(huán)圖的拓?fù)湫蛄校?/p>

（6）給出該圖有無環(huán)的判定結(jié)果。若為有向無環(huán)圖，則給出其拓?fù)湫蛄?；若圖

中存在環(huán)，則列出環(huán)中的所有頂點(diǎn)；3．設(shè)計(jì)要求

?利用C、C++、C#或Java等語言實(shí)現(xiàn)該程序，程序應(yīng)上機(jī)調(diào)試通過并運(yùn)行正確。?假使程序采用C#或Java等語言實(shí)現(xiàn)，則酌情加分；假使主要函數(shù)采用動態(tài)鏈接庫形式實(shí)現(xiàn)，則酌情加分。

?測試時(shí)分別輸入存在環(huán)和不存在環(huán)的兩個圖，輸出是否存在環(huán)的判定結(jié)果，并給出相應(yīng)的拓?fù)湫蛄谢蛘吡谐霏h(huán)中的所有頂點(diǎn)。?撰寫課程設(shè)計(jì)報(bào)告，報(bào)告格式按規(guī)范設(shè)置。

?課程設(shè)計(jì)報(bào)告中應(yīng)給出算法過程的具體分析、程序數(shù)據(jù)所采用的存儲結(jié)構(gòu)圖、程序流程圖、測試數(shù)據(jù)及其結(jié)果分析、算法的時(shí)間和空間繁雜度等，另外還可以提出算法的進(jìn)一步改進(jìn)方法。

課題B3：浮點(diǎn)數(shù)的IEEE754標(biāo)準(zhǔn)格式轉(zhuǎn)換及輸出1．設(shè)計(jì)目的

14

?把握float型浮點(diǎn)數(shù)的存儲結(jié)構(gòu)和特點(diǎn)。?把握C系列語言中的位運(yùn)算和串操作方法。?了解IEEE754標(biāo)準(zhǔn)。2．主要內(nèi)容

（1）輸入一個十進(jìn)制形式浮點(diǎn)數(shù)，將其IEEE754結(jié)構(gòu)的存儲形式以十六進(jìn)制形

式輸出。

（2）以8位十六進(jìn)制數(shù)形式給定一個IEEE754結(jié)構(gòu)的浮點(diǎn)數(shù)，將其代表的十進(jìn)

制數(shù)輸出。

（3）驗(yàn)證例子程序如IEEE754.exe所示。

圖IEEE754標(biāo)準(zhǔn)float格式

3．設(shè)計(jì)要求

?利用C、C++、C#或Java等語言實(shí)現(xiàn)該程序，程序應(yīng)上機(jī)調(diào)試通過并運(yùn)行正確。?假使程序采用C#或Java等語言實(shí)現(xiàn)，則酌情加分；假使主要函數(shù)采用動態(tài)鏈接庫形式實(shí)現(xiàn)，則酌情加分。

?輸入一個八位的十六進(jìn)制數(shù)，輸出該數(shù)按IEEE754標(biāo)準(zhǔn)所對應(yīng)的浮點(diǎn)數(shù)；輸入一個十進(jìn)制形式的浮點(diǎn)數(shù)，計(jì)算出該浮點(diǎn)數(shù)按IEEE754標(biāo)準(zhǔn)所對應(yīng)32位存儲形式，將該存儲形式以一個八位的十六進(jìn)制數(shù)形式輸出。?撰寫課程設(shè)計(jì)報(bào)告，報(bào)告格式按規(guī)范設(shè)置。

?課程設(shè)計(jì)報(bào)告中應(yīng)給出算法過程的具體分析、程序數(shù)據(jù)所采用的存儲結(jié)構(gòu)圖、程序流程圖、測試數(shù)據(jù)及其結(jié)果分析、算法的時(shí)間和空間繁雜度等，另外還可以提出算法的進(jìn)一步改進(jìn)方法。課題B4：哈夫曼樹和哈夫曼編碼1．設(shè)計(jì)目的

?復(fù)習(xí)二叉樹的存儲結(jié)構(gòu)和遍歷方法。

?把握二叉樹的非線性特點(diǎn)、遞歸特點(diǎn)和動態(tài)特性。?把握哈夫曼樹的構(gòu)造過程和哈夫曼編碼的求解方法。2．主要內(nèi)容（1）生成哈夫曼樹。

（2）哈夫曼樹采用靜態(tài)鏈表或二叉鏈表存儲結(jié)構(gòu)。

若采用靜態(tài)鏈表，其數(shù)據(jù)類型為：

15

typedefstruct//定義結(jié)構(gòu)體

{intweight;//定義一個整型權(quán)值變量intlchild,rchild,parent;//定義左、右孩子及雙親指針}HTNode;

typedefHTNodeHFMT[MAXLEN];//是向量類型的（3）求哈夫曼樹對應(yīng)的哈夫曼編碼。3．設(shè)計(jì)要求

?利用C、C++、C#或Java等語言實(shí)現(xiàn)該程序，程序應(yīng)上機(jī)調(diào)試通過并運(yùn)行正確。?假使程序采用C#或Java等語言實(shí)現(xiàn)，則酌情加分；假使主要函數(shù)采用動態(tài)鏈接庫形式實(shí)現(xiàn)，則酌情加分。

?輸入一批權(quán)值，建立哈夫曼樹，并求相應(yīng)的哈夫曼編碼。?撰寫課程設(shè)計(jì)報(bào)告，報(bào)告格式按規(guī)范設(shè)置。

?課程設(shè)計(jì)報(bào)告中應(yīng)給出算法過程的具體分析、程序數(shù)據(jù)所采用的存儲結(jié)構(gòu)圖、程序流程圖、測試數(shù)據(jù)及其結(jié)果分析、算法的時(shí)間和空間繁雜度等，另外還可以提出算法的進(jìn)一步改進(jìn)方法。課題B5：大整數(shù)運(yùn)算1．設(shè)計(jì)目的

?了解串的一般操作方法和存儲結(jié)構(gòu)。?把握數(shù)字字符串和其對應(yīng)數(shù)值的轉(zhuǎn)換技巧。?分析大整數(shù)運(yùn)算的特點(diǎn)。2．主要內(nèi)容

任意輸出兩個大整數(shù)（至少18位以上），求它們加、減、乘、除的結(jié)果。如12345678901234567890+1234567890=1234567890246913578012345678901234567890-1234567890=12345678900000000000

12345678901234567890*1234567890=1524157875171467887501905210012345678901234567890/1234567890=100000000013．設(shè)計(jì)要求

?利用C、C++、C#或Java等語言實(shí)現(xiàn)該程序，程序應(yīng)上機(jī)調(diào)試通過并運(yùn)行正確。?假使程序采用C#或Java等語言實(shí)現(xiàn)，則酌情加分；假使主要函數(shù)采用動態(tài)鏈接庫形式實(shí)現(xiàn)，則酌情加分。

?輸入兩個大整數(shù)，通過菜單項(xiàng)選擇擇項(xiàng)分別求其加減乘除運(yùn)算的結(jié)果。?撰寫課程設(shè)計(jì)報(bào)告，報(bào)告格式按規(guī)范設(shè)置。

?課程設(shè)計(jì)報(bào)告中應(yīng)給出算法過程的具體分析、程序數(shù)據(jù)所采用的存儲結(jié)構(gòu)圖、程序流程圖、測試數(shù)據(jù)及其結(jié)果分析、算法的時(shí)間和空間繁雜度等，另外還可以提出算法的進(jìn)一步改進(jìn)方法。

16

課題B6：平衡二叉樹的構(gòu)造及輸出1．設(shè)計(jì)目的

?復(fù)習(xí)二叉樹的三叉鏈表存儲結(jié)構(gòu)和遍歷方法。?把握二叉排序樹的特點(diǎn)和生成方法。

?把握平衡二叉樹四種不平衡形態(tài)的判定和旋轉(zhuǎn)為平衡的方法。2．主要內(nèi)容算法步驟：

（1）輸入結(jié)點(diǎn)數(shù)據(jù)，構(gòu)造二叉樹的結(jié)點(diǎn)，按二叉排序樹的規(guī)則插入該結(jié)點(diǎn)到三

叉鏈表中；

（2）從插入的新結(jié)點(diǎn)開始，依次尋覓其雙親，并檢查其雙親的平衡因子是否屬

于[-1,1]區(qū)間，直到樹根節(jié)點(diǎn)；假使始終未發(fā)現(xiàn)不平衡結(jié)點(diǎn)，則可以斷定插入該結(jié)點(diǎn)后的平衡二叉樹依舊保持平衡，跳轉(zhuǎn)到步驟（1）繼續(xù)插入下一個結(jié)點(diǎn)；

（3）在步驟（2）中一旦發(fā)現(xiàn)某雙親的平衡因子不屬于[-1,1]區(qū)間，則可以斷定

插入新結(jié)點(diǎn)后的二叉樹已不再平衡，該雙親結(jié)點(diǎn)即為離插入點(diǎn)最近的不平衡結(jié)點(diǎn)；

（4）根據(jù)該不平衡結(jié)點(diǎn)左右孩子及插入新結(jié)點(diǎn)的值，即可判定出該二叉樹的不

平衡形態(tài)（共有LL型、LR型、RR型、RL型四種），然后判定得到的不平衡形態(tài)調(diào)用不同的旋轉(zhuǎn)函數(shù)即可將其重新調(diào)整為平衡二叉樹；

（5）重復(fù)步驟（1）（2）（3）（4），直到所有結(jié)點(diǎn)都插入到該平衡二叉樹中為止；（6）輸出該二叉樹的前序（或者后序）序列和中序序列，手工恢復(fù)出該二叉樹，

檢驗(yàn)其是否為平衡二叉樹；并驗(yàn)證其中序序列的有序性。3．設(shè)計(jì)要求

?利用C、C++、C#或Java等語言實(shí)現(xiàn)該程序，程序應(yīng)上機(jī)調(diào)試通過并運(yùn)行正確。?假使程序采用C#或Java等語言實(shí)現(xiàn)，則酌情加分；假使主要函數(shù)采用動態(tài)鏈接庫形式實(shí)現(xiàn)，則酌情加分。?分析平衡二叉樹的查找效率。

?撰寫課程設(shè)計(jì)報(bào)告，報(bào)告格式按規(guī)范設(shè)置。

?課程設(shè)計(jì)報(bào)告中應(yīng)給出算法過程的具體分析、程序數(shù)據(jù)所采用的存儲結(jié)構(gòu)圖、程序流程圖、測試數(shù)據(jù)及其結(jié)果分析、算法的時(shí)間和空間繁雜度等，另外還可以提出算法的進(jìn)一步改進(jìn)方法。課題B7：稀疏矩陣的運(yùn)算1．設(shè)計(jì)目的

?把握稀疏矩陣的特點(diǎn)及其存儲形式(每個非零元素用一個三元組結(jié)點(diǎn)形式存儲，為零的元素隱含表示不用存儲)。

17

?把握稀疏矩陣的順序存儲及鏈?zhǔn)酱鎯Ψ椒ā?/p>

?把握稀疏矩陣的簡單運(yùn)算（轉(zhuǎn)置、加、減、乘、除/求逆）。2．主要內(nèi)容

（1）采用單鏈表形式存儲稀疏矩陣中各個非零元素的值，其中單鏈表中的結(jié)點(diǎn)

數(shù)據(jù)類型定義如下：typedefstruct_node{introw;//行號intcol;//列號

intweight;//矩陣中的非零元素值struct_node*next;}Node;

（2）輸入二維矩陣A、B、C，分別進(jìn)行矩陣的加減乘除操作。

?01??10030??900?30???????A?C??00?A??02023?B??73001?

?00??00500??00000?????????31????0?2?C??00?

??0??1?01????100000???80060?????A?B??75005?A?B???7?1003?

?00500??00500?????B?1???????????建立的單鏈表存儲結(jié)構(gòu)如下圖所示：

矩陣A轉(zhuǎn)置后的單鏈表存儲結(jié)構(gòu)如下圖所示：

矩陣A和B相加之和矩陣的單鏈表存儲結(jié)構(gòu)如下圖所示：

18

矩陣A和B相減之差矩陣的單鏈表存儲結(jié)構(gòu)如下圖所示：

矩陣A和C相乘之積矩陣的單鏈表存儲結(jié)構(gòu)如下圖所示：

矩陣B求逆之后的單鏈表存儲結(jié)構(gòu)略。

（3）將矩陣的轉(zhuǎn)置、加、減、乘、求逆分別用函數(shù)實(shí)現(xiàn)，在主函數(shù)中分別調(diào)用

以上函數(shù)進(jìn)行驗(yàn)證。3．設(shè)計(jì)要求

?利用C、C++、C#或Java等語言實(shí)現(xiàn)該程序，程序應(yīng)上機(jī)調(diào)試通過并運(yùn)行正確。?假使程序采用C#或Java等語言實(shí)現(xiàn)，則酌情加分；假使主要函數(shù)采用動態(tài)鏈接庫形式實(shí)現(xiàn)，則酌情加分。

?輸入相應(yīng)矩陣，通過菜單項(xiàng)選擇項(xiàng)得到矩陣間的運(yùn)算結(jié)果，比較程序運(yùn)行結(jié)果和手工計(jì)算結(jié)果是否一致；假使兩個矩陣不能進(jìn)行某種運(yùn)算，需給出相應(yīng)提醒。?轉(zhuǎn)置、加、減、乘等功能為必做，矩陣相除/求逆的功能為選做。?撰寫課程設(shè)計(jì)報(bào)告，報(bào)告格式按規(guī)范設(shè)置。

?課程設(shè)計(jì)報(bào)告中應(yīng)給出算法過程的具體分析、程序數(shù)據(jù)所采用的存儲結(jié)構(gòu)圖、程序流程圖、測試數(shù)據(jù)及其結(jié)果分析、算法的時(shí)間和空間繁雜度等，另外還可以提出算法的進(jìn)一步改進(jìn)方法。

課題B8：中國象棋中馬的遍歷問題（棧的應(yīng)用）1．設(shè)計(jì)目的

?練習(xí)棧在實(shí)際問題中的使用方法，把握棧的本質(zhì)。?把握求解問題時(shí)使用的回溯策略。

?比較遞歸和迭代函數(shù)的時(shí)間和空間代價(jià)，以及它們的難易程度。?總結(jié)適合用遞歸或迭代解決問題的特點(diǎn)。2．主要內(nèi)容

編寫程序?qū)崿F(xiàn)馬對棋盤方格的遍歷。一個棋盤有八行八列共64個方格，輸入馬的起始方格位置，從起始方格出發(fā)，一個馬的移動必需跨越兩行一列或是兩列一行。設(shè)起始方格的次序?yàn)?，馬跳過的下一個方格的次序是上一個方格的次序加1。馬必需經(jīng)過每個方格且僅經(jīng)過一次，并且馬的移動不能超越棋盤邊界，

19

求出馬經(jīng)過這64個方格的次序。

例如，下圖顯示了坐標(biāo)（5，3）位置上馬的所有合法移動位置（即K0~K7）。

圖位置K上馬的八個合法移動位置

簡化問題表述則為：從坐標(biāo)（row，column）出發(fā)，依次嘗試：（row-2，column+1）、（row-1，column+2）、（row+1，column+2）、（row+2，column+1）、（row+2，column-1）、（row+1，column-2）、（row-1，column-2）、（row-2，column-1）這八個方向。

先將整個棋盤（實(shí)質(zhì)就是一個二維數(shù)組）的所有方格初始化為-1。從起始位置開始，可將馬的每次跳動抽象為一個棧結(jié)點(diǎn)，當(dāng)馬跳到下一個方格時(shí)就將起跳方格的信息壓棧，并在棋盤中標(biāo)記好馬經(jīng)過該起跳方格的次序。

當(dāng)馬跳到某個方格發(fā)現(xiàn)無處可跳時(shí)就出棧一個結(jié)點(diǎn)（相當(dāng)于跳回到上一步），并將該方格的次序恢復(fù)為初始值-1，然后嘗試出棧結(jié)點(diǎn)對應(yīng)方格的下一個騰躍方向。提醒：某個方格無處可跳意味著該方格的八個方向要么是死路，要么就是超出棋盤邊界的，此時(shí)只能通過出棧方式回跳到上一個方格，從而進(jìn)一步嘗試上一個方格的其它方向是否為遍歷通路。

該棧結(jié)點(diǎn)的結(jié)構(gòu)可以設(shè)置如下：

其中row保存起跳方格的行號，column保存起跳方格的列號，direction保存起跳方格的方向（int型，取值為0-7，對應(yīng)K0-K7這八個方向）。通過當(dāng)前方格位置及方向即可計(jì)算出下一個方格的行號和列號，便可進(jìn)一步判斷該方格是否越界或者馬是否已經(jīng)經(jīng)過了。

假設(shè)馬的起始位置為（5,3），則馬遍歷整個棋盤方格的次序如下圖所示。

20

假設(shè)馬的起始位置為（6,8）時(shí)，則馬遍歷整個棋盤方格的次序如下圖所示。

3．設(shè)計(jì)要求

?利用C、C++、C#或Java等語言實(shí)現(xiàn)該程序，程序應(yīng)上機(jī)調(diào)試通過并運(yùn)行正確。?假使程序采用C#或Java等語言實(shí)現(xiàn)，則酌情加分；假使主要函數(shù)采用動態(tài)鏈接庫形式實(shí)現(xiàn)，則酌情加分。

?輸入馬的初始坐標(biāo)位置，輸出馬對整個棋盤的遍歷順序。?撰寫課程設(shè)計(jì)報(bào)告，報(bào)告格式按規(guī)范設(shè)置。

?課程設(shè)計(jì)報(bào)告中應(yīng)給出算法過程的具體分析、程序數(shù)據(jù)所采用的存儲結(jié)構(gòu)圖、程序流程圖、測試數(shù)據(jù)及其結(jié)果分析、算法的時(shí)間和空間繁雜度等，另外還可以提出算法的進(jìn)一步改進(jìn)方法。課題B9：基于十字鏈表有向圖的遍歷1．設(shè)計(jì)目的

?把握十字鏈表結(jié)構(gòu)頂點(diǎn)數(shù)組的構(gòu)造方法。?把握十字鏈表結(jié)構(gòu)中弧結(jié)點(diǎn)的插入和刪除方法。?把握基于十字鏈表存儲結(jié)構(gòu)有向圖的兩種遍歷方法。2．主要內(nèi)容

（1）輸入給定有向圖的頂點(diǎn)總數(shù)和所有頂點(diǎn)標(biāo)志（每個頂點(diǎn)均用一個大寫英文

字母作為標(biāo)志）；

（2）輸入圖中弧的總數(shù)，并利用循環(huán)依次輸入各條弧，建立該有向圖的十字鏈

表存儲結(jié)構(gòu)；

（3）輸入一條弧的信息，構(gòu)造弧結(jié)點(diǎn)，并將該弧結(jié)點(diǎn)插入到十字鏈表結(jié)構(gòu)中；（4）輸入一條已存在的弧，將其從圖的十字鏈表結(jié)構(gòu)中找到并刪除；（5）輸出圖。

（6）實(shí)現(xiàn)BFS或DFS算法輸出基于十字鏈表存儲結(jié)構(gòu)有向圖的遍歷序列。

21

以上（3）（4）（5）（6）項(xiàng)功能以菜單形式列出。

圖B9-1有向圖

圖B9-2十字鏈表

3．設(shè)計(jì)要求

?利用C、C++、C#或Java等語言實(shí)現(xiàn)該程序，程序應(yīng)上機(jī)調(diào)試通過并運(yùn)行正確。?假使程序采用C#或Java等語言實(shí)現(xiàn)，則酌情加分；假使主要函數(shù)采用動態(tài)鏈接庫形式實(shí)現(xiàn)，則酌情加分。

?輸入數(shù)據(jù)，并驗(yàn)證操作后的輸出結(jié)果。?撰寫課程設(shè)計(jì)報(bào)告，報(bào)告格式按規(guī)范設(shè)置。

?課程設(shè)計(jì)報(bào)告中應(yīng)給出算法過程的具體分析、程序數(shù)據(jù)所采用的存儲結(jié)構(gòu)圖、程序流程圖、測試數(shù)據(jù)及其結(jié)果分析、算法的時(shí)間和空間繁雜度等，另外還可以提出算法的進(jìn)一步改進(jìn)方法。C類題目[共5題]課題C1：多項(xiàng)式運(yùn)算1．設(shè)計(jì)目的

?（1）把握線性表的順序存儲結(jié)構(gòu)和鏈?zhǔn)酱鎯Y(jié)構(gòu)。?（2）把握線性表插入、刪除等基本運(yùn)算。

?（3）把握線性表的典型應(yīng)用——多項(xiàng)式運(yùn)算（加、減、乘、除[選做]）。2．主要內(nèi)容

22

實(shí)現(xiàn)順序結(jié)構(gòu)或鏈?zhǔn)浇Y(jié)構(gòu)的多項(xiàng)式加減乘除運(yùn)算。假使多項(xiàng)式采用順序結(jié)構(gòu)，則多項(xiàng)式運(yùn)算的最高次應(yīng)能達(dá)到x99。

例如，已知：f(x)?8x6?4x5?2x4?123x3?x?10

g(x)?2x3?5x2?x

（1）相加結(jié)果：f(x)?g(x)?8x6?4x5?2x4?121x3?5x2?10（2）相減結(jié)果：f(x)?g(x)?8x6?4x5?2x4?125x3?5x2?2x?10（3）相乘結(jié)果：

f(x)*g(x)?16x9?32x8?16x7?232x6?613x5?125x4?25x3?51x2?10x（4）相除結(jié)果：

商?4x3?12x2?27x；余數(shù)??32x2?x?10

假使采用順序存儲結(jié)構(gòu)，則順序表結(jié)點(diǎn)的數(shù)據(jù)類型定義如下：typedefstruct_node{floatcoe;//系數(shù)intindex;//指數(shù)}Node;

函數(shù)f(x)的順序存儲結(jié)構(gòu)如下圖所示。

圖多項(xiàng)式的順序表存儲結(jié)構(gòu)

假使采用鏈?zhǔn)酱鎯Y(jié)構(gòu)，則鏈表結(jié)點(diǎn)的數(shù)