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