數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)

PAGE4實(shí)驗(yàn)項(xiàng)目名稱：線性表（實(shí)驗(yàn)一）實(shí)驗(yàn)?zāi)康?1)了解線性表的邏輯結(jié)構(gòu)特性是數(shù)據(jù)元素之間存在著線性關(guān)系，在計(jì)算機(jī)中表示這種關(guān)系有順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)；(2)掌握這兩種存儲(chǔ)結(jié)構(gòu)的描述方法；(3)掌握線性表的基本操作（查找、插入、刪除）；(4)考慮時(shí)間和空間復(fù)雜度設(shè)計(jì)算法。2、實(shí)驗(yàn)內(nèi)容（1）創(chuàng)建一個(gè)順序表，存放在數(shù)組A[N]中，元素的類型為整型，設(shè)計(jì)算法調(diào)整A，使其左邊的所有元素小于0，右邊的所有元素大于0（要求算法的時(shí)間復(fù)雜度和空間復(fù)雜度均為O(n)）。建立一個(gè)循環(huán)單鏈表，其節(jié)點(diǎn)有l(wèi)eft,data和right三個(gè)域，其中data為數(shù)據(jù)域，存放元素的有效信息，right域?yàn)橹羔樣颍赶蚝罄^節(jié)點(diǎn)，left為指針域，它的值為NULL。編寫(xiě)一個(gè)算法將此表改為循環(huán)雙鏈表。實(shí)驗(yàn)項(xiàng)目名稱：棧（實(shí)驗(yàn)二）、實(shí)驗(yàn)?zāi)康?1)理解棧的定義、特點(diǎn)及與線性表的異同；(2)熟悉順序棧的組織方法，棧滿、?？盏呐袛鄺l件及其描述；(3)掌握棧的基本操作（進(jìn)棧、退棧等）。2、實(shí)驗(yàn)內(nèi)容(1)設(shè)計(jì)一個(gè)算法，將一般算術(shù)表達(dá)式轉(zhuǎn)化為逆波蘭表達(dá)式，并求逆波蘭表達(dá)式的值。(2)設(shè)計(jì)兩個(gè)棧S1、S2都采用順序棧方式，并且共享一個(gè)存儲(chǔ)區(qū)[0，MaxLen-1]，為了盡量利用空間，減少溢出的可能，可采用棧頂相向、迎面增長(zhǎng)的存儲(chǔ)方式，如下圖所示。設(shè)計(jì)一個(gè)有關(guān)棧的入棧和出棧算法。實(shí)驗(yàn)項(xiàng)目名稱：隊(duì)列（實(shí)驗(yàn)三）、實(shí)驗(yàn)?zāi)康?1)理解隊(duì)列的定義、特點(diǎn)及與線性表的異同；(2)熟悉隊(duì)列的組織方法，隊(duì)列滿、隊(duì)列空的判斷條件及其描述；(3)掌握隊(duì)列的基本操作（入隊(duì)、出隊(duì)等）。2、實(shí)驗(yàn)內(nèi)容(1)假設(shè)以數(shù)組sequ[MaxSise]存放環(huán)形隊(duì)列的元素，同時(shí)rear和len分別指示環(huán)形隊(duì)列中隊(duì)尾元素的位置和內(nèi)含元素的個(gè)數(shù)。設(shè)計(jì)相應(yīng)的入隊(duì)和出隊(duì)算法。(2)某汽車輪渡口，過(guò)江渡船每次能載10輛車過(guò)江。過(guò)江車輛分別為客車類和貨車類，上船有如下規(guī)定：同類車先到先上船，客車先于貨車上渡船，且每上4輛客車，才允許上一輛貨車；若等待客車不足4輛則以貨車代替；若無(wú)貨車等待則允許客車都上船。設(shè)計(jì)一個(gè)算法模擬渡口管理。實(shí)驗(yàn)項(xiàng)目名稱：二叉樹(shù)（實(shí)驗(yàn)四）1、實(shí)驗(yàn)?zāi)康?1)掌握二叉樹(shù)的結(jié)構(gòu)特性和二叉鏈表存儲(chǔ)結(jié)構(gòu)；(2)理解二叉樹(shù)、完全二叉樹(shù)、滿二叉樹(shù)的概念和存儲(chǔ)特點(diǎn)；(3)掌握二叉樹(shù)遍歷的遞歸和非遞歸方法。2、實(shí)驗(yàn)內(nèi)容（1）假設(shè)二叉樹(shù)采用鏈接存儲(chǔ)方式存儲(chǔ)，分別編寫(xiě)一個(gè)二叉樹(shù)先序遍歷的遞歸算法和非遞歸算法。（2）一棵完全二叉樹(shù)以順序方式存儲(chǔ)，設(shè)計(jì)一個(gè)遞歸算法，對(duì)該完全二叉樹(shù)進(jìn)行中序遍歷。實(shí)驗(yàn)項(xiàng)目名稱：哈夫曼樹(shù)（實(shí)驗(yàn)五）1、實(shí)驗(yàn)?zāi)康?1)理解哈夫曼樹(shù)的概念、結(jié)構(gòu)特性和哈夫曼編碼原理；(2)掌握構(gòu)造哈夫曼樹(shù)的基本方法；(3)掌握運(yùn)用哈夫曼樹(shù)進(jìn)行哈夫曼編碼的方法；2、實(shí)驗(yàn)內(nèi)容根據(jù)哈夫曼(Huffman)編碼的原理，編寫(xiě)一個(gè)程序，在用戶輸入節(jié)點(diǎn)權(quán)重的基礎(chǔ)上建立它的哈夫曼編碼。實(shí)驗(yàn)項(xiàng)目名稱：圖（實(shí)驗(yàn)六）1、實(shí)驗(yàn)?zāi)康?1)理解圖的基本概念、圖的結(jié)構(gòu)特性；(2)掌握鄰接表表示圖的基本方法；(3)掌握連通圖遍歷的基本的方法。2、實(shí)驗(yàn)內(nèi)容(1)用鄰接表存儲(chǔ)一個(gè)圖G。分別設(shè)計(jì)實(shí)現(xiàn)下列要求的算法：-求出圖G中每個(gè)頂點(diǎn)的出度；-求出圖G中出度最大的一個(gè)頂點(diǎn)，輸出該頂點(diǎn)的編號(hào)；-計(jì)算圖G中出度為0的頂點(diǎn)數(shù)。(2)編寫(xiě)一個(gè)實(shí)現(xiàn)連通圖G的深度優(yōu)先遍歷（從頂點(diǎn)V0出發(fā)，以鄰接矩陣為存儲(chǔ)結(jié)構(gòu)）的遞歸和非遞歸函數(shù)，分別用這兩種方法對(duì)圖進(jìn)行深度優(yōu)先遍歷，比較遍歷結(jié)果。實(shí)驗(yàn)項(xiàng)目名稱：圖（實(shí)驗(yàn)七）1、實(shí)驗(yàn)?zāi)康?1)理解拓?fù)渑判虻幕靖拍詈屯負(fù)渑判虻膶?shí)用意義；(2)掌握AOV-網(wǎng)解決拓?fù)渑判騿?wèn)題的基本方法。(3)理解最小生成樹(shù)的基本概念和實(shí)用意義；(4)掌握利用MST性質(zhì)構(gòu)造最小生成樹(shù)的prim算法和Kruskal算法。2、實(shí)驗(yàn)內(nèi)容(1)教學(xué)計(jì)劃編制問(wèn)題。按先修課程和后續(xù)課程關(guān)系，編制一個(gè)簡(jiǎn)單的排課計(jì)劃程序。(2)在n個(gè)城市之間架設(shè)n-1條線路，要求建設(shè)代價(jià)最小。編寫(xiě)完整算法構(gòu)造最小生成樹(shù)。實(shí)驗(yàn)項(xiàng)目名稱：查找（實(shí)驗(yàn)八）1、實(shí)驗(yàn)?zāi)康?1)理解查找表的基本概念，定義、分類和各類的特點(diǎn)；(2)掌握哈希表的構(gòu)造方法以及解決沖突的方法；(3)掌握哈希存儲(chǔ)和哈希查找的基本思想及有關(guān)方法。2、實(shí)驗(yàn)內(nèi)容使用哈希函數(shù)：H（K）=3KMOD11并采用鏈地址法處理沖突。試對(duì)關(guān)鍵字序列（22，41，53，46，30，13，01，67）構(gòu)造哈希表，設(shè)計(jì)構(gòu)造哈希表的完整算法。實(shí)驗(yàn)項(xiàng)目名稱：排序（實(shí)驗(yàn)九）1、實(shí)驗(yàn)?zāi)康?1)理解各類內(nèi)部排序的基本思想；(2)掌握各類內(nèi)部排序的基本方法；(3)了解各類內(nèi)部排序的優(yōu)缺點(diǎn)。2、實(shí)驗(yàn)內(nèi)容(1)編寫(xiě)一個(gè)雙向冒泡排序算法，即在排序過(guò)程中以交替的正、反兩個(gè)方向進(jìn)行遍歷。若第一趟把關(guān)鍵字最大的記錄放到最末尾，則第二趟把關(guān)鍵字最小的記錄放到最前端，如此反復(fù)進(jìn)行之。(2)設(shè)計(jì)一個(gè)進(jìn)行堆排序的算法。實(shí)驗(yàn)項(xiàng)目名稱：自主設(shè)計(jì)應(yīng)用實(shí)例（可選）指導(dǎo)思想：訓(xùn)練學(xué)生自主學(xué)習(xí)、綜合知識(shí)和查閱、收集資料的能力。通過(guò)自主學(xué)習(xí)、查閱和收集所需的知識(shí)點(diǎn)完成。給學(xué)生充分展示才華的舞臺(tái)，對(duì)學(xué)生設(shè)計(jì)的軟件作品要提供一個(gè)自由展示的平臺(tái)、互動(dòng)交流的平臺(tái)，可以大大提高學(xué)生的學(xué)習(xí)激情和科學(xué)研究的精神，也能顯著提高學(xué)習(xí)效果。實(shí)驗(yàn)?zāi)康募耙螅簽檫M(jìn)一步提高教與學(xué)的效果，在各個(gè)章節(jié)的基本編程訓(xùn)練的基礎(chǔ)上，再結(jié)合課程重點(diǎn)和難點(diǎn)進(jìn)行較大軟件編制的選題，并在具體題目上提倡與實(shí)際應(yīng)用相結(jié)合并由學(xué)生自主選題，教師審核。說(shuō)明：在線性表、棧、隊(duì)列、二叉樹(shù)、圖、查找和排序等實(shí)驗(yàn)項(xiàng)目中選擇