《數(shù)據(jù)結(jié)構(gòu)課程實驗》大綱

一、《數(shù)據(jù)結(jié)構(gòu)課程實驗》的地位與作用

"數(shù)據(jù)結(jié)構(gòu)”是計算機專業(yè)一門重要的專業(yè)技術(shù)基礎(chǔ)課程，是計算機專業(yè)的一門核心的

關(guān)鍵性課程。本課程較系統(tǒng)地介紹了軟件設(shè)計中常用的數(shù)據(jù)結(jié)構(gòu)以及相應(yīng)的存儲結(jié)構(gòu)和實現(xiàn)

算法，介紹了常用的多種查找和排序技術(shù)，并做了性能分析和比較，內(nèi)容非常豐富。本課程

的學(xué)習(xí)將為后續(xù)課程的學(xué)習(xí)以及軟件設(shè)計水平的提高打下良好的基礎(chǔ).

由于以下原因，使得掌握這門課程具有較大的難度：

(1)內(nèi)容豐富，學(xué)習(xí)量大，給學(xué)習(xí)帶來困難；

(2)貫穿全書的動態(tài)鋌表存儲結(jié)構(gòu)和遞歸技術(shù)是學(xué)習(xí)中的重點也是難點；

(3)所用到的技術(shù)多，而在此之前的各門課程中所介紹的專業(yè)性知識又不多，因而加

大了學(xué)習(xí)難度；

(4)隱含在各部分的技術(shù)和方法豐富，也是學(xué)習(xí)的重點和難點。

根據(jù)《數(shù)據(jù)結(jié)構(gòu)課程》課程本身的技術(shù)特性，設(shè)置《數(shù)據(jù)結(jié)構(gòu)課程實驗》實踐環(huán)節(jié)十

分重要"通過實驗實踐內(nèi)容的訓(xùn)練，突出構(gòu)造性思維訓(xùn)練的特征，目的是提高學(xué)生組織數(shù)據(jù)

及編寫大型程序的能力。實驗學(xué)時為10。

結(jié)構(gòu)課程實驗》的目的和要求

不少學(xué)生在解答習(xí)題尤其是算法設(shè)計題時，覺得無從下手，做起來特別費勁。實驗中的

內(nèi)容和教科書的內(nèi)容是密切相關(guān)的，解決題目要求所需的各種技術(shù)大多可從教科書中找到，

只不過其出現(xiàn)的形式呈多樣化,因此需要仔細體會，在反復(fù)實踐的過程中才能掌握。

為了幫助學(xué)生更好地學(xué)習(xí)本課程，理解和掌握算法設(shè)計所需的技術(shù)，為整個專業(yè)學(xué)習(xí)打

好基礎(chǔ)，要求運用所學(xué)知識，上機解決一些典型問題，通過分析、設(shè)計、編碼、調(diào)試等各環(huán)

節(jié)的訓(xùn)練，使學(xué)生深刻理解、牢固掌握所用到的一些技術(shù)。數(shù)據(jù)結(jié)構(gòu)中稍微復(fù)雜一些的算法

設(shè)計中可能同時要用到多種技術(shù)和方法，如算法設(shè)計的構(gòu)思方法，動態(tài)鏈表，算法的編碼，

遞歸技術(shù)，與特定問題相關(guān)的技術(shù)等，要求重點掌握線性鏈表、二叉樹和樹、圖結(jié)構(gòu)、數(shù)組

結(jié)構(gòu)相關(guān)算法的設(shè)計。在掌握基本算法的亶出上，掌握分析、解決實際問題的能力。

三、《數(shù)據(jù)結(jié)構(gòu)課程實驗》內(nèi)容

課程實驗共10學(xué)時，要求完成以下五個題目：

實習(xí)一約瑟夫環(huán)問題(2學(xué)時)

用循環(huán)鏈表實現(xiàn)約瑟夫環(huán)問題,熟悉鏈表結(jié)構(gòu)的使用。

實習(xí)二，煌后問題(2學(xué)時)

在8x8的棋盤上放置彼此不受攻擊的8個皇后，熟悉遞歸與回溯程序設(shè)計方法。

實習(xí)三二叉樹基本操作(2學(xué)時)

創(chuàng)建、遍歷、顯示二叉樹，通過二叉樹的基本操作，掌握樹結(jié)構(gòu)的處理方法。

實習(xí)四哈夫曼編碼與譯碼

針對字符集A及其各字符的頻率值(可統(tǒng)計獲得)給出其中給字符哈夫曼編碼，并

針對一段文本（定義在A上）進行編碼和譯碼，實現(xiàn)一個哈夫曼編碼/譯碼系統(tǒng)。

實習(xí)五最小生成樹問題：2學(xué)時）

在n個城市之間建設(shè)網(wǎng)絡(luò)，只需保證連通即可，求最經(jīng)濟的架設(shè)方法。

四、《數(shù)據(jù)結(jié)構(gòu)課程實驗》考核方式

采用上機情況、程序質(zhì)量、實習(xí)報告相結(jié)合的形式，滿分力100分。

1.上機情況（30%）

包括出勤情況、調(diào)試表現(xiàn)、是否上網(wǎng)、玩游戲。

2.程序質(zhì)量（50%）

3.實習(xí)報告（20%）

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

實習(xí)一線性表

本次實習(xí)的主要目的在于熟悉線性表的基本運算在兩種存儲結(jié)構(gòu)上的實現(xiàn)，其中以熟悉

各種鏈表的操作為側(cè)重點。通過本次實習(xí)還可幫助讀者復(fù)習(xí)高級語言的使用方法。

1、城市鏈表

［問題描述］

將若干城市的信息，存入一個帶頭結(jié)點的單鏈表。結(jié)點中的城市信息包括：城市名，城

市的位置坐標。要求能夠利用城市名和位置坐標進行有關(guān)查找、插入、刪除、更新等操作。

［基本要求］

(1)給定一城市名，返回其位置坐標；

(2)給定一個位B坐標P和f距離D,返回所有與P的笈聘小于等于D的城市。

［測試數(shù)據(jù)］

由學(xué)生依據(jù)軟件工程的測試技術(shù)自己確定。注意測試邊界數(shù)據(jù)。

2、約瑟夫環(huán)

［問題描述］

約瑟夫(Joeph)問題的一種描述是:編號為12..小的n個人按II頁時針方向圍坐~溷，

每人持有一個密碼(正整數(shù))。一開始任選一個正整數(shù)作為報數(shù)上限值m,從第一個人開始

按順時針方向自1開始代蝴蹶，報到m時停出滕。報m的人出列，將他的密碼作為新的

m值，從他在順時針方向上的下一個人開始重新從1報數(shù)，如此下去，直至所有人全部出列

為止。試設(shè)計T程序求出出列順序。

［基本要求］

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

［測試數(shù)據(jù)］

m的媚為20；密碼：3,1,7,2,4,8,4(IB解蛤果防6,1,4,7,2,3,5)。

［實現(xiàn)提示］

程序運行后首先要求用戶指定初始報數(shù)上限值，然后讀取各人的密碼。設(shè)n&30。

［選作內(nèi)容］

向上述程序中添加在JII頁序結(jié)構(gòu)上實現(xiàn)的部分。

3、線性表的逆置

［問題描述］

分別以不同存儲結(jié)構(gòu)實現(xiàn)線性表的就地逆置。線性表的就地逆置就是在原表的存儲空間

內(nèi)將線性表(al,a2,a3,...,an)逆置為(an,an-1,,a2,al)e

［基本要求］

用順序存儲結(jié)構(gòu)實現(xiàn)線性表的就地逆置,并將結(jié)果輸出。

［測試數(shù)據(jù)］

由學(xué)生依據(jù)軟件工程的測試技術(shù)自己確定。注意測試邊界數(shù)據(jù)，如空表。

［實現(xiàn)提示］

設(shè)三個連續(xù)的指針，分別指向當前結(jié)點、當前結(jié)點的前趨、當前結(jié)點的后繼。

［選作內(nèi)容］

利用單鏈表作為存儲結(jié)構(gòu)。首先先建立線性表的帶頭結(jié)點的單鏈表表示形式，之后在不

借助輔助結(jié)點空間的情況下實現(xiàn)單鏈表的逆置，并將結(jié)果輸出。

4、長整數(shù)運算

［問題描述］

設(shè)計一個程序?qū)崿F(xiàn)兩個任意長的整數(shù)求和運算.

［基本要求］

利用雙項循環(huán)鏈表實現(xiàn)長整數(shù)的存儲，每個結(jié)點含一個整型變量。任何整型變量的范圍

是-(215-1)~(215-1)。輸入木嘮出形式：按中國對于長的表示習(xí)慣，每四位一組，

組間用逗號隔開。

［測試數(shù)據(jù)］

(1)0;0;應(yīng)輸出"0"。

H

(2)-2345,6789;-7654,3211;酶出-lz0000,0000".

(3)-9999,9999;1,0000,0000,0000;瞬出“9999,0000,0001"。

(4)1,0001,000;-1,0001,0001;應(yīng)輸出"0"。

(5)1,0001,0001;-1,0001,0000;心獺出T°

［實現(xiàn)提示］

(1)每個結(jié)點中可以存放的最大整數(shù)為215-1=32767,才能保證兩數(shù)相加不會溢出。

但若這樣存，即相當于按32768進制數(shù)存，在十進制數(shù)與32768進制數(shù)之間的轉(zhuǎn)換十分不方

便。故可以在每個結(jié)點中僅存十進制數(shù)的4位，即不超過9999的非負整數(shù)，整個鏈表視為

萬進制數(shù)。

(2)可以利用頭結(jié)點數(shù)據(jù)域的符號代?長髏的符號。用其絕對值表示元素結(jié)點數(shù)目。

相加過程中不要破壞兩個操作數(shù)鏈表。兩操作數(shù)的頭指針存于指針數(shù)組中是簡化程序結(jié)構(gòu)的

一種方法。不能給長整數(shù)位繳定上限。

［選作內(nèi)容］

修改上述程序，使它在整型量范圍是-(2n-l)~(2n-l)的計算機上都能有效地運行。

其中，n是由程序讀入的參量，輸入數(shù)據(jù)的分組方法可以另行規(guī)定。

實習(xí)二棧、隊列與遞歸算法設(shè)計

僅僅認識到榔口隊列是兩種特殊的線性表是遠遠不夠的，本次實習(xí)的目的在于使讀者深

入了解棧和隊列的特征，以便在實際問題背景下靈活運用它們：同時還將鞏固這兩種結(jié)構(gòu)的

構(gòu)造方法，接觸較復(fù)雜問題的遞歸算法設(shè)計。

1、數(shù)制轉(zhuǎn)換問題

［問題描述］

將十進制數(shù)N和其它d進制數(shù)的轉(zhuǎn)換是計算屐現(xiàn)計算的基本問題，其解決方案很多，

其中最簡單方;蝗于下列原理：即除d取余法。例如：(1348)10=(2504)8

NNdiv8Nmod8

13481684

168210

2125

202

從中我們可以看出，最先產(chǎn)生的余數(shù)4蹄換結(jié)果的最低位，這正好符合棧的特性即后

進先出的特性。所以可以用順序棧來模擬這個過程。

［基本要求］

對于鍵盤輸入的任意一個非負的十進制整數(shù)，打印輸出與其等值的八進制數(shù)。由于上述

的計算過程是從低位到高位順序產(chǎn)生的八進制數(shù)的各個數(shù)位，而打印愉出，一般來說應(yīng)從高

儂他位進行，恰好和計算過程相反。因此可以先將計算過程中得到的/也制數(shù)的各位進棧，

待相對應(yīng)的八進制數(shù)的各位均產(chǎn)生以后，再使其按順序出棧，并打印輸出。即得到了與輸入

的十進制數(shù)相對應(yīng)的/1進制數(shù)。

［測試數(shù)據(jù)］

由學(xué)生依據(jù)軟件工程的測試技術(shù)自己確定。注意測試邊界數(shù)據(jù)。

2、回文判斷

［問題描述］

試寫一個算法，判斷依次瀆入的一個以@為結(jié)束符的字母序列，是否為形如’序列1&

序夕」2'模式的字符序列。其中序列1和序歹U2中都不含字符,且序列2是序列1

的逆序列。例如，'a+b&b+a'是屬該模式的字符序列，而’1+3&3-r則不是。

［實現(xiàn)提示］

首先，序^1進棧,然后序1出棧并與序2匕戢。

［測試數(shù)據(jù)］

由學(xué)生依據(jù)軟件工程的測試技術(shù)自己確定。注意測試邊界數(shù)據(jù)，如序列1和序列2均為

空串。

3、商品貨架管理

［問題描述］

商品貨架可以看成一個棧，棧頂商品的生產(chǎn)日期最早，棧底商品的生產(chǎn)日期最近。上

貨時，需要倒貨架，以保證生產(chǎn)日期較近的商品在較下的位置。

［基本要求］

針對一種特定商品，實現(xiàn)上述管理過程。

［實現(xiàn)提示］

用棧模擬貨架和周轉(zhuǎn)空間。

［測試數(shù)據(jù)］

由學(xué)生依據(jù)軟件工程的測試技術(shù)自己確定。注意測試邊界數(shù)據(jù)，如空棧。

4、括號匹配的檢驗

［問題描述］

假設(shè)表達式中允許有兩種括號：圓括號和方括號，其嵌套的順序隨意，即（（）口）或

［（［］［］）］等為正確格式,［（］）或（（（］均為不正確的格式。檢驗括號是否匹配的方

法可用”期待的緊迫程度"這個概念來描述。例如：考慮下列的括號序：

［（［］［］）］

12345678

當計算機接受了第1個括號以后，他期待著與其匹配的第8個括號的出現(xiàn)，然而等來的

卻是第2個括號，此時第1個括號只能暫時靠邊，而迫切等待與第2個括號相匹配第

7個括號")"的出現(xiàn)，類似的，因只等來了第3個括號”「，此時，其期待的緊迫程度

較第2個括號更緊迫，則第2個括號只能靠邊，讓位于第3個括號，顯然第3個括號的期待

緊迫程度高于第2個括號，幣第2個括號的期待緊迫程度高于第1個括號;在接受了第4

個括號之后，第3個括號的期待得到了滿足，消解之后，第2個括號的期待匹酉蹴成了最急

迫的任務(wù)了.......依次類推?？梢娺@個處理過程正好和棧的特點相吻合。

［基本要求］

讀入圖括號和方括號的任意序,愉出"匹配"或"此串括號匹酉壞合法”.

［測試數(shù)據(jù)］

輸入(［］())，結(jié)果"匹配"

輸入［()］,結(jié)果"此串括號匹配不合法”

［實現(xiàn)提示］

設(shè)置一個棧，每讀入一個括號，若是左括號，則作為一個新的更急迫的期待壓入棧中；

若是右括號，并且與當前棧頂?shù)淖罄ㄌ栂嗥ヅ洌瑒t將當前棧頂?shù)淖罄ㄌ柾顺?，繼續(xù)讀下一個

括號，如果讀入的右括號與當前棧頂?shù)淖罄ㄌ柌黄ヅ?，則屬于不合法的情況。在初始和結(jié)束

時，棧應(yīng)該是空的。

［選作內(nèi)容］

考慮增加大括號的情況。

5、停車場管理

［問題描述］

設(shè)停車場內(nèi)只有一個可停放n輛汽車的狹長通道，且只有一個大門可供汽車進出。汽車

在停車場內(nèi)按車輛到達時間的先后順序，依次由北向南排列(大門在最南端，最先到達的第

T車停放在車場的最北端)，若車場內(nèi)已停滿n輛汽車，則后來的汽車只能在門外的便道

上等候，一旦有車開走，則排在便道上的第一輛車即可開入；當停車場內(nèi)某輛車要離開時，

在它之后開入的車輛必須先退出車場為它讓路，待該輛車開出大門外，其它車輛再按原次序

進入車場，每輛停放在車場的車在它離開停車場時必須按它停留的時間長短交納費用。試為

停車場編制按上述要求進行管理的模擬程序。

［測試數(shù)據(jù)］

也■■一

設(shè)n=2輸入319：('A',1,5),('A',2,10),('D',1,15),('A',3,

20),('A',4,25),('A',5,30),(U,2,35),(U,4,40),(E,0,

0).每一組輸入數(shù)據(jù)包括三人數(shù)據(jù)項：汽車"到達"或"離去"信息、汽車牌照號碼及到達

或離去的時刻，其中,'A'表示到達；’D'表示離去，'E'表示輸入結(jié)束。

［基本要求］

以棧模擬停車場，以隊列模擬車場外的便道，按照從終端讀入的輸入數(shù)據(jù)序列進行模擬

管理。每一組輸入數(shù)據(jù)包括三個數(shù)據(jù)項：汽車"到達"或"離去"信息、汽車牌照號碼及到

達或罔去的時刻，對每一組輸入數(shù)據(jù)進行操作后的輸出數(shù)據(jù)為：若是車輛到達，則輸出汽車

在停車場內(nèi)或便道上的停車位置；若是車離去；則輸出汽車在停車場內(nèi)停留的時間和應(yīng)交納

的費用(在便道上停留的時間不收費)。棧以順序結(jié)構(gòu)實現(xiàn)，隊列以鏈表實現(xiàn)。

［實現(xiàn)提示］

需另設(shè)一個棧，臨時停放為給要離去的汽車讓路而從停車場退出來的汽車，也用順序存

儲結(jié)構(gòu)實現(xiàn)。輸入數(shù)據(jù)按到達或離去的時刻有序。棧中每個元素表示一輛汽車，包含兩個數(shù)

據(jù)項：汽車的牌照號碼和進入停車場的時刻。

［選作內(nèi)容］

(1)兩個棧共享空間，思考應(yīng)開辟數(shù)組的空間是多少？

(2)汽車可有不同種類，則它們的占地面積不同，收費標準也不同，如1輛客轉(zhuǎn)口

1.5輛小;氣車的占地面積相同，1輛十輪卡車占地面積相當于3輛小;氣車的占地面積。

(3)汽車可以直接從便道上開走，此時SE在它前面的汽車要先開走讓路，然后再依次

排到隊尾。

(4)停放在便道上的汽車也收費，收費標準比停放在停車場的車低，請思考如何修改

結(jié)構(gòu)以滿足這種要求。

實習(xí)三串及其應(yīng)用

本次實習(xí)的目的是熟悉串類型的實現(xiàn)方法和文本模式匹配方法，熟悉一般文字處理軟件

的設(shè)計方法，較復(fù)雜問題的分解求精方法，在第二次實習(xí)的基礎(chǔ)上，進一步強化這樣一個觀

念：程序是數(shù)據(jù)結(jié)構(gòu)結(jié)合定義在其上的操作，此外還希望起到訓(xùn)練合作能力和熟悉文件操作

的目的。本次實習(xí)的難度較大。

1、文學(xué)研究助手

［問題描述］

義學(xué)研究人員需要統(tǒng)計某篇英義小說中某些形容詞的出現(xiàn)次數(shù)和位置。試寫一個實現(xiàn)這

一目標的文字統(tǒng)計系統(tǒng)，稱為"文學(xué)研究助手”。

［基本要求］

英文小說存于一個文本文件中。待統(tǒng)計的詞匯集合要一次輸入完畢，即統(tǒng)計工作必須在

程序的一次運行之后就全部完成。程序的輸出結(jié)果是每個詞的出現(xiàn)次數(shù)和出現(xiàn)位置所在行的

行號，格式自行設(shè)計。

［測試數(shù)據(jù)］

以你的源程序模擬英文小說，程序語言保留字集作為待統(tǒng)計的詞匯集。

［實現(xiàn)提示］

設(shè)小說中的詞匯一律不跨行。這樣，每讀入一行，就統(tǒng)計每個詞在這行中的出現(xiàn)次數(shù)。

出現(xiàn)位置所在行的行號可以用建表存儲。若某行中出現(xiàn)了不止一次，不必存多個相同的行號。

如果讀者希望達到選作部分(1)和(2)所提出的要求，見首先應(yīng)把KMP算法改寫成如

下的等價形式，再將它推廣到多個模式的情形。

［選作內(nèi)容］

(1)^1，羈TKMP算去。

(2)整個統(tǒng)計過程中只對小說文字掃描Tg以提高效率。

(3)假設(shè)小說中的每個單詞或者從行首開始，或者前置以一個空格符。利用單詞匹配

特點另寫T高效的統(tǒng)由辨，與KMP算法統(tǒng)由辨進行效率唾。

(4)推廣到更一般的模式集匹配問題，并設(shè)待查模式串可以跨行(提示：定義操作

getachar)

2、簡單行編輯程序

［問題描述］

文本編輯程序是利用計算機進行文字加工的基本軟件工具，實現(xiàn)對文本文件的插入、刪

除等修改操作。限制這些操作以行為單位進行的編輯程序稱為行編輯程序。

被編輯的文本文件可能很大，全部讀入編輯程序的數(shù)據(jù)空間(內(nèi)存)的做法既不經(jīng)濟，

也不總能實現(xiàn)。一種解決方法是逐段地編輯。件可時刻只把待編輯文件的一E殳放在內(nèi)存，稱

為活區(qū)。試按照這種方法實現(xiàn)一個簡單的行編輯程序。設(shè)文件每行不超過320個字符,很少

儂80秒。

［基本要求］

實現(xiàn)以下4條基本編輯命令:

(1)行插人讖：k行號＞＜回車＞＜文本＞＜回車,

將＜訃＞舌區(qū)犍〈彳污＞行加

(2)彳珊除。格式：d＜i^1＞［口＜彳療2＞］＜回車＞

刪除活區(qū)中第4行號1＞行(至懈＜行號2＞行)?兩種格式的例子是："diO/"和

Mdl0al4zH

(3)活區(qū)切換。格式:n＜回車＞

將活區(qū)寫入輸出文件，并從輸入文件中讀入下一段，作為新的活區(qū)。

(4)活區(qū)顯示。格式：p＜回車＞

逐頁地(每頁20行)顯示活區(qū)內(nèi)容，每顯示一頁之后請用戶決定是否繼續(xù)顯示以后各

頁(如果存在)。印出的每一行要前置以行號和一個空格符，行號固定占4位，增量為10

各條命令中的行號均須在活區(qū)中各行行號范圍之內(nèi)，只有插入命令的行號可以等于活區(qū)

第一行行號減1,表示插入當前屏幕中第一行之前，否則命令參數(shù)非法。

［測試數(shù)據(jù)］

由學(xué)生依據(jù)軟件工程的測試技術(shù)自己確定。注怠測試邊界數(shù)據(jù)，如首行、尾行。

［實現(xiàn)提示］

(1)設(shè)活區(qū)的大小用行數(shù)activemaxlen(可設(shè)為100)來描述?？紤]到文本文件行長

通常為正態(tài)分布，且峰值在60到70之間，用320xactivemaxlen大小的字符數(shù)組實現(xiàn)存儲

將造成大量浪費?？梢砸詷藴市袎K為單位為各行分配存儲，每個標準行塊含81個字符。這

些行塊可以組成一個數(shù)組，也可以利用動態(tài)鏈表連接起來。一行文字可能占多個行塊。行尾

可用來的ASCH字符(如(012)8)標識。此外，還應(yīng)記住活區(qū)起始行號。行插入將引

起隨后各行行號的順序下推。

(2)初始化過程包括：請用戶提供輸入文件名(空串表示磁人文件)和輸出文彳牛名，

兩者不能相同。然后盡可能多地從輸入文件中讀入各行，但不超過activemaxlenx的值

可以自定，例如20。

(3)在執(zhí)行行插入命令的過程中，每接收到一行時到要檢查活區(qū)大小是否已達

activemaxleno如果是,則為了在插入這一行之后仍保持活區(qū)大小不超過activemaxlen,

應(yīng)將插入點之前的活區(qū)部分中第一行輸出到輸出文件中；若插入點為第一行之前，則只得將

新插入的這一行輸出。

(4)若輸入文件尚未讀完，活區(qū)切換命令可將原活區(qū)中最后幾行留在活區(qū)頂部，以保

持閱讀連續(xù)性；否則，它意味著結(jié)束編輯或開始編輯另一個文件。

(5)可令前三條命令執(zhí)行后自動調(diào)用活區(qū)顯示。

［選作內(nèi)容］

(1)對于命令格式法等一切錯誤作嚴格檢查不睡當處理.

(2)加入更復(fù)雜的編豐■作，如對禽亍進行串替換；在活區(qū)內(nèi)進行模式匹配等，格式

可以為S＜行號＞@＜串1＞@＜串2＞＜叵嚀＞和m＜^＞＜回車

實習(xí)四樹、圖及其應(yīng)用

樹和圖是兩種應(yīng)用極為廣泛的數(shù)據(jù)結(jié)構(gòu)，也是這門課程的重點。它們的特點在于非線性。

廣義表本質(zhì)上是樹結(jié)構(gòu)；稀晞矩陣的十字鏈表存儲結(jié)構(gòu)也是圖的一種存儲結(jié)構(gòu)，故也把它們

歸在這次實習(xí)中。本章實習(xí)繼續(xù)突出了數(shù)據(jù)結(jié)構(gòu)加操作的程序設(shè)計觀點，但根據(jù)這兩種結(jié)構(gòu)

的非線性特點，將操作進一步集中在遍歷操作上，因為遍歷操作是其他眾多操作的基礎(chǔ)。遍

歷邏輯的（或符號形式的）結(jié)構(gòu)，訪問動作可是彳小可操作。本次實習(xí)還希望達到熟悉各種存

儲結(jié)構(gòu)的特征，以及如何應(yīng)用樹和圖結(jié)構(gòu)解決具體問題（即原理與應(yīng)用的結(jié)合）等目的。

1、二叉樹的建立與遍歷

［問題描述］

建立一棵二叉樹，并對其進行遍歷（先序、中序、后序），打印輸出遍歷結(jié)果。

［基本要求］

從鍵盤接受輸入（先序），以二叉鏈表作為存（髓構(gòu)，建立二叉樹（以先序來1立），并

采用遞歸算法對其進行遍歷（先序、中序、后序），將遍歷結(jié)果打印輸出。

［測試數(shù)據(jù)］

ABC0（|）DE（i）G4）（t）F（t）（t）4）（其中4）痂領(lǐng)砂）

貝瑜出結(jié)果為先序：ABCDEGF

.CBEGDFA

岳：CGBFDBA

［選作內(nèi)容］

采用非遞歸算法實現(xiàn)二叉樹遍歷。

2、打印樹結(jié)構(gòu)

［問題描述］

按凹入表形式打印樹形結(jié)構(gòu)。

例如：

E

A

D

B

［測試數(shù)據(jù)］

由學(xué)生依據(jù)軟件工程的測試技術(shù)自己確定。注意測試邊界數(shù)據(jù)，如空樹。

［實現(xiàn)提示］

(1)利用樹的先根遍歷方法；

(2)利用結(jié)點的深度控制橫向位置。

3、哈夫曼編碼/譯碼器

【問題描述】

設(shè)計一個利用哈夫曼算法的編碼和譯碼系統(tǒng)，重復(fù)地顯示并處理以下項目，直到選擇退出為

上

【基本要求】

Q)初始化：鍵盤輸入字符集大小n、n個字符和n個權(quán)值，建立哈夫曼樹;

(2)編碼:利用建好的哈夫屈樹生成哈夫?qū)ぞ幋a；

G)輸談碼；

(4)設(shè)字符集及頻度如下表：

^^fSABCDEFGHIJKLM

頻度1B66413223210321154757153220

射NOPQRSTUVWXYZ

頻度5763151485180238181161

【選做內(nèi)容】

⑴率就能；

⑵顯示哈夫曼樹；

(3)界面設(shè)計的優(yōu)化。

4、圖遍歷的演示

［問物S述］

很多涉及圖上操作的算法都是以圖的遍歷操作為基礎(chǔ)的。試寫一個程序，演示無向圖的

遍歷操作。

［基本要求］

以鄰接表為存儲結(jié)構(gòu)，實現(xiàn)連通無向圖的深度優(yōu)先^廣度優(yōu)先遍歷。以用戶指定的結(jié)點

為起點，分別輸出每種遍歷下的結(jié)點訪問序列和相應(yīng)生成樹的邊集。

［測Ji檄據(jù)］

由學(xué)生依據(jù)軟件工程的測試技術(shù)自己確定。注意測試邊界數(shù)據(jù)，如單個結(jié)點。

［實現(xiàn)提示］

設(shè)圖的結(jié)點不超過30個，每個結(jié)點用一個編號表示(如果一個圖有n個結(jié)點，則它們

的編號分別為L2，…,n)。通過輸入圖的全部邊輸入一個圖，每個邊為一個數(shù)對，可以對邊

的輸入111頁序作出某種限制。注意，生成樹的邊是有向邊，端點”頁序不能顛倒。

［選作內(nèi)容］

(1)借助于棧類型(自己定義和實現(xiàn))將深度優(yōu)先遍歷用非遞歸算法實現(xiàn)。

(2)以鄰接多重表為存儲結(jié)構(gòu)建立深度優(yōu)先生成樹和廣度優(yōu)先生成樹，再按凹入表或

樹形打印生成樹

(3)實現(xiàn)有向圖的遍歷操作.

實習(xí)五查找和排序

本次實習(xí)旨在集中對幾個專門的問題作較為深入的探討和理解，不強調(diào)對某些特定的編

程技術(shù)的訓(xùn)練。

1、二叉^序樹

［問題描述］

從鍵盤讀入一組蜂，建立二叉^序樹并對其進行查找、遍歷、格式化打印等有關(guān)操作。

［基本要求］

建立二叉排序樹并對其進行查找，包括成功和不成功兩種情況，并給出查找長度。

［測郵據(jù)］

由學(xué)生依據(jù)軟件工程的測試技術(shù)自己確定。注意測試邊界數(shù)據(jù)。

闔乍內(nèi)容］

實現(xiàn)二叉排序樹的插入、刪除操作.

2、哈希表設(shè)計

［問題描述］

針對某個集體中人名設(shè)計一個哈希表,使得平均查找長度不超過R,并完成相應(yīng)的建表

和查表程序。

［基本要求］

假設(shè)人名為中國人姓名的漢語拼音形式。待填入哈希表的人名共有30個，取平均查找

長度的上限為2。哈希函數(shù)用除留余數(shù)法構(gòu)造，用線性探測再散列法或鏈地址法處理沖突。

［測試數(shù)據(jù)］

取讀者周圍較熟悉的30個人名。

［選作內(nèi)容］

(1)從教科書上介紹的集中哈希函數(shù)構(gòu)造方法中選出適用者并設(shè)計幾個不同的哈希函

數(shù),I：破他們的地址J中突率(可以用更大的名字集合作實驗)O

(2)研究這30個人名的特點，努力找一個哈希函數(shù)，使得對于不同的拼音名一定不

發(fā)生地址沖突。

(3)在哈希函數(shù)確定的前提下嘗試各種不同處理中突的萬法，考察平均查找長度的變

化和造好的哈希表中關(guān)鍵字穗集性。

3、內(nèi)醐脖算法比較

［問題描述］

各種內(nèi)部排序算法的時間復(fù)雜度分析結(jié)果只給出了算法執(zhí)行時間的階，或大概執(zhí)行時

間。試通過隨機的數(shù)據(jù)比較各算法的關(guān)鍵字匕徽次數(shù)和關(guān)鍵字移動次數(shù)，以取得直觀感受。

［基本要求］

(1)對以下10種常用的內(nèi)部排序算法進行比較：直接插入排序；折半折入排序；二

路插入排序；希爾排序；起斷脖；快速排序；簡單選擇排序；堆排序；歸并排序；基數(shù)排

序。

(2)待排序表的表長不少于100;其中的數(shù)據(jù)要用偽隨機數(shù)產(chǎn)生程序產(chǎn)生；至少要用

5組不同的輸入數(shù)據(jù)作匕匕較；比較的指標為有關(guān)健字參加的比較次數(shù)和關(guān)鍵字移動次數(shù)(關(guān)

鍵字交換1十為3次移動).

［測赧據(jù)］

由隨機產(chǎn)生器決定。

［實現(xiàn)1示］

主要工作是設(shè)法在程序中適當?shù)牡胤讲迦胗嫈?shù)操作。程序還可以包括計算幾組數(shù)據(jù)得出

結(jié)果波動大小的解釋。注意分塊調(diào)試的方法。

［選作內(nèi)容］

對不同的輸入表長做試驗，觀察檢查兩個指標相關(guān)于表長的變化關(guān)系。還可以對穩(wěn)定性

做臉證。

3、統(tǒng)計成績

［問題描述］

給出n個學(xué)生的m門考試的成績表，每個學(xué)生的信息由學(xué)號、姓名以及各科成責組成。

對學(xué)生的考試成績進行有關(guān)統(tǒng)計，并打印統(tǒng)計表。

［基本要求］

(1)按總數(shù)高彳時欠序，打印出名次表，分數(shù)相同的為同一名次；

(2)按名次打印出每個學(xué)生的學(xué)號、姓名、總分以及各科成績。

［測郵據(jù)］

由學(xué)生依據(jù)軟件工程的測試技術(shù)自己確定。注意測試邊界數(shù)據(jù)。

［謝乍內(nèi)容］

對各科成績設(shè)置不同的權(quán)值。

附錄2

實驗報告示例

級班.年_______日

姓名_____學(xué)號__.電話_____

1.目

編制一個演示單鏈表插入、刪除、查找等操作的程序

2.需求分析

本演示程序用TC編寫，完成單鏈表的生成，任意位置的插入、刪除，以及確定某一元

素在單鏈表中的位置.

①輸入的形式^口輸入值的范圍：插入元素時需要輸入插入的位置和元素的值；刪除元

素時輸入刪除元素的位置；查找操作時需要輸入元素的值。在所有輸入中，元素的值都是整

數(shù)

②輸出的形式：在所有三種操作中都顯示操作是否正確以及操作后單鏈表的內(nèi)容。其

中刪除操作后顯示刪除的元素的值，查找操作后顯示要查找元素的位置。

③程序所能達到的功能：完成單鏈表的生成(通過插入操作)、插入、刪除、查找操作

④測郵據(jù)：

A.插入操作中依次輸入11,12,13,14,15,16,生成T單雌

B.查找操作中依次輸入12,15,22返回這3個元素在單鏈表中的位置

C.刪除操作中依次輸入2,5,刪除位于2和5的元素

設(shè)計

1)為了實現(xiàn)上述程序功能,需要定義單鏈表的抽象數(shù)據(jù)類型：

ADTLinkList{

:D={ai|aiGlntegerSet,i=0,1,2,,n,n>0}

:R={<ai,ai+l>|ai,ai+1eD)

基本操作：

InitLinkList(&L)

操作結(jié)果：構(gòu)造一個空的單鏈表L.

InsLinkList(&L,pos,e)

初始條!牛：單鏈表L已存在

操作結(jié)果：將元素e插入到單鏈表L的pos位置

DelLinkList(&L,pos,加)

初始條件：單鏈表L已存在

操作結(jié)果：將單鏈表L中pos位置的元素刪除，

元素值置入e中返回

LocLinkList(L,e)

初始條件：單鏈表L依存在

操作結(jié)果：單鏈表L中查找是否元素e,

若存在，返回元素在表中的位置;若不存在，返回T.

MenuQ

操作結(jié)果：在屏幕上顯示操作菜單

2)本程序包含7個函數(shù)：

①主函數(shù)main。

②初始化單鏈表函數(shù)［nitLinkList。

③顯示操作菜單的數(shù)menu。

④顯示單躁內(nèi)容函數(shù)dispLinkListO

⑤插入元素函數(shù)InsLinkListO

⑥刪除元素函數(shù)DelLinkListO

⑦好玩素函數(shù)LocLinkListO

各函數(shù)間關(guān)系如下：

InitLinkList

Menu

DispLinkList

InsLinkList

DelLinkList