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