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

PAGE1PAGE1算法與數(shù)據(jù)結(jié)構(gòu)課程教學(xué)大綱（AlgorithmandDataStructure）學(xué)時(shí)數(shù)：48其中：實(shí)驗(yàn)學(xué)時(shí)：12課外學(xué)時(shí)：0學(xué)分?jǐn)?shù)：3適用專(zhuān)業(yè)：電子信息工程一、課程的性質(zhì)、目的和任務(wù)本課程是電子信息工程專(zhuān)業(yè)的專(zhuān)業(yè)任選課程。本課程的目的在于分析研究計(jì)算機(jī)加工的數(shù)據(jù)對(duì)象的特性，以便選擇適當(dāng)?shù)臄?shù)據(jù)結(jié)構(gòu)和存儲(chǔ)結(jié)構(gòu)，從而使建立在其上的解決問(wèn)題的算法達(dá)到最優(yōu)。其任務(wù)主要是通過(guò)本課程的學(xué)習(xí)，使學(xué)生能深透地理解數(shù)據(jù)結(jié)構(gòu)的邏輯結(jié)構(gòu)和物理結(jié)構(gòu)的基本概念以及有關(guān)算法，培養(yǎng)基本的、良好的程序設(shè)計(jì)技能，編制高效可靠的程序，為以后利用計(jì)算機(jī)資源高效地開(kāi)發(fā)非數(shù)值處理的計(jì)算機(jī)程序打下堅(jiān)實(shí)的理論、方法和技術(shù)基礎(chǔ)。二、課程教學(xué)的基本要求本課程要求學(xué)生能較系統(tǒng)地學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)的邏輯結(jié)構(gòu)和物理結(jié)構(gòu)的基本概念以及有關(guān)算法。并通過(guò)實(shí)踐環(huán)節(jié)，使學(xué)生加深對(duì)算法與數(shù)據(jù)結(jié)構(gòu)的理解，能運(yùn)用數(shù)據(jù)結(jié)構(gòu)知識(shí)建立數(shù)學(xué)模型，解決實(shí)際的應(yīng)用問(wèn)題。（一）了解數(shù)據(jù)結(jié)構(gòu)及其分類(lèi)、數(shù)據(jù)結(jié)構(gòu)與算法的密切關(guān)系。（二）熟悉各種基本數(shù)據(jù)結(jié)構(gòu)及其操作，學(xué)會(huì)根據(jù)實(shí)際問(wèn)題要求來(lái)選擇數(shù)據(jù)結(jié)構(gòu)。（三）掌握設(shè)計(jì)算法的步驟和算法分析方法，掌握數(shù)據(jù)結(jié)構(gòu)在排序等常用算法中的應(yīng)用。三、課程的教學(xué)內(nèi)容、重點(diǎn)和難點(diǎn)第一章緒論一、數(shù)據(jù)結(jié)構(gòu)的基本概念二、算法描述（一）算法的概念（二）算法的描述三、算法分析與評(píng)價(jià)（一）算法設(shè)計(jì)的要求（二）算法效率的度量重點(diǎn)：數(shù)據(jù)結(jié)構(gòu)的基本概念，邏輯結(jié)構(gòu)、存儲(chǔ)結(jié)構(gòu)的聯(lián)系與區(qū)別，算法的分析與評(píng)價(jià)。難點(diǎn)：算法分析第二章線性表一、線性表的基本概念（一）線性表的定義（二）線性表的基本運(yùn)算二、線性表的順序結(jié)構(gòu)及運(yùn)算實(shí)現(xiàn)（一）線性表的順序存儲(chǔ)結(jié)構(gòu)（二）線性表在順序存儲(chǔ)結(jié)構(gòu)下的運(yùn)算實(shí)現(xiàn)三、線性表的鏈?zhǔn)酱鎯?chǔ)和運(yùn)算實(shí)現(xiàn)（一）鏈表的存儲(chǔ)結(jié)構(gòu)（二）單向鏈表（三）循環(huán)鏈表（四）雙向鏈表四、線性表的應(yīng)用重點(diǎn)：掌握在順序表和鏈表上實(shí)現(xiàn)的插入、刪除和按值查找的算法。難點(diǎn)：線性表與線性結(jié)構(gòu)的聯(lián)系與區(qū)別。頭結(jié)點(diǎn)在鏈表中的作用。刪除、插入運(yùn)算中的指針操作順序。第三章棧和隊(duì)列一、棧（一）棧的定義和運(yùn)算（二）棧的順序存儲(chǔ)結(jié)構(gòu)及其基本運(yùn)算的實(shí)現(xiàn)（三）棧的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)及其基本運(yùn)算的實(shí)現(xiàn)二、棧的應(yīng)用三、棧與遞歸（一）遞歸與遞歸程序的設(shè)計(jì)（二）遞歸程序執(zhí)行過(guò)程的分析（三）遞歸的應(yīng)用舉例四、隊(duì)列（一）隊(duì)列的定義和運(yùn)算（二）隊(duì)列的順序存儲(chǔ)結(jié)構(gòu)及其基本運(yùn)算的實(shí)現(xiàn)（三）隊(duì)列的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)及其基本運(yùn)算的實(shí)現(xiàn)（四）隊(duì)列應(yīng)用舉例重點(diǎn)：掌握在兩種存儲(chǔ)結(jié)構(gòu)上對(duì)棧和隊(duì)列所施加的基本運(yùn)算的實(shí)現(xiàn)。難點(diǎn)：循環(huán)隊(duì)列的隊(duì)空、隊(duì)滿判斷條件。循環(huán)隊(duì)列上的插入、刪除操作。第四章串一、串及其運(yùn)算（一）串的邏輯結(jié)構(gòu)（二）串的基本運(yùn)算二、串的存儲(chǔ)結(jié)構(gòu)（一）串的順序存儲(chǔ)結(jié)構(gòu)及其基本運(yùn)算的實(shí)現(xiàn)（二）串的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)及其基本運(yùn)算的實(shí)現(xiàn)重點(diǎn)：串的存儲(chǔ)結(jié)構(gòu)。難點(diǎn)：串的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)及其基本運(yùn)算的實(shí)現(xiàn)。第五章數(shù)組和廣義表一、數(shù)組（一）數(shù)組的定義（二）數(shù)組的基本操作（三）數(shù)組的存儲(chǔ)結(jié)構(gòu)二、矩陣的壓縮存儲(chǔ)（一）特殊矩陣的壓縮存儲(chǔ)方法（二）稀疏矩陣的壓縮存儲(chǔ)方法三、廣義表（一）廣義表的定義（二）廣義表的存儲(chǔ)結(jié)構(gòu)（三）廣義表的基本操作重點(diǎn)：理解多維數(shù)組的結(jié)構(gòu)特點(diǎn)和在內(nèi)存中的兩種順序存儲(chǔ)方式，領(lǐng)會(huì)稀疏矩陣的壓縮方式和簡(jiǎn)單運(yùn)算。難點(diǎn)：稀疏矩陣的壓縮存儲(chǔ)表示下的運(yùn)算的實(shí)現(xiàn)。第六章樹(shù)和二叉樹(shù)一、樹(shù)的邏輯結(jié)構(gòu)和存儲(chǔ)結(jié)構(gòu)（一）樹(shù)的定義和基本運(yùn)算（二）樹(shù)的表示（三）樹(shù)的存儲(chǔ)結(jié)構(gòu)二、二叉樹(shù)（一）二叉樹(shù)的定義與性質(zhì)（二）二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)（三）二叉樹(shù)的基本運(yùn)算及實(shí)現(xiàn)三、遍歷二叉樹(shù)和線索二叉樹(shù)（一）遍歷二叉樹(shù)（二）線索二叉樹(shù)四、樹(shù)、森林與二叉樹(shù)的轉(zhuǎn)換五、二叉樹(shù)的應(yīng)用（一）二叉排序樹(shù)（二）路徑長(zhǎng)度和哈夫曼樹(shù)（三）構(gòu)造哈夫曼樹(shù)重點(diǎn)：理解樹(shù)的定義、術(shù)語(yǔ)，掌握其各種存儲(chǔ)結(jié)構(gòu)。深刻理解二叉樹(shù)的定義、性質(zhì)及其存儲(chǔ)方法。掌握二叉樹(shù)的線索化方法。熟練掌握森林與二叉樹(shù)間的相互轉(zhuǎn)換。領(lǐng)會(huì)樹(shù)和森林的遍歷。難點(diǎn)：二叉樹(shù)的遞歸定義；二叉樹(shù)鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的組織方式；三種遍歷的主要區(qū)別；二叉樹(shù)上的復(fù)雜運(yùn)算；哈夫曼算法及其應(yīng)用。第七章圖一、圖及其基本運(yùn)算（一）圖的定義（二）圖的基本術(shù)語(yǔ)（三）圖的基本運(yùn)算二、圖的存儲(chǔ)結(jié)構(gòu)（一）鄰接矩陣（二）鄰接表（三）十字鏈表三、圖的遍歷（一）深度優(yōu)先搜索（二）廣度優(yōu)先搜索四、最小生成樹(shù)（一）克魯斯卡爾算法（二）普里姆算法*五、最短路徑（一）求一頂點(diǎn)到其余頂點(diǎn)的最短路徑（二）每對(duì)頂點(diǎn)之間的最短路徑*六、拓?fù)渑判蛑攸c(diǎn)：掌握?qǐng)D的兩種存儲(chǔ)結(jié)構(gòu)的表示方法。熟練掌握?qǐng)D的兩種遍歷的算法思想。掌握拓?fù)渑判?、關(guān)鍵路徑、最短路徑的算法思想。難點(diǎn)：正確理解與區(qū)別圖的常用術(shù)語(yǔ)。區(qū)別圖的兩種存儲(chǔ)結(jié)構(gòu)的不同點(diǎn)及其應(yīng)用場(chǎng)合。關(guān)鍵路徑的算法思想。第八章排序一、排序的基本概念（一）排序及其分類(lèi)（二）排序算法的效率分析二、插入排序（一）直接插入排序（二）折半插入排序（三）希爾排序三、交換排序（一）冒泡排序（二）快速排序四、選擇排序（一）簡(jiǎn)單選擇排序（二）堆排序五、歸并排序六、各種排序方法的比較重點(diǎn)：掌握各種排序方法。難點(diǎn)：快速排序算法，堆排序方法。第九章查找一、基本概念二、順序表的靜態(tài)查找（一）簡(jiǎn)單順序查找（二）二分查找（三）分塊查找三、樹(shù)表的動(dòng)態(tài)查找（一）二叉排序樹(shù)（二）平衡二叉樹(shù)四、散列表查找（一）什么是散列表（二）散列函數(shù)的構(gòu)造方法（三）沖突的解決方法（四）散列表的查找及性能分析（五）有關(guān)散列表的算法重點(diǎn)：掌握在順序表、有序表、索引表、散列表等上的查找方法和算法。難點(diǎn)：二叉排序樹(shù)上的插入算法。平衡二叉樹(shù)的旋轉(zhuǎn)平衡算法；散列表上的有關(guān)算法。四、課程各教學(xué)環(huán)節(jié)要求（一）算法與數(shù)據(jù)結(jié)構(gòu)知識(shí)的應(yīng)用很廣泛，所以授課時(shí)，應(yīng)注重與實(shí)際問(wèn)題的聯(lián)系。（二）本課程有12學(xué)時(shí)上機(jī)實(shí)驗(yàn)，通過(guò)上機(jī)使學(xué)生能夠深入理解算法與數(shù)據(jù)結(jié)構(gòu)課程的主要內(nèi)容，掌握其精髓，能夠進(jìn)一步熟悉C語(yǔ)言或者C++的編程。（三）本課程主要是由講授和一定數(shù)量的上機(jī)實(shí)驗(yàn)兩部分組成。在授課的過(guò)程中應(yīng)安排適當(dāng)?shù)淖鳂I(yè)和練習(xí)。（四）增強(qiáng)學(xué)生的感性認(rèn)識(shí)和實(shí)際編程能力，安排一定數(shù)量的綜合性或設(shè)計(jì)性上機(jī)實(shí)驗(yàn)。（五）考試形式開(kāi)卷、閉卷皆可，重點(diǎn)在于運(yùn)用所學(xué)的知識(shí)對(duì)具體實(shí)際問(wèn)題的解決和分析處理。五、學(xué)時(shí)分配教學(xué)內(nèi)容各教學(xué)環(huán)節(jié)學(xué)時(shí)分配作業(yè)題量備注章節(jié)主要內(nèi)容講授實(shí)驗(yàn)討論習(xí)題課外其它小計(jì)1緒論222線性表4433棧和隊(duì)列4434串1125數(shù)組和廣義表2226樹(shù)81947圖61748內(nèi)部排序3329查找3142合計(jì)331234822六、課程與其它課程的聯(lián)系本課程的先修課程為《計(jì)算機(jī)文化基礎(chǔ)》、《C語(yǔ)言程序設(shè)計(jì)》或者《C++語(yǔ)言程序設(shè)計(jì)》。七、教材與教學(xué)參考書(shū)（一）教材趙堅(jiān)等編著.數(shù)據(jù)結(jié)構(gòu)（C語(yǔ)言版）.北京：中國(guó)水利水電出版社，2005年5月。（二）教學(xué)參考書(shū)[1]唐善策等編著.數(shù)據(jù)結(jié)構(gòu)－用C語(yǔ)言描述.北京：高等教育出版，1995年。[2