保持青春的秘訣，是有一顆不安分的心。
data structure a
課程**：
課程性質：專業基礎理論課/必修
適用專業：資訊計算、資訊保安
開課學期：5
總學時數：72
總學分數：4.5
編寫年月：2023年7月
修訂年月：2023年7月
執筆：高學軍、劉科峰、李小英
一、課程的性質和目的
資料結構是資訊與計算科學專業的一門重要專業基礎課程。當用計算機來解決實際問題時，就要涉及到資料的表示及資料的處理，而資料表示及資料處理正是資料結構課程的主要研究物件，通過這兩方面內容的學習，為後續課程，特別是軟體方面的課程打下了厚實的知識基礎，同時也提供了必要的技能訓練。因此，資料結構課程在資訊與計算科學專業中具有舉足輕重的作用。
二、課程教學內容及學時分配
第1章緒論 （4學時）
理解資料、資料元素和資料項的概念及其相互間的關係。理解資料結構的邏輯結構、儲存結構的聯絡與區別，以及在資料結構上施加的運算及其實現。掌握簡單的演算法分析方法。
本章知識點為：資料、資料元素、資料物件、資料結構、儲存結構和資料型別等概念術語的確定含義；抽象資料型別的定義、表示和實現方法；描述演算法的類c語言；演算法設計的基本要求以及從時間和空間角度分析演算法的方法。
第2章線性表 （10學時，2個學時實驗上機）
理解線性表的定義及其運算。理解順序表和煉表的定義、組織形式、結構特徵和型別說明，掌握在這兩種表上實現的插入、刪除和按值查詢的演算法。了解迴圈鍊錶、雙向(迴圈)鍊錶的結構特點和在其上施加的插入、刪除等操作。
掌握稀疏多項式**性表的兩種儲存結構上的實現方法。
本章知識點為：線性表的邏輯結構定義、抽象資料型別定義和各種儲存結構的描述方法；**性表的兩類儲存結構(順序的和鏈式的) 上實現基本操作；稀疏多項式的抽象資料型別定義、表示和加法的實現。
第3章棧和佇列 （6學時，2個學時實驗上機）
理解棧和佇列的定義、特徵及在其上所定義的基本運算。掌握在兩種儲存結構上對棧和佇列所施加的基本運算的實現。熟練掌握迴圈佇列和鏈佇列的基本操作實現演算法，尤其是隊滿和隊空的描述方法。
本章知識點為：抽象資料型別棧的定義；棧的表示和實現；棧的應用；抽象資料型別佇列的定義；鏈佇列；迴圈佇列。
第4章串 （4學時，2個學時實驗上機）
熟悉串的七種基本操作的定義，並能利用這些基本操作來實現串的其它各種操作的方法。熟練掌握在
串的定長順序儲存結構上實現串的各種操作的方法。掌握串的堆儲存結構以及在其上實現串操作的基本方法。
本章知識點為：串的資料型別定義；串的三種儲存表示：定長順序儲存結構、塊鏈儲存結構和堆分配儲存結構；串的各種基本操作的實現及其應用；
第5章陣列和廣義表 （6學時，2個學時實驗上機）
了解陣列的兩種儲存表示方法，並掌握陣列在以行為主的儲存結構中的位址計算方法。掌握對特殊矩陣進行壓縮儲存時的下標變換公式。了解稀疏矩陣的兩種壓縮儲存方法的特點和適用範圍，領會以三元組表示稀疏矩陣時進行矩陣運算採用的處理方法。
掌握廣義表的結構特點及其儲存表示方法。
本章知識點為：陣列的型別定義和表示方式；特殊矩陣和稀疏矩陣的壓縮儲存方法及運算的實現；廣義表的邏輯結構和儲存結構和廣義表的操作。
第6章樹和二叉樹 （12學時，2個學時實驗上機）
深刻理解樹的定義、性質及其儲存方法，熟練掌握二叉樹的二叉鍊錶儲存方式、結點結構和型別定義，並能畫出給定二叉樹的二叉鍊錶的結構示意圖；理解並掌握二叉樹的三種遍歷方法，並能寫出該三種遍歷的演算法；會完成樹、森林與二叉樹間的相互轉換；理解哈夫曼樹的構造方法，並能對給定的資料集合構造出哈夫曼樹。
本章知識點為：二叉樹的定義、性質和儲存結構；二叉樹的遍歷和線索化以及遍歷演算法的各種描述形式；樹和森林的定義、儲存結構、與二叉樹的轉換、遍歷；樹的多種應用。
第7章圖 （12學時，2個學時實驗上機）
理解圖的基本概念及術語，掌握圖的兩種儲存結構(鄰接矩陣和鄰接表)的表示方法；熟練掌握圖的兩種遍歷(深度優先搜尋遍歷和廣度優先搜尋遍歷)的演算法思想、步驟，並能列出在兩種儲存結構上按上述兩種遍歷演算法得到的序列；理解最小生成樹的概念，能按prim演算法構造最小生成樹；了解並掌握拓撲排序、關鍵路徑、最短路徑的演算法思想。
本章知識點為：圖的定義和術語；圖的四種儲存結構：陣列表示法、鄰接表、十字鍊錶和鄰接多重表；圖的兩種遍歷策略：
深度優先搜尋和廣度優先搜尋；圖的連通性：連通分量和最小生成樹；拓撲排序和關鍵路徑；兩類求最短路徑問題的解法。
第8章查詢 （10學時，2個學時實驗上機）
了解查詢的基本思想及查詢成功和不成功的概念，掌握在順序表、有序表、索引表、雜湊表等上的查詢方法和演算法，並能求出相應的平均查詢長度。
本章知識點為：討論查詢表(包括靜態查詢表和動態查詢表)的各種實現方法
：順序表、有序表、樹表和雜湊表；平均查詢長度的討論。
第9章內部排序 （8學時，2個學時實驗上機）
了解排序的基本思想和基本概念，理解和掌握插入排序、氣泡排序、快速排序、直接選擇排序、堆排序、歸併排序和基數排序的基本思想、步驟及演算法。
本章知識點為：討論比較各種內部排序方法，插入排序、交換排序、選擇排序、歸併排序和基數排序的基本思想、演算法特點、排序過程以及它們的時間複雜度分析。在每類排序方法中，又從簡單方法入手，重點討論效能先進的高效方法。
三、課程教學的基本要求本課程是資訊與計算科學專業的重要專業基礎課，電腦科學各領域及有關的系統和應用軟體都要用到各種資料結構。在教學方法上採用課堂講授，課後自學，課堂討論等教學形式。
(一)課堂講授本課程屬於基礎理論課程。在傳授知識原理的前提下，配合實際應用例子，由淺入深善於誘導，使學生從被動吸收知識的狀態下，轉化到主動索取知識的狀態中來，並採用多**輔助教學，加大課堂授課的知識含量。注重培養學生的學習興趣，提高學生的基本素質。
（二）課後自學為了培養學生整理歸納，綜合分析和處理問題的能力，每章都安排一部分內容，課上教師只給出自學提綱，不作詳細講解，課後學生自學。
（三）課堂討論課堂討論的目的是活躍學習氣氛，開拓思路。教師應認真組織，安排重點發言，充分調動每一名同學的學習積極性，做好總結。
（四）課外作業為了讓學生鞏固所學的知識，每章都布置一定數量課外作業。
（五）實驗用c語言或c++語言完成一些演算法設計題。培養學生的演算法設計能力和程式設計能力。
總評成績：平時作業佔30%，閉卷考試佔70%。
四、本課程與其它課程的聯絡與分工先修課程：離散數學，c++物件導向程式設計等。
後續課程：作業系統，資料庫原理等。
五、建議教材與教學參考書
[1] 嚴蔚敏吳偉民編著，資料結構(c語言版)，北京:清華大學出版社, 2004
[2] 嚴蔚敏吳偉民編著，資料結構題集(c語言版)，北京:清華大學出社，2004
[3] willan ford,willian topp. data structures with c++. new jersey:
prentice hall inc, adivision simon & schuster ***pany，1996(資料結構--c++語言描述.北京:清華大學出版社，1997)
[4] 徐孝凱，資料結構實用教程（c/c++描述），北京:清華大學出版社，1999
[5] 陳慧南.資料結構（使用c++語言描述），南京:東南大學出版社，2001
[6] 殷人昆,陶永雷,謝若陽等
.資料結構（用物件導向方法與c++描述），北京:清華大學出版社，1999
保持青春的秘訣，是有一顆不安分的心。
資料結構課程教學大綱
一 課程基本概況 課程名稱 資料結構 課程名稱 英文 data structures 課程編號 b09042 課程總學時 60 其中，講課48，實驗12 課程學分 3 課程分類 專業選修課 開設學期 4 適用專業 計算機網路工程本科 先修課程 集合論，圖論，高階語言 結構或記錄，指標 後續課程 資料...
《資料結構》課程教學大綱
資料結構 課程教學大綱 2012版 一 課程基本資訊 課程名稱 資料結構 英文名稱 data structure 課程編碼 11107c 11207c 課程類別 專業主幹課 總學時 64學時 含實驗16學時 總學分 4 適用專業 電腦科學與技術 網路工程方向 先修課程 高階語言程式設計，離散數學，概...
《資料結構》教學大綱
五 課程的教學內容 一 課堂講授的教學內容 1 資料結構的概念 資料結構的概念，抽象資料型別，演算法和演算法分析。2 線性表 線性表邏輯結構，線性表的順序儲存及運算實現，線性表的鏈式儲存和實現，一元多項式的表示與相加。3棧和佇列 棧基本概念及棧的應用，佇列基本概念及佇列的應用。4 串串及其基本運算，...