【正文】 d”,pdata)。p=pnext。} } 可參考如下代碼： include “” define MaxSize 100 typedef int ElemType。main(){LinkQueue Q。ElemType e。/*初始化并建立鏈隊列*//*入鏈隊列*/ /*出鏈隊列*/*遍歷鏈隊列*/}DestoryQueue(amp。Q)。getch()。}五、思考與提高？ 試寫一個算法，判別讀入的一個以‘@’為結(jié)束符的字符序列是否是?回文?。實驗三 樹操作一、實驗?zāi)康?，掌握二叉樹的建立與存儲 ，掌握二叉樹的遍歷方法二、實驗內(nèi)容 三、實驗步驟、二叉樹的建立、二叉樹的先序、中序與后序遍歷算法。,并通過調(diào)用函數(shù), 輸出先序遍歷、中序遍歷與后序遍歷的結(jié)果。四、實現(xiàn)提示：首先建立二叉樹的根 結(jié)點，然后建立其左右子樹，直到空子樹為止。、中序遍歷與后序遍歷二叉樹。include include typedef int Status。typedef char ElemType。typedef struct BiTNode { ElemType data。struct BiTNode *lchild,*rchild。}BiTNode,*BiTree。/*建立二叉樹*/BiTree CreateBiTree(BiTree amp。T){ } /*先序遍歷*/ Status PreOrderTraverse(BiTree T){ } /*中序遍歷*/ Status InOrderTraverse(BiTree T){ } /*后序遍歷*/ Status PostOrderTraverse(BiTree T){ }int main(){ BiTree T。CreateBiTree(T)。PreOrderTraverse(T)。printf(“n”)。/*先序遍歷*/ InOrderTraverse(T)。printf(“n”)。/*中序遍歷*/ PostOrderTraverse(T)。printf(“n”)。/*后序遍歷*/return 0。}五、思考與提高編寫遞歸算法，計算二叉樹中葉子結(jié)點的數(shù)目。第五篇：數(shù)據(jù)結(jié)構(gòu)實驗指導(dǎo)書目 錄實驗規(guī)則2 實驗環(huán)境2 實驗報告要求3 實驗一 單鏈表（一）4 實驗二 單鏈表（二）5 實驗三 棧6 實驗四 二叉樹7 實驗五 最短路徑8 實驗六 內(nèi)部排序9實 驗 規(guī) 則為了順利完成實驗教學(xué)任務(wù)，確保人身、設(shè)備的安全，培養(yǎng)嚴(yán)謹(jǐn)、踏實、實事求是的科學(xué)作風(fēng)和愛護(hù)國家財產(chǎn)的優(yōu)良品質(zhì)，特制定以下實驗規(guī)則：實驗前必須充分預(yù)習(xí)，完成指定的預(yù)習(xí)任務(wù)。預(yù)習(xí)要求如下：（1）認(rèn)真閱讀指導(dǎo)書，進(jìn)行必要的設(shè)計與計算。（2）熟悉實驗內(nèi)容。（3）預(yù)先復(fù)習(xí)，并按要求編寫程序。（4）未完成預(yù)習(xí)任務(wù)者不得進(jìn)入實驗室。遵守以下紀(jì)律：（1）在實驗室不得做和實驗無關(guān)的事情。（2）進(jìn)行任課老師指定內(nèi)容以外的實驗，必須經(jīng)指導(dǎo)教師同意。（3）遵守紀(jì)律，不遲到。（4）保持實驗室內(nèi)安靜、整潔，愛護(hù)公物，不許亂寫亂畫。實 驗 環(huán) 境本實驗在386以上的微機(jī)上進(jìn)行。實驗報告要求實驗題目 2．實驗?zāi)康?3．實驗環(huán)境4．實驗內(nèi)容與完成情況（可以附上自主設(shè)計的源程序）5．出現(xiàn)的問題及對問題的解決方案 6．實驗思考：（學(xué)生對本次實驗的收獲的總結(jié)）實驗一 單鏈表（一）一、實驗?zāi)康恼莆站€性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)及其基本操作。二、預(yù)習(xí)要求看懂書上的算法，深入理解鏈表的物理存儲模式和邏輯模式。根據(jù)要求，編寫程序準(zhǔn)備上機(jī)調(diào)試。三、實驗內(nèi)容實現(xiàn)一個簡單的學(xué)生信息管理系統(tǒng)，該系統(tǒng)的功能有：利用單鏈表建立學(xué)生基本信息表瀏覽每個學(xué)生的信息根據(jù)學(xué)號查詢某個學(xué)生的基本信息添加學(xué)生信息到單鏈表中刪除一個學(xué)生的信息四、實現(xiàn)提示設(shè)計結(jié)點的結(jié)構(gòu)體類型，包括學(xué)生的學(xué)號、姓名、年齡、性別；要求設(shè)計一個簡單的菜單界面，根據(jù)需要選擇所要進(jìn)行的操作；構(gòu)造函數(shù)，每一個函數(shù)實現(xiàn)上述的一個功能。實驗二 單鏈表（二）一、實驗?zāi)康恼莆站€性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)及其基本操作。二、預(yù)習(xí)要求看懂書上的算法，深入理解鏈表的物理存儲模式和邏輯模式。根據(jù)要求，編寫程序準(zhǔn)備上機(jī)調(diào)試。三、實驗內(nèi)容實現(xiàn)單鏈表的就地逆置。建立兩個非遞減有序單鏈表，然后合并成一個非遞減鏈表。建立兩個非遞減有序單鏈表，然后合并成一個非遞增鏈表。編寫一個主函數(shù),調(diào)試上述算法。四、選做題、思考題如何用帶表頭結(jié)點的單鏈表作為多項式的存儲表示，實現(xiàn)兩個多項式的相加。約毖夫環(huán)的實現(xiàn)。如何利用文件實現(xiàn)學(xué)生信息的存取。實驗三 棧一、實驗?zāi)康纳钊肓私獠⒄莆諚５奶匦约捌湓趯嶋H中的應(yīng)用；熟練掌握棧的算法實現(xiàn)；運用棧操作求解實際問題。二、預(yù)習(xí)要求看懂書上的算法，深入理解棧的特性和存儲結(jié)構(gòu)，以便在實際問題背景下靈活運用。根據(jù)要求，編寫程序準(zhǔn)備上機(jī)調(diào)試。三、實驗內(nèi)容利用棧實現(xiàn)數(shù)據(jù)的分類，要求當(dāng)輸入為偶數(shù)時進(jìn)棧1，當(dāng)輸入為奇數(shù)時進(jìn)棧2，最后分別從棧1和棧2輸出偶數(shù)和奇數(shù)序列。四、實現(xiàn)提示開辟一個連續(xù)的存儲空間，實現(xiàn)兩個棧順序存儲空間的共享；分別在兩端設(shè)置棧頂指針，并按要求實現(xiàn)棧操作。采用順序存儲實現(xiàn)棧的初始化、入棧、出棧操作。五、選做題、思考題兩棧空間共享時，棧滿的條件是什么？為停車場編制進(jìn)行管理的模擬程序（習(xí)題集P96，）。編寫程序，利用棧實現(xiàn)表達(dá)式求值。實驗四 二叉樹一、實驗?zāi)康耐ㄟ^實踐掌握二叉樹的存儲結(jié)構(gòu)和遍歷思想；掌握二叉樹的常見算法的程序?qū)崿F(xiàn)。二、預(yù)習(xí)要求二叉樹的三種遍歷方法。三、實驗內(nèi)容輸入字符序列，建立二叉鏈表。利用棧，編寫非遞歸算法，編程實現(xiàn)二叉樹的中序遍歷。求二叉樹的葉子結(jié)點個數(shù)。在主函數(shù)中設(shè)計一個簡單的菜單，分別調(diào)試上述算法。四、選做題、思考題如何實現(xiàn)二叉樹的后序遍歷（非遞歸）。如何求二叉樹的高度。實驗五 最短路徑（旅游景點導(dǎo)游咨詢模擬）一、實驗?zāi)康睦脠D的最短路徑原理為用戶提供路徑咨詢，掌握求最短路徑的算法并編程實現(xiàn)。二、預(yù)習(xí)要求學(xué)習(xí)了解圖的存儲結(jié)構(gòu)，掌握求最短路徑的兩種算法。三、實驗內(nèi)容設(shè)計一個旅游景點導(dǎo)游模擬程序，為來訪的客人提供景點最短路徑的信息查詢服務(wù)，任意選取n城市，構(gòu)成一個有向帶權(quán)圖，圖中頂點表示城市，邊上的權(quán)值表示兩點間的距離，根據(jù)用戶指定的始點和終點輸出相應(yīng)的最短路徑。四、實現(xiàn)提示咨詢以用戶和計算機(jī)的對話方式進(jìn)行，由用戶輸入起始點和終點，輸出信息：最短路徑是多少？并指出所經(jīng)過的城市。存儲結(jié)構(gòu)可選用鄰接矩陣。五、選做題、思考題1．如何實現(xiàn)對城市信息進(jìn)行編輯（如：添加或刪除）的功能。2．用鄰接表作存儲結(jié)構(gòu)，求一指定景點出發(fā)，到其余各景點的最短路徑。實驗六 內(nèi)部排序一、實驗?zāi)康闹庇^感受算法的關(guān)鍵字比較次數(shù)和關(guān)鍵字移動次數(shù)。二、預(yù)習(xí)要求常見的排序算法(插入排序、交換排序、選擇排序、歸并排序、基數(shù)排序等)的思想、特點及其適用條件。根據(jù)要求，編寫程序準(zhǔn)備上機(jī)調(diào)試。三、實驗內(nèi)容對直接插入排序和簡單選擇排序算法進(jìn)行關(guān)鍵字比較次數(shù)和關(guān)鍵字移動次數(shù)的比較。利用鏈?zhǔn)酱鎯Y(jié)構(gòu)，編寫程序，實現(xiàn)直接插入排序和冒泡排序。四、實現(xiàn)提示測試數(shù)據(jù)可以為幾組典型的數(shù)據(jù)：正序、逆序、亂序。五、選做題、思考題快速排序算法的非遞歸實現(xiàn)。結(jié)合實驗，理解針對不同待排元素的特點而選擇不同排序方法的重要性。如何對本實驗進(jìn)行時間、空間的復(fù)雜度分析。