




版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請(qǐng)進(jìn)行舉報(bào)或認(rèn)領(lǐng)
文檔簡(jiǎn)介
1、數(shù)據(jù)結(jié)構(gòu)課程實(shí)驗(yàn)指導(dǎo)數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)教學(xué)大綱課程代碼:0806523006 開課學(xué)期:3開課專業(yè):信息管理與信息系統(tǒng)總學(xué)時(shí)/實(shí)驗(yàn)學(xué)時(shí):64/16總學(xué)分/實(shí)驗(yàn)學(xué)分:3.5/0.5一、課程簡(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ù)庫(kù)系統(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)用所涉
2、及的數(shù)據(jù)選擇適當(dāng)?shù)倪壿嫿Y(jié)構(gòu)、存儲(chǔ)機(jī)構(gòu)及其相應(yīng)的操作算法,并初步掌握時(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)容的目的。三、實(shí)驗(yàn)
3、方式與基本要求實(shí)驗(yàn)方式是上機(jī)編寫完成實(shí)驗(yàn)項(xiàng)目指定功能的程序,并調(diào)試、運(yùn)行,最終得出正確結(jié)果。具體實(shí)驗(yàn)要求如下:1. 問題分析充分地分析和理解問題本身,弄清要求,包括功能要求、性能要求、設(shè)計(jì)要求和約束,以及基本數(shù)據(jù)特性、數(shù)據(jù)間聯(lián)系等等。2. 數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)針對(duì)要解決的問題,考慮各種可能的數(shù)據(jù)結(jié)構(gòu),并且力求從中選出最佳方案(必須連同算法實(shí)現(xiàn)一起考慮),確定主要的數(shù)據(jù)結(jié)構(gòu)和全程變量。對(duì)引入的每種數(shù)據(jù)結(jié)構(gòu)和全程變量要詳細(xì)說明其功用、初值和操作的特點(diǎn)。3. 算法設(shè)計(jì)算法設(shè)計(jì)分概要和詳細(xì)設(shè)計(jì)。概要設(shè)計(jì)著重解決程序的類的設(shè)計(jì)問題,這包括考慮如何把被開發(fā)的問題程序分解成若干個(gè)類,并決定類與類之間的關(guān)系。詳細(xì)設(shè)計(jì)
4、則要決定每個(gè)類內(nèi)部的具體算法,包括輸入、處理和輸出。4. 測(cè)試用例設(shè)計(jì)準(zhǔn)備典型測(cè)試數(shù)據(jù)和測(cè)試方案。測(cè)試數(shù)據(jù)要有代表性、敏感性。測(cè)試方案包括單元測(cè)試和單元集成測(cè)試。5. 上機(jī)調(diào)試對(duì)程序進(jìn)行編譯,糾正程序中可能出現(xiàn)的語法錯(cuò)誤。調(diào)試前,先運(yùn)行一遍程序看看究竟將會(huì)發(fā)生什么。如果情況很糟,則根據(jù)事先設(shè)計(jì)的測(cè)試方案并結(jié)合現(xiàn)場(chǎng)情況進(jìn)行錯(cuò)誤跟蹤,包括打印執(zhí)行路徑或輸出中間變量值等手段。6. 程序性能分析在運(yùn)行結(jié)果正確的前提下再分析程序中主要算法是否具有較好的時(shí)間復(fù)雜度和空間復(fù)雜度。如果沒有,則通過改變數(shù)據(jù)結(jié)構(gòu)或操作方法使編寫的程序性能達(dá)到最佳。7. 實(shí)驗(yàn)總結(jié)每個(gè)實(shí)驗(yàn)完成后要認(rèn)真書寫實(shí)驗(yàn)報(bào)告,對(duì)程序運(yùn)行的結(jié)構(gòu),
5、要認(rèn)真分析,總結(jié)每次實(shí)驗(yàn)項(xiàng)目的體會(huì)與收獲。四、報(bào)告與考核每個(gè)實(shí)驗(yàn)都要求學(xué)生根據(jù)上機(jī)內(nèi)容寫出實(shí)驗(yàn)報(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ì)??己朔绞剑好總€(gè)實(shí)驗(yàn)項(xiàng)目根據(jù)以下兩個(gè)方面進(jìn)行考核:1指導(dǎo)教師隨堂抽查學(xué)生的實(shí)驗(yàn)過程(包括實(shí)驗(yàn)預(yù)習(xí)、實(shí)驗(yàn)出勤、實(shí)驗(yàn)結(jié)果的測(cè)試),并根據(jù)抽查結(jié)果評(píng)定學(xué)生成績(jī),此成績(jī)占此實(shí)驗(yàn)總成績(jī)的70%;2學(xué)生編寫課程實(shí)驗(yàn)報(bào)告,每位學(xué)生按照實(shí)驗(yàn)報(bào)告的內(nèi)容和要求編寫詳細(xì)的實(shí)驗(yàn)報(bào)告上交給指導(dǎo)老師,由指導(dǎo)老師根據(jù)每位學(xué)生的完成情況評(píng)定成績(jī),此成績(jī)占實(shí)驗(yàn)總成績(jī)的30%。五、設(shè)備及器材材料配置硬件:奔
6、騰以上PC機(jī)軟件:Netbeans 6.5以上或Eclipse、MyEclipse等編程環(huán)境六、實(shí)驗(yàn)指導(dǎo)書及主要參考書1劉小晶.數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)指導(dǎo)書(Java語言版)2 Robert Lafore著,計(jì)曉云等譯. Java數(shù)據(jù)結(jié)構(gòu)和算法(第二版)M. 北京:中國(guó)電力出版社,2004.3 Sartaj Sahni著,孔芳,高偉譯. 數(shù)據(jù)結(jié)構(gòu)、算法與應(yīng)用(Java語言描述)M. 北京:中國(guó)水利水電出版社,2007.4 葉核亞. 數(shù)據(jù)結(jié)構(gòu)(Java版)M. 北京:電子工業(yè)出版社,2004.5 鄧俊輝. 數(shù)據(jù)結(jié)構(gòu)與算法(Java語言描述)M. 北京:機(jī)械工業(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 耿國(guó)華等 數(shù)據(jù)結(jié)構(gòu)-C語言描述. 高教出版社.2005.710 劉懷亮. 數(shù)據(jù)結(jié)構(gòu)(C語言描述) .冶金出版社.2005.211 劉懷亮. 數(shù)據(jù)結(jié)構(gòu)(C語言描述)習(xí)題與實(shí)驗(yàn)指導(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)課程實(shí)驗(yàn).北京:清華大學(xué)出版社.2002; 16 孟佳娜,胡瀟琨.算法與數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)與習(xí)題.北京:機(jī)械工業(yè)出版社.2004.七、實(shí)驗(yàn)項(xiàng)目與內(nèi)容提要序號(hào)實(shí)驗(yàn)名稱目的要求、內(nèi)容提要(限20字)每組人數(shù)實(shí)驗(yàn)學(xué)時(shí)實(shí)驗(yàn)類型必做選做所在實(shí)驗(yàn)分室1順序表的基本操作熟悉并完成順序表上基本操作的算法及其應(yīng)用問題的編程實(shí)現(xiàn)。1個(gè)班2驗(yàn)證與設(shè)計(jì)必做2鏈表的基本操作熟悉并完成單鏈表和雙向鏈表基本操作算法的編程實(shí)現(xiàn)。1個(gè)班2驗(yàn)證與設(shè)計(jì)必做3棧的基本操作熟悉并完成順序棧和鏈?;静僮魉惴捌鋺?yīng)用問題的編程實(shí)現(xiàn)1個(gè)班2驗(yàn)證與設(shè)計(jì)必做4隊(duì)列的基本操作熟悉并完成循環(huán)順序隊(duì)列和循環(huán)鏈隊(duì)列基本操作算法及其應(yīng)用
9、問題的編程實(shí)現(xiàn)。1個(gè)班2驗(yàn)證與設(shè)計(jì)必做5二叉樹的操作熟悉并完成二叉樹遍歷算法及其應(yīng)用問題的編程實(shí)現(xiàn)。1個(gè)班2驗(yàn)證與設(shè)計(jì)必做6靜態(tài)查找表的查找操作熟悉并完成靜態(tài)查找表上的順序查找、二分查找和索引查找算法的編程實(shí)現(xiàn)1個(gè)班2驗(yàn)證與設(shè)計(jì)必做7二叉排序樹的查找操作熟悉并完成在二叉排序樹上進(jìn)行查找、插入和刪除操作的編程實(shí)現(xiàn)。1個(gè)班2驗(yàn)證與設(shè)計(jì)選做8哈希表上的查找操作熟悉并完成哈希表的建立、查找和插入操作的編程實(shí)現(xiàn)1個(gè)班2驗(yàn)證與設(shè)計(jì)選做9排序操作熟悉并完成幾種主要排序操作的編程實(shí)現(xiàn)。1個(gè)班2驗(yàn)證與設(shè)計(jì)必做10圖的遍歷熟悉并完成圖的遍歷、最小生成樹及其應(yīng)用問題的編程實(shí)現(xiàn)1個(gè)班2驗(yàn)證與設(shè)計(jì)選做實(shí)驗(yàn)B01: 順序
10、表的操作實(shí)驗(yàn)一、實(shí)驗(yàn)名稱和性質(zhì)所屬課程數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)名稱順序表的操作實(shí)驗(yàn)學(xué)時(shí)2實(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了解順序表的應(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í)驗(yàn)的軟硬件環(huán)境要求硬件環(huán)境要求:PC機(jī)(單機(jī))使用的軟件名稱、版本號(hào)以及模塊:Netbeans 6.5以上或Eclipse、MyEclipse等編程環(huán)境下 。五、知識(shí)準(zhǔn)備前期要求熟練掌握了
11、Java語言的編程規(guī)則、方法和順序表的基本操作算法。六、驗(yàn)證性實(shí)驗(yàn)1實(shí)驗(yàn)要求編程實(shí)現(xiàn)如下功能:(1)根據(jù)輸入順序表的長(zhǎng)度n和各個(gè)數(shù)據(jù)元素值建立一個(gè)順序表,并輸出順序表中各元素值,觀察輸入的內(nèi)容與輸出的內(nèi)容是否一致。(2)在順序表的第i(0in)個(gè)元素之前插入一個(gè)值為x的元素,并輸出插入后的順序表中各元素值。(3)刪除順序表中第i(0in-1)個(gè)元素,并輸出刪除后的順序表中各元素值。(4)在順序表中查找值為x的數(shù)據(jù)元素初次出現(xiàn)的位置。如果查找成功,則返回該數(shù)據(jù)元素在順序表中的位序號(hào);如果查找失敗,則返回-1。2. 實(shí)驗(yàn)相關(guān)原理線性表的順序存儲(chǔ)結(jié)構(gòu)稱為順序表,線性表的順序存儲(chǔ)結(jié)構(gòu)在線性表Java接
12、口的實(shí)現(xiàn)類中描述如下:public class SqList implements IListprivate Object listElem; / 線性表存儲(chǔ)空間private int curLen; /線性表的當(dāng)前長(zhǎng)度 【核心算法提示】順序表插入操作的基本步驟:要在當(dāng)前的順序表中的第i(0in, n為線性表的當(dāng)前長(zhǎng)度)個(gè)數(shù)據(jù)元素之前插入一個(gè)數(shù)據(jù)元素x,首先要判斷插入位置i是否合法, i的合法值范圍:1in+1,若是合法位置,就再判斷順序表是否滿,如果不滿,則將第i個(gè)數(shù)據(jù)元素及其之后的所有數(shù)據(jù)元素都后移一個(gè)位置,此時(shí)第i個(gè)位置已經(jīng)騰空,再將待插入的數(shù)據(jù)元素x插入到該位置上,最后將線性表的當(dāng)前長(zhǎng)
13、度值增加1,否則拋出異常。順序表刪除操作的基本步驟:要?jiǎng)h除當(dāng)前順序表中的第i(0in-1)個(gè)數(shù)據(jù)元素,首先仍然要判斷i的合法性,i 的合法范圍是0in-1,若是合法位置,則將第i個(gè)數(shù)據(jù)元素之后的所有數(shù)據(jù)元素都前移一個(gè)位置,最后將線性表的當(dāng)前長(zhǎng)度減1,否則拋出異常。順序表查找操作的基本步驟:要在當(dāng)前順序表中查找一個(gè)給定值的數(shù)據(jù)元素,則可以采用順序查找的方法,從順序表中第0個(gè)數(shù)據(jù)元素開始依次將數(shù)據(jù)元素值與給定值進(jìn)行比較,若相等則返回該數(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+; / 表長(zhǎng)加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ù)元素左移一個(gè)存儲(chǔ)位置 curLen-; / 表長(zhǎng)減1 在當(dāng)前順序表是的查找操作算法int
16、indexOf(Object x) int j = 0; / j指示順序表中待比較的數(shù)據(jù)元素,其初始值指示順序表中第0個(gè)數(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; / 線性表存儲(chǔ)空間private int curLen; / 當(dāng)前長(zhǎ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)造一個(gè)存儲(chǔ)空間容量為maxSize的空線性表public SqList(int
18、maxSize) curLen = 0; / 置順序表的當(dāng)前長(zhǎng)度為0listElem = new ObjectmaxSize;/ 為順序表分配maxSize個(gè)存儲(chǔ)單元/ 在線性表的第i個(gè)數(shù)據(jù)元素之前插入一個(gè)值為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或者大于表長(zhǎng)throw new Exception("插入位置不合理");/ 輸出異常for (int j = curLen; j > i; j-)listElemj = listElemj - 1;/ 插入位置及之后的元素后移listElemi = x; / 插入xcurLen+;/ 表長(zhǎng)度增1/ 將線性表中第i個(gè)數(shù)據(jù)元素刪除。其中i取值范圍為:0icurLen- 1,如果i值不在此范圍則拋出異常public void remove(int i) throws Exception if (i < 0 | i > curlew - 1) / i小
20、于1或者大于表長(zhǎng)減1throw new Exception("刪除位置不合理");/ 輸出異常for (int j = i; j < curLen - 1; j+)listElemj = listElemj + 1;/ 被刪除元素之后的元素左移curLen-; / 表長(zhǎng)度減1 /查找順序表中值的x元素,若查找成功則返回元素在表中的位序(0curLen-1),否則返回-1 public int indexOf(Object x) int j = 0; / j指示順序表中待比較的數(shù)據(jù)元素,其初始值指示順序表中第0個(gè)數(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();/ 換行/測(cè)試類public class SY1_
22、SqList public static void main(String args) throws Exception SqList L=new SqList(20); /構(gòu)造一個(gè)存儲(chǔ)容量為0的空順序表 Scanner sc=new Scanner(System.in); System.out.println("請(qǐng)輸入順序表的長(zhǎng)度:"); int n=sc.nextInt(); System.out.println("請(qǐng)輸入順序表中的各個(gè)數(shù)據(jù)元素:"); for(int i=0;i<n;i+) L.insert(i,sc.nextInt(); S
23、ystem.out.println("請(qǐng)輸入待插入的位置i(0curLen):"); int i=sc.nextInt(); System.out.println("請(qǐng)輸入待插入的數(shù)據(jù)值x:"); int x=sc.nextInt(); L.insert(i, x); System.out.println("插入后的順序表為:"); L.display(); System.out.println("請(qǐng)輸入待刪除元素的位置(0curLen-1):"); i=sc.nextInt(); L.remove(i); Sys
24、tem.out.println("刪除后的順序表為:"); L.display(); System.out.println("請(qǐng)輸入待查找的數(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+"個(gè)位置上&qu
25、ot;); 4運(yùn)行結(jié)果參考如圖1-1所示:圖1-1: 驗(yàn)證性實(shí)驗(yàn)運(yùn)行結(jié)果備注: 以下設(shè)計(jì)性和應(yīng)用性實(shí)驗(yàn)內(nèi)容學(xué)生可根據(jù)自己的掌握程度或興趣自行選擇其一或其二完成。七、設(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,56,78。則刪除重復(fù)元素后所得的
26、有序表為: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(i<L.getCurLen()-1) if (L.getListElem()i.equals(L.getListElem()i+1) /如果第i個(gè)及第i+1個(gè)相鄰
27、元素值相等 for (int j=i+1;j<L.getCurLen();j+) /將第i+1個(gè)元素及其之后的所有元素前移一個(gè)位地置 L.getListElem()j-1=L.getListElem()j; L.setCurLen(L.getCurLen()-1); /有序順序表的表長(zhǎng)減1 else i+; 八、應(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é)英語高等數(shù)學(xué)2008001
28、AlanF93882008002DanieM75692008003HelenM56772008004BillF87902008006PeterM79862008006AmyF6875要求采用順序存儲(chǔ)結(jié)構(gòu)來實(shí)現(xiàn)對(duì)上述成績(jī)表的相關(guān)操作。實(shí)驗(yàn)B02: 鏈表的操作實(shí)驗(yàn)一、實(shí)驗(yàn)名稱和性質(zhì)所屬課程數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)名稱鏈表的操作實(shí)驗(yàn)學(xué)時(shí)2實(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)插入、刪除和查找操作(設(shè)計(jì)性內(nèi)容)。
29、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)1實(shí)驗(yàn)要求編程實(shí)現(xiàn)如下功能:(1)根據(jù)輸入的一系列整數(shù),以0標(biāo)志結(jié)束,用頭插法建立單鏈表,并輸出單鏈表中各元素值,觀察輸入的內(nèi)容與輸出的內(nèi)容是否一致。(2)在單鏈表的第i個(gè)元素之前插入一個(gè)值為x的元素,并輸出插入后的單鏈表中各元素值。(3)刪除單鏈表中第i個(gè)
30、元素,并輸出刪除后的單鏈表中各元素值。(4)在單鏈表中查找第i個(gè)元素,如果查找成功,則顯示該元素的值,否則顯示該元素不存在。2. 實(shí)驗(yàn)相關(guān)原理:線性表的鏈?zhǔn)絻?chǔ)結(jié)構(gòu)是用一組任意的存儲(chǔ)單元依次存放線性表中的元素,這組存儲(chǔ)單元可以是連續(xù)的,也可以是不連續(xù)的。為反映出各元素在線性表中的前后邏輯關(guān)系,對(duì)每個(gè)數(shù)據(jù)元素來說,除了存儲(chǔ)其本身數(shù)據(jù)值之外,還需增加一個(gè)或多個(gè)指針域,每個(gè)指針域的值稱為指針,又稱作鏈,它用來指示它在線性表中的前驅(qū)或后繼的存儲(chǔ)地址。這兩個(gè)部分的的一起組成一個(gè)數(shù)據(jù)元素的存儲(chǔ)映像,稱為結(jié)點(diǎn),若干個(gè)結(jié)點(diǎn)鏈接成鏈表。如果一個(gè)結(jié)點(diǎn)中只含一個(gè)指針的鏈表,則稱單鏈表。單鏈表中結(jié)點(diǎn)類描述如下:clas
31、s Node private Object data; / 存放結(jié)點(diǎn)值private Node next; / 后繼結(jié)點(diǎn)的引用 / 無參數(shù)時(shí)的構(gòu)造函數(shù)public Node() this(null, null);/帶一個(gè)參數(shù)時(shí)的構(gòu)造函數(shù)public Node(Object data) this(data, null);/帶兩個(gè)參數(shù)時(shí)的構(gòu)造函數(shù)public Node(Object data, Node next) this.data = data;this.next = next;【核心算法提示】1 鏈表建立操作的基本步驟:鏈表是一個(gè)動(dòng)態(tài)的結(jié)構(gòu),它不需要予分配空間,因此建立鏈表的過程是一個(gè)結(jié)點(diǎn)“
32、逐個(gè)插入” 的過程。先建立一個(gè)只含頭結(jié)點(diǎn)的空單鏈表,然后依次生成新結(jié)點(diǎn),再不斷地將其插入到鏈表的頭部或尾部,分別稱其為“頭插法”和“尾插法”。2 鏈表查找操作的基本步驟:因鏈表是一種"順序存取"的結(jié)構(gòu),則要在帶頭結(jié)點(diǎn)的鏈表中查找到第 i個(gè) 元素,必須從頭結(jié)點(diǎn)開始沿著后繼指針依次"點(diǎn)數(shù)",直到點(diǎn)到第 i 個(gè)結(jié)點(diǎn)為止,如果查找成功,則用e返回第i個(gè)元素值。頭結(jié)點(diǎn)可看成是第0個(gè)結(jié)點(diǎn)。3 鏈表插入操作的基本步驟:先確定要插入的位置,如果插入位置合法,則再生成新的結(jié)點(diǎn),最后通過修改鏈將新結(jié)點(diǎn)插入到指定的位置上。4 鏈表刪除操作的基本步驟:先確定要?jiǎng)h除的結(jié)點(diǎn)位置,如
33、果位置合法,則再通過修改鏈?zhǔn)贡粍h結(jié)點(diǎn)從鏈表中“卸下”,最后釋放被刪結(jié)點(diǎn)的空間。 【核心算法描述】用頭插法創(chuàng)建帶頭結(jié)點(diǎn)的單鏈表操作算法void creat() throws Exception /*輸入一系列整數(shù),以0標(biāo)志結(jié)束,將這些整數(shù)作為/data域并用頭插法建立一個(gè)帶頭結(jié)點(diǎn)的單鏈表 Scanner sc = new Scanner(System.in);/ 構(gòu)造用于輸入的對(duì)象 for (int x=sc.nextInt(); x!=0; x=sc.nextInt()/ 輸入n個(gè)元素的值insert(0, x);/ 生成新結(jié)點(diǎn),插入到表頭在當(dāng)前帶頭結(jié)點(diǎn)的單鏈表上的查找操作算法Object g
34、et(int i) throws Exception Node p = head.getNext();/ 初始化,p指向首結(jié)點(diǎn),j為計(jì)數(shù)器int j = 0;while (p != null && j < i) / 從首結(jié)點(diǎn)開始向后查找,直到p指向第i個(gè)結(jié)點(diǎn)或p為空p = p.getNext();/ 指向后繼結(jié)點(diǎn)+j;/ 計(jì)數(shù)器的值增1if (j > i | p = null) / i小于0或者大于表長(zhǎng)減1throw new Exception("第" + i + "個(gè)元素不存在");/ 拋出異常return p.getDat
35、a(); / 返回結(jié)點(diǎn)p的數(shù)據(jù)域的值在當(dāng)前帶頭結(jié)點(diǎn)的單鏈表上的插入操作算法void insert(int i, Object x) throws Exception Node p = head;/ 初始化p為頭結(jié)點(diǎn),j為計(jì)數(shù)器int j = -1;while (p != null && j < i - 1) / 尋找i個(gè)結(jié)點(diǎn)的前驅(qū)p = p.getNext();+j;/ 計(jì)數(shù)器的值增1if (j > i - 1 | p = null) / i不合法throw new Exception("插入位置不合理");/ 輸出異常Node s = new
36、Node(x); / 生成新結(jié)點(diǎn)s.setNext(p.getNext();/ 插入單鏈表中p.setNext(s);在當(dāng)前帶頭結(jié)點(diǎn)的單鏈表上的刪除操作算法void remove(int i) throws Exception Node p = head;/ 初始化p為頭結(jié)點(diǎn),j為計(jì)數(shù)器int j = -1;while (p.getNext() != null && j < i - 1) / 尋找i個(gè)結(jié)點(diǎn)的前驅(qū)p = p.getNext();+j;/ 計(jì)數(shù)器的值增1if (j > i - 1 | p.getNext() = null) / i小于0或者大于表長(zhǎng)減1t
37、hrow new Exception("刪除位置不合理");/ 輸出異常p.setNext(p.getNext().getNext();/ 刪除結(jié)點(diǎn)3源程序代碼參考package sy;import java.util.Scanner;/單鏈表的結(jié)點(diǎn)類class Node private Object data; / 存放結(jié)點(diǎn)值private Node next; / 后繼結(jié)點(diǎn)的引用public Node() / 無參數(shù)時(shí)的構(gòu)造函數(shù)this(null, null);public Node(Object data) / 構(gòu)造值為data的結(jié)點(diǎn)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; /實(shí)現(xiàn)鏈表的基本操作類 class LinkList Node head=new Node();/生成一個(gè)帶頭結(jié)點(diǎn)
39、的空鏈表 / 根據(jù)輸入的一系列整數(shù),以0標(biāo)志結(jié)束,用頭插法建立單鏈表 public void creat() throws Exception Scanner sc = new Scanner(System.in); / 構(gòu)造用于輸入的對(duì)象 for (int x=sc.nextInt(); x!=0; x=sc.nextInt() / 輸入若干個(gè)數(shù)據(jù)元素的值(以0結(jié)束)insert(0, x);/ 生成新結(jié)點(diǎn),插入到表頭 /返回帶頭結(jié)點(diǎn)的單鏈表中第i個(gè)結(jié)點(diǎn)的數(shù)據(jù)域的值。其中:0icurLen-1 public Object get(int i) throws Exception Node p
40、= head.getNext();/ 初始化,p指向首結(jié)點(diǎn),j為計(jì)數(shù)器int j = 0;while (p != null && j < i) / 從首結(jié)點(diǎn)開始向后查找,直到p指向第i個(gè)結(jié)點(diǎn)或p為空p = p.getNext();/ 指向后繼結(jié)點(diǎn)+j;/ 計(jì)數(shù)器的值增1if (j > i | p = null) / i小于0或者大于表長(zhǎng)減1throw new Exception("第" + i + "個(gè)元素不存在");/ 拋出異常return p.getData(); / 返回結(jié)點(diǎn)p的數(shù)據(jù)域的值 /在帶頭結(jié)點(diǎn)的單鏈表中的第i個(gè)
41、數(shù)據(jù)元素之前插入一個(gè)值為x的元素 public void insert(int i, Object x) throws Exception Node p = head;/ 初始化p為頭結(jié)點(diǎn),j為計(jì)數(shù)器int j = -1;while (p != null && j < i - 1) / 尋找i個(gè)結(jié)點(diǎn)的前驅(qū)p = p.getNext();+j;/ 計(jì)數(shù)器的值增1if (j > i - 1 | p = null) / i不合法throw new Exception("插入位置不合理");/ 輸出異常Node s = new Node(x); / 生成
42、新結(jié)點(diǎn)s.setNext(p.getNext();/ 插入單鏈表中p.setNext(s); / 刪除帶頭結(jié)點(diǎn)的第i個(gè)數(shù)據(jù)元素。其中i取值范圍為:0ilength()- 1,如果i值不在此范圍則拋出異常public void remove(int i) throws Exception Node p = head;/ 初始化p為頭結(jié)點(diǎn),j為計(jì)數(shù)器int j = -1;while (p.getNext() != null && j < i - 1) / 尋找i個(gè)結(jié)點(diǎn)的前驅(qū)p = p.getNext();+j;/ 計(jì)數(shù)器的值增1if (j > i - 1 | p.get
43、Next() = null) / i小于0或者大于表長(zhǎng)減1throw new Exception("刪除位置不合理");/ 輸出異常p.setNext(p.getNext().getNext();/ 刪除結(jié)點(diǎn) / 輸出線性表中的數(shù)據(jù)元素public void display() Node p = head.getNext();/ 取出帶頭結(jié)點(diǎn)的單鏈表中的首結(jié)點(diǎn)元素while (p != null) System.out.print(p.getData() + " ");/ 輸出數(shù)據(jù)元素的值p = p.getNext();/ 取下一個(gè)結(jié)點(diǎn)System.ou
44、t.println();/ 換行 /測(cè)試類 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("請(qǐng)輸入鏈表中的各個(gè)數(shù)據(jù)元素(0為結(jié)束):"); L.creat(); System.out.println("建立的單鏈表為:"); L.display(); System.out.print
45、ln("請(qǐng)輸入待插入的位置i(0curLen):"); int i=sc.nextInt(); System.out.println("請(qǐng)輸入待插入的數(shù)據(jù)值x:"); int x= sc.nextInt(); L.insert(i, x); System.out.println("插入后的鏈表為:"); L.display(); System.out.println("請(qǐng)輸入待刪除元素的位置(0curLen-1):"); i=sc.nextInt(); L.remove(i); System.out.println
46、("刪除后的鏈表為:"); L.display(); System.out.println("請(qǐng)輸入待查找的數(shù)據(jù)元素的位序號(hào)(0curLen-1):"); i=sc.nextInt(); Object o=L.get(i); System.out.println("此單鏈表中第"+i+"個(gè)結(jié)點(diǎn)的數(shù)據(jù)元素值為"+o); 4運(yùn)行結(jié)果參考如圖2-1所示:圖2-1: 驗(yàn)證性實(shí)驗(yàn)運(yùn)行結(jié)果備注: 以下設(shè)計(jì)性和應(yīng)用性實(shí)驗(yàn)內(nèi)容學(xué)生可根據(jù)自己的掌握程度或興趣自行選擇其一或其二完成。七、設(shè)計(jì)性實(shí)驗(yàn)編程實(shí)現(xiàn)在雙向循環(huán)鏈表上的插入和刪除操
47、作1 實(shí)驗(yàn)要求(1)輸入鏈表的長(zhǎng)度和各元素的值,用尾插法建立雙向循環(huán)鏈表,并輸出鏈表中各元素值,觀察輸入的內(nèi)容與輸出的內(nèi)容是否一致。(2)在雙向循環(huán)鏈表的第i個(gè)元素之前插入一個(gè)值為x的元素,并輸出插入后的鏈表中各元素值。(3)刪除雙向循環(huán)鏈表中第i個(gè)元素,并輸出刪除后的鏈表中各元素值。(4)在雙向循環(huán)鏈表中查找值為x元素,如果查找成功,則顯示該元素在鏈表中的位序號(hào),否則顯示該元素不存在。2核心算法提示 雙向循環(huán)鏈表中的結(jié)點(diǎn)類描述如下: class DuLNode private Object data;/ 存放結(jié)點(diǎn)值 private DuLNode prior; / 前驅(qū)結(jié)點(diǎn)的引用 priva
48、te DuLNode next; / 后繼結(jié)點(diǎn)的引用 雙向循環(huán)鏈表類描述如下:class DuCircleLinkList private DuLNode head;/ 雙向循環(huán)鏈表的頭結(jié)點(diǎn)/ 構(gòu)造函數(shù):構(gòu)造一個(gè)只含頭結(jié)點(diǎn)的空雙向循環(huán)鏈表public DuCircleLinkList() head = new DuLNode(); / 初始化頭結(jié)點(diǎn)head.setPrior(head);/ 初始化頭結(jié)點(diǎn)的前驅(qū)和后繼head.setNext(head); 不論是建立雙向循環(huán)鏈表還是在雙向循環(huán)鏈表中進(jìn)行插入、刪除和查找操作,其操作方法和步驟都跟單鏈表類似。只不過要注意兩點(diǎn):(1)凡是在操作中遇到有
49、修改鏈的地方,都要進(jìn)行前驅(qū)和后繼兩個(gè)指針的修改。(2)單鏈表操作算法中的判斷條件:p= =null 或p!=null ,在循環(huán)鏈表的操作算法中則需改為:p= =head或p!= head,其中head為鏈表的頭指針。3核心算法描述 在當(dāng)前帶頭結(jié)點(diǎn)的雙向循環(huán)鏈表上的插入操作的算法void insert(int i, Object x) throws Exception DuLNode p = head.getNext();/ 初始化,p指向首結(jié)點(diǎn),j為計(jì)數(shù)器int j = 0;while (!p.equals(head) && j < i) / 確定插入位置ip = p.g
50、etNext();/ 指向后繼結(jié)點(diǎn)+j;/ 計(jì)數(shù)器的值增1if (j !=i ) / i小于0或者大于表長(zhǎng)throw new Exception("插入位置不合理");/ 輸出異常DuLNode s = new DuLNode(x);/ 生成新結(jié)點(diǎn)sp.getPrior().setNext(s); /將結(jié)點(diǎn)s插入到p結(jié)點(diǎn)的前面s.setPrior(p.getPrior();s.setNext(p);p.setPrior(s); 在當(dāng)前帶頭結(jié)點(diǎn)的雙向循環(huán)鏈表上的刪除操作算法void remove(int i) throws Exception DuLNode p = head
51、.getNext();/ 初始化,p指向首節(jié)點(diǎn)結(jié)點(diǎn),j為計(jì)數(shù)器int j = 0;while (!p.equals(head) && j < i) / 確定刪除位置ip = p.getNext();/ 指向后繼結(jié)點(diǎn)+j;/ 計(jì)數(shù)器的值增1if (j != i|p.equals(head) / i小于0或者大于表長(zhǎng)減1throw new Exception("刪除位置不合理");/ 輸出異常p.getPrior().setNext(p.getNext();p.getNext().setPrior(p.getPrior(); 在帶頭結(jié)點(diǎn)的雙向循環(huán)鏈表上的查找操作算法int indexOf(Object x) DuLNod
溫馨提示
- 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請(qǐng)下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請(qǐng)聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
- 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會(huì)有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
- 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
- 5. 人人文庫(kù)網(wǎng)僅提供信息存儲(chǔ)空間,僅對(duì)用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對(duì)用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對(duì)任何下載內(nèi)容負(fù)責(zé)。
- 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請(qǐng)與我們聯(lián)系,我們立即糾正。
- 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶因使用這些下載資源對(duì)自己和他人造成任何形式的傷害或損失。
最新文檔
- 工地宰羊過節(jié)活動(dòng)方案
- 少年向上活動(dòng)方案
- 小小特種兵訓(xùn)練活動(dòng)方案
- 展播心得征集活動(dòng)方案
- 小微企業(yè)信貸活動(dòng)方案
- 希望小屋走訪活動(dòng)方案
- 工會(huì)作品征集活動(dòng)方案
- 巧手搭建活動(dòng)方案
- 小班教育活動(dòng)方案
- 市場(chǎng)特價(jià)活動(dòng)方案
- 2024版標(biāo)本采集課件
- 招生就業(yè)處2025年工作計(jì)劃
- 市場(chǎng)營(yíng)銷學(xué)練習(xí)及答案(吳健安)
- Unit 4 Friends forever Understanding ideas 課件高中英語外研版(2019)必修第一冊(cè)-2
- 脊柱健康與中醫(yī)養(yǎng)生課件
- 甘肅省慶陽市(2024年-2025年小學(xué)五年級(jí)語文)人教版期末考試(下學(xué)期)試卷及答案
- 2024馬克思主義發(fā)展史第2版配套題庫(kù)里面包含考研真題課后習(xí)題和章節(jié)題庫(kù)
- 基層管理角色轉(zhuǎn)變
- 2024年輸配電及用電工程職稱評(píng)審題庫(kù)-多選、判斷
- 急救車藥品管理制度
- 4.1中國(guó)特色社會(huì)主義進(jìn)入新時(shí)代+課件-高中政治統(tǒng)編版必修一中國(guó)特色社會(huì)主義+(36張)
評(píng)論
0/150
提交評(píng)論