【正文】 四）教學時數8學時。教學重點：在順序表和鏈表上各種基本算法的實現及相關的時間性能分析。（四）教學時數4學時。算法時間復雜度和空間復雜度的分析。二、教學內容第一章 緒論（一）教學目的要求介紹數據結構的一些基本概念，算法的時間復雜度和空間復雜度的分析方法，抽象數據類型的定義和使用以及算法的描述方法。另一方面，本課程的學習過程也是進行復雜程序設計的訓練過程，要求學生會書寫符合軟件工程規(guī)范的文件，編寫的程序代碼應結構清晰、正確易讀，能上機調試并排除錯誤。第一篇：《算法與數據結構》教學大綱《算法與數據結構》教學大綱一、使用說明（一）課程性質《數據結構》是一門專業(yè)基礎課，在計算機軟件的各個領域中均會使用到數據結構的有關知識。（三）教學時數課堂講授每周4學時，18周，共72學時。掌握數據結構的一些基本概念，掌握算法的時間復雜度和空間復雜度的分析方法，了解抽象數據類型的定義和使用，了解算法的描述方法。教學重點：有關數據結構的各個名詞和術語的含義，以及語句頻度和時間復雜度、空間復雜度的估算。第二章 線性表（一）教學目的與要求介紹線性表的基本概念和類型定義，對順序表和單鏈表的常用操作方法及其程序實現，循環(huán)鏈表和雙向鏈表的定義和它的插入、刪除等操作方法。教學難點：用所學的基本知識設計有效算法解決與線性表相關的應用問題。第三章 棧和隊列（一）教學目的與要求介紹棧和隊列的定義，順序和鏈接存儲的棧和隊列的各種運算的方法及其程序實現。教學難點：遞歸的實現、循環(huán)隊列中對邊界條件的處理。掌握串的基本概念和操作，掌握串的存儲結構以及基本操作的算法實現。優(yōu)先級隊列 隊列 棧與遞歸的實現 棧的應用舉例棧第一節(jié)一、串的定義二、串的基本操作第二節(jié)一、定長順序存儲表示二、堆分配存儲表示三、串的塊鏈存儲表示四、字符串操作的實現第三節(jié)二、模式匹配的一種改進算法（三）教學方法與形式課堂講授、多媒體課件。（二）教學內容主要內容：稀疏矩陣的定義、存儲和運算，廣義表的定義、存儲和運算串的類型定義。（四）教學時數6學時。教學重點：二叉樹和樹的遍歷及其應用。最優(yōu)樹和赫夫曼編碼樹和森林遍歷二叉樹和線索二叉樹二叉樹樹的定義和基本術語第七章 圖（一）教學目的與要求介紹圖的定義和術語；圖的存儲結構及深度和廣度優(yōu)先搜索方法及其實現；圖的生成樹的概念，求圖的最小生成樹的普里姆算法和克魯斯卡爾算法并了解其實現算法；拓撲排序的方法并了解其實現算法；計算關鍵路徑的方法及其實現算法。教學難點：基于遍歷算法的應用。哈希表的定義，構造哈希函數的多種方法，以及處理沖突的方法；B樹的定義，查找、插入和刪除元素的方法。教學重點：順序查找、二分查找、二叉排序樹上查找以及散列表上查找的基本思想和算法實現。第九章 內部排序（一）教學目的與要求介紹插入排序、交換排序、選擇排序、快速排序、歸并排序、基數排序的方法及其實現，快速排序、堆排序、二路歸并排序的方法及其實現，各種排序方法的穩(wěn)定性、時間復雜度和空間復雜度。教學難點：快速排序partition算法的應用和堆的調整。掌握文件和記錄的基本概念以及基本操作。第一節(jié)一、文件及其類別二、記錄的邏輯結構和物理結構三、文件的操作四、文件的物理結構第二節(jié)一、順序文件的定義順序文件 基本概念各種排序方法的綜合比較歸并排序法 基數排序 選擇排序法 交換排序法 插入排序 排序的定義和方法二、順序文件的優(yōu)缺點第三節(jié)一、索引文件的定義二、索引文件的特點第四節(jié)一、ISAM文件二、VSAM文件第五節(jié)一、散列文件的定義二、散列文件的特點第六節(jié)一、多重表文件二、倒排文件（三）教學方法與形式課堂講授、多媒體課件。嚴蔚敏，吳偉民：《數據結構（C語言版）》 及《數據結構題集（C語言版）》，清華大學出版社，2003年第一版。為后續(xù)計算機專業(yè)課程的學習打下堅實的基礎。它既有完整的學科體系和學科深度，又有較強的實踐性。經過上機實習和課程設計的訓練，使學生能夠編制、調試具有一定難度的中型程序；以培養(yǎng)良好的軟件工程習慣和面向對象的軟件思維方法。知識點：數據、數據元素、數據結構、數據類型、抽象數據類型、算法及其設計原則、時間復雜度、空間復雜度。扎實的指針操作和內存動態(tài)分配的編程技術是學好本章的基本要求，分清鏈表中指針 p 和結點 *p 之間的對應關系，區(qū)分鏈表中的頭結點、頭指針和首元結點的不同所指以及循環(huán)鏈表、雙向鏈表的特點等。知識點：順序棧、鏈棧、循環(huán)隊列、鏈隊列。知識點：串的類型定義、串的存儲表示、串匹配、KMP算法。樹和二叉樹(8學時)學習目標：(1)領會樹和二叉樹的類型定義，理解樹和二叉樹的結構差別；(2)熟記二叉樹的主要特性，并掌握它們的證明方法；(3)熟練掌握二叉樹的各種遍歷算法，并能靈活運用遍歷算法實現二叉樹的其它操作；(4)理解二叉樹的線索化過程以及在中序線索化樹上找給定結點的前驅和后繼的方法；(5)熟練掌握二叉樹和樹的各種存儲結構及其建立的算法；(6)學會編寫實現樹的各種操作的算法；(7)了解最優(yōu)樹的特性，掌握建立最優(yōu)樹和赫夫曼編碼的方法。重點和難點：圖的應用極為廣泛，而且圖的各種應用問題的算法都比較經典，因此本章重點在于理解各種圖的算法及其應用場合。知識點：順序表、有序表、索引順序表、靜態(tài)查找樹、二叉查找樹、二叉平衡樹、哈希表。按平均時間復雜度劃分，內部排序可分為三類：O(n2)的簡單排序方法，O(n*logn)的高效排序方法和O(d*n)的基數排序方法；(3)理解排序方法“穩(wěn)定”或“不穩(wěn)定”的含義，弄清楚在什么情況下要求應用的排序方法必須是穩(wěn)定的。重點和難點：本章重點在于了解各種文件的結構特點及其適用場合。隊列()實驗四 隊列的應用要求：理解隊列的定義，特征及在其上所定義的基本運算；掌握在兩種存儲結構上對隊列所施加的基本運算的實現。深刻理解二叉樹的定義，性質及其存儲方法；熟練掌握二叉樹的二叉鏈表存儲方式，結點結構和類型定義；理解并掌握二叉樹的三種遍歷算法；掌握二叉樹的線索化方法；靈活運用二叉樹的遍歷方法解決相關的應用問題。五、大綱說明課堂講述的論題只是核心或有特色的知識內容，還有相當數量的篇章內容留給學生自學，所確定的自學部分內容亦屬考查范圍。本課強調能力的培養(yǎng)，期末采用半開卷考試(允許同學攜帶一頁A4紙的總結資料)。通過這個實驗，培養(yǎng)學生綜合運用數據結構基本知識和程序設計基本知識，解決實際問題，提高程序設計的能力和團隊協作精神。三、基本要求、設計、上機實現等諸環(huán)節(jié)上投入精力，加強指導、討論和答疑的力度。四、教學內容：應用所掌握的線性表、樹、圖等數據結構知識解決實際問題。：按照軟件開發(fā)規(guī)范的要求書寫設計報告（參見附錄三報告書寫格式）；要求報告層次結構清晰、圖表完整、語言通順、字跡工整。五、考核方法學習成績的評定方式：考查。附錄二開發(fā)步驟、目的； ；； ； 、上機調試； 、評價。非數值計算問題的數學模型不再是傳統(tǒng)的數學方程問題，而是諸如表、樹、圖之類的數據結構。教學目的為：了解算法對于程序設計的重要性 ； 學習掌握基本數據結構的描述與實現方法，熟練掌握典型數據結構及其應用算法的設計。算法時間復雜度后綴表達式的算法，數制的換算利用本章的基本知識設計相關的應用問題循環(huán)隊列的特點及判斷溢出的條件利用隊列的特點設計相關的應用問題串的模式匹配運算算法二叉樹遍歷算法的設計利用二叉樹遍歷算法，解決簡單應用問題 哈夫曼樹的算法圖的遍歷最小生成樹最短路徑二叉排序樹查找平衡樹二叉樹堆排序快速排序 歸并排序三、教學方法與手段充分利用多媒體教學工具，配合黑板上的教學內容較難部分的算法實現過程演義四、教學內容、目標與學時分配教學內容 教學目標 課時分配緒論數據結構的內容邏輯結構與存儲結構算法和算法分析