資料結構與演算法實驗
指導書電腦科學與資訊工程學院
資料結構與演算法課程組編寫
1. 實驗目的要求
本次實驗的目的掌握順序表的儲存結構形式及其描述和基本運算的實現;掌握動態鍊錶結構及相關演算法設計
實驗要求:輸入和驗證程式例題。正確除錯程式,記錄程式執行結果。完成實驗報告。
2.實驗主要內容
2.1 實現順序表的建立、插入、刪除和輸出功能。
2.2線性表的單鏈表設計以及各種基本操作的實現。
2.3 實現兩個有序單鏈表的合併。
3.實驗步驟
2.1實驗步驟
● 建立main函式。
● 輸入42頁線性表seqlist的定義和相關的常量定義。
● 輸入除錯演算法2.2 inslist 方法,為順序表插入元素。
● 在main函式中呼叫inslist為順序表插入多個資料。
● 編寫線性表輸出函式,通過迴圈依次輸出sqlist中的各個元素的內容。
● 輸入除錯演算法2.3,刪除元素(在刪除元素方法前後分別輸出順序表,觀察刪除結果是否正確)。
2.2實驗步驟
● 建立main函式。
● 輸入48頁鍊錶linklist和結點node的定義。
● 實現演算法2.5,初始化單鏈表。
● 實現演算法2.6 或2.7 ,初始化鍊錶資料。
● 編寫煉表表輸出函式,通過while迴圈依次輸出linklist中的各個元素的內容。輸出剛建立的鍊錶。
● 實現演算法2.8,獲得第i個資料元素
● 實現演算法2.11,在鍊錶中插入資料元素,可通過輸入鍊錶檢查結果。
● 實現演算法2.12,在鍊錶中刪除元素,可通過輸入鍊錶檢查結果。
1.實驗目的要求
本次實驗的目的在於使學生深入了解棧和佇列的特徵,掌握在實際問題背景下的靈活運用。
實驗要求,正確除錯本程式,記錄輸出結果。完成實驗報告。
2.實驗主要內容
2.1 用順序結構表示棧並實現棧的各種基本操作
2.2 使用棧檢查括號匹配的檢驗
2.3採用鏈式結構表示佇列並實現各種基本操作實現(選做)。
3.實驗步驟
2.1實驗步驟
● 建立main函式
● 按80頁錄入seqstack型別定義和相關常量定義。
● 錄入並除錯方法initstack、gettop、push、pop方法
● 編寫方法輸出棧中元素內容
● 呼叫方法,出棧入棧若干元素,通過輸出棧內容,觀察棧內容變化
2.2實驗思路
● 棧操作為字元,因此需要將stackelemtype定義為char
● 迴圈:錄入並除錯演算法3.12
2.4實驗步驟
● 錄入85頁鏈佇列定義
● 實現85頁演算法3.8,3.9。
● 實現輸出佇列內元素方法
● 入佇列、出佇列若干資料,觀察佇列內容變化
1.實驗目的要求
通過本實驗使學生深刻理解二叉樹的性質和儲存結構,熟練掌握二叉樹的遍歷演算法。認識哈夫曼樹、哈夫曼編碼的作用和意義。
實驗要求:建乙個二叉樹並按照前序、中序、後序三種方法遍歷此二叉樹, 正確除錯本程式。
能夠建立乙個哈夫曼樹,並輸出哈夫曼編碼,正確調程式。寫出實驗報告。
2.實驗主要內容
2.1 對二叉樹進行先序、中序、後序遞迴遍歷,中序非遞迴遍歷。
2.2 根據已知的字元及其權值,建立哈夫曼樹,並輸出哈夫曼編碼。
3.實驗步驟
2.1實驗步驟
● 輸入二叉鍊錶的定義
● 錄入除錯演算法6.7,實現二叉樹的建構函式
● 編寫二叉樹列印函式,可以通過遞迴演算法將二叉樹輸出為廣義表的形式,以方便觀察樹的結構。
● 錄入和除錯演算法6.1、6.2、6.3,實現二叉樹的前序、中序和後序的遞迴遍歷演算法。為簡化程式設計,可以將visit函式直接使用printf函式輸出結點內容來代替。
2.2 實驗步驟
● 輸入哈夫曼樹型別定義
● 錄入和除錯演算法6.19、演算法6.20,獲得哈夫曼編碼
1.實驗目的要求
理解圖的基本概念,兩種主要的儲存結構。掌握在鄰接鍊錶儲存結構下的圖的深度優先遞迴遍歷、廣度優先遍歷。通過選做題"最短路徑問題"認識圖及其演算法具有廣泛的應用意義。
實驗要求:正確除錯程式。寫出實驗報告。
2.實驗主要內容
2.1 在鄰接矩陣儲存結構下的圖的深度優先遞迴遍歷、廣度優先遍歷。
2.2 拓撲排序,求圖的拓撲序列
3.實驗步驟
2.1 實驗步驟
● 要完成圖的兩種遍歷演算法,首先需要進行圖的資料初始化。為把時間主要花在遍歷演算法的實現上,圖的初始化採用結構體宣告時初始化的方法。示例**如下:
#include ""
typedef int arcell;
typedef int adjmatrix[5][5];
typedef struct mgraph;
void main(),
0,1,0,1,0},
1,0,0,0,1},
1,0,0,1,0},
0,1,0,0,1},
1,0,0,0,0}} ,5,9};
}● 錄入除錯演算法7.5 深度優先遍歷圖,輸出頂點遍歷順序。
● 錄入除錯演算法7.8廣度優先遍歷圖, 輸出頂點遍歷順序。
2.2實驗步驟
● 錄入adjlist 鄰接表結構定義
● 錄入並除錯演算法7.11 拓撲排序演算法(需要先實現演算法7.12求入度演算法)
1.實驗目的要求
了解靜態搜尋、動態搜尋和雜湊(雜湊)搜尋表的基本方法。
實驗要求:正確除錯程式,記錄結果,寫出實驗報告。
2.實驗主要內容
2.1 編寫折半查詢演算法。
2.2 選用一種方法構造雜湊表,並提供該雜湊表查詢元素的方法。
3.實驗步驟
2.1 實驗步驟
● 錄入並除錯演算法8.3
● 修改演算法8.3,能夠輸出折半查詢每次比較的關鍵字
2.2 實驗步驟
● 參考演算法8.15進行實現
1.實驗目的要求
理解並掌握內部排序的各種演算法和使用場合
實驗要求:正確除錯程式,記錄結果,寫出實驗報告。
2.實驗主要內容
2.1 編寫實現高階排序演算法和普通排序演算法的效率。
2.2 構造大量資料,比較演算法之間的花費時間
3.實驗步驟
2.1 實驗步驟
● 編寫**,產生乙個包含至少1萬以上不重複資料的陣列keylist。
● 錄入並實現演算法9.1,對keylist進行排序。
● 錄入並實現演算法9.3,對keylist進行排序。
● 比較兩種演算法之間的計算時間差異。
● 把陣列大小提高到10萬、20萬、30萬、40萬、50萬、比較兩種演算法計算時間差異,繪製兩種演算法的時間曲線(execl)。
2019版《資料結構A》課程實驗指導書
data structure course design 課程編號 06311360學時 15 學分 1 先修課程 程式設計基礎 物件導向程式設計 適用專業 電腦科學與技術 網路工程 軟體工程 一 實驗目的 資料結構a 課程是電腦科學與技術及其相關專業的一門重要的專業基礎課。在課堂教學中,比較全面 ...
資料結構實驗指導書
第一部分課程概述 資料結構是計算機程式設計的重要理論技術基礎,它不僅是計算機學科的核心課程,而且已成為其它立功專業的熱門選修課。資料結構實驗可以使學生對資料結構課程所教授的內容通過實驗環節加以實踐,提高學生的程式設計 編寫及除錯能力,是一門基礎的實驗課程。第二部分實驗要求 通過實驗,學生對常用資料結...
資料結構實驗指導書
實驗名稱資料結構試驗 課程名稱資料結構 專業班級學生姓名 學號成績 指導老師實驗日期 2010年3月 5月 實驗報告如列印,紙張用a4,左裝訂 頁邊距 上下2.5cm,左2.5cm,右2.0cm 字型 字型小四號,1.25倍行距。驗證性 綜合性實驗報告應包含的主要內容 一 實驗目的及要求 1 實驗目...