1、程序技術(shù)基礎(chǔ)課程實(shí)驗(yàn)指導(dǎo)課程代碼：070050 開課學(xué)期：4開課專業(yè)：信管類總學(xué)時(shí)/實(shí)驗(yàn)學(xué)時(shí)：64/32總學(xué)分/實(shí)驗(yàn)學(xué)分：4/2一、課程簡(jiǎn)介數(shù)據(jù)結(jié)構(gòu)是計(jì)算機(jī)各專業(yè)的重要技術(shù)基礎(chǔ)課。在計(jì)算機(jī)科學(xué)中，數(shù)據(jù)結(jié)構(gòu)不僅是一般程序設(shè)計(jì)的基礎(chǔ)，而且是編譯原理、操作系統(tǒng)、數(shù)據(jù)庫系統(tǒng)及其它系統(tǒng)程序和大型應(yīng)用程序開發(fā)的重要基礎(chǔ)。數(shù)據(jù)結(jié)構(gòu)課程主要討論各種主要數(shù)據(jù)結(jié)構(gòu)的特點(diǎn)、計(jì)算機(jī)內(nèi)的表示方法、處理數(shù)據(jù)的算法以及對(duì)算法性能的分析。通過對(duì)本課程的系統(tǒng)學(xué)習(xí)使學(xué)生掌握各種數(shù)據(jù)結(jié)構(gòu)的特點(diǎn)、存儲(chǔ)表示、運(yùn)算的原理和方法，學(xué)會(huì)從問題入手，分析研究計(jì)算機(jī)加工的數(shù)據(jù)結(jié)構(gòu)的特性，以便為應(yīng)用所涉及的數(shù)據(jù)選擇適當(dāng)?shù)倪壿嫿Y(jié)構(gòu)、存儲(chǔ)機(jī)構(gòu)及其相應(yīng)

2、的操作算法，并初步掌握時(shí)間和空間分析技術(shù)。另一方面，本課程的學(xué)習(xí)過程也是進(jìn)行復(fù)雜程序設(shè)計(jì)的訓(xùn)練過程，通過對(duì)本課程算法設(shè)計(jì)和上機(jī)實(shí)踐的訓(xùn)練，還應(yīng)培養(yǎng)學(xué)生的數(shù)據(jù)抽象能力和程序設(shè)計(jì)的能力。二、實(shí)驗(yàn)的地位、作用和目的數(shù)據(jù)結(jié)構(gòu)是一門實(shí)踐性較強(qiáng)的基礎(chǔ)課程，本課程實(shí)驗(yàn)主要是著眼于原理和應(yīng)用的結(jié)合，通過實(shí)驗(yàn)，一方面能使學(xué)生學(xué)會(huì)把書上學(xué)到的知識(shí)用于解決實(shí)際問題，加強(qiáng)培養(yǎng)學(xué)生如何根據(jù)計(jì)算機(jī)所處理對(duì)象的特點(diǎn)來組織數(shù)據(jù)存儲(chǔ)和編寫性能好的操作算法的能力，為以后相關(guān)課程的學(xué)習(xí)和大型軟件的開發(fā)打下扎實(shí)的基礎(chǔ)。另一方面使書上的知識(shí)變活，起到深化理解和靈活掌握教學(xué)內(nèi)容的目的。三、報(bào)告與考核每個(gè)實(shí)驗(yàn)都要求學(xué)生根據(jù)上機(jī)內(nèi)容寫出實(shí)驗(yàn)

3、報(bào)告，報(bào)告要求包括以下七個(gè)方面的內(nèi)容：1實(shí)驗(yàn)?zāi)康模?實(shí)驗(yàn)內(nèi)容；3實(shí)驗(yàn)要求；4算法設(shè)計(jì)；5詳細(xì)程序清單；6程序運(yùn)行結(jié)果；7實(shí)驗(yàn)心得體會(huì)。32 / 32文檔可自由編輯目錄實(shí)驗(yàn)一 順序表的操作實(shí)驗(yàn)3實(shí)驗(yàn)二 鏈表的操作實(shí)驗(yàn)6實(shí)驗(yàn)三 棧和隊(duì)列的操作實(shí)驗(yàn)8實(shí)驗(yàn)四 二叉樹的遍歷實(shí)驗(yàn)11實(shí)驗(yàn)五 二叉排序樹的查找操作14實(shí)驗(yàn)六 圖的操作實(shí)驗(yàn)16實(shí)驗(yàn)七 查找操作實(shí)驗(yàn)18實(shí)驗(yàn)八 排序操作實(shí)驗(yàn)21實(shí)驗(yàn)一 順序表的操作實(shí)驗(yàn)一、實(shí)驗(yàn)名稱和性質(zhì)所屬課程數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)名稱順序表的操作實(shí)驗(yàn)學(xué)時(shí)4實(shí)驗(yàn)性質(zhì)驗(yàn)證 綜合 設(shè)計(jì)必做/選做必做 選做二、實(shí)驗(yàn)?zāi)康?掌握線性表的順序存儲(chǔ)結(jié)構(gòu)的表示和實(shí)現(xiàn)方法。2掌握順序表基本操作的算法實(shí)現(xiàn)。3了

4、解順序表的應(yīng)用。三、實(shí)驗(yàn)內(nèi)容1建立順序表。2在順序表上實(shí)現(xiàn)插入、刪除和查找操作（驗(yàn)證性內(nèi)容）。3刪除有序順序表中的重復(fù)元素（設(shè)計(jì)性內(nèi)容）。4完成一個(gè)簡(jiǎn)單學(xué)生成績(jī)管理系統(tǒng)的設(shè)計(jì)（應(yīng)用性設(shè)計(jì)內(nèi)容）。七、設(shè)計(jì)性實(shí)驗(yàn)編程實(shí)現(xiàn)刪除有序順序表中的所有重復(fù)元素，即使有序順序表中相同的元素只保留一個(gè)。1. 實(shí)驗(yàn)要求 根據(jù)輸入的n個(gè)非遞減的有序數(shù)據(jù)建立一個(gè)有序順序表，并輸出有序順序表中各元素值。 刪除有序順序表中所有的重復(fù)元素，并顯示刪除后的有序順序表中各元素值。2. 核心算法提示要在有序順序表中刪除重復(fù)的元素，首先就要抓住有序順序表的特性：重復(fù)的元素總是在相鄰的位置上，如：12，15，15，15，35，56，

5、56，78。則刪除重復(fù)元素后所得的有序表為：12，15，35，56，78。下面給出大致的操作步驟：從第0個(gè)元素開始，依次將它與后面相鄰的元素進(jìn)行比較，如果相等則將前面那個(gè)相等的元素從順序表中刪除；如果不相等，則繼續(xù)往下比較，如此重復(fù)，直到最后一個(gè)元素為止。3. 核心算法描述/ 刪除有序順序表L中的所有重復(fù)元素，即使得有序順序表中相同的元素只保留一個(gè)public static void remove_repeat(SqList L) int i=0; while(iL.getCurLen()-1) if (L.getListElem()i.equals(L.getListElem()i+1) /

6、如果第i個(gè)及第i+1個(gè)相鄰元素值相等 for (int j=i+1;jL.getCurLen();j+) /將第i+1個(gè)元素及其之后的所有元素前移一個(gè)位地置 L.getListElem()j-1=L.getListElem()j; L.setCurLen(L.getCurLen()-1); /有序順序表的表長(zhǎng)減1 else i+; 結(jié)果：八、應(yīng)用性設(shè)計(jì)實(shí)驗(yàn)編程實(shí)現(xiàn)一個(gè)簡(jiǎn)單學(xué)生成績(jī)管理系統(tǒng)的設(shè)計(jì)。實(shí)驗(yàn)要求此系統(tǒng)的功能包括： 查詢：按特定的條件查找學(xué)生 修改：按學(xué)號(hào)對(duì)某個(gè)學(xué)生的某門課程成績(jī)進(jìn)行修改 插入：增加新學(xué)生的信息 刪除：按學(xué)號(hào)刪除已退學(xué)的學(xué)生的信息。學(xué)生成績(jī)表的數(shù)據(jù)如下：學(xué)號(hào)姓名性別大學(xué)英

7、語高等數(shù)學(xué)2008001AlanF93882008002DanieM75692008003HelenM56772008004BillF87902008006PeterM79862008006AmyF6875要求采用順序存儲(chǔ)結(jié)構(gòu)來實(shí)現(xiàn)對(duì)上述成績(jī)表的相關(guān)操作。截圖實(shí)驗(yàn)心得：實(shí)驗(yàn)二 鏈表的操作實(shí)驗(yàn)一、實(shí)驗(yàn)名稱和性質(zhì)所屬課程數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)名稱鏈表的操作實(shí)驗(yàn)學(xué)時(shí)4實(shí)驗(yàn)性質(zhì)驗(yàn)證 綜合 設(shè)計(jì)必做/選做必做 選做二、實(shí)驗(yàn)?zāi)康?掌握線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的表示和實(shí)現(xiàn)方法。2掌握鏈表基本操作的算法實(shí)現(xiàn)。三、實(shí)驗(yàn)內(nèi)容1建立單鏈表，并在單鏈表上實(shí)現(xiàn)插入、刪除和查找操作（驗(yàn)證性內(nèi)容）。2建立雙向鏈表，并在雙向鏈表上實(shí)現(xiàn)插入

8、、刪除和查找操作（設(shè)計(jì)性內(nèi)容）。3計(jì)算已知一個(gè)單鏈表中數(shù)據(jù)域值為一個(gè)指定值x的結(jié)點(diǎn)個(gè)數(shù)（應(yīng)用性設(shè)計(jì)內(nèi)容）。四、實(shí)驗(yàn)的軟硬件環(huán)境要求硬件環(huán)境要求：PC機(jī)（單機(jī)）使用的軟件名稱、版本號(hào)以及模塊：Netbeans 6.5以上或Eclipse、MyEclipse等編程環(huán)境下。五、知識(shí)準(zhǔn)備前期要求熟練掌握了Java語言的編程規(guī)則、方法和單鏈表和雙向鏈表的基本操作算法。六、驗(yàn)證性實(shí)驗(yàn)運(yùn)行結(jié)果參考如圖4-1所示：七、設(shè)計(jì)性實(shí)驗(yàn) 兩個(gè)一元多項(xiàng)式的相乘 P54-55截圖：八、應(yīng)用性設(shè)計(jì)實(shí)驗(yàn)編寫一個(gè)程序，計(jì)算出一個(gè)單鏈表中數(shù)據(jù)域值為一個(gè)指定值x的結(jié)點(diǎn)個(gè)數(shù)。實(shí)驗(yàn)要求： 從鍵盤輸入若干個(gè)整數(shù)，以此序列為順序建立一個(gè)不

9、帶頭結(jié)點(diǎn)的單鏈表； 輸出此單鏈表中的各個(gè)數(shù)據(jù)元素值； 給定一個(gè)x的具體整數(shù)值，計(jì)算并返回此單鏈表中數(shù)據(jù)域值為x的結(jié)點(diǎn)個(gè)數(shù)值。截圖實(shí)驗(yàn)心得：實(shí)驗(yàn)三 棧和隊(duì)列的操作實(shí)驗(yàn)一、實(shí)驗(yàn)名稱和性質(zhì)所屬課程數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)名稱棧和隊(duì)列的操作實(shí)驗(yàn)學(xué)時(shí)4實(shí)驗(yàn)性質(zhì)驗(yàn)證 綜合 設(shè)計(jì)必做/選做必做 選做二、實(shí)驗(yàn)?zāi)康?掌握棧和對(duì)的存儲(chǔ)結(jié)構(gòu)的表示和實(shí)現(xiàn)方法。2掌握棧的入棧和出棧等基本操作算法實(shí)現(xiàn)。3了解棧在解決實(shí)際問題中的簡(jiǎn)單應(yīng)用。三、實(shí)驗(yàn)內(nèi)容1建立順序棧，并在順序棧上實(shí)現(xiàn)入棧和出棧操作（驗(yàn)證性內(nèi)容）。2建立鏈棧，并在鏈棧上實(shí)現(xiàn)入棧和出棧操作（設(shè)計(jì)性內(nèi)容）。3實(shí)現(xiàn)漢諾（Hanoi）塔求解問題（應(yīng)用性設(shè)計(jì)內(nèi)容）。四、實(shí)驗(yàn)的軟硬件

10、環(huán)境要求硬件環(huán)境要求：PC機(jī)（單機(jī)）使用的軟件名稱、版本號(hào)以及模塊：Netbeans 6.5以上或Eclipse、MyEclipse等編程環(huán)境下。五、知識(shí)準(zhǔn)備前期要求熟練掌握了Java語言的編程規(guī)則、方法和順序棧、鏈棧的基本操作算法。六、驗(yàn)證性實(shí)驗(yàn)實(shí)驗(yàn)截圖七、設(shè)計(jì)性實(shí)驗(yàn)P111 4-1,4-3，4-4,4-5，4-10截圖：4-1 4-3 4-4 4-5 4-10 八、應(yīng)用性設(shè)計(jì)實(shí)驗(yàn)編程實(shí)現(xiàn)漢諾（Hanoi）塔求解問題。1實(shí)驗(yàn)要求假設(shè)有三個(gè)命名為X、Y和Z的塔座，在塔座X上插有n個(gè)直徑大小各不相同且從小到大編號(hào)為1,2,n的圓盤?，F(xiàn)要求將塔座X上的n個(gè)圓盤借助于塔座Y移至塔座Z上，并仍按同樣順

11、序疊排。圓盤移動(dòng)時(shí)必須遵循下列規(guī)則： 每次只能移動(dòng)一個(gè)圓盤； 圓盤可以插在X、Y和Z中的任何一個(gè)塔座上； 任何時(shí)刻都不能將一個(gè)較大的圓盤壓在較小的圓盤上。截圖：實(shí)驗(yàn)心得：實(shí)驗(yàn)四 二叉樹的遍歷實(shí)驗(yàn)一、實(shí)驗(yàn)名稱和性質(zhì)所屬課程數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)名稱二叉樹的操作實(shí)驗(yàn)學(xué)時(shí)4實(shí)驗(yàn)性質(zhì)驗(yàn)證 綜合 設(shè)計(jì)必做/選做必做 選做二、實(shí)驗(yàn)?zāi)康?理解二叉樹的類型定義與性質(zhì)。2掌握二叉樹的二叉鏈表存儲(chǔ)結(jié)構(gòu)的表示和實(shí)現(xiàn)方法。3掌握二叉樹遍歷操作的算法實(shí)現(xiàn)。4熟悉二叉樹遍歷操作的應(yīng)用。三、實(shí)驗(yàn)內(nèi)容1建立二叉樹的二叉鏈表存儲(chǔ)結(jié)構(gòu)。2實(shí)現(xiàn)二叉樹的先根、中根和后根三種遍歷操作（驗(yàn)證性內(nèi)容）。3應(yīng)用二叉樹的遍歷操作來實(shí)現(xiàn)判斷兩棵二叉樹是否

12、相等的操作（設(shè)計(jì)性內(nèi)容）。4求從二叉樹根結(jié)點(diǎn)到指定結(jié)點(diǎn)p之間的路徑（應(yīng)用性設(shè)計(jì)內(nèi)容）。四、實(shí)驗(yàn)的軟硬件環(huán)境要求硬件環(huán)境要求：PC機(jī)（單機(jī)）使用的軟件名稱、版本號(hào)以及模塊：Netbeans 6.5以上或Eclipse、MyEclipse等編程環(huán)境下。五、知識(shí)準(zhǔn)備前期要求掌握二叉樹的二叉鏈表的存儲(chǔ)結(jié)構(gòu)表示和三種遍歷操作算法。六、驗(yàn)證性實(shí)驗(yàn)4運(yùn)行結(jié)果七、設(shè)計(jì)性實(shí)驗(yàn)編程實(shí)現(xiàn)根據(jù)二叉樹的先序遍歷序列和中序遍歷序列來建立兩棵二叉樹，并判斷這兩棵二叉樹是否相等。1. 實(shí)驗(yàn)要求 假設(shè)二叉樹的結(jié)點(diǎn)值是字符，請(qǐng)分別根據(jù)輸入的兩棵二叉樹的先根遍歷序列和中根遍歷序列來建立二叉鏈表表示的兩棵二叉樹。 分別利用先根、中根

13、和后根遍歷方法來實(shí)現(xiàn)判斷兩棵二叉樹是否相等的操作。 主程序中要求設(shè)計(jì)一個(gè)菜單，允許用戶通過菜單來多次選擇執(zhí)行利用哪一種遍歷方法來判斷兩棵二叉樹是否相等。截圖：實(shí)驗(yàn)心得：實(shí)驗(yàn)五 二叉排序樹的查找操作一、實(shí)驗(yàn)名稱和性質(zhì)所屬課程數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)名稱二叉排序樹的操作實(shí)驗(yàn)學(xué)時(shí)4實(shí)驗(yàn)性質(zhì)驗(yàn)證 綜合 設(shè)計(jì)必做/選做必做 選做二、實(shí)驗(yàn)?zāi)康?掌握二叉排序樹的含義及其在計(jì)算機(jī)中的存儲(chǔ)實(shí)現(xiàn)。2掌握在二叉排序樹上查找操作的算法實(shí)現(xiàn)。3掌握二叉排序樹的插入、刪除操作的算法實(shí)現(xiàn)。三、實(shí)驗(yàn)內(nèi)容1建立二叉排序樹。2在二叉排序樹上實(shí)現(xiàn)對(duì)給定值進(jìn)行查找操作（驗(yàn)證性內(nèi)容）。四、實(shí)驗(yàn)的軟硬件環(huán)境要求硬件環(huán)境要求：PC機(jī)（單機(jī)）使用的軟件

14、名稱、版本號(hào)以及模塊：Netbeans 6.5以上或Eclipse、MyEclipse等編程環(huán)境下。 五、知識(shí)準(zhǔn)備前期要求掌握二叉排序樹的含義、二叉排序樹上的查找算法和二叉排序上的插入、刪除操作的算法。六、驗(yàn)證性實(shí)驗(yàn)運(yùn)行結(jié)果： 七、設(shè)計(jì)性實(shí)驗(yàn)編程判斷一棵二叉樹是否為二叉排序樹。1實(shí)驗(yàn)要求 二叉樹采用二叉鏈表作為存儲(chǔ)結(jié)構(gòu)，且樹中結(jié)點(diǎn)的關(guān)鍵字均不相同。 要輸出最后的判斷結(jié)果。截圖：實(shí)驗(yàn)心得：實(shí)驗(yàn)六 圖的操作實(shí)驗(yàn)一、實(shí)驗(yàn)名稱和性質(zhì)所屬課程數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)名稱圖的操作實(shí)驗(yàn)學(xué)時(shí)4實(shí)驗(yàn)性質(zhì)驗(yàn)證 綜合 設(shè)計(jì)必做/選做必做 選做二、實(shí)驗(yàn)?zāi)康?掌握?qǐng)D的相關(guān)概念。2掌握用鄰接矩陣和鄰接表的方法描述圖的存儲(chǔ)結(jié)構(gòu)。3掌握

15、圖的深度優(yōu)先搜索和廣度優(yōu)先搜索遍歷的方法及其計(jì)算機(jī)的實(shí)現(xiàn)。4理解最小生成樹的有關(guān)算法三、實(shí)驗(yàn)內(nèi)容1用鄰接表作為圖的存儲(chǔ)結(jié)構(gòu)建立一個(gè)圖，并對(duì)此圖分別進(jìn)行深度優(yōu)先搜索和廣度優(yōu)先搜索遍歷（驗(yàn)證性內(nèi)容）。 2用鄰接矩陣作為圖的存儲(chǔ)結(jié)構(gòu)建立一個(gè)網(wǎng)，并構(gòu)造該網(wǎng)的最小生成樹（設(shè)計(jì)性內(nèi)容）。3校園導(dǎo)游程序的實(shí)現(xiàn)（應(yīng)用性設(shè)計(jì)內(nèi)容）。四、實(shí)驗(yàn)的軟硬件環(huán)境要求硬件環(huán)境要求：PC機(jī)（單機(jī)）使用的軟件名稱、版本號(hào)以及模塊：Netbeans 6.5以上或Eclipse、MyEclipse等編程環(huán)境下。五、知識(shí)準(zhǔn)備前期要求掌握?qǐng)D與網(wǎng)的含義、圖的鄰接矩陣和鄰接表的存儲(chǔ)表示、圖的深度優(yōu)先搜索遍歷和廣度優(yōu)先搜索遍歷方法、最小生成

16、樹的概念及其構(gòu)造算法。六、驗(yàn)證性實(shí)驗(yàn)運(yùn)行結(jié)果七、設(shè)計(jì)性實(shí)驗(yàn)用鄰接矩陣作為圖的存儲(chǔ)結(jié)構(gòu)建立一個(gè)網(wǎng)，并構(gòu)造該網(wǎng)的最小生成樹。截圖實(shí)驗(yàn)心得：實(shí)驗(yàn)七 查找操作實(shí)驗(yàn)一、實(shí)驗(yàn)名稱和性質(zhì)所屬課程數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)名稱查找操作實(shí)驗(yàn)學(xué)時(shí)4實(shí)驗(yàn)性質(zhì)驗(yàn)證 綜合 設(shè)計(jì)必做/選做必做 選做二、實(shí)驗(yàn)?zāi)康?掌握順序查找操作的算法實(shí)現(xiàn)。2掌握二分查找操作的算法實(shí)現(xiàn)及實(shí)現(xiàn)該查找的前提。3掌握哈希查找操作的算法實(shí)現(xiàn)。三、實(shí)驗(yàn)內(nèi)容1建立順序查找表，并在此查找表上實(shí)現(xiàn)順序查找操作（驗(yàn)證性內(nèi)容）。2建立有序順序查找表，并在此查找表上實(shí)現(xiàn)二分查找操作（驗(yàn)證性內(nèi)容）。3建立索引查找表，并在此查找表上實(shí)現(xiàn)索引查找操作（設(shè)計(jì)性內(nèi)容）。四、實(shí)驗(yàn)的軟硬

17、件環(huán)境要求硬件環(huán)境要求：PC機(jī)（單機(jī)）使用的軟件名稱、版本號(hào)以及模塊：Netbeans 6.5以上或Eclipse、MyEclipse等編程環(huán)境下。五、知識(shí)準(zhǔn)備前期要求掌握查找的含義和順序查找、二分查找及索引查找操作的方法。六、驗(yàn)證性實(shí)驗(yàn)(一)運(yùn)行結(jié)果。運(yùn)行結(jié)果（二）哈希表操作1實(shí)驗(yàn)要求運(yùn)行結(jié)果實(shí)驗(yàn)心得：實(shí)驗(yàn)八 排序操作實(shí)驗(yàn)一、實(shí)驗(yàn)名稱和性質(zhì)所屬課程數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)名稱排序操作實(shí)驗(yàn)學(xué)時(shí)4實(shí)驗(yàn)性質(zhì)驗(yàn)證 綜合 設(shè)計(jì)必做/選做必做 選做二、實(shí)驗(yàn)?zāi)康?熟悉并掌握各種排序方法的設(shè)計(jì)思路。2掌握各種具體排序算法在計(jì)算機(jī)上的實(shí)現(xiàn)。3掌握各種排序方法的性能比較。三、實(shí)驗(yàn)內(nèi)容1比較用直接插入排序、冒泡排序和簡(jiǎn)單選擇排序方法進(jìn)行排