數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(1)課件

1、課 程 設(shè) 計時間： 二周。完成方式： 一人一題?？己朔绞剑?考查。 考核形式： 檢查：上機運行、檢查結(jié)果； 答辯：對程序提問、回答問題； 提交：原程序清單、課程設(shè)計報告。 成績評定方式： 按上機調(diào)試情況、運行結(jié)果和答辯情況、課程設(shè)計報告三方面評定。 成績評定檔次： 優(yōu)、良、中、及格、不及格。文檔要求課程設(shè)計報告按教務(wù)處指定的格式填寫打印。1 封面2 課程設(shè)計任務(wù)書3 課程設(shè)計鑒定表4 目錄 要求給出標題及頁次。5 課程設(shè)計的目的6 課程設(shè)計任務(wù)與要求7 設(shè)計思想及實現(xiàn)要點8 系統(tǒng)測試 說明程序調(diào)試過程中出現(xiàn)的問題及解決的方法。9 操作說明 說明使用本軟件的操作方法。10 總結(jié) 在總結(jié)中可談本

2、人的心得體會及軟件進一步改進的方向等項內(nèi)容。11 參考文獻12 附錄題目1 一元多項式計算器問題描述： 設(shè)計一個稀疏多項式簡單計算器基本要求： (1) 輸入并分別建立多項式A和B。 (2) 輸入輸出多項式，輸出形式為整數(shù)序列： n,c1,e1,c2,e2， 其中n是多項式的項數(shù)，ci和ei是第i項的系數(shù)和指數(shù)，序列按指數(shù)降序排列。 (3)完成兩個多項式的相加、相減，并將結(jié)果輸出。測試數(shù)據(jù)：(1)A+B A=3x14-8x8+6x2+2； B=2x10+4x8+-6x2(2) A-B A=11x14+3x10+2x8+10 x6+5 ； B=2x14+3x8+5x6+7(3) A+B A=x3+

3、x1 ； B=-x3-x1(4) A+B A=0 ； B=x7+x5+x3+x1(5)A-B A=100 x100+50 x50+20 x20+x ； B=10 x100+10 x50+10 x20+x選作內(nèi)容：（1）多項式在x=1時的運算結(jié)果；（2）求多項式A和B的乘積。題目2 迷宮問題 問題描述： 以一個m*n的長方陣表示迷宮，0和1分別表示迷宮中的通路和障礙。迷宮問題要求求出從入口（1,1）到出口（m,n）的一條通路，或得出沒有通路的結(jié)論。 基本要求： 首先實現(xiàn)一個以鏈表作存儲結(jié)構(gòu)的棧類型，然后編寫一個求迷宮問題的非遞歸程序，求得的通路以三元組（i,j,d）的形式輸出，其中：（i，j）指

4、示迷宮中的一個坐標， d表示走到下一坐標的方向。測試數(shù)據(jù)： 左上角（1,1）為入口，右下角（m,n）為出口。選作內(nèi)容： （1）編寫遞歸形式的算法，求得迷宮中的所有可能的通路； （2）以方陣的形式輸出迷宮及其通路迷宮中的所有可能的通路；題目3 二叉排序樹的應(yīng)用 問題描述： 利用二叉排序樹對順序表進行排序?；疽螅?（1）生成一個順序表L; （2）對所生成的順序表L構(gòu)造二叉排序樹; （3）利用棧結(jié)構(gòu)實現(xiàn)中序遍歷二叉排序樹; （4）中序遍歷所構(gòu)造的二叉排序樹將記錄由小到大輸出。測試數(shù)據(jù)： 用偽隨機數(shù)產(chǎn)生程序產(chǎn)生隨機數(shù)，表長不小于20。選作內(nèi)容： 實現(xiàn)二叉排序樹的插入和刪除操作。問題描述： 設(shè)計一個

5、交通咨詢系統(tǒng)，為自駕游旅行者客咨詢從任一個城市到另一個城市之間的最短路徑問題。設(shè)計分三個部分，一是建立交通網(wǎng)絡(luò)圖的存儲結(jié)構(gòu)；二是解決單源最短路徑問題；最后再實現(xiàn)兩個城市頂點之間的最短路徑問題?；疽螅?1 對城市信息(城市名、城市間的里程)進行編輯：具備添加、修改、刪除功能； 2 咨詢以用戶和計算機對話方式進行，要注意人機交互的屏幕界面。由用戶選擇輸入起點、終點，輸出信息：旅行者從起點、終點經(jīng)過的每一座城市。 3. 主程序可以有系統(tǒng)界面、菜單；也可用命令提示方式；選擇功能模塊執(zhí)行，要求在程序運行過程中可以反復操作。題目4 交通咨詢系統(tǒng)測試數(shù)據(jù)： 參考數(shù)據(jù)結(jié)構(gòu)（C語言版）（嚴蔚敏 吳偉民編著）

6、7.6節(jié)圖7.33的交通圖。 答辯測試數(shù)據(jù)：北京到烏魯木齊；北京到昆明；廣州到哈爾濱；烏魯木齊到南昌；沈陽到昆明。選作內(nèi)容： 考慮由于路況不同，不同城市間自駕旅行每百公里油耗不同，為旅行選擇最經(jīng)濟路線。題目5 內(nèi)部排序算法的比較 問題描述： 通過比較各內(nèi)部排序算法的關(guān)鍵字比較次數(shù)和關(guān)鍵字移動的次數(shù)，以取得直觀感受。 基本要求： 1、待排序表的表長不小于100； 2、至少要用5組不同的輸入數(shù)據(jù)作比較； 3、排序算法不少于5種； 4、最后要對結(jié)果作簡單的分析。 測試數(shù)據(jù)： 用偽隨機數(shù)產(chǎn)生程序產(chǎn)生。 選作內(nèi)容： 對不同的表長做試驗分析兩個指標相對于表長變化關(guān)系。實 現(xiàn) 要 點 多項式相加 p(x)=

7、3x148x8+6x2+2q(x)=2x10+4x86x2 p(x)p(x)+q(x)結(jié)果：p(x) =3x14+2x104x8+2 題目1 多項式的算術(shù)運算多項式的邏輯結(jié)構(gòu)：視為線性表 p(x)=3x14-8x8+6x2+2 數(shù)據(jù)元素 (coef,exp) 表示多項式項 coefxexp ，coef是該項的系數(shù)，exp是變元x的指數(shù)。多項式的存儲表示 p(x)=3x14-8x8+6x2+2 ( (3,14)，(-8,8)，(6,2)，(2,0) ) 順序表示 線性表長度事先難以確定； 算術(shù)運算需插入和刪除元素。 多項式的鏈接表示多項式的項 多項式相加帶頭結(jié)點的線性鏈表類型(pp37) typ

8、edef struct LNode / 結(jié)點類型 ElemType data; LNode *next; *Link,*Position; struct LinkList / 鏈表類型 Link head,tail; / 分別指向線性鏈表中的頭結(jié)點和最后一個結(jié)點 int len; / 指示線性鏈表中數(shù)據(jù)元素的個數(shù) ; 分配由p指向的值為e的結(jié)點Status MakeNode(Link &p,ElemType e) / 分配由p指向的值為e的結(jié)點，并返回OK； /若分配失敗, 則返回ERROR p=(Link)malloc(sizeof(LNode); if(!p) return ERROR;

9、p-data=e; return OK; 釋放p所指結(jié)點void FreeNode(Link &p) / 釋放p所指結(jié)點 free(p); p=NULL; 構(gòu)造一個空的線性鏈表Status InitList(LinkList &L) Link p; p=(Link)malloc(sizeof(LNode); / 生成頭結(jié)點 if (p) p-next=NULL; L.head=L.tail=p; L.len=0; return OK; else return ERROR; 銷毀線性鏈表LStatus DestroyList(LinkList &L) / 銷毀線性鏈表L，L不再存在 ClearL

10、ist(L); / 清空鏈表 FreeNode(L.head); L.tail=NULL; L.len=0; return OK; 將線性鏈表L重置為空表Status ClearList(LinkList &L) Link p,q; if(L.head!=L.tail) / 不是空表 p=q=L.head-next; L.head-next=NULL; while (p!=L.tail) p=q-next; free(q); q=p; free(q); L.tail=L.head; L.len=0; return OK; 將s所指結(jié)點插入在第一個結(jié)點之前Status InsFirst(Link

11、List &L, Link h,Link s) / 形參增加L,因為需修改L/ h指向L的一個結(jié)點，把h當做頭結(jié)點，/將s所指結(jié)點插入在第一個結(jié)點之前 s-next=h-next; h-next=s; if (h=L.tail) / h指向尾結(jié)點 L.tail=h-next; / 修改尾指針 L.len+; return OK; 刪除鏈表中的第一個結(jié)點Status DelFirst(LinkList &L,Link h,Link &q) / 形參增加L,因為需修改L。 h指向L的一個結(jié)點， / 把h當做頭結(jié)點，刪除鏈表中的第一個結(jié)點并 / 以q返回。 q=h-next; if (q) /鏈表非

12、空 h-next=q-next; if(!h-next) L.tail=h; /刪除尾結(jié)點，修改尾指針 L.len-; return OK; else return FALSE; / 鏈表空 Status Append(LinkList &L,Link s) / 將指針s (s-data為第一個數(shù)據(jù)元素)所指 (彼此/ 以指針相 鏈，以NULL結(jié)尾)的一串結(jié)點鏈接在/ 線性鏈表L的最后一個結(jié)點之后, 并改變鏈表L / 的尾指針指向新的尾結(jié)點 int i=1; L.tail-next=s; while(s-next) s=s-next; i+; L.tail=s; L.len+=i; retur

13、n OK; 鏈接兩個單鏈表返回p所指結(jié)點中數(shù)據(jù)元素的值ElemType GetCurElem(Link p) /已知p指向線性鏈表中的一個結(jié)點， /返回p所指結(jié)點中數(shù)據(jù)元素的值 return p-data; 判斷線性鏈表L為空表Status ListEmpty(LinkList L) / 若線性鏈表L為空表，則返回TRUE，否則返回FALSE if (L.len) return FALSE; else return TRUE; 返回線性鏈表L中頭結(jié)點的位置Position GetHead(LinkList L) / 返回線性鏈表L中頭結(jié)點的位置 return L.head; 返回p所指結(jié)點的直

14、接后繼的位置 Position NextPos(Link p) / 已知p指向線性鏈表L中的一個結(jié)點， / 返回p所指結(jié)點的直接后繼的位置 / 若無后繼，則返回NULL return p-next; LocateElem:判定升序鏈表L中是否存在與e相等的元素 Status LocateElem(LinkList L,ElemType e,Position &q, int(*compare)(ElemType,ElemType) / 若升序鏈表L中存在與e滿足判定函數(shù)compare()取值為0的元素， / 則q 指示 L 中第一個值為e的結(jié)點的位置；否則q指示第一個與e / 滿足判定函數(shù)com

15、pare()取值0的元素的前驅(qū)的位置。 Link p=L.head, pp; do pp=p; p=p-next; while (p&(compare(p-data,e)data.expndata,e)0) q=pp; return FALSE; / 到表尾或compare(p-data,e)0 else q=p; return TRUE; / 找到 項結(jié)點項結(jié)點 Term typedef struct / 項的表示,多項式的項作為LinkList的數(shù)據(jù)元素pp42 float coef; / 系數(shù) int expn; / 指數(shù) term,ElemType; / 兩個類型名:term用于本AD

16、T,/ElemType為LinkList的數(shù)據(jù)對象名 typedef LinkList polynomial; #define DestroyPolyn DestroyList #define PolynLength ListLength多項式的基本操作的函數(shù)int cmp(term a,term b) / CreatPolyn()的實參 / 依a的指數(shù)值b的指數(shù)值，分別返回-1、0或+1 if(a.expn=b.expn) return 0; else return (a.expn-b.expn)/abs(a.expn-b.expn); 建立表示一元多項式 void CreatPolyn(p

17、olynomial &P,int m) /pp42, 算法2.22 / 輸入m項的系數(shù)和指數(shù)，建立表示一元多項式的有序鏈表P Position q,s; term e; int i; InitList(p); printf(請依次輸入%d個系數(shù)，指數(shù)：n,m); for(i=1;idata.coef+=qb-data.coef; / 兩者的指數(shù)值相等,修改Pa當前結(jié)點的系數(shù)值 if(qa-data.coef=0) / 刪除多項式Pa中當前結(jié)點 DelFirst(Pa,ha,qa); FreeNode(qa); else ha=qa; DelFirst(Pb,hb,qb); FreeNode(q

18、b); qb=NextPos(hb); qa=NextPos(ha); break; case 1: DelFirst(Pb,hb,qb); /多項式Pb中當前結(jié)點的指數(shù)值小 InsFirst(Pa,ha,qb); ha=ha-next; qb=NextPos(hb); 系數(shù)處理一元多項式系數(shù)取反void Opposite(polynomial Pa) / 一元多項式系數(shù)取反 Position p; p=Pa.head; while(p-next) p=p-next; p-data.coef*=-1; 多項式減法 void SubtractPolyn(polynomial &Pa,polyno

19、mial &Pb) / 多項式減法:Pa=Pa-Pb,并銷毀一元多項式Pb Opposite(Pb); AddPolyn(Pa,Pb); 打印輸出一元多項式P void PrintPolyn(polynomial P) / 打印輸出一元多項式P Link q; q=P.head-next; / q指向第一個結(jié)點 printf( 系數(shù) 指數(shù)n); while(q) printf(%f %dn,q-data.coef,q-data.expn); q=q-next; void CreatPolyn(polynomial &P,int m) / 算法2.22void AddPolyn(polynomi

20、al &Pa,polynomial &Pb) / 算法2.23void PrintPolyn(polynomial P) / 打印輸出一元多項式 主函數(shù)題目2 迷宮問題 問題：以一個m*n的方陣表示迷宮，0和1分別表示迷宮中的通路和障礙。迷宮問題要求求出從入口（1,1）到出口（m,n）的所有通路，或得出沒有通路的結(jié)論。 思路：從入口（1,1）出發(fā)，按某一方向向前搜索，若能走通（未走過），即某處可以到達，則到達新點，否則，試探下一方向；若所有的方向都沒有通路，則沿原路返回前一點，換下一個方向再試探，直到所有可能的通路都探索到，或找到一條通路，或無路可走又返回到入口點。 用一個棧保存所能到達的每一

21、點的下標及從該點前進的方向。需要解決的四個問題（1）表示迷宮的數(shù)據(jù)結(jié)構(gòu) 利用mazemn表示一個迷宮， mazemn=0，1。 1表示通路， 0 表示不通。 為簡化問題用mazem+2n+2來表示一個迷宮，這樣每個點的試探方向都為8。00000000000011101110010101111000100000100011101110010011000000110011000000000000（2）試探方向 (北) (x-1,y-1) (x-1,y) (x-1,y+1)(西) (x,y-1) (x,y) (x,y+1) (東) (x+1,y-1) (x+1,y) (x+1,y+1) (南)方向V

22、：0=v(x,y,d) 出棧； 求出下一個要試探的方向d+； while (還有剩余試探的方向） if（d方向可走） (x,y,d)入棧； 求新點坐標（i，j）； 將新點（i，j）切換為當前點（x，y）； if (x,y)=(m,n) 結(jié)束； else 重置d=0; else d+; 題目3 利用二叉排序樹對順序表進行排序涉及知識面1 排序2 查找3 樹4 順序表5 棧設(shè)計內(nèi)容、要求：生成一個順序表L對所生成的順序表L構(gòu)造二叉排序樹利用棧結(jié)構(gòu)實現(xiàn)中序遍歷二叉排序樹中序遍歷所構(gòu)造的二叉排序樹將記錄由小到大輸出步驟1 生成順序表L定義順序表：p22；利用算法2.3 InitList_Sq 初始化順

23、序表；利用算法2.4 ListInsert_Sq 生成順序表；數(shù)據(jù)元素個數(shù)和數(shù)據(jù)元素的值從鍵盤輸入；2 對所生成順序表L構(gòu)造二叉排序樹（1）定義二叉排序樹 P127（2）初始化二叉排序樹為空樹 BiTree T=NULL；（3）按待排序的順序表構(gòu)造二叉排序樹 利用算法9.5(b)和9.6 方法： for (int i=0;idata;方法：用output替代visit調(diào)用算法6.3 i=0; InorderTraverse(T,output(T,l,i);按順序輸出順序表L L即為由小到大排序的順序表。函數(shù)表InitList_Sq, ListInsert_Sq, InsertBST, Sear

24、chBST, InOrderTraverser,output, InitStack, StackEmpty, Push, Pop四 函數(shù)調(diào)用關(guān)系 mainInitList_Sq InOrderTraverser ListInsert_Sq InsertBST SearchBST output InitStack StackEmpty Push Pop問題描述： 設(shè)計一個交通咨詢系統(tǒng)，為自駕游旅行者客咨詢從任一個城市到另一個城市之間的最短路徑問題。設(shè)計分三個部分，一是建立交通網(wǎng)絡(luò)圖的存儲結(jié)構(gòu)；二是解決單源最短路徑問題；最后再實現(xiàn)兩個城市頂點之間的最短路徑問題。題目4 交通咨詢系統(tǒng)(1) 數(shù)據(jù)存儲。 城市信息(城市名、代碼)、城市間的里程存儲于磁盤文件。建議把城市信息存于文件前面，交通信息存于文件的后面，用fread和fwrite函數(shù)