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

1、數(shù)據(jù)結(jié)構(gòu)課程教學(xué)大綱課程名稱數(shù)據(jù)結(jié)構(gòu)課程編碼131500014課程類型（學(xué)院內(nèi)）跨專業(yè)課程適用范圍院級課程學(xué)分數(shù)3先修課程程序設(shè)計語言學(xué)時數(shù)48其中實驗學(xué)時其中實踐學(xué)時考核方式考試制定單位數(shù)學(xué)與信息科學(xué)學(xué)院執(zhí)筆者 審核者一、教學(xué)大綱說明（一）課程的性質(zhì)、地位、作用和任務(wù)數(shù)據(jù)結(jié)構(gòu)是計算機程序設(shè)計的重要理論技術(shù)基礎(chǔ)，它不僅是計算機科學(xué)的核心課程，而且已成為其他理工科專業(yè)的專業(yè)主干課。本課程的主要目的是培養(yǎng)學(xué)生的數(shù)據(jù)抽象能力，其任務(wù)是通過若干數(shù)據(jù)結(jié)構(gòu)應(yīng)用實例，引導(dǎo)學(xué)生學(xué)習(xí)數(shù)據(jù)類型的使用，為學(xué)生今后學(xué)習(xí)、開發(fā)與應(yīng)用作些鋪墊。（二）課程教學(xué)的目的和要求通過本課程的學(xué)習(xí)，使學(xué)生較好地掌握數(shù)據(jù)結(jié)構(gòu)的基本內(nèi)容

2、，并在一定程度上能利用數(shù)據(jù)結(jié)構(gòu)的思想和方法，為應(yīng)用所涉及的數(shù)據(jù)選擇適當(dāng)?shù)倪壿嫿Y(jié)構(gòu)、存儲結(jié)構(gòu)及其相應(yīng)的算法，解決一些實際問題。具體教學(xué)要求：了解：數(shù)組和廣義表，動態(tài)存儲管理，外部排序以及文件的有關(guān)內(nèi)容。 理解：各種數(shù)據(jù)結(jié)構(gòu)的基本概念和術(shù)語，如線性結(jié)構(gòu)、樹型結(jié)構(gòu)、圖型結(jié)構(gòu)等。 掌握：算法的時間分析和空間分析技術(shù)，學(xué)會分析研究計算機加工的數(shù)據(jù)結(jié)構(gòu)的特性，以便為應(yīng)用涉及的數(shù)據(jù)選擇適當(dāng)?shù)倪壿嫿Y(jié)構(gòu)、存儲結(jié)構(gòu)及其相應(yīng)的算法，通過復(fù)雜程序設(shè)計的訓(xùn)練和堅持結(jié)構(gòu)化程序設(shè)計的思想，使編寫出的程序可讀性強，符合軟件工程的規(guī)范。（三）課程教學(xué)方法與手段本課程80%為教學(xué)部分，20%為學(xué)生自學(xué)部分（教材中打*號部分）。教

3、學(xué)部分又分為課堂講授及練習(xí)兩部分。課堂講授以多媒體教學(xué)為主，練習(xí)則由教師布置若干任務(wù)，通過習(xí)題課或?qū)W生獨立完成，適當(dāng)采用定期答疑以及課外網(wǎng)絡(luò)交流。（四）課程與其它課程的聯(lián)系本課程要求學(xué)生具備一定的程序設(shè)計能力，因此學(xué)生至少應(yīng)先修“計算機基礎(chǔ)”及“程序設(shè)計語言”兩門專業(yè)基礎(chǔ)課程。通過對“數(shù)據(jù)結(jié)構(gòu)”的學(xué)習(xí)，將來為“數(shù)據(jù)庫系統(tǒng)”、“面向?qū)ο笙到y(tǒng)設(shè)計”、“算法設(shè)計與分析”、“ 云計算技術(shù)”等后續(xù)課程作必要的鋪墊。（五）教材與教學(xué)參考書教材：數(shù)據(jù)結(jié)構(gòu)（C語言版），嚴蔚敏、吳偉民著，清華大學(xué)出版社 2003教學(xué)參考書：數(shù)據(jù)結(jié)構(gòu)算法實現(xiàn)及解析，高一凡編著，西安電子科技大學(xué)出版社 2004二、課程的教學(xué)內(nèi)容、

4、重點和難點第一章 緒論內(nèi)容：“數(shù)據(jù)結(jié)構(gòu)”的基本概念和術(shù)語，算法的設(shè)計要求抽象數(shù)據(jù)類型的表示與實現(xiàn)， 算法時間效率及空間效率的度量方法；重點：算法的設(shè)計要求抽象數(shù)據(jù)類型的表示與實現(xiàn)，算法時間效率及空間效率的度量 方法；難點：算法時間效率及空間效率的度量方法；第二章 線性表內(nèi)容：線性表的類型定義，線性表的順序表示和實現(xiàn)，線性表的線性鏈表、循環(huán)鏈表及雙向鏈表的表示和實現(xiàn)及其應(yīng)用（一元多項式相加），抽象數(shù)據(jù)類型的表示與實現(xiàn)；重點：線性表的線性鏈表、循環(huán)鏈表及雙向鏈表的表示和實現(xiàn)及其應(yīng)用（一元多項式相加），抽象數(shù)據(jù)類型的表示與實現(xiàn)；難點：線性表的線性鏈表、循環(huán)鏈表及雙向鏈表的表示和實現(xiàn)及其應(yīng)用（一元多項

5、式相加）。第三章 棧和隊列內(nèi)容：棧和隊列的特性及其抽象數(shù)據(jù)類型表示，棧和隊列的表示和實現(xiàn)，棧的應(yīng)用（數(shù)制轉(zhuǎn)換、括號匹配的檢驗、迷宮求解、表達式求解）；重點：棧和隊列的表示和實現(xiàn)，棧的應(yīng)用（數(shù)制轉(zhuǎn)換、括號匹配的檢驗、迷宮求解、表達式求解）；難點：棧的應(yīng)用（數(shù)制轉(zhuǎn)換、括號匹配的檢驗、迷宮求解、表達式求解）；第四章 串內(nèi)容：串的特點及其類型定義，串的定長順序存儲、堆分配存儲表示方法，串的模式匹配算法，文本編輯方面的應(yīng)用；重點：串的定長順序存儲、堆分配存儲表示方法，串的模式匹配算法，文本編輯方面的應(yīng)用；難點：串的模式匹配算法；第五章 數(shù)組與廣義表內(nèi)容：數(shù)組的定義和性質(zhì)、數(shù)組的順序表示與實現(xiàn)、規(guī)則矩陣與

6、一般稀疏矩陣的壓縮存貯、廣義表的定義、廣義表的存儲結(jié)構(gòu)重點：數(shù)組的順序表示與實現(xiàn)、規(guī)則矩陣與一般稀疏矩陣的壓縮存貯、廣義表的存儲結(jié)構(gòu)難點：規(guī)則矩陣與一般稀疏矩陣的壓縮存貯、廣義表的存儲結(jié)構(gòu)第六章 樹和二叉樹內(nèi)容：樹和二叉樹的定義和性質(zhì)，二叉樹的存儲結(jié)構(gòu)，二叉樹的遍歷算法及線索二叉樹的方法，赫夫曼樹及其應(yīng)用，樹和二叉樹的轉(zhuǎn)換方法，回朔法與樹的遍歷；重點：二叉樹的遍歷算法及線索二叉樹的方法，赫夫曼樹及其應(yīng)用，樹和二叉樹的轉(zhuǎn)換方法，回朔法與樹的遍歷；難點：二叉樹的遍歷算法及線索二叉樹的方法，赫夫曼樹及其應(yīng)用；第七章 圖內(nèi)容：圖的性質(zhì)與特點，圖的鄰接距陣以及鄰接表表示方法，圖的遍歷、最小生成樹、關(guān)鍵路

7、徑以及最短路徑；重點：圖的鄰接距陣以及鄰接表表示方法，圖的遍歷、最小生成樹、關(guān)鍵路徑以及最短路徑；難點：圖的遍歷、求最小生成樹、關(guān)鍵路徑以及最短路徑的算法；第八章 查找內(nèi)容：順序表查找、二叉排序樹和平衡二叉樹，哈希表，各種查找方法在時間上的定性或定量的分析和比較；重點：順序表查找、二叉排序樹和平衡二叉樹，哈希表，各種查找方法在時間上的定性或定量的分析和比較；難點：二叉排序樹和平衡二叉樹，哈希表及各種查找方法在時間上的定性或定量的分析和比較；第九章 內(nèi)部排序內(nèi)容：插入排序、快速排序、選擇排序以及歸并排序、基數(shù)排序的實現(xiàn)方法，各種排序方法在時間上的定性或定量的分析和比較；重點：插入排序、快速排序、選擇排序以及歸并排序的實現(xiàn)方法，各種排序方法在時間上的定性或定量的分析和比較；難點：快速排序、選擇排序以及歸并排序的實現(xiàn)方法。三、學(xué)時分配教學(xué)內(nèi)容各教學(xué)環(huán)節(jié)學(xué)時分配采用何種多媒體教學(xué)手段章節(jié)主要內(nèi)容學(xué)時分配講授實驗討論習(xí)題實踐其它1基本概念和術(shù)語，算法分析22CAI課件，電腦演示2線性表的表示與實現(xiàn)、多項式的表示與相加44CAI課件，電腦演示3棧和隊列的應(yīng)用44CAI課件，電腦演示4串的表示與應(yīng)用422CAI課件，電腦演示5數(shù)組與廣義表44CAI課件，電腦演示6樹和二叉