《數(shù)據(jù)結(jié)構(gòu)》實(shí)驗(yàn)指導(dǎo)書

PAGEPAGE1《數(shù)據(jù)結(jié)構(gòu)》上機(jī)實(shí)驗(yàn)指導(dǎo)書主編：高艷霞軟件學(xué)院數(shù)據(jù)結(jié)構(gòu)課程組2008年8月23日目錄TOC\o"1-1"\h\z\u《數(shù)據(jù)結(jié)構(gòu)》實(shí)驗(yàn)?zāi)康呐c要求 1實(shí)驗(yàn)一線性表的基本操作及其應(yīng)用 4實(shí)驗(yàn)二棧和隊(duì)列的基本操作及其應(yīng)用 7實(shí)驗(yàn)三二叉樹的基本運(yùn)算 11實(shí)驗(yàn)四哈夫曼樹與哈夫曼編碼 13實(shí)驗(yàn)五圖的基本操作 14實(shí)驗(yàn)六圖的應(yīng)用 15實(shí)驗(yàn)七查找應(yīng)用（哈希表的應(yīng)用） 17實(shí)驗(yàn)八排序 20

《數(shù)據(jù)結(jié)構(gòu)》實(shí)驗(yàn)?zāi)康呐c要求一、實(shí)驗(yàn)?zāi)康臄?shù)據(jù)結(jié)構(gòu)是信息與計(jì)算科學(xué)專業(yè)中一門重要的專業(yè)基礎(chǔ)課程。當(dāng)用計(jì)算機(jī)來解決實(shí)際問題時(shí)，就要涉及到數(shù)據(jù)的表示及數(shù)據(jù)的處理，而數(shù)據(jù)表示及數(shù)據(jù)處理正是數(shù)據(jù)結(jié)構(gòu)課程的主要研究對(duì)象，通過這兩方面內(nèi)容的學(xué)習(xí)，為后續(xù)課程，特別是軟件方面的課程打下了厚實(shí)的知識(shí)基礎(chǔ)，同時(shí)也提供了必要的技能訓(xùn)練。因此，數(shù)據(jù)結(jié)構(gòu)課程在計(jì)算機(jī)應(yīng)用專業(yè)中具有舉足輕重的作用。

本課程的任務(wù)是：通過實(shí)踐，學(xué)生對(duì)常用數(shù)據(jù)結(jié)構(gòu)的基本概念及其不同的實(shí)現(xiàn)方法的理論得到進(jìn)一步的掌握，并對(duì)在不同存儲(chǔ)結(jié)構(gòu)上實(shí)現(xiàn)不同的運(yùn)算方式和技巧有所體會(huì)。二、實(shí)驗(yàn)要求1．準(zhǔn)備好上機(jī)所需要的程序，并經(jīng)人工檢查后才能上機(jī)，以提高上機(jī)效率。對(duì)程序中自己有疑問的地方應(yīng)作記號(hào)，以便在上機(jī)時(shí)給予注意。不得抄別人所編的程序。2．上機(jī)輸入并調(diào)試所編的程序。3．上機(jī)結(jié)束后，提交實(shí)驗(yàn)報(bào)告，實(shí)驗(yàn)報(bào)告應(yīng)包括以下內(nèi)容：（1）題目；（2）算法的基本思想描述；（3）算法分析；（4）主要數(shù)據(jù)結(jié)構(gòu)描述；（5）程序流程圖；（6）程序清單；（7）運(yùn)行的結(jié)果；（8）對(duì)運(yùn)行情況所作的分析以及本次調(diào)試程序所取的經(jīng)驗(yàn)。如果程序未通過，應(yīng)分析其原因。三、實(shí)驗(yàn)步驟1．問題分析和任務(wù)的定義明確問題要求做什么，限制做什么（本步強(qiáng)調(diào)做什么，而不是怎么做）。對(duì)問題的描述應(yīng)避開算法和所涉及的數(shù)據(jù)類型，而是所完成的任務(wù)做出明確的回答。如輸入數(shù)據(jù)的類型、值的范圍以及輸入的形式；輸出數(shù)據(jù)的類型、值得范圍及輸出的形式；這異步還應(yīng)該為調(diào)試程序準(zhǔn)備好測(cè)試數(shù)據(jù)，包括合法的輸入數(shù)據(jù)和非法形式的輸入數(shù)據(jù)。數(shù)據(jù)類型和系統(tǒng)設(shè)計(jì)在設(shè)計(jì)這一步驟中分為邏輯設(shè)計(jì)和詳細(xì)設(shè)計(jì)兩步實(shí)現(xiàn)。邏輯設(shè)計(jì)指的是，為問題的描述中涉及的操作對(duì)象定義相應(yīng)的數(shù)據(jù)類型，并按照以數(shù)據(jù)結(jié)構(gòu)為中心的原則劃分模塊，定義主模塊和各抽象數(shù)據(jù)類型；詳細(xì)設(shè)計(jì)則為定義相應(yīng)的存儲(chǔ)結(jié)構(gòu)并寫出各函數(shù)的偽碼算法。在這個(gè)過程中，要綜合考慮系統(tǒng)的功能，使得系統(tǒng)結(jié)構(gòu)清晰、合理、簡(jiǎn)單和易于調(diào)試，抽象數(shù)據(jù)類型的實(shí)現(xiàn)盡可能做到數(shù)據(jù)的封裝，基本操作的規(guī)格說明盡可能的明確和具體。作為邏輯設(shè)計(jì)的結(jié)果。應(yīng)寫出每個(gè)抽象數(shù)據(jù)類型的定義（包括數(shù)據(jù)結(jié)構(gòu)的描述和每個(gè)基本操作的規(guī)格說明），各個(gè)主要模塊的算法，并畫出模塊之間的調(diào)用關(guān)系圖。詳細(xì)設(shè)計(jì)的結(jié)果是對(duì)數(shù)據(jù)結(jié)構(gòu)和基本操作的規(guī)格說明做出進(jìn)一步的求精，寫出數(shù)據(jù)存儲(chǔ)結(jié)構(gòu)的類型定義，按照算法書寫規(guī)范用類C語言寫出函數(shù)形式的算法框架。編碼實(shí)現(xiàn)和靜態(tài)檢查上機(jī)準(zhǔn)備和上機(jī)調(diào)試總結(jié)和整理實(shí)習(xí)報(bào)告四、實(shí)驗(yàn)總結(jié)對(duì)實(shí)驗(yàn)中發(fā)現(xiàn)的問題，調(diào)試中的問題分析、解決方法，對(duì)算法的改進(jìn)意見、建議、收獲、體會(huì)等。通過上機(jī)實(shí)驗(yàn)加深對(duì)課程內(nèi)容的理解，增加感性認(rèn)識(shí)，提高軟件設(shè)計(jì)、編寫及調(diào)試程序的能力。要求所編的程序能正確運(yùn)行，并提交實(shí)驗(yàn)報(bào)告。實(shí)驗(yàn)報(bào)告的基本要求為：實(shí)驗(yàn)報(bào)告參考規(guī)范：實(shí)驗(yàn)題目班級(jí)姓名學(xué)號(hào)日期需求分析：陳述程序設(shè)計(jì)的任務(wù)，強(qiáng)調(diào)程序要做什么，明確規(guī)定：1）輸入的形式和輸出值的范圍；2）輸出的形式；3）程序所能達(dá)到的功能；4）測(cè)試數(shù)據(jù)：包括正確的輸入輸出結(jié)果和錯(cuò)誤的輸入及輸出結(jié)果。概要設(shè)計(jì)：說明用到的數(shù)據(jù)結(jié)構(gòu)定義、主程序的流程及各程序模塊之間的調(diào)用關(guān)系。詳細(xì)設(shè)計(jì)：提交帶注釋的源程序或者用偽代碼寫出每個(gè)操作所涉及的算法。調(diào)試分析：1）調(diào)試過程中所遇到的問題及解決方法；2）算法的時(shí)空分析；3）經(jīng)驗(yàn)與體會(huì)。用戶使用說明：說明如何使用你的程序，詳細(xì)列出每一步操作步驟。測(cè)試結(jié)果：列出對(duì)于給定的輸入所產(chǎn)生的輸出結(jié)果。若有可能，測(cè)試隨輸入規(guī)模的增長(zhǎng)所用算法的實(shí)際運(yùn)行時(shí)間的變化。

實(shí)驗(yàn)一線性表的基本操作及其應(yīng)用一、實(shí)驗(yàn)?zāi)康?、幫助讀者復(fù)習(xí)C++語言程序設(shè)計(jì)中的知識(shí)。2、熟悉線性表的邏輯結(jié)構(gòu)。3、熟悉線性表的基本運(yùn)算在兩種存儲(chǔ)結(jié)構(gòu)上的實(shí)現(xiàn)，其中以熟悉鏈表的操作為側(cè)重點(diǎn)。二、實(shí)驗(yàn)內(nèi)容本次實(shí)驗(yàn)提供3個(gè)題目，每個(gè)題目都標(biāo)有難度系數(shù)，*越多難度越大，學(xué)生可以根據(jù)自己的情況任選一個(gè)。題目一：?jiǎn)捂湵淼幕静僮鳎?）[問題描述]實(shí)現(xiàn)帶頭結(jié)點(diǎn)的單鏈表的建立、求長(zhǎng)度，取元素、修改元素、插入、刪除等單鏈表的基本操作。[基本要求]（1）依次從鍵盤讀入數(shù)據(jù)，建立帶頭結(jié)點(diǎn)的單鏈表；（2）輸出單鏈表中的數(shù)據(jù)元素（3）求單鏈表的長(zhǎng)度；（4）根據(jù)指定條件能夠取元素和修改元素；（5）實(shí)現(xiàn)在指定位置插入和刪除元素的功能。[測(cè)試數(shù)據(jù)]由學(xué)生任意指定。題目二：約瑟夫環(huán)（**）

[問題描述]

約瑟夫（Joseph）問題的一種描述是：編號(hào)為1,2,…,n的n個(gè)人按順時(shí)針方向圍坐一圈，每人持有一個(gè)密碼（正整數(shù)）。一開始任選一個(gè)正整數(shù)作為報(bào)數(shù)上限值m，從第一個(gè)人開始按順時(shí)針方向自1開始順序報(bào)數(shù)，報(bào)到m時(shí)停止報(bào)數(shù)。報(bào)m的人出列，將他的密碼作為新的m值，從他在順時(shí)針方向上的下一個(gè)人開始重新從1報(bào)數(shù)，如此下去，直至所有人全部出列為止。試設(shè)計(jì)一個(gè)程序求出出列順序。[基本要求]

利用單向循環(huán)鏈表存儲(chǔ)結(jié)構(gòu)模擬此過程，按照出列的順序印出各人的編號(hào)。

[測(cè)試數(shù)據(jù)]由學(xué)生任意指定。

如：m的初值為20；n的值為7；密碼：3，1，7，2，4，8，4；（正確的輸出結(jié)果應(yīng)為6，1，4，7，2，3，5）。

(報(bào)告上要求寫出多批數(shù)據(jù)測(cè)試結(jié)果)

[實(shí)現(xiàn)提示]

程序運(yùn)行后首先要求用戶輸入初始報(bào)數(shù)上限值m，人數(shù)n,(設(shè)n≤30)。然后輸入各人的密碼。[選作內(nèi)容]

向上述程序中添加在順序結(jié)構(gòu)上實(shí)現(xiàn)的部分。題目三：多項(xiàng)式的表示及相加（***）[問題描述]設(shè)計(jì)一個(gè)算法，以實(shí)現(xiàn)一元稀疏多項(xiàng)式的加法運(yùn)算。[基本要求]（1）輸入并建立多項(xiàng)式；（2）輸出多項(xiàng)式，輸出形式為整數(shù)序列：n，c1，e1，c2，e2，……，cn，en，其中n是多項(xiàng)式的項(xiàng)數(shù)，ci和ei分別是第i項(xiàng)的系數(shù)和指數(shù)，序列按指數(shù)降序排列；（3）多項(xiàng)式a和b相加，建立多項(xiàng)式a+b。[測(cè)試數(shù)據(jù)]由學(xué)生任意指定。[實(shí)現(xiàn)提示]

用帶表頭結(jié)點(diǎn)的單鏈表存儲(chǔ)多項(xiàng)式。[選作內(nèi)容]

多項(xiàng)式a和b相減，建立多項(xiàng)式a-b。三、實(shí)驗(yàn)前的準(zhǔn)備工作1、掌握線性表的邏輯結(jié)構(gòu)。2、掌握線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。3、熟練掌握線性表的插入、刪除等操作。四、實(shí)驗(yàn)報(bào)告要求1、實(shí)驗(yàn)報(bào)告要按照實(shí)驗(yàn)報(bào)告格式規(guī)范書寫。2、實(shí)驗(yàn)上要寫出多批測(cè)試數(shù)據(jù)的運(yùn)行結(jié)果。3、結(jié)合運(yùn)行結(jié)果，對(duì)程序進(jìn)行分析。

實(shí)驗(yàn)二棧和隊(duì)列的基本操作及其應(yīng)用一、實(shí)驗(yàn)?zāi)康?、掌握棧和隊(duì)列的順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，以便在實(shí)際中靈活應(yīng)用。2、掌握棧和隊(duì)列的特點(diǎn)，即后進(jìn)先出和先進(jìn)先出的原則。3、掌握棧和隊(duì)列的基本運(yùn)算，如：入棧與出棧，入隊(duì)與出隊(duì)等運(yùn)算在順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)上的實(shí)現(xiàn)。二、實(shí)驗(yàn)內(nèi)容本次實(shí)驗(yàn)提供2個(gè)題目，每個(gè)題目都標(biāo)有難度系數(shù)，*越多難度越大，學(xué)生可以根據(jù)自己的情況任選一個(gè)！題目一：回文判斷（*）[問題描述]對(duì)于一個(gè)從鍵盤輸入的字符串，判斷其是否為回文?；匚募凑葱蛳嗤?。如“abba”是回文，而“abab”不是回文。[基本要求]（1）數(shù)據(jù)從鍵盤讀入；（2）輸出要判斷的字符串；（3）利用棧的基本操作對(duì)給定的字符串判斷其是否是回文，若是則輸出“Yes”，否則輸出“No”。[測(cè)試數(shù)據(jù)]由學(xué)生任意指定。題目二：商品貨架管理（**）[問題描述]商店貨架以棧的方式擺放商品。生產(chǎn)日期越近的越靠近棧底，出貨時(shí)從棧頂取貨。一天營(yíng)業(yè)結(jié)束，如果貨架不滿，則需上貨。入貨直接將商品擺放到貨架上，則會(huì)使生產(chǎn)日期越近的商品越靠近棧頂。這樣就需要倒貨架，使生產(chǎn)日期越近的越靠近棧底。[基本要求]設(shè)計(jì)一個(gè)算法，保證每一次上貨后始終保持生產(chǎn)日期越近的商品越靠近棧底。[實(shí)現(xiàn)提示]可以用一個(gè)隊(duì)列和一個(gè)臨時(shí)棧作為周轉(zhuǎn)。[測(cè)試數(shù)據(jù)]由學(xué)生任意指定。三、實(shí)驗(yàn)前的準(zhǔn)備工作1、掌握棧的邏輯結(jié)構(gòu)和存儲(chǔ)結(jié)構(gòu)。2、熟練掌握棧的出棧、入棧等操作。3、掌握隊(duì)列的邏輯結(jié)構(gòu)和存儲(chǔ)結(jié)構(gòu)。4、熟練掌握隊(duì)列的出隊(duì)、入隊(duì)等操作四、實(shí)驗(yàn)報(bào)告要求1、實(shí)驗(yàn)報(bào)告要按照實(shí)驗(yàn)報(bào)告格式規(guī)范書寫。2、實(shí)驗(yàn)上要寫出多批測(cè)試數(shù)據(jù)的運(yùn)行結(jié)果。3、結(jié)合運(yùn)行結(jié)果，對(duì)程序進(jìn)行分析。題目三：Rails（ACM訓(xùn)練題）Description：ThereisafamousrailwaystationinPopPushThelocaltraditionisthateverytrainarrivingfromthedirectionAcontinuesinthedirectionBwithcoachesreorganizedinsomeway.AssumethatthetrainarrivingfromthedirectionAhasN<=1000coachesnumberedinincreasingorder1,2,...,N.ThechieffortrainreorganizationsmustknowwhetheritispossibletomarshalcoachescontinuinginthedirectionBsothattheirorderwillbea1,a2,...,aN.Helphimandwriteaprogramthatdecideswhetheritispossibletogettherequiredorderofcoaches.YoucanassumethatsinglecoachescanbedisconnectedfromthetrainbeforetheyenterthestationandthattheycanmovethemselvesuntiltheyareonthetrackinthedirectionB.Youcanalsosupposethatatanytimetherecanbelocatedasmanycoachesasnecessaryinthestation.ButonceacoachhasenteredthestationitcannotreturntothetrackinthedirectionAandalsoonceithasleftthestationinthedirectionBitcannotreturnbacktothestation.InputTheinputconsistsofblocksoflines.Eachblockexceptthelastdescribesonetrainandpossiblymorerequirementsforitsreorganization.InthefirstlineoftheblockthereistheintegerNdescribedabove.Ineachofthenextlinesoftheblockthereisapermutationof1,2,...,N.Thelastlineoftheblockcontainsjust0.

Thelastblockconsistsofjustonelinecontaining0.OutputTheoutputcontainsthelinescorrespondingtothelineswithpermutationsintheinput.AlineoftheoutputcontainsYesifitispossibletomarshalthecoachesintheorderrequiredonthecorrespondinglineoftheinput.OtherwiseitcontainsNo.Inaddition,thereisoneemptylineafterthelinescorrespondingtooneblockoftheinput.Thereisnolineintheoutputcorrespondingtothelast``null''blockoftheinput.SampleInput512345541230665432100SampleOutputYesNoYes題目四：SlidingWindow（ACM訓(xùn)練題）DescriptionAnarrayofsizen≤106isgiventoyou.Thereisaslidingwindowofsizekwhichismovingfromtheveryleftofthearraytotheveryright.Youcanonlyseetheknumbersinthewindow.Eachtimetheslidingwindowmovesrightwardsbyoneposition.Followingisanexample:

Thearrayis[1

3

-1

-3

5

3

6

7],andkis3.WindowpositionMinimumvalueMaximumvalue[1

3

-1]

-3

5

3

6

7

-13

1

[3

-1

-3]

5

3

6

7

-33

1

3

[-1

-3

5]

3

6

7

-35

1

3

-1

[-3

5

3]

6

7

-35

1

3

-1

-3

[5

3

6]

7

36

1

3

-1

-3

5

[3

6

7]37Yourtaskistodeterminethemaximumandminimumvaluesintheslidingwindowateachposition.InputTheinputconsistsoftwolines.Thefirstlinecontainstwointegersnandkwhicharethelengthsofthearrayandtheslidingwindow.Therearenintegersinthesecondline.OutputTherearetwolinesintheoutput.Thefirstlinegivestheminimumvaluesinthewindowateachposition,fromlefttoright,respectively.Thesecondlinegivesthemaximumvalues.SampleInput8313-1-35367SampleOutput-1-3-3-333335567

實(shí)驗(yàn)三二叉樹的基本運(yùn)算一、實(shí)驗(yàn)?zāi)康?、使學(xué)生熟練掌握二叉樹的邏輯結(jié)構(gòu)和存儲(chǔ)結(jié)構(gòu)。2、熟練掌握二叉樹的各種遍歷算法。二、實(shí)驗(yàn)內(nèi)容[問題描述]建立一棵二叉樹，試編程實(shí)現(xiàn)二叉樹的如下基本操作：1.按先序序列構(gòu)造一棵二叉鏈表表示的二叉樹T；2.對(duì)這棵二叉樹進(jìn)行遍歷：先序、中序、后序以及層次遍歷，分別輸出結(jié)點(diǎn)的遍歷序列；3.求二叉樹的深度/結(jié)點(diǎn)數(shù)目/葉結(jié)點(diǎn)數(shù)目；(選做)4.將二叉樹每個(gè)結(jié)點(diǎn)的左右子樹交換位置。（選做）[基本要求]從鍵盤接受輸入（先序），以二叉鏈表作為存儲(chǔ)結(jié)構(gòu)，建立二叉樹（以先序來建立），[測(cè)試數(shù)據(jù)]如輸入：ABCффDEфGффFффф（其中ф表示空格字符）則輸出結(jié)果為：先序：ABCDEGF中序：CBEGDFA后序：CGEFDBA層序：ABCDEFG[選作內(nèi)容]采用非遞歸算法實(shí)現(xiàn)二叉樹遍歷。

三、實(shí)驗(yàn)前的準(zhǔn)備工作1、掌握樹的邏輯結(jié)構(gòu)。2、掌握二叉樹的邏輯結(jié)構(gòu)和存儲(chǔ)結(jié)構(gòu)。3、掌握二叉樹的各種遍歷算法的實(shí)現(xiàn)。四、實(shí)驗(yàn)報(bào)告要求1、實(shí)驗(yàn)報(bào)告要按照實(shí)驗(yàn)報(bào)告格式規(guī)范書寫。2、實(shí)驗(yàn)上要寫出多批測(cè)試數(shù)據(jù)的運(yùn)行結(jié)果。3、結(jié)合運(yùn)行結(jié)果，對(duì)程序進(jìn)行分析。

實(shí)驗(yàn)四哈夫曼樹與哈夫曼編碼一、實(shí)驗(yàn)?zāi)康?、使學(xué)生熟練掌握哈夫曼樹的生成算法。2、熟練掌握哈夫曼編碼的方法。二、實(shí)驗(yàn)內(nèi)容[問題描述]已知n個(gè)字符在原文中出現(xiàn)的頻率，求它們的哈夫曼編碼。[基本要求]1.初始化：從鍵盤讀入n個(gè)字符，以及它們的權(quán)值，建立Huffman樹。（具體算法可參見教材P147的算法6.12）

2.編碼：根據(jù)建立的Huffman樹，求每個(gè)字符的Huffman編碼。對(duì)給定的待編碼字符序列進(jìn)行編碼。

[選作內(nèi)容]1.譯碼：利用已經(jīng)建立好的Huffman樹，對(duì)上面的編碼結(jié)果譯碼。譯碼的過程是分解電文中的字符串，從根結(jié)點(diǎn)出發(fā)，按字符’0’和’1’確定找左孩子或右孩子，直至葉結(jié)點(diǎn)，便求得該子串相應(yīng)的字符。2.打印

Huffman樹。［測(cè)試數(shù)據(jù)］利用教材P.148例6－2中的數(shù)據(jù)調(diào)試程序?？稍O(shè)8種符號(hào)分別為A,B,C,D,E,F,G,H。編/譯碼序列為“CFBABBFHGH”(也可自己設(shè)定數(shù)據(jù)進(jìn)行測(cè)試)。三、實(shí)驗(yàn)前的準(zhǔn)備工作1、掌握樹的邏輯結(jié)構(gòu)。2、掌握哈夫曼樹的定義及生成算法。3、掌握哈夫曼編碼的方法。四、實(shí)驗(yàn)報(bào)告要求1、實(shí)驗(yàn)報(bào)告要按照實(shí)驗(yàn)報(bào)告格式規(guī)范書寫。2、實(shí)驗(yàn)上要寫出多批測(cè)試數(shù)據(jù)的運(yùn)行結(jié)果。3、結(jié)合運(yùn)行結(jié)果，對(duì)程序進(jìn)行分析。實(shí)驗(yàn)五圖的基本操作一、實(shí)驗(yàn)?zāi)康?、使學(xué)生可以鞏固所學(xué)的有關(guān)圖的基本知識(shí)。2、熟練掌握?qǐng)D的存儲(chǔ)結(jié)構(gòu)。3、熟練掌握?qǐng)D的兩種遍歷算法。二、實(shí)驗(yàn)內(nèi)容[問題描述]對(duì)給定圖，實(shí)現(xiàn)圖的深度優(yōu)先遍歷和廣度優(yōu)先遍歷。[基本要求]以鄰接表為存儲(chǔ)結(jié)構(gòu)，實(shí)現(xiàn)連通無向圖的深度優(yōu)先和廣度優(yōu)先遍歷。以用戶指定的結(jié)點(diǎn)為起點(diǎn)，分別輸出每種遍歷下的結(jié)點(diǎn)訪問序列。【測(cè)試數(shù)據(jù)】由學(xué)生依據(jù)軟件工程的測(cè)試技術(shù)自己確定。三、實(shí)驗(yàn)前的準(zhǔn)備工作1、掌握?qǐng)D的相關(guān)概念。2、掌握?qǐng)D的邏輯結(jié)構(gòu)和存儲(chǔ)結(jié)構(gòu)。3、掌握?qǐng)D的兩種遍歷算法的實(shí)現(xiàn)。四、實(shí)驗(yàn)報(bào)告要求1、實(shí)驗(yàn)報(bào)告要按照實(shí)驗(yàn)報(bào)告格式規(guī)范書寫。2、實(shí)驗(yàn)上要寫出多批測(cè)試數(shù)據(jù)的運(yùn)行結(jié)果。3、結(jié)合運(yùn)行結(jié)果，對(duì)程序進(jìn)行分析。

實(shí)驗(yàn)六圖的應(yīng)用一、實(shí)驗(yàn)?zāi)康?、使學(xué)生可以鞏固所學(xué)的有關(guān)圖的基本知識(shí)。2、熟練掌握?qǐng)D的存儲(chǔ)結(jié)構(gòu)。3、掌握如何應(yīng)用圖解決各種實(shí)際問題。二、實(shí)驗(yàn)內(nèi)容本次實(shí)驗(yàn)提供2個(gè)題目，學(xué)生可以任選一個(gè)。題目一：最小生成樹問題[問題描述]若要在n個(gè)城市之間建設(shè)通信網(wǎng)絡(luò)，只需要假設(shè)n-1條線路即可。如何以最低的經(jīng)濟(jì)代價(jià)建設(shè)這個(gè)通信網(wǎng)，是一個(gè)網(wǎng)的最小生成樹問題。[基本要求]利用克魯斯卡爾算法求網(wǎng)的最小生成樹。要求輸出各條邊及它們的權(quán)值。［實(shí)現(xiàn)提示］通信線路一旦建成，必然是雙向的。因此，構(gòu)造最小生成樹的網(wǎng)一定是無向網(wǎng)。設(shè)圖的頂點(diǎn)數(shù)不超過30個(gè)，并為簡(jiǎn)單起見，網(wǎng)中邊的權(quán)值設(shè)成小于100的整數(shù)。圖的存儲(chǔ)結(jié)構(gòu)的選取應(yīng)和所作操作相適應(yīng)。為了便于選擇權(quán)值最小的邊，此題的存儲(chǔ)結(jié)構(gòu)既不選用鄰接矩陣的數(shù)組表示法，也不選用鄰接表，而是以存儲(chǔ)邊（帶權(quán)）的數(shù)組表示圖。［測(cè)試數(shù)據(jù)］由學(xué)生依據(jù)軟件工程的測(cè)試技術(shù)自己確定。題目二：最短路徑問題[問題描述]給定一個(gè)無向網(wǎng)，可以求得任意一對(duì)頂點(diǎn)之間的最短路徑。[基本要求]以鄰接矩陣為存儲(chǔ)結(jié)構(gòu)，用迪杰斯特拉算法求解從某一源點(diǎn)到其它頂點(diǎn)之間的最短路徑及最短路徑長(zhǎng)度。[測(cè)試數(shù)據(jù)]由學(xué)生依據(jù)軟件工程的測(cè)試技術(shù)自己確定。三、實(shí)驗(yàn)前的準(zhǔn)備工作1、掌握?qǐng)D的相關(guān)概念。2、掌握?qǐng)D的邏輯結(jié)構(gòu)和存儲(chǔ)結(jié)構(gòu)。3、掌握?qǐng)D的各種應(yīng)用的實(shí)現(xiàn)。四、實(shí)驗(yàn)報(bào)告要求1、實(shí)驗(yàn)報(bào)告要按照實(shí)驗(yàn)報(bào)告格式規(guī)范書寫。2、實(shí)驗(yàn)上要寫出多批測(cè)試數(shù)據(jù)的運(yùn)行結(jié)果。3、結(jié)合運(yùn)行結(jié)果，對(duì)程序進(jìn)行分析。

實(shí)驗(yàn)七查找應(yīng)用（哈希表的應(yīng)用）一、實(shí)驗(yàn)?zāi)康?.熟悉有關(guān)哈希表的基本概念。2.熟悉構(gòu)造哈希表的方法。3.掌握處理哈希沖突的閉散列法和開散列法。二、實(shí)驗(yàn)內(nèi)容[問題描述]程序1采用除留余數(shù)法定義哈希表，哈希表長(zhǎng)度為20，哈希函數(shù)為H(key)=key%13。產(chǎn)生沖突時(shí)采用線性探測(cè)法實(shí)現(xiàn)下面要求的功能。[基本要求]/*哈希表類型的定義*/#defineNIL–1#definem997typedefstruct{intkey;}LHashTable;/*初始化哈希表*/voidHashListInit(LHashTableHT[m])/*清空哈希表*/voidHashListClear(LHashTableHT[m])/*在哈希表中查找元素*/intHashListSearch(LHashTableHT[],intk)/*在哈希表中插入元素*/voidHashListInsert(LHashTableHT[m],intk)/*從哈希表中刪除元素*/voidHashListDelete(LHashTableHT[m],intk)/*輸出哈希表中所有元素*/voidPrintHashList(LHashTableHT[m])[問題描述]程序2采用除留余數(shù)法定義哈希表，哈希表長(zhǎng)度為20，哈希函數(shù)為H