《程序技術(shù)基礎(chǔ)》實驗報告

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

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

3、核每個實驗都要求學(xué)生根據(jù)上機內(nèi)容寫出實驗報告，報告要求包括以下七個方面的內(nèi)容：.專業(yè)專注.1 實驗?zāi)康?；2 實驗內(nèi)容 ；3 實驗要求 ；4 算法設(shè)計 ；5 詳細程序清單；6 程序運行結(jié)果；7 實驗心得體會。.專業(yè)專注.目錄實驗一順序表的操作實驗4實驗二鏈表的操作實驗8實驗三棧和隊列的操作實驗11實驗四二叉樹的遍歷實驗15實驗五二叉排序樹的查找操作19實驗六圖的操作實驗21實驗七查找操作實驗24實驗八排序操作實驗27.專業(yè)專注.實驗一順序表的操作實驗一、實驗名稱和性質(zhì)所屬課程數(shù)據(jù)結(jié)構(gòu)實驗名稱順序表的操作實驗學(xué)時4實驗性質(zhì)驗證 綜合設(shè)計必做 /選做必做選做二、實驗?zāi)康? 掌握線性表的順序存儲結(jié)構(gòu)

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

5、有序順序表的特性：重復(fù)的元素總是在相鄰的位置上，如： 12 ， 15 ， 15， 15， 35， 56 ， 56 ， 78 。 則刪除重復(fù)元素后所得的有序表為 ： 12，15 ， 35， 56 ， 78。 下面給出大致的操作步驟：從第 0 個元素開始 ，依次將它與后面相鄰的元素進行比較，如果相等則將前面那個相等的元素從順序表中刪除；如果不相等 ，則繼續(xù)往下比較，如此重復(fù) ，直到最后一個元素為止。3. 核心算法描述/ 刪除有序順序表 L 中的所有重復(fù)元素 ，即使得有序順序表中相同的元素只保留一個publicstaticvoid remove_repeat(SqList L)int i=0;whi

6、le (i<L.getCurLen()-1)if (L.getListElem()i.equals(L.getListElem()i+1)/ 如果第 i個及第 i+1 個相鄰元素值相等for ( int j=i+1;j<L.getCurLen();j+)/ 將第 i+1 個元素及其之后的所有元素前移一個位地置L.getListElem()j-1=L.getListElem()j;L.setCurLen(L.getCurLen()-1);/ 有序順序表的表長減1elsei+;結(jié)果：.專業(yè)專注.八、應(yīng)用性設(shè)計實驗編程實現(xiàn)一個簡單學(xué)生成績管理系統(tǒng)的設(shè)計。實驗要求此系統(tǒng)的功能包括：查詢 ：

7、按特定的條件查找學(xué)生修改 ：按學(xué)號對某個學(xué)生的某門課程成績進行修改插入 ：增加新學(xué)生的信息刪除 ：按學(xué)號刪除已退學(xué)的學(xué)生的信息。學(xué)生成績表的數(shù)據(jù)如下：學(xué)號姓名性別大學(xué)英語高等數(shù)學(xué)2008001AlanF93882008002DanieM75692008003HelenM56772008004BillF87902008006PeterM79862008006AmyF6875.專業(yè)專注.要求采用順序存儲結(jié)構(gòu)來實現(xiàn)對上述成績表的相關(guān)操作。截圖實驗心得 ：.專業(yè)專注.Netbeans 6.5五、知識準備前期要求熟練掌握了.實驗二鏈表的操作實驗一、實驗名稱和性質(zhì)所屬課程數(shù)據(jù)結(jié)構(gòu)實驗名稱鏈表的操作實驗學(xué)時

8、4實驗性質(zhì)驗證 綜合設(shè)計必做 /選做必做選做二、實驗?zāi)康? 掌握線性表的鏈式存儲結(jié)構(gòu)的表示和實現(xiàn)方法。2 掌握鏈表基本操作的算法實現(xiàn)。三、實驗內(nèi)容1 建立單鏈表 ，并在單鏈表上實現(xiàn)插入、刪除和查找操作（驗證性內(nèi)容 ）。2 建立雙向鏈表 ，并在雙向鏈表上實現(xiàn)插入、刪除和查找操作（設(shè)計性內(nèi)容 ）。3 計算已知一個單鏈表中數(shù)據(jù)域值為一個指定值x 的結(jié)點個數(shù) （應(yīng)用性設(shè)計內(nèi)容）。四、實驗的軟硬件環(huán)境要求硬件環(huán)境要求：PC 機（單機）使用的軟件名稱、版本號以及模塊：以上或 Eclipse 、 MyEclipse等編程環(huán)境下。Java 語言的編程規(guī)則、方法和單鏈表和雙向鏈表的基本操作算專業(yè)專注.法。六、驗

9、證性實驗運行結(jié)果參考如圖4-1 所示：七、設(shè)計性實驗兩個一元多項式的相乘P54-55截圖 ：八、應(yīng)用性設(shè)計實驗編寫一個程序，計算出一個單鏈表中數(shù)據(jù)域值為一個指定值x 的結(jié)點個數(shù) 。實驗要求 ： 從鍵盤輸入若干個整數(shù)，以此序列為順序建立一個不帶頭結(jié)點的單鏈表； 輸出此單鏈表中的各個數(shù)據(jù)元素值； 給定一個x 的具體整數(shù)值 ，計算并返回此單鏈表中數(shù)據(jù)域值為x 的結(jié)點個數(shù)值 。截圖.專業(yè)專注.實驗心得 ：.專業(yè)專注.實驗三棧和隊列的操作實驗一、實驗名稱和性質(zhì)所屬課程數(shù)據(jù)結(jié)構(gòu)實驗名稱棧和隊列的操作實驗學(xué)時4實驗性質(zhì)驗證 綜合設(shè)計必做 / 選做必做選做二、實驗?zāi)康? 掌握棧和對的存儲結(jié)構(gòu)的表示和實現(xiàn)方法。

10、2 掌握棧的入棧和出棧等基本操作算法實現(xiàn)。3 了解棧在解決實際問題中的簡單應(yīng)用。三、實驗內(nèi)容1 建立順序棧 ，并在順序棧上實現(xiàn)入棧和出棧操作（驗證性內(nèi)容 ）。2 建立鏈棧 ，并在鏈棧上實現(xiàn)入棧和出棧操作（設(shè)計性內(nèi)容 ）。3 實現(xiàn)漢諾 （Hanoi ）塔求解問題 （應(yīng)用性設(shè)計內(nèi)容）。四、實驗的軟硬件環(huán)境要求硬件環(huán)境要求：PC 機（單機）使用的軟件名稱、版本號以及模塊：Netbeans 6.5以上或 Eclipse 、 MyEclipse等編程環(huán)境下。.專業(yè)專注.五、知識準備前期要求熟練掌握了Java 語言的編程規(guī)則、方法和順序棧 、鏈棧的基本操作算法。六、驗證性實驗實驗截圖七、設(shè)計性實驗P111

11、4-1,4-3 ，4-4,4-5 ， 4-10截圖 ：4-14-3.專業(yè)專注.4-44-54-10.專業(yè)專注.八、應(yīng)用性設(shè)計實驗編程實現(xiàn)漢諾（Hanoi ）塔求解問題 。1 實驗要求假設(shè)有三個命名為X、Y 和 Z 的塔座 ，在塔座 X 上插有 n 個直徑大小各不相同且從小到大編號為1,2,n 的圓盤 。 現(xiàn)要求將塔座X 上的 n 個圓盤借助于塔座Y 移至塔座 Z 上，并仍按同樣順序疊排。圓盤移動時必須遵循下列規(guī)則： 每次只能移動一個圓盤； 圓盤可以插在X、Y 和 Z 中的任何一個塔座上； 任何時刻都不能將一個較大的圓盤壓在較小的圓盤上。截圖 ：.專業(yè)專注.實驗心得 ：.專業(yè)專注.實驗四二叉樹的

12、遍歷實驗一、實驗名稱和性質(zhì)所屬課程數(shù)據(jù)結(jié)構(gòu)實驗名稱二叉樹的操作實驗學(xué)時4實驗性質(zhì)驗證 綜合設(shè)計必做 /選做必做選做二、實驗?zāi)康? 理解二叉樹的類型定義與性質(zhì)。2 掌握二叉樹的二叉鏈表存儲結(jié)構(gòu)的表示和實現(xiàn)方法。3 掌握二叉樹遍歷操作的算法實現(xiàn)。4 熟悉二叉樹遍歷操作的應(yīng)用。三、實驗內(nèi)容1 建立二叉樹的二叉鏈表存儲結(jié)構(gòu)。2 實現(xiàn)二叉樹的先根、中根和后根三種遍歷操作（驗證性內(nèi)容 ）。3 應(yīng)用二叉樹的遍歷操作來實現(xiàn)判斷兩棵二叉樹是否相等的操作（設(shè)計性內(nèi)容 ）。4 求從二叉樹根結(jié)點到指定結(jié)點p 之間的路徑 （應(yīng)用性設(shè)計內(nèi)容）。四、實驗的軟硬件環(huán)境要求硬件環(huán)境要求：PC 機（單機）.專業(yè)專注.使用的軟件名

13、稱、版本號以及模塊：Netbeans 6.5以上或 Eclipse 、 MyEclipse等編程環(huán)境下。五、知識準備前期要求掌握二叉樹的二叉鏈表的存儲結(jié)構(gòu)表示和三種遍歷操作算法。六、驗證性實驗4 運行結(jié)果七、設(shè)計性實驗編程實現(xiàn)根據(jù)二叉樹的先序遍歷序列和中序遍歷序列來建立兩棵二叉樹，并判斷這兩棵二叉樹是否相等。1. 實驗要求 假設(shè)二叉樹的結(jié)點值是字符 ，請分別根據(jù)輸入的兩棵二叉樹的先根遍歷序列和中根遍歷序列來建立二叉鏈表表示的兩棵二叉樹。 分別利用先根 、中根和后根遍歷方法來實現(xiàn)判斷兩棵二叉樹是否相等的操作。 主程序中要求設(shè)計一個菜單，允許用戶通過菜單來多次選擇執(zhí)行利用哪一種遍歷方法來判斷兩棵二

14、叉樹是否相等。截圖 ：.專業(yè)專注.實驗心得 ：.專業(yè)專注.實驗五二叉排序樹的查找操作一、實驗名稱和性質(zhì)所屬課程數(shù)據(jù)結(jié)構(gòu)實驗名稱二叉排序樹的操作實驗學(xué)時4實驗性質(zhì)驗證 綜合設(shè)計必做 /選做必做選做二、實驗?zāi)康? 掌握二叉排序樹的含義及其在計算機中的存儲實現(xiàn)。2 掌握在二叉排序樹上查找操作的算法實現(xiàn)。3 掌握二叉排序樹的插入、刪除操作的算法實現(xiàn)。三、實驗內(nèi)容1 建立二叉排序樹。2 在二叉排序樹上實現(xiàn)對給定值進行查找操作（驗證性內(nèi)容 ）。四、實驗的軟硬件環(huán)境要求硬件環(huán)境要求：PC 機（單機）使用的軟件名稱、版本號以及模塊：Netbeans 6.5以上或 Eclipse 、 MyEclipse等編程環(huán)

15、境下。五、知識準備.專業(yè)專注.前期要求掌握二叉排序樹的含義、二叉排序樹上的查找算法和二叉排序上的插入、刪除操作的算法 。六、驗證性實驗運行結(jié)果 ：七、設(shè)計性實驗編程判斷一棵二叉樹是否為二叉排序樹。1 實驗要求 二叉樹采用二叉鏈表作為存儲結(jié)構(gòu)，且樹中結(jié)點的關(guān)鍵字均不相同。 要輸出最后的判斷結(jié)果。截圖 ：實驗心得 ：.專業(yè)專注.實驗六圖的操作實驗一、實驗名稱和性質(zhì)所屬課程數(shù)據(jù)結(jié)構(gòu)實驗名稱圖的操作實驗學(xué)時4實驗性質(zhì)驗證 綜合設(shè)計必做 / 選做必做選做二、實驗?zāi)康? 掌握圖的相關(guān)概念。2 掌握用鄰接矩陣和鄰接表的方法描述圖的存儲結(jié)構(gòu)。3 掌握圖的深度優(yōu)先搜索和廣度優(yōu)先搜索遍歷的方法及其計算機的實現(xiàn)。4

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

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

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