數(shù)據(jù)結(jié)構(gòu)上機(jī)實驗指導(dǎo)

1、數(shù)據(jù)結(jié)構(gòu)課程上機(jī)實驗指導(dǎo)書實驗【實驗名稱】 順序表的基本算法【實驗?zāi)康摹?創(chuàng)建一個順序表，掌握線性表順序存儲的特點。設(shè)計和驗證順序表的查找、 插入、 刪除 算法。【實驗要求】（ 1） 從鍵盤讀入一組整數(shù)， 按輸入順序形成順序表。 并將創(chuàng)建好的順序表元素依次 打印在屏幕上。（2）設(shè)計一個帶選擇菜單的主函數(shù)， 菜單中具備任意選擇刪除、 插入、 查找數(shù)據(jù)元 素的功能。（ 3） 當(dāng)選擇刪除功能時， 從鍵盤讀入欲刪除的元素位置或元素值， 按指定方式刪除； 當(dāng)選擇插入功能時，從鍵盤讀入新元素值和被插入位置，在指定位置插入； 當(dāng)選擇查找功能時，從鍵盤讀入欲查找的元素值，返回其位置序號。（ 4） 每種操作結(jié)束

2、后，都能在屏幕上打印出此時順序表元素的遍歷結(jié)果?！緦嶒灢襟E】1、實驗前先寫好算法。2、上機(jī)編寫程序。3、編譯。4、調(diào)試。例程： 書上參考算法 2-1，2-4，2-5，2-6，2-8！帶菜單的主函數(shù)參考書上 2.5 綜合實例！ 注意：順序表的結(jié)構(gòu)體！typedef structdatatype itemslistsize;int length;SpList;實驗二【實驗名稱】 單鏈表的基本算法【實驗?zāi)康摹縿?chuàng)建一個單鏈表，掌握線性表鏈?zhǔn)酱鎯Φ奶攸c。設(shè)計和驗證鏈表的查找、插入、刪除、 求表長的算法?！緦嶒炓蟆浚?1） 從鍵盤讀入一組整數(shù)， 按輸入順序形成單鏈表。 并將創(chuàng)建好的單鏈表元素依次 打印在

3、屏幕上。 （注意：選擇頭插法或者尾插法！ ）（2） 設(shè)計一個帶選擇功能菜單的主函數(shù)， 菜單中至少具備任意選擇刪除、 插入、 查 找數(shù)據(jù)元素，和求單鏈表表長等幾項功能。（ 3） 當(dāng)選擇刪除功能時， 從鍵盤讀入欲刪除的元素位置， 按指定位置刪除； 當(dāng)選擇 插入功能時，從鍵盤讀入新元素值和被插入位置，在指定位置插入；當(dāng)選擇 查找功能時，從鍵盤讀入欲查找的元素值，返回其位置序號；當(dāng)選擇求表長 功能時，返回該單鏈表表長的數(shù)值。（ 4） 每種操作結(jié)束后，都能在屏幕上打印出此時單鏈表元素的遍歷結(jié)果?！緦嶒灢襟E】1、實驗前先寫好算法。2、上機(jī)編寫程序。3、編譯。4、調(diào)試。例程： 書上參考算法 2-10，2-1

4、2， 2-13，2-15，2-17！帶菜單的主函數(shù)參考書上 2.5 綜合實 例！另外，注意，指針的初始化！指針的操作必須謹(jǐn)慎！鏈表的結(jié)構(gòu)體如下：typedef struct NodeDatatype ch;struct Node *next;LNode, *Pnode, *Linklist;實驗三【實驗名稱】 回文判斷的算法 【實驗?zāi)康摹坷脳：完犃械牟僮鱽韺崿F(xiàn)對字符序列是否是一個回文序列的判斷。設(shè)計和驗證入棧、 出棧及入隊、出隊的算法?！緦嶒炓蟆浚?1）從鍵盤讀入一組字符序列，按輸入順序入隊列到鏈?zhǔn)疥犃?A 中。并將創(chuàng)建好的 A 隊列中元素依次遍歷，打印在屏幕上。（ 2）將字符序列從 A

5、隊列出隊列，壓入到一個順序棧 B 中。（3）再將字符序列從順序棧 B 中出棧，所有元素依次遍歷，打印在屏幕上。（4）將 A，B 的元素值逐一比較，判斷是否一致。若一致則是回文，并將判定結(jié)果打印到屏幕上。注意：指定采用順序棧和鏈隊列的結(jié)構(gòu)來實現(xiàn)?！緦嶒灢襟E】1、設(shè)計算法2、編寫程序3、編譯4、調(diào)試?yán)蹋?棧的各種操作如算法3-3， 3-4，隊列的操作比如算法3-15， 3-16 等等?？赡苡玫降淖址瘮?shù)，比如 strlen （） , strcmp （）等。順序棧：typedef struct char itemsstacksize; int top;SqStack;鏈隊列：typedef st

6、ruct QNode char data; struct QNode *next;LQNode , *PQNode;typedef structPQNode front ,rear;LinkQueue;實驗四【實驗名稱】 哈希查找【實驗?zāi)康摹框炞C哈希查找算法【實驗要求】（1） 先創(chuàng)建一個數(shù)組類型的順序表，以 1 作為結(jié)束。從鍵盤輸入一組數(shù)據(jù)元素后， 按順序表的遍歷輸出，并打印顯示。（ 2） 再以哈希函數(shù)方式， 將數(shù)據(jù)元素放入哈希表中， 并將哈希表輸出， 并打印顯示。 采用線性探測法處理沖突。 注意：哈希表的下標(biāo)和數(shù)據(jù)內(nèi)容都顯示到屏幕上。（ 3） 輸入需要查找的任意元素的關(guān)鍵字，查找并輸出該元素

7、的位置下標(biāo)序列號。若 有沖突，顯示它原來的下標(biāo)位置和新的下標(biāo)位置。若沒有，也將找不到的信息 反饋出來。注意：用線性探測法處理沖突。【實驗步驟】1、設(shè)計算法2、編寫程序3、編譯4、調(diào)試?yán)蹋簠⒖紩系乃惴?P274-277 的多個算法。比如：哈希表的地址區(qū)間為 0-17，哈希函數(shù)為 h（key）=K%17 。采用線性探測法處理沖突。 若給定關(guān)鍵字序列： 26，25，72，38，8，18，59。請問搜索 59 在幾號下標(biāo)位置，需要查找 多少次？實驗五實驗名稱】 排序操作實驗?zāi)康摹框炞C各種排序算法。在調(diào)試中體會排序過程。實驗要求】（ 1） 從鍵盤讀入一組無序數(shù)據(jù)，按輸入順序先創(chuàng)建一個線性表。（ 2）

8、 用帶菜單的主函數(shù)任意選擇一種排序算法將該表進(jìn)行遞增排序。 實驗步驟】1、設(shè)計算法2、編寫程序3、編譯4、調(diào)試?yán)蹋?冒泡排序法、直接選擇排序法、直接插入排序?qū)嶒灹ňC合）【實驗名稱】 學(xué)生成績表的操作【實驗?zāi)康摹考訌?qiáng)線性表操作的訓(xùn)練?！緦嶒炓蟆浚?1） 先創(chuàng)建一個數(shù)組類型或鏈表類型的線性表，其中每個數(shù)據(jù)元素包括的數(shù)據(jù)項內(nèi) 容有：學(xué)生學(xué)號，姓名，及語文，數(shù)學(xué)，英語三門課程的分?jǐn)?shù)。（ 2） 利用鍵盤輸入數(shù)字在主函數(shù)中選擇菜單的功能，可以對學(xué)生成績表進(jìn)行多項操 作，比如：增加一個學(xué)生的信息，刪除一個學(xué)生的信息，查找一個學(xué)生的信息， 或者按某門課程分?jǐn)?shù)進(jìn)行學(xué)生的排序等等。（ 3） 每個操作完成后，在屏幕上將該線性表的數(shù)值完全輸出?！緦嶒灢襟E】5、設(shè)計算法6、編寫程序7、編譯8、調(diào)試?yán)蹋?線性表的各種操作數(shù)據(jù)結(jié)構(gòu)課程實驗報告要求實驗題目班級姓名學(xué)號日期、需求分析1.2.3.程序的功能； 輸入輸出的要求； 測試數(shù)據(jù)。、概要設(shè)計1.2.本程序所用的抽象數(shù)據(jù)類型的定義； 主