數(shù)據(jù)結構一元多項式

1、 數(shù)據(jù)結構 課程設計報告系 別：計算機與電子系 專業(yè)班級：電子0802班 學生姓名：胡錦奎（）指導教師：程海英 （課程設計時間：20 10 年 12月 27日20 11 年1月7日）華中科技大學武昌分校目 錄1課程設計目的3頁2課程設計題目描述和要求 3頁3課程設計報告內容5頁3.1 一元多項式運算的實現(xiàn) 5頁3.2 迷宮問題實現(xiàn) 9頁3.3 校園導游咨詢13頁3.4 跳舞搭配問題15頁3.5 利用棧實現(xiàn)表達式求值18頁4總結 20頁參考文獻 21頁（要求：目錄題頭用三號黑體字居中書寫，隔行書寫目錄內容。目錄中各級題序及標題用小四號黑體）一課程設計目的： 數(shù)據(jù)結構課程設計是在學完數(shù)據(jù)結構課程之

2、后的實踐教學環(huán)節(jié).該實踐教學是軟件設計的綜合訓練,包括問題分析,總體結構設計,用戶界面設計,程序設計基本技能和技巧。要求學生在設計中逐步提高程序設計能力,培養(yǎng)科學的軟件工作方法.學生通過數(shù)據(jù)結構課程設計在各方面得到鍛煉 二課程設計題目描述和要求：1一元多項式加法、減法、乘法運算的實現(xiàn)1）設計內容：完成兩個一元多項式作加法、減法、乘法，給出明確的等式形式。完成總體設計，搭好框架，確定人機對話的界面，確定函數(shù)個數(shù)；函數(shù)功能要劃分好，總體設計應畫流程圖，程序一定要經(jīng)得起測試2）設計要求（1）用C語言編程實現(xiàn)上述實驗內容中的結構定義和算法。（2）要有main()函數(shù)，并且在main()函數(shù)中使用檢測數(shù)

3、據(jù)調用上述算法。（3）用switch語句設計如下選擇式菜單。 *數(shù)據(jù)結構綜合性實驗* *一、多項式的加法、減法、乘法運算* * 1.多項式創(chuàng)建 * * 2.多項式相加 * * 3.多項式相減 * 4.多項式相乘 * 5.清空多項式 * 0.退出系統(tǒng) * 請選擇（05） *請選擇（0-5）:。2迷宮求解1）設計內容：以一個m*n的長方形矩陣表示迷宮，0和1分別表示迷宮中的通路和障礙。設計一個程序，對任意設定的迷宮，求出一條從入口到出口的通路，或得出沒有通路的結論。2)設計要求（1）用C語言編程實現(xiàn)上述實驗內容中的結構定義和算法；（2）要有main()函數(shù)，并且在main()函數(shù)中使用檢測數(shù)據(jù)調用

4、上述算法；3、校園導游咨詢1）設計內容：設計一個校園導游程序，為來訪的客人提供各種信息咨詢服務，包括：（1）設計所在的學校的校園平面圖，所含景點不少于5個。以圖中頂點表示校內各景點，存放景點的名稱、代號、簡介等信息；以邊表示路徑，存放路徑長度等相關信息。（2）為來訪客人提供圖中任意景點相關信息的咨詢。（3）為來訪客人提供圖中任意景點的問路查詢，即查詢任意兩個景點之間的一條最短的簡單路徑2）設計要求：（1）用C語言編程實現(xiàn)上述實驗內容中的結構定義和算法；（2）要有main()函數(shù)，并且在main()函數(shù)中使用檢測數(shù)據(jù)調用上述算法；（3）用switch語句設計如下選擇式菜單4、跳舞配對問題設計內容

5、與要求：一共有m個女生，有n個男生（且mn），現(xiàn)要開一個舞會，男女分別編號坐在舞池的兩邊的椅子上。每曲開始時，依次從男和女中各出一個人配對跳舞，本曲沒成功配對者坐著等待下一曲找舞伴。設計一系統(tǒng)模擬動態(tài)地顯示出上述過程，要求如下：1）輸出每曲配對情況；2）計算出任何一個男（編號為X）和任意一個女（編號為Y），在第K曲配對跳舞的情況，至少求出K的兩個值。5、實現(xiàn)表達式求解設計內容：輸入一個表達式，按如下要求完成其求值運算：1）表達式中允許有兩種括號：（、）、，請驗證其匹配成對的合法性；2）運算符限定于加、減、乘、除四種運算，請驗證表達式是否書寫合法，如3+2-*5就不是一個合法表達式；3）使用棧的

6、原理實現(xiàn)表達式求值；4）盡量考慮參與運算的數(shù)是非1位數(shù)，如234+32*12。三課程設計報告內容1 一元多項式加法，減法，乘法運算的實現(xiàn) 1.1數(shù)據(jù)結構設計根據(jù)下面給出的存儲結構定義：#define MAXSIZE 20 /定義線性表最大容量 /定義多項式項數(shù)據(jù)類型typedef struct float coef; /系數(shù) int expn; /指數(shù) term,elemType;typedef struct term termsMAXSIZE; /線性表中數(shù)組元素 int last; /指向線性表中最后一個元素位置 SeqList;typedef SeqList polynomial;1.2

7、基本操作函數(shù)說明 polynomial*Init_Polynomial();/初始化空的多項式int PloynStatus(polynomial*p)/判斷多項式的狀態(tài) int Location_Element(polynomial*p,term x)在多項式p中查找與x項指數(shù)相同的項是否存在int Insert_ElementByOrder(polynomial*p,term x)/在多項式p中插入一個指數(shù)項xint CreatePolyn(polynomial*P,int m)/輸入m項系數(shù)和指數(shù)，建立表示一元多項式的有序表pchar compare(term term1,term te

8、rm2)/比較指數(shù)項term1和指數(shù)項term2polynomial*addPloyn(polynomial*p1,polynomial*p2)/將多項式p1和多項式p2相加，生成一個新的多項式polynomial*subStractPloyn(polynomial*p1,polynomial*p2)/多項式p1和多項式p2相減，生成一個新的多項式polynomial*mulitPloyn(polynomial*p1,polynomial*p2)/多項式p1和多項式p2相乘，生成一個新的多項式void printPloyn(polynomial*p)/輸出在順序存儲結構的多項式p1.3設計思路

9、及算法設計 （1）一元多項式的建立：輸入多項式采用頭插法的方式，輸入多項式中一個項的系數(shù)和指數(shù)（2）顯示輸入的數(shù)字：顯示你輸入的各項式的指數(shù)和系數(shù)。（3）.一元多項式加減法和乘法運算進行加減法和乘法的運算后得到的簡化的一元多項式可以用一個核心函數(shù)addPloyn來實現(xiàn)多項式的加法，它把p1所指向的多項式加p2所指向的多項式，結果為p3所指的多項式。相加時，首先設兩個指針變量p1和p2分別從多項式中的首項開始掃描，比較p1和p2所指結點指數(shù)域的值，可能出現(xiàn)下面三種情況之一：A，p1-terms【i】大于p2-terms【j】，則p1繼續(xù)向后掃描。B，p1-terms【i】等于p2-terms【j

10、】，則將其系數(shù)相加。若結果不為零，將結果放入p3-terms【k】中，否則同時刪除p1和p2所指結點。然后p1和p2繼續(xù)向后掃描C，p1-terms【i】小于p2-terms【j】，則將p3所指結點插入p2所指結點之前，然后p1，p2繼續(xù)向后掃描減法的算法實現(xiàn)和加法類似，乘法的算法實現(xiàn)是讓系數(shù)想乘，指數(shù)部分相加 （4）.一元多項式輸出和整理以降冪的形式輸出1.4功能模塊圖主函數(shù)建立鏈表排列和組件相加減或相乘入輸組成多項式1.5 源代碼分析見電子檔1.6測試與結果 2.迷宮問題實現(xiàn) 2.1數(shù)據(jù)結構設計根據(jù)以上問題給出存儲結構定義： typedef struct /定義坐標int x;int y;

11、item; /定義坐標和方向typedef structint x;int y;int d;dataType; /定義順序棧的類型定義typedef structdataType dataMAXLEN;int top;SeqStack;item move8; /8鄰域試探方向數(shù)組int mazeM+2N+2=1,1,1,1,1,1,1,1,1,1,1,0,1,1,1,0,1,1,1,1,1,1,0,1,0,1,1,1,1,1,1,0,1,0,0,0,0,0,1,1,1,0,1,1,1,0,1,1,1,1,1,1,0,0,1,1,0,0,0,1,1,0,1,1,0,0,1,1,0,1,1,1,1

12、,1,1,1,1,1,1,1,; /定義迷宮數(shù)組，0表示有路徑，1表示不存在路徑 2.2基本操作函數(shù)說明void print_Path(SeqStack*s);/輸出迷宮路線SeqStack*InitSeqStack()/該函數(shù)初始化一個空棧，并返回指向該棧的存儲單元首地址int Push(SeqStack*s,dataType x)/將元素x入棧s,若入棧成功返回結果1；否則返回0int StackEmpty(SeqStack*s)/該函數(shù)判斷棧是否為空，若?？辗祷亟Y果1；否則返回0int Pop(SeqStack*s,dataType*x)/將棧頂元素出棧，放入x所指向的存儲單元中，若出棧

13、返回結果1；否則返回0void init_move(item move8)/初始化8鄰域方向int find_Path(int mazeM+2N+2,item move8)/在迷宮maze二維數(shù)組中按move的8鄰域方向探測迷宮路線，存在返回1，否則返回0void print_Path(SeqStack*s)/輸出棧s中所有迷宮路徑2.3程序設計內容與思路 迷宮求解的第一步是確定存儲表示。最直接的表示無疑是數(shù)組，我們用二維數(shù)組maze表示迷宮，闖迷宮的物體的位置可以用數(shù)組的行row，列col表示，即maze【row】【col】。用X表示迷宮中的一點，下一步可試探的方向共有8個，如果參照指南針的

14、指向，這8個方向分別為東，南，西，北，東北，東南，西北，西南。有一點需要注意，迷宮中的位置并不都有8個領域，如在迷宮的靠墻位置其領域數(shù)小于8，為了方便處理，在迷宮周圍加上一圈，可省去邊界檢查。這樣m*n的迷宮需要(m+2)*(n+2)大小的數(shù)組，入口點改為maze【1】【1】，出口點改為maze【m】【n】 為了程序實現(xiàn)進一步簡化，可以再定義一個數(shù)組move表示移動的方向.下一步的移動方向可用下列式子表示 nextRow=row+movedir.x nextcol=col+movedir.y 在迷宮中搜索，某一時刻有多種選擇，究竟哪個方向最好，當時并無定論，所以只有先把當前位置保存起來，然后任

15、選一個方向。如果隨后的搜索碰到死路，可以回到當前保存起來的位置，然后嘗試另一個尚未搜索的方向 2.4程序流程圖 2.5 源代碼分析 見電子檔 2.6測試與結果 3.校園導游咨詢 3.1 數(shù)據(jù)結構設計 #define INT_MAX 10000 #define n 10 /定義全局變量 int costnn; /邊的值 int shortestnn; /兩點間的最短距離 int pathnn; /經(jīng)過的景點 3.2 基本操作函數(shù)說明 void introduce(); /景點介紹 int shortestdistance(); /要查找的兩景點的最短距離 void floyed(); /用flo

16、yed算法求兩個景點的最短路徑 void display(int i,int j); /打印兩個景點的路徑及最短距離3.3 程序設計內容與思路（1）用鏈接矩陣表示法創(chuàng)建一個圖，并設計一個交互式界面（2）設計景點介紹界面，用switch語句（3）設計查找最短路徑的算法，可用floyd算法（4）打印出兩個景點之間的最短路徑在該程序的設計中，先設計出main（）主函數(shù)，在屏幕上顯示所要操作的界面，在main（）主函數(shù)中調用另外兩個函數(shù)：void introduce（）和void shortestdistance（）。接下來再設計這兩個函數(shù)，當然，在主函數(shù)調用前，要事先聲明這兩個函數(shù)3.4 源代碼分析

17、見電子檔3.5 測試與結果4.跳舞搭配問題 4.1 數(shù)據(jù)結構設計 Typedef struct QNode /定義鏈隊結點類型 int num; struct QNode*next; QNode,*QueuePtr; Typedef stuuct /定義鏈隊頭指針類型 QueuePtr front； /隊頭指針 QueuePtr rear； /隊尾指針 LinkQueue； 42基本操作函數(shù)說明 void sleep(clock-t wait); /延遲函數(shù) void InitQ(LinkQueue &Q); /建立空隊列 void EnQueue(LinkQueue &Q,int num);

18、 /入隊列 void DeQueue(LinkQueue &Q,int &num); /出隊列 void DestoryQueue(LinkQueue &Q); /刪除隊列 void PrintF(LinkQueue &F,int i); /打印第i首曲子是女隊的情況 void PrintM(LinkQueue &M,int i); /打印第i首曲子是男隊的情況 void check（int n）； /判斷輸入n是否合法4.3 設計思路和算法設計在算法中假設男士和女士的記錄存放在一個數(shù)組中作為輸入，然后依次掃描該數(shù)組中的各元素，并根據(jù)性別判斷是進男隊還是進女隊。當這兩隊構造完成之后，依次將兩隊

19、的對頭元素出對來配對舞伴，直到某隊隊列為空為止。此時，若某隊仍有等待配對者，算法輸出此隊等待中的人數(shù)和隊頭的等待著的名字，它將是下一輪舞曲開始時第一個獲得舞伴的人數(shù)據(jù)模型（邏輯結構）: 循環(huán)隊列（兩個），將男生、女生兩組人分別存放，以實現(xiàn)循環(huán)配對輸出。存儲結構: 循環(huán)鏈表核心算法: 循環(huán)隊列的入隊，出隊，判隊滿，判隊空。輸入數(shù)據(jù): 男生人數(shù)、女生人數(shù)，歌曲數(shù)量輸出數(shù)據(jù): 每一首歌曲播放時，男生和女生搭配情況（只輸出編號即可） 當要查找的男女搭配時輸出歌曲編號，和他們搭配的總次數(shù)。 循環(huán)隊列是在隊列的順序存儲結構中，除了用乙組地址連續(xù)的存儲單元依次存放從隊列頭到隊列尾的元素外，尚需附設兩個指針f

20、ront和rear分別指示隊列頭元素和隊列尾元素的位置。循環(huán)隊列（兩個），將男生、女生兩組人分別存放，以實現(xiàn)循環(huán)配對輸出。循環(huán)隊列的入隊，出隊，判隊滿，判隊空。（1） 要模擬動態(tài)地顯示出現(xiàn)題目中所要求的循環(huán)，我們要先建立兩個循環(huán)隊列SqQueue和SqQueue2。（2） 將男生、女生兩組人分別存入這兩個隊列。以實現(xiàn)他們的循環(huán)配對輸出，這是循環(huán)隊列固有的特性。（3） 利用循環(huán)隊列的特性，將男女生分別進行入隊列和出隊列操作，且實現(xiàn)搭配輸出。（4） 循環(huán)隊列的長度分別設為男女生的個數(shù)即可。（5） 在計算機終端輸出的結果是：根據(jù)要求輸出男生女生搭配情況。4.4程序流程圖4.5源代碼分析見電子檔4.6

21、 測試與結果 5.利用棧實現(xiàn)表達式求值 5.1數(shù)據(jù)結構設計 typedef struct /運算符棧char *base;char *top;int stacksize;SqStackcha;typedef struct /運算數(shù)棧double *base;double *top;int stacksize;SqStackdou; 5.2 基本操作函數(shù)說明char gettop(sqstackcha &s); /取操作符棧頂元素double gettop(sqstackdou &s); /取操作數(shù)棧頂元素int precede(sqstackcha &s,char c); /比較字符c與操作符

22、棧頂元素的優(yōu)先級void initstak(sqstackcha &s); /初始化操作符棧void initstak(sqstackdou &s); /初始化操作數(shù)棧double opterate(double a,char theta,double b); /對操作數(shù)a和b用操作符運行其結果void push(sqstackcha &s,char e); /操作符入棧char pop(sqstackcha &s,char e); /操作符出棧double pop(sqstackdou &s,double e);操作符出棧void initstack(sqstackcha &s)/初始化字符

23、型棧5.3設計內容與思路（1）設計主函數(shù)，包含界面設計和后綴表達式的算法設計。在此問題中，如果是單位操作數(shù)，處理會比較方便，對于多位的操作數(shù)，可以采用這樣的處理思路：把包含后綴表達式的一個字符串由一個字符指針參數(shù)所指向，每次從該字符串中讀入一個字符，若它是空格則不做任何處理，若它是運算符，則表明它的兩個操作數(shù)已經(jīng)在棧中，其中棧頂元素為運算符的后一個操作數(shù)，棧頂元素的前一個元素為運算符的前一個操作數(shù)，把它們彈出后進行相應的運算并保存在一個變量中。（2）設計函數(shù)，實現(xiàn)把輸入的中綴表達式轉化為后綴表達式5.4源代碼分析見電子檔5.5測試與結果四總結通過兩周的學習和實踐，解決實際問題，讓我對數(shù)據(jù)結構有

24、了更深的了解，對數(shù)據(jù)結構產(chǎn)生了濃厚的興趣，同時也讓我提高了解決實際問題的能力。我們要不斷的通過上機來提高自己的學習水平，在上機的同時改正了自己對某些算法的錯誤使用，使自己在通過程序解決問題時抓住關鍵算法，有了算法設計思想和流程圖，并用C語言描繪出關鍵算法。以前我對數(shù)據(jù)結構（C語言描述）的一些標準庫函數(shù)不太了解，還有對函數(shù)調用的正確使用不夠熟悉，還有對C語言中經(jīng)常出現(xiàn)的錯誤也不了解，通過實踐，使我在這幾個方面的認識有所提高。讓自己有一定的能力去改正一些常見的錯誤語法，很高興這兩周的學習讓我對數(shù)據(jù)結構（C語言描述）有了新的認識，所以后在學習過程中，我會更加注視實踐操作，使自己便好地學好計算機。在這

25、次課程設計的實驗中，我收獲了許多知識，通過查找大量資料，請教老師，以及不懈的努力，也培養(yǎng)了獨立思考、動手操作的能力。我也學會了許多學習和解決實際問題的方法，讓我受益匪淺。課程設計對我來說，趣味性強，不僅鍛煉能力，而且可以學到很多東西，在與老師和同學的交流過程中，互動學習，將知識融會貫通，也增強了我和同學之間的團隊合作的能力。讓我們知道只要努力，集中精力解決問題，一定會有收獲的，過程也是很重要的。在這次課程設計中我們要學會利用時間，在規(guī)定的時間內完成我們的任務，要逐漸養(yǎng)成用C語言編寫程序的良好習慣。這些對我來說都是一種鍛煉，一個知識積累的過程，一種能力的提高。要打好基礎，才能用更好的辦法，更簡潔明了的程序解決實際問題，只有這樣才能進一步的取得