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

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

3、的基本概念、順序存儲及操作的實現(xiàn)、鏈?zhǔn)酱鎯安僮鞯膶崿F(xiàn)教學(xué)要求讓學(xué)生了解線性表的邏輯結(jié)構(gòu)、存儲結(jié)構(gòu)，并嘗試在不同存儲結(jié)構(gòu)上實現(xiàn)線性表的基本操作：建表、查找、插入和刪除元素。重點基本操作的實現(xiàn)難點鏈?zhǔn)酱鎯ι系慕ū聿僮鳁Ｅc隊列（3+2學(xué)時）教學(xué)內(nèi)容棧基本概念、順序棧和鏈棧上操作的實現(xiàn)、棧的應(yīng)用隊列基本概念、順序隊列（循環(huán)隊列）上操作的實現(xiàn)、鏈隊列教學(xué)要求讓學(xué)生了解操作受限的兩個線性表：棧和隊列，并掌握棧的基本操作及應(yīng)用。重點棧的應(yīng)用難點無串（3+2學(xué)時）教學(xué)內(nèi)容串的基本概念、串的順序存儲及基本操作、串的鏈?zhǔn)酱鎯Α⒋哪Ｊ狡ヅ渌惴ń虒W(xué)要求讓學(xué)生了解另一種特殊的線性表串（所有數(shù)據(jù)元素均為字符），掌握串

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

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