《數(shù)據(jù)結(jié)構(gòu)》課程實(shí)驗(yàn)大綱

1、數(shù)據(jù)結(jié)構(gòu)課程實(shí)驗(yàn)大綱 實(shí) 驗(yàn) 學(xué) 時(shí)： 12 課程總學(xué)時(shí)：64 適 用 專 業(yè)：計(jì)算機(jī)科學(xué)與技術(shù)（考試） 實(shí)驗(yàn)項(xiàng)目數(shù)：6 軟件工程（考試） 教育技術(shù)學(xué)（考試） 網(wǎng)絡(luò)工程（考試） 通信工程（考試） 開課教研室(系)： 計(jì)算機(jī)工程 大綱執(zhí)筆人： 一、 本實(shí)驗(yàn)課的基本理論和目的數(shù)據(jù)結(jié)構(gòu)是計(jì)算機(jī)學(xué)科的核心專業(yè)基礎(chǔ)課程，是計(jì)算機(jī)程序設(shè)計(jì)的重要理論和實(shí)踐基礎(chǔ)。本課程討論了軟件設(shè)計(jì)中經(jīng)常遇到的線性表、堆棧、隊(duì)列、串、數(shù)組、二叉樹、圖等典型數(shù)據(jù)結(jié)構(gòu)的設(shè)計(jì)方法以及各種典型排序和查找算法的性能和設(shè)計(jì)方法，并介紹了各種典型數(shù)據(jù)結(jié)構(gòu)的應(yīng)用。數(shù)據(jù)結(jié)構(gòu)課程是一門理論和實(shí)踐相結(jié)合的課程。 上機(jī)實(shí)驗(yàn)是為訓(xùn)練學(xué)生的實(shí)際程序設(shè)計(jì)

2、能力安排的、包含在教學(xué)課時(shí)內(nèi)的教學(xué)內(nèi)容。實(shí)驗(yàn)?zāi)康氖牵?（1）進(jìn)一步深入理解相關(guān)部分的基本概念和授課內(nèi)容。 （2）進(jìn)一步提高實(shí)際動手進(jìn)行程序設(shè)計(jì)的能力。二、 本實(shí)驗(yàn)課的基本要求 （1）認(rèn)真閱讀掌握和實(shí)驗(yàn)相關(guān)的教材內(nèi)容。 （2）自己編程，可以參考別人的程序設(shè)計(jì)方法，但不得抄襲別人的程序。 （3）程序有錯(cuò)誤時(shí)，盡量先自己調(diào)試，在自己能力達(dá)不到時(shí)，可請教同學(xué)或詢問老師。 （4）及時(shí)完成實(shí)驗(yàn)報(bào)告。三、設(shè)置的實(shí)驗(yàn)項(xiàng)目、實(shí)驗(yàn)內(nèi)容和學(xué)時(shí)分配 實(shí)驗(yàn)一 線性表的基本操作和簡單程序（2學(xué)時(shí)） 實(shí)驗(yàn)內(nèi)容如下： （1）熟悉Visual C+ 6.0實(shí)驗(yàn)環(huán)境。 （2）閱讀教材上順序堆棧和鏈?zhǔn)蕉褩５某绦颍⒆约烘I入這些程序

3、。 （3）設(shè)計(jì)一個(gè)使用堆棧的應(yīng)用程序。 （4）分析應(yīng)用程序的運(yùn)行情況。 實(shí)驗(yàn)二 順序棧的實(shí)現(xiàn)（2學(xué)時(shí)）實(shí)驗(yàn)內(nèi)容如下： （1）定義棧的順序存取結(jié)構(gòu)。 （2）分別定義順序棧的基本操作（初始化棧、判?？辗?、入棧、出棧等）。 （3）定義一個(gè)函數(shù)用來判斷算術(shù)表達(dá)式中包含圓括號、方括號是否正確配對。其中，括號配對共有四種情況：左右括號配對次序不正確；右括號多于左括號；左括號多于右括號；左右括號匹配正確。（4）設(shè)計(jì)一個(gè)測試主函數(shù)進(jìn)行測試。 （5）對程序的運(yùn)行結(jié)果進(jìn)行分析。實(shí)驗(yàn)三 折半查找算法設(shè)計(jì)（2學(xué)時(shí)）實(shí)驗(yàn)內(nèi)容如下： （1）分析掌握折半查找算法思想，在此基礎(chǔ)上，設(shè)計(jì)出遞歸算法和循環(huán)結(jié)構(gòu)兩種實(shí)現(xiàn)方法的折半查

4、找函數(shù)。 （2）編寫程序?qū)崿F(xiàn)：在保存于數(shù)組的1000個(gè)有序數(shù)據(jù)元素中查找數(shù)據(jù)元素x是否存在。數(shù)據(jù)元素x要包含兩種情況：一種是數(shù)據(jù)元素x包含在數(shù)組中；另一種是數(shù)據(jù)元素x不包含在數(shù)組中 （3）數(shù)組中數(shù)據(jù)元素的有序化既可以初始賦值時(shí)實(shí)現(xiàn)，也可以設(shè)計(jì)一個(gè)排序函數(shù)實(shí)現(xiàn)。 （4）根據(jù)兩種方法的實(shí)際運(yùn)行時(shí)間，進(jìn)行兩種方法時(shí)間效率的分析對比。實(shí)驗(yàn)四 二叉樹設(shè)計(jì)（2學(xué)時(shí)）實(shí)驗(yàn)內(nèi)容如下：（1）定義二叉鏈存儲結(jié)構(gòu)。 （2）設(shè)計(jì)二叉樹的基本操作（初始化一棵帶頭結(jié)點(diǎn)的二叉樹、左結(jié)點(diǎn)插入、右結(jié)點(diǎn)插入、中序遍歷二叉樹等）。 （3）按照建立一棵實(shí)際二叉樹的操作需要，編寫建立二叉樹、遍歷二叉樹的函數(shù)。 （4）編寫測試主函數(shù)并上

5、機(jī)運(yùn)行。打印出運(yùn)行結(jié)果，并結(jié)合程序運(yùn)行結(jié)果進(jìn)行分析。實(shí)驗(yàn)五 圖的設(shè)計(jì)（2學(xué)時(shí)）實(shí)驗(yàn)內(nèi)容如下： （1）定義鄰接矩陣存儲結(jié)構(gòu)或鄰接表存儲結(jié)構(gòu)。 （2）按照建立一個(gè)帶權(quán)有向圖的操作需要，編寫在鄰接矩陣或鄰接表存儲結(jié)構(gòu)下，帶權(quán)有向圖基本操作的實(shí)現(xiàn)函數(shù)（如初始化圖、在圖中插入一個(gè)結(jié)點(diǎn)、在圖中插入一條邊、在圖中尋找序號為v的結(jié)點(diǎn)的第一個(gè)鄰接結(jié)點(diǎn)、在圖中尋找序號為v1結(jié)點(diǎn)的鄰接結(jié)點(diǎn)v2的下一個(gè)鄰接結(jié)點(diǎn)、圖的深度優(yōu)先遍歷、圖的廣度優(yōu)先遍歷等）。 （3）設(shè)計(jì)一個(gè)測試主函數(shù)，首先創(chuàng)建一個(gè)圖（有n個(gè)結(jié)點(diǎn)和e條邊），然后打印圖的n個(gè)結(jié)點(diǎn)信息和e條邊信息，最后分別打印出圖的深度優(yōu)先遍歷和廣度優(yōu)先遍歷的結(jié)點(diǎn)信息序列。實(shí)驗(yàn)六順序隊(duì)列下的基數(shù)排序算法設(shè)計(jì)（2學(xué)時(shí)）實(shí)驗(yàn)內(nèi)容如下： （1）編寫基于順序隊(duì)列的基數(shù)排序函數(shù)。 （2）設(shè)計(jì)一個(gè)測試主函數(shù)，實(shí)現(xiàn)對基于順序隊(duì)列結(jié)構(gòu)的基數(shù)排序算法的測試。 （3）分析程序的運(yùn)行結(jié)果。 （4）分析比較鏈?zhǔn)疥?duì)列結(jié)構(gòu)的基數(shù)排序算法和順序隊(duì)列結(jié)構(gòu)的基