《數(shù)據(jù)結(jié)構(gòu)》課程標(biāo)準(zhǔn)

《數(shù)據(jù)結(jié)構(gòu)》課程標(biāo)準(zhǔn)學(xué)時(shí)：72學(xué)時(shí)（其中：講課學(xué)時(shí)：36上機(jī)學(xué)時(shí)：36）先修課程：高等數(shù)學(xué)、C語言程序設(shè)計(jì)后續(xù)課程：軟件開發(fā)相關(guān)的應(yīng)用性課程（Android應(yīng)用開發(fā)、軟件工程等）適用專業(yè)：軟件技術(shù)、移動應(yīng)用開發(fā)、軟件與信息服務(wù)等開課部門：信息工程與大數(shù)據(jù)學(xué)院一、課程的性質(zhì)《數(shù)據(jù)結(jié)構(gòu)》是面向軟件技術(shù)相關(guān)專業(yè)的一門專業(yè)基礎(chǔ)課，課程要求：熟練掌握線性表、棧和隊(duì)的存儲結(jié)構(gòu)及基本操作，并能在相應(yīng)的應(yīng)用中正確地選用，培養(yǎng)學(xué)生用鏈?zhǔn)浇Y(jié)構(gòu)編寫程序的能力；了解串和廣義表的定義和存儲結(jié)構(gòu)；掌握數(shù)組的存儲結(jié)構(gòu)，熟悉稀疏矩陣的兩種壓縮存儲方法的特點(diǎn)及適用范圍；了解樹的存儲結(jié)構(gòu)及特點(diǎn)，掌握二叉樹和圖的存儲結(jié)構(gòu)及其相應(yīng)算法，培養(yǎng)學(xué)生用非線性結(jié)構(gòu)解決實(shí)際問題的能力；掌握各種查找、排序方法，培養(yǎng)學(xué)生靈活應(yīng)用已有排序方法的能力，開拓思路編寫新的排序算法。二、課程設(shè)計(jì)理念數(shù)據(jù)結(jié)構(gòu)是計(jì)算機(jī)存儲、組織數(shù)據(jù)的方式。數(shù)據(jù)結(jié)構(gòu)是指相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合。精心選擇的數(shù)據(jù)結(jié)構(gòu)可以帶來更高的運(yùn)行或存儲效率，數(shù)據(jù)結(jié)構(gòu)往往同高興的檢索算法和索引技術(shù)有關(guān)。1、課程地位理念在許多類型的程序設(shè)計(jì)中，數(shù)據(jù)結(jié)構(gòu)的選擇是一個基本的設(shè)計(jì)考慮因素。許多大型的構(gòu)造經(jīng)驗(yàn)表明，系統(tǒng)實(shí)現(xiàn)的困難程度和系統(tǒng)構(gòu)造的質(zhì)量都嚴(yán)重的依賴于是否選擇了最優(yōu)的數(shù)據(jù)結(jié)構(gòu)。許多時(shí)候，確定了數(shù)據(jù)結(jié)構(gòu)后，算法就容易得到了。有些時(shí)候事情也會反過來，我們根據(jù)特定算法來選擇數(shù)據(jù)結(jié)構(gòu)與之適應(yīng)。不論哪種情況，選擇合適的數(shù)據(jù)結(jié)構(gòu)都是非常重要的。選擇了數(shù)據(jù)結(jié)構(gòu)，算法隨之確定，是數(shù)據(jù)而不是算法是系統(tǒng)構(gòu)造的關(guān)鍵因素。2、課程學(xué)情理念本課程開設(shè)在嵌入式系統(tǒng)工程?？频谝粚W(xué)期，學(xué)生在學(xué)習(xí)本課程前已具備計(jì)算機(jī)基礎(chǔ)、C語言基礎(chǔ)等知識，本課程力圖讓學(xué)生學(xué)會在C語言環(huán)境下，運(yùn)用面向?qū)ο蟮乃枷刖帉懸?guī)范的代碼，實(shí)現(xiàn)經(jīng)典的數(shù)據(jù)結(jié)構(gòu)和算法。熟悉常用的數(shù)據(jù)結(jié)構(gòu)和算法，使學(xué)生初步具備一個優(yōu)秀的軟件開發(fā)人員所應(yīng)有的基本能力。3、課程內(nèi)容理念根據(jù)本課程的教學(xué)目標(biāo)，確定了課程內(nèi)容體系結(jié)構(gòu)的五個組成部分：集合結(jié)構(gòu)、線性表、堆棧和隊(duì)列、樹和二叉樹、查找和排序。內(nèi)容主要包括：緒論、線性表、有序線性表、堆棧、隊(duì)列、樹、二叉樹、二叉樹的遍歷、順序查找、折半查找、插入排序、選擇排序等。4、課程要求理念《數(shù)據(jù)結(jié)構(gòu)》是一門偏重理論的課程，有很強(qiáng)的理論性。在多年的教學(xué)研究和教學(xué)實(shí)踐中，《數(shù)據(jù)結(jié)構(gòu)》形成了獨(dú)具特色的“七化”教學(xué)方法，即教學(xué)資源立體化、教師精講主導(dǎo)化、學(xué)生學(xué)習(xí)團(tuán)隊(duì)化、教學(xué)過程流水化、程序項(xiàng)目核心化、知識技能點(diǎn)索引化、和C語言結(jié)合化。5、課程考核理念如何客觀反映出學(xué)生對數(shù)據(jù)結(jié)構(gòu)的理解、掌握、綜合應(yīng)用的實(shí)際情況，傳統(tǒng)的閉卷考試有不完善的地方，應(yīng)該對考核內(nèi)容和形式進(jìn)行適當(dāng)?shù)恼{(diào)整，過程評價(jià)與終結(jié)評價(jià)相結(jié)合，形成全方位、更加公正客觀的評價(jià)體系?？己朔椒ú捎谩癗+2”成績評定方式，采用“課堂考勤＋課堂實(shí)訓(xùn)練習(xí)＋期末考試”的方式。三、課程目標(biāo)（一）總目標(biāo)本課程以培養(yǎng)學(xué)生的數(shù)據(jù)抽象能力和復(fù)雜程序設(shè)計(jì)的能力為總目標(biāo)。通過本課程的學(xué)習(xí)，學(xué)生可以學(xué)會分析研究計(jì)算機(jī)加工的數(shù)據(jù)結(jié)構(gòu)的特性，以便為應(yīng)用涉及的數(shù)據(jù)選擇適當(dāng)?shù)倪壿嫿Y(jié)構(gòu)、存儲結(jié)構(gòu)及其相應(yīng)的運(yùn)算，并初步掌握算法的時(shí)間分析和空間分析的技術(shù)；另一方面，本課程的學(xué)習(xí)過程也是復(fù)雜程序設(shè)計(jì)的訓(xùn)練過程，要求學(xué)生編寫的程序結(jié)構(gòu)清楚和正確易讀，符合軟件工程的規(guī)范。（二）具體目標(biāo)1.知識目標(biāo)（1）掌握各種主要數(shù)據(jù)結(jié)構(gòu)的特點(diǎn)、計(jì)算機(jī)內(nèi)的表示方法，以及處理數(shù)據(jù)的算法實(shí)現(xiàn)。（2）使學(xué)生學(xué)會分析研究計(jì)算機(jī)加工的數(shù)據(jù)結(jié)構(gòu)的特性，以便為應(yīng)用涉及的數(shù)據(jù)選擇適當(dāng)?shù)倪壿嫿Y(jié)構(gòu)、存儲結(jié)構(gòu)及相應(yīng)的算法，并初步了解對算法的時(shí)間分析和空間分析技術(shù)。（3）通過對本課程算法設(shè)計(jì)和上機(jī)實(shí)踐的訓(xùn)練，培養(yǎng)學(xué)生的數(shù)據(jù)抽象能力和復(fù)雜程序設(shè)計(jì)的能力。2.能力目標(biāo)（1）有初步的算法分析和設(shè)計(jì)能力。（2）能夠有效地獲取、利用、傳遞信息。（3）通過獨(dú)立學(xué)習(xí)，不斷獲取新的知識和技能，能夠在工作中尋求發(fā)現(xiàn)問題、解決問題的途徑。3.素質(zhì)目標(biāo)（1）培養(yǎng)學(xué)生“愛崗、敬業(yè)、細(xì)致、求精”的職業(yè)道德與情感。（2）培養(yǎng)學(xué)生良好的動手實(shí)踐習(xí)慣，尤其注重挖掘?qū)W生的潛質(zhì)。（3）注重培養(yǎng)學(xué)生與社會接軌。（4）培養(yǎng)學(xué)生嚴(yán)謹(jǐn)?shù)男惺嘛L(fēng)格。4.培養(yǎng)目標(biāo)系統(tǒng)地學(xué)習(xí)和掌握基本數(shù)據(jù)結(jié)構(gòu)及其不同算法的實(shí)現(xiàn)，掌握分析、比較和選擇不同數(shù)據(jù)結(jié)構(gòu)和不同存儲結(jié)構(gòu)，為后續(xù)課程的學(xué)習(xí)打好基礎(chǔ)；掌握在不同存儲結(jié)構(gòu)上實(shí)現(xiàn)的不同算法及其設(shè)計(jì)思想。體會并掌握結(jié)構(gòu)選擇和算法設(shè)計(jì)的思想模式及技巧，進(jìn)一步提高學(xué)生的程序設(shè)計(jì)水平和解決實(shí)際問題的能力。四、課程設(shè)計(jì)思路本課程標(biāo)準(zhǔn)從計(jì)算機(jī)軟件技術(shù)及應(yīng)用技術(shù)專業(yè)的視角出發(fā)，以滿足本專業(yè)就業(yè)崗位所必須具備的計(jì)算機(jī)軟件技術(shù)基礎(chǔ)知識為基礎(chǔ)，教學(xué)內(nèi)容設(shè)計(jì)通過崗位工作目標(biāo)與任務(wù)分析，分解完成工作任務(wù)所必備的知識和能力，采用并列和流程相結(jié)合的教學(xué)結(jié)構(gòu)，構(gòu)建教學(xué)內(nèi)容的任務(wù)和達(dá)到工作任務(wù)要求而組建的各項(xiàng)目，以及教學(xué)要求和參考教學(xué)課時(shí)數(shù)。通過實(shí)踐操作、案例分析，培養(yǎng)學(xué)生的綜合職業(yè)能力，基本達(dá)到程序員級職業(yè)技能鑒定標(biāo)準(zhǔn)。五、課程的主要內(nèi)容及基本要求第一章緒論主要內(nèi)容：什么是數(shù)據(jù)結(jié)構(gòu)、數(shù)據(jù)結(jié)構(gòu)的基本概念和術(shù)語、抽象數(shù)據(jù)類型的定義、表示和實(shí)現(xiàn)方法；描述算法的類C語言；算法設(shè)計(jì)的基本要求以及從時(shí)間和空間角度分析算法的方法。教學(xué)重點(diǎn)：各名詞、術(shù)語的含義、基本概念；數(shù)據(jù)的邏輯結(jié)構(gòu)和存儲結(jié)構(gòu)之間的關(guān)系。教學(xué)難點(diǎn)：算法的時(shí)間復(fù)雜度及其分析。教學(xué)要求：理解數(shù)據(jù)、數(shù)據(jù)元素、數(shù)據(jù)項(xiàng)的概念及其相互關(guān)系；了解抽象數(shù)據(jù)類型的定義、表示和實(shí)現(xiàn)方法；理解存儲結(jié)構(gòu)與邏輯結(jié)構(gòu)的關(guān)系；了解四種基本存儲方式；理解算法的概念并初步掌握類C語言；了解算法分析的基本概念、時(shí)間復(fù)雜度及其量級的概念。第二章線性表主要內(nèi)容：線性表的邏輯結(jié)構(gòu)定義、抽象數(shù)據(jù)類型定義和各種存儲結(jié)構(gòu)的描述方法；在線性表的兩類存儲結(jié)構(gòu)（順序的和鏈?zhǔn)降模┥蠈?shí)現(xiàn)基本操作；一元多項(xiàng)式的表示及其相加。教學(xué)重點(diǎn)：線性表的有關(guān)概念，線性表的兩類存儲結(jié)構(gòu)（即順序表和鏈表）的表示及其運(yùn)算的實(shí)現(xiàn)，能根據(jù)具體問題的要求設(shè)計(jì)合理的數(shù)據(jù)結(jié)構(gòu)和算法。教學(xué)難點(diǎn)：指針、鏈表和順序表的概念及表示，有關(guān)鏈表結(jié)構(gòu)的基本操作、算法設(shè)計(jì)和靈活運(yùn)用。教學(xué)要求：熟練掌握兩類存儲結(jié)構(gòu)的描述方法，鏈表中的頭結(jié)點(diǎn)、頭指針和首元結(jié)點(diǎn)的區(qū)別及循環(huán)鏈表、雙向鏈表的特點(diǎn)等。熟練掌握線性表在順序存儲結(jié)構(gòu)上實(shí)現(xiàn)基本操作（查找、插入、刪除）的算法；熟練掌握在各種鏈表結(jié)構(gòu)中實(shí)現(xiàn)線性表操作的基本方法，能在實(shí)際應(yīng)用中選用適當(dāng)?shù)逆湵斫Y(jié)構(gòu)。能夠了解靜態(tài)鏈表，加深對鏈表本質(zhì)的理解。能夠從時(shí)間和空間復(fù)雜度的角度綜合比較線性表存儲結(jié)構(gòu)的不同特點(diǎn)及其使用場合。第三章棧和隊(duì)列主要內(nèi)容：棧和隊(duì)列的結(jié)構(gòu)特點(diǎn)，在兩種存儲結(jié)構(gòu)上如何實(shí)現(xiàn)棧和隊(duì)列的基本操作以及棧和隊(duì)列在程序設(shè)計(jì)中的應(yīng)用。教學(xué)重點(diǎn)：棧和隊(duì)列的特點(diǎn)，基于順序棧、鏈棧、循環(huán)隊(duì)列和鏈隊(duì)列上的基本運(yùn)算的實(shí)現(xiàn)和簡單算法設(shè)計(jì)。教學(xué)難點(diǎn)：循環(huán)隊(duì)列的組成及在該結(jié)構(gòu)上判斷隊(duì)滿和隊(duì)空的條件。教學(xué)要求：掌握棧和隊(duì)列這兩種抽象數(shù)據(jù)類型的特點(diǎn)，并能在相應(yīng)的應(yīng)用中正確選用它們；熟練掌握棧類型的兩種實(shí)現(xiàn)方法，棧滿和?？盏臈l件以及它們的描述方法；熟練掌握循環(huán)隊(duì)列和鏈隊(duì)列的基本操作、實(shí)現(xiàn)算法以及隊(duì)滿和隊(duì)空的條件描述方法。串（補(bǔ)充）主要內(nèi)容：串的數(shù)據(jù)類型定義；串的三種存儲結(jié)構(gòu)表示；串的各種基本操作的實(shí)現(xiàn)及應(yīng)用。教學(xué)重點(diǎn)：串的定義及三種存儲結(jié)構(gòu)表示，串的五種基本操作，并能根據(jù)五種基本操作實(shí)現(xiàn)串的其它各種操作。教學(xué)難點(diǎn)：堆分配存儲表示及算法。教學(xué)要求：熟悉串的五種基本操作的定義，并利用這些基本操作實(shí)現(xiàn)串的其它各種操作的方法；熟悉在串的定長順序存儲結(jié)構(gòu)上實(shí)現(xiàn)串的各種操作的方法；掌握串的堆存儲結(jié)構(gòu)以及在其上實(shí)現(xiàn)串的各種操作的方法。數(shù)組和廣義表（補(bǔ)充）主要內(nèi)容：數(shù)組的類型定義和表示方式；特殊矩陣和稀疏矩陣的壓縮存儲方法及運(yùn)算的實(shí)現(xiàn)；廣義表的定義及其存儲結(jié)構(gòu)。教學(xué)重點(diǎn)：數(shù)組的兩種存儲結(jié)構(gòu)及其地址計(jì)算方法，特殊矩陣進(jìn)行壓縮存儲時(shí)的下標(biāo)變換公式，稀疏矩陣的兩種壓縮存儲方法，利用稀疏矩陣進(jìn)行矩陣運(yùn)算時(shí)采用的處理方法。教學(xué)難點(diǎn)：行邏輯鏈接的順序表的矩陣運(yùn)算，稀疏矩陣的十字鏈表存儲表示。教學(xué)要求：了解數(shù)組的兩種存儲表示方法，并掌握數(shù)組在以行為主的存儲結(jié)構(gòu)中的地址計(jì)算方法；掌握對特殊矩陣進(jìn)行壓縮存儲時(shí)的下標(biāo)變換公式；熟悉稀疏矩陣的兩種壓縮存儲方法的特點(diǎn)及適用范圍，熟悉三元組表示稀疏矩陣進(jìn)行矩陣運(yùn)算采用的處理方法；了解廣義表的結(jié)構(gòu)特點(diǎn)及其存儲表示方法。第四章樹和二叉樹主要內(nèi)容：二叉樹的定義、性質(zhì)和存儲結(jié)構(gòu)；二叉樹的遍歷和線索化以及遍歷算法的各種描述形式；樹和森林的定義、存儲結(jié)構(gòu)與二叉樹的轉(zhuǎn)換、遍歷；樹的應(yīng)用。教學(xué)重點(diǎn)：樹型結(jié)構(gòu)的概念，二叉樹、滿二叉樹、完全二叉樹的定義和性質(zhì)，二叉樹的存儲結(jié)構(gòu)及其三種遍歷算法，樹的存儲結(jié)構(gòu)和它與二叉樹之間的相互轉(zhuǎn)換；最優(yōu)樹的構(gòu)造和哈夫曼編碼。教學(xué)難點(diǎn)：遍歷二叉樹的遞歸算法，線索二叉樹。教學(xué)要求：熟練掌握二叉樹的結(jié)構(gòu)特性，了解相應(yīng)的證明方法；熟悉二叉樹的各種存儲結(jié)構(gòu)的特點(diǎn)及適用范圍；熟練掌握二叉樹遍歷算法，并能靈活運(yùn)用遍歷算法實(shí)現(xiàn)二叉樹的其他操作；理解二叉樹線索的實(shí)質(zhì)；熟練掌握二叉樹的線索化過程；熟悉樹的各種存儲結(jié)構(gòu)及其特點(diǎn)，掌握樹和森林與二叉樹的轉(zhuǎn)換方法；了解最優(yōu)樹的特性，掌握建立最優(yōu)樹和哈夫曼編碼的方法。第五章圖主要內(nèi)容：圖的定義和術(shù)語；圖的四種存儲結(jié)構(gòu)；數(shù)組表示法、鄰接表、十字鏈表和鄰接多重表；圖的兩種遍歷；圖的連通性；連通分量和最小生成樹；拓?fù)渑判蚝完P(guān)鍵路徑；兩類求最短路徑問題的算法。教學(xué)重點(diǎn)：圖的有關(guān)概念；圖的兩種存儲結(jié)構(gòu)（鄰接矩陣和鄰接表）；圖的兩種遍歷算法；最小生成樹的構(gòu)造；拓?fù)渑判?。教學(xué)難點(diǎn)：關(guān)鍵路徑的概念，最短路徑及其算法的實(shí)現(xiàn)。教學(xué)要求：理解圖的概念并熟悉有關(guān)術(shù)語，熟練掌握圖的兩種存儲結(jié)構(gòu)（鄰接矩陣和鄰接表），熟悉圖的各種存儲結(jié)構(gòu)及其構(gòu)造算法，熟練掌握圖的兩種搜索路徑遍歷的基本思想和算法，了解拓?fù)渑判虻母拍詈退惴?，熟悉求關(guān)鍵路徑和兩類求最短路徑問題的基本思想。第六章查找主要內(nèi)容：討論查找表（動態(tài)查找表和靜態(tài)查找表）的各種實(shí)現(xiàn)方法；關(guān)于衡量查找表的主要操作——平均查找長度的討論。教學(xué)重點(diǎn)：順序表、有序表、二叉排序樹和哈希表。教學(xué)難點(diǎn)：平均查找長度的分析；二叉排序樹的刪除操作；平衡二叉樹的平衡方法。教學(xué)要求：熟練掌握順序表和有序表的查找方法；熟練掌握二叉排序樹的構(gòu)造和查找方法；熟悉二叉平衡樹的維護(hù)平衡方法；了解B—樹的特點(diǎn)；熟練掌握哈希表的構(gòu)造方法；掌握描述查找過程的判定樹的構(gòu)造方法；以及按定義計(jì)算各種查找方法在等概率情況下查找成功時(shí)的平均查找長度。第七章排序主要內(nèi)容：討論比較各種內(nèi)部排序方法：插入排序、交換排序、選擇排序、歸并排序和基數(shù)排序的基本思想，算法特點(diǎn)、排序過程以及它們的時(shí)間復(fù)雜度分析。教學(xué)重點(diǎn)：希爾排序、快速排序、堆排序和歸并排序。教學(xué)難點(diǎn)：快速排序和堆排序以及分析排序算法的平均情況和最壞情況的時(shí)間性能。教學(xué)要求：深刻理解排序的定義和各種排序方法的特點(diǎn)，并能靈活的應(yīng)用。了解各種方法的排序過程及其依據(jù)原則；掌握各種排序方法的時(shí)間復(fù)雜度的分析方法；理解排序方法穩(wěn)定或不穩(wěn)定的含義；了解表排序和地址排序的過程及其適用場合。六、考核模式與成績評定辦法本課程為考試課程，期末考試采用百分制的閉卷考試模式。學(xué)生的考試成績由平時(shí)成績（40%）和期末考試（60%）組成，其中，平時(shí)成績包括出勤（10%）、作業(yè)（10%）、實(shí)驗(yàn)和上機(jī)成績（20%）。七、選用教材和主要參考書本大綱是根據(jù)教材《數(shù)據(jù)結(jié)構(gòu)》所設(shè)計(jì)的。教材：1李學(xué)剛，數(shù)據(jù)結(jié)構(gòu)（C語言描述），高等教育出版社，2013.5參考文獻(xiàn)（含參考書、有關(guān)資料出處、相關(guān)課程網(wǎng)站網(wǎng)址等）：1嚴(yán)蔚敏，吳偉民，米寧編著·數(shù)據(jù)結(jié)構(gòu)題集·C語言版，北京，清華大學(xué)出版社，