程序設(shè)計(jì)與數(shù)據(jù)結(jié)構(gòu)教學(xué)大綱

1、西安電子科技大學(xué) “卓越工程師教育培養(yǎng)計(jì)劃”試點(diǎn)課程教學(xué)大綱“程序設(shè)計(jì)與數(shù)據(jù)結(jié)構(gòu)”教學(xué)大綱課程名稱：程序設(shè)計(jì)與數(shù)據(jù)結(jié)構(gòu) 英文名稱：Program Design and Data Structure 學(xué) 時(shí)：96 學(xué) 分：6課程類型：必修 課程性質(zhì)：專業(yè)基礎(chǔ)課適用專業(yè)：自動(dòng)化（交通信息工程及控制） 先修課程：計(jì)算機(jī)科學(xué)與編程導(dǎo)論開課學(xué)期：第1、2學(xué)期 開課院系：信息科學(xué)與技術(shù)學(xué)院一、課程的教學(xué)目標(biāo)與任務(wù)本課程培養(yǎng)學(xué)生較熟練地掌握C語言程序設(shè)計(jì)的基本技能，掌握各種基本數(shù)據(jù)結(jié)構(gòu)和算法。通過本課程的學(xué)習(xí)，掌握C語言基礎(chǔ)知識；掌握簡單算法和數(shù)據(jù)結(jié)構(gòu)的基本設(shè)計(jì)方法；掌握復(fù)雜數(shù)據(jù)結(jié)構(gòu)（例如棧和隊(duì)列以及鏈表）

2、的含義并能簡單應(yīng)用，建立程序設(shè)計(jì)的思想，培養(yǎng)學(xué)生的問題解決能力和實(shí)際編程能力；了解并初步掌握當(dāng)前軟件行業(yè)公認(rèn)的程序設(shè)計(jì)風(fēng)格和編程實(shí)踐。學(xué)生應(yīng)掌握各種基本數(shù)據(jù)結(jié)構(gòu)的概念、實(shí)現(xiàn)方法及涉及的基本算法，并能用這些數(shù)據(jù)結(jié)構(gòu)和算法解決相關(guān)的應(yīng)用問題，為進(jìn)一步學(xué)習(xí)相關(guān)學(xué)科打下堅(jiān)實(shí)的基礎(chǔ)。通過本課程的學(xué)習(xí)。重點(diǎn)是闡述程序設(shè)計(jì)思想和各種數(shù)據(jù)結(jié)構(gòu)及其相關(guān)算法，培養(yǎng)學(xué)生分析問題和使用程序和數(shù)據(jù)結(jié)構(gòu)解決問題的能力。二、本課程與其它課程的聯(lián)系和分工“計(jì)算機(jī)科學(xué)與編程導(dǎo)論”是本課程的先修課程。具體分工是:由計(jì)算機(jī)科學(xué)與編程導(dǎo)論課程建立對計(jì)算機(jī)的基本認(rèn)識，了解軟件的構(gòu)成及分類，了解程序的運(yùn)行原理和過程；由本課程介紹程序設(shè)計(jì)

3、基礎(chǔ)和軟件開發(fā)方法，C語言的基本語法和語義（包括變量、簡單數(shù)據(jù)類型、表達(dá)式和語句、輸入和輸出基礎(chǔ)、順序、條件和循環(huán)控制結(jié)構(gòu)、函數(shù)定義、函數(shù)調(diào)用和參數(shù)傳遞等關(guān)于程序設(shè)計(jì)的基本要素），基本數(shù)據(jù)結(jié)構(gòu)和算法，使用C語言進(jìn)行程序設(shè)計(jì)的方法以及使用程序解決問題的方法。與本課程關(guān)聯(lián)的有相同學(xué)期開設(shè)的“程序語言設(shè)計(jì)實(shí)驗(yàn)”獨(dú)立實(shí)驗(yàn)課，此外，為增強(qiáng)軟件開發(fā)能力，在短二期設(shè)置相應(yīng)的能力訓(xùn)練實(shí)踐課程“軟件基礎(chǔ)訓(xùn)練”。本課程為計(jì)算機(jī)學(xué)科的多個(gè)后續(xù)課程打下基礎(chǔ)，如計(jì)算機(jī)網(wǎng)絡(luò)、課外創(chuàng)新實(shí)踐等。三、課程內(nèi)容及基本要求第一部分：C語言程序設(shè)計(jì)（一）計(jì)算機(jī)與程序設(shè)計(jì)概述（2學(xué)時(shí)）主要內(nèi)容：（1）計(jì)算機(jī)軟件分類（2）計(jì)算機(jī)語言（3

4、）程序執(zhí)行的原理和過程（4）軟件開發(fā)方法1.基本要求了解計(jì)算機(jī)軟件的分類以及計(jì)算機(jī)語言的分類；理解程序執(zhí)行的原理和過程；了解基本的軟件開發(fā)方法和應(yīng)用軟件的開發(fā)方法。2.重點(diǎn)、難點(diǎn)重點(diǎn)：程序執(zhí)行的原理和過程由于在計(jì)算機(jī)科學(xué)與編程導(dǎo)論課程中已經(jīng)講授了基本的計(jì)算機(jī)概念和軟件的基礎(chǔ)知識，因此這里僅需進(jìn)行內(nèi)容回顧，并重點(diǎn)討論程序執(zhí)行原理和過程，介紹軟件開發(fā)方法。(二) C程序基礎(chǔ)（2學(xué)時(shí))主要內(nèi)容：（1）字符集、保留字集、標(biāo)識符、算符等基本詞法元素（2）變量聲明和數(shù)據(jù)類型（3）可執(zhí)行語句（4）鍵盤輸入和屏幕輸出等輸入/輸出基礎(chǔ)（5）運(yùn)算符與表達(dá)式（6）C預(yù)處理：include、define（7）C程序的

5、一般形式1.基本要求記住C所用的字符集和保留字，了解C的基本數(shù)據(jù)類型；明確常量、變量與字面量的含義；掌握運(yùn)算符的使用、表達(dá)式的含義和計(jì)算過程；掌握用標(biāo)準(zhǔn)函數(shù)實(shí)現(xiàn)輸入和輸出的基本方法；掌握各類可執(zhí)行語句的使用；了解C編譯器的基本工作過程和各類預(yù)編譯語句的使用；能熟練運(yùn)用上述基本元素進(jìn)行簡單的C程序設(shè)計(jì)。2.重點(diǎn)、難點(diǎn)重點(diǎn)： 基本數(shù)據(jù)類型、運(yùn)算符與表達(dá)式、基本的輸入和輸出處理、語句由于這是第一門程序設(shè)計(jì)課程，因此需要讓學(xué)生深入理解變量、表達(dá)式的內(nèi)涵，掌握C程序的一般形式，并建立良好的編程風(fēng)格。(三) 基本程序控制結(jié)構(gòu)（8學(xué)時(shí))主要內(nèi)容：（1）控制結(jié)構(gòu)（2）條件語句：if語句和switch語句；嵌套

6、if語句和多選項(xiàng)決策（3）循環(huán)語句：for語句；do-while語句;嵌套循環(huán)1.基本要求了解什么是控制結(jié)構(gòu)；掌握基本的程序控制結(jié)構(gòu)（包括順序結(jié)構(gòu)、條件選擇和循環(huán)結(jié)構(gòu)）及其執(zhí)行流程；掌握不同程序控制結(jié)構(gòu)的C語言實(shí)現(xiàn)；掌握嵌套的程序控制結(jié)構(gòu)及其執(zhí)行流程；熟練使用C語言控制結(jié)構(gòu)設(shè)計(jì)程序。2. 重點(diǎn)、難點(diǎn)重點(diǎn)：條件結(jié)構(gòu)和循環(huán)結(jié)構(gòu)的基本形式及執(zhí)行流程難點(diǎn)：if語句的匹配原則；循環(huán)語句的結(jié)束條件和執(zhí)行次數(shù)；復(fù)合控制結(jié)構(gòu)的流程?？梢圆捎昧鞒虉D來闡述不同控制結(jié)構(gòu)的執(zhí)行流程，便于學(xué)生理解。這部分內(nèi)容需特別加強(qiáng)應(yīng)用舉例。(四) 數(shù)組與字符串（6學(xué)時(shí))主要內(nèi)容：（1）聲明和引用數(shù)組及數(shù)組下標(biāo)（2）多維數(shù)組（3）字

7、符數(shù)組與字符串（4）字符串庫函數(shù)的使用1.基本要求掌握聲明數(shù)組和引用數(shù)組的語法；掌握數(shù)組初始化的方法；掌握C語言數(shù)組下標(biāo)的特殊性；了解多維數(shù)組的聲明及引用語法；掌握字符數(shù)組與字符串的區(qū)別；掌握初始化字符串變量的方法；掌握常用的字符串操作庫函數(shù)。2. 重點(diǎn)、難點(diǎn)重點(diǎn)：聲明數(shù)組和引用數(shù)組的語法；字符串的特殊性；字符串操作庫函數(shù)的使用。難點(diǎn)：數(shù)組的存儲和訪問方法；C語言數(shù)組下標(biāo)的特殊性；字符串與字符數(shù)組的區(qū)別。(五) 函數(shù)與模塊化編程（10學(xué)時(shí))主要內(nèi)容：（1）函數(shù)的基本概念（2）函數(shù)的定義、聲明和調(diào)用（3）參數(shù)傳遞和變量的作用域（4）遞歸（5）標(biāo)準(zhǔn)函數(shù)或預(yù)定義函數(shù)（6）模塊化編程1.基本要求了解函

8、數(shù)是過程抽象的基本形式，掌握函數(shù)的定義、聲明和調(diào)用方法；了解函數(shù)、變量等先聲明后引用的一般原則；理解參數(shù)傳遞的內(nèi)涵，了解函數(shù)操作的對象的不同形式、作用域和使用方法；了解遞歸函數(shù)的運(yùn)行過程，掌握遞歸函數(shù)的編寫方法；掌握標(biāo)準(zhǔn)函數(shù)或預(yù)定義函數(shù)的使用方法；理解模塊化編程的內(nèi)涵并掌握自頂向下設(shè)計(jì)的方法。2.重點(diǎn)、難點(diǎn)重點(diǎn)：函數(shù)的定義、聲明和調(diào)用，參數(shù)傳遞，變量（數(shù)據(jù)）的作用域，遞歸函數(shù)的運(yùn)行過程和遞歸函數(shù)的編寫，標(biāo)準(zhǔn)函數(shù)的使用；模塊化編程的意義難點(diǎn)：參數(shù)傳遞，尤其是數(shù)組作為函數(shù)參數(shù)；變量的作用域；遞歸函數(shù)的運(yùn)行過程和遞歸函數(shù)的編寫。這部分內(nèi)容需特別加強(qiáng)應(yīng)用舉例。(六) 結(jié)構(gòu)體與共用體（聯(lián)合）（6學(xué)時(shí)）主

9、要內(nèi)容：（1）結(jié)構(gòu)體的聲明及數(shù)據(jù)程遠(yuǎn)引用（2）共用體的聲明與使用（3）共用體與結(jié)構(gòu)體的區(qū)別1.基本要求掌握結(jié)構(gòu)類型的定義和使用，了解聯(lián)合數(shù)據(jù)類型的定義和使用；理解共用體與結(jié)構(gòu)體的區(qū)別。2.重點(diǎn)、難點(diǎn)重點(diǎn)：結(jié)構(gòu)類型的定義和應(yīng)用。這部分內(nèi)容需特別加強(qiáng)應(yīng)用舉例。(七) 動(dòng)態(tài)數(shù)據(jù)結(jié)構(gòu)（指針）（8學(xué)時(shí))主要內(nèi)容：（1）指針的概念及其含義以及如何使用指針引用變量（2）指針運(yùn)算的意義及其使用（3）動(dòng)態(tài)內(nèi)存分配（4）使用指針實(shí)現(xiàn)鏈表、二叉樹等動(dòng)態(tài)數(shù)據(jù)結(jié)構(gòu)1.基本要求理解指針其實(shí)是一個(gè)內(nèi)存地址；掌握如何通過指針引用變量；理解只恨運(yùn)算的意義及合法性；掌握分配內(nèi)存和回收內(nèi)存的方法；了解如何使用指針實(shí)現(xiàn)鏈表等動(dòng)態(tài)數(shù)據(jù)

10、結(jié)構(gòu)。2.重點(diǎn)、難點(diǎn)重點(diǎn)：指針的概念及其含義了；使用指針變量的方法；指針運(yùn)算的含義。難點(diǎn)：指針是C語言中初學(xué)者比較難以理解和掌握的一個(gè)問題，需要從指針的本質(zhì)來闡明它的實(shí)際意義及使用方法；使用指針實(shí)現(xiàn)動(dòng)態(tài)數(shù)據(jù)結(jié)構(gòu)是一種高效的方法，但也是初學(xué)者容易犯錯(cuò)誤的地方，需要特別加強(qiáng)引用舉例。(八) 文件處理（6學(xué)時(shí)）主要內(nèi)容：（1）文件指針變量（2）文件的打開與關(guān)閉、打開文件的不同方式（3）文件讀寫和定位1.基本要求了解磁盤文件的不同組織形式；掌握打開文件的不同方式和關(guān)閉文件的方法；掌握讀寫文件和在文件中定位的方法。2.重點(diǎn)、難點(diǎn)重點(diǎn)：文件的打開方式；文件讀寫和定位。第二部分：數(shù)據(jù)結(jié)構(gòu)(一) 數(shù)據(jù)結(jié)構(gòu)的基

11、本概念（2學(xué)時(shí)） 主要內(nèi)容：(1) 數(shù)據(jù)結(jié)構(gòu)的概念，包括數(shù)據(jù)、數(shù)據(jù)元素、結(jié)構(gòu)；(2) 邏輯結(jié)構(gòu)和物理結(jié)構(gòu)的概念和區(qū)別；(3) 抽象數(shù)據(jù)類型的概念、表示和實(shí)現(xiàn)；(4) 算法的概念、特性、設(shè)計(jì)要求；(5) 算法性能評價(jià)方法，大O記法。1 基本要求應(yīng)了解數(shù)據(jù)結(jié)構(gòu)的基本含義、課程所研究的主要內(nèi)容，了解四類基本結(jié)構(gòu)：集合、線性結(jié)構(gòu)、樹形結(jié)構(gòu)、圖狀結(jié)構(gòu)。掌握邏輯結(jié)構(gòu)和物理結(jié)構(gòu)的定義與區(qū)別,了解兩類存儲結(jié)構(gòu)：順序存儲結(jié)構(gòu)和鏈?zhǔn)酱鎯Y(jié)構(gòu)。掌握抽象數(shù)據(jù)類型ADT的定義、表示和實(shí)現(xiàn)。掌握算法的定義、特性、設(shè)計(jì)要求和性能度量方法，包括時(shí)間復(fù)雜度和空間復(fù)雜度，能用大O記法表示時(shí)間、空間復(fù)雜度。2 重點(diǎn)與難點(diǎn)重點(diǎn)：數(shù)據(jù)

12、結(jié)構(gòu)的定義，四類基本結(jié)構(gòu)；邏輯結(jié)構(gòu)和物理結(jié)構(gòu)的區(qū)別，兩類存儲結(jié)構(gòu)；ADT的定義；算法的性能度量方法。難點(diǎn)：邏輯結(jié)構(gòu)、物理結(jié)構(gòu)的區(qū)別；時(shí)間復(fù)雜度的定義與大O表示法。（二）線性表（6學(xué)時(shí)）主要內(nèi)容：(1) 線性表的概念與基本運(yùn)算；(2) 線性表的順序表示和實(shí)現(xiàn)；(3) 線性表的鏈?zhǔn)奖硎竞蛯?shí)現(xiàn)，包括單鏈表、靜態(tài)鏈表、循環(huán)鏈表、雙向鏈表；(4) 線性表的應(yīng)用：一元多項(xiàng)式的表示與相加。1. 基本要求掌握線性表的概念和基本運(yùn)算，能用基本運(yùn)算實(shí)現(xiàn)一些應(yīng)用。熟練掌握順序表的表示，理解隨機(jī)存取的含義，掌握順序表的基本算法，包括插入、刪除、查找。熟練掌握鏈?zhǔn)酱鎯Φ谋硎竞蛯?shí)現(xiàn)，理解頭指針、頭結(jié)點(diǎn)的含義，掌握單鏈表、

13、靜態(tài)鏈表、循環(huán)鏈表、雙向鏈表的概念和基本運(yùn)算實(shí)現(xiàn)，包括插入和刪除。2. 重點(diǎn)與難點(diǎn)重點(diǎn)：線性表的概念；順序表的表示、特點(diǎn)，插入、刪除操作的實(shí)現(xiàn)與復(fù)雜度分析；鏈?zhǔn)奖硎镜奶攸c(diǎn)，各種鏈表的概念，插入、刪除操作的實(shí)現(xiàn)。難點(diǎn)：順序表與鏈表的特性對比與選取，插入、刪除操作的實(shí)現(xiàn)。（三）棧和隊(duì)列（4學(xué)時(shí)）主要內(nèi)容：(1) 棧的概念、基本運(yùn)算；(2) 棧的兩種實(shí)現(xiàn)：順序棧和鏈棧，入棧與出棧操作的實(shí)現(xiàn)；(3) 棧的應(yīng)用，特別是棧與函數(shù)調(diào)用、遞歸的關(guān)系；(4) 隊(duì)列的概念、基本運(yùn)算；(5) 隊(duì)列的兩種實(shí)現(xiàn)：鏈隊(duì)列和循環(huán)隊(duì)列，入隊(duì)列和出隊(duì)列操作的實(shí)現(xiàn)。1. 基本要求掌握棧的基本概念：后進(jìn)先出的特點(diǎn)、棧底、棧頂。熟練

14、掌握順序棧和鏈棧的表示方法，入棧、出棧操作的實(shí)現(xiàn)。了解棧的幾種應(yīng)用，如數(shù)制轉(zhuǎn)換、括號匹配的檢驗(yàn)、行編輯程序、迷宮求解、表達(dá)式求值。理解棧在函數(shù)調(diào)用與遞歸實(shí)現(xiàn)中的重要作用，會(huì)寫遞歸程序。掌握隊(duì)列的概念：先進(jìn)先出的特點(diǎn)、隊(duì)頭、隊(duì)尾。熟練掌握鏈隊(duì)列、循環(huán)隊(duì)列的表示方法，入隊(duì)列、出隊(duì)列操作的實(shí)現(xiàn)，理解循環(huán)隊(duì)列設(shè)計(jì)的初衷。2. 重點(diǎn)與難點(diǎn)重點(diǎn)：棧的概念與特點(diǎn)；順序棧和鏈棧的表示，入棧和出棧的實(shí)現(xiàn)；棧與函數(shù)調(diào)用和遞歸實(shí)現(xiàn)的關(guān)系；隊(duì)列的概念與特點(diǎn)；鏈隊(duì)列與循環(huán)隊(duì)列的表示，入隊(duì)列、出隊(duì)列的實(shí)現(xiàn)。難點(diǎn)：棧與函數(shù)調(diào)用、遞歸的關(guān)系；循環(huán)隊(duì)列的設(shè)計(jì)初衷與基本運(yùn)算實(shí)現(xiàn)。（四）串（2學(xué)時(shí)）主要內(nèi)容：(1) 串的概念與基本

15、運(yùn)算；(2) 串的三種表示與實(shí)現(xiàn)：定長順序串、堆分配順序串、塊鏈串；(3) 串的模式匹配算法：BF算法與KMP算法。1. 基本要求掌握串的基本概念：子串、主串、位置；掌握串的基本運(yùn)算。掌握三種表示方法：定長順序存儲、堆分配順序存儲、塊鏈存儲。掌握樸素的模式匹配算法BF算法和改進(jìn)的模式匹配算法KMP算法，理解改進(jìn)的思路。2. 重點(diǎn)與難點(diǎn)重點(diǎn)：串的概念，與線性表的區(qū)別；基本運(yùn)算；三種表示方法；BF算法；KMP算法。難點(diǎn)：KMP算法。（五）數(shù)組和廣義表（4學(xué)時(shí)）主要內(nèi)容：(1) 數(shù)組的定義；(2) 數(shù)組的順序表示和實(shí)現(xiàn)；(3) 矩陣的壓縮存儲；(4) 廣義表1. 基本要求掌握數(shù)組的定義，理解數(shù)組與線

16、性表的區(qū)別。熟練掌握數(shù)組的順序表示和實(shí)現(xiàn)，特別是高維數(shù)組的兩種順序存儲方法：行序?yàn)橹餍蚺c列序?yàn)橹餍?。掌握特殊矩陣的壓縮存儲，包括對稱矩陣、三角矩陣和對角矩陣。掌握稀疏矩陣的壓縮存儲方法。掌握廣義表的定義和基本運(yùn)算，了解廣義表的存儲結(jié)構(gòu)。2. 重點(diǎn)與難點(diǎn)重點(diǎn)：數(shù)組的定義和存儲；特殊矩陣的壓縮存儲；廣義表的定義與運(yùn)算。難點(diǎn)：高維數(shù)組的順序存儲方法；特殊矩陣的壓縮存儲方法。（六）樹和二叉樹（8學(xué)時(shí)）主要內(nèi)容：(1) 樹的定義與基本術(shù)語；(2) 二叉樹的定義、基本性質(zhì)、存儲結(jié)構(gòu)；(3) 二叉樹的遍歷與線索化；(4) 樹與森林的存儲、遍歷，及與二叉樹的轉(zhuǎn)化；(5) 樹的應(yīng)用：樹與等價(jià)類；(6) 樹的應(yīng)用

17、：最優(yōu)二叉樹（Huffman樹）。1. 基本要求掌握樹的定義與基本術(shù)語：結(jié)點(diǎn)、度、葉子、孩子、雙親、兄弟、層次、深度；掌握二叉樹的定義和基本性質(zhì)，掌握基本性質(zhì)的證明方法；掌握二叉樹的順序存儲和鏈?zhǔn)酱鎯煞N實(shí)現(xiàn)方法，理解兩者的適用場合；熟練掌握二叉樹的遍歷方法：先序、中序和后序遍歷；掌握二叉樹的線索化，理解線索化的作用和意義；掌握樹的存儲方法：雙親表示法、孩子表示法、孩子兄弟表示法；掌握樹、森林與二叉樹的轉(zhuǎn)化方法；掌握樹與森林的遍歷方法；掌握用樹實(shí)現(xiàn)等價(jià)類的方法；掌握Huffman樹的構(gòu)造方法與用途。2. 重點(diǎn)與難點(diǎn)重點(diǎn)：二叉樹的定義、性質(zhì)與存儲結(jié)構(gòu)；二叉樹的遍歷；樹與森林的存儲與遍歷。難點(diǎn)：二

18、叉樹遍歷的非遞歸算法實(shí)現(xiàn)；由先序、中序遍歷序列確定二叉樹與森林的方法；Huffman樹的構(gòu)造方法。（七）圖（10學(xué)時(shí)）主要內(nèi)容：(1) 圖的定義和術(shù)語；(2) 圖的存儲結(jié)構(gòu)：鄰接矩陣、鄰接表、十字鏈表、鄰接多重表；(3) 圖的遍歷：深度優(yōu)先搜索和廣度優(yōu)先搜索；(4) 圖的連通分量與最小生成樹；(5) 拓?fù)渑判蚺c關(guān)鍵路徑算法；(6) 最短路徑算法：Dijkstra算法和Flody算法。1. 基本要求掌握圖的定義與術(shù)語：頂點(diǎn)、邊、弧、有向圖、無向圖、鄰接點(diǎn)、簡單路徑、回路、連通圖、連通分量、生成樹；掌握圖的存儲結(jié)構(gòu)：鄰接矩陣、鄰接表、十字鏈表、鄰接多重表；熟練掌握圖的深度優(yōu)先搜索和廣度優(yōu)先搜索遍歷

19、方法；掌握最小生成樹的構(gòu)造方法：Prim算法和Kruskal算法；掌握拓?fù)渑判蛩惴ê完P(guān)鍵路徑的求法；掌握單源最短路徑算法Dijkstra算法和任兩點(diǎn)間的最短路徑算法Flody算法。2. 重點(diǎn)與難點(diǎn)重點(diǎn)：圖的各種存儲結(jié)構(gòu)；圖的遍歷算法；最小生成樹構(gòu)造算法；拓?fù)渑判蛩惴?；關(guān)鍵路徑求法；最短路徑算法。難點(diǎn)：鄰接矩陣和鄰接表的定義與特性；最短路徑算法。（八）查找（6學(xué)時(shí)）主要內(nèi)容：(1) 查找的概念；(2) 靜態(tài)查找表：順序查找、折半查找、索引查找；(3) 動(dòng)態(tài)查找表：二叉排序樹、平衡二叉樹、B樹；(4) 哈希表1. 基本要求掌握查找的基本概念：關(guān)鍵字、查找、平均查找長度；掌握順序查找、折半查找與索引

20、查找的概念、實(shí)現(xiàn)與性能分析方法；掌握二叉排序樹的概念、實(shí)現(xiàn)與性能分析方法；理解平衡二叉樹的設(shè)計(jì)思路；了解B-樹的定義與實(shí)現(xiàn)方法；掌握哈希表的設(shè)計(jì)思路、哈希函數(shù)的構(gòu)造方法、處理沖突的方法和性能分析方法。2. 重點(diǎn)與難點(diǎn)重點(diǎn)：順序查找、折半查找、二叉排序樹的定義、實(shí)現(xiàn)和性能分析；哈希表的定義、哈希函數(shù)構(gòu)造方法、處理沖突方法。難點(diǎn)：平衡二叉樹的實(shí)現(xiàn)；B-樹的實(shí)現(xiàn)；各種查找方法的性能分析。（九）排序（6學(xué)時(shí)）主要內(nèi)容：(1) 排序的基本概念；(2) 插入排序：直接插入、折半插入、2-路插入、希爾排序；(3) 交換排序：起泡排序、快速排序；(4) 選擇排序：簡單選擇排序、樹形選擇排序與堆排序；(5) 歸

21、并排序與基數(shù)排序；(6) 各種內(nèi)部排序算法的比較；(7) 外部排序1. 基本要求掌握排序的基本概念：穩(wěn)定與不穩(wěn)定、內(nèi)部與外部排序；掌握各種插入排序算法的思路、實(shí)現(xiàn)與性能評價(jià)：直接插入、折半插入、2-路插入、希爾排序；掌握起泡排序、快速排序的思路、實(shí)現(xiàn)與性能評價(jià)；掌握簡單選擇排序、堆排序的思路、實(shí)現(xiàn)與性能評價(jià)；掌握歸并排序、基數(shù)排序的思路、實(shí)現(xiàn)與性能評價(jià)；掌握各種內(nèi)部排序算法的性能比較與選取方法；了解外部排序的思路與基本方法。2. 重點(diǎn)與難點(diǎn)重點(diǎn)：直接插入排序、希爾排序；起泡排序、快速排序；簡單選擇排序、堆排序；歸并排序；基數(shù)排序；各種內(nèi)部排序算法的性能分析與比較。難點(diǎn)：希爾排序；快速排序；堆排

22、序；各種內(nèi)部排序算法的性能分析。四、教學(xué)安排及方式總學(xué)時(shí) 96 學(xué)時(shí)，講課 96學(xué)時(shí)。1課時(shí)安排 教學(xué)環(huán)節(jié)教學(xué)時(shí)數(shù)課程內(nèi)容講 課習(xí) 題 課討 論 課上 機(jī)參觀或看錄像小 計(jì)第一部分：C語言程序設(shè)計(jì)(一) 計(jì)算機(jī)與程序設(shè)計(jì)概述2 2 (二) C程序基礎(chǔ)22 2(三) 基本程序結(jié)構(gòu)828(四) 數(shù)組與字符串646(五) 函數(shù)與模塊化編程10610(六) 結(jié)構(gòu)體與共用體626(七) 動(dòng)態(tài)數(shù)據(jù)結(jié)構(gòu)（指針）848(八) 文件處理646第二部分：數(shù)據(jù)結(jié)構(gòu)(一) 緒論2 2 (二) 線性表66(三) 棧和隊(duì)列44(四) 串22(五) 數(shù)組和廣義表44(六) 樹88(七) 圖1010(八) 查找66(九) 排序662實(shí)踐環(huán)節(jié)：獨(dú)立實(shí)驗(yàn)課程：程序語言設(shè)計(jì)實(shí)驗(yàn)（第1學(xué)期）實(shí)踐內(nèi)容：軟件基礎(chǔ)訓(xùn)練（短I學(xué)期）3. 教學(xué)方法和建議程序設(shè)計(jì)和數(shù)據(jù)結(jié)構(gòu)是計(jì)算機(jī)專業(yè)的基礎(chǔ)課，注重理論教學(xué)更注重上機(jī)實(shí)踐。教學(xué)過程中應(yīng)加強(qiáng)應(yīng)用舉例和作業(yè)講評環(huán)節(jié)，使學(xué)生切實(shí)掌握基本的程序設(shè)計(jì)技術(shù)。五