2012級(jí)算法與數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)指導(dǎo)書18

1、 算法與數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)指導(dǎo)書 實(shí)驗(yàn)課程類別：課程內(nèi)實(shí)驗(yàn) 實(shí)驗(yàn)課程性質(zhì)：必修 適用專業(yè)、年級(jí)：2012級(jí)計(jì)算機(jī)大類 開課院、系：計(jì)算機(jī)科學(xué)與工程學(xué)院 學(xué)時(shí)：18 編寫依據(jù)：算法與數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)教學(xué)大綱 修訂時(shí)間：2014年2月 算法與數(shù)據(jù)結(jié)構(gòu)課程實(shí)驗(yàn)指導(dǎo)書(以下簡(jiǎn)稱：指導(dǎo)書)是針對(duì)計(jì)算機(jī)學(xué)院所開設(shè) 的對(duì)應(yīng)課程的上機(jī)實(shí)驗(yàn)而編寫的教學(xué)文件，供學(xué)生上機(jī)實(shí)驗(yàn)時(shí)使用。 上機(jī)的工作環(huán)境要求：Windows 2000或以上操作系統(tǒng)、 VC+ 6.0或者其它高級(jí)程序設(shè) 計(jì)語言。 學(xué)生應(yīng)按指導(dǎo)教師的要求獨(dú)立完成實(shí)驗(yàn)，并按要求撰寫實(shí)驗(yàn)報(bào)告。 每一個(gè)實(shí)驗(yàn)，編程上機(jī)調(diào)試并且提交電子文檔實(shí)驗(yàn)報(bào)告，以學(xué)號(hào)姓名作為文件名上傳。

2、報(bào)告內(nèi)容至少包含如下內(nèi)容： 1、 學(xué)生基本情況：專業(yè)班級(jí)、學(xué)號(hào)、姓名 2、 實(shí)驗(yàn)題目、實(shí)驗(yàn)內(nèi)容 3、 設(shè)計(jì)分析 4、 源程序代碼 5、 測(cè)試用例(盡量覆蓋所有分支) 6、 實(shí)驗(yàn)總結(jié) 實(shí)驗(yàn)內(nèi)容與學(xué)時(shí)分配 序 次 實(shí)驗(yàn) 題目 實(shí)驗(yàn) 類型 基本技能訓(xùn)練 學(xué) 時(shí) -一 線性結(jié)構(gòu)綜合應(yīng)用 基礎(chǔ)性 (1) 掌握線性結(jié)構(gòu)的常用操作； (2) 能夠應(yīng)用線性結(jié)構(gòu)解決比較簡(jiǎn)單的問題。 10 -二 非線性結(jié)構(gòu)綜合應(yīng) 用 設(shè)計(jì)性 (1) 掌握樹形、圖形結(jié)構(gòu)的插入、刪除、 查找等算法； (2) 能夠應(yīng)用二叉樹解決比較簡(jiǎn)單的問題。 4 三 查找技術(shù)綜合應(yīng)用 設(shè)計(jì)性 (1) 熟練掌握查找的常用算法； (2) 設(shè)計(jì)和應(yīng)用查找

3、算法解決簡(jiǎn)單的實(shí)際問題。 2 四 排序技術(shù)綜合應(yīng)用 基礎(chǔ)性 (1) 熟練掌握常用的排序方法，并掌握用咼級(jí)語言實(shí) 現(xiàn)排序算法的方法； (2) 深刻理解排序的定義和各種排序方法的特點(diǎn)，并 能加以靈活應(yīng)用； (3) 了解各種方法的排序過程及其依據(jù)的原則，并掌 握各種排序方法的時(shí)間復(fù)雜度的分析方法。 2 實(shí)驗(yàn)說明 實(shí)驗(yàn)一、線性結(jié)構(gòu)綜合應(yīng)用 (一) 順序表的應(yīng)用 1、實(shí)驗(yàn)?zāi)康模?(1) 掌握用VC+上機(jī)調(diào)試線性表的基本方法； (2) 掌握順序表的存儲(chǔ)結(jié)構(gòu)以及基本運(yùn)算的實(shí)現(xiàn)。 2、實(shí)驗(yàn)內(nèi)容 約瑟夫環(huán)問題：設(shè)編號(hào)為 1, 2, 3,n的n(n0)個(gè)人按順時(shí)針方向 圍坐一圈，m為任意一個(gè)正整數(shù)。從第一個(gè)人開始

4、順時(shí)針方向自1起順序報(bào)數(shù)， 報(bào)到m時(shí)停止并且報(bào) m的人出列，再從他的下一個(gè)人開始重新從1報(bào)數(shù)，報(bào) 到m時(shí)停止并且報(bào) m的人出列。如此下去，直到所有人全部出列為止。要求 設(shè)計(jì)一個(gè)程序模擬此過程，對(duì)任意給定的m和n,求出出列編號(hào)序列。 3、實(shí)驗(yàn)要求：用順序表實(shí)現(xiàn)。 (二) 鏈表的應(yīng)用 1、實(shí)驗(yàn)?zāi)康模?(1) 熟練掌握鏈表結(jié)構(gòu)及有關(guān)算法的設(shè)計(jì)； (3) 掌握用鏈表表示特定形式的數(shù)據(jù)的方法，并能編寫出有關(guān)運(yùn)算的算法。 2、實(shí)驗(yàn)內(nèi)容：一元多項(xiàng)式求和。 把任意給定的兩個(gè)一元多項(xiàng)式P(x) ,Q(x)輸入計(jì)算機(jī)，計(jì)算它們的和 并輸出計(jì)算結(jié)果。 3、實(shí)驗(yàn)說明： 一元多項(xiàng)式可以用單鏈表表示，結(jié)點(diǎn)結(jié)構(gòu)圖示如下：

5、coef exp n ext 一元多項(xiàng)式鏈表的結(jié)點(diǎn)結(jié)構(gòu) 元多項(xiàng)式算法偽代碼如下： 1. 工作指針p、q初始化； 2. while (p存在且q存在)執(zhí)行下列三種情形之一 2.1如果p-expvq-exp，則指針p后移; 2.2 如果 p-expq-exp，則 2.2.1將結(jié)點(diǎn)q插入到結(jié)點(diǎn)p之前； 2.2.2指針q指向原指結(jié)點(diǎn)的下一個(gè)結(jié)點(diǎn)； 2.3 如果 p-exp=q-exp，則 2.3.1 p-coef =p-coef+q-coef ； 2.3.2如果p-coef =0，則執(zhí)行下列操作，否則，指針 p后移; 2.3.2.1刪除結(jié)點(diǎn)p； 2.3.2.2使指針p指向它原指結(jié)點(diǎn)的下一個(gè)結(jié)點(diǎn)； 2.

6、3.3刪除結(jié)點(diǎn)q; 2.3.4使指針q指向它原指結(jié)點(diǎn)的下一個(gè)結(jié)點(diǎn)； 3. 如果q不為空，將結(jié)點(diǎn)q鏈接在第一個(gè)單鏈表的后面； （三）棧的應(yīng)用 1、實(shí)驗(yàn)?zāi)康模?（1 ）掌握棧的特點(diǎn)及其存儲(chǔ)方法； （2）掌握棧的常見算法以及程序?qū)崿F(xiàn)； （3 ）了解遞歸的工作過程。 2、實(shí)驗(yàn)內(nèi)容：表達(dá)式求值問題。 這里限定的表達(dá)式求值問題是：用戶輸入一個(gè)包含“ +、 -”、 “ *、 “/、”正整 數(shù)和圓括號(hào)的合法數(shù)學(xué)表達(dá)式，計(jì)算該表達(dá)式的運(yùn)算結(jié)果。 算術(shù)表達(dá)式求值過程是：STEP 1:先將算術(shù)表達(dá)式轉(zhuǎn)換成后綴表達(dá)式。 STEP 2:然后對(duì)該后綴表達(dá)式求值。 3、實(shí)驗(yàn)說明：在設(shè)計(jì)相關(guān)算法中用到棧，這里采用順序棧存儲(chǔ)結(jié)

7、構(gòu)。 中綴表達(dá)式exp二二后綴表達(dá)式postexp偽代碼如下： 初始化運(yùn)算符棧op; 將=進(jìn)棧； 從exp讀取字符ch; while （ch!=0） if （ch不為運(yùn)算符） 將后續(xù)的所有數(shù)字均依次存放到postexp中，并以字符#標(biāo)志數(shù)值串結(jié)束； else switch（Precede（op棧頂運(yùn)算符,ch） case :/棧頂運(yùn)算符應(yīng)先執(zhí)行，所以出棧并存放到postexp中 退棧運(yùn)算符并將其存放到 postexp中;break; 若字符串exp掃描完畢，則將運(yùn)算符棧op中=之前的所有運(yùn)算符依次岀棧并存放到 postexp中。最后得到后綴表達(dá)式 postexp; 對(duì)后綴表達(dá)式postexp求

8、值偽代碼如下: while （從 postexp 讀取字符 ch,ch!=0） 若ch為數(shù)字，將后續(xù)的所有數(shù)字構(gòu)成一個(gè)整數(shù)存放到數(shù)值棧st中。 若ch為“ +”則，從數(shù)值棧st中退棧兩個(gè)運(yùn)算數(shù)，相加后進(jìn)棧st中。 若ch為”則從數(shù)值棧st中退棧兩個(gè)運(yùn)算數(shù)，相減后進(jìn)棧st中。 若ch為“ *則從數(shù)值棧st中退棧兩個(gè)運(yùn)算數(shù)，相乘后進(jìn)棧st中。 若ch為“/則從數(shù)值棧st中退棧兩個(gè)運(yùn)算數(shù)，相除后進(jìn)棧st中（若除數(shù)為零，則提示相應(yīng)的錯(cuò)誤 信息）。 若字符串postexp掃描完畢，則數(shù)值棧op中的棧頂元素就是表達(dá)式的值。 (四) 隊(duì)列的應(yīng)用 1、實(shí)驗(yàn)?zāi)康模?(1) 掌握隊(duì)列的特點(diǎn)及其存儲(chǔ)方法； (2)

9、掌握隊(duì)列的常見算法和程序?qū)崿F(xiàn)。 2、實(shí)驗(yàn)內(nèi)容：火車車廂重排問題。 3、實(shí)驗(yàn)說明： 轉(zhuǎn)軌站示意圖如下： Hi 1 1 581742963 ” 分別對(duì)k個(gè)隊(duì)列初始化； 初始化下一個(gè)要輸出的車廂編號(hào)nowOut = 1; 依次取入軌中的每一個(gè)車廂的編號(hào)； 3.1如果入軌中的車廂編號(hào)等于 nowOut，貝U 3.1.1輸岀該車廂； 3.1.2 nowOut+ ； 3.2否則，考察每一個(gè)緩沖軌隊(duì)列 for (j=1; j=k; j+) 3.2.1取隊(duì)列j的隊(duì)頭元素c； 3.2.2 如果 c=nowOut，貝U 3.2.2.1將隊(duì)列j的隊(duì)頭元素出隊(duì)并輸出； 3.2.2.2 nowOut+ ； 3.3如果入

10、軌和緩沖軌的隊(duì)頭元素沒有編號(hào)為nowOut的車廂，貝U 3.3.1求小于入軌中第一個(gè)車廂編號(hào)的最大隊(duì)尾元素所在隊(duì)列編號(hào)j; 3.3.2如果j存在，則把入軌中的第一個(gè)車廂移至緩沖軌j ； 3.3.2如果j不存在，但有多于一個(gè)空緩沖軌，則把入軌中的第一個(gè)車廂移至一個(gè) 空緩沖軌；否則車廂無法重排，算法結(jié)束； - u987654321 H3i -缶 * 1 入軌 1 1 * 1* 岀軌 H2. 火車車廂重排過程如下: 581 * H1 1 ； 入軌 H3I岀軌 742! 963 H2 (a)將369、247依次入緩沖軌 1 1 58 二！ - * ; H1 1 1 入軌 1 H3: 1 96 岀軌 H

11、2 各1移至出軌，234移至 4321 H1 1 5 ! 54321 入軌: H3 岀軌 1 87 1 H2 96 (c)將8入緩沖軌，5移至岀軌 Hi ! 987654321 - _ -尸 H3岀軌 H2 (d)將6789移至出軌 火車車廂重排算法偽代碼如下: (五) 稀疏矩陣的應(yīng)用 1、實(shí)驗(yàn)?zāi)康模?(1) 掌握掌握稀疏矩陣的表示方法及其運(yùn)算的實(shí)現(xiàn)； (2) 實(shí)現(xiàn)稀疏矩陣在三元組、十字鏈表等表示下的各運(yùn)算并分析其效率。 2、實(shí)驗(yàn)內(nèi)容 在mKn的矩陣中，有t個(gè)非零元。令 s =t/(m*n),稱3矩陣的稀疏因子, 常認(rèn)為SW 0.0時(shí)稱為稀疏矩陣。稀疏矩陣在工程中有著大量的應(yīng)用，不少工 程問題

12、都可以轉(zhuǎn)化為對(duì)稀疏矩陣的計(jì)算問題。用三元組表實(shí)現(xiàn)稀疏矩陣的轉(zhuǎn) 置，用(順序取，直接存)方法。 3、實(shí)驗(yàn)說明： 引入兩個(gè)數(shù)組作為輔助數(shù)據(jù)結(jié)構(gòu)： numnu:表示矩陣A中某列的非零元素的個(gè)數(shù)； cpotnu:初始值表示矩陣 A中某列的第一個(gè)非零元素在B中的位置。 num 與 cpot遞推關(guān)系： cpot0=0; . cpotcol=cpotcol -1+numcol -1;1 coldatav root-data，則把結(jié)點(diǎn)s插入到root的左子樹中；否則 3. 把結(jié)點(diǎn)s插入到root的右子樹中。 二叉排序樹中刪除一個(gè)結(jié)點(diǎn) f的左孩子結(jié)點(diǎn)p算法偽代碼如下: 1. 若結(jié)點(diǎn)p是葉子，則直接刪除結(jié)點(diǎn)p;

13、2. 若結(jié)點(diǎn)p只有左子樹，則只需重接p的左子樹； 若結(jié)點(diǎn)p只有右子樹，則只需重接 p的右子樹； 3. 若結(jié)點(diǎn)p的左右子樹均不空，則 3.1查找結(jié)點(diǎn)p的右子樹上的最左下結(jié)點(diǎn)s以及結(jié)點(diǎn)s的雙親結(jié)點(diǎn)par； 3.2將結(jié)點(diǎn)s數(shù)據(jù)域替換到被刪結(jié)點(diǎn) p的數(shù)據(jù)域； 3.3若結(jié)點(diǎn)p的右孩子無左子樹，則將 s的右子樹接到par的右子樹上; 否則，將s的右子樹接到結(jié)點(diǎn) par的左子樹上； 3.4刪除結(jié)點(diǎn)s； 實(shí)驗(yàn)四、排序技術(shù)綜合應(yīng)用 (九) 排序技術(shù)綜合應(yīng)用 1、實(shí)驗(yàn)?zāi)康模?(1)熟練掌握常用的排序方法，并掌握用高級(jí)語言實(shí)現(xiàn)排序算法的方法； (2 )深刻理解排序的定義和各種排序方法的特點(diǎn)，并能加以靈活應(yīng)用； (3

14、) 了解各種方法的排序過程及其依據(jù)的原則，并掌握各種排序方法的時(shí)間 復(fù)雜度的分析方法。 2、 實(shí)驗(yàn)內(nèi)容：對(duì)希爾排序、快速排序、歸并排序任意選擇兩種排序方法進(jìn)行比較。 任意選擇希爾排序、快速排序、歸并排序中兩種排序方法，對(duì)任意給定一 組數(shù)據(jù)：?jiǎn)卧觥螠p、亂碼等，對(duì)它們進(jìn)行比較分析。 3、實(shí)驗(yàn)說明： 希爾排序算法如下： void ShellSort(int r , int n) for (d=n/2; d=1; d=d/2)以增量為d進(jìn)行直接插入排序 for (i=d+1; i0 j=j-d) rj+d=rj;/記錄后移d個(gè)位置 rj+d=r0; 快速排序算法偽碼如下: void QuickSor

15、t(int r , int first, int end) if (firstvend) / 遞歸結(jié)束 pivot=Partition(r, first, end); QuickSort(r, first, pivot-1); QuickSort(r, pivot+1, end); int Partition(int r , int first, int end) i=first; j=end;/ 初始化 while (ij) while (ij if (ij) ri rj; i+; while (ij if (ij) rjri; j-; / 一次劃分 /遞歸地對(duì)左側(cè)子序列進(jìn)行快速排序 /遞歸

16、地對(duì)右側(cè)子序列進(jìn)行快速排序 /右側(cè)掃描 /將較小記錄交換到前面 /左側(cè)掃描 /將較大記錄交換到后面 retutn i; /i為軸值記錄的最終位置 修訂者：蔡瓊 When you are old and grey and full of sleep, And no ddi ng by the fire, take dow n this book, And slowly read, and dream of the soft look Your eyes had once, and of their shadows deep; How many loved your mome nts of gla

17、d grace, And loved your beauty with love false or true, But one man loved the pilgrim soul in you. And loved the sorrows of your cha nging face; And bending dow n beside the glow ing bars, Murmur, a little sadly, how love fled And paced upon the mountains overhead And hid his face amid a crowd of st

18、ars. The furthest dista nee in the world Is not betwee n life and death But whe n I sta nd in front of you Yet you dont know that I love you. The furthest dista nee in the world Is not whe n I sta nd in front of you Yet you cant see my love But whe n un doubtedly knowing the love from both Yet cannot be together. The furthest dista nee in the world Is not being apart while being in