數(shù)據(jù)結(jié)構課程設計課件

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

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

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

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

5、Insert_sqlist函數(shù)Else if (il-last+1) Else if (il-last+1)8/8/20227數(shù)據(jù)結(jié)構課程設計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é)構課程設計P161Void print(head)Linklist *head;Void print(linklist *head)8/8/20229數(shù)據(jù)結(jié)構課程設計線性表1、順序表的就地逆置方法32、單鏈表的就地逆置選做題設A和B是兩個單鏈表，

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

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

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

9、*S) if (S-top=0)printf(n棧是空的!); return FALSE; elsereturn S-stackS-top-1; 8/8/202215數(shù)據(jù)結(jié)構課程設計判別空棧int StackEmpty(SeqStack *S) if (S-top=0)return TRUE;elsereturn FALSE; 8/8/202216數(shù)據(jù)結(jié)構課程設計順序棧的入棧操作例如用堆棧存放（A，B，C，D）AACBABAtop核心語句：順序棧入棧函數(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é)構課程設計順序棧出棧操作例如從棧中取出BDCBAtoptopDCABDCBAtopDCBAtop低地址L高地址MD核心語句：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é)構課程設計兩個棧的共享技術： 利用了?！皸５孜恢貌蛔?，而棧頂位置動態(tài)變化”的特性。為兩個棧申請一個共享的一維數(shù)組空間SM，將兩個棧的棧底分別放在一維數(shù)組的兩端，分別是0， M-1。 由于兩個棧頂動態(tài)變化，可以形成互補，使得每個?？捎玫淖畲罂臻g與實際使用的需求有關。兩棧共享比兩個棧分別申請M/2的空間利用率高。 兩棧共享的數(shù)據(jù)結(jié)構定義如下： typedef int datatype；/棧元素的數(shù)據(jù)類型，假設為整型int maxsize100；/棧的容量，元素最多不能超

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

13、)；return 0;/改棧頂指針加1或減1，來選擇不滿的棧if（k = = 0）s-topk+; else s-topk-；/將x插入當前棧頂s-datas-topk = x; return 1； 8/8/202222數(shù)據(jù)結(jié)構課程設計(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é)構課程設計主程序編寫輸入部分：雙重循環(huán)，外層輸入棧號，內(nèi)層輸入數(shù)據(jù)。輸出部分：分別將兩個棧中的內(nèi)容輸出。先打印棧號，再打印數(shù)據(jù)。測試數(shù)據(jù)：P1688/8/202224數(shù)據(jù)結(jié)構課程設計課程設計（3）-隊列8/8/202225數(shù)據(jù)結(jié)構課程設計隊列的特性FIFO8/8/202226數(shù)據(jù)結(jié)構課程設計1、順序隊列約定：若隊列不空，隊頭指針front，指向隊頭元素。隊尾指針rear，指向隊尾元素的下一個位置。8/8/202227數(shù)據(jù)結(jié)構課程設計順序隊的幾種狀態(tài)示意圖頭指針始終指向隊頭元素，尾指針始終指向

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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