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

1、數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)8/8/20221數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)目錄課程設(shè)計(jì)1 線性表的逆置課程設(shè)計(jì)2 棧(1)課程設(shè)計(jì)2 棧(2)8/8/20222數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)序號(hào)實(shí)驗(yàn)項(xiàng)目名稱時(shí)數(shù)必開(kāi)選開(kāi)每套儀器人數(shù)目的要求實(shí)驗(yàn)類型1順序表3必開(kāi)1了解線性表的特性，以及它們?cè)趯?shí)際問(wèn)題中的應(yīng)用。掌握順序表的實(shí)現(xiàn)方法，以及它們的基本操作。驗(yàn)證2單鏈表3必開(kāi)1掌握單鏈表的基本操作：插入、刪除、查找等運(yùn)算。驗(yàn)證3循環(huán)鏈表3選開(kāi)1掌握循環(huán)鏈表的基本操作：插入、刪除、查找等運(yùn)算。設(shè)計(jì)4棧3必開(kāi)1了解棧的特性，以及它在實(shí)際問(wèn)題中的應(yīng)用。掌握棧的實(shí)現(xiàn)方法以及它的基本操作，學(xué)會(huì)運(yùn)用棧來(lái)解決問(wèn)題。驗(yàn)證8/8/20223數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)序

2、號(hào)實(shí)驗(yàn)項(xiàng)目名稱時(shí)數(shù)必開(kāi)選開(kāi)儀器人數(shù)目的要求實(shí)驗(yàn)類型5隊(duì)列3必開(kāi)1了解順序隊(duì)列和鏈隊(duì)列的特性，以及它們?cè)趯?shí)際問(wèn)題中的應(yīng)用。掌握鏈隊(duì)列的實(shí)現(xiàn)方法，以及它們的基本操作。驗(yàn)證6樹(shù)和二叉樹(shù)(1)3必開(kāi)1掌握二叉樹(shù)的結(jié)構(gòu)特征，進(jìn)一步掌握指針變量、動(dòng)態(tài)變量的含義以及二叉樹(shù)的各種存儲(chǔ)結(jié)構(gòu)的特點(diǎn)及遍歷方法；掌握用指針類型描述、訪問(wèn)和處理二叉樹(shù)的運(yùn)算。驗(yàn)證樹(shù)和二叉樹(shù)(2)3必開(kāi)1了解樹(shù)的一個(gè)應(yīng)用，掌握建立哈夫曼樹(shù)建立及應(yīng)用驗(yàn)證7線索樹(shù)3選開(kāi)1了解線索二叉樹(shù)的一個(gè)應(yīng)用，掌握線索樹(shù)建立、查找、刪除結(jié)點(diǎn)等操作及應(yīng)用設(shè)計(jì)8圖(1)3必開(kāi)1了解圖的結(jié)構(gòu)及存儲(chǔ)形式，掌握?qǐng)D的鄰接矩陣的存儲(chǔ)方式驗(yàn)證圖(2)3必開(kāi)1掌握?qǐng)D的基本存

3、儲(chǔ)方法；掌握?qǐng)D的深度優(yōu)先遍歷或廣度優(yōu)先遍歷方法并用高級(jí)語(yǔ)言實(shí)現(xiàn)方法。驗(yàn)證9最小生成樹(shù)3選開(kāi)1了解最小生成樹(shù)生成方法，掌握用高級(jí)語(yǔ)言實(shí)現(xiàn)最小生成樹(shù)的方法。驗(yàn)證8/8/20224數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)序號(hào)實(shí)驗(yàn)項(xiàng)目名稱時(shí)數(shù)必開(kāi)選開(kāi)儀器人數(shù)目的要求實(shí)驗(yàn)類型10最短路徑3選開(kāi)1了解路徑的概念及實(shí)現(xiàn)的算法，掌握用高級(jí)語(yǔ)言實(shí)現(xiàn)最短路徑的算法。驗(yàn)證11排序（含排序1、排序2）6必開(kāi)1掌握常用的排序方法，并掌握用高級(jí)語(yǔ)言實(shí)現(xiàn)排序算法的方法；深刻理解排序的定義和各種排序方法的特點(diǎn)，并能加以靈活應(yīng)用；了解各種方法的排序過(guò)程，并掌握各種排序方法的時(shí)間復(fù)雜度的分析方法。驗(yàn)證12查找（含查找1、查找2）6必開(kāi)1了解線性表的查找

4、方法，用一種查找方法實(shí)現(xiàn)對(duì)給定鍵值的查找，并能用高級(jí)語(yǔ)言實(shí)現(xiàn)查找算法。驗(yàn)證13大型作業(yè)18必開(kāi)1綜合以上知識(shí)，給出若干個(gè)題目，由學(xué)生任選一題，然后分析題意、查閱資料、設(shè)計(jì)算法、調(diào)試編程直到解決問(wèn)題，并寫(xiě)出課程設(shè)計(jì)總結(jié)報(bào)告上交，最后進(jìn)行面試、評(píng)分。綜合8/8/20225數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)成績(jī)?cè)u(píng)定學(xué)生上交的課程設(shè)計(jì)的實(shí)驗(yàn)報(bào)告和編程質(zhì)量占總成績(jī)的50%，大作業(yè)和編程質(zhì)量總成績(jī)的占50%，成績(jī)不合格者重修。課程設(shè)計(jì)最終成績(jī)分為“優(yōu)秀”、“良好”、“中等”、“及格”、“不及格”五級(jí)。 要求：實(shí)驗(yàn)報(bào)告用16開(kāi)紙，手寫(xiě)8/8/20226數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)課程設(shè)計(jì)1 線性表的逆置P158加頭文件#include

5、Insert_sqlist函數(shù)Else if (il-last+1) Else if (il-last+1)8/8/20227數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)P159Print_sqlist函數(shù)for(i=0;ilast-1;i+)for(i=0;ilast;i+)Inverse_sqlist函數(shù)J=L-last-1-i;J=L-last-i;8/8/20228數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)P161Void print(head)Linklist *head;Void print(linklist *head)8/8/20229數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)線性表1、順序表的就地逆置方法32、單鏈表的就地逆置選做題設(shè)A和B是兩個(gè)單鏈表，

6、其表中元素遞增有序。試寫(xiě)一算法將A和B歸并成一個(gè)按元素值遞減有序的單鏈表C，并要求輔助空間為O(1)，請(qǐng)分析算法的時(shí)間復(fù)雜度。8/8/202210數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)課程設(shè)計(jì)2 棧(1)題目1 P165 用棧逆置一個(gè)線性表。題目2 設(shè)計(jì)算法判斷一個(gè)算術(shù)表達(dá)式的三種括號(hào)是否正確配對(duì)。 (提示： 對(duì)表達(dá)式進(jìn)行掃描，凡遇到( 就進(jìn)棧，遇) 就退掉棧頂?shù)脑兀遗袛嗯c當(dāng)前掃描到的字符是否匹配？如果匹配，繼續(xù)掃描；否則，沒(méi)有正確配對(duì)，停止掃描表達(dá)式，返回FALSE。表達(dá)式掃描完畢，如果棧應(yīng)為空，則返回TRUE)二選一8/8/202211數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)課程設(shè)計(jì)2 棧(2)題目一P168設(shè)兩個(gè)順序棧共享存儲(chǔ)空

7、間，試寫(xiě)出兩個(gè)棧公用的棧操作算法push(s,x,k)和pop(s,x,k),其中k為0或1，分別用來(lái)表示兩個(gè)不同的棧號(hào)。請(qǐng)寫(xiě)一個(gè)完整的程序?qū)崿F(xiàn)之。題目二設(shè)字符串train代表火車(chē)的座位席，其中，H表示硬席,S表示軟席，試將S調(diào)到H的前面，并輸出調(diào)整后的train字符串。train=“HHSHSHHH”train=“SSHHHHHH”要求用棧實(shí)現(xiàn)二選一8/8/202212數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)順序棧存儲(chǔ)結(jié)構(gòu)的描述：#define Maxsize 100 /*設(shè)順序棧的最大長(zhǎng)度為100，可依實(shí)現(xiàn)情況而修改*/typedef int datatype;typedef structdatatype sta

8、ckMaxsize;int top； /*棧頂指針*/SeqStack； /*順序棧類型定義*/SeqStack *s； /*s為順序棧類型變量的指針*/8/8/202213數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)構(gòu)造一個(gè)空順序棧 SeqStack * InitStack( ) SeqStack *S ;S=(SeqStack *)malloc(sizeof(SeqStack);if (!S) /*空間申請(qǐng)失敗*/ printf(“空間不足”)；return NULL; elseS-top=0; return S; 8/8/202214數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)取順序棧棧頂元素datatype GetTop(SeqStack

9、*S) if (S-top=0)printf(n棧是空的!); return FALSE; elsereturn S-stackS-top-1; 8/8/202215數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)判別空棧int StackEmpty(SeqStack *S) if (S-top=0)return TRUE;elsereturn FALSE; 8/8/202216數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)順序棧的入棧操作例如用堆棧存放（A，B，C，D）AACBABAtop核心語(yǔ)句：順序棧入棧函數(shù)PUSH（）SeqStack*Push(SeqStack *S，datatype x) if (S-top=Maxsize)return NU

10、LL; else S-stackS-top=x;S-top+; return S; Push (s,B);Push (s,C);Push (s,D);toptoptoptop低地址LPush (s,A);高地址MBCD8/8/202217數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)順序棧出棧操作例如從棧中取出BDCBAtoptopDCABDCBAtopDCBAtop低地址L高地址MD核心語(yǔ)句：pop ( );順序棧出棧函數(shù)POP( )datatype pop( SeqStack *S) if (S-top= =0) printf(nThe sequence stack is empty!);return FALSE; S

11、-top-;return S-stackS-top; pop ( );printf( pop () );8/8/202218數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)兩個(gè)棧的共享技術(shù)： 利用了?！皸５孜恢貌蛔?，而棧頂位置動(dòng)態(tài)變化”的特性。為兩個(gè)棧申請(qǐng)一個(gè)共享的一維數(shù)組空間SM，將兩個(gè)棧的棧底分別放在一維數(shù)組的兩端，分別是0， M-1。 由于兩個(gè)棧頂動(dòng)態(tài)變化，可以形成互補(bǔ)，使得每個(gè)?？捎玫淖畲罂臻g與實(shí)際使用的需求有關(guān)。兩棧共享比兩個(gè)棧分別申請(qǐng)M/2的空間利用率高。 兩棧共享的數(shù)據(jù)結(jié)構(gòu)定義如下： typedef int datatype；/棧元素的數(shù)據(jù)類型，假設(shè)為整型int maxsize100；/棧的容量，元素最多不能超

12、過(guò)它typedef struct datatype datamaxsize； int top2；sqstack；/順序棧類型定義8/8/202219數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)（圖） 共享?xiàng)?8/8/202220數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)(1)初始化操作void InitStack(sqstack *S) S-top0= -1; S-top1= M; 8/8/202221數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)(2)入棧操作int Push(sqstack *s, datatype x, int k)/s是指向棧類型的指針，x是將要入棧的數(shù)據(jù)，k是棧號(hào)if (s-top0+1= = s-top1) printf(“兩個(gè)棧均滿，不能進(jìn)棧！”

13、)；return 0;/改棧頂指針加1或減1，來(lái)選擇不滿的棧if（k = = 0）s-topk+; else s-topk-；/將x插入當(dāng)前棧頂s-datas-topk = x; return 1； 8/8/202222數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)(3)出棧操作int pop(sqstack * S，datatype *x，int k)/出棧操作，棧頂元素由參數(shù)返回if (k = 0&s-top0 = -1)|( k =1&s-top1 = = maxsize)printf(“棧空，不能退棧！”)；return -1;*x = s-datas-topk; /取出棧頂元素值給X if（k = = 0）s-t

14、opk-; /改棧頂指針加1或減1else S-topk+；return 1;8/8/202223數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)主程序編寫(xiě)輸入部分：雙重循環(huán)，外層輸入棧號(hào)，內(nèi)層輸入數(shù)據(jù)。輸出部分：分別將兩個(gè)棧中的內(nèi)容輸出。先打印棧號(hào)，再打印數(shù)據(jù)。測(cè)試數(shù)據(jù)：P1688/8/202224數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)課程設(shè)計(jì)（3）-隊(duì)列8/8/202225數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)隊(duì)列的特性FIFO8/8/202226數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)1、順序隊(duì)列約定：若隊(duì)列不空，隊(duì)頭指針front，指向隊(duì)頭元素。隊(duì)尾指針rear，指向隊(duì)尾元素的下一個(gè)位置。8/8/202227數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)順序隊(duì)的幾種狀態(tài)示意圖頭指針始終指向隊(duì)頭元素，尾指針始終指向

15、隊(duì)尾元素的下一個(gè)元素為了防止出現(xiàn)假溢出，即在假溢出時(shí)，還能進(jìn)行入隊(duì)操作，我們采取循環(huán)隊(duì)列。8/8/202228數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)在出隊(duì)時(shí)：隊(duì)頭指針也要采用front=(front+1)%MAXSIZE循環(huán)隊(duì)列示意圖在入隊(duì)時(shí)：將數(shù)據(jù)區(qū)data0MAXSIZE-1看成是首尾相接的圓環(huán),當(dāng)入隊(duì)到Maxsize-1時(shí),若隊(duì)頭元素的前面仍有空閑位置,下一個(gè)地址就應(yīng)翻轉(zhuǎn)為0,使data0接在dataMAXSIZE-1之后, 通過(guò)求余運(yùn)算rear=(rear+1)%MAXSIZE來(lái)求得。8/8/202229數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)循環(huán)隊(duì)列的幾種狀態(tài)在循環(huán)隊(duì)列中當(dāng)采用入隊(duì)操作: rear=(rear+1)%MAXSIZ

16、E出隊(duì)操作: front=(front+1)%MAXSIZE新問(wèn)題：空隊(duì)和隊(duì)滿時(shí)都有front=rear,那么又如何判斷隊(duì)空和隊(duì)滿？8/8/202230數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)J2 J3J1 J4 J5frontrear解決方案-人為浪費(fèi)一個(gè)單元：大小為MAXSIZE的數(shù)組，只存MAXSIZE-1個(gè)結(jié)點(diǎn)。約定：front和rear二者之一指向?qū)嵲?，另一個(gè)指向空閑元素(假設(shè)front指向隊(duì)頭元素，rear指向隊(duì)尾元素的下一個(gè)位置，即rear 所指的單元始終為空）。隊(duì)空條件 : front = = rear (初始化時(shí)：front=rear)隊(duì)滿條件： front=（rear+1)%N (N=MAXSI

17、ZE)隊(duì)列長(zhǎng)度（即數(shù)據(jù)元素個(gè)數(shù)）：L=（Nrearfront）% N 8/8/202231數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)循環(huán)隊(duì)列循環(huán)隊(duì)列類型定義：#define MAXSIZE 100 /*隊(duì)列的最大元素?cái)?shù)為100*/typedef struct /*定義循環(huán)隊(duì)列*/ datatype dMAXSIZE; int front; /*頭指針,若隊(duì)列不空,則指向隊(duì)頭元素*/ int rear; /*尾指針,若隊(duì)列不空,則指向隊(duì)尾元素的下一位置*/ sequeue;sequeue *Q;8/8/202232數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)循環(huán)隊(duì)列的基本操作實(shí)現(xiàn)建循環(huán)隊(duì)列循環(huán)隊(duì)列入隊(duì)循環(huán)隊(duì)列的出隊(duì)循環(huán)隊(duì)列的判空8/8/202233

18、數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)建循環(huán)隊(duì)列void InitQueue(sequeue *Q) /*構(gòu)造一個(gè)空隊(duì)列Q*/ Q-front = Q-rear=0;8/8/202234數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)循環(huán)隊(duì)列入隊(duì)操作sequeue *EnQueue(sequeue *Q, datatype x) /*入隊(duì)*/if(Q-rear+1)% MAXSIZE= Q-front) printf(“隊(duì)列已滿，不能入隊(duì)！n”)； return NULL; else dQ-rear=x; /*將x插入隊(duì)尾*/ Q-rear =(Q-rear+1)% MAXSIZE; /*隊(duì)尾指針后移*/ return Q; 8/8/202235

19、數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)循環(huán)隊(duì)列的出隊(duì)操作datatype DeQueue(sequeue *Q) /*出隊(duì)列*/datatype y; if(Q-front= Q-rear) printf(“隊(duì)列為空，無(wú)法出隊(duì)！n”)； return 0; else y= Q-dQ-front; /*隊(duì)頭元素出隊(duì)，存入y中*/ Q-front=(Q-front+1)%MAXSIZE; /*隊(duì)頭指針后移*/ return y; 8/8/202236數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)循環(huán)隊(duì)列的判空操作int QueueEmpty(sequeue *Q)if(Q-front= Q-rear) return 1; /*隊(duì)列為空時(shí)返回1*/

20、else return 0; /*隊(duì)列非空時(shí)返回0*/8/8/202237數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)2、鏈隊(duì)列#define NULL 0typedef struct node /*定義鏈隊(duì)列結(jié)點(diǎn)類型*/ datatype data; struct node *next; linkqueue;typedef struct /*封裝隊(duì)頭指針和隊(duì)尾指針*/ linkqueue *front; /*定義隊(duì)頭指針*/ linkqueue *rear; /*定義隊(duì)尾指針*/ Lqueue; 8/8/202238數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)鏈隊(duì)的幾種狀態(tài)示意圖：(1)空鏈隊(duì)的特征？front=rear(2) 鏈隊(duì)會(huì)滿嗎？一般不

21、會(huì)，因?yàn)閯h除時(shí)有free動(dòng)作。除非內(nèi)存不足！(b)元素x入隊(duì)(d)元素x出隊(duì)此時(shí)，front= =rear修改rear指針修改頭結(jié)點(diǎn)的指針域8/8/202239數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)(3) 怎樣實(shí)現(xiàn)鏈隊(duì)的入隊(duì)和出隊(duì)操作？若設(shè)p所指結(jié)點(diǎn)為入隊(duì)或出隊(duì)結(jié)點(diǎn)入隊(duì)（尾部插入）：rear-next=p; rear=p;出隊(duì)（頭部刪除）：front-next=p-next;8/8/202240數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)鏈隊(duì)列基本操作的實(shí)現(xiàn)構(gòu)造一個(gè)空鏈隊(duì)鏈隊(duì)入隊(duì)鏈隊(duì)出隊(duì)判空隊(duì)列8/8/202241數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)構(gòu)造一個(gè)空鏈隊(duì)操作void InitQueue(Lqueue *Q) Q-front=(linkqueue *)m

22、alloc(sizeof(linkqueue);if(!Q-front)printf(“Overflow!”);/*存儲(chǔ)分配失敗*/elseQ-front-next =NULL;Q-rear = Q-front;8/8/202242數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)鏈隊(duì)入隊(duì)操作linkqueue *EnQueue(Lqueue *Q, datatype x)linkqueue *p; p=(linkqueue *)malloc(sizeof(linkqueue);/*開(kāi)辟新結(jié)點(diǎn)*/ if(!p)printf(“Overflow!”);return NULL; /*存儲(chǔ)分配失敗*/ elsep-data=x; p

23、-next= NULL;Q-rear-next=p; Q-rear=p; return Q;8/8/202243數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)鏈隊(duì)出隊(duì)操作datatype DeQueue(Lqueue *Q)datatype y; linkqueue *p; if(Q-rear = Q-front) printf(“隊(duì)列為空，無(wú)法出隊(duì)！n”)； return -1; else p=Q-front-next; y=p-data; /*隊(duì)頭元素存入y*/ Q-front-next=p-next; /*隊(duì)頭指針后移*/ if(Q-rear=p) Q-rear=Q-front; /*出隊(duì)后為空隊(duì)*/ free(p)

24、; /*釋放存儲(chǔ)空間*/ return y; 8/8/202244數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)判空隊(duì)列函數(shù)int QueueEmpty(Lqueue *Q)if(Q-rear=Q-front) return 1; /*隊(duì)列為空時(shí)返回1*/else return 0; /*隊(duì)列非空時(shí)返回0*/ 8/8/202245數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)設(shè)計(jì)題目請(qǐng)?jiān)O(shè)計(jì)一個(gè)算法，用一個(gè)棧S將一個(gè)隊(duì)列Q逆置。要求：采用鏈棧和鏈隊(duì)列來(lái)實(shí)現(xiàn)。調(diào)試運(yùn)行實(shí)例： 含多個(gè)元素的隊(duì)列（2，4，6，8，10）； 含一個(gè)元素的隊(duì)列（5）； 空隊(duì)列（）。 8/8/202246數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)解題思路8/8/202247數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)課程設(shè)計(jì)4 Huff

25、man樹(shù)8/8/202248數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)例:a7b5c2d4a7b5c2d46a7b5c2d4611a7b5c2d4611188/8/202249數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)8/8/202250數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)8/8/202251數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)Huffman樹(shù)的定義#define n 7 /n為葉子結(jié)點(diǎn)個(gè)數(shù)#define m 2*n-1 /m為哈夫曼樹(shù)的結(jié)點(diǎn)總數(shù)#define MAXVAL 999 /最小權(quán)值初始化用typedef int datatype;typedef struct char ch;/存放的字符float weight; /權(quán)值datatype lchild,rchild,par

26、ent; /左右孩子域和雙親 hufmtree;8/8/202252數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)必做題目題目一對(duì)于給定的n個(gè)結(jié)點(diǎn)的權(quán)值，建立一棵哈夫曼樹(shù)。具體要求如下：算法輸入：n個(gè)結(jié)點(diǎn)的權(quán)值。算法輸出：哈夫曼樹(shù)，打印出哈夫曼樹(shù)的所有的結(jié)點(diǎn)序號(hào)、雙親結(jié)點(diǎn)、左孩子、右孩子和權(quán)值。測(cè)試數(shù)據(jù)：結(jié)點(diǎn)數(shù)n=7，權(quán)值為7、5、2、3、8、10、20；結(jié)點(diǎn)數(shù)n=8，權(quán)值為7、19、2、6、32、3、21、10。 8/8/202253數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)Huffman算法的應(yīng)用（一）題目二輸入一串字符，根據(jù)不同字符的出現(xiàn)頻率構(gòu)造字符的Huffman編碼。（1）編碼：將輸入字符串按 Huffman編碼輸出（可放到一個(gè)文件里）。

27、（2）解碼：輸入按某Huffman編碼的01串，進(jìn)行譯碼，輸出譯碼后的字符。8/8/202254數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)編碼如圖所示，輸入“hhhhhhhuffffffffman”之后，先輸出每個(gè)字符的編碼，然后輸出整個(gè)字符串的編碼“11111111111111101100000000100110001010”,共38位。8/8/202255數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)解碼輸入“11101100100110001010”輸出“huffman”8/8/202256數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)Huffman算法的應(yīng)用（二）題目三輸入一串字符，根據(jù)不同字符的出現(xiàn)頻率構(gòu)造字符的Huffman編碼。（1）編碼：將輸入字符串按 Huff

28、man編碼輸出到一個(gè)文件里，要求將“0”“1”作為二進(jìn)制的“0”“1”寫(xiě)入到文件里。提示：需要二進(jìn)制到十進(jìn)制的轉(zhuǎn)換。（2）解碼：輸入按某Huffman編碼的文件，進(jìn)行譯碼，輸出譯碼后的字符。提示：需要十進(jìn)制到二進(jìn)制的轉(zhuǎn)換。8/8/202257數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)編碼如圖所示，輸入“hhhhhhhuffffffffman”之后，輸出整個(gè)字符串的編碼“11111111111111101100000000100110001010 0000000110”“255 254 192 54 40 6”(寫(xiě)入文件的內(nèi)容)最后2個(gè)字節(jié)：一個(gè)用來(lái)存放部分有效編碼，后面一個(gè)字節(jié)用來(lái)指示前面的一個(gè)字節(jié)中有效編碼的位數(shù)（取

29、值18）。每8位二進(jìn)制數(shù)可以用一個(gè)short型的無(wú)符號(hào)整數(shù)來(lái)表示，整個(gè)編碼應(yīng)該占6個(gè)字節(jié)，而如果用ASCII編碼的話，18個(gè)字符需要占18個(gè)字節(jié)。8/8/202258數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)解碼輸入“255 254 192 54 40 6”輸出“hhhhhhhuffffffffman”8/8/202259數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)要求時(shí)間：兩次課（本周及下周）題目一必做題目二、三選1個(gè)做8/8/202260數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)圖實(shí)驗(yàn)一對(duì)給出的無(wú)向圖，編寫(xiě)一個(gè)完整的程序，建立其鄰接矩陣，并輸出此鄰接矩陣。實(shí)驗(yàn)二編寫(xiě)一個(gè)用菜單驅(qū)動(dòng)的完整的程序，建立無(wú)向圖的鄰接表，要求其鄰接表中的結(jié)點(diǎn)按頂點(diǎn)序號(hào)從大到小順序排列。實(shí)驗(yàn)三編

30、寫(xiě)一個(gè)用菜單驅(qū)動(dòng)的完整的程序?qū)崿F(xiàn)，建立有向圖G的鄰接表。編一個(gè)函數(shù)根據(jù)用戶輸入的偶對(duì)（以輸入0表示結(jié)束）建立有向圖G的鄰接表，并輸出這個(gè)鄰接表。實(shí)驗(yàn)四編寫(xiě)一個(gè)用菜單驅(qū)動(dòng)的完整的程序?qū)崿F(xiàn)，利用深度優(yōu)先搜索方法求出無(wú)向圖中通過(guò)給定點(diǎn)Vi的簡(jiǎn)單回路（鄰接表存儲(chǔ)）。 實(shí)驗(yàn)五： 編寫(xiě)一個(gè)用菜單驅(qū)動(dòng)的完整的程序?qū)崿F(xiàn)圖的深度優(yōu)先遍歷的非遞歸算法。8/8/202261數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)無(wú)向圖及其鄰接矩陣、鄰接表8/8/202262數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)要求選擇一（五選二）請(qǐng)你任選兩個(gè)題目，將它們編寫(xiě)在一個(gè)完整的程序中（兩周內(nèi)完成）。選擇二（三選二）三、四、五題中任選二題，對(duì)所選的每道題單獨(dú)編成完整程序（每周完成一個(gè)）

31、。8/8/202263數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)查找線性表的查找基本知識(shí)點(diǎn)：線性表的數(shù)據(jù)類型定義、查找操作8/8/202264數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)一、順序查找(Sequential Search) 基本思想是：從表的一端開(kāi)始，順序掃描線性表，依次將掃描到的結(jié)點(diǎn)關(guān)鍵字和給定值K相比較。若當(dāng)前掃描到的結(jié)點(diǎn)關(guān)鍵字與K相等，則查找成功；若掃描結(jié)束后，仍未找到關(guān)鍵字等于K的結(jié)點(diǎn)，則查找失敗。8/8/202265數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)又稱折半查找，它是一種效率較高的查找方法。要求：要求線性表是有序表，即表中結(jié)點(diǎn)按關(guān)鍵字有序，并且要用向量作為表的存儲(chǔ)結(jié)構(gòu)。二、二分查找 8/8/202266數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)Low是查找的開(kāi)始位置，high是查找的結(jié)束位置二分查找的基本思想是：（1）首先確定該區(qū)間的中點(diǎn)位置： mid = （2）然后將中間位置記錄的鍵值Rmid.key和所給關(guān)鍵字K進(jìn)行比較：若相等，則查找成功并返回此位置，否則須確定新的查找區(qū)間，繼續(xù)二分查找。8/8/202267數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)二分查找判定樹(shù)的組成如對(duì)表R3，7，11，1