一、課程基本概況
課程名稱：資料結構
課程名稱（英文）：data structures
課程編號：b09042
課程總學時：60（其中，講課48，實驗12）
課程學分：3
課程分類：專業選修課
開設學期：4
適用專業：計算機網路工程本科
先修課程：集合論，圖論，高階語言（結構或記錄，指標）
後續課程：資料庫，編譯原理，作業系統等
二、課程的性質、目的和任務
資料結構是計算機專業的一門核心專業課程，是軟體課程中非常重要的一門課程，在整個專業教學中占有十分重要的地位，是一門理論性非常強的課程。通過課堂教學、課外練習和上機實習，使學生了解資料物件的特性，資料組織的基本方法，並初步具備分析和解決現實世界問題在計算機中如何表示和處理的能力以及培養良好的程式設計技能，為後續課程的學習和科研工作的參與打下良好的基礎。
三、主要內容、重點及深度
本門課程共60學時，其中理論教學48學時，實驗教學12學時。其中，理論教學部分：
第一章緒論
（一）目的要求
了解資料結構的意義與發展過程、資料結構在電腦科學中的作用、學習本課程的目的、任務及要求。理解資料結構的基本概念；演算法設計；掌握演算法的時間和空間複雜度。
（二）教學內容
本章知識點：
1.相關的基本概念(掌握)；
2.演算法五大要素 (掌握)；
3.計算語句頻度和估算演算法時間複雜度的方法（掌握）。
（三）重點與難點
重點：資料結構的定義；演算法的描述方法。
難點：資料結構的定義；演算法與程式的區別；時間複雜度及其計算。
第二章線性表
（一）目的要求
掌握線性表的邏輯結構；線性表的儲存結構及操作的實現；理解一元多項式的表示；
（二）教學內容
本章知識點：
1.線性表的邏輯結構(掌握)；
2.線性表的儲存結構(掌握)；
3.線性表在順序結構和鏈式結構上實現基本操作的方法(掌握)；
4.從時間和空間複雜度的角度比較線性表兩種儲存結構的不同特點及其適用場合(掌握)。
（三）重點與難點
重點：線性表的概念；線性表的順序儲存結構、鏈式儲存結構及其常用演算法。
難點：鏈式儲存結構及其常用演算法；雙向迴圈鍊錶。
第三章棧和佇列
（一）目的要求
掌握棧的定義，表示及實現；表示式求值；棧與遞迴過程；佇列的定義、表示及實現。
（二）教學內容
本章知識點：
1.棧和佇列的特點(掌握)；
2.在兩種儲存結構上棧的基本操作的實現(掌握)；
3.迴圈佇列和鏈佇列的基本運算(熟練掌握)；
4.遞迴演算法執行過程中棧狀態的變化過程(掌握)。
（三）重點與難點
重點：堆疊和佇列的概念；遞迴的定義；迴圈佇列和鏈佇列的基本運算。
難點：遞迴的程式設計實現；迴圈佇列和鏈佇列的基本運算。
第四章串
（一）目的要求
了解串的邏輯結構，儲存結構；掌握串操作的實現(重點難點bf和kmp演算法) 串的應用。
（二）教學內容
本章知識點：
1.串的七種基本運算的定義（了解）；
2.利用這些基本運算來實現串的其它各種運算的方法(掌握)；
3.在順序儲存結構上實現串的各種操作的方法(掌握)；
4.kmp演算法，熟悉next函式和改進next函式的定義和計算(掌握)；
5.串名的儲存映象和在堆儲存結構實現串操作的方法(理解)。
（三）重點與難點
重點：串定義和儲存方法；串的操作
難點：串操作實現方法
第五章陣列和廣義表
（一）目的要求
掌握陣列的儲存結構；稀疏矩陣的表示及操作的實現；廣義表的定義和儲存結構；廣義表的遞迴演算法。
（二）教學內容
本章知識點：
1.陣列在以行為主的儲存結構中的位址計算方法(掌握)；
2.矩陣實現壓縮儲存時的下標變換(掌握)；
3.理解稀疏矩陣的兩種儲存方式的特點和適用範圍，領會以三元組表示稀疏矩陣時進行運算採用的處理方法(掌握)；
4.廣義表的定義及其儲存結構，學會廣義表的表頭，表尾分析方法(掌握)；
5.學習編制廣義表的遞迴演算法(掌握)。
（三）重點與難點
重點：多維陣列元素儲存位址的計算；稀疏矩陣的三元組表示；廣義表的儲存定義、操作。
難點：稀疏矩陣的三元組表示；廣義表的儲存定義、操作。
第六章樹和二叉樹
（一）目的要求
了解樹的基本概念；理解二叉樹的性質和儲存結構；遍歷二叉樹和線索二叉樹；理解樹的儲存結構和遍歷；集合的一種表示方法；掌握哈夫曼樹及其應用；
（二）教學內容
本章知識點：
1.二叉樹的結構特點(理解)；
2.二叉樹的各種儲存結構的特點及適用範圍(掌握)；
3.按各種次序遍歷二叉樹的遞迴和非遞迴演算法(掌握)；
4.二叉樹的線索化，在中序線索樹上找給定結點的前驅和後繼的方法(掌握)；
5.樹的各種儲存結構及其特點(掌握)；
6.編寫樹的各種運算的演算法(掌握)；
7.建立最優二叉樹和哈夫曼編碼的方法(掌握)。
（三）重點與難點
重點：二叉樹的概念、性質；二叉樹的遍歷方式；構造二叉排序樹。
難點：二叉樹的遍歷方式；二叉排序樹的構造方法；二叉樹的線索化。
第七章圖
（一）目的要求
理解圖的基本概念；圖的儲存結構；掌握圖的遍歷及應用；拓撲排序和關鍵路徑。
（二）教學內容
本章知識點：
1.熟悉圖的各種儲存結構；
2.了解實際問題與採用何種儲存結構和演算法有密切聯絡(掌握)；
3.遍歷圖的遞迴和非遞迴演算法(掌握)；
4.應用圖的遍歷演算法求各種簡單路徑問題（比如，最小生成樹、最短路徑、拓撲排序、關鍵路徑等）(掌握)。
（三）重點與難點
重點：圖的儲存結構；圖的遍歷
難點：圖遍歷的演算法；
第八章動態儲存管理
（一）目的要求
了解邊界標識法和夥伴系統；無用單元收集和緊縮；
（二）教學內容
本章知識點：
1.儲存器分配策略和演算法（了解）；
2.無用單元收集時的標誌演算法（了解）。
（三）重點與難點
儲存器分配策略和演算法、無用單元收集時的標誌演算法
第九章查詢
（一）目的要求
了解靜態查詢表(順序表，有序表，索引順序表)；動態查詢表(二叉排序樹，平衡二叉樹，b-樹和b+樹)的建立和查詢；掌握雜湊表的建立，查詢及分析；
（二）教學內容
本章知識點：
1.順序查詢、折半查詢和索引查詢的方法、應用(掌握)；
2.二叉排序樹的構造方法(掌握)；
3.二叉平衡樹的建立方法(掌握)；
4.b-樹，b+樹和鍵樹的特點以及它們的建立過程（理解）；
5.雜湊表的構造方法(掌握)；
6.按定義計算各種查詢方法在等概率情況下查詢成功時和失敗時的平均查詢長度；
7.雜湊表在查詢不成功時的平均查詢長度的計算方法(掌握)。
（三）重點與難點
重點：二叉排序樹的構造方法、二叉平衡樹的建立方法；雜湊表的構造、應用；
難點：二叉排序樹的構造及應用；雜湊表的構造方法；查詢的平均長度。
第十章內部排序
（一）目的要求
掌握插入排序、交換排序(起泡排序，快速排序)、選擇排序(簡單選擇，樹形選擇，堆)、歸併排序、基數排序等演算法。
（二）教學內容
本章知識點：
1.各種排序方法的特點並能靈活應用(掌握)；
2.各種方法的排序過程(掌握)；
3.各種排序方法的時間複雜度分析(掌握)。
（三）重點與難點
重點：各種排序方法的特點及其應用；實現排序的各種演算法。
難點：各種排序演算法的時間複雜度分析。
第十一章外部排序
（一）目的要求
理解外部排序的基本方法；掌握敗者樹和多路平衡歸併的實現；置換--選擇排序；最佳歸併樹。
（二）教學內容
本章知識點：
1.外部排序的兩個過程(理解)；
2.外排過程中所需進行外存讀/寫次數的計算方法(掌握)；
3.敗者樹的建立過程(掌握)；
4.實現多路歸併的演算法(掌握)；
5.置換-選擇排序的過程(掌握)；
6.最佳歸併樹的構造方法（熟悉）；
7.按最佳歸併樹的歸併方案進行平衡歸併時，外存讀/寫次數的計算方法(掌握)。
（三）重點與難點
重點：外部排序過程和實現方法；多路並歸演算法及其實現；
難點：最佳並歸樹的構造方法及其應用。
實踐教學部分：上機實驗分4個專題，每個專題可提供2~4個難度不等的題目供選。
實驗一停車場管理系統
（一）實驗內容
以棧模擬車場，以佇列模擬車場外的便道，按照從終端讀入的輸入資料序列進行模擬管理。棧以順序結構實現，佇列以鍊錶結構實現。
（二）實驗過程
程式設計實現實驗內容。
（三）實驗教學基本要求
通過例項，使學生掌握棧和佇列兩種特殊的線性結構，掌握棧和佇列的特點。
實驗後學生提交實驗報告。
（四）實驗裝置和材料
計算機。
（五）實驗學時
4學時實驗二教學計畫編制問題
（一）實驗內容
假設任何專業都有固定的學習年限，每學年含兩學期，每學期的時間長度和學分上限值均相等。每個專業開設的課程都是確定的，而且課程在開設時間的安排必須滿足先修關係。每門課程有哪些先修課程是確定的，可以有任意多門，也可以沒有。
每門課恰好佔乙個學期。編制乙個教學計畫程式。
（二）實驗過程
程式設計實現實驗內容。
（三）實驗教學基本要求
通過例項，使學生熟悉圖的各種儲存結構的特性，掌握如何應用圖結構解決具體問題。
實驗後學生提交實驗報告。
（四）實驗裝置和材料
計算機。
（五）實驗學時
2學時實驗三最小生成樹問題
（一）實驗內容
利用克魯斯卡爾演算法求最小生成樹。以文字形式輸出樹中各條邊以及他們的權值。
（二）實驗過程
程式設計實現實驗內容
（三）實驗教學基本要求
通過例項，使學生熟悉圖的各種儲存結構的特性，掌握如何應用圖結構解決具體問題。
實驗後學生提交實驗報告。
（四）實驗裝置和材料
計算機。
（五）實驗學時
2學時實驗四雜湊表設計
（一）實驗內容
假設人名為中國人的漢語拼音形式。待填入雜湊表的人名共有30個，取平均查詢長度的上限為2。雜湊函式用除留餘數法構造，用偽隨機探測再雜湊法處理衝突。
（二）實驗過程
程式設計實現實驗內容
（三）實驗教學基本要求
掌握索引技術的使用。
（四）實驗裝置和材料
計算機（五）實驗學時
4學時四、學時分配表
五、課程教學的基本要求和主要環節
本課程可採用課堂講授、課堂討論、習題課等進行課堂教學;條件允許可採用cai、電子教案、幻燈片、參觀等進行輔助教學;每章布置3~6道習題以鞏固教學; 在課程後半程，安排3~4個上機實驗，讓學生應用資料結構的理論、方法，分組設計幾個較大的軟體，使理論與實際相結合。
《資料結構》課程教學大綱
保持青春的秘訣，是有一顆不安分的心。data structure a 課程 課程性質 專業基礎理論課 必修 適用專業 資訊計算 資訊保安 開課學期 5 總學時數 72 總學分數 4.5 編寫年月 2003年7月 修訂年月 2007年7月 執筆 高學軍 劉科峰 李小英 一 課程的性質和目的 資料結構是...
《資料結構》課程教學大綱
資料結構 課程教學大綱 2012版 一 課程基本資訊 課程名稱 資料結構 英文名稱 data structure 課程編碼 11107c 11207c 課程類別 專業主幹課 總學時 64學時 含實驗16學時 總學分 4 適用專業 電腦科學與技術 網路工程方向 先修課程 高階語言程式設計，離散數學，概...
《資料結構》教學大綱
五 課程的教學內容 一 課堂講授的教學內容 1 資料結構的概念 資料結構的概念，抽象資料型別，演算法和演算法分析。2 線性表 線性表邏輯結構，線性表的順序儲存及運算實現，線性表的鏈式儲存和實現，一元多項式的表示與相加。3棧和佇列 棧基本概念及棧的應用，佇列基本概念及佇列的應用。4 串串及其基本運算，...