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

1、數(shù)據(jù)結(jié)構(gòu)課程教學(xué)大綱課程名稱(chēng)數(shù)據(jù)結(jié)構(gòu)/Data Structure課程編碼10020400110課程類(lèi)型專(zhuān)業(yè)必修課課程性質(zhì)專(zhuān)業(yè)主干課適用范圍信息與計(jì)算科學(xué)專(zhuān)業(yè)學(xué)分?jǐn)?shù)4先修課程程序設(shè)計(jì)語(yǔ)言學(xué)時(shí)數(shù)72 實(shí)驗(yàn)/實(shí)踐學(xué)時(shí)無(wú)課外學(xué)時(shí)無(wú)考核方式考試 （一）課程的地位、作用和任務(wù)“數(shù)據(jù)結(jié)構(gòu)”是計(jì)算機(jī)程序設(shè)計(jì)的重要理論技術(shù)基礎(chǔ)，它不僅是計(jì)算機(jī)科學(xué)的核心課程，而且已成為其他理工科專(zhuān)業(yè)的熱門(mén)選修課。本課程的主要目的是培養(yǎng)學(xué)生的數(shù)據(jù)抽象能力，其任務(wù)是通過(guò)若干數(shù)據(jù)結(jié)構(gòu)應(yīng)用實(shí)例，引導(dǎo)學(xué)生學(xué)習(xí)數(shù)據(jù)類(lèi)型的使用，為學(xué)生今后學(xué)習(xí)、開(kāi)發(fā)與應(yīng)用作些鋪墊。 （二）課程教學(xué)的目的和要求本課程的主要目的是培養(yǎng)學(xué)生的數(shù)據(jù)抽象能力，對(duì)學(xué)生要

2、求如下：掌握算法的時(shí)間分析和空間分析技術(shù)，學(xué)會(huì)分析研究計(jì)算機(jī)加工的數(shù)據(jù)結(jié)構(gòu)的特性，以便為應(yīng)用涉及的數(shù)據(jù)選擇適當(dāng)?shù)倪壿嫿Y(jié)構(gòu)、存儲(chǔ)結(jié)構(gòu)及其相應(yīng)的算法；理解各種數(shù)據(jù)結(jié)構(gòu)的基本概念和術(shù)語(yǔ)，如線(xiàn)性結(jié)構(gòu)、樹(shù)型結(jié)構(gòu)、圖型結(jié)構(gòu)等；了解數(shù)組和廣義表，動(dòng)態(tài)存儲(chǔ)管理，外部排序以及文件的有關(guān)內(nèi)容。另一方面，本課程的學(xué)習(xí)過(guò)程也是復(fù)雜程序設(shè)計(jì)的訓(xùn)練過(guò)程，要求學(xué)生編寫(xiě)程序時(shí)始終堅(jiān)持結(jié)構(gòu)化程序設(shè)計(jì)的思想，可讀性強(qiáng)，符合軟件工程的規(guī)范?！皵?shù)據(jù)結(jié)構(gòu)”作為信息與計(jì)算科學(xué)等專(zhuān)業(yè)的專(zhuān)業(yè)必修課，要求學(xué)生能夠做到為應(yīng)用涉及的數(shù)據(jù)選擇適當(dāng)?shù)倪壿嫿Y(jié)構(gòu)、存儲(chǔ)結(jié)構(gòu)及其相應(yīng)的算法。（三）課程教學(xué)方法和手段本課程80%為教學(xué)部分，20%為學(xué)生自學(xué)部分

3、（教材中打*號(hào)部分）。教學(xué)部分又分為課堂講授及練習(xí)兩部分。課堂講授以多媒體教學(xué)為主，練習(xí)則由教師布置若干任務(wù)，通過(guò)習(xí)題課或?qū)W生獨(dú)立完成。（四）課程與其它課程的聯(lián)系本課程要求學(xué)生具備一定的程序設(shè)計(jì)能力，因此學(xué)生至少應(yīng)先修“計(jì)算機(jī)基礎(chǔ)”及“程序設(shè)計(jì)語(yǔ)言”兩門(mén)專(zhuān)業(yè)基礎(chǔ)課程。通過(guò)對(duì)“數(shù)據(jù)結(jié)構(gòu)”的學(xué)習(xí)，將來(lái)為“數(shù)據(jù)庫(kù)系統(tǒng)”、“面向?qū)ο笙到y(tǒng)設(shè)計(jì)”、“算法設(shè)計(jì)與分析”、“應(yīng)用軟件設(shè)計(jì)”等后續(xù)課程作必要的鋪墊。 （五）教材與參考書(shū)教材：嚴(yán)蔚敏、吳偉民著，數(shù)據(jù)結(jié)構(gòu)（C語(yǔ)言版），清華大學(xué)出版社，2003年教學(xué)參考書(shū)：王 玲，數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)教程，四川大學(xué)出版社，2003年 二、課程的教學(xué)內(nèi)容、重點(diǎn)和難點(diǎn)第一章 緒論內(nèi)

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

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

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

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