數(shù)據(jù)結(jié)構(gòu)A教學(xué)實(shí)施方案(參考)

1、201 201 學(xué)年第 學(xué)期數(shù)據(jù)結(jié)構(gòu)A課程教學(xué)實(shí)施方案（計(jì)算機(jī)科學(xué)與技術(shù)、軟件工程專(zhuān)業(yè) 教學(xué)班號(hào)：001）任課教師： 樂(lè)曉波一、 課程概況【課程名稱(chēng)】 數(shù)據(jù)結(jié)構(gòu)A ?！菊n程性質(zhì)】 本課程屬于計(jì)算機(jī)科學(xué)與技術(shù)、軟件專(zhuān)業(yè)的專(zhuān)業(yè)基礎(chǔ)課，必修課?！窘虒W(xué)對(duì)象】 計(jì)算機(jī)軟件工程專(zhuān)業(yè)（14-1、2班），教學(xué)班號(hào)：001?！窘虒W(xué)總學(xué)時(shí)】56學(xué)時(shí)。其中：理論教學(xué)40學(xué)時(shí)，實(shí)驗(yàn)：16學(xué)時(shí)。【學(xué)分】 3.5學(xué)分。【先修課程】C語(yǔ)言程序設(shè)計(jì)（或C+語(yǔ)言程序設(shè)計(jì)）?！竞笮拚n程】操作系統(tǒng)、編譯原理、程序設(shè)計(jì)方法。二、 教學(xué)地位與作用及主要教學(xué)目的數(shù)據(jù)結(jié)構(gòu)是計(jì)算機(jī)軟件專(zhuān)業(yè)的一門(mén)重要的專(zhuān)業(yè)理論基礎(chǔ)課，它不僅是計(jì)算機(jī)科學(xué)的核心

2、課程，而且也是其他理工專(zhuān)業(yè)的熱門(mén)選修課程。數(shù)據(jù)結(jié)構(gòu)課程是操作系統(tǒng)、編譯原理、程序設(shè)計(jì)方法、人工智能原理等后續(xù)課程的重要基礎(chǔ)課程，同時(shí)，其所涉及的內(nèi)容也是程序設(shè)計(jì)技術(shù)的必備知識(shí)。通過(guò)學(xué)習(xí)該課程使學(xué)生學(xué)會(huì)分析和研究計(jì)算機(jī)進(jìn)行數(shù)據(jù)加工的數(shù)據(jù)結(jié)構(gòu)特性，掌握算法的復(fù)雜度分析技術(shù)，并初步具有對(duì)實(shí)際應(yīng)用問(wèn)題的認(rèn)識(shí)和分析能力，對(duì)于實(shí)際應(yīng)用問(wèn)題能選擇適當(dāng)?shù)臄?shù)據(jù)結(jié)構(gòu)和存儲(chǔ)結(jié)構(gòu)以及相應(yīng)的算法編制出高效率的程序，同時(shí)為后續(xù)專(zhuān)業(yè)課程打下基礎(chǔ)。數(shù)據(jù)結(jié)構(gòu)課程的主要內(nèi)容包括：算法分析、線性表及其應(yīng)用、棧和隊(duì)列、串及其應(yīng)用、數(shù)組和廣義表、樹(shù)和二叉樹(shù)及其應(yīng)用、圖的表示及其應(yīng)用、查找方法及其分析、排序算法及其分析技術(shù)等。三、 課程

3、選用教材 【使用教材】1教材：陳倩怡等編著.數(shù)據(jù)結(jié)構(gòu)（C語(yǔ)言版）.武昌: 華中科技大學(xué)出版社,2013年1月出版。2教材選用依據(jù)：該教材在總結(jié)我校計(jì)算機(jī)類(lèi)二十多年教學(xué)的實(shí)踐經(jīng)驗(yàn)，兼顧本學(xué)科的廣度與深度的基礎(chǔ)上，集我校計(jì)算機(jī)與通信工程學(xué)院計(jì)算機(jī)科學(xué)與技術(shù)教研室全體教師的集體智慧而編寫(xiě)出來(lái)的一本適合我校計(jì)算機(jī)類(lèi)本科學(xué)生的實(shí)用教材。該教材概念表述嚴(yán)謹(jǐn)，邏輯推理嚴(yán)密，語(yǔ)言精練，是計(jì)算機(jī)類(lèi)一本極好的教科書(shū)?！緟⒖冀滩摹?1. 王紅梅數(shù)據(jù)結(jié)構(gòu)（C+版）M北京：清華大學(xué)出版社，2007年7月出版。2. 李根強(qiáng)主編.數(shù)據(jù)結(jié)構(gòu)（C+版）M. 北京:中國(guó)水利電力出版社,2005年1月出版3. 朱戰(zhàn)立編著數(shù)據(jù)結(jié)構(gòu)（

4、C+語(yǔ)言描述）M. 北京:高等教育出版社,2004年月出版4. 教材：嚴(yán)蔚敏，吳偉民編著.數(shù)據(jù)結(jié)構(gòu)（C語(yǔ)言版）.北京: 清華大學(xué)出版社,2010年3月修訂版。在講授過(guò)程中，考慮到該課程理論性邏輯性強(qiáng)、難度大等特點(diǎn)，任課教師應(yīng)采取深入淺出的原則，對(duì)每個(gè)教學(xué)內(nèi)容結(jié)合實(shí)際應(yīng)用問(wèn)題以更加生動(dòng)的方式講述該課程的全部?jī)?nèi)容。對(duì)概念、原理的解釋和描述應(yīng)盡可能地以日常生活所接觸到的實(shí)際例子和圖示加以對(duì)比說(shuō)明（如線性表的應(yīng)用、圖的遍歷的應(yīng)用、最短路徑和關(guān)鍵路徑的應(yīng)用等），引導(dǎo)學(xué)生逐步理解概念與原理之間、原理與應(yīng)用之間的聯(lián)系。四、 本課程的特點(diǎn)及教學(xué)手段和方法1 課程特點(diǎn)：數(shù)據(jù)結(jié)構(gòu)以嚴(yán)謹(jǐn)?shù)臄?shù)學(xué)和C或C+語(yǔ)言為基礎(chǔ)，

5、既有抽象的數(shù)據(jù)類(lèi)型的定義，又有嚴(yán)格的C語(yǔ)言類(lèi)型定義和算法描述，既有直觀的圖形表示，又有豐富的系統(tǒng)描述手段和算法的分析技術(shù)，為計(jì)算機(jī)科學(xué)及計(jì)算機(jī)的應(yīng)用提供堅(jiān)實(shí)的理論基礎(chǔ)和應(yīng)用分析工具，是一門(mén)集理論和實(shí)踐為一體的綜合性課程。其特點(diǎn)是基礎(chǔ)理論性強(qiáng)，既有邏輯思維、抽象思維的訓(xùn)練，又有聯(lián)系實(shí)際的物理形象思維的鍛煉，且所涉及的應(yīng)用面較廣。2 課程重點(diǎn)和難點(diǎn)：重點(diǎn)：線性表、棧和隊(duì)列、樹(shù)與二叉樹(shù)、圖、查找、內(nèi)部排序。難點(diǎn)：結(jié)構(gòu)體數(shù)據(jù)類(lèi)型的應(yīng)用、指針數(shù)據(jù)類(lèi)型的應(yīng)用、數(shù)組、線索化二叉樹(shù)、算法的遞歸與非遞歸實(shí)現(xiàn)。3 教學(xué)方法與手段：講授時(shí)要遵循由淺入深的原則，對(duì)易混淆的概念加以詳細(xì)說(shuō)明，對(duì)每章的重點(diǎn)及各類(lèi)不同類(lèi)型的

6、數(shù)據(jù)結(jié)構(gòu)要作詳細(xì)的分類(lèi)介紹，并著重培養(yǎng)學(xué)生對(duì)實(shí)際應(yīng)用問(wèn)題進(jìn)行形式化描述及構(gòu)造算法的能力以及在此基礎(chǔ)上進(jìn)行算法分析的能力。為幫助學(xué)生理解較抽象的內(nèi)容，力爭(zhēng)在較少的學(xué)時(shí)數(shù)中講授體系完整的教學(xué)內(nèi)容，擬采用我室自制的完全符合教學(xué)大綱的電子教學(xué)課件。同時(shí)，利用“學(xué)寶”教學(xué)教學(xué)軟件采用云環(huán)境下新的教學(xué)模式，推進(jìn)教學(xué)方法的改革，使教學(xué)達(dá)到事半功倍的效果。五、 教學(xué)進(jìn)度該課程教學(xué)總學(xué)時(shí)為56（含實(shí)驗(yàn)16學(xué)時(shí)）學(xué)時(shí)，3.5學(xué)分。教學(xué)安排按照一學(xué)期14周進(jìn)行，平均每周4學(xué)時(shí)。其中實(shí)驗(yàn)共安排8次，每次2學(xué)時(shí)，共16學(xué)時(shí)。 具體教學(xué)進(jìn)度安排詳見(jiàn)表1所示。表1 教學(xué)進(jìn)度計(jì)劃表教學(xué)內(nèi)容總學(xué)時(shí)其 中課外輔導(dǎo)/課外實(shí)踐備 注

7、課堂上機(jī)實(shí)驗(yàn)緒論222線性表8626棧4222隊(duì)列4222串4222數(shù)組與廣義表444樹(shù)與二叉樹(shù)8626圖8828查找8626內(nèi)部排序4222總計(jì)56401640六、 教學(xué)內(nèi)容重點(diǎn)與難點(diǎn)及解決辦法1 緒論（講授：2學(xué)時(shí)）教學(xué)重點(diǎn)：（1） 數(shù)據(jù)結(jié)構(gòu)、邏輯結(jié)構(gòu)、物理結(jié)構(gòu)、數(shù)據(jù)類(lèi)型、抽象數(shù)據(jù)類(lèi)型、算法、算法的時(shí)間復(fù)雜度和空間復(fù)雜度及其計(jì)算。（2） 算法的五要素、算法的書(shū)寫(xiě)規(guī)范。教學(xué)難點(diǎn)：抽象數(shù)據(jù)類(lèi)型。解決辦法：通過(guò)聯(lián)系實(shí)際，舉例說(shuō)明抽象數(shù)據(jù)類(lèi)型的內(nèi)涵，如：復(fù)數(shù)的抽象性及其在C或C+中的描述與實(shí)現(xiàn)。2 線性表（講授：6學(xué)時(shí)）教學(xué)重點(diǎn)：（1） 線性表的邏輯定義機(jī)器各種存儲(chǔ)結(jié)構(gòu)的描述方法。（2） 線性表基

8、于各種存儲(chǔ)結(jié)構(gòu)之上的基本操作的實(shí)現(xiàn)方法。（3） 利用線性表表示一元多項(xiàng)式并實(shí)現(xiàn)多項(xiàng)式的相關(guān)運(yùn)算。教學(xué)難點(diǎn)：線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的實(shí)現(xiàn)。解決辦法：利用電子課件詳細(xì)、動(dòng)態(tài)地講解鏈?zhǔn)浇Y(jié)構(gòu)的物理形式，并通過(guò)第一次實(shí)驗(yàn)上機(jī)練習(xí)加深對(duì)該存儲(chǔ)結(jié)構(gòu)的理解。3 棧和隊(duì)列（講授：4學(xué)時(shí)）教學(xué)重點(diǎn)：（1） 棧和隊(duì)列的邏輯結(jié)構(gòu)。（2） 棧和隊(duì)列的基本操作在靜態(tài)存儲(chǔ)結(jié)構(gòu)和動(dòng)態(tài)存儲(chǔ)結(jié)構(gòu)上的實(shí)現(xiàn)方法。（3） 棧和隊(duì)列在程序設(shè)計(jì)中的應(yīng)用（如表達(dá)式的求值、遞歸程序設(shè)計(jì)）。教學(xué)難點(diǎn)：棧的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的實(shí)現(xiàn)；隊(duì)列的順序存儲(chǔ)結(jié)構(gòu)（循環(huán)隊(duì)列）的實(shí)現(xiàn)。解決辦法：首先結(jié)合實(shí)際例子幫助學(xué)生充分理解邏輯棧的特點(diǎn)，如：手槍的子彈夾等。然后利用對(duì)

9、線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的理解進(jìn)一步加深學(xué)生理解鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)下的棧的實(shí)現(xiàn)方法。配合安排相應(yīng)的驗(yàn)證性實(shí)驗(yàn)以加深理解。首先結(jié)合實(shí)際例子幫助學(xué)生充分理解邏輯隊(duì)列的特點(diǎn)，如：裝羽毛球的圓筒盒子等。然后在利用電子課件形象地描述物理結(jié)構(gòu)的實(shí)現(xiàn)。配合安排相應(yīng)的驗(yàn)證性實(shí)驗(yàn)上機(jī)一次以加深理解。4 串（講授：2學(xué)時(shí)）教學(xué)重點(diǎn)：（1） 串的邏輯結(jié)構(gòu)及其三種存儲(chǔ)結(jié)構(gòu)。（2） 串的基本操作在靜態(tài)存儲(chǔ)結(jié)構(gòu)和堆結(jié)構(gòu)下的實(shí)現(xiàn)方法。教學(xué)難點(diǎn)：串的模式匹配算法的理解與實(shí)現(xiàn)。解決辦法：先利用比較簡(jiǎn)單的串的順序存儲(chǔ)結(jié)構(gòu)來(lái)討論最簡(jiǎn)單的模式匹配算法的原理及其實(shí)現(xiàn)，然后再由淺入深地討論其他效率較高的算法?？梢砸笠话阃瑢W(xué)僅掌握基本算法。利用課

10、余時(shí)間組織學(xué)生討論改進(jìn)算法。5 數(shù)組與廣義表（講授：4學(xué)時(shí)）教學(xué)重點(diǎn)：（1） 數(shù)組的邏輯結(jié)構(gòu)及存儲(chǔ)結(jié)構(gòu)。（2） 特殊矩陣和稀疏矩陣的壓縮存儲(chǔ)及其矩陣運(yùn)算的實(shí)現(xiàn)。（3） 廣義表的邏輯結(jié)構(gòu)及其存儲(chǔ)結(jié)構(gòu)。教學(xué)難點(diǎn)：特殊矩陣和稀疏矩陣的壓縮存儲(chǔ)的理解與實(shí)現(xiàn)。解決辦法：制作直觀而形象的電子課件，利用動(dòng)畫(huà)效果講解物理存儲(chǔ)結(jié)構(gòu)的原理，然后在用C或C+語(yǔ)言進(jìn)行物理結(jié)構(gòu)的描述。6 樹(shù)和二叉樹(shù)（講授：6學(xué)時(shí)）教學(xué)重點(diǎn)：（1） 樹(shù)的邏輯結(jié)構(gòu)與基本操作。（2） 二叉樹(shù)的定義、性質(zhì)與存儲(chǔ)結(jié)構(gòu)。（3） 遍歷二叉樹(shù)與線索二叉樹(shù)。（4） 樹(shù)的存儲(chǔ)結(jié)構(gòu)與樹(shù)的遍歷。（5） 哈夫曼樹(shù)及其應(yīng)用。教學(xué)難點(diǎn)：三種不同的遍歷二叉樹(shù)的遞歸和

11、非遞歸算法。解決辦法：重點(diǎn)講述一種（如中序遍歷）算法的遞歸算法思想和非遞歸算法思想，并引導(dǎo)學(xué)生編寫(xiě)相應(yīng)程序。然后舉一反三地講解其他兩種遍歷算法。配合安排驗(yàn)證性實(shí)驗(yàn)上機(jī)一次。7 圖（講授：8學(xué)時(shí)）教學(xué)重點(diǎn)：（1） 圖的定義與存儲(chǔ)結(jié)構(gòu)。（2） 圖的兩種遍歷策略。（3） 無(wú)向圖的邊通分量及最小生成樹(shù)。（4） 拓?fù)渑判蚺c關(guān)鍵路徑。（5） 求網(wǎng)絡(luò)中的最短路徑。教學(xué)難點(diǎn)：圖的定義與存儲(chǔ)結(jié)構(gòu)；圖的兩種遍歷策略。解決辦法：先重點(diǎn)講述圖的順序（數(shù)組）存儲(chǔ)方法的實(shí)現(xiàn)思想，然后再講述圖的鄰接表法的存儲(chǔ)方法；精講深度優(yōu)先遍歷算法思想及其實(shí)現(xiàn)方法；課后組織學(xué)生討論廣度優(yōu)先遍歷算法，并引導(dǎo)學(xué)生編寫(xiě)相應(yīng)程序，利用課余時(shí)間上

12、機(jī)實(shí)現(xiàn)之。8 查找（講授：6學(xué)時(shí)）教學(xué)重點(diǎn)：（1） 順序查找。（2） 折半查找。（3） 索引查找。（4） 二叉排序樹(shù)和二叉平衡樹(shù)的查找方法。（5） 哈希表的建立及其查找方法。（6） 各種查找方法的查找效率的分析。教學(xué)難點(diǎn)：哈希表的建立及其查找方法。解決辦法：結(jié)合實(shí)際例子先講述哈希表的存儲(chǔ)結(jié)構(gòu)及其沖突的一般解決方法。然后再展開(kāi)更深入的解決沖突問(wèn)題的常用算法。9 內(nèi)部排序（講授：2學(xué)時(shí)）教學(xué)重點(diǎn)：（1） 插入排序。（2） 快速排序。（3） 選擇排序。（4） 歸并排序。（5） 各種排序算法的時(shí)間復(fù)雜度分析與比較。教學(xué)難點(diǎn)：各種排序算法的時(shí)間復(fù)雜度分析與比較。解決辦法：以兩個(gè)較簡(jiǎn)單的排序算法為例（如：

13、插入排序和選擇排序）說(shuō)明排序算法效率分析及其比較的一般方法。并配合安排設(shè)計(jì)性實(shí)驗(yàn)一次。要求學(xué)生能根據(jù)一批數(shù)據(jù)建立幾種不同的數(shù)據(jù)結(jié)構(gòu)，采用不同的搜索或排序算法對(duì)這些數(shù)據(jù)進(jìn)行查找或排序，并對(duì)其進(jìn)行分析與比較。七、 實(shí)驗(yàn)教學(xué)實(shí)驗(yàn)教學(xué)共16學(xué)時(shí)，實(shí)驗(yàn)內(nèi)容及學(xué)時(shí)分配安排詳見(jiàn)表2所示。表2 實(shí)驗(yàn)教學(xué)安排表序號(hào)實(shí)驗(yàn)項(xiàng)目名稱(chēng)實(shí)驗(yàn)類(lèi)型學(xué)時(shí)分配必開(kāi)/選開(kāi)分組要求1線性表設(shè)計(jì)性實(shí)驗(yàn)2H必開(kāi)1人/組2棧設(shè)計(jì)性實(shí)驗(yàn)2H必開(kāi)1人/組3隊(duì)列設(shè)計(jì)性實(shí)驗(yàn)2H必開(kāi)1人/組4串驗(yàn)證性實(shí)驗(yàn)2H必開(kāi)1人/組5二叉樹(shù)設(shè)計(jì)性實(shí)驗(yàn)2H必開(kāi)1人/組6圖驗(yàn)證性實(shí)驗(yàn)2H必開(kāi)1人/組7查找驗(yàn)證性實(shí)驗(yàn)2H必開(kāi)1人/組8排序驗(yàn)證性實(shí)驗(yàn)2H必開(kāi)1人/組具體實(shí)驗(yàn)內(nèi)容與要求詳見(jiàn)201 -201 第 學(xué)期計(jì)算機(jī)軟件工程專(zhuān)業(yè)數(shù)據(jù)結(jié)構(gòu)A教學(xué)日歷。 八、 教學(xué)輔導(dǎo)、作業(yè)、考試關(guān)于教學(xué)輔導(dǎo)：每周安排一次課外答疑，答疑地點(diǎn)與時(shí)間另行通知。 關(guān)于作業(yè)：作業(yè)分兩部分。第一部分主要是在每次上實(shí)驗(yàn)課的時(shí)候根據(jù)具體的實(shí)驗(yàn)內(nèi)容對(duì)學(xué)生進(jìn)行考核，學(xué)生以上機(jī)實(shí)驗(yàn)報(bào)告的形式提交上機(jī)實(shí)驗(yàn)報(bào)告；第二部分主要是針對(duì)每次理論課授課的內(nèi)容在課堂上布置的作業(yè)，教師每次授課時(shí)將利用課堂的最后5分鐘針對(duì)本次授課內(nèi)容布置作業(yè)，學(xué)生在課后利用課余時(shí)間完成作業(yè)。 關(guān)于考試：本課程屬考試課程。考試方式采取閉卷筆試的形式，其考試成績(jī)占學(xué)期總成績(jī)的80%；平時(shí)成績(jī)（作業(yè)與上機(jī)）占學(xué)期總成績(jī)的20%。九