數據結構實驗指導書Java語言版

1、數據結構課程實驗指導數據結構實驗教學大綱課程代碼：0806523006 開課學期：3開課專業(yè)：信息管理與信息系統(tǒng)總學時/實驗學時：64/16總學分/實驗學分：3.5/0.5一、課程簡介數據結構是計算機各專業(yè)的重要技術基礎課。在計算機科學中，數據結構不僅是一般程序設計的基礎，而且是編譯原理、操作系統(tǒng)、數據庫系統(tǒng)及其它系統(tǒng)程序和大型應用程序開發(fā)的重要基礎。數據結構課程主要討論各種主要數據結構的特點、計算機內的表示方法、處理數據的算法以及對算法性能的分析。通過對本課程的系統(tǒng)學習使學生掌握各種數據結構的特點、存儲表示、運算的原理和方法，學會從問題入手，分析研究計算機加工的數據結構的特性，以便為應用所涉

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

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

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

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

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

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

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

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

10、表的操作實驗一、實驗名稱和性質所屬課程數據結構實驗名稱順序表的操作實驗學時2實驗性質驗證 綜合 設計必做/選做必做 選做二、實驗目的1掌握線性表的順序存儲結構的表示和實現方法。2掌握順序表基本操作的算法實現。3了解順序表的應用。三、實驗內容1建立順序表。2在順序表上實現插入、刪除和查找操作（驗證性內容）。3刪除有序順序表中的重復元素（設計性內容）。4完成一個簡單學生成績管理系統(tǒng)的設計（應用性設計內容）。四、實驗的軟硬件環(huán)境要求硬件環(huán)境要求：PC機（單機）使用的軟件名稱、版本號以及模塊：Netbeans 6.5以上或Eclipse、MyEclipse等編程環(huán)境下 。五、知識準備前期要求熟練掌握了

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

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

13、度值增加1，否則拋出異常。順序表刪除操作的基本步驟：要刪除當前順序表中的第i(0in-1)個數據元素，首先仍然要判斷i的合法性，i 的合法范圍是0in-1，若是合法位置，則將第i個數據元素之后的所有數據元素都前移一個位置，最后將線性表的當前長度減1，否則拋出異常。順序表查找操作的基本步驟：要在當前順序表中查找一個給定值的數據元素，則可以采用順序查找的方法，從順序表中第0個數據元素開始依次將數據元素值與給定值進行比較，若相等則返回該數據元素在順序表中的位置，如果所有數據元素都與x比較但都不相等，表明值為x的數據元素在順序表中不存在，則返回-1值。【核心算法描述】在當前順序表上的插入操作算法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;/ 插入位置及其之后的所有數據元素后移一位

15、listElemi = x; / 插入x curLen+; / 表長加1 在當前順序表上的刪除操作算法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;/ 被刪除元素及其之后的數據元素左移一個存儲位置 curLen-; / 表長減1 在當前順序表是的查找操作算法int

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

17、Elem; / 線性表存儲空間private int curLen; / 當前長度 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; / 順序表的構造函數，構造一個存儲空間容量為maxSize的空線性表public SqList(int

18、maxSize) curLen = 0; / 置順序表的當前長度為0listElem = new ObjectmaxSize;/ 為順序表分配maxSize個存儲單元/ 在線性表的第i個數據元素之前插入一個值為x的數據元素。其中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個數據元素刪除。其中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指示順序表中待比較的數據元素，其初始值指示順序表中第0個數據元素 while (j < curLen &am

21、p;& !listElemj.equals(x) /依次比較 j+; if (j < curLen) / 判斷j的位置是否位于順序表中 return j; / 返回值為x的數據元素在順序表中的位置 else return -1; / 值為x的數據元素在順序表中不存在 / 輸出順序表中的數據元素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); /構造一個存儲容量為0的空順序表 Scanner sc=new Scanner(System.in); System.out.println("請輸入順序表的長度:"); int n=sc.nextInt(); System.out.println("請輸入順序表中的各個數據元素:"); 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("請輸入待插入的數據值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("請輸入待查找的數據元素:"); x=sc.nextInt(); int order=L.indexOf(x); if (order=-1) System.out.println("此順序表中不包含值為"+x+"的數據元素!"); else System.out.println("值為"+x+"元素在順序表中的第"+order+"個位置上&qu

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

26、有序表為：12，15，35，56，78。下面給出大致的操作步驟：從第0個元素開始，依次將它與后面相鄰的元素進行比較，如果相等則將前面那個相等的元素從順序表中刪除；如果不相等，則繼續(xù)往下比較，如此重復，直到最后一個元素為止。3. 核心算法描述/ 刪除有序順序表L中的所有重復元素，即使得有序順序表中相同的元素只保留一個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+; 八、應用性設計實驗編程實現一個簡單學生成績管理系統(tǒng)的設計。實驗要求此系統(tǒng)的功能包括： 查詢：按特定的條件查找學生 修改：按學號對某個學生的某門課程成績進行修改 插入：增加新學生的信息 刪除：按學號刪除已退學的學生的信息。學生成績表的數據如下：學號姓名性別大學英語高等數學2008001

28、AlanF93882008002DanieM75692008003HelenM56772008004BillF87902008006PeterM79862008006AmyF6875要求采用順序存儲結構來實現對上述成績表的相關操作。實驗B02: 鏈表的操作實驗一、實驗名稱和性質所屬課程數據結構實驗名稱鏈表的操作實驗學時2實驗性質驗證 綜合 設計必做/選做必做 選做二、實驗目的1掌握線性表的鏈式存儲結構的表示和實現方法。2掌握鏈表基本操作的算法實現。三、實驗內容1建立單鏈表，并在單鏈表上實現插入、刪除和查找操作（驗證性內容）。2建立雙向鏈表，并在雙向鏈表上實現插入、刪除和查找操作（設計性內容）。

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

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

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

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

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

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

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

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

37、hrow new Exception("刪除位置不合理");/ 輸出異常p.setNext(p.getNext().getNext();/ 刪除結點3源程序代碼參考package sy;import java.util.Scanner;/單鏈表的結點類class Node private Object data; / 存放結點值private Node next; / 后繼結點的引用public Node() / 無參數時的構造函數this(null, null);public Node(Object data) / 構造值為data的結點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; /實現鏈表的基本操作類 class LinkList Node head=new Node();/生成一個帶頭結點

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

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

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

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

43、Next() = null) / i小于0或者大于表長減1throw new Exception("刪除位置不合理");/ 輸出異常p.setNext(p.getNext().getNext();/ 刪除結點 / 輸出線性表中的數據元素public void display() Node p = head.getNext();/ 取出帶頭結點的單鏈表中的首結點元素while (p != null) System.out.print(p.getData() + " ");/ 輸出數據元素的值p = p.getNext();/ 取下一個結點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("請輸入鏈表中的各個數據元素(0為結束):"); L.creat(); System.out.println("建立的單鏈表為:"); L.display(); System.out.print

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

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

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

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

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

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