【文章內(nèi)容簡介】 時(shí))實(shí)驗(yàn)7 圖的建立與遍歷(2學(xué)時(shí))實(shí)驗(yàn)8 查找與排序(2學(xué)時(shí))注：教師可根據(jù)教學(xué)實(shí)際情況（如：學(xué)生情況及學(xué)時(shí)情況等），適當(dāng)調(diào)整實(shí)踐教學(xué)內(nèi)容及學(xué)時(shí)分配。五、課程考核本課程考核形式為：平時(shí)成績占40%，期末考試成績占60%。其中平時(shí)成績的結(jié)構(gòu)分包括：課堂表現(xiàn)10%、平時(shí)作業(yè)10%和實(shí)驗(yàn)20%，期末考試為閉卷筆試考試：120分鐘，卷面分滿分100分。期末考試成績低于50分者，本課程成績按不及格論處。課堂表現(xiàn)10%：包括課堂考勤和課堂提問，如果缺課課時(shí)達(dá)到本課程教學(xué)時(shí)數(shù)的1/3，則取消考試資格。平時(shí)作業(yè)10%：根據(jù)上交次數(shù)及完成情況進(jìn)行評(píng)定。實(shí)驗(yàn)20%：根據(jù)各次實(shí)驗(yàn)完成情況及實(shí)驗(yàn)報(bào)告成績進(jìn)行評(píng)定。期末考試60%：本課程的期末考試考核內(nèi)容主要包括線性表、棧與隊(duì)列、串、數(shù)組與廣義表、樹與二叉樹、圖、查找和內(nèi)部排序。其中，線性表、二叉樹、圖、查找和內(nèi)部排序內(nèi)容為考核的重點(diǎn)。六、本課程與其它課程的先行后續(xù)關(guān)系先行課程：《高級(jí)程序設(shè)計(jì)語言》、《離散數(shù)學(xué)》后續(xù)課程：《操作系統(tǒng)》、《編譯原理》、《數(shù)據(jù)庫理論》、《算法分析與設(shè)計(jì)》等七、建議教材及教學(xué)參考書：嚴(yán)蔚敏，吳偉民編著，《數(shù)據(jù)結(jié)構(gòu)（C語言版）》，清華大學(xué)出版， 嚴(yán)蔚敏，吳偉民編著，《數(shù)據(jù)結(jié)構(gòu)題集（C語言版）》，清華大學(xué)出版， ：[1] 許卓群，張乃孝，楊冬青，唐世渭，《數(shù)據(jù)結(jié)構(gòu)》，高等教育出版社，2004.[2] 徐孝凱，《數(shù)據(jù)結(jié)構(gòu)簡明教程》，清華大學(xué)出版社，1995 [3] 陳文博，朱青，《數(shù)據(jù)結(jié)構(gòu)與算法》，機(jī)械工業(yè)出版社，1996 [4] 李云清，楊慶紅，揭安全編著，《數(shù)據(jù)結(jié)構(gòu)》（C語言版），人民郵電出版社，2007.[5] 楊秀金主編，《數(shù)據(jù)結(jié)構(gòu)》，西安電子科技大學(xué)出版社，2002.[6] 李廉治，姜文清，郭福順，《數(shù)據(jù)結(jié)構(gòu)》，大連理工大學(xué)出版社，1989[7] Aho A V, Hopcroft J E, Ullman J Structures and Publishing Company,Inc.,1983[8] Baron R J, Shapiro L Structures and their Nostrand Reinhold Company, 1980[9] Esakov J, Weiss Structures: An Advanced Approach Using , Inc.,1989[10] [美]S巴斯《計(jì)算機(jī)算法：設(shè)計(jì)和分析引論》朱洪等譯，復(fù)旦大學(xué)出版社，1985第三篇：《數(shù)據(jù)結(jié)構(gòu) A》課程教學(xué)大綱《數(shù)據(jù)結(jié)構(gòu) A》課程教學(xué)大綱Data Structure A課程代碼：適用專業(yè)：信息計(jì)算、信息安全 總學(xué)時(shí)數(shù)：72編寫年月：2003年7月執(zhí)筆：高學(xué)軍、劉科峰、李小英一、課程的性質(zhì)和目的數(shù)據(jù)結(jié)構(gòu)是信息與計(jì)算科學(xué)專業(yè)的一門重要專業(yè)基礎(chǔ)課程。當(dāng)用計(jì)算機(jī)來解決實(shí)際問題時(shí)，就要涉及到數(shù)據(jù)的表示及數(shù)據(jù)的處理，而數(shù)據(jù)表示及數(shù)據(jù)處理正是數(shù)據(jù)結(jié)構(gòu)課程的主要研究對(duì)象，通過這兩方面內(nèi)容的學(xué)習(xí)，為后續(xù)課程，特別是軟件方面的課程打下了厚實(shí)的知識(shí)基礎(chǔ)，同時(shí)也提供了必要的技能訓(xùn)練。因此，數(shù)據(jù)結(jié)構(gòu)課程在信息與計(jì)算科學(xué)專業(yè)中具有舉足輕重的作用。課程性質(zhì)：專業(yè)基礎(chǔ)理論課/必修 開課學(xué)期：5 總學(xué)分?jǐn)?shù)： 修訂年月：2007年7月二、課程教學(xué)內(nèi)容及學(xué)時(shí)分配第1章 緒論（4學(xué)時(shí)）理解數(shù)據(jù)、數(shù)據(jù)元素和數(shù)據(jù)項(xiàng)的概念及其相互間的關(guān)系。理解數(shù)據(jù)結(jié)構(gòu)的邏輯結(jié)構(gòu)、存儲(chǔ)結(jié)構(gòu)的聯(lián)系與區(qū)別，以及在數(shù)據(jù)結(jié)構(gòu)上施加的運(yùn)算及其實(shí)現(xiàn)。掌握簡單的算法分析方法。本章知識(shí)點(diǎn)為：數(shù)據(jù)、數(shù)據(jù)元素、數(shù)據(jù)對(duì)象、數(shù)據(jù)結(jié)構(gòu)、存儲(chǔ)結(jié)構(gòu)和數(shù)據(jù)類型等概念術(shù)語的確定含義；抽象數(shù)據(jù)類型的定義、表示和實(shí)現(xiàn)方法；描述算法的類C語言；算法設(shè)計(jì)的基本要求以及從時(shí)間和空間角度分析算法的方法。第2章 線性表（10學(xué)時(shí)，2個(gè)學(xué)時(shí)實(shí)驗(yàn)上機(jī)）理解線性表的定義及其運(yùn)算。理解順序表和鏈表的定義、組織形式、結(jié)構(gòu)特征和類型說明，掌握在這兩種表上實(shí)現(xiàn)的插入、刪除和按值查找的算法。了解循環(huán)鏈表、雙向(循環(huán))鏈表的結(jié)構(gòu)特點(diǎn)和在其上施加的插入、刪除等操作。掌握稀疏多項(xiàng)式在線性表的兩種存儲(chǔ)結(jié)構(gòu)上的實(shí)現(xiàn)方法。本章知識(shí)點(diǎn)為：線性表的邏輯結(jié)構(gòu)定義、抽象數(shù)據(jù)類型定義和各種存儲(chǔ)結(jié)構(gòu)的描述方法；在線性表的兩類存儲(chǔ)結(jié)構(gòu)(順序的和鏈?zhǔn)降?上實(shí)現(xiàn)基本操作；稀疏多項(xiàng)式的抽象數(shù)據(jù)類型定義、表示和加法的實(shí)現(xiàn)。第3章 棧和隊(duì)列（6學(xué)時(shí)，2個(gè)學(xué)時(shí)實(shí)驗(yàn)上機(jī)）理解棧和隊(duì)列的定義、特征及在其上所定義的基本運(yùn)算。掌握在兩種存儲(chǔ)結(jié)構(gòu)上對(duì)棧和隊(duì)列所施加的基本運(yùn)算的實(shí)現(xiàn)。熟練掌握循環(huán)隊(duì)列和鏈隊(duì)列的基本操作實(shí)現(xiàn)算法，尤其是隊(duì)滿和隊(duì)空的描述方法。本章知識(shí)點(diǎn)為：抽象數(shù)據(jù)類型棧的定義；棧的表示和實(shí)現(xiàn)；棧的應(yīng)用；抽象數(shù)據(jù)類型隊(duì)列的定義；鏈隊(duì)列；循環(huán)隊(duì)列。第4章 串（4學(xué)時(shí)，2個(gè)學(xué)時(shí)實(shí)驗(yàn)上機(jī)）熟悉串的七種基本操作的定義，并能利用這些基本操作來實(shí)現(xiàn)串的其它各種操作的方法。熟練掌握在串的定長順序存儲(chǔ)結(jié)構(gòu)上實(shí)現(xiàn)串的各種操作的方法。掌握串的堆存儲(chǔ)結(jié)構(gòu)以及在其上實(shí)現(xiàn)串操作的基本方法。本章知識(shí)點(diǎn)為：串的數(shù)據(jù)類型定義；串的三種存儲(chǔ)表示：定長順序存儲(chǔ)結(jié)構(gòu)、塊鏈存儲(chǔ)結(jié)構(gòu)和堆分配存儲(chǔ)結(jié)構(gòu)；串的各種基本操作的實(shí)現(xiàn)及其應(yīng)用；第5章 數(shù)組和廣義表（6學(xué)時(shí)，2個(gè)學(xué)時(shí)實(shí)驗(yàn)上機(jī)）了解數(shù)組的兩種存儲(chǔ)表示方法，并掌握數(shù)組在以行為主的存儲(chǔ)結(jié)構(gòu)中的地址計(jì)算方法。掌握對(duì)特殊矩陣進(jìn)行壓縮存儲(chǔ)時(shí)的下標(biāo)變換公式。了解稀疏矩陣的兩種壓縮存儲(chǔ)方法的特點(diǎn)和適用范圍，領(lǐng)會(huì)以三元組表示稀疏矩陣時(shí)進(jìn)行矩陣運(yùn)算采用的處理方法。掌握廣義表的結(jié)構(gòu)特點(diǎn)及其存儲(chǔ)表示方法。本章知識(shí)點(diǎn)為：數(shù)組的類型定義和表示方式；特殊矩陣和稀疏矩陣的壓縮存儲(chǔ)方法及運(yùn)算的實(shí)現(xiàn)；廣義表的邏輯結(jié)構(gòu)和存儲(chǔ)結(jié)構(gòu)和廣義表的操作。第6章 樹和二叉樹（12學(xué)時(shí)，2個(gè)學(xué)時(shí)實(shí)驗(yàn)上機(jī)）深刻理解樹的定義、性質(zhì)及其存儲(chǔ)方法，熟練掌握二叉樹的二叉鏈表存儲(chǔ)方式、結(jié)點(diǎn)結(jié)構(gòu)和類型定義，并能畫出給定二叉樹的二叉鏈表的結(jié)構(gòu)示意圖；理解并掌握二叉樹的三種遍歷方法，并能寫出該三種遍歷的算法；會(huì)完成樹、森林與二叉樹間的相互轉(zhuǎn)換；理解哈夫曼樹的構(gòu)造方法，并能對(duì)給定的數(shù)據(jù)集合構(gòu)造出哈夫曼樹。本章知識(shí)點(diǎn)為：二叉樹的定義、性質(zhì)和存儲(chǔ)結(jié)構(gòu)；二叉樹的遍歷和線索化以及遍歷算法的各種描述形式；樹和森林的定義、存儲(chǔ)結(jié)構(gòu)、與二叉樹的轉(zhuǎn)換、遍歷；樹的多種應(yīng)用。第7章 圖（12學(xué)時(shí)，2個(gè)學(xué)時(shí)實(shí)驗(yàn)上機(jī)）理解圖的基本概念及術(shù)語，掌握?qǐng)D的兩種存儲(chǔ)結(jié)構(gòu)(鄰接矩陣和鄰接表)的表示方法；熟練掌握?qǐng)D的兩種遍歷(深度優(yōu)先搜索遍歷和廣度優(yōu)先搜索遍歷)的算法思想、步驟，并能列出在兩種存儲(chǔ)結(jié)構(gòu)上按上述兩種遍歷算法得到的序列；理解最小生成樹的概念，能按Prim算法構(gòu)造最小生成樹；了解并掌握拓?fù)渑判?、關(guān)鍵路徑、最短路徑的算法思想。本章知識(shí)點(diǎn)為：圖的定義和術(shù)語；圖的四種存儲(chǔ)結(jié)構(gòu)：數(shù)組表示法、鄰接表、十字鏈表和鄰接多重表；圖的兩種遍歷策略：深度優(yōu)先搜索和廣度優(yōu)先搜索；圖的連通性：連通分量和最小生成樹；拓?fù)渑判蚝完P(guān)鍵路徑；兩類求最短路徑問題的解法。第8章 查找（10學(xué)時(shí)，2個(gè)學(xué)時(shí)實(shí)驗(yàn)上機(jī)）了解查找的基本思想及查找成功和不成功的概念，掌握在順序表、有序表、索引表、散列表等上的查找方法和算法，并能求出相應(yīng)的平均查找長度。本章知識(shí)點(diǎn)為：討論查找表(包括靜態(tài)查找表和動(dòng)態(tài)查找表)的各種實(shí)現(xiàn)方法：順序表、有序表、樹表和哈希表；平均查找長度的討論。第9章 內(nèi)部排序（8學(xué)時(shí)，2個(gè)學(xué)時(shí)實(shí)驗(yàn)上機(jī)）了解排序的基本思想和基本概念，理解和掌握插入排序、冒泡排序、快速排序、直接選擇排序、堆排序、歸并排序和基數(shù)排序的基本思想、步驟及算法。本章知識(shí)點(diǎn)為：討論比較各種內(nèi)部排序方法，插入排序、交換排序、選擇排序、歸并排序和基數(shù)排序的基本思想、算法特點(diǎn)、排序過程以及它們的時(shí)間復(fù)雜度分析。在每類排序方法中，又從簡單方法入手，重點(diǎn)討論性能先進(jìn)的高效方法。三、課程教學(xué)的基本要求本課程是信息與計(jì)算科學(xué)專業(yè)的重要專業(yè)基礎(chǔ)課，計(jì)算機(jī)科學(xué)各領(lǐng)域及有關(guān)的系統(tǒng)和應(yīng)用軟件都要用到各種數(shù)據(jù)結(jié)構(gòu)。在教學(xué)方法上采用課堂講授，課后自學(xué)，課堂討論等教學(xué)形式。(一)課堂講授本課程屬于基礎(chǔ)理論課程。在傳授知識(shí)原理的前提下，配合實(shí)際應(yīng)用例子，由淺入深善于誘導(dǎo)，使學(xué)生從被動(dòng)吸收知識(shí)的狀態(tài)下，轉(zhuǎn)化到主動(dòng)索取知識(shí)的狀態(tài)中來，并采用多媒體輔助教學(xué)，加大課堂授課的知識(shí)含量。注重培養(yǎng)學(xué)生的學(xué)習(xí)興趣，提高學(xué)生的基本素質(zhì)。（二）課后自學(xué)為了培養(yǎng)學(xué)生整理歸納，綜合分析和處理問題的能力，每章都安排一部分內(nèi)容，課上教師只給出自學(xué)提綱，不作詳