數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)教學(xué)大綱一、課程基本信息課程名稱（中文）數(shù)據(jù)結(jié)構(gòu)課程名稱（英文）DataStructure課程類型專業(yè)基礎(chǔ)課學(xué)分4（5）總學(xué)時(shí)52+16（52+32）適用對象信息與計(jì)算科學(xué)專業(yè)（本科）考核方式閉卷筆試與上機(jī)考試相結(jié)合、其中平時(shí)成績占20%、實(shí)驗(yàn)成績占20%、期末考試成績占60%先修課程C程序設(shè)計(jì)后繼課程操作系統(tǒng)、數(shù)據(jù)庫原理、數(shù)學(xué)建模等二、實(shí)驗(yàn)課程簡介本課程是結(jié)合理論課程《數(shù)據(jù)結(jié)構(gòu)》安排的實(shí)踐課程，目的是通過本課程的實(shí)踐與操作，加深理論課程中數(shù)據(jù)結(jié)構(gòu)與算法的理解。數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)是對學(xué)生的一種全面綜合訓(xùn)練，是與課堂聽講、自學(xué)和練習(xí)相輔相成的必不可少的一個(gè)教學(xué)環(huán)節(jié)。針對本實(shí)驗(yàn)課程的特點(diǎn)，分為驗(yàn)證性、設(shè)計(jì)性實(shí)驗(yàn)。其中驗(yàn)證性實(shí)驗(yàn)要求學(xué)生能理解程序，掌握程序流程，明白程序運(yùn)行結(jié)果；設(shè)計(jì)性實(shí)驗(yàn)讓學(xué)生利用所學(xué)的知識開發(fā)小型項(xiàng)目，要求學(xué)生能獨(dú)立分析問題，設(shè)計(jì)算法，實(shí)現(xiàn)程序的各項(xiàng)功能，得到正確的可執(zhí)行程序，學(xué)會調(diào)試程序，對設(shè)計(jì)過程進(jìn)行系統(tǒng)的總結(jié)。三、實(shí)驗(yàn)?zāi)康摹稊?shù)據(jù)結(jié)構(gòu)》課程實(shí)驗(yàn)的目的是訓(xùn)練學(xué)生進(jìn)行復(fù)雜程序設(shè)計(jì)的技能和培養(yǎng)良好程序設(shè)計(jì)的習(xí)慣。通過完成本實(shí)驗(yàn)課的實(shí)驗(yàn)，學(xué)生應(yīng)學(xué)會和掌握本課程的基本和重點(diǎn)知識；深刻理解邏輯結(jié)構(gòu)、物理結(jié)構(gòu)、算法設(shè)計(jì)之間的關(guān)系；訓(xùn)練并具有進(jìn)行復(fù)雜程序設(shè)計(jì)的能力，養(yǎng)成良好程序設(shè)計(jì)的習(xí)慣。四、實(shí)驗(yàn)內(nèi)容與要求（一）線性表的應(yīng)用1.實(shí)驗(yàn)?zāi)康恼莆站€性表的基本結(jié)構(gòu)和操作方法，培養(yǎng)學(xué)生靈活使用結(jié)構(gòu)解決實(shí)際問題的能力。2.實(shí)驗(yàn)內(nèi)容一條記錄有學(xué)號和成績兩個(gè)數(shù)據(jù)項(xiàng)，按成績由大到小建立兩個(gè)有序表（可用順序表或者鏈?zhǔn)奖韺?shí)現(xiàn)），并合并成一個(gè)有序表（有能力的同學(xué)才做這個(gè)合并）。第一個(gè)表輸入的數(shù)據(jù)如下（學(xué)號，成績）：(1,70),(2,85),(3,75),(4,90)，第二個(gè)表輸入的數(shù)據(jù)如下（學(xué)號，成績）：(5,60),(6,80),(7,76),(8,50)。3.實(shí)驗(yàn)要求（1）編寫初始化函數(shù)，插入函數(shù)，顯示函數(shù),釋放函數(shù),對兩個(gè)表統(tǒng)一處理；（2）有能力的同學(xué)再編寫合并函數(shù)，把兩個(gè)有序表合并成一個(gè)新的有序表（保留原表）；（3）可用順序表或者鏈表實(shí)現(xiàn)；（二）棧的應(yīng)用1.實(shí)驗(yàn)?zāi)康恼莆諚２僮鞯姆椒跋嚓P(guān)應(yīng)用。2.實(shí)驗(yàn)內(nèi)容假設(shè)表達(dá)式中允許包含兩種括號：圓括號和方括號，其嵌套的順序任意，即([]())或[([][])]等都為正確的格式，而[(])為不正確的格式。利用棧編程序檢驗(yàn)表達(dá)式中的括號是否合法。3.實(shí)驗(yàn)要求先實(shí)現(xiàn)棧的基本操作：初始化，入棧，出棧等。每讀入一個(gè)括號，若是右括號，則或者是置于棧頂?shù)淖罄ㄌ柕靡韵?，或者是不合法的情況；若是左括號，則直接入棧?？捎庙樞驐；蛘哝湕?shí)現(xiàn)。（三）隊(duì)列的應(yīng)用1.實(shí)驗(yàn)?zāi)康恼莆贞?duì)列操作的方法及相關(guān)應(yīng)用。2.實(shí)驗(yàn)內(nèi)容用隊(duì)列進(jìn)行迷宮求解（即寬度優(yōu)先搜索）。3.實(shí)驗(yàn)要求先實(shí)現(xiàn)隊(duì)列的基本操作：初始化，入隊(duì)，出隊(duì)等?？蓞⒖加脳＿M(jìn)行迷宮求解的方法?？捎庙樞蜿?duì)列或者鏈隊(duì)列實(shí)現(xiàn)。（四）二叉樹1.實(shí)驗(yàn)?zāi)康恼莆諛湫谓Y(jié)構(gòu)的特點(diǎn)、二叉樹的存儲方式以及相應(yīng)操作。2.實(shí)驗(yàn)內(nèi)容編寫一個(gè)程序?qū)崿F(xiàn)下列目標(biāo)：（1）根據(jù)輸入的數(shù)據(jù)建立一個(gè)二叉樹；（2）輸出二叉樹；（3）輸出其前序、中序和后序遍歷的結(jié)果；（4）輸出樹的深度、最大元、最小元。3.實(shí)驗(yàn)要求用鏈表實(shí)現(xiàn)。（五）圖的操作1.實(shí)驗(yàn)?zāi)康恼莆請D形結(jié)構(gòu)的特點(diǎn)、存儲方式以及相應(yīng)操作。2.實(shí)驗(yàn)內(nèi)容（1）輸入帶權(quán)圖的鄰接矩陣（用數(shù)組表示）；（2）輸出深度優(yōu)先搜索結(jié)果和廣度優(yōu)先搜索結(jié)果；（3）輸出其最小生成樹。3.實(shí)驗(yàn)要求（1）權(quán)為正數(shù)；（2）最小生成樹出發(fā)點(diǎn)為第一個(gè)頂點(diǎn)。（六）查找1.實(shí)驗(yàn)?zāi)康恼莆侦o態(tài)查找表和動態(tài)查找表的實(shí)現(xiàn)方法。2.實(shí)驗(yàn)內(nèi)容（1）使用順序查找方法從已知的數(shù)據(jù)序列中查找輸入的數(shù)據(jù)；（2）使用折半查找方法從已知的有序數(shù)據(jù)序列中查找輸入的數(shù)據(jù)；（3）利用平衡二叉樹實(shí)現(xiàn)一個(gè)動態(tài)查找表。3.實(shí)驗(yàn)要求（1）順序查找和折半查找中的數(shù)據(jù)序列使用數(shù)組初始化生成，查找數(shù)據(jù)由鍵盤輸入；（2）實(shí)現(xiàn)動態(tài)查找表的三種功能：查找、插入和刪除。（七）排序算法1.實(shí)驗(yàn)?zāi)康氖煜づ判蛩惴ā?.實(shí)驗(yàn)內(nèi)容（1）編程實(shí)現(xiàn)快速排序算法；（2）編程實(shí)現(xiàn)冒泡排序算法；（3）編程實(shí)現(xiàn)基數(shù)排序算法。3.實(shí)驗(yàn)要求數(shù)據(jù)的存儲使用數(shù)組，數(shù)據(jù)個(gè)數(shù)和數(shù)據(jù)由鍵盤輸入。五、主要儀器設(shè)備個(gè)人計(jì)算機(jī)六、實(shí)驗(yàn)學(xué)時(shí)分配表序號實(shí)驗(yàn)項(xiàng)目名稱學(xué)時(shí)實(shí)驗(yàn)內(nèi)容實(shí)驗(yàn)性質(zhì)演示驗(yàn)證設(shè)計(jì)綜合1線性表的應(yīng)用2（4）長整數(shù)的加減√2棧的應(yīng)用2（4）括號匹配√3隊(duì)列的應(yīng)用2（2）迷宮的求解√4二叉樹4（6）二叉樹的建立、遍歷√5圖的操作2（6）圖的存儲、搜索、最小生成樹√6查找2（6）靜態(tài)查找表與動態(tài)查找表√7排序算法2（6）各種排序算法的實(shí)現(xiàn)√七、考核方法本課程采用平時(shí)考核、實(shí)驗(yàn)報(bào)告與期末上機(jī)考試相結(jié)合的方式評定學(xué)生成績，該成績占總評成績的20%。八、教材及參考書教材：《數(shù)據(jù)結(jié)構(gòu)（C語言版）》（清華大學(xué)出版社，2012年5月，嚴(yán)蔚敏，吳偉民主編）《數(shù)據(jù)結(jié)構(gòu)（C語言版）》（華中科技大學(xué)出版社,2017年03月，孫麗云）參考書：《數(shù)據(jù)結(jié)構(gòu)題集（C語言版