數(shù)據(jù)結(jié)構(gòu)（DataStructure）課程基本信息課程編號：04021523課程總學(xué)時：32實(shí)驗(yàn)學(xué)時：8學(xué)時課程性質(zhì)：選修課程屬性:專業(yè)類開設(shè)學(xué)期：第4學(xué)期適用專業(yè)：電子信息工程對先修的要求：高等數(shù)學(xué)、C語言程序設(shè)計(jì)對后續(xù)的支撐：人工智能導(dǎo)論一、課程的教學(xué)理念、性質(zhì)、目標(biāo)和任務(wù)《數(shù)據(jù)結(jié)構(gòu)》是電子信息專業(yè)的一門專業(yè)選修課?！皵?shù)據(jù)結(jié)構(gòu)”是設(shè)計(jì)與實(shí)現(xiàn)編譯程序、操作系統(tǒng)、數(shù)據(jù)庫系統(tǒng)及其它系統(tǒng)程序和大型應(yīng)用程序的重要基礎(chǔ)，是介于數(shù)學(xué)，計(jì)算機(jī)硬件，軟件之間的一門重要課程。本課程較系統(tǒng)地介紹了軟件設(shè)計(jì)中常用的數(shù)據(jù)結(jié)構(gòu)以及相應(yīng)的存儲結(jié)構(gòu)和實(shí)現(xiàn)算法，介紹了常用的多種查找和排序技術(shù)，并對進(jìn)行性能分析和比較。數(shù)據(jù)結(jié)構(gòu)是程序設(shè)計(jì)（特別是非數(shù)值計(jì)算的程序設(shè)計(jì)）的基礎(chǔ)，也是設(shè)計(jì)和實(shí)現(xiàn)編譯程序、操作系統(tǒng)、數(shù)據(jù)庫系統(tǒng)及其它系統(tǒng)程序和大型應(yīng)用程序的重要基礎(chǔ)。數(shù)據(jù)結(jié)構(gòu)課程要求掌握數(shù)據(jù)組織方法和計(jì)算機(jī)的表示方法，為數(shù)據(jù)選擇適當(dāng)?shù)倪壿嫿Y(jié)構(gòu)、存儲結(jié)構(gòu)以及相應(yīng)的處理算法，能夠分析算法的時間、空間復(fù)雜度，培養(yǎng)良好的程序設(shè)計(jì)風(fēng)格，掌握進(jìn)行復(fù)雜程序設(shè)計(jì)的技能。本課程的學(xué)習(xí)將為后續(xù)課程的學(xué)習(xí)以及軟件設(shè)計(jì)水平的提高打下良好的基礎(chǔ)。二、課程目標(biāo)及對畢業(yè)要求指標(biāo)點(diǎn)的支撐序號課程目標(biāo)支撐畢業(yè)要求指標(biāo)點(diǎn)畢業(yè)要求1掌握數(shù)據(jù)結(jié)構(gòu)的相關(guān)概念，理解計(jì)算機(jī)處理非數(shù)值數(shù)據(jù)問題的基本原理和處理方法，掌握實(shí)際問題到不同數(shù)據(jù)類型數(shù)據(jù)的抽象過程和處理方法；指標(biāo)點(diǎn)1.222理解計(jì)算機(jī)處理數(shù)據(jù)的基本方法，能夠運(yùn)用數(shù)據(jù)分析以及數(shù)據(jù)處理算法，對實(shí)際問題進(jìn)行分析和處理，并能得到有效結(jié)果。指標(biāo)點(diǎn)2.44三、教學(xué)內(nèi)容及進(jìn)度安排（一）理論教學(xué)序號教學(xué)內(nèi)容學(xué)生學(xué)習(xí)預(yù)期成果課內(nèi)學(xué)時教學(xué)方式支撐課程目標(biāo)1第1章緒論數(shù)據(jù)結(jié)構(gòu)、算法描述和算法分析、算法作性能評價的方法；理解抽象數(shù)據(jù)類型的表示與實(shí)現(xiàn)；掌握數(shù)據(jù)結(jié)構(gòu)的內(nèi)容。熟悉與數(shù)據(jù)結(jié)構(gòu)相關(guān)的基本概念和基本方法。2課堂PPT講解目標(biāo)12第2章線性表線性表的抽象數(shù)據(jù)類型定義；線性表的順序存儲和鏈?zhǔn)酱鎯Ψ椒ǎ痪€性表的各種運(yùn)算、一元多項(xiàng)式的表示及相加。掌握線性表的各種運(yùn)算、一元多項(xiàng)式的表示及相加。2課堂PPT講解+代碼演示；典型應(yīng)用案例分析。目標(biāo)13第3章限定性線性表——棧和隊(duì)列棧和隊(duì)列的抽象數(shù)據(jù)類型定義；棧與遞歸的實(shí)現(xiàn)；棧和隊(duì)列的典型應(yīng)用；用順序結(jié)構(gòu)和單鏈表結(jié)構(gòu)實(shí)現(xiàn)棧和隊(duì)列掌握棧和隊(duì)列兩種限定性線性表的定義、概念、性質(zhì)和操作方法。4課堂PPT講解+代碼演示；典型應(yīng)用案例分析。目標(biāo)14第4章樹和二叉樹樹的概念與定義；二叉樹的性質(zhì)；二叉樹、樹、森林與二叉樹的相互轉(zhuǎn)換。掌握二叉樹的遍歷，二叉樹、樹、森林與二叉樹的相互轉(zhuǎn)換，哈夫曼樹及其應(yīng)用。6課堂PPT講解+代碼演示；典型應(yīng)用案例分析。目標(biāo)15第5章圖圖的定義與基本術(shù)語；有向無環(huán)圖的應(yīng)用和最短路徑；圖的存儲結(jié)構(gòu)、圖的遍歷、圖的連通性問題；圖的存儲結(jié)構(gòu)、圖的遍歷。掌握各種圖的結(jié)構(gòu)、遍歷等知識，并能應(yīng)用圖的知識解決實(shí)際問題。4課堂PPT講解+代碼演示；典型應(yīng)用案例分析。目標(biāo)16第6章查找查找算法的性能評價方法；基于線性表的查找法、基于樹的查找法、計(jì)算式查找法——哈希法；基于線性表的查找法、基于樹的查找法、計(jì)算式查找法——哈希法。掌握常用的查找方法。2課堂PPT講解+代碼演示；典型應(yīng)用案例分析。目標(biāo)17第7章內(nèi)部排序排序的基本概念；直接插入排序、希爾排序、冒泡排序、快速排序、簡單選擇排序、歸并排序。掌握常用的排序方法。2課堂PPT講解+代碼演示；典型應(yīng)用案例分析。目標(biāo)1（二）實(shí)驗(yàn)教學(xué)序號實(shí)驗(yàn)名稱學(xué)時實(shí)驗(yàn)教學(xué)內(nèi)容學(xué)習(xí)要求支撐課程目標(biāo)1實(shí)驗(yàn)一線性表的基本操作2在不同的存儲結(jié)構(gòu)（順序結(jié)構(gòu)和鏈?zhǔn)浇Y(jié)構(gòu)），實(shí)現(xiàn)線性表的基本操作。掌握線性表的特點(diǎn)；掌握線性表的順序存儲結(jié)構(gòu)和鏈?zhǔn)酱鎯Y(jié)構(gòu)的基本運(yùn)算；掌握線性表的基本操作；能獨(dú)立編寫程序并通過調(diào)試。目標(biāo)22實(shí)驗(yàn)二棧及其應(yīng)用2編寫一個程序listack.cpp，實(shí)現(xiàn)鏈棧（假設(shè)棧中元素類型ElemType為char）的各種基本運(yùn)算，并在此基礎(chǔ)上設(shè)計(jì)一個程序完成如下功能：初始化棧s；判斷棧s是否非空；依次進(jìn)棧元素a、b、c、d、e；判斷棧s是否非空；輸出出棧序列；判斷棧s是否非空；釋放棧。掌握棧的特點(diǎn)；掌握棧的順序存儲結(jié)構(gòu)和鏈?zhǔn)酱鎯Y(jié)構(gòu)的基本運(yùn)算；掌握棧的基本操作；能獨(dú)立編寫程序并通過調(diào)試。目標(biāo)23實(shí)驗(yàn)三隊(duì)列的基本操作2編寫一個程序，實(shí)現(xiàn)隊(duì)列（假設(shè)隊(duì)列中元素類型ElemType為char）的各種基本運(yùn)算，并在此基礎(chǔ)上設(shè)計(jì)一個程序，完成如下功能：初始化隊(duì)列q；判斷隊(duì)列q是否非空；依次進(jìn)隊(duì)元素a、b、c；出隊(duì)一個元素，輸出該元素；依次進(jìn)隊(duì)元素d、e、f；輸出出隊(duì)序列；釋放隊(duì)列。掌握隊(duì)列的特點(diǎn)；掌握隊(duì)列的順序存儲結(jié)構(gòu)和鏈?zhǔn)酱鎯Y(jié)構(gòu)的基本運(yùn)算；掌握隊(duì)列的基本操作；能獨(dú)立編寫程序并通過調(diào)試。目標(biāo)24實(shí)驗(yàn)四二叉樹的基本操作2編寫程序?qū)崿F(xiàn)二叉樹的基本運(yùn)算，并在此基礎(chǔ)上設(shè)計(jì)一個程序完成如下功能：由如圖所示的二叉樹創(chuàng)建對應(yīng)的二叉鏈存儲結(jié)構(gòu)b，該二叉樹的括號表示串為“A(B(D,E(H(J,K(L,M(,N))))),C(F,G(,I)))”；輸出二叉樹b；輸出’H’結(jié)點(diǎn)的左右孩子結(jié)點(diǎn)值；輸出二叉樹b的高度；釋放二叉樹b。掌握二叉樹的基本概念和其基本操作；掌握二叉樹的生成、遍歷等算法；能獨(dú)立編寫程序并通過調(diào)試。目標(biāo)2四、課程思政本課程融合課程思政內(nèi)容，將德育內(nèi)容融入課程體系。教學(xué)過程中探討學(xué)科前沿動態(tài)，引導(dǎo)學(xué)生探索新知識及培養(yǎng)創(chuàng)新思維和綜合能力；將實(shí)踐教學(xué)與理論教學(xué)相結(jié)合，用完美的實(shí)驗(yàn)結(jié)果驗(yàn)證理論知識，加深印象并提高學(xué)生對此課程的興趣。主要從以下幾個方面開展課程思政教學(xué)：（1）激發(fā)對算法設(shè)計(jì)的熱愛之情，增強(qiáng)學(xué)好專業(yè)的使命感和責(zé)任感；強(qiáng)化工科思想素養(yǎng)和行為習(xí)慣，提高緣事析理、明辨是非的能力和工程倫理意識；培養(yǎng)精益求精的大國工匠精神，激發(fā)科技報國的家國情懷和使命擔(dān)當(dāng)，成為德才兼?zhèn)?、全面發(fā)展的技能型人才.（2）幫助學(xué)生樹立正確的科學(xué)觀，提高美學(xué)素養(yǎng)，學(xué)會欣賞“代碼之美”和“算法之美”。（3）哈夫曼樹：引導(dǎo)學(xué)生要打破常規(guī)，從逆向思維的角度分析問題、解決問題。同時引導(dǎo)學(xué)生解決問題要尋求最佳方案，以最小大代價達(dá)到最大的效益。（4）隊(duì)列：日常生活排隊(duì)現(xiàn)象，引導(dǎo)學(xué)生要尊重社會公德，遵守公共秩序，要守規(guī)矩但是不要墨守陳規(guī)。（5）實(shí)驗(yàn)數(shù)據(jù)的客觀記錄與分析，培養(yǎng)學(xué)生的實(shí)事求是科學(xué)態(tài)度。五、教材及參考資料1.選用教材：（1）理論課教材：數(shù)據(jù)結(jié)構(gòu)——C語言描述（第二版），耿國華，西安電子科技大學(xué)出版社，2016（2）實(shí)驗(yàn)課教材：自編2.參考書：（1）數(shù)據(jù)結(jié)構(gòu)與算法分析C語言描述（原書第2版），[美]馬克·艾倫·維斯（Mark，Allen，Weiss）著，馮舜璽譯譯，機(jī)械工業(yè)出版社，2019（2）數(shù)據(jù)結(jié)構(gòu)（第5版）（C語言版），鄧文華著，電子工業(yè)出版社，2019（3）數(shù)據(jù)結(jié)構(gòu)（C語言版），嚴(yán)蔚敏，清華大學(xué)出版社，20183.推薦網(wǎng)站（線上資源）：（1）西北大學(xué):數(shù)據(jù)結(jié)構(gòu)教學(xué)網(wǎng)，/datastr/（2）吉林大學(xué)數(shù)據(jù)結(jié)構(gòu)，/z/i/230.ds（3）南京郵電大學(xué)數(shù)據(jù)結(jié)構(gòu)，/course/NJUPT-1206361803六、教學(xué)條件計(jì)算機(jī)、C語言開發(fā)工具。七、課程考核、考核方式及成績評定序號課程目標(biāo)（支撐畢業(yè)要求指標(biāo)點(diǎn)）考核內(nèi)容評價依據(jù)及成績比例(%)成績比例(%)課堂表現(xiàn)作業(yè)實(shí)驗(yàn)期末考試1目標(biāo)1：（支撐畢業(yè)要求指標(biāo)點(diǎn)1.2）數(shù)據(jù)結(jié)構(gòu)的基本概念、基本原理和處理方法。1020020502目標(biāo)2：（支撐畢業(yè)要求指標(biāo)點(diǎn)2.4）應(yīng)用數(shù)據(jù)結(jié)構(gòu)知識，對實(shí)際問題進(jìn)行分析和處理，并能得到有效結(jié)果。00104050合計(jì)10201060100（1）課堂表現(xiàn)考核內(nèi)容及評分標(biāo)準(zhǔn)課程目標(biāo)考核內(nèi)容評分標(biāo)準(zhǔn)90-100分80-89分70-79分60-69分<60分課程目標(biāo)1（10%）考核學(xué)生預(yù)習(xí)、復(fù)習(xí)、課堂參與情況。遵守課堂紀(jì)律，積極參與教學(xué)活動，踴躍回答問題，準(zhǔn)確率大于90%；或能回答老師提出的問題，準(zhǔn)確率大于90%遵守課堂紀(jì)律，認(rèn)真參與教學(xué)活動，踴躍回答問題，準(zhǔn)確率大于80%；或能回答老師提出的問題，準(zhǔn)確率大于80%。遵守課堂紀(jì)律，上課狀態(tài)一般，能回答老師提出的問題，準(zhǔn)確率大于70%。遵守課堂紀(jì)律，上課狀態(tài)一般，能回答老師提出的問題，準(zhǔn)確率大于60%。遵守課堂紀(jì)律，但不能正常參與課堂教學(xué)活動，不能回答老師提出的問題。（2）作業(yè)評分標(biāo)準(zhǔn)成績課程目標(biāo)優(yōu)秀（90-100分）良好（80-89分）中等（70-79分）及格（60-69分）不及格（<60分）課程目標(biāo)1（20%）按時上交，書寫規(guī)范工整；運(yùn)用所學(xué)理論知識和公式正確，計(jì)算步驟完整，計(jì)算結(jié)果正確。按時上交，書寫工整；運(yùn)用所學(xué)理論知識和公式正確，計(jì)算步驟較完整，計(jì)算結(jié)果正確。按時上交，書寫較工整；運(yùn)用所學(xué)理論知識和公式正確，計(jì)算步驟較完整，計(jì)算結(jié)果基本正確。按時上交，書寫潦草；運(yùn)用所學(xué)理論知識和公式基本正確，計(jì)算步驟簡單，計(jì)算結(jié)果基本正確。不按時上交書寫潦草；運(yùn)用所學(xué)理論知識和公式不正確，計(jì)算步驟較少，計(jì)算結(jié)果不正確。每次作業(yè)按百分制評分，以所有作業(yè)的平均成績計(jì)入總成績。（3）實(shí)驗(yàn)環(huán)節(jié)評分標(biāo)準(zhǔn)成績課程目標(biāo)優(yōu)秀（90-100分）良好（80-89分）中等（70-79分）及格（60-69分）不及格（<60分）課程目標(biāo)2（10%）實(shí)驗(yàn)態(tài)度端正；實(shí)驗(yàn)操作規(guī)范、實(shí)驗(yàn)結(jié)果正確；考核中能準(zhǔn)確地回答全部問題；實(shí)驗(yàn)報告撰寫規(guī)范、整潔、全面。實(shí)驗(yàn)態(tài)度端正；實(shí)驗(yàn)操作規(guī)范、實(shí)驗(yàn)結(jié)果正確；考核中能基本準(zhǔn)確地回答全部問題；實(shí)驗(yàn)報告撰寫規(guī)范整潔。實(shí)驗(yàn)態(tài)度端正；實(shí)驗(yàn)操作基本規(guī)范，實(shí)驗(yàn)結(jié)果正確；考核中能準(zhǔn)確地回答主要問題；實(shí)驗(yàn)報告撰寫基本規(guī)范。實(shí)驗(yàn)態(tài)度較端正；實(shí)驗(yàn)操作基本規(guī)范，實(shí)驗(yàn)結(jié)果基本正確；考核中能準(zhǔn)確地回答部分問題；實(shí)驗(yàn)報告撰寫基本規(guī)范。實(shí)驗(yàn)態(tài)度不端正；無法獨(dú)立完成實(shí)驗(yàn)操作，實(shí)驗(yàn)結(jié)果不正確；考核中不能準(zhǔn)確地回答主要問題；實(shí)驗(yàn)報告書寫不規(guī)范。（4）期末考核內(nèi)容及評分標(biāo)準(zhǔn)課程目標(biāo)考核內(nèi)容評分標(biāo)準(zhǔn)90-100分80-89分70-79分60-69分<60分課程目標(biāo)1（20%）數(shù)據(jù)結(jié)構(gòu)的基本概念、基本原理和處理方法。熟練掌握數(shù)據(jù)結(jié)構(gòu)的基本概念、基本原理和處理方法。掌握數(shù)據(jù)結(jié)構(gòu)的基本概念、基本原理和處理方法?；菊莆諗?shù)據(jù)結(jié)構(gòu)的基本概念、基本原理和處理方法。了解數(shù)據(jù)結(jié)構(gòu)的基本概念、基本原理和處理方法。不了解數(shù)據(jù)結(jié)構(gòu)的基本概念、基本原理和處理方法。課程目標(biāo)2（40%）應(yīng)用數(shù)據(jù)結(jié)構(gòu)知識，對實(shí)際問題進(jìn)行分析和處理，并能得到有效結(jié)果。具有很強(qiáng)的應(yīng)用數(shù)據(jù)結(jié)構(gòu)知識，對實(shí)際問題進(jìn)行分析和處理，并能得到有效結(jié)果。具有較強(qiáng)的應(yīng)用數(shù)據(jù)結(jié)構(gòu)知識，對實(shí)際問題進(jìn)行分析和處理，并能得到有效結(jié)果。具有一定的應(yīng)用數(shù)據(jù)結(jié)構(gòu)知識，對實(shí)際問題進(jìn)行分析和處理，并能得到有