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

1、4/4數(shù)據(jù)結(jié)構(gòu)課程教學(xué)大綱英文名稱Data Structure課程代碼EDUE2012課程性質(zhì)必修課授課對(duì)象教育技術(shù)學(xué)學(xué) 分3.5學(xué) 時(shí)72（54+18）課程簡(jiǎn)介在學(xué)習(xí)了一門(mén)程序設(shè)計(jì)課程之后，要想深入學(xué)習(xí)編程，數(shù)據(jù)結(jié)構(gòu)是必要的通關(guān)課程。該課程從比較抽象的視角分析數(shù)據(jù)的邏輯結(jié)構(gòu)、存儲(chǔ)結(jié)構(gòu)及相關(guān)算法的實(shí)現(xiàn)。課程性質(zhì)與目的作為計(jì)算機(jī)相關(guān)專業(yè)的一門(mén)核心基礎(chǔ)課，數(shù)據(jù)結(jié)構(gòu)的研究對(duì)象主要是數(shù)據(jù)的邏輯結(jié)構(gòu)、數(shù)據(jù)的物理存儲(chǔ)結(jié)構(gòu)及對(duì)數(shù)據(jù)的操作（算法）等三個(gè)方面。通過(guò)該課程的學(xué)習(xí)，要求學(xué)習(xí)者能夠掌握常用的線性結(jié)構(gòu)和非線性結(jié)構(gòu)的基本概念、存儲(chǔ)表示和基于不同存儲(chǔ)基礎(chǔ)上的基本操作的實(shí)現(xiàn)方法，學(xué)會(huì)分析各種算法在時(shí)間和空間上

2、的效率等。在此過(guò)程中，培養(yǎng)更加嚴(yán)謹(jǐn)?shù)倪壿嬐评砟芰?，為編?xiě)出高質(zhì)量程序打下良好基礎(chǔ)。教學(xué)內(nèi)容與學(xué)時(shí)分配C語(yǔ)言復(fù)習(xí)（3+2學(xué)時(shí)）教學(xué)內(nèi)容以一個(gè)實(shí)驗(yàn)題為切入點(diǎn)，帶領(lǐng)學(xué)生復(fù)習(xí)相關(guān)知識(shí)點(diǎn)：基本輸入輸出語(yǔ)句的使用、結(jié)構(gòu)體的定義、結(jié)構(gòu)體類型的聲明、結(jié)構(gòu)體變量的定義、結(jié)構(gòu)體數(shù)組、常用算法、函數(shù)的調(diào)用等。教學(xué)要求復(fù)習(xí)C語(yǔ)言相關(guān)知識(shí)點(diǎn)，為數(shù)據(jù)結(jié)構(gòu)的學(xué)習(xí)做好準(zhǔn)備。重點(diǎn)結(jié)構(gòu)體的相關(guān)內(nèi)容難點(diǎn)無(wú)數(shù)據(jù)結(jié)構(gòu)概述（3學(xué)時(shí)）教學(xué)內(nèi)容數(shù)據(jù)結(jié)構(gòu)的起源、基本概念和術(shù)語(yǔ)、抽象數(shù)據(jù)類型、算法與算法分析、學(xué)習(xí)提示教學(xué)要求讓學(xué)生初步建立對(duì)數(shù)據(jù)結(jié)構(gòu)的認(rèn)識(shí)：研究什么、為什么學(xué)習(xí)、怎么學(xué)習(xí)。重點(diǎn)什么是數(shù)據(jù)結(jié)構(gòu)難點(diǎn)無(wú)線性表（6+4學(xué)時(shí)）教學(xué)內(nèi)容線性表

3、的基本概念、順序存儲(chǔ)及操作的實(shí)現(xiàn)、鏈?zhǔn)酱鎯?chǔ)及操作的實(shí)現(xiàn)教學(xué)要求讓學(xué)生了解線性表的邏輯結(jié)構(gòu)、存儲(chǔ)結(jié)構(gòu)，并嘗試在不同存儲(chǔ)結(jié)構(gòu)上實(shí)現(xiàn)線性表的基本操作：建表、查找、插入和刪除元素。重點(diǎn)基本操作的實(shí)現(xiàn)難點(diǎn)鏈?zhǔn)酱鎯?chǔ)上的建表操作棧與隊(duì)列（3+2學(xué)時(shí)）教學(xué)內(nèi)容?；靖拍?、順序棧和鏈棧上操作的實(shí)現(xiàn)、棧的應(yīng)用隊(duì)列基本概念、順序隊(duì)列（循環(huán)隊(duì)列）上操作的實(shí)現(xiàn)、鏈隊(duì)列教學(xué)要求讓學(xué)生了解操作受限的兩個(gè)線性表：棧和隊(duì)列，并掌握棧的基本操作及應(yīng)用。重點(diǎn)棧的應(yīng)用難點(diǎn)無(wú)串（3+2學(xué)時(shí)）教學(xué)內(nèi)容串的基本概念、串的順序存儲(chǔ)及基本操作、串的鏈?zhǔn)酱鎯?chǔ)、串的模式匹配算法教學(xué)要求讓學(xué)生了解另一種特殊的線性表串（所有數(shù)據(jù)元素均為字符），掌握串

4、的基本操作及串的模式匹配算法。重點(diǎn)串的模式匹配算法難點(diǎn)無(wú)數(shù)組和廣義表（3+2學(xué)時(shí)）教學(xué)內(nèi)容數(shù)組的定義、數(shù)組的順序存儲(chǔ)、矩陣的壓縮存儲(chǔ)、廣義表教學(xué)要求讓學(xué)生了解兩種線性結(jié)構(gòu)向非線性結(jié)構(gòu)的過(guò)渡形式：數(shù)組和廣義表，掌握兩種特殊矩陣（對(duì)稱矩陣和稀疏矩陣）的壓縮存儲(chǔ)。重點(diǎn)矩陣的壓縮存儲(chǔ)難點(diǎn)無(wú)樹(shù)和二叉樹(shù)（9+2學(xué)時(shí)）教學(xué)內(nèi)容樹(shù)的基本概念、樹(shù)的存儲(chǔ)結(jié)構(gòu)、二叉樹(shù)的概念與性質(zhì)、二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)、遍歷二叉樹(shù)、線索二叉樹(shù)、樹(shù)和森林與二叉樹(shù)的互換、赫夫曼樹(shù)（最優(yōu)二叉樹(shù)）教學(xué)要求讓學(xué)生了解樹(shù)型結(jié)構(gòu)的邏輯特征，掌握二叉樹(shù)的相關(guān)知識(shí)點(diǎn)并能夠在計(jì)算機(jī)上實(shí)現(xiàn)二叉樹(shù)的基本操作。重點(diǎn)二叉樹(shù)的性質(zhì)、存儲(chǔ)、遍歷難點(diǎn)線索化二叉樹(shù)圖（6+

5、2學(xué)時(shí)）教學(xué)內(nèi)容圖的基本概念、圖的存儲(chǔ)結(jié)構(gòu)、圖的遍歷、連通網(wǎng)的最小生成樹(shù)教學(xué)要求讓學(xué)生了解圖的邏輯特征，掌握?qǐng)D的鄰接矩陣存儲(chǔ)和鄰接表存儲(chǔ)兩種方法，并在此基礎(chǔ)上實(shí)現(xiàn)圖的建立和遍歷算法，初步了解最小生成樹(shù)。重點(diǎn)圖的兩種存儲(chǔ)方式及相應(yīng)操作的實(shí)現(xiàn)難點(diǎn)鄰接表存儲(chǔ)圖的實(shí)現(xiàn)查找（9學(xué)時(shí)）教學(xué)內(nèi)容查找的基本概念、靜態(tài)查找表、動(dòng)態(tài)查找表、哈希表教學(xué)要求讓學(xué)生全面了解各種不同的查找算法：理解算法原理、掌握算法實(shí)現(xiàn)。重點(diǎn)順序表上的查找、有序表上的折半查找、二叉排序樹(shù)上的查找難點(diǎn)二叉排序上上的刪除操作排序（9+2學(xué)時(shí)）教學(xué)內(nèi)容排序的基本概念、插入排序、交換排序、選擇排序、歸并排序教學(xué)要求讓學(xué)生全面了解各種不同的內(nèi)排序（插入、交換、選擇、歸并等）算法的算法思想和算法實(shí)現(xiàn)。重點(diǎn)插入和交換排序難點(diǎn)希爾排序和快速排序的實(shí)現(xiàn)過(guò)程推薦教材及教學(xué)參考書(shū)嚴(yán)蔚敏、吳偉民編著，數(shù)據(jù)結(jié)構(gòu)（C語(yǔ)言），清華大學(xué)出版社，2011年7月。程杰著，大話數(shù)據(jù)結(jié)構(gòu)，清華大學(xué)出版社，2011年6月第1版。授課形式