數(shù)據(jù)結構與算法實習指導書

1、數(shù)據(jù)結構與算法實習指導書上海交通大學電院數(shù)據(jù)結構大平臺課程組目錄1. 關于實習步驟的要求和建議2. 上機實習實習一 線性結構實習二 樹和二叉樹實習三 查找實習四 圖3. 實習報告樣例1 關于實習步驟的要求和建議從以往的教學事先實習的經(jīng)驗來看，在初學階段執(zhí)行嚴格的實習步驟規(guī)范（包括上機操作規(guī)范），機時利用率會大大提高，有助于養(yǎng)成良好的程序編制風格，培養(yǎng)嚴謹、科學、高效的工作方式。在以往的教學實踐中，經(jīng)常發(fā)現(xiàn)很多學生抱怨說，化了兩個小時才找出一個錯誤，甚至一無所獲。他們不明白造成這種情況的原因，正是他們自己。有的學生不屑于按實習步驟規(guī)范去做，甚至對于實習步驟的要求和建議看都不看一遍，認為那是浪費時

2、間，這是及其害的。實習步驟規(guī)范不但可以培養(yǎng)科學化的工作作風，而且還能有效地避免錯誤。具體的步驟機規(guī)范如下：1 問題分析與系統(tǒng)的結構設計： 充分地分析和理解問題本身，弄清要求作什么，限制條件是什么。按照以數(shù)據(jù)結構為中心的原則劃分模塊，即定義數(shù)據(jù)結構及其在這些結構之上的操作，使得對數(shù)據(jù)結構的存取通過這些操作加以實現(xiàn)。在這個過程中，要綜合考慮系統(tǒng)功能。要考慮系統(tǒng)結構清晰、合理、簡單并且易于調試。最后寫出每個子程序（過程或函數(shù)）的規(guī)格說明，列出它們之間的調用關系，可以使用調用關系圖表示則更加清晰，這樣便完成了系統(tǒng)結構設計。2 詳細設計和編碼詳細設計的目的是對子程序（過程或函數(shù)）的進一步求精。用 IF

3、、WHILE和賦值語句等，以及自然語言寫出算法的框架。利用自然語言的目的是避免陷入細節(jié)。在編碼時，可以對詳細設計的結果進一步求精，用高級語言表示出來。程序的每一行最好不超過 60 個字符。每個子程序（或過程、函數(shù)）通常不要太長，以 40 行為宜。子程序（或過程、函數(shù)）包含的程序行數(shù)太多，易于造成理解的困難。控制 IF 、WHILE 等語句的連續(xù)嵌套的深度應加以控制。程序的目的性必須明確。對每一段程序完成的作用，除非常明顯的除外（如：x = x + 1; 注釋為 x 加 1，沒有什么意義），都應加以注釋。這會對程序的調試提供很多方便。另外，根據(jù)情況可以設立若干調試點，即輸出若干信息，用于驗證和你

4、的設想是否一致。另外，對于輸入輸出語句，必須對它們的作用加以說明。否則，在調試程序時，無法了解系統(tǒng)需要輸入什么，系統(tǒng)輸出的又是什么。程序的書寫，必須按照一定的規(guī)范，如保留字小寫時涂黑等等。3 上機準備和靜態(tài)檢查上機準備：l 高級語言文本l 熟悉機器的用戶手冊，熟悉常用的命令。l 準備調試的工具，考慮調試方案。如果機器上沒有現(xiàn)成的調試工具可供利用，可以自己先設計一些以供使用。l 靜態(tài)檢查自己用一組數(shù)據(jù)手動執(zhí)行程序；或同同學一起閱讀自己的程序，以全面地了解該程序的邏輯。4 上機調試程序自底向上，先調試底層模塊，再調試上層模塊。最后，整個程序進行聯(lián)調。調試正確后將源程序和運行結果加以列印輸出。5 實

5、習報告的整理l 需求及規(guī)格說明問題描述，求解的問題是什么。l 設計：設計思想：存儲結構、主要的算法思想。設計表示：子程序（過程或函數(shù)）的規(guī)格說明，通過調用關系圖表 示它們之間的調用關系。實現(xiàn)注釋：詳細設計表示：主要算法的框架。l 用戶手冊：使用說明。l 調試報告：問題是如何解決的，討論與分析、改進設想、經(jīng)驗與體會、時空復雜度等。l 附錄源程序清單和結果：源程序必須有注釋，以及必要的測試數(shù)據(jù)和運行結果數(shù)據(jù)。提倡用英文描述。l 實驗報告要求：在程序開發(fā)過程中，逐步形成各種必要的文檔及資料?？梢詫懺趯嶒瀳蟾婕埳?，或以電子文檔的形式進行書寫。2 上機實習 l 以下的實習題目配合課程的進度，請同學們務必

6、自己完成。為了鍛煉自己的應用各種不同的數(shù)據(jù)結構的能力，盡可能的多作一些題目是非常必要的。在完成各種不同題目的過程中，對各種算法的時、空復雜性的分析，將幫助您在更高的角度解決各種應用問題。l 為了減輕同學的負擔，我們對同學的實習報告進行了精簡。本實習報告中的題目分以下幾種類型：1、 實習題：必須按照實習報告的規(guī)范完成。每個實習的第一題都是實習題，必須編寫詳細的實習報告。實習報告的書寫方法，請參閱本指導書的第 3 部分：實習報告的樣例。2、 作業(yè)題：同樣必須完成。只需交代清楚題目的解法，輔以求解程序和注釋，使得別人能夠看懂你的算法和程序即可。不必象實習題那樣書寫完整的實習報告。3、 選作題：鼓勵同

7、學選作的題目，尤其是學有余力的同學。以下為各次實習作業(yè)：實習一 線性結構1、（實習題） 請寫出計算兩個以 單鏈接表表示的多項式相乘的程序。 2、（作業(yè)題） 已知兩個單鏈表 A 和 B 分別表示兩個集合，其元素遞增排列。請編寫程序求集合 A 和 B 的交集 C = AÇB，要求單鏈表C按其元素遞增排列，并利用原表（即表A和表B）的結點空間存放表C。3、（作業(yè)題） 假設有 二 個棧共同使用一塊順序存儲的空間，為簡單起見可設為共同使用數(shù)組 int a200。它們的棧底分別設在數(shù)組的兩端，而棧頂指針在進行插 入操作時，向中間方向移動。請給出進出棧的程序。4、（選作題） 將具有頭結點的單鏈表的

8、所有指針全部進行倒向。要求使用的額外空間只能為 O(1),時間代價只能為O(n)，其中 n 為結點個數(shù)。 注意：如下圖1所示的單鏈表，倒向之后將如圖2所示。head ABCDhead ABCD圖 1、倒向之前的單鏈表 圖 2、倒向之后的單鏈表實習二 樹和二叉樹1、（實習題） 請編寫一個程序，確定二叉樹的特征。如：每個節(jié)點的層次，從根到該節(jié)點的枝長（路徑長度），子孫的個數(shù)及祖先的個數(shù)。每個節(jié)點在前序、中序、后序中的訪問的序號。2、（作業(yè)題） 設二叉樹的結點的數(shù)據(jù)場之值僅為一大寫英文字母。其前序和中序的遍歷結果（打印結點的數(shù)據(jù)場之值）分別保存在字符串數(shù)組 preorderN 及 inorderN之

9、中，其中 N 未常數(shù)。請設計程序以標準形式形式存儲保存該二叉樹。3、（作業(yè)題） 設樹的根結點的層號為1，而其他各層上的結點的層號比其父結點的層號大 1。另外設該樹中的結點的數(shù)據(jù)場之值為正整數(shù)。這樣數(shù)對( Ik，Wk)就表示了該樹中的結點的層號和其數(shù)據(jù)場之值。從鍵盤上依次輸入 m 個數(shù)對，如：( I1，W1)，( I2，W2)，( Im，Wm)；這些數(shù)對是按照結點的前序序列給出的。注意這是用 層號 前序 表示一棵樹的方法。如：（1，A）, （2，B）, （2，C）, （3，E）, （4，G）, （3，F(xiàn)）, （2，D）, （3，X）, （3，Y）, （3，Z）；它所表示的樹如圖 3 所示。請編寫

10、程序，以標準形式存儲這棵樹。為了簡單起見，可設這棵樹上的結點的度數(shù)最大為 3，結點的存儲形式為：dataparentson1 son2 son3其中：data 域為結點的數(shù)據(jù)場，parent 域為結點的父親結點的地址，son1，son2，son3分別給出結點的三個兒子的地址。ACDBZYXFEG 圖 3 、 一課三次樹4、（選作題） 用標準形式給出了一棵度為三的樹（每個結點包含數(shù)據(jù)場、指向兒子節(jié)點的指針場，可參閱上題 ）。設該三次樹的數(shù)據(jù)場的值為一個字符，請編寫一個程序，以樹的兩維形式表示打印節(jié)點的值。 注意：圖 3 即為樹的二維表示形式。在實現(xiàn)時，為了方便可用打點的方法代替直線。實習三 查找

11、1、（實習題） 從鍵盤上輸 入一串正整數(shù)， 最后輸入1作為輸入結束的標志。如輸入的序列為：2，5，7，23，48，96，-1。請以這些正整數(shù)的值作為二叉排序樹中的結點的數(shù)據(jù)場之值，建立一棵二叉排序樹。注意：請采用動態(tài)存儲方法保存這棵二叉排序樹，事先并未知道該二叉排序樹中的結點的個數(shù)。2、 （作業(yè)題） 已知一棵排序二叉樹，樹中結點的形式為：data info left right其中，data 給出結點的數(shù)據(jù)場，info 給出本結點的左子樹中的結點總數(shù)，left和 right 分別給出本結點的左兒子和右兒子的地址。數(shù)據(jù)場data 和info的類型皆為 int。又已知該二叉排序樹的根結點的地址為

12、root。請設計二個函數(shù)，分別實現(xiàn)下述功能：1 按遞增序找出該二叉排序樹中的第 i 個小的結點。2 插入數(shù)據(jù)場之值為 x 的結點，并仍應保持該二叉排序樹的性質不 變。3、 （作業(yè)題） 已知一棵二叉排序樹，其根結點的地址為 root。請編寫一個程序，構造出一棵具有相同結點的完全二叉樹，且它同樣是二叉排序樹。4、（選作題）在平衡的排序二叉樹的中，試編寫刪除具有給定關鍵字的結點的函數(shù)。 實習四 圖1、（實習題） 以數(shù)偶的形式依次從鍵盤上輸入一串數(shù)據(jù)。如：(A，B)為從起始結點（其數(shù)據(jù)場之值為一大寫的英文字母 A ），到終止結點（其數(shù)據(jù)場之值為一大寫的英文字母 B）的無向邊。最后輸入（Z，Z）表示輸入

13、結束。請用無向圖的鄰接多重表存儲該無向圖，并注意一定要使用動態(tài)存儲結構。2、（作業(yè)題） 已知一以動態(tài)存儲結構形式存儲的，以鄰接多重表表示的無向圖。請用KRUSKAL算法求出它的最小代價生成樹。3、（作業(yè)題） 已知一以鄰接矩陣形式存儲的 AOV 圖。請求出它的所有的合理的拓撲排序的序列。4 、（選作題） 已 知 一 以 動 態(tài) 存 儲 結 構 形 式 存 儲 的， 以 鄰 接 表 表 示 的 有 向 圖。 請 求 出 它 的 強 連 通 分 量。3、實習報告樣例一、實習題：約瑟夫(Josephus)問題：設有n 個人圍成一個圓圈，任意給定一個正整數(shù)m，從第一個人開始順時針計數(shù)，計到第m個人，將其

14、從圓圈中除去。然后再從下一個人開始，周而復始，直到圓圈中只剩一個人為止，那么剩下的那個人就是贏家。1需求分析和說明分析約瑟夫問題：n個人圍成圈，從第一個人開始，數(shù)到第m個人，刪除并以下一個人開始進行第二輪操作，直到最后一個人作為優(yōu)勝者。例如n=6, m=3, 處理過程下圖。2設計n個人圍圈，形成線性關系；處理為逐個刪除，故用鏈式結構合適；又人員圍成圓圈，所以此鏈式結構采用循環(huán)方式較好；排號按照一個方向進行，故數(shù)據(jù)結構采用帶頭結點的單向循環(huán)鏈表。假設人員以首次的編號命名，對每個人員采用編號和姓名加以描述。存儲結構：struct person /定義人員信息，包括序號和姓名intno;char n

15、ame10;/circlinklist.h單向循環(huán)鏈表類template <class ElemType> class CircLinkList CircLinkListNode<ElemType> *head, *tail;/指向表頭結頭和尾結點CircLinkListNode<ElemType> *currPtr; /指向當前工作結點CircLinkListNode<ElemType> *prevPtr； /指向當前工作結點的前一結點int size;/表中元素的個數(shù)int position;/表中當前元素所在的元素序號（位置）public:

16、 CircLinkList ( )；/構造函數(shù) CircLinkList ( )； /析構函數(shù)void Clear ( )； /鏈表置空int Length ( ) constreturn size;； /求鏈表長度bool IsEmpty ( ) constreturn (size=0);；/判斷鏈表是否空bool IsEnd ( ) constreturn (currPtr=tail);；/當前結點是否是尾結點int CurrentPosition() constreturn position; /返回當前結點的序號ElemType Data ( ) const; /返回當前指針所指的結點

17、中的元素值void GoNext ( );/將當前指針指向當前結點后面的一個結點void Reset(int pos)；/將當前指針指向序號為pos的結點CircLinkListNode<ElemType> *Find ( ElemType e ); /查找從當前結點起第一個元素值為e的結點/各種位置上的插入操作void InsertFront (const ElemType e )；/在首結點位置上插入元素值為e的新結點void InsertTail (const ElemType e )；/在尾結點之后插入元素值為e的新結點，使其成為新的尾結點void InsertAt (co

18、nst ElemType e )；/在當前結點位置上插入元素值為e的新結點， /原來的當前結點成為其后一個結點void InsertAfter (const ElemType e )；/在當前結點之后插入元素值為e的新結點 ElemType RemoveFront( );/刪除首結點，并返回其元素值ElemType RemoveAt( );/刪除當前結點，并返回其元素值;算法思想：聲明一個person類型的單向循環(huán)鏈表。從鍵盤順序輸入n個人的姓名, 建立約瑟夫環(huán)。計數(shù)并逐個讀取并刪除第m個人，直到鏈表為空，其中最后一個被讀出的即優(yōu)勝者。調用關系：程序任務簡單，故設計在一個main()函數(shù)內，只

19、設計類成員函數(shù)的調用，無另外的子程序或函數(shù)。算法實現(xiàn)框架：3用戶手冊：運行程序，按照屏幕提示分別輸入圈內人數(shù)n，正整數(shù)m和n個人的姓名，之后屏幕將顯示按照輸入次序排好的人員被逐個刪除的次序，最后顯示最后的出優(yōu)勝者。4調試報告：時間復雜度分析：該算法在建立時的時間復雜度為O(n), 刪除時時間耗費在逐個數(shù)元素上，按照第m個刪除的原則，不妨將n個元素分成若干組，每組m個人，n個人最多分n/m+1組。擴展最后一組，使其也是m個人，對組內元素從1到m排號，每組排號為m的只數(shù)到一次便被刪除；第二圈數(shù)每組排號為1的被刪除，每個元素數(shù)過2次；第三圈數(shù)每組排號為2的被刪除，每個元素數(shù)過3次；最后，第m圈, 每

20、組排號為m-1的被刪除，每個元素數(shù)過m次；故總刪除總的時間為：(n/m+1)(1+2+3+m)=m(m+1)(n/m+1)/2，時間復雜度為：O（n*m）；縮小最后一組，使其是0個人，同上可得刪除總的時間為：(n/m)(1+2+3+m)=m(m+1)(n/m)/2，時間復雜度也為：O（n*m）；綜合建立和刪除，算法時間復雜度為：O（n*m）算法改進思路：在對元素數(shù)數(shù)刪除過程中，總是要去判斷是否是頭結點并繞過它，可以改進一下，去掉頭結點，由此看來，并非鏈式結構帶有頭結點都有益處。改進后性能可以提高，但時間復雜度依然為：O（n*m）5附錄源程序清單/josephusRing.cpp#include

21、 <iostream.h>#include "circlinklist.h"struct person /定義人員信息，包括序號和姓名intno;char name10;void main() CircLinkList<person> josephusRing;/聲稱一個單向循環(huán)鏈表類對象person temp;int i;int n, m;/共有n個人，計數(shù)到 m 刪除/從鍵盤輸入總人數(shù)ncout<<"Input the number of people:"cin>>n;cout<<endl;

22、/從鍵盤輸入計數(shù)標準mcout<<"Input count number:"cin>>m;cout<<endl;/順序輸入n個人的姓名, 建立約瑟夫環(huán)cout<<"Input every person's name:"<<endl;for (i=1; i<=n; i+) cin>>;/輸入姓名temp.no=i;/將輸入次序作為人員編號josephusRing.InsertTail(temp);/將新來人員信息加入到鏈表尾部/計數(shù)并逐個刪除第m個人，直到鏈表為空josephusRing.Reset(1); /當前結點設置為首結點i=0;cout<<"Deleted order: "<<endl;while (!josephusRing.IsEmpty() /以鏈表為空作為結束條件josephusRing.GoNext();/將當前結點設置為當前結