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

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

2、人的心得體會(huì)及軟件進(jìn)一步改進(jìn)的方向等項(xiàng)內(nèi)容。11 參考文獻(xiàn)12 附錄題目1 一元多項(xiàng)式計(jì)算器問(wèn)題描述： 設(shè)計(jì)一個(gè)稀疏多項(xiàng)式簡(jiǎn)單計(jì)算器基本要求： (1) 輸入并分別建立多項(xiàng)式A和B。 (2) 輸入輸出多項(xiàng)式，輸出形式為整數(shù)序列： n,c1,e1,c2,e2， 其中n是多項(xiàng)式的項(xiàng)數(shù)，ci和ei是第i項(xiàng)的系數(shù)和指數(shù)，序列按指數(shù)降序排列。 (3)完成兩個(gè)多項(xiàng)式的相加、相減，并將結(jié)果輸出。測(cè)試數(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）多項(xiàng)式在x=1時(shí)的運(yùn)算結(jié)果；（2）求多項(xiàng)式A和B的乘積。題目2 迷宮問(wèn)題 問(wèn)題描述： 以一個(gè)m*n的長(zhǎng)方陣表示迷宮，0和1分別表示迷宮中的通路和障礙。迷宮問(wèn)題要求求出從入口（1,1）到出口（m,n）的一條通路，或得出沒(méi)有通路的結(jié)論。 基本要求： 首先實(shí)現(xiàn)一個(gè)以鏈表作存儲(chǔ)結(jié)構(gòu)的棧類(lèi)型，然后編寫(xiě)一個(gè)求迷宮問(wèn)題的非遞歸程序，求得的通路以三元組（i,j,d）的形式輸出，其中：（i，j）指

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

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

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

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

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

9、p-data=e; return OK; 釋放p所指結(jié)點(diǎn)void FreeNode(Link &p) / 釋放p所指結(jié)點(diǎn) free(p); p=NULL; 構(gòu)造一個(gè)空的線性鏈表Status InitList(LinkList &L) Link p; p=(Link)malloc(sizeof(LNode); / 生成頭結(jié)點(diǎn) if (p) p-next=NULL; L.head=L.tail=p; L.len=0; return OK; else return ERROR; 銷(xiāo)毀線性鏈表LStatus DestroyList(LinkList &L) / 銷(xiāo)毀線性鏈表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é)點(diǎn)插入在第一個(gè)結(jié)點(diǎn)之前Status InsFirst(Link

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

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

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

14、接后繼的位置 Position NextPos(Link p) / 已知p指向線性鏈表L中的一個(gè)結(jié)點(diǎn)， / 返回p所指結(jié)點(diǎn)的直接后繼的位置 / 若無(wú)后繼，則返回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 中第一個(gè)值為e的結(jié)點(diǎn)的位置；否則q指示第一個(gè)與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; / 找到 項(xiàng)結(jié)點(diǎn)項(xiàng)結(jié)點(diǎn) Term typedef struct / 項(xiàng)的表示,多項(xiàng)式的項(xiàng)作為L(zhǎng)inkList的數(shù)據(jù)元素pp42 float coef; / 系數(shù) int expn; / 指數(shù) term,ElemType; / 兩個(gè)類(lèi)型名:term用于本AD

16、T,/ElemType為L(zhǎng)inkList的數(shù)據(jù)對(duì)象名 typedef LinkList polynomial; #define DestroyPolyn DestroyList #define PolynLength ListLength多項(xiàng)式的基本操作的函數(shù)int cmp(term a,term b) / CreatPolyn()的實(shí)參 / 依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); 建立表示一元多項(xiàng)式 void CreatPolyn(p

17、olynomial &P,int m) /pp42, 算法2.22 / 輸入m項(xiàng)的系數(shù)和指數(shù)，建立表示一元多項(xiàng)式的有序鏈表P Position q,s; term e; int i; InitList(p); printf(請(qǐng)依次輸入%d個(gè)系數(shù)，指數(shù)：n,m); for(i=1;idata.coef+=qb-data.coef; / 兩者的指數(shù)值相等,修改Pa當(dāng)前結(jié)點(diǎn)的系數(shù)值 if(qa-data.coef=0) / 刪除多項(xiàng)式Pa中當(dāng)前結(jié)點(diǎn) 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); /多項(xiàng)式Pb中當(dāng)前結(jié)點(diǎn)的指數(shù)值小 InsFirst(Pa,ha,qb); ha=ha-next; qb=NextPos(hb); 系數(shù)處理一元多項(xiàng)式系數(shù)取反void Opposite(polynomial Pa) / 一元多項(xiàng)式系數(shù)取反 Position p; p=Pa.head; while(p-next) p=p-next; p-data.coef*=-1; 多項(xiàng)式減法 void SubtractPolyn(polynomial &Pa,polyno

19、mial &Pb) / 多項(xiàng)式減法:Pa=Pa-Pb,并銷(xiāo)毀一元多項(xiàng)式Pb Opposite(Pb); AddPolyn(Pa,Pb); 打印輸出一元多項(xiàng)式P void PrintPolyn(polynomial P) / 打印輸出一元多項(xiàng)式P Link q; q=P.head-next; / q指向第一個(gè)結(jié)點(diǎn) 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) / 打印輸出一元多項(xiàng)式 主函數(shù)題目2 迷宮問(wèn)題 問(wèn)題：以一個(gè)m*n的方陣表示迷宮，0和1分別表示迷宮中的通路和障礙。迷宮問(wèn)題要求求出從入口（1,1）到出口（m,n）的所有通路，或得出沒(méi)有通路的結(jié)論。 思路：從入口（1,1）出發(fā)，按某一方向向前搜索，若能走通（未走過(guò)），即某處可以到達(dá)，則到達(dá)新點(diǎn)，否則，試探下一方向；若所有的方向都沒(méi)有通路，則沿原路返回前一點(diǎn)，換下一個(gè)方向再試探，直到所有可能的通路都探索到，或找到一條通路，或無(wú)路可走又返回到入口點(diǎn)。 用一個(gè)棧保存所能到達(dá)的每一

21、點(diǎn)的下標(biāo)及從該點(diǎn)前進(jìn)的方向。需要解決的四個(gè)問(wèn)題（1）表示迷宮的數(shù)據(jù)結(jié)構(gòu) 利用mazemn表示一個(gè)迷宮， mazemn=0，1。 1表示通路， 0 表示不通。 為簡(jiǎn)化問(wèn)題用mazem+2n+2來(lái)表示一個(gè)迷宮，這樣每個(gè)點(diǎn)的試探方向都為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) 出棧； 求出下一個(gè)要試探的方向d+； while (還有剩余試探的方向） if（d方向可走） (x,y,d)入棧； 求新點(diǎn)坐標(biāo)（i，j）； 將新點(diǎn)（i，j）切換為當(dāng)前點(diǎn)（x，y）； if (x,y)=(m,n) 結(jié)束； else 重置d=0; else d+; 題目3 利用二叉排序樹(shù)對(duì)順序表進(jìn)行排序涉及知識(shí)面1 排序2 查找3 樹(shù)4 順序表5 棧設(shè)計(jì)內(nèi)容、要求：生成一個(gè)順序表L對(duì)所生成的順序表L構(gòu)造二叉排序樹(shù)利用棧結(jié)構(gòu)實(shí)現(xiàn)中序遍歷二叉排序樹(shù)中序遍歷所構(gòu)造的二叉排序樹(shù)將記錄由小到大輸出步驟1 生成順序表L定義順序表：p22；利用算法2.3 InitList_Sq 初始化順

23、序表；利用算法2.4 ListInsert_Sq 生成順序表；數(shù)據(jù)元素個(gè)數(shù)和數(shù)據(jù)元素的值從鍵盤(pán)輸入；2 對(duì)所生成順序表L構(gòu)造二叉排序樹(shù)（1）定義二叉排序樹(shù) P127（2）初始化二叉排序樹(shù)為空樹(shù) BiTree T=NULL；（3）按待排序的順序表構(gòu)造二叉排序樹(shù) 利用算法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問(wèn)題描述： 設(shè)計(jì)一個(gè)交通咨詢系統(tǒng)，為自駕游旅行者客咨詢從任一個(gè)城市到另一個(gè)城市之間的最短路徑問(wèn)題。設(shè)計(jì)分三個(gè)部分，一是建立交通網(wǎng)絡(luò)圖的存儲(chǔ)結(jié)構(gòu)；二是解決單源最短路徑問(wèn)題；最后再實(shí)現(xiàn)兩個(gè)城市頂點(diǎn)之間的最短路徑問(wèn)題。題目4 交通咨詢系統(tǒng)(1) 數(shù)據(jù)存儲(chǔ)。 城市信息(城市名、代碼)、城市間的里程存儲(chǔ)于磁盤(pán)文件。建議把城市信息存于文件前面，交通信息存于文件的后面，用fread和fwrite函數(shù)