上海交通大學電院資料結構大平台課程組
目錄1. 關於實習步驟的要求和建議
2. 上機實習
實習一線性結構
實習二樹和二叉樹
實習三查詢
實習四圖
實習五排序
3. 實習報告樣例
1． 關於實習步驟的要求和建議
從以往的教學事先實習的經驗來看，在初學階段執行嚴格的實習步驟規範（包括上機操作規範），機時利用率會大大提高，有助於養成良好的程式編制風格，培養嚴謹、科學、高效的工作方式。
在以往的教學實踐中，經常發現很多學生抱怨說，化了兩個小時才找出乙個錯誤，甚至一無所獲。他們不明白造成這種情況的原因，正是他們自己。有的學生不屑於按實習步驟規範去做，甚至對於實習步驟的要求和建議看都不看一遍，認為那是浪費時間，這是及其害的。
實習步驟規範不但可以培養科學化的工作作風，而且還能有效地避免錯誤。
具體的步驟機規範如下：
1． 問題分析與系統的結構設計：
充分地分析和理解問題本身，弄清要求作什麼，限制條件是什麼。按照以資料結構為中心的原則劃分模組，即定義資料結構及其在這些結構之上的操作，使得對資料結構的訪問通過這些操作加以實現。在這個過程中，要綜合考慮系統功能。
要考慮系統結構清晰、合理、簡單並且易於除錯。最後寫出每個子程式（過程或函式）的規格說明，列出它們之間的呼叫關係，可以使用呼叫關係圖表示則更加清晰，這樣便完成了系統結構設計。
2． 詳細設計和編碼
詳細設計的目的是對子程式（過程或函式）的進一步求精。用 if 、while和賦值語句等，以及自然語言寫出演算法的框架。利用自然語言的目的是避免陷入細節。
在編碼時，可以對詳細設計的結果進一步求精，用高階語言表示出來。
程式的每一行最好不超過 60 個字元。每個子程式（或過程、函式）通常不要太長，以 40 行為宜。子程式（或過程、函式）包含的程式行數太多，易於造成理解的困難。
控制 if 、while 等語句的連續巢狀的深度應加以控制。程式的目的性必須明確。對每一段程式完成的作用，除非常明顯的除外（如：
x = x + 1; 注釋為 x 加 1，沒有什麼意義），都應加以注釋。這會對程式的除錯提供很多方便。另外，根據情況可以設立若干調試點，即輸出若干資訊，用於驗證和你的設想是否一致。
另外，對於輸入輸出語句，必須對它們的作用加以說明。否則，在除錯程式時，無法了解系統需要輸入什麼，系統輸出的又是什麼。程式的書寫，必須按照一定的規範，如保留字小寫時塗黑等等。
3． 上機準備和靜態檢查
上機準備：
● 高階語言文字
● 熟悉機器的使用者手冊，熟悉常用的命令。
● 準備除錯的工具，考慮除錯方案。如果機器上沒有現成的除錯工具可供利用，可以自己先設計一些以供使用。
● 靜態檢查
自己用一組資料手動執行程式；或同同學一起閱讀自己的程式，以全面地了解該程式的邏輯。
4． 上機除錯程式
自底向上，先除錯底層模組，再除錯上層模組。最後，整個程式進行聯調。除錯正確後將源程式和執行結果加以列印輸出。
5． 實習報告的整理
● 需求及規格說明
問題描述，求解的問題是什麼。
● 設計：
設計思想：儲存結構、主要的演算法思想。
設計表示：子程式（過程或函式）的規格說明，通過呼叫關係圖表示它們之間的呼叫關係。
實現注釋：
詳細設計表示：主要演算法的框架。
● 使用者手冊：使用說明。
● 除錯報告：問題是如何解決的，討論與分析、改進設想、經驗與體會、時空複雜度等。
● 附錄
源程式清單和結果：源程式必須有注釋，以及必要的測試資料和執行結果資料。提倡用英文描述。
● 實驗報告要求：
在程式開發過程中，逐步形成各種必要的文件及資料。可以寫在實驗報告紙上，或以電子文件的形式進行書寫。
2． 上機實習
● 以下的實習題目配合課程的進度，請同學們務必自己完成。為了鍛鍊自己的應用各種不同的資料結構的能力，盡可能的多作一些題目是非常必要的。在完成各種不同題目的過程中，對各種演算法的時、空複雜性的分析，將幫助您在更高的角度解決各種應用問題。
● 為了減輕同學的負擔，我們對同學的實習報告進行了精簡。本實習報告中的題目分以下幾種型別：
1、 實習題：必須按照實習報告的規範完成。每個實習的第一題都是實習題，必須編寫詳細的實習報告。實習報告的書寫方法，請參閱本指導書的第 3 部分：實習報告的樣例。
2、 作業題：同樣必須完成。只需交代清楚題目的解法，輔以求解程式和注釋，使得別人能夠看懂你的演算法和程式即可。不必象實習題那樣書寫完整的實習報告。
3、 選作題：鼓勵同學選作的題目，尤其是學有餘力的同學。
以下為各次實習作業：
實習一線性結構
1、（實習題） 請寫出計算兩個以單鏈結表表示的多項式相乘的程式。
2、（作業題） 已知兩個單鏈表 a 和 b 分別表示兩個集合，其元素遞增排列。請編寫程式求集合 a 和 b 的交集 c = ab，要求單鏈表c按其元素遞增排列，並利用原表（即表a和表b）的結點空間存放表c。
3、（作業題） 假設有二個棧共同使用一塊順序儲存的空間，為簡單起見可設為共同使用陣列 int a〔200〕。它們的棧底分別設在陣列的兩端，而棧頂指標在進行插入操作時，向中間方向移動。請給出進出棧的程式。
4、（選作題） 將具有頭結點的單鏈表的所有指標全部進行倒向。要求使用的額外空間只能為 o(1),時間代價只能為o(n)，其中 n 為結點個數。
注意：如下圖1所示的單鏈表，倒向之後將如圖2所示。
圖 1、倒向之前的單鏈表
圖 2、倒向之後的單鏈表
實習二樹和二叉樹
1、（實習題） 請編寫乙個程式，確定二叉樹的特徵。如：每個節點的層次，從根到該節點的枝長（路徑長度），子孫的個數及祖先的個數。每個節點在前序、中序、後序中的訪問的序號。
2、（作業題） 設二叉樹的結點的資料場之值僅為一大寫英文本母。其前序和中序的遍歷結果（列印結點的資料場之值）分別儲存在字串陣列 preorder[n] 及 inorder[n]之中，其中 n 未常數。請設計程式以標準形式形式儲存儲存該二叉樹。
3、（作業題） 設樹的根結點的層號為1，而其他各層上的結點的層號比其父結點的層號大 1。另外設該樹中的結點的資料場之值為正整數。這樣數對( ik，wk)就表示了該樹中的結點的層號和其資料場之值。
從鍵盤上依次輸入 m 個數對，如：( i1，w1)，( i2，w2)，……，( im，wm)；這些數對是按照結點的前序序列給出的。注意這是用層號 ＋ 前序表示一棵樹的方法。
如：（1，a）, （2，b）, （2，c）, （3，e）, （4，g）, （3，f）, （2，d）, （3，x）, （3，y）, （3，z）；它所表示的樹如圖 3 所示。請編寫程式，以標準形式儲存這棵樹。
為了簡單起見，可設這棵樹上的結點的度數最大為 3，結點的儲存形式為：
data parent son1 son2 son3
其中：data 域為結點的資料場，parent 域為結點的父親結點的位址，son1，son2，son3分別給出結點的三個兒子的位址。
圖 3 、 一課三次樹
4、（選作題） 用標準形式給出了一棵度為三的樹（每個結點包含資料場、指向兒子節點的指標場，可參閱上題 ）。設該三次樹的資料場的值為乙個字元，請編寫乙個程式，以樹的兩維形式表示列印節點的值。 注意：
圖 3 即為樹的二維表示形式。在實現時，為了方便可用打點的方法代替直線。
實習三查詢
1、（實習題） 從鍵盤上輸入一串正整數， 最後輸入－1作為輸入結束的標誌。如輸入的序列為：2，5，7，23，48，96，……，-1。
請以這些正整數的值作為二叉排序樹中的結點的資料場之值，建立一棵二叉排序樹。注意：請採用動態儲存方法儲存這棵二叉排序樹，事先並未知道該二叉排序樹中的結點的個數。
2、 （作業題） 已知一棵排序二叉樹，樹中結點的形式為：
datainfoleftright
其中，data 給出結點的資料場，info 給出本結點的左子樹中的結點總數，left和 right 分別給出本結點的左兒子和右兒子的位址。資料場data 和info的型別皆為 int。又已知該二叉排序樹的根結點的位址為 root。
請設計二個函式，分別實現下述功能：
1． 按遞增序找出該二叉排序樹中的第 i 個小的結點。
2． 插入資料場之值為 x 的結點，並仍應保持該二叉排序樹的性質不
變。3、 （作業題） 已知一棵二叉排序樹，其根結點的位址為 root。請編寫乙個程式，構造出一棵具有相同結點的完全二叉樹，且它同樣是二叉排序樹。
4、（選作題）在平衡的排序二叉樹的中，試編寫刪除具有給定關鍵字的結點的函式。
實習四圖
1、（實習題） 以數偶的形式依次從鍵盤上輸入一串資料。如：(a，b)為從起始結點（其資料場之值為一大寫的英文本母 a ），到終止結點（其資料場之值為一大寫的英文本母 b）的無向邊。
最後輸入（z，z）表示輸入結束。請用無向圖的鄰接多重表儲存該無向圖，並注意一定要使用動態儲存結構。
2、（作業題） 已知一以動態儲存結構形式儲存的，以鄰接多重表表示的無向圖。請用kruskal演算法求出它的最小代價生成樹。
3、（作業題） 已知一以鄰接矩陣形式儲存的 aov 圖。請求出它的所有的合理的拓撲排序的序列。
4 、（選作題） 已知一以動態儲存結構形式儲存的， 以鄰接表表示的有向圖。 請求出它的強連通分量。
實習五排序
1、（實習題）編寫乙個程式，查詢未排序序列中第k個最小的元素，要求使用類似快速排序的演算法。並簡單討論一下在最壞情況下，所耗費的時間。
2、（作業題）奇偶排序。將被排序的序列進行如下操作。反覆進行直至不再進行交換為止。
第一遍：比較x[i]同x[i+1](對所有奇數i);第二遍：比較x[i]同x[i+1](對所有偶數i);每次比較，如果x[i]>x[i+1]則交換之，繼續這樣做，直至不交換為止。
該方法的結束條件如何?寫乙個c++程式加以實現。
3、（作業題）已知整數陣列 int a[n]。其中：a[1]，a[2]， ……a[n-2]，a[n-1] 已經被整理成為最小化堆，注意此處未使用a[ 0 ]。
請設計乙個函式加以完成，並且程式的時間複雜性必須為o(log2n)。
4 、（選作題）已知整數陣列 int a[n]。其中，a[1]，a[2]， ……，a[n－1] 已被整理成最小化堆。在將a[1]，a[2]， ……，a[n-1]，a[n] 整理成最小堆時，可分兩步進行：
1、先找出a[n]之值的插入位置； 2、再進行適當的資料移動即可。現僅僅考慮第一步，找出a[n]之值的插入位置。請設計乙個程式加以完成。
注意該程式的時間複雜性必須為o(log2log2n)，並加以證明。
《資料結構與演算法》實驗指導書
鬱松軟體學院 資料結構 是計算機 資訊管理和電子商務專業一門重要的專業技術基礎課程，是計算機 資訊管理和電子商務專業的一門關鍵性課程。本課程較系統地介紹了軟體設計中常用的資料結構以及相應的儲存結構和實現演算法，介紹了常用的多種查詢和排序技術，並做了一些效能分析和比較，內容非常豐富。本課程的學習將為後...
《資料結構 演算法與應用》實驗指導書
山東大學軟體學院 一 實驗要求 1 採用良好的程式設計風格 關鍵操作要有注釋。2 程式能夠執行，顯示執行結果。二 開發工具 microsoft visual c eclipse ide for c 三 實驗時間 地點 一 實驗目的 1 熟悉開發工具的使用。2 掌握遞迴的實現思想。二 實驗內容 1 輸...
《資料結構與演算法》實驗指導書2019版
大連民族學院 資訊與通訊工程學院 2013 年10 月10 日 基本要求 1.學生必須按時到實驗室做實驗，不得遲到早退，未經老師批准不得中途離開。凡遲到者，應給予批評並作適當扣分。實驗課遲到20分鐘以上及無故缺席者視為曠課，曠課者不予補做實驗，本次實驗以零分計。學生因病或特殊情況不能按時到實驗室做實...