1、算法與數據結構實驗報告算法與數據結構實驗報告學院：計算機與信息學院專業班級：姓名：學號：實驗目的：掌握棧和隊列特點、邏輯結構和存儲結構熟悉對棧和隊列的一些基本操作和具體的函數定義。利用棧和隊列的基本操作完成一定功能的程序。實驗任務：給出順序棧的類定義和函數實現，利用棧的基本操作完成十進制數與其它進制數的轉換。（如）實驗原理：將十進制數轉換為八進制時，采用的是“除取余數法”，即每次用除所得的余數作為八進為新的值重復上述計算，直到為為止。最后的轉換結果。程序清單：DATA_TYPE;DATA_TYPEx);DATA_TYPEdataMAXLEN;DATA_TYPES;請輸入一個十進制數和所需轉換的

2、進制輸出轉換結果輸出轉換結果測試數據：運行結果：給出順序隊列的類定義和函數實現，并利用隊列計算并打印楊輝三角的前行的內容。一個數是，從第三行開始的其余的數是上一行個數求出下一行的一個數時，其中的前一個便需要刪除，而新求出的數就要入隊。程序清單：DATA_TYPE;get_front(DATA_TYPEDATA_TYPEx);DATA_TYPEdataMAXLEN;(front%MAXLEN=rear%MAXLEN);DATA_TYPEdatarear%MAXLEN=x;Q;運行結果：給出鏈棧的類定義和函數實現，并設計程序完成如下功能：讀入一個有限大小的整數，并讀入各元素的值。個特點就是先進后出

3、，這樣，當將原棧為空時，輸出與輸入次序相反，從而實現了本題的要求。程序清單：DATA_TYPE;DATA_TYPEDATA_TYPEx);DATA_TYPE;DATA_TYPEu;L;n;請任意輸入一個整數;測試數據：運行結果：實驗目的：理解線性表的鏈式存儲結構。熟練掌握動態鏈表結構及有關算法的設計。鏈表結構，并設計相關算法。實驗任務：在一個遞增有序的鏈表L中插入一個值為的元素，并保持其遞增有序特性。實驗數據：鏈表元素為（）,x分別為，和。實驗原理:給出了要插入的條件，但沒有給定插置的前驅結點而不是序號。程序清單:;list();i,*x);list:list()=-=NULL;=0;x;*s

4、,*rear;x;=)=-=x;-=s;=s;x;*p;(p!=NULL);u,*P;L;x;請輸入要插入的值L.insert(x);運行結果：將單鏈表中的奇數項和偶數項結點分解開，顯示結果，以便對照求解結果。實驗測試數據：第一組數據：鏈表為（）第二組數據：鏈表為（）數字來控制，把他們取出來并重新連起來。程序清單：;list();*;list:list()=-=NULL;=0;x;*s,*rear;x;=)=-=x;-=s;=s;x;*p;(p!=NULL);A,&C)*PA,*PB,*PC,*s;PA=-PANULL=s;=s;L,L1,L2;divide(L,L1,L2);原鏈表：偶鏈表：

5、奇鏈表：實驗結果：第一組數據：第二組數據：求兩個遞增有序鏈表L1和L2中的公共元素，并以同樣方式連接成鏈表L3。實驗測試數據：第一組數據：第一個鏈表為（，）第二個鏈表為（，）第二組數據：第一個鏈表元素為（，）第二個鏈表元素為（，）實驗原理：設置兩個指針怕，分別依次指示A,B表中的元素，其初始值分別為和均非空時，根據其值的大小關系可能有如下三種情況。C繼續A同時也往后移。表明A表中這一元素可能在B表當前元素的后面,因此要往B表的后面搜索,故而執行然后繼續搜索。表明A中這一元素在B以繼續對A表中下一個元素的判斷。反復執行上述比較，直到至少有一個為空為止。此時，剩余的非空部分沒有所需要的公共元素，因

6、而搜索結束。程序清單：list();&x);i);&L2);list:list()x;*s;輸入一個值：;輸入一個值：;&L2)*u;p;NULL;&C)*u;*s;i)*u;u;L1,L2,L3;共有的元素為：;運行結果;第一組數據：第二組數據：實驗目的：掌握二叉樹的動態鏈表存儲結構及表示。掌握二叉樹的三種遍歷算法。運用二叉樹三種遍歷的方法求解有關問題。二叉樹。后序遍歷。結點的數目。前k（）個結點的值。包括存儲結點值的數據部分及指向兩個孩子結點的指針，不妨設為和。對二叉樹的遍歷是在對各子樹分別遍歷的基礎之上法來實現對左、右子樹的遍歷。程序清單：;*rchild;*T);*T);*T);*T)

7、;*&T);*T);*T);*T)*T)if(T!=NULL)visit(T);*T)if(T!=NULL)visit(T);*T)if(T!=NULL)visit(T);*&T)T=NULL;b;a;*T)T=NULL),+;*TT=NULLT-+T-+1;t;#表示空：;先序序列：中序序列：;t.inorder();后序序列：二叉樹的高度為：結點數為：運行結果：實驗目的：掌握圖的基本概念。掌握圖的存儲結構的設計與實現，基本運算的實現。掌握圖的兩種遍歷算法，以及遍歷算法的應用。實驗任務：以鄰接矩陣鄰接表的存儲結構建立圖。對圖進行深度優先遍歷廣度優先遍歷。求圖中邊的數目。判斷無向圖是否是連通的

8、。A為階的，其中Aij表示頂點到vj之間是否有邊或弧：若存在，則Aij為，否則為。鄰接表的表示方式是將每個頂點的鄰接點連成執行遍歷時，搜索下一個訪問頂點是從當前訪問頂點到一個鄰接點即意味著搜索到一條以為一個端點的邊或弧，故應在算法中計數。程序清單：;E;);Travel_DFS();v););v););i,j;i,j,k;請輸入頂點數請輸入各頂點的值請輸入邊：ij，i為時結束w;i;i;k;無向圖不連通。無向圖連通。i;E=0;G;深度遍歷的訪問序列為：;無向圖G的邊數為：運行結果：實驗目的：掌握順序表的查找方法，尤其是二分查找方法。掌握二叉排序樹的建立及查找。實驗任務：對下列數據表，分別采用

9、二分查找算法實現查并以二分查找的判定樹來解釋。實驗測試數據：數據表為查找的元素分別為：，實驗原理：設查找區域的首尾下標分別用變量和和該區域的中間元素的關鍵字進行比較。程序清單：or;list();/初始化list:list()/求表長/求關鍵值表長/建表x;請依次輸入順序表中各個元素的值，結束符為/建立關鍵值表x;請依次輸入所搜索的關鍵字，結束符為/顯示表i;/二分查找法list:j;/初始化查找區域元素下標是：查找失敗/返回查找失敗的標志0;L;運行結果:實驗任務：遍歷序列。實驗測試數據：構建二叉排序樹的輸入序列如下：，設計算法在二叉排序樹中查找指定值的結點。在任務所建立的二叉排序樹中分別查找下列元素：，程序清單：;*;*if(t!=NULL)*T,int查找失敗！0;查找成功！0;*p=NULL;n;輸入數據個數輸入數據：a;中序遍歷:輸入要查找的值：實驗結果：實驗任務：取方法對排序過程中數據的比較和移動次數的影響。測試數據：數組元素分別為：（）后再對整個序列進行直接插入排序。程序清單：;list();list:list()x;請依次輸入順序表中各個元素的值，結束符為i;/希爾排序i,j,dh;n;實驗結果：實驗任務：實現堆排序算法，給出排序結果。測試數據：）用篩選