數(shù)據(jù)結(jié)構(gòu)實驗指導(dǎo)書Java語言版

1、數(shù)據(jù)結(jié)構(gòu)課程實驗指導(dǎo)數(shù)據(jù)結(jié)構(gòu)實驗教學(xué)大綱課程代碼：0806523006 開課學(xué)期：3開課專業(yè)：信息管理與信息系統(tǒng)總學(xué)時/實驗學(xué)時：64/16總學(xué)分/實驗學(xué)分：3.5/0.5一、課程簡介數(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)用所涉

2、及的數(shù)據(jù)選擇適當(dāng)?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、方式與基本要求實驗方式是上機編寫完成實驗項目指定功能的程序，并調(diào)試、運行，最終得出正確結(jié)果。具體實驗要求如下：1. 問題分析充分地分析和理解問題本身，弄清要求，包括功能要求、性能要求、設(shè)計要求和約束，以及基本數(shù)據(jù)特性、數(shù)據(jù)間聯(lián)系等等。2. 數(shù)據(jù)結(jié)構(gòu)設(shè)計針對要解決的問題，考慮各種可能的數(shù)據(jù)結(jié)構(gòu)，并且力求從中選出最佳方案（必須連同算法實現(xiàn)一起考慮），確定主要的數(shù)據(jù)結(jié)構(gòu)和全程變量。對引入的每種數(shù)據(jù)結(jié)構(gòu)和全程變量要詳細(xì)說明其功用、初值和操作的特點。3. 算法設(shè)計算法設(shè)計分概要和詳細(xì)設(shè)計。概要設(shè)計著重解決程序的類的設(shè)計問題，這包括考慮如何把被開發(fā)的問題程序分解成若干個類，并決定類與類之間的關(guān)系。詳細(xì)設(shè)計

4、則要決定每個類內(nèi)部的具體算法，包括輸入、處理和輸出。4. 測試用例設(shè)計準(zhǔn)備典型測試數(shù)據(jù)和測試方案。測試數(shù)據(jù)要有代表性、敏感性。測試方案包括單元測試和單元集成測試。5. 上機調(diào)試對程序進行編譯，糾正程序中可能出現(xiàn)的語法錯誤。調(diào)試前，先運行一遍程序看看究竟將會發(fā)生什么。如果情況很糟，則根據(jù)事先設(shè)計的測試方案并結(jié)合現(xiàn)場情況進行錯誤跟蹤，包括打印執(zhí)行路徑或輸出中間變量值等手段。6. 程序性能分析在運行結(jié)果正確的前提下再分析程序中主要算法是否具有較好的時間復(fù)雜度和空間復(fù)雜度。如果沒有，則通過改變數(shù)據(jù)結(jié)構(gòu)或操作方法使編寫的程序性能達到最佳。7. 實驗總結(jié)每個實驗完成后要認(rèn)真書寫實驗報告，對程序運行的結(jié)構(gòu)，

5、要認(rèn)真分析，總結(jié)每次實驗項目的體會與收獲。四、報告與考核每個實驗都要求學(xué)生根據(jù)上機內(nèi)容寫出實驗報告，報告要求包括以下七個方面的內(nèi)容：1實驗?zāi)康模?實驗內(nèi)容；3實驗要求；4算法設(shè)計；5詳細(xì)程序清單；6程序運行結(jié)果；7實驗心得體會。考核方式：每個實驗項目根據(jù)以下兩個方面進行考核：1指導(dǎo)教師隨堂抽查學(xué)生的實驗過程（包括實驗預(yù)習(xí)、實驗出勤、實驗結(jié)果的測試），并根據(jù)抽查結(jié)果評定學(xué)生成績，此成績占此實驗總成績的70%；2學(xué)生編寫課程實驗報告，每位學(xué)生按照實驗報告的內(nèi)容和要求編寫詳細(xì)的實驗報告上交給指導(dǎo)老師，由指導(dǎo)老師根據(jù)每位學(xué)生的完成情況評定成績，此成績占實驗總成績的30%。五、設(shè)備及器材材料配置硬件：奔

6、騰以上PC機軟件：Netbeans 6.5以上或Eclipse、MyEclipse等編程環(huán)境六、實驗指導(dǎo)書及主要參考書1劉小晶.數(shù)據(jù)結(jié)構(gòu)實驗指導(dǎo)書(Java語言版)2 Robert Lafore著,計曉云等譯. Java數(shù)據(jù)結(jié)構(gòu)和算法(第二版)M. 北京：中國電力出版社,2004.3 Sartaj Sahni著,孔芳,高偉譯. 數(shù)據(jù)結(jié)構(gòu)、算法與應(yīng)用(Java語言描述)M. 北京：中國水利水電出版社,2007.4 葉核亞. 數(shù)據(jù)結(jié)構(gòu)(Java版)M. 北京：電子工業(yè)出版社，2004.5 鄧俊輝. 數(shù)據(jù)結(jié)構(gòu)與算法(Java語言描述)M. 北京：機械工業(yè)出版社，2006.6 朱戰(zhàn)立. 數(shù)據(jù)結(jié)構(gòu)- J

7、ava語言描述M. 北京：清華大學(xué)出版社，2005.7 張銘.數(shù)據(jù)結(jié)構(gòu)與算法. 高教出版社.2008.68 張銘.數(shù)據(jù)結(jié)構(gòu)與算法學(xué)習(xí)指導(dǎo)與習(xí)題解析. 高教出版社.20099 耿國華等 數(shù)據(jù)結(jié)構(gòu)-C語言描述. 高教出版社.2005.710 劉懷亮. 數(shù)據(jù)結(jié)構(gòu)(C語言描述) .冶金出版社.2005.211 劉懷亮. 數(shù)據(jù)結(jié)構(gòu)(C語言描述)習(xí)題與實驗指導(dǎo)導(dǎo).冶金出版社.2005.212 蔡子經(jīng)，施伯樂.數(shù)據(jù)結(jié)構(gòu)教程.上海:復(fù)旦大學(xué)出版社.199413 嚴(yán)蔚敏,吳偉民.數(shù)據(jù)結(jié)構(gòu)(C語言版).北京：清華大學(xué)出版社.1999；14 嚴(yán)蔚敏,吳偉民.數(shù)據(jù)結(jié)構(gòu)題集(C語言版).北京：清華大學(xué)出版社.1999；

8、15 徐孝凱.數(shù)據(jù)結(jié)構(gòu)課程實驗.北京：清華大學(xué)出版社.2002； 16 孟佳娜,胡瀟琨.算法與數(shù)據(jù)結(jié)構(gòu)實驗與習(xí)題.北京：機械工業(yè)出版社.2004.七、實驗項目與內(nèi)容提要序號實驗名稱目的要求、內(nèi)容提要（限20字）每組人數(shù)實驗學(xué)時實驗類型必做選做所在實驗分室1順序表的基本操作熟悉并完成順序表上基本操作的算法及其應(yīng)用問題的編程實現(xiàn)。1個班2驗證與設(shè)計必做2鏈表的基本操作熟悉并完成單鏈表和雙向鏈表基本操作算法的編程實現(xiàn)。1個班2驗證與設(shè)計必做3棧的基本操作熟悉并完成順序棧和鏈?；静僮魉惴捌鋺?yīng)用問題的編程實現(xiàn)1個班2驗證與設(shè)計必做4隊列的基本操作熟悉并完成循環(huán)順序隊列和循環(huán)鏈隊列基本操作算法及其應(yīng)用

9、問題的編程實現(xiàn)。1個班2驗證與設(shè)計必做5二叉樹的操作熟悉并完成二叉樹遍歷算法及其應(yīng)用問題的編程實現(xiàn)。1個班2驗證與設(shè)計必做6靜態(tài)查找表的查找操作熟悉并完成靜態(tài)查找表上的順序查找、二分查找和索引查找算法的編程實現(xiàn)1個班2驗證與設(shè)計必做7二叉排序樹的查找操作熟悉并完成在二叉排序樹上進行查找、插入和刪除操作的編程實現(xiàn)。1個班2驗證與設(shè)計選做8哈希表上的查找操作熟悉并完成哈希表的建立、查找和插入操作的編程實現(xiàn)1個班2驗證與設(shè)計選做9排序操作熟悉并完成幾種主要排序操作的編程實現(xiàn)。1個班2驗證與設(shè)計必做10圖的遍歷熟悉并完成圖的遍歷、最小生成樹及其應(yīng)用問題的編程實現(xiàn)1個班2驗證與設(shè)計選做實驗B01: 順序

10、表的操作實驗一、實驗名稱和性質(zhì)所屬課程數(shù)據(jù)結(jié)構(gòu)實驗名稱順序表的操作實驗學(xué)時2實驗性質(zhì)驗證 綜合 設(shè)計必做/選做必做 選做二、實驗?zāi)康?掌握線性表的順序存儲結(jié)構(gòu)的表示和實現(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)容）。四、實驗的軟硬件環(huán)境要求硬件環(huán)境要求：PC機（單機）使用的軟件名稱、版本號以及模塊：Netbeans 6.5以上或Eclipse、MyEclipse等編程環(huán)境下 。五、知識準(zhǔn)備前期要求熟練掌握了

11、Java語言的編程規(guī)則、方法和順序表的基本操作算法。六、驗證性實驗1實驗要求編程實現(xiàn)如下功能：（1）根據(jù)輸入順序表的長度n和各個數(shù)據(jù)元素值建立一個順序表，并輸出順序表中各元素值，觀察輸入的內(nèi)容與輸出的內(nèi)容是否一致。（2）在順序表的第i(0in)個元素之前插入一個值為x的元素，并輸出插入后的順序表中各元素值。（3）刪除順序表中第i(0in-1)個元素，并輸出刪除后的順序表中各元素值。（4）在順序表中查找值為x的數(shù)據(jù)元素初次出現(xiàn)的位置。如果查找成功，則返回該數(shù)據(jù)元素在順序表中的位序號；如果查找失敗，則返回-1。2. 實驗相關(guān)原理線性表的順序存儲結(jié)構(gòu)稱為順序表，線性表的順序存儲結(jié)構(gòu)在線性表Java接

12、口的實現(xiàn)類中描述如下：public class SqList implements IListprivate Object listElem; / 線性表存儲空間private int curLen; /線性表的當(dāng)前長度 【核心算法提示】順序表插入操作的基本步驟：要在當(dāng)前的順序表中的第i(0in, n為線性表的當(dāng)前長度)個數(shù)據(jù)元素之前插入一個數(shù)據(jù)元素x，首先要判斷插入位置i是否合法， i的合法值范圍：1in+1，若是合法位置，就再判斷順序表是否滿，如果不滿，則將第i個數(shù)據(jù)元素及其之后的所有數(shù)據(jù)元素都后移一個位置，此時第i個位置已經(jīng)騰空，再將待插入的數(shù)據(jù)元素x插入到該位置上，最后將線性表的當(dāng)前長

13、度值增加1，否則拋出異常。順序表刪除操作的基本步驟：要刪除當(dāng)前順序表中的第i(0in-1)個數(shù)據(jù)元素，首先仍然要判斷i的合法性，i 的合法范圍是0in-1，若是合法位置，則將第i個數(shù)據(jù)元素之后的所有數(shù)據(jù)元素都前移一個位置，最后將線性表的當(dāng)前長度減1，否則拋出異常。順序表查找操作的基本步驟：要在當(dāng)前順序表中查找一個給定值的數(shù)據(jù)元素，則可以采用順序查找的方法，從順序表中第0個數(shù)據(jù)元素開始依次將數(shù)據(jù)元素值與給定值進行比較，若相等則返回該數(shù)據(jù)元素在順序表中的位置，如果所有數(shù)據(jù)元素都與x比較但都不相等，表明值為x的數(shù)據(jù)元素在順序表中不存在，則返回-1值?！竞诵乃惴枋觥吭诋?dāng)前順序表上的插入操作算法voi

14、d insert(int i, Object x) throws Exception if (curLen = listElem.length) / 判斷順序表是否已滿 throw new Exception("順序表已滿"); / 拋出異常 if (i < 0 | i > curLen) / i不合法 throw new Exception("插入位置不合法");/ 拋出異常 for (int j = curLen; j > i; j-) listElemj = listElemj - 1;/ 插入位置及其之后的所有數(shù)據(jù)元素后移一位

15、listElemi = x; / 插入x curLen+; / 表長加1 在當(dāng)前順序表上的刪除操作算法void remove(int i) throws Exception if (i < 0 | i > curLen - 1) / i不合法 throw new Exception("刪除位置不合法");/ 拋出異常 for (int j = i; j < curLen - 1; j+) listElemj = listElemj + 1;/ 被刪除元素及其之后的數(shù)據(jù)元素左移一個存儲位置 curLen-; / 表長減1 在當(dāng)前順序表是的查找操作算法int

16、indexOf(Object x) int j = 0; / j指示順序表中待比較的數(shù)據(jù)元素，其初始值指示順序表中第0個數(shù)據(jù)元素while (j < curLen && !listElemj.equals(x) /依次比較j+;if (j < curLen) / 判斷j的位置是否位于順序表中 return j; / 返回值為x的數(shù)據(jù)元素在順序表中的位置elsereturn -1; / 值為x的數(shù)據(jù)元素在順序表中不存在3源程序代碼參考package sy;import java.util.Scanner;class SqList private Object list

17、Elem; / 線性表存儲空間private int curLen; / 當(dāng)前長度 public int getCurLen() return curLen; public void setCurLen(int curLen) this.curLen = curLen; public Object getListElem() return listElem; public void setListElem(Object listElem) this.listElem = listElem; / 順序表的構(gòu)造函數(shù)，構(gòu)造一個存儲空間容量為maxSize的空線性表public SqList(int

18、maxSize) curLen = 0; / 置順序表的當(dāng)前長度為0listElem = new ObjectmaxSize;/ 為順序表分配maxSize個存儲單元/ 在線性表的第i個數(shù)據(jù)元素之前插入一個值為x的數(shù)據(jù)元素。其中i取值范圍為：0icurLen。public void insert(int i, Object x) throws Exception if (curLen = listElem.length) / 判斷順序表是否已滿throw new Exception("順序表已滿");/ 輸出異常if (i < 0 | i > curLen) /

19、 i小于0或者大于表長throw new Exception("插入位置不合理");/ 輸出異常for (int j = curLen; j > i; j-)listElemj = listElemj - 1;/ 插入位置及之后的元素后移listElemi = x; / 插入xcurLen+;/ 表長度增1/ 將線性表中第i個數(shù)據(jù)元素刪除。其中i取值范圍為：0icurLen- 1,如果i值不在此范圍則拋出異常public void remove(int i) throws Exception if (i < 0 | i > curlew - 1) / i小

20、于1或者大于表長減1throw new Exception("刪除位置不合理");/ 輸出異常for (int j = i; j < curLen - 1; j+)listElemj = listElemj + 1;/ 被刪除元素之后的元素左移curLen-; / 表長度減1 /查找順序表中值的x元素,若查找成功則返回元素在表中的位序(0curLen-1),否則返回-1 public int indexOf(Object x) int j = 0; / j指示順序表中待比較的數(shù)據(jù)元素，其初始值指示順序表中第0個數(shù)據(jù)元素 while (j < curLen &am

21、p;& !listElemj.equals(x) /依次比較 j+; if (j < curLen) / 判斷j的位置是否位于順序表中 return j; / 返回值為x的數(shù)據(jù)元素在順序表中的位置 else return -1; / 值為x的數(shù)據(jù)元素在順序表中不存在 / 輸出順序表中的數(shù)據(jù)元素public void display() for (int j = 0; j < curLen; j+)System.out.print(listElemj + " ");System.out.println();/ 換行/測試類public class SY1_

22、SqList public static void main(String args) throws Exception SqList L=new SqList(20); /構(gòu)造一個存儲容量為0的空順序表 Scanner sc=new Scanner(System.in); System.out.println("請輸入順序表的長度:"); int n=sc.nextInt(); System.out.println("請輸入順序表中的各個數(shù)據(jù)元素:"); for(int i=0;i<n;i+) L.insert(i,sc.nextInt(); S

23、ystem.out.println("請輸入待插入的位置i(0curLen):"); int i=sc.nextInt(); System.out.println("請輸入待插入的數(shù)據(jù)值x:"); int x=sc.nextInt(); L.insert(i, x); System.out.println("插入后的順序表為:"); L.display(); System.out.println("請輸入待刪除元素的位置(0curLen-1):"); i=sc.nextInt(); L.remove(i); Sys

24、tem.out.println("刪除后的順序表為:"); L.display(); System.out.println("請輸入待查找的數(shù)據(jù)元素:"); x=sc.nextInt(); int order=L.indexOf(x); if (order=-1) System.out.println("此順序表中不包含值為"+x+"的數(shù)據(jù)元素!"); else System.out.println("值為"+x+"元素在順序表中的第"+order+"個位置上&qu

25、ot;); 4運行結(jié)果參考如圖1-1所示：圖1-1: 驗證性實驗運行結(jié)果備注: 以下設(shè)計性和應(yīng)用性實驗內(nèi)容學(xué)生可根據(jù)自己的掌握程度或興趣自行選擇其一或其二完成。七、設(shè)計性實驗編程實現(xiàn)刪除有序順序表中的所有重復(fù)元素，即使有序順序表中相同的元素只保留一個。1. 實驗要求 根據(jù)輸入的n個非遞減的有序數(shù)據(jù)建立一個有序順序表，并輸出有序順序表中各元素值。 刪除有序順序表中所有的重復(fù)元素，并顯示刪除后的有序順序表中各元素值。2. 核心算法提示要在有序順序表中刪除重復(fù)的元素，首先就要抓住有序順序表的特性：重復(fù)的元素總是在相鄰的位置上，如：12，15，15，15，35，56，56，78。則刪除重復(fù)元素后所得的

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

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

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

29、3計算已知一個單鏈表中數(shù)據(jù)域值為一個指定值x的結(jié)點個數(shù)（應(yīng)用性設(shè)計內(nèi)容）。四、實驗的軟硬件環(huán)境要求硬件環(huán)境要求：PC機（單機）使用的軟件名稱、版本號以及模塊：Netbeans 6.5以上或Eclipse、MyEclipse等編程環(huán)境下。五、知識準(zhǔn)備前期要求熟練掌握了Java語言的編程規(guī)則、方法和單鏈表和雙向鏈表的基本操作算法。六、驗證性實驗1實驗要求編程實現(xiàn)如下功能：（1）根據(jù)輸入的一系列整數(shù)，以0標(biāo)志結(jié)束，用頭插法建立單鏈表，并輸出單鏈表中各元素值，觀察輸入的內(nèi)容與輸出的內(nèi)容是否一致。（2）在單鏈表的第i個元素之前插入一個值為x的元素，并輸出插入后的單鏈表中各元素值。（3）刪除單鏈表中第i個

30、元素，并輸出刪除后的單鏈表中各元素值。（4）在單鏈表中查找第i個元素，如果查找成功，則顯示該元素的值，否則顯示該元素不存在。2. 實驗相關(guān)原理：線性表的鏈?zhǔn)絻Y(jié)構(gòu)是用一組任意的存儲單元依次存放線性表中的元素，這組存儲單元可以是連續(xù)的，也可以是不連續(xù)的。為反映出各元素在線性表中的前后邏輯關(guān)系，對每個數(shù)據(jù)元素來說，除了存儲其本身數(shù)據(jù)值之外，還需增加一個或多個指針域，每個指針域的值稱為指針，又稱作鏈，它用來指示它在線性表中的前驅(qū)或后繼的存儲地址。這兩個部分的的一起組成一個數(shù)據(jù)元素的存儲映像，稱為結(jié)點，若干個結(jié)點鏈接成鏈表。如果一個結(jié)點中只含一個指針的鏈表，則稱單鏈表。單鏈表中結(jié)點類描述如下：clas

31、s Node private Object data; / 存放結(jié)點值private Node next; / 后繼結(jié)點的引用 / 無參數(shù)時的構(gòu)造函數(shù)public Node() this(null, null);/帶一個參數(shù)時的構(gòu)造函數(shù)public Node(Object data) this(data, null);/帶兩個參數(shù)時的構(gòu)造函數(shù)public Node(Object data, Node next) this.data = data;this.next = next;【核心算法提示】1 鏈表建立操作的基本步驟：鏈表是一個動態(tài)的結(jié)構(gòu)，它不需要予分配空間，因此建立鏈表的過程是一個結(jié)點“

32、逐個插入” 的過程。先建立一個只含頭結(jié)點的空單鏈表，然后依次生成新結(jié)點，再不斷地將其插入到鏈表的頭部或尾部，分別稱其為“頭插法”和“尾插法”。2 鏈表查找操作的基本步驟：因鏈表是一種"順序存取"的結(jié)構(gòu)，則要在帶頭結(jié)點的鏈表中查找到第 i個 元素，必須從頭結(jié)點開始沿著后繼指針依次"點數(shù)"，直到點到第 i 個結(jié)點為止,如果查找成功，則用e返回第i個元素值。頭結(jié)點可看成是第0個結(jié)點。3 鏈表插入操作的基本步驟：先確定要插入的位置，如果插入位置合法，則再生成新的結(jié)點，最后通過修改鏈將新結(jié)點插入到指定的位置上。4 鏈表刪除操作的基本步驟：先確定要刪除的結(jié)點位置，如

33、果位置合法，則再通過修改鏈?zhǔn)贡粍h結(jié)點從鏈表中“卸下”，最后釋放被刪結(jié)點的空間。 【核心算法描述】用頭插法創(chuàng)建帶頭結(jié)點的單鏈表操作算法void creat() throws Exception /*輸入一系列整數(shù)，以0標(biāo)志結(jié)束，將這些整數(shù)作為/data域并用頭插法建立一個帶頭結(jié)點的單鏈表 Scanner sc = new Scanner(System.in);/ 構(gòu)造用于輸入的對象 for (int x=sc.nextInt(); x!=0; x=sc.nextInt()/ 輸入n個元素的值insert(0, x);/ 生成新結(jié)點,插入到表頭在當(dāng)前帶頭結(jié)點的單鏈表上的查找操作算法Object g

34、et(int i) throws Exception Node p = head.getNext();/ 初始化，p指向首結(jié)點，j為計數(shù)器int j = 0;while (p != null && j < i) / 從首結(jié)點開始向后查找，直到p指向第i個結(jié)點或p為空p = p.getNext();/ 指向后繼結(jié)點+j;/ 計數(shù)器的值增1if (j > i | p = null) / i小于0或者大于表長減1throw new Exception("第" + i + "個元素不存在");/ 拋出異常return p.getDat

35、a(); / 返回結(jié)點p的數(shù)據(jù)域的值在當(dāng)前帶頭結(jié)點的單鏈表上的插入操作算法void insert(int i, Object x) throws Exception Node p = head;/ 初始化p為頭結(jié)點,j為計數(shù)器int j = -1;while (p != null && j < i - 1) / 尋找i個結(jié)點的前驅(qū)p = p.getNext();+j;/ 計數(shù)器的值增1if (j > i - 1 | p = null) / i不合法throw new Exception("插入位置不合理");/ 輸出異常Node s = new

36、Node(x); / 生成新結(jié)點s.setNext(p.getNext();/ 插入單鏈表中p.setNext(s);在當(dāng)前帶頭結(jié)點的單鏈表上的刪除操作算法void remove(int i) throws Exception Node p = head;/ 初始化p為頭結(jié)點,j為計數(shù)器int j = -1;while (p.getNext() != null && j < i - 1) / 尋找i個結(jié)點的前驅(qū)p = p.getNext();+j;/ 計數(shù)器的值增1if (j > i - 1 | p.getNext() = null) / i小于0或者大于表長減1t

37、hrow new Exception("刪除位置不合理");/ 輸出異常p.setNext(p.getNext().getNext();/ 刪除結(jié)點3源程序代碼參考package sy;import java.util.Scanner;/單鏈表的結(jié)點類class Node private Object data; / 存放結(jié)點值private Node next; / 后繼結(jié)點的引用public Node() / 無參數(shù)時的構(gòu)造函數(shù)this(null, null);public Node(Object data) / 構(gòu)造值為data的結(jié)點this(data, null);

38、public Node(Object data, Node next) this.data = data;this.next = next; public Object getData() return data; public void setData(Object data) this.data = data; public Node getNext() return next; public void setNext(Node next) this.next = next; /實現(xiàn)鏈表的基本操作類 class LinkList Node head=new Node();/生成一個帶頭結(jié)點

39、的空鏈表 / 根據(jù)輸入的一系列整數(shù)，以0標(biāo)志結(jié)束，用頭插法建立單鏈表 public void creat() throws Exception Scanner sc = new Scanner(System.in); / 構(gòu)造用于輸入的對象 for (int x=sc.nextInt(); x!=0; x=sc.nextInt() / 輸入若干個數(shù)據(jù)元素的值(以0結(jié)束)insert(0, x);/ 生成新結(jié)點,插入到表頭 /返回帶頭結(jié)點的單鏈表中第i個結(jié)點的數(shù)據(jù)域的值。其中：0icurLen-1 public Object get(int i) throws Exception Node p

40、= head.getNext();/ 初始化，p指向首結(jié)點，j為計數(shù)器int j = 0;while (p != null && j < i) / 從首結(jié)點開始向后查找，直到p指向第i個結(jié)點或p為空p = p.getNext();/ 指向后繼結(jié)點+j;/ 計數(shù)器的值增1if (j > i | p = null) / i小于0或者大于表長減1throw new Exception("第" + i + "個元素不存在");/ 拋出異常return p.getData(); / 返回結(jié)點p的數(shù)據(jù)域的值 /在帶頭結(jié)點的單鏈表中的第i個

41、數(shù)據(jù)元素之前插入一個值為x的元素 public void insert(int i, Object x) throws Exception Node p = head;/ 初始化p為頭結(jié)點,j為計數(shù)器int j = -1;while (p != null && j < i - 1) / 尋找i個結(jié)點的前驅(qū)p = p.getNext();+j;/ 計數(shù)器的值增1if (j > i - 1 | p = null) / i不合法throw new Exception("插入位置不合理");/ 輸出異常Node s = new Node(x); / 生成

42、新結(jié)點s.setNext(p.getNext();/ 插入單鏈表中p.setNext(s); / 刪除帶頭結(jié)點的第i個數(shù)據(jù)元素。其中i取值范圍為：0ilength()- 1,如果i值不在此范圍則拋出異常public void remove(int i) throws Exception Node p = head;/ 初始化p為頭結(jié)點,j為計數(shù)器int j = -1;while (p.getNext() != null && j < i - 1) / 尋找i個結(jié)點的前驅(qū)p = p.getNext();+j;/ 計數(shù)器的值增1if (j > i - 1 | p.get

43、Next() = null) / i小于0或者大于表長減1throw new Exception("刪除位置不合理");/ 輸出異常p.setNext(p.getNext().getNext();/ 刪除結(jié)點 / 輸出線性表中的數(shù)據(jù)元素public void display() Node p = head.getNext();/ 取出帶頭結(jié)點的單鏈表中的首結(jié)點元素while (p != null) System.out.print(p.getData() + " ");/ 輸出數(shù)據(jù)元素的值p = p.getNext();/ 取下一個結(jié)點System.ou

44、t.println();/ 換行 /測試類 public class SY2_LinkList public static void main(String args) throws Exception Scanner sc=new Scanner(System.in); LinkList L=new LinkList(); System.out.println("請輸入鏈表中的各個數(shù)據(jù)元素(0為結(jié)束):"); L.creat(); System.out.println("建立的單鏈表為:"); L.display(); System.out.print

45、ln("請輸入待插入的位置i(0curLen):"); int i=sc.nextInt(); System.out.println("請輸入待插入的數(shù)據(jù)值x:"); int x= sc.nextInt(); L.insert(i, x); System.out.println("插入后的鏈表為:"); L.display(); System.out.println("請輸入待刪除元素的位置(0curLen-1):"); i=sc.nextInt(); L.remove(i); System.out.println

46、("刪除后的鏈表為:"); L.display(); System.out.println("請輸入待查找的數(shù)據(jù)元素的位序號(0curLen-1):"); i=sc.nextInt(); Object o=L.get(i); System.out.println("此單鏈表中第"+i+"個結(jié)點的數(shù)據(jù)元素值為"+o); 4運行結(jié)果參考如圖2-1所示：圖2-1: 驗證性實驗運行結(jié)果備注: 以下設(shè)計性和應(yīng)用性實驗內(nèi)容學(xué)生可根據(jù)自己的掌握程度或興趣自行選擇其一或其二完成。七、設(shè)計性實驗編程實現(xiàn)在雙向循環(huán)鏈表上的插入和刪除操

47、作1 實驗要求（1）輸入鏈表的長度和各元素的值，用尾插法建立雙向循環(huán)鏈表，并輸出鏈表中各元素值，觀察輸入的內(nèi)容與輸出的內(nèi)容是否一致。（2）在雙向循環(huán)鏈表的第i個元素之前插入一個值為x的元素，并輸出插入后的鏈表中各元素值。（3）刪除雙向循環(huán)鏈表中第i個元素，并輸出刪除后的鏈表中各元素值。（4）在雙向循環(huán)鏈表中查找值為x元素，如果查找成功，則顯示該元素在鏈表中的位序號，否則顯示該元素不存在。2核心算法提示 雙向循環(huán)鏈表中的結(jié)點類描述如下： class DuLNode private Object data;/ 存放結(jié)點值 private DuLNode prior; / 前驅(qū)結(jié)點的引用 priva

48、te DuLNode next; / 后繼結(jié)點的引用 雙向循環(huán)鏈表類描述如下：class DuCircleLinkList private DuLNode head;/ 雙向循環(huán)鏈表的頭結(jié)點/ 構(gòu)造函數(shù):構(gòu)造一個只含頭結(jié)點的空雙向循環(huán)鏈表public DuCircleLinkList() head = new DuLNode(); / 初始化頭結(jié)點head.setPrior(head);/ 初始化頭結(jié)點的前驅(qū)和后繼head.setNext(head); 不論是建立雙向循環(huán)鏈表還是在雙向循環(huán)鏈表中進行插入、刪除和查找操作，其操作方法和步驟都跟單鏈表類似。只不過要注意兩點：（1）凡是在操作中遇到有

49、修改鏈的地方，都要進行前驅(qū)和后繼兩個指針的修改。（2）單鏈表操作算法中的判斷條件：p= =null 或p!=null ,在循環(huán)鏈表的操作算法中則需改為：p= =head或p!= head,其中head為鏈表的頭指針。3核心算法描述 在當(dāng)前帶頭結(jié)點的雙向循環(huán)鏈表上的插入操作的算法void insert(int i, Object x) throws Exception DuLNode p = head.getNext();/ 初始化,p指向首結(jié)點,j為計數(shù)器int j = 0;while (!p.equals(head) && j < i) / 確定插入位置ip = p.g

50、etNext();/ 指向后繼結(jié)點+j;/ 計數(shù)器的值增1if (j !=i ) / i小于0或者大于表長throw new Exception("插入位置不合理");/ 輸出異常DuLNode s = new DuLNode(x);/ 生成新結(jié)點sp.getPrior().setNext(s); /將結(jié)點s插入到p結(jié)點的前面s.setPrior(p.getPrior();s.setNext(p);p.setPrior(s); 在當(dāng)前帶頭結(jié)點的雙向循環(huán)鏈表上的刪除操作算法void remove(int i) throws Exception DuLNode p = head

51、.getNext();/ 初始化,p指向首節(jié)點結(jié)點,j為計數(shù)器int j = 0;while (!p.equals(head) && j < i) / 確定刪除位置ip = p.getNext();/ 指向后繼結(jié)點+j;/ 計數(shù)器的值增1if (j != i|p.equals(head) / i小于0或者大于表長減1throw new Exception("刪除位置不合理");/ 輸出異常p.getPrior().setNext(p.getNext();p.getNext().setPrior(p.getPrior(); 在帶頭結(jié)點的雙向循環(huán)鏈表上的查找操作算法int indexOf(Object x) DuLNod