1、數據結構課程實驗大綱 實 驗 學 時： 12 課程總學時：64 適 用 專 業：計算機科學與技術（考試） 實驗項目數：6 軟件工程（考試） 教育技術學（考試） 網絡工程（考試） 通信工程（考試） 開課教研室(系)： 計算機工程 大綱執筆人： 一、 本實驗課的基本理論和目的數據結構是計算機學科的核心專業基礎課程，是計算機程序設計的重要理論和實踐基礎。本課程討論了軟件設計中經常遇到的線性表、堆棧、隊列、串、數組、二叉樹、圖等典型數據結構的設計方法以及各種典型排序和查找算法的性能和設計方法，并介紹了各種典型數據結構的應用。數據結構課程是一門理論和實踐相結合的課程。 上機實驗是為訓練學生的實際程序設計

2、能力安排的、包含在教學課時內的教學內容。實驗目的是： （1）進一步深入理解相關部分的基本概念和授課內容。 （2）進一步提高實際動手進行程序設計的能力。二、 本實驗課的基本要求 （1）認真閱讀掌握和實驗相關的教材內容。 （2）自己編程，可以參考別人的程序設計方法，但不得抄襲別人的程序。 （3）程序有錯誤時，盡量先自己調試，在自己能力達不到時，可請教同學或詢問老師。 （4）及時完成實驗報告。三、設置的實驗項目、實驗內容和學時分配 實驗一 線性表的基本操作和簡單程序（2學時） 實驗內容如下： （1）熟悉Visual C+ 6.0實驗環境。 （2）閱讀教材上順序堆棧和鏈式堆棧的程序，并自己鍵入這些程序

3、。 （3）設計一個使用堆棧的應用程序。 （4）分析應用程序的運行情況。 實驗二 順序棧的實現（2學時）實驗內容如下： （1）定義棧的順序存取結構。 （2）分別定義順序棧的基本操作（初始化棧、判棧空否、入棧、出棧等）。 （3）定義一個函數用來判斷算術表達式中包含圓括號、方括號是否正確配對。其中，括號配對共有四種情況：左右括號配對次序不正確；右括號多于左括號；左括號多于右括號；左右括號匹配正確。（4）設計一個測試主函數進行測試。 （5）對程序的運行結果進行分析。實驗三 折半查找算法設計（2學時）實驗內容如下： （1）分析掌握折半查找算法思想，在此基礎上，設計出遞歸算法和循環結構兩種實現方法的折半查

4、找函數。 （2）編寫程序實現：在保存于數組的1000個有序數據元素中查找數據元素x是否存在。數據元素x要包含兩種情況：一種是數據元素x包含在數組中；另一種是數據元素x不包含在數組中 （3）數組中數據元素的有序化既可以初始賦值時實現，也可以設計一個排序函數實現。 （4）根據兩種方法的實際運行時間，進行兩種方法時間效率的分析對比。實驗四 二叉樹設計（2學時）實驗內容如下：（1）定義二叉鏈存儲結構。 （2）設計二叉樹的基本操作（初始化一棵帶頭結點的二叉樹、左結點插入、右結點插入、中序遍歷二叉樹等）。 （3）按照建立一棵實際二叉樹的操作需要，編寫建立二叉樹、遍歷二叉樹的函數。 （4）編寫測試主函數并上

5、機運行。打印出運行結果，并結合程序運行結果進行分析。實驗五 圖的設計（2學時）實驗內容如下： （1）定義鄰接矩陣存儲結構或鄰接表存儲結構。 （2）按照建立一個帶權有向圖的操作需要，編寫在鄰接矩陣或鄰接表存儲結構下，帶權有向圖基本操作的實現函數（如初始化圖、在圖中插入一個結點、在圖中插入一條邊、在圖中尋找序號為v的結點的第一個鄰接結點、在圖中尋找序號為v1結點的鄰接結點v2的下一個鄰接結點、圖的深度優先遍歷、圖的廣度優先遍歷等）。 （3）設計一個測試主函數，首先創建一個圖（有n個結點和e條邊），然后打印圖的n個結點信息和e條邊信息，最后分別打印出圖的深度優先遍歷和廣度優先遍歷的結點信息序列。實驗六順序隊列下的基數排序算法設計（2學時）實驗內容如下： （1）編寫基于順序隊列的基數排序函數。 （2）設計一個測試主函數，實現對基于順序隊列結構的基數排序算法的測試。 （3）分析程序的運行結果。 （4）分析比較鏈式隊列結構的基數排序算法和順序隊列結構的基