數(shù)據(jù)結(jié)構(gòu)課程教學大綱

數(shù)據(jù)結(jié)構(gòu)課程教學大綱課程名稱：數(shù)據(jù)結(jié)構(gòu)/DataStructure課程代碼：06131204課程類型：專業(yè)/必修總學時數(shù)：64（理論學時：40實驗或?qū)嵺`學時：24）學分：4先修課程：計算機應(yīng)用基礎(chǔ)、計算機C程序語言設(shè)計開課單位：經(jīng)管學院適用專業(yè)：信息管理與信息系統(tǒng)專業(yè)一、課程的性質(zhì)、目的和任務(wù)《數(shù)據(jù)結(jié)構(gòu)》是計算機程序設(shè)計的重要理論技術(shù)基礎(chǔ)，數(shù)據(jù)結(jié)構(gòu)課程培養(yǎng)學生的數(shù)據(jù)抽象能力，讓學生了解各種數(shù)據(jù)的組織方式，為學生下一步的面向?qū)ο缶幊桃约败浖ぞ邔W習打下堅實的基礎(chǔ)。二、教學內(nèi)容、教學基本要求及教學重點與難點1．數(shù)據(jù)結(jié)構(gòu)基本概念和術(shù)語了解算法和算法分析，理解數(shù)據(jù)結(jié)構(gòu)基本概念和術(shù)語，掌握抽象數(shù)據(jù)類型的表示與實現(xiàn)。教學重點與難點：數(shù)據(jù)結(jié)構(gòu)的基本概念，算法時間與空間復(fù)雜度，對于抽象數(shù)據(jù)類型的理解與掌握。2．線性表了解雙向鏈表，理解線性表的類型定義，掌握線性表的順序表示和實現(xiàn);掌握線性表的鏈式表示和實現(xiàn)和一元多項式的表示和相加，循環(huán)鏈表的操作。教學重點與難點：線性表的順序表示，線性表的鏈式表示與實現(xiàn)3．棧了解棧和隊列的概念，理解棧的順序存儲表示，掌握隊列的鏈式存儲表示，掌握循環(huán)隊列（隊列的順序表示）的實現(xiàn)。教學重點與難點：棧和隊列的存儲與實現(xiàn)，棧的操作，尤其是?？臻g的動態(tài)分配，循環(huán)隊列的概念與操作。串了解串的概念，理解串類型的定義，掌握串類型的操作。教學重點與難點：串的操作，串的模式匹配，串模式匹配中的KMP算法。5．數(shù)組與廣義表了解多維數(shù)組在內(nèi)存中的保存方式，理解廣義表的概念和存儲方式，掌握多維數(shù)組中某一元素在內(nèi)存中的保存位置的計算，掌握特殊矩陣和稀疏矩陣的壓縮存儲方式。教學重點與難點：多維數(shù)組中元素的保存位置,稀疏矩陣的壓縮存儲，稀疏矩陣十字鏈表保存方式。6．樹了解樹和二叉樹的概念，理解二叉樹的遍歷,掌握樹和二叉樹的存儲方式,掌握赫夫曼樹的概念及其應(yīng)用，掌握線索二叉樹的建立和遍歷。教學重點與難點：樹的概念，二叉樹的遍歷，線索二叉樹的建立和遍歷，稀疏矩陣十字鏈表保存方式。7．圖了解圖的定義和術(shù)語，理解圖的存儲結(jié)構(gòu)，掌握圖的遍歷,理解圖的連通性問題，理解有向無環(huán)圖的概念和應(yīng)用,掌握求最短路徑的方法。教學重點與難點：圖的存儲結(jié)構(gòu)，圖的遍歷，求圖的最短路徑，拓撲排序和關(guān)鍵路徑的求法，最短路徑的求法。8．查找了解二叉排序樹和平衡二叉樹，了解索引順序表的查找，理解順序表的查找，掌握有序表的查找，哈希表的概念及其處理沖突的方法。教學重點與難點：有序表的查找，哈希表的概念及其處理沖突的方法，平衡二叉樹的構(gòu)造方法。9．內(nèi)部排序了解歸并排序和基數(shù)排序，理解每種簡單排序改良后的復(fù)雜排序方法，掌握各種簡單排序方法。教學重點與難點：插入排序，快速排序，選擇排序，堆排序，快速排序。三、課內(nèi)實驗或?qū)嵺`環(huán)節(jié)教學安排及要求序號教學內(nèi)容教學基本要求實驗類別課內(nèi)學時課外學時備注1循環(huán)鏈表的實現(xiàn)了解循環(huán)鏈表概念，熟悉循環(huán)鏈表屬性，掌握建立一個循環(huán)鏈表，按順序輸出所有結(jié)點的數(shù)據(jù)的方法設(shè)計性22必做2約瑟夫環(huán)的實現(xiàn)了解約瑟夫環(huán)概念，熟悉循環(huán)鏈表屬性，掌握用循環(huán)鏈表實現(xiàn)一個約瑟夫環(huán)的方法設(shè)計性22選做3數(shù)制轉(zhuǎn)換程序了解棧的概念，熟悉棧的實現(xiàn)，掌握使用棧將十進制數(shù)轉(zhuǎn)換成八進制數(shù)的方法設(shè)計性22必做4串匹配算法的實現(xiàn)了解串的概念，熟悉串的屬性，掌握輸入母串和子串，求得子串位置的方法設(shè)計性22必做5稀疏矩陣運算了解三元組的概念，熟悉三元組的屬性，掌握將一個三元組表示的稀疏矩陣轉(zhuǎn)置后輸出的方法設(shè)計性22選做6二叉樹數(shù)據(jù)結(jié)構(gòu)的實現(xiàn)了解二叉樹的概念，熟悉二叉樹的屬性，掌握動態(tài)建立一個二叉樹的方法設(shè)計性22選做7二叉樹遍歷演示了解中序遍歷的概念，熟悉中序遍歷的過程，掌握中序遍歷一棵二叉樹，輸出遍歷結(jié)點序列的方法設(shè)計性22必做8樹的存儲了解樹存儲的方式，熟悉樹存儲的實現(xiàn)，掌握用雙親表示法存儲一課樹，并對此樹進行層次遍歷的方法設(shè)計性22選做9圖的數(shù)據(jù)結(jié)構(gòu)的實現(xiàn)了解圖的概念，熟悉圖的表示方式，掌握輸入圖的結(jié)點和邊的信息，用鄰接矩陣存儲這個圖的方法。設(shè)計性22選做10更改圖的存儲方式了解圖的存儲方式，熟悉圖的鄰接矩陣，掌握將一個用鄰接矩陣存儲的圖轉(zhuǎn)換成鄰接表的方法設(shè)計性22選做11折半查找了解查找的概念，熟悉查找的各種方法，掌握按順序輸入一個結(jié)點序列，然后用折半查找找出給定結(jié)點的位置的方法設(shè)計性22必做12簡單排序了解排序的概念，熟悉排序的方法，掌握直接插入，簡單選擇和冒泡排序設(shè)計性22必做小計2424四、學時分配表序號課程內(nèi)容課內(nèi)學時課外學時講課學時上機學時實踐學時試驗學時小計其中課內(nèi)研討學時1緒論224022線性表426043棧和隊列426044串426045數(shù)組和廣義表426046樹和二叉樹628067圖6410068查找448049內(nèi)部排序641006合計402464040五、課外學習要求課外學習主要以做紙質(zhì)練習題和程序為主，練習題每章至少兩個習題以上。程序以上機學習要運行的程序為準。六、教學方法教學方法以課堂講解基本概念及程序編寫及演示為主。有關(guān)程序部分必須解釋每句程序的含義與作用。七、課程考核要求及方法1．考核方式：考試（√）2．成績評定：計分制：百分制（√）；五級分制（）；兩級分制（）總評成績構(gòu)成：平時考核（40）％；中期考核（）％；期末考核（60）％平時成績構(gòu)成：考勤考紀（10）％；作業(yè)（10）％；實踐環(huán)節(jié)（20）％；其他（）％八、建議教材及參考資料建議教材：1、嚴蔚敏，吳偉民編著.數(shù)據(jù)結(jié)構(gòu)(C語言版).清華大學出版社，2001年(第二版)。參考資料：1、夏寬理，王春