數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)指導(dǎo)(16學(xué)時)

1、數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)指導(dǎo)書（16學(xué)時）計算機(jī)專業(yè)實(shí)驗(yàn)中心目 錄實(shí)驗(yàn)一 C語言結(jié)構(gòu)體與指針2實(shí)驗(yàn)二 線性順序表的實(shí)現(xiàn)及操作2實(shí)驗(yàn)三 串的匹配與替換3實(shí)驗(yàn)四 線性鏈表的實(shí)現(xiàn)及操作3實(shí)驗(yàn)五 棧和隊(duì)列的應(yīng)用4實(shí)驗(yàn)六 二叉樹的實(shí)現(xiàn)及遍歷4實(shí)驗(yàn)七 圖的實(shí)現(xiàn)及遍歷4實(shí)驗(yàn)八 查找算法的實(shí)現(xiàn)及比較5實(shí)驗(yàn)一 C語言結(jié)構(gòu)體與指針1、實(shí)驗(yàn)?zāi)康模?鞏固復(fù)習(xí)前期所學(xué)C語言的函數(shù)參數(shù)傳遞、指針和結(jié)構(gòu)體等知識點(diǎn)，加強(qiáng)學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)語言基礎(chǔ)。2、實(shí)驗(yàn)內(nèi)容： 1) 學(xué)生信息的顯示，具體要求如下： 􀁺 定義一個結(jié)構(gòu)體描述學(xué)生信息(學(xué)號，姓名，性別，年齡，住址)； 􀁺 設(shè)計一個函數(shù)，用于顯示單個學(xué)生信息，函

2、數(shù)的參數(shù)為前面定義的結(jié)構(gòu)體類型； 􀁺 設(shè)計一個主函數(shù)，在主函數(shù)中輸入學(xué)生的信息，并調(diào)用前面定義的函數(shù)進(jìn)行顯示（學(xué)生人數(shù)不少于5人）。2) 輸入若干個整數(shù)作為數(shù)組元素值，然后按輸入時順序的就地逆置排序，最后打印出逆置后的元素值。要求用指針和動態(tài)內(nèi)存分配方法實(shí)現(xiàn)。例如 輸入：10 2 30 4 5，逆置后顯示為：5 4 30 2 10。3、思考題： 分析結(jié)果是否正確，如果不正確是什么原因。 實(shí)驗(yàn)二 線性順序表的實(shí)現(xiàn)及操作1、實(shí)驗(yàn)?zāi)康模?1) 掌握建立線性順序表的基本方法。 2) 理解和掌握線性順序表元素查找算法。 3) 掌握線性順序表的插入、刪除算法的思想和實(shí)現(xiàn)。 2、實(shí)驗(yàn)內(nèi)容：

3、 1) 建立一個線性順序表，要求從鍵盤輸入10個整數(shù)，并將該線性順序表的元素從屏幕顯示出來； 2) 編寫查找函數(shù)，在上面的線性順序表中查找其中一個元素，如果找到，返回該元素在線性順序表中的位置和該元素的值，否則提示無此元素。要求被查找元素從鍵盤輸入。3) 編寫插入和刪除函數(shù)，由用戶輸入待插入元素及插入位置，將完成插入后的線性順序表輸出；由用戶輸入刪除第幾個元素，將完成刪除后的線性順序表輸出。3、思考題： 分析線性順序表結(jié)構(gòu)下插入和刪除算法的時間復(fù)雜度。 實(shí)驗(yàn)三 串的匹配與替換1、實(shí)驗(yàn)?zāi)康模?1) 掌握串存儲結(jié)構(gòu)； 2) 掌握串的匹配算法，并能進(jìn)行相關(guān)應(yīng)用。 2、實(shí)驗(yàn)內(nèi)容： 設(shè)串采用靜態(tài)數(shù)組存儲

4、結(jié)構(gòu)，編寫函數(shù)實(shí)現(xiàn)串的替換Replace(S，start，T，V)，即要求在主串S中從位置start開始查找是否存在子串T。若存在，則用子串V去替換子串T，且函數(shù)返回1；若主串S中不存在子串T，則函數(shù)返回0。要求設(shè)計主函數(shù)進(jìn)行測試。 3、思考題： 使用串的塊鏈存儲結(jié)構(gòu)，改寫上述程序。實(shí)驗(yàn)四 線性鏈表的實(shí)現(xiàn)及操作1、實(shí)驗(yàn)?zāi)康模?1) 深入理解線性鏈表的邏輯結(jié)構(gòu)和鏈?zhǔn)酱鎯Y(jié)構(gòu)； 2) 掌握線性鏈表的基本操作及應(yīng)用： 3) 培養(yǎng)學(xué)生靈活使用結(jié)構(gòu)解決實(shí)際問題的能力。 2、實(shí)驗(yàn)內(nèi)容： 1) 設(shè)計一個100位以內(nèi)的長整數(shù)加減運(yùn)算的程序。要求如下： 􀁺 輸入輸出要求：每四位一組，組間用逗號

5、分隔； 􀁺 加和減分別用不同的程序?qū)崿F(xiàn) 􀁺 程序應(yīng)考慮輸入數(shù)據(jù)的符號 2) 用循環(huán)鏈表實(shí)現(xiàn)約瑟夫環(huán)問題 3、思考題： 嘗試按照指數(shù)降序排列建立并輸出多項(xiàng)式；能夠完成兩個多項(xiàng)式的相加、相減，并將結(jié)果輸出。實(shí)驗(yàn)五 棧和隊(duì)列的應(yīng)用1、實(shí)驗(yàn)?zāi)康模?掌握棧與隊(duì)列的基本結(jié)構(gòu)和操作方法，培養(yǎng)學(xué)生靈活使用結(jié)構(gòu)解決實(shí)際問題的能力。2、實(shí)驗(yàn)內(nèi)容： 1) 利用棧深度優(yōu)先進(jìn)行迷宮求解。 􀁺 用數(shù)組表示迷宮 􀁺 建立棧，利用棧實(shí)現(xiàn)深度優(yōu)先搜索 2) 利用隊(duì)列寬度優(yōu)先進(jìn)行迷宮求解。 􀁺 用數(shù)組表示迷宮 􀁺 建立隊(duì)列

6、，利用隊(duì)列實(shí)現(xiàn)寬度優(yōu)先搜索 3、思考題： 1) 考慮用棧結(jié)構(gòu)實(shí)現(xiàn)數(shù)制轉(zhuǎn)換問題和字符匹配問題；2) 考慮用隊(duì)列結(jié)構(gòu)實(shí)現(xiàn)楊輝三角輸出問題和回文問題； 3) 利用棧和隊(duì)列模擬停車場管理。 實(shí)驗(yàn)六 二叉樹的實(shí)現(xiàn)及遍歷1、實(shí)驗(yàn)?zāi)康模?1) 掌握二叉樹的定義、結(jié)構(gòu)特征，以及各種存儲結(jié)構(gòu)的特點(diǎn)及使用范圍。2) 掌握用指針類型描述、訪問和處理二叉樹的運(yùn)算。 3) 掌握二叉樹的建立方法 4) 掌握二叉樹遍歷的基本方法（前序、中序、后序） 2、實(shí)驗(yàn)內(nèi)容： 1) 采用二叉樹鏈表作為存儲結(jié)構(gòu)，完成二叉樹的建立，先序、中序和后序以及按層次遍歷的操作，求所有葉子及結(jié)點(diǎn)總數(shù)的操作。2) 輸出樹的深度，最大元，最小元。 3、

7、思考題： 畫出所設(shè)計的二叉樹，以后序遍歷算法為例，畫出執(zhí)行蹤跡示意圖。 實(shí)驗(yàn)七 圖的實(shí)現(xiàn)及遍歷1、實(shí)驗(yàn)?zāi)康模?1) 掌握有向圖和無向圖的概念； 2) 掌握鄰接矩陣和鄰接鏈表建立圖的存儲結(jié)構(gòu)； 3) 掌握DFS及BFS對圖的遍歷操作和過程； 4) 了解圖結(jié)構(gòu)在人工智能、工程等領(lǐng)域的廣泛應(yīng)用。 2、實(shí)驗(yàn)內(nèi)容： 1) 采用鄰接矩陣作為圖的存儲結(jié)構(gòu)，完成有向圖和無向圖的DFS和BFS操作； 2) 采用鄰接鏈表作為圖的存儲結(jié)構(gòu)，完成有向圖和無向圖的DFS和BFS操作。3、思考題： 1) 畫出DFS方法和BFS方法遍歷圖G的示意圖。2) 畫出你所設(shè)計的圖，寫出兩種方法的遍歷序列。 實(shí)驗(yàn)八 查找算法的實(shí)現(xiàn)及比較1、實(shí)驗(yàn)?zāi)康模?1) 掌握線性結(jié)構(gòu)（順序查找、折半查找）上查找的基本思想和算法實(shí)現(xiàn)，了解怎樣對各種查找方法進(jìn)行時間性能（平均查找長度）分析。2) 掌握樹形結(jié)構(gòu)（二叉排序樹）實(shí)現(xiàn)查找的基本思想和算法實(shí)現(xiàn)，了解怎樣對各種查找方法進(jìn)行時間性能（平均查找長