數(shù)據(jù)結(jié)構(gòu)與問(wèn)題求解 課程教學(xué)大綱

數(shù)據(jù)結(jié)構(gòu)與問(wèn)題求解課程教學(xué)大綱01基本信息課程名稱：數(shù)據(jù)結(jié)構(gòu)與問(wèn)題求解

英文名稱：DataStructureandProblemSolving課程類別：學(xué)科基礎(chǔ)教育課程課程性質(zhì)：必修學(xué)分：5總學(xué)時(shí)：80其中，講授44學(xué)時(shí)，上機(jī)24學(xué)時(shí)，研討12學(xué)時(shí)適用專業(yè)：計(jì)算機(jī)科學(xué)與技術(shù)、軟件工程、網(wǎng)絡(luò)工程、大數(shù)據(jù)、人工智能、信息與計(jì)算科學(xué)等先修課程：程序設(shè)計(jì)與問(wèn)題求解后繼課程：算法設(shè)計(jì)與問(wèn)題求解02課程簡(jiǎn)介《數(shù)據(jù)結(jié)構(gòu)與問(wèn)題求解》是信息類專業(yè)基礎(chǔ)課程，其目標(biāo)是要求學(xué)生理解和掌握面向?qū)ο蟪绦蛟O(shè)計(jì)（C++）基礎(chǔ)知識(shí)和編程方法、數(shù)據(jù)結(jié)構(gòu)的相關(guān)知識(shí)。討論各種數(shù)據(jù)的抽象表示、實(shí)現(xiàn)方法、處理數(shù)據(jù)的算法設(shè)計(jì)以及對(duì)算法性能的分析。使學(xué)生能夠運(yùn)用面向?qū)ο蟪绦蛟O(shè)計(jì)的方法開(kāi)發(fā)應(yīng)用程序，理解使用面向?qū)ο蟮姆绞饺绾文芴岣叱绦虻目删S護(hù)性。本課程主要通過(guò)案例學(xué)習(xí)和實(shí)訓(xùn)練習(xí)，初步掌握使用經(jīng)典模型解決實(shí)際問(wèn)題的方法；通過(guò)設(shè)置預(yù)習(xí)和研討環(huán)節(jié)，引導(dǎo)學(xué)生自主學(xué)習(xí)、對(duì)數(shù)據(jù)結(jié)構(gòu)進(jìn)行深入的探討，分析不同解決方案的優(yōu)劣，具備一定的復(fù)雜工程問(wèn)題求解能力。03課程目標(biāo)1、課程思政教學(xué)目標(biāo)：通過(guò)本課程的學(xué)習(xí)，使學(xué)生學(xué)習(xí)溝通、組織、團(tuán)隊(duì)合作的社會(huì)能力，培養(yǎng)學(xué)生安全、規(guī)范的專業(yè)素養(yǎng)以及一絲不茍的工匠精神；了解計(jì)算機(jī)軟件從業(yè)人員應(yīng)當(dāng)具備的職業(yè)道德守則，為進(jìn)軍軟件行業(yè)做準(zhǔn)備；理解并敬重工匠精神，在學(xué)習(xí)中努力發(fā)揚(yáng)工匠精神。幫助學(xué)生了解新時(shí)代國(guó)家對(duì)軟件行業(yè)從業(yè)者的要求；通過(guò)軟件行業(yè)發(fā)展前景，引發(fā)學(xué)生對(duì)未來(lái)的職業(yè)愿景，激發(fā)學(xué)生對(duì)社會(huì)主義核心價(jià)值觀的認(rèn)同感。通過(guò)課程思政教學(xué)，培養(yǎng)愛(ài)國(guó)、愛(ài)黨、具有良好的職業(yè)道德和高度職業(yè)責(zé)任感的專業(yè)人才。2、課程教學(xué)總目標(biāo)：通過(guò)本課程的學(xué)習(xí)，使學(xué)生能夠運(yùn)用C++面向?qū)ο蟪绦蛟O(shè)計(jì)的方法，能初步的理解和能夠運(yùn)用面向?qū)ο笾兄匾乃膫€(gè)概念--抽象、封裝、繼承和多態(tài)，能理解面向?qū)ο蟪绦蛟O(shè)計(jì)的優(yōu)勢(shì)，能使用面向?qū)ο蟮乃枷胪瓿沙绦虻脑O(shè)計(jì)，能對(duì)類進(jìn)行拓展和維護(hù)。以堆棧和隊(duì)列為例，進(jìn)一步了解線性表的應(yīng)用范疇和規(guī)約，能以樹(shù)和圖為例了解非線性結(jié)構(gòu)的數(shù)據(jù)結(jié)構(gòu)的應(yīng)用范疇和規(guī)約。能使用經(jīng)典的數(shù)據(jù)結(jié)構(gòu)解決實(shí)際問(wèn)題。通過(guò)進(jìn)一步學(xué)習(xí)數(shù)據(jù)的查詢算法和排序算法，能比較使用不同方案實(shí)現(xiàn)同一功能的效率優(yōu)劣。能通過(guò)查閱相關(guān)技術(shù)文檔、查閱文獻(xiàn)或者通過(guò)與老師同學(xué)討論，解決在程序設(shè)計(jì)過(guò)程中遇到的問(wèn)題。能夠通過(guò)閱讀老師提供的文獻(xiàn)、觀看老師提供的線上資源或者自主學(xué)習(xí)，能夠運(yùn)用一定的課堂外的拓展知識(shí)，并能使用拓展知識(shí)解決實(shí)際問(wèn)題。3、課程目標(biāo)與學(xué)生能力和素質(zhì)培養(yǎng)的關(guān)系：課程思政目標(biāo)的實(shí)施有利于培養(yǎng)學(xué)生愛(ài)國(guó)精神、職業(yè)責(zé)任感，團(tuán)隊(duì)合作、組織、溝通等社會(huì)能力。課程教學(xué)目標(biāo)的實(shí)施有利于培養(yǎng)學(xué)生對(duì)復(fù)雜問(wèn)題的分析判斷能力，培養(yǎng)學(xué)生對(duì)復(fù)雜問(wèn)題的求解和創(chuàng)新思維，培養(yǎng)學(xué)生自主學(xué)習(xí)、拓展知識(shí)的意識(shí)。4、畢業(yè)要求—課程目標(biāo)關(guān)系（OBE結(jié)果導(dǎo)向）考慮本課程與專業(yè)畢業(yè)要求的支撐關(guān)系，制定本課程學(xué)習(xí)目標(biāo)。通過(guò)本課程的教學(xué)，達(dá)到以下課程目標(biāo)，見(jiàn)表1：■

表1畢業(yè)要求-課程目標(biāo)關(guān)系表04課程內(nèi)容及學(xué)時(shí)分配（一）C++語(yǔ)言基本知識(shí)（2學(xué)時(shí)）學(xué)習(xí)C++基本語(yǔ)法，包括輸入/輸出、常量、命名空間、內(nèi)存分配與回收、引用等基本語(yǔ)法。1、基本要求（1）掌握輸入輸出cin/cout（2）掌握const常量的使用（3）學(xué)會(huì)使用命名空間（4）掌握使用new與delete進(jìn)行內(nèi)存的分配與回收（5）理解引用、內(nèi)聯(lián)函數(shù)等知識(shí)點(diǎn)。2、重點(diǎn)、難點(diǎn)重點(diǎn)：輸入輸出格式控制、new/delete內(nèi)存分配與回收難點(diǎn)：new/delete、引用。3、小組討論問(wèn)題1：C語(yǔ)言和C++語(yǔ)言的比較。問(wèn)題2：C++的引用模式和C語(yǔ)言的指針模式有什么區(qū)別和聯(lián)系。問(wèn)題3：什么場(chǎng)合使用內(nèi)聯(lián)函數(shù)。問(wèn)題4：C++的輸入輸出語(yǔ)句的特點(diǎn)。組織方式：小組內(nèi)進(jìn)行討論，每組推選兩位同學(xué)講解和演示老師指定的習(xí)題，進(jìn)行講解的同學(xué)由老師評(píng)講解分。研討完畢后所有同學(xué)上交研討作業(yè)，按正確率和研討記錄進(jìn)行評(píng)分。4、說(shuō)明：本部分基本概念較多，是C++編程的基礎(chǔ)。本章的教學(xué)支撐“畢業(yè)要求1.2”，使得學(xué)生開(kāi)始掌握軟件設(shè)計(jì)的理論與方法，運(yùn)用C++語(yǔ)言進(jìn)行軟件系統(tǒng)開(kāi)發(fā)的能力。（二）類的定義（4學(xué)時(shí)）了解基本的面向?qū)ο蟪绦蛟O(shè)計(jì)思維、初步培養(yǎng)學(xué)生抽象思維能力，并在抽象結(jié)果的基礎(chǔ)上進(jìn)行類的定義。掌握類定義中的基本元素，包括構(gòu)造函數(shù)、成員函數(shù)、析構(gòu)函數(shù)、構(gòu)造函數(shù)重載、默認(rèn)構(gòu)造函數(shù)等語(yǔ)法。1、基本要求（1）類與對(duì)象的基本概念（2）類的定義（3）成員函數(shù)（4）構(gòu)造函數(shù)（5）析構(gòu)函數(shù)（6）帶參數(shù)的構(gòu)造函數(shù)與構(gòu)造函數(shù)重載（7）默認(rèn)構(gòu)造函數(shù)（8）成員初始化列表（9）this指針（10）應(yīng)用：棧（Stack）類、隊(duì)列（Queue）類、鏈表（LinkList）分析與實(shí)現(xiàn)2、重點(diǎn)、難點(diǎn)重點(diǎn)：構(gòu)造函數(shù)、析構(gòu)函數(shù)、this指針、構(gòu)造函數(shù)重載、成員初始化列表難點(diǎn)：構(gòu)造函數(shù)重載、成員初始化列表3、小組討論問(wèn)題1：大小寫(xiě)的轉(zhuǎn)換。問(wèn)題2：不同數(shù)據(jù)類型的轉(zhuǎn)換。問(wèn)題3：實(shí)際問(wèn)題的計(jì)算機(jī)表示。問(wèn)題4：數(shù)學(xué)公式在計(jì)算機(jī)中的實(shí)現(xiàn)。組織方式：小組內(nèi)進(jìn)行討論，每組推選兩位同學(xué)講解和演示老師指定的習(xí)題，進(jìn)行講解的同學(xué)由老師評(píng)講解分。研討完畢后所有同學(xué)上交研討作業(yè)，按正確率和研討記錄進(jìn)行評(píng)分。4、說(shuō)明：本部分是類的定義的基礎(chǔ)，需要熟練掌握。本章的教學(xué)支撐“畢業(yè)要求4.1”，通過(guò)為學(xué)生提供數(shù)據(jù)輸入輸出、數(shù)據(jù)存儲(chǔ)等技術(shù)文檔，使得學(xué)生能掌握數(shù)據(jù)的輸入輸出和處理方法。通過(guò)案例學(xué)習(xí)掌握對(duì)實(shí)際問(wèn)題進(jìn)行抽象，設(shè)計(jì)出合適的類并進(jìn)行封裝的方法。（三）類的繼承（4學(xué)時(shí)）在基本抽象能力的基礎(chǔ)之上培養(yǎng)學(xué)生發(fā)現(xiàn)類之間的繼承關(guān)系的能力，提高程序代碼的重用性，消除代碼冗余。掌握類的繼承的語(yǔ)法、訪問(wèn)控制規(guī)則、派生類構(gòu)造函數(shù)的定義、調(diào)用次序等。1、基本要求（1）繼承與派生的概念（2）繼承語(yǔ)法（3）訪問(wèn)控制規(guī)則（4）派生類構(gòu)造函數(shù)定義（5）派生類構(gòu)造函數(shù)與析構(gòu)函數(shù)調(diào)用次序（6）構(gòu)造函數(shù)與析構(gòu)函數(shù)構(gòu)造規(guī)則（7）應(yīng)用：隊(duì)列與雙向隊(duì)列、鏈表與雙向鏈表2、重點(diǎn)、難點(diǎn)重點(diǎn)：繼承語(yǔ)法、訪問(wèn)控制規(guī)則、構(gòu)造函數(shù)與析構(gòu)調(diào)用次序難點(diǎn)：訪問(wèn)控制規(guī)則、構(gòu)造函數(shù)與析構(gòu)調(diào)用次序3、小組討論問(wèn)題1：哪些場(chǎng)景會(huì)使用到類的繼承。問(wèn)題2：父類和子類中分別設(shè)計(jì)哪些類的成員。問(wèn)題3：堆棧類的特點(diǎn)是什么？能夠用它解決哪些實(shí)際問(wèn)題。問(wèn)題4：隊(duì)列類的特點(diǎn)是什么？能夠用它解決哪些實(shí)際問(wèn)題。組織方式：小組內(nèi)進(jìn)行討論，每組推選兩位同學(xué)講解和演示老師指定的習(xí)題，進(jìn)行講解的同學(xué)由老師評(píng)講解分。研討完畢后所有同學(xué)上交研討作業(yè)，按正確率和研討記錄進(jìn)行評(píng)分。4、說(shuō)明：本部分是類的繼承，需要培養(yǎng)較好的抽象能力、并應(yīng)用繼承的語(yǔ)法加以實(shí)現(xiàn)的能力。本章的教學(xué)支撐“畢業(yè)要求1.2”，使得學(xué)生開(kāi)始掌握面向?qū)ο蟪绦蛟O(shè)計(jì)的理論與方法，能夠運(yùn)用C++語(yǔ)言設(shè)計(jì)出具有繼承關(guān)系的類，能進(jìn)行包含多個(gè)類的較為復(fù)雜的程序開(kāi)發(fā)，提高軟件系統(tǒng)開(kāi)發(fā)的能力。（四）多態(tài)（4學(xué)時(shí)）C++的多態(tài)分為兩種：靜態(tài)多態(tài)（重載，模板）和動(dòng)態(tài)多態(tài)（覆蓋，虛函數(shù)實(shí)現(xiàn)），多態(tài)是面向?qū)ο缶幊讨凶钪匾沫h(huán)節(jié)，需要培養(yǎng)學(xué)生較高的抽象能力，特別是應(yīng)用純虛函數(shù)進(jìn)行抽象、編程實(shí)現(xiàn)的能力。1、基本要求（1）多態(tài)性概念（2）運(yùn)算符重載（3）虛函數(shù)意義（4）虛函數(shù)定義（5）虛析構(gòu)函數(shù)（6）純虛函數(shù)抽象類（7）應(yīng)用：幾何圖形求面積2、重點(diǎn)、難點(diǎn)重點(diǎn)：多態(tài)性概念、運(yùn)算符重載、虛函數(shù)、純虛函數(shù)、抽象類難點(diǎn)：運(yùn)算符重載、純虛函數(shù)與抽象類3、說(shuō)明：本部分是面向?qū)ο缶幊讨凶钪匾沫h(huán)節(jié)，需要深入理解、反復(fù)實(shí)踐，提高抽象能力。4、小組討論問(wèn)題1：多態(tài)能夠運(yùn)用于哪些場(chǎng)景。問(wèn)題2：運(yùn)算符重載能運(yùn)用于哪些場(chǎng)景，對(duì)軟件的可維護(hù)性有何意義。問(wèn)題3：在設(shè)計(jì)程序中能否使用多繼承。組織方式：小組內(nèi)進(jìn)行討論，每組推選兩位同學(xué)講解和演示老師指定的習(xí)題，進(jìn)行講解的同學(xué)由老師評(píng)講解分。研討完畢后所有同學(xué)上交研討作業(yè)，按正確率和研討記錄進(jìn)行評(píng)分。本章的教學(xué)支撐“畢業(yè)要求1.2”，使得學(xué)生開(kāi)始掌握軟件設(shè)計(jì)的理論與方法，運(yùn)用C++語(yǔ)言實(shí)現(xiàn)多態(tài)，提高軟件系統(tǒng)開(kāi)發(fā)的能力。同時(shí)，對(duì)于復(fù)雜的工程問(wèn)題需要設(shè)計(jì)復(fù)雜的類圖、類之間的關(guān)系圖，能夠通過(guò)查詢資料完成類的設(shè)計(jì)，可以支撐“支撐畢業(yè)要求4.1”。（五）模板與容器（2學(xué)時(shí)）模板（template）是C++語(yǔ)言的一項(xiàng)重要技術(shù)，代碼重用的重要機(jī)制，是泛型技術(shù)的基礎(chǔ)。STL即標(biāo)準(zhǔn)模板，是基于模板技術(shù)的一個(gè)庫(kù)，提供了模板化的通用數(shù)據(jù)結(jié)構(gòu)、類和算法。STL的核心內(nèi)容包括容器、迭代器和算法。1、基本要求（1）模板概念（2）函數(shù)模板（3）類模板（4）容器（5）迭代器（6）關(guān)聯(lián)式容器（7）算法2、重點(diǎn)、難點(diǎn)重點(diǎn)：函數(shù)模板、類模板、容器、迭代器、關(guān)聯(lián)式容器難點(diǎn)：類模板、迭代器、關(guān)聯(lián)式容器3、小組討論問(wèn)題1：使用STL重新完成約瑟夫環(huán)問(wèn)題，和前面的解題方式進(jìn)行比較。問(wèn)題2：觀察STL中堆棧類和隊(duì)列類的設(shè)計(jì)，從中可以學(xué)習(xí)到哪些設(shè)計(jì)思路。問(wèn)題3：使用模板的意義有哪些。組織方式：小組內(nèi)進(jìn)行討論，每組推選兩位同學(xué)講解和演示老師指定的習(xí)題，進(jìn)行講解的同學(xué)由老師評(píng)講解分。研討完畢后所有同學(xué)上交研討作業(yè)，按正確率和研討記錄進(jìn)行評(píng)分。4、說(shuō)明：本部分主要講解STL標(biāo)準(zhǔn)容器，需要熟練掌握。本章的教學(xué)支撐“畢業(yè)要求12.1”，通過(guò)為學(xué)生提供STL的拓展學(xué)習(xí)資料，STL的技術(shù)文檔，以及STL的案例程序，使學(xué)生能自主學(xué)習(xí)STL的拓展知識(shí)，能夠根據(jù)明確的需求，調(diào)用標(biāo)準(zhǔn)庫(kù)，實(shí)現(xiàn)針對(duì)計(jì)算機(jī)相關(guān)復(fù)雜工程問(wèn)題的算法。

(六)壓縮矩陣與字符串（4學(xué)時(shí)）掌握特殊矩陣、稀疏矩陣的壓縮方法，設(shè)計(jì)良好的存儲(chǔ)結(jié)構(gòu)來(lái)降低內(nèi)存消耗，理解字符串匹配算法KMP，掌握KMP算法中轉(zhuǎn)移函數(shù)next的計(jì)算方法。1、基本要求（1）特殊矩陣的壓縮存儲(chǔ)（2）稀疏矩陣的壓縮存儲(chǔ)（3）字符串的存儲(chǔ)（4）字符串的轉(zhuǎn)移函數(shù)（5）KMP算法2、重點(diǎn)、難點(diǎn)重點(diǎn)：稀疏矩陣、字符串的轉(zhuǎn)移函數(shù)、KMP算法難點(diǎn)：稀疏矩陣、字符串轉(zhuǎn)移函數(shù)next3、小組討論問(wèn)題1：在稀疏矩陣壓縮后，能否完整的還原，探討哪些壓縮方式是不能還原的。問(wèn)題2：稀疏矩陣的計(jì)算是否需要還原，哪些情況下還原效率更高。問(wèn)題3：kmp算法是如何提高模式識(shí)別的效率。對(duì)算法的效率提高有哪些啟發(fā)。問(wèn)題4：kmp算法還能應(yīng)用與哪些場(chǎng)景。組織方式：小組內(nèi)進(jìn)行討論，每組推選兩位同學(xué)講解和演示老師指定的習(xí)題，進(jìn)行講解的同學(xué)由老師評(píng)講解分。研討完畢后所有同學(xué)上交研討作業(yè)，按正確率和研討記錄進(jìn)行評(píng)分。4、說(shuō)明：本部分介紹矩陣壓縮、字符串匹配，需要掌握基本的矩陣壓縮方法和字符串匹配算法。本章的教學(xué)支撐“畢業(yè)要求1.2”，使得學(xué)生能夠掌握運(yùn)用數(shù)學(xué)方法對(duì)矩陣進(jìn)行壓縮存儲(chǔ)，能夠分析KMP算法是如何提高程序效率的。（七）樹(shù)與二叉樹(shù)（10學(xué)時(shí)）掌握樹(shù)的概念、特別是二叉樹(shù)的存儲(chǔ)和基本算法。掌握二叉樹(shù)的基本性質(zhì)、遍歷訪問(wèn)操作、非遞歸遍歷方法和哈夫曼樹(shù)及編碼。1、基本要求（1）樹(shù)的邏輯結(jié)構(gòu)（2）樹(shù)的存儲(chǔ)結(jié)構(gòu)（3）二叉樹(shù)的邏輯結(jié)構(gòu)（4）二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)（5）二叉樹(shù)遍歷的非遞歸算法（6）樹(shù)、森林與二叉樹(shù)的轉(zhuǎn)換（7）哈夫曼樹(shù)和哈夫曼編碼2、重點(diǎn)、難點(diǎn)重點(diǎn)：二叉樹(shù)的邏輯結(jié)構(gòu)、二叉樹(shù)的非遞歸算法、哈夫曼樹(shù)和哈夫曼編碼難點(diǎn)：二叉樹(shù)的非遞歸算法、哈夫曼樹(shù)及編碼3、小組討論問(wèn)題1：樹(shù)的結(jié)構(gòu)能應(yīng)用與哪些場(chǎng)景。問(wèn)題2：各種樹(shù)的存儲(chǔ)方式有哪些，分別適合于存儲(chǔ)什么類型的數(shù)據(jù)。問(wèn)題3：哈夫曼編碼的編碼方式是否有多種，效率是否一致。問(wèn)題4：哈夫曼編碼可以運(yùn)用于哪些場(chǎng)合。組織方式：小組內(nèi)進(jìn)行討論，每組推選兩位同學(xué)講解和演示老師指定的習(xí)題，進(jìn)行講解的同學(xué)由老師評(píng)講解分。研討完畢后所有同學(xué)上交研討作業(yè)，按正確率和研討記錄進(jìn)行評(píng)分。4、說(shuō)明：本部分介紹樹(shù)與二叉樹(shù)，需要深入掌握二叉樹(shù)的主要操作。本章的教學(xué)支撐“畢業(yè)要求1.2”，通過(guò)將哈夫曼樹(shù)應(yīng)用于哈夫曼編碼問(wèn)題，根據(jù)具體的問(wèn)題確定葉子結(jié)點(diǎn)的權(quán)值計(jì)算方法，培養(yǎng)學(xué)生的復(fù)雜工程問(wèn)題分析、改進(jìn)的能力。同時(shí)本章的教學(xué)支撐“畢業(yè)要求4.1”，使得學(xué)生能掌握軟件設(shè)計(jì)的理論與方法，運(yùn)用C++語(yǔ)言進(jìn)行軟件系統(tǒng)開(kāi)發(fā)的能力。（八）圖（10學(xué)時(shí)）掌握?qǐng)D的基本概念、基本實(shí)現(xiàn)，以及對(duì)圖的基本操作，包括深度遍歷、廣度遍歷、最小生成樹(shù)、最短路徑、關(guān)鍵路徑等。具備應(yīng)用這些知識(shí)求解實(shí)際問(wèn)題的能力。1、基本要求（1）圖的邏輯結(jié)構(gòu)（2）圖的存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)（3）圖的遍歷（4）最小生成樹(shù)（5）最短路徑（6）有向無(wú)環(huán)圖及其應(yīng)用2、重點(diǎn)、難點(diǎn)重點(diǎn)：圖的存儲(chǔ)及實(shí)現(xiàn)、圖的遍歷、最小生成樹(shù)、最短路徑、有向無(wú)環(huán)圖。難點(diǎn)：最小生成樹(shù)、最短路徑、有向無(wú)環(huán)圖3、小組討論問(wèn)題1：圖的遍歷可以應(yīng)用于哪些場(chǎng)景。問(wèn)題2：最小生成樹(shù)可以應(yīng)用于哪些場(chǎng)景。問(wèn)題3：最短路徑可以應(yīng)用于哪些場(chǎng)景。問(wèn)題4：如何判斷圖中是否存在環(huán)。問(wèn)題5：關(guān)鍵路徑是否存在多條？組織方式：小組內(nèi)進(jìn)行討論，每組推選兩位同學(xué)講解和演示老師指定的習(xí)題，進(jìn)行講解的同學(xué)由老師評(píng)講解分。研討完畢后所有同學(xué)上交研討作業(yè)，按正確率和研討記錄進(jìn)行評(píng)分。4、說(shuō)明：本章的教學(xué)支撐“畢業(yè)要求1.2”，通過(guò)將復(fù)雜的工程問(wèn)題抽象為圖的問(wèn)題，來(lái)培養(yǎng)學(xué)生應(yīng)用數(shù)據(jù)結(jié)構(gòu)模型的能力。本章的教學(xué)支撐“畢業(yè)要求4.1”，使得學(xué)生能掌握軟件設(shè)計(jì)的理論與方法，運(yùn)用C++語(yǔ)言進(jìn)行軟件系統(tǒng)開(kāi)發(fā)的能力。（九）排序與查找（8學(xué)時(shí)）掌握查找的主要方法，二叉排序樹(shù)、平衡二叉樹(shù)、散列技術(shù)等；掌握基本的排序算法的實(shí)現(xiàn)及性能，能夠針對(duì)問(wèn)題選擇合適的算法。1、基本要求（1）查找概述（2）二叉排序樹(shù)（3）平衡二叉樹(shù)（4）散列表的查找技術(shù)（5）直接插入排序（6）希爾排序（7）快速排序（8）堆排序（9）歸并排序2、重點(diǎn)、難點(diǎn)重點(diǎn)：二叉排序樹(shù)、平衡二叉樹(shù)、散列表的查找技術(shù)、快速排序、堆排序、歸并排序難點(diǎn)：平衡二叉樹(shù)、散列表的查找技術(shù)、快速排序、堆排序3、說(shuō)明：高效的查找方法和排序方法是解決一般工程問(wèn)題的常用方法，需要熟練掌握。4、小組討論問(wèn)題1：如何判斷二叉樹(shù)是否是平衡的。問(wèn)題2：二叉排序樹(shù)是否可以用于排序，如何實(shí)現(xiàn)。問(wèn)題3：哈希函數(shù)的設(shè)計(jì)方法有哪些，以學(xué)生學(xué)號(hào)為關(guān)鍵字可以如何設(shè)計(jì)哈希函數(shù)。問(wèn)題4：比較各種排序算法的效率。組織方式：小組內(nèi)進(jìn)行討論，每組推選兩位同學(xué)講解和演示老師指定的習(xí)題，進(jìn)行講解的同學(xué)由老師評(píng)講解分。研討完畢后所有同學(xué)上交研討作業(yè)，按正確率和研討記錄進(jìn)行評(píng)分。4、說(shuō)明本章的教學(xué)支撐“畢業(yè)要求12.1”，通過(guò)為學(xué)生提供拓展學(xué)習(xí)資料，使得學(xué)生能自主掌握二叉排序樹(shù)平衡的實(shí)現(xiàn)算法的思想，能比較多種哈希函數(shù)的設(shè)計(jì)方法適用于那些場(chǎng)景，培養(yǎng)學(xué)生運(yùn)用C++語(yǔ)言進(jìn)行軟件系統(tǒng)開(kāi)發(fā)的能力。另外，通過(guò)培養(yǎng)學(xué)生對(duì)比學(xué)習(xí)不同的查找、排序算法，理解不同算法的優(yōu)缺點(diǎn)，為解決復(fù)雜軟件工程問(wèn)題分析打基礎(chǔ)。（十）索引技術(shù)（2學(xué)時(shí)）掌握基本的索引技術(shù)，包括靜態(tài)索引技術(shù)、動(dòng)態(tài)索引技術(shù)。1、基本要求（1）靜態(tài)索引（2）B-樹(shù)（3）B+樹(shù)（4）Trie樹(shù)（5）哈希索引2、重點(diǎn)、難點(diǎn)重點(diǎn)：B-樹(shù)、B+樹(shù)、哈希索引難點(diǎn)：B-樹(shù)、B+樹(shù)、哈希索引本課程內(nèi)容、建議學(xué)時(shí)以及知識(shí)單元與課程目標(biāo)支撐關(guān)系如表2所示。■

表2

課程內(nèi)容及學(xué)時(shí)分配05教學(xué)方法及要求1、教學(xué)方法要求：要求任課教師具有計(jì)算機(jī)科學(xué)與技術(shù)專業(yè)、軟件工程、信息技術(shù)等背景；教學(xué)大綱的基本內(nèi)容要認(rèn)真執(zhí)行，根據(jù)課程目標(biāo)、教學(xué)計(jì)劃和所選教材在深度上可做恰當(dāng)處理，整個(gè)教學(xué)活動(dòng)由理論課教學(xué)+研討上機(jī)課教學(xué)完成，二者是一個(gè)有機(jī)整體。在教學(xué)開(kāi)始之前，教師需要制定詳細(xì)的教學(xué)計(jì)劃。教學(xué)計(jì)劃應(yīng)該根據(jù)學(xué)生的實(shí)際情況進(jìn)行調(diào)整和優(yōu)化。為了使學(xué)生更好地理解和掌握程序設(shè)計(jì)的知識(shí)和技能，教師需要準(zhǔn)備豐富的教學(xué)資源。這包括教材、教案、PPT、案例、練習(xí)題等。教師需要搭建適合學(xué)生實(shí)驗(yàn)和練習(xí)的環(huán)境。這包括編程環(huán)境、調(diào)試工具、測(cè)試數(shù)據(jù)等。在教學(xué)開(kāi)始之前，教師需要了解學(xué)生的學(xué)習(xí)情況、興趣愛(ài)好、學(xué)習(xí)習(xí)慣等方面的信息。這有助于教師更好地制定教學(xué)計(jì)劃和教學(xué)資源，以及更好地指導(dǎo)學(xué)生掌握編程知識(shí)和技能。在理論教學(xué)時(shí)，以課堂教學(xué)為主，采用線上+線下混合式教學(xué)，結(jié)合多媒體和網(wǎng)絡(luò)等多種教學(xué)手段，增加教學(xué)內(nèi)容的信息量，增強(qiáng)教學(xué)的互動(dòng)性；注重聯(lián)系實(shí)際，介紹數(shù)據(jù)結(jié)構(gòu)相關(guān)算法的典型應(yīng)用實(shí)例，幫助學(xué)生掌握基本求解方法；利用OJ平臺(tái)訓(xùn)練學(xué)生的編程能力。2、課程思政教學(xué)方法及要求：在數(shù)據(jù)結(jié)構(gòu)相關(guān)算法介紹中引入科學(xué)人物、新聞、事件等，加深對(duì)中國(guó)計(jì)算機(jī)算法研究和應(yīng)用的發(fā)展現(xiàn)狀的認(rèn)識(shí)；運(yùn)用案例式、討論式教學(xué)方法加深學(xué)生對(duì)程序設(shè)計(jì)和軟件開(kāi)發(fā)的國(guó)家標(biāo)準(zhǔn)、法律法規(guī)的認(rèn)識(shí)；通過(guò)課程分組實(shí)驗(yàn)，培養(yǎng)學(xué)生的溝通、組織、團(tuán)隊(duì)合作的能力。引導(dǎo)學(xué)生明確：建設(shè)網(wǎng)絡(luò)強(qiáng)國(guó)，不僅僅是靠網(wǎng)絡(luò)技術(shù)，還要有軟件技術(shù)等其他各類技術(shù)的支撐。引導(dǎo)學(xué)生作為軟件技術(shù)專業(yè)的一員，應(yīng)更加明晰專業(yè)人才的培養(yǎng)目標(biāo)，更加明確專業(yè)領(lǐng)域內(nèi)工作崗位和工作內(nèi)容的社會(huì)價(jià)值，自覺(jué)樹(shù)立遠(yuǎn)大職業(yè)理想，將職業(yè)生涯、職業(yè)發(fā)展脈絡(luò)與國(guó)家發(fā)展的歷史進(jìn)程融合起來(lái)。06重點(diǎn)與難點(diǎn)1、重點(diǎn)：構(gòu)造函數(shù)及成員初始化列表、繼承語(yǔ)法、純虛函數(shù)與抽象類、函數(shù)模板與類模板、稀疏矩陣、KMP算法、二叉樹(shù)的邏輯結(jié)構(gòu)、二叉樹(shù)的遞歸算法、圖的遍歷、有向無(wú)環(huán)圖、二叉排序樹(shù)、散列表的查找技術(shù)、歸并排序。2、難點(diǎn)：構(gòu)造函數(shù)重載、訪問(wèn)控制規(guī)則、運(yùn)算符重載、迭代器與關(guān)聯(lián)式容器、字符串轉(zhuǎn)移函數(shù)next、二叉樹(shù)的非遞歸算法、哈夫曼樹(shù)及編碼、最小生成樹(shù)、最短路徑、平衡二叉樹(shù)、快速排序、堆排序。07學(xué)習(xí)要求課堂回答問(wèn)題及討論要求：運(yùn)用相關(guān)知識(shí)對(duì)問(wèn)題進(jìn)行多人討論，提出正確解決方案。作業(yè)要求：每章提交一次研討作業(yè)，能夠熟練掌握鏈表、隊(duì)列、棧、樹(shù)、圖等知識(shí)，且針對(duì)問(wèn)題進(jìn)行建模并求解。課外自主學(xué)習(xí)要求：每章提交一次預(yù)習(xí)作業(yè)，對(duì)課程內(nèi)容進(jìn)行預(yù)習(xí)并完成相關(guān)練習(xí)?？荚囈螅簷C(jī)試考試。題型為：編程題。針對(duì)所有知識(shí)點(diǎn)進(jìn)行綜合類程序設(shè)計(jì)考核。08考核內(nèi)容及考核方式1、考核內(nèi)容及評(píng)價(jià)依據(jù)本課程考核內(nèi)容、建議評(píng)價(jià)依據(jù)以及與課程目標(biāo)對(duì)應(yīng)關(guān)系如表3所示?！?/p>

表3課程目標(biāo)-考核方式關(guān)系表2、成績(jī)?cè)u(píng)定最終成績(jī)由平時(shí)成績(jī)、期末成績(jī)組合而成。期末考試以O(shè)J系統(tǒng)評(píng)判結(jié)果來(lái)考核。各部分所占比例如下：平時(shí)作業(yè)成績(jī)：50%。預(yù)習(xí)作業(yè)占總成績(jī)20%，每周進(jìn)行一次主題研討，占總成績(jī)的30%?？荚嚦煽?jī)：50%。主要考核程序設(shè)計(jì)、算法與數(shù)據(jù)結(jié)構(gòu)知識(shí)掌握程度。機(jī)試考試。題型為：編程題。預(yù)習(xí)作業(yè)、小組研討作業(yè)的成績(jī)?cè)u(píng)定標(biāo)準(zhǔn)分別如表4、5所示。表4，5中優(yōu)秀分?jǐn)?shù)段為100-90，良好分?jǐn)?shù)段為89-80，合格分?jǐn)?shù)段為79-60，不合格分?jǐn)?shù)段為≤59?？荚嚦煽?jī)：50%。主要考核程序設(shè)計(jì)、算法與數(shù)據(jù)結(jié)構(gòu)知識(shí)掌握程度。機(jī)試考試。題型為：編程題。（1）成績(jī)?cè)u(píng)定標(biāo)準(zhǔn)預(yù)習(xí)作業(yè)考核與評(píng)價(jià)標(biāo)準(zhǔn)如表4所示?！?/p>

表4

預(yù)習(xí)作業(yè)考核與評(píng)價(jià)標(biāo)準(zhǔn)研討作業(yè)考核與評(píng)價(jià)標(biāo)準(zhǔn)如表5所示?！?/p>

表5

研討作業(yè)考核與評(píng)價(jià)標(biāo)準(zhǔn)通過(guò)預(yù)習(xí)作業(yè)、研討作業(yè)、期末機(jī)試來(lái)對(duì)學(xué)生專業(yè)核心知識(shí)掌握進(jìn)行考核，即對(duì)3個(gè)畢業(yè)指標(biāo)點(diǎn)的達(dá)成度進(jìn)行評(píng)估。（2）課程目標(biāo)與評(píng)分標(biāo)準(zhǔn)之間的對(duì)應(yīng)關(guān)系■

表6

課程目標(biāo)達(dá)-成績(jī)?cè)u(píng)定標(biāo)準(zhǔn)關(guān)系表09教材及參考書(shū)目教材：鄧澤林、李峰編著.數(shù)據(jù)結(jié)構(gòu)與問(wèn)題求解（C++版、微課版），清華大學(xué)出版社，2024.參考書(shū)目：[1]譚浩強(qiáng).C++面向?qū)ο蟪绦蛟O(shè)計(jì)（第3版）[M]，北京:清華大學(xué)出版社，2020.11[2]，在線判定系統(tǒng)[3]長(zhǎng)沙理工大學(xué)ACM集訓(xùn)隊(duì)編著.OJ習(xí)題匯總（電子版）?參考書(shū)籍本書(shū)是為以數(shù)據(jù)結(jié)構(gòu)、問(wèn)題求解為閱讀目的的讀者編寫(xiě)的教材，以培養(yǎng)讀者的數(shù)據(jù)結(jié)構(gòu)分析、算法設(shè)計(jì)、問(wèn)題求解能力為基本目標(biāo)。本書(shū)讀者需要掌握程序設(shè)計(jì)基礎(chǔ)知識(shí)，并具備一定的編程能力。本書(shū)以數(shù)據(jù)結(jié)構(gòu)為主線，通過(guò)問(wèn)題和案例引入內(nèi)容，重點(diǎn)講解利用數(shù)據(jù)結(jié)構(gòu)知識(shí)求解問(wèn)題的思路、算法實(shí)現(xiàn)與執(zhí)行過(guò)程、能力拓展。全書(shū)主要內(nèi)容為概論、C++編程入門(mén)、線性表、堆棧和隊(duì)列、串、數(shù)組和廣義表、樹(shù)與二叉樹(shù)、圖、查找、排序、索引結(jié)構(gòu)等，講解了棧和隊(duì)列、KMP、哈夫曼樹(shù)與編碼、最短路徑、最小生成樹(shù)、拓?fù)渑判颉㈥P(guān)鍵路徑、哈希查找、二叉查找樹(shù)、B樹(shù)、B+樹(shù)、Trie樹(shù)等經(jīng)典問(wèn)題，并提供了能力拓展環(huán)節(jié)，引導(dǎo)讀者開(kāi)展數(shù)據(jù)結(jié)構(gòu)應(yīng)用實(shí)踐。代碼使用C++語(yǔ)言加以描述和實(shí)現(xiàn)，并用圖解的形式詳細(xì)描述了算法的執(zhí)行過(guò)程，使讀者能夠深入了解數(shù)據(jù)結(jié)構(gòu)相關(guān)算法的運(yùn)行過(guò)程和結(jié)果。本書(shū)可作為本科院校數(shù)據(jù)結(jié)構(gòu)的教學(xué)用書(shū)，也可作為從事數(shù)據(jù)結(jié)構(gòu)與算法設(shè)計(jì)的科技人員、算法競(jìng)賽選手的參考書(shū)及培訓(xùn)教材。第1章概論11.1數(shù)據(jù)結(jié)構(gòu)簡(jiǎn)介11.2數(shù)據(jù)結(jié)構(gòu)的研究對(duì)象11.2.1數(shù)據(jù)邏輯結(jié)構(gòu)11.2.2數(shù)據(jù)物理結(jié)構(gòu)21.2.3數(shù)據(jù)存儲(chǔ)結(jié)構(gòu)21.3常用數(shù)據(jù)結(jié)構(gòu)31.3.1數(shù)組31.3.2棧31.3.3隊(duì)列31.3.4鏈表31.3.5樹(shù)31.3.6圖41.3.7堆41.3.8散列(哈希)表41.4數(shù)據(jù)結(jié)構(gòu)常用運(yùn)算41.4.1數(shù)據(jù)結(jié)構(gòu)常用的運(yùn)算41.4.2算法性能分析5習(xí)題5第2章C++編程入門(mén)62.1語(yǔ)法基礎(chǔ)62.1.1數(shù)據(jù)類型62.1.2輸入輸出72.1.3命名空間72.1.4內(nèi)存分配與回收82.1.5引用92.1.6內(nèi)聯(lián)函數(shù)102.1.7運(yùn)算符重載102.1.8函數(shù)重載112.1.9異常112.2類與對(duì)象132.2.1概述132.2.2構(gòu)造函數(shù)142.2.3對(duì)象的定義與使用152.2.4默認(rèn)構(gòu)造函數(shù)152.2.5成員初始化列表162.2.6this指針172.2.7析構(gòu)函數(shù)182.3繼承18目錄〖3〗2.3.1繼承與派生的概念182.3.2繼承語(yǔ)法形式182.3.3訪問(wèn)控制規(guī)則192.3.4派生類構(gòu)造函數(shù)定義202.3.5派生類構(gòu)造函數(shù)與析構(gòu)函數(shù)調(diào)用次序202.3.6構(gòu)造函數(shù)與析構(gòu)函數(shù)構(gòu)造規(guī)則232.4多態(tài)252.4.1多態(tài)的概念252.4.2虛函數(shù)252.4.3虛析構(gòu)函數(shù)272.4.4純虛函數(shù)與抽象類282.5模板與容器292.5.1模板概念292.5.2函數(shù)模板302.5.3類模板302.5.4容器312.5.5迭代器322.5.6關(guān)聯(lián)式容器322.5.7算法332.6能力拓展342.6.1C#語(yǔ)言索引器模擬342.6.2數(shù)據(jù)訪問(wèn)服務(wù)器模擬35習(xí)題39第3章線性表403.1線性表概述403.2線性表的定義及基本操作403.3線性表存儲(chǔ)結(jié)構(gòu)413.3.1線性表的順序存儲(chǔ)結(jié)構(gòu)413.3.2線性表的鏈表存儲(chǔ)結(jié)構(gòu)413.4線性表的實(shí)現(xiàn)413.4.1單鏈表413.4.2雙向鏈表453.4.3循環(huán)鏈表463.5能力拓展473.5.1判斷鏈表中是否存在環(huán)473.5.2約瑟夫環(huán)49習(xí)題50第4章堆棧和隊(duì)列534.1堆棧534.1.1堆棧的定義534.1.2堆棧的基本操作及抽象數(shù)據(jù)類型描述534.2堆棧的存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)544.2.1堆棧的順序存儲(chǔ)結(jié)構(gòu)及類的實(shí)現(xiàn)544.2.2堆棧的鏈表存儲(chǔ)結(jié)構(gòu)及類的實(shí)現(xiàn)564.3隊(duì)列594.3.1隊(duì)列的定義594.3.2隊(duì)列的基本操作及抽象數(shù)據(jù)類型描述594.4隊(duì)列的存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)604.4.1隊(duì)列的順序存儲(chǔ)結(jié)構(gòu)及類的實(shí)現(xiàn)604.4.2隊(duì)列的鏈表存儲(chǔ)結(jié)構(gòu)及類的實(shí)現(xiàn)634.5堆棧和隊(duì)列的應(yīng)用場(chǎng)景654.5.1堆棧的應(yīng)用場(chǎng)景654.5.2隊(duì)列的應(yīng)用場(chǎng)景664.6能力拓展664.6.1波蘭表達(dá)式求值664.6.2銀行排隊(duì)模擬68習(xí)題72第5章串755.1串的定義755.1.1串的基本概念755.1.2抽象數(shù)據(jù)類型定義755.2串的實(shí)現(xiàn)765.2.1串的構(gòu)造765.2.2串的賦值775.2.3子串截取785.2.4子串插入785.2.5串的復(fù)制805.2.6串的比較815.2.7串的拼接815.3串的模式匹配算法825.3.1暴力匹配825.3.2KMP匹配算法835.3.3改進(jìn)的

KMP

算法875.4能力拓展88習(xí)題90第6章數(shù)組和廣義表936.1數(shù)組的基本概念936.1.1數(shù)組的定義936.1.2數(shù)組的基本操作936.2數(shù)組的存儲(chǔ)結(jié)構(gòu)與抽象數(shù)據(jù)類型描述946.3特殊矩陣的壓縮存儲(chǔ)966.3.1對(duì)稱矩陣966.3.2三角矩陣986.3.3對(duì)角矩陣996.4稀疏矩陣的壓縮存儲(chǔ)1006.4.1稀疏矩陣的順序存儲(chǔ)結(jié)構(gòu)——三元組順序表1016.4.2稀疏矩陣的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)——十字鏈表1036.5廣義表1046.5.1廣義表的定義和基本運(yùn)算1046.5.2廣義表的存儲(chǔ)1056.6能力拓展106習(xí)題107第7章樹(shù)與二叉樹(shù)1117.1樹(shù)的概念1117.2二叉樹(shù)1127.2.1二叉樹(shù)的定義1127.2.2二叉樹(shù)的性質(zhì)1137.2.3二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)1147.3二叉樹(shù)的抽象數(shù)據(jù)類型描述1167.4二叉樹(shù)的操作1177.4.1前序遍歷1177.4.2二叉樹(shù)的構(gòu)建1187.4.3中序遍歷1197.4.4后序遍歷1197.4.5層序遍歷1207.4.6線索二叉樹(shù)1207.5二叉樹(shù)與樹(shù)、