資料結構（data structure）
電腦科學與技術、資訊管理及相關專業本科學生
課堂授課學時：60學時實驗學時：20學時
學分：4
c 語言或c++語言、離散數學
五、教學目的
《資料結構》是電腦科學的一門實用性很強的專業基礎課。通過本課程的學習，學生能夠掌握電腦科學中的資料組織、儲存、處理方面的基本方法，並通過書中演算法的學習，掌握資料結構的使用條件和適用情況，了解評價演算法的主要方法和指標，提高程式設計的質量和效率，為今後的學習、工作和生活中運用計算機打下乙個堅實的基礎。
六、學時分配表
七、講授內容
第一章緒論
1.1 什麼是資料結構
介紹線性結構,樹結構,圖結構方面的典型例子.
1.2 基本概念和術語
介紹資料、資料元素、資料物件、資料結構、集合、資料結構的形式定義，資料的邏輯結構、物理結構（儲存結構）、虛擬儲存結構、資料型別、抽象資料型別、多形資料型別、演算法等概念或術語。
1.3 抽象資料型別的表示與實現
介紹一種演算法描述工具類c語言.
1.4 演算法和演算法分析
簡單介紹演算法的特性,演算法設計的要求,演算法效率的度量,演算法的儲存空間需求
第二章線性表
2.1 線性表的型別定義
線性表、資料項、記錄、檔案的概念，抽象資料型別線性表的定義。
2.2 線性表的順序表示和實現
線性表的順序儲存結構中元素的儲存位置公式型別描述插入、刪除、元素定位等操作的演算法。
2.3 線性表的鏈式表示和實現
2.3.1 線性鍊錶
結點、資料域、指標域、指標、線性鍊錶、頭指標、頭結點等術語；
線性鍊錶的型別描述。插入、刪除等操作的演算法。
2.3.2 迴圈鍊錶
2.3.3 雙向鍊錶
第三章棧和佇列
3.1 棧
3.1.1 抽象資料型別棧的定義
棧、棧頂、棧底等術語
棧的抽象資料型別的定義
3.1.2棧的表示和實現
3.2 佇列
3.2.1 抽象資料型別佇列的定義
3.2.2 鏈佇列
佇列的鏈式儲存結構的實現
3.2.3 迴圈佇列
佇列的順序儲存結構的實現
第四章串
4.1 串型別的定義
講授串中常用術語及串的抽象資料型別
4.2 串的表示和實現
串的常用操作在兩種儲存結構下的實現
第五章陣列和廣義表
5.1 陣列的定義
講授陣列抽象資料型別。
5.2 陣列的順序表示和實現
講授以行序為主和以列序為主的陣列儲存結構。
5.3 矩陣的壓縮儲存
講授特殊矩陣和稀疏矩陣的儲存方式及矩陣運算操作的實現。
5.4 廣義表的定義
講授廣義表的抽象資料型別及常用概念術語。
5.5 廣義表的儲存結構
講授廣義表的鏈式儲存結構。
第六章樹和二叉樹
6.1 樹的定義和基本術語
講授樹的定義和樹結構中的術語及樹結構的抽象資料型別。
6.2 二叉樹
講授二叉樹的定義及二叉樹抽象資料型別、二叉樹的性質、二叉樹的儲存結構。
6.3 遍歷二叉樹和線索二叉樹
6.3.1 遍歷二叉樹
主要掌握三種遍歷方法。
6.3.2 線索二叉樹
主要掌握二叉樹線索化的方法。
6.4 樹和森林
講授樹的儲存結構及一般樹和森林與二叉樹的對應轉換、樹與森林的遍歷方法。
6.5 赫夫曼樹
主要掌握構造赫夫曼樹的赫夫曼方法。
第七章圖
7.1 圖的定義和術語
講授圖結構的定義、抽象資料型別、圖當中使用的概念術語。
7.2 圖的儲存結構
陣列表示法,鄰接表法、鄰接多重表、十字鍊錶儲存結構。
7.3 圖的遍歷
講授圖的深度優先搜尋遍歷方法和廣度優先搜尋遍歷方法及演算法。
7.4 最小生成樹
主要掌握普里姆和克魯斯卡爾方法構造最小生成樹,演算法可做選擇講解。
7.5 拓撲排序和關鍵路徑
主要掌握拓撲排序方法, 演算法。求關鍵路徑的方法。
7.6 最短路徑
主要掌握迪傑斯特拉方法和弗洛伊德方法求最短路徑。演算法可做選擇性講解。
第八章查詢
8.1 靜態查詢表
8.1.1 順序表的查詢
順序表的型別描述、順序查詢演算法。
8.1.2 有序表的查詢
二分查詢演算法。
8.1.3 索引順序表的查詢
8.2 二叉排序樹
8.3 雜湊表
8.3.1 什麼是雜湊表
8.3.2 雜湊函式的構造方法
8.3.3 處理衝突的方法
第九章內部排序
9.1 概述
9.2 插入排序
9.2.1 直接插入排序
9.2.2 其它插入排序（選講）
9.2.3 希爾排序
9.3 快速排序
9.4 選擇排序
9.4.1 簡單選擇排序
9.4.2 樹形選擇排序
9.4.3 堆排序
9.5 歸併排序
9.6 基數排序
9.7 各種內部排序方法的比較討論
八、實驗內容：
實驗一利用順序儲存結構儲存線性表時的插入演算法程式設計（綜合性實驗）
實驗內容：線性表順序儲存結構型別定義的描述、線性表順序儲存結構上插入操作演算法的步驟、編寫成乙個完整的vc++源程式。
實驗二利用順序儲存結構儲存線性表時的刪除演算法程式設計（綜合性實驗）
實驗內容：線性表順序儲存結構型別定義的描述、線性表順序儲存結構上刪除操作演算法
的步驟、編寫成乙個完整的vc++源程式。
實驗三利用鏈式儲存結構儲存線性表時的插入演算法程式設計（綜合性實驗）
實驗內容：線性表鏈式儲存結構型別定義的描述、線性表鏈式儲存結構上插入操作演算法的步驟、編寫成乙個完整的vc++源程式。
實驗四利用鏈式儲存結構儲存線性表時的刪除演算法程式設計（綜合性實驗）
實驗內容：線性表鏈式儲存結構型別定義的描述、線性表鏈式儲存結構上刪除操作演算法的步驟、編寫成乙個完整的vc++源程式。
實驗五利用順序儲結構儲存棧的抽象資料型別的實現（綜合性實驗）
實驗內容：棧的順序儲存結構型別定義的描述、棧的順序儲存結構上各種操作演算法的步驟、編寫成乙個完整的vc++源程式。
實驗六迴圈佇列抽象資料型別的實現（綜合性實驗）
實驗內容：迴圈佇列型別定義的描述、迴圈佇列中各種操作演算法的步驟、編寫成乙個完整的vc++源程式。
實驗七用三元組方式儲存稀疏矩陣時矩真轉置演算法的實現（綜合性實驗）
實驗內容：稀疏矩陣的三元組順序表儲存表示的描述、稀疏矩陣轉置演算法的步驟、編寫成乙個完整的vc++源程式。
實驗八按先序遍歷二叉樹建立二叉鍊錶的遞迴演算法的實現（綜合性實驗）
實驗內容：用二叉鍊錶儲存二叉樹的型別描述、先序遍歷二叉樹的遞迴演算法的步驟、編寫成乙個完整的vc++源程式。
實驗九用鄰接矩陣儲存圖構造乙個無向網（綜合性實驗）
實驗內容：用陣列儲存圖的型別描述、建立無向網的鄰接矩陣的演算法步驟、編寫成乙個完整的vc++源程式。
實驗十有序表的二分查詢演算法的實現（綜合性實驗）
實驗內容：靜態查詢表的順序儲存結構的型別描述、有序表上二分查詢演算法的步驟、
編寫成乙個完整的vc++源程式。
九、考核辦法：
考試採用筆試和平時成績相結合的方法，筆試成績佔80%，平時成績佔20%。平時成績包括作業和實驗兩部分。依據工作量統計辦法，作業次數=理論學時/3，本門課程的作業次數為20次，每次0.
5分，共10分。實驗共10個，其中由教師選擇6個實驗用於記分，可根據不同實驗的難易度不同給分，6個實驗共記10分。
十、教材及主要教學參考用書
1、嚴蔚敏、吳偉民編著《（ c 語言版）資料結構》，清華大學出版社。
2、唐髮根編著《資料結構》，科學出版社。
3、資料結構（用物件導向方法與c++描述）》，殷人昆等著，清華大學出版社，清華大
學計算機系列教材。
《資料結構》教學大綱
五 課程的教學內容 一 課堂講授的教學內容 1 資料結構的概念 資料結構的概念，抽象資料型別，演算法和演算法分析。2 線性表 線性表邏輯結構，線性表的順序儲存及運算實現，線性表的鏈式儲存和實現，一元多項式的表示與相加。3棧和佇列 棧基本概念及棧的應用，佇列基本概念及佇列的應用。4 串串及其基本運算，...
《資料結構》課程教學大綱
保持青春的秘訣，是有一顆不安分的心。data structure a 課程 課程性質 專業基礎理論課 必修 適用專業 資訊計算 資訊保安 開課學期 5 總學時數 72 總學分數 4.5 編寫年月 2003年7月 修訂年月 2007年7月 執筆 高學軍 劉科峰 李小英 一 課程的性質和目的 資料結構是...
資料結構本教學大綱
資料結構 本 課程教學大綱 第一部分大綱說明 一 課程的性質與任務 資料結構 本 是 廣播電視大學電腦科學與技術本科專業 專科起點 的統設必修 學位課程。本課程4學分，72學時，其中實驗24學時，開設一學期。資料結構 本 是計算機科學技術與專業的一門重要的專業基礎課。主要介紹如何合理地組織資料 有效...