1、算法與數(shù)據(jù)結(jié)構(gòu)實驗報告算法與數(shù)據(jù)結(jié)構(gòu)實驗報告學(xué)院：計算機與信息學(xué)院專業(yè)班級：姓名：學(xué)號：實驗?zāi)康模赫莆諚：完犃刑攸c、邏輯結(jié)構(gòu)和存儲結(jié)構(gòu)熟悉對棧和隊列的一些基本操作和具體的函數(shù)定義。利用棧和隊列的基本操作完成一定功能的程序。實驗任務(wù)：給出順序棧的類定義和函數(shù)實現(xiàn)，利用棧的基本操作完成十進制數(shù)與其它進制數(shù)的轉(zhuǎn)換。（如）實驗原理：將十進制數(shù)轉(zhuǎn)換為八進制時，采用的是“除取余數(shù)法”，即每次用除所得的余數(shù)作為八進為新的值重復(fù)上述計算，直到為為止。最后的轉(zhuǎn)換結(jié)果。程序清單：DATA_TYPE;DATA_TYPEx);DATA_TYPEdataMAXLEN;DATA_TYPES;請輸入一個十進制數(shù)和所需轉(zhuǎn)換的

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

3、，這樣，當(dāng)將原棧為空時，輸出與輸入次序相反，從而實現(xiàn)了本題的要求。程序清單：DATA_TYPE;DATA_TYPEDATA_TYPEx);DATA_TYPE;DATA_TYPEu;L;n;請任意輸入一個整數(shù);測試數(shù)據(jù)：運行結(jié)果：實驗?zāi)康模豪斫饩€性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)。熟練掌握動態(tài)鏈表結(jié)構(gòu)及有關(guān)算法的設(shè)計。鏈表結(jié)構(gòu)，并設(shè)計相關(guān)算法。實驗任務(wù)：在一個遞增有序的鏈表L中插入一個值為的元素，并保持其遞增有序特性。實驗數(shù)據(jù)：鏈表元素為（）,x分別為，和。實驗原理:給出了要插入的條件，但沒有給定插置的前驅(qū)結(jié)點而不是序號。程序清單:;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);運行結(jié)果：將單鏈表中的奇數(shù)項和偶數(shù)項結(jié)點分解開，顯示結(jié)果，以便對照求解結(jié)果。實驗測試數(shù)據(jù)：第一組數(shù)據(jù)：鏈表為（）第二組數(shù)據(jù)：鏈表為（）數(shù)字來控制，把他們?nèi)〕鰜聿⒅匦逻B起來。程序清單：;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、奇鏈表：實驗結(jié)果：第一組數(shù)據(jù)：第二組數(shù)據(jù)：求兩個遞增有序鏈表L1和L2中的公共元素，并以同樣方式連接成鏈表L3。實驗測試數(shù)據(jù)：第一組數(shù)據(jù)：第一個鏈表為（，）第二個鏈表為（，）第二組數(shù)據(jù)：第一個鏈表元素為（，）第二個鏈表元素為（，）實驗原理：設(shè)置兩個指針怕，分別依次指示A,B表中的元素，其初始值分別為和均非空時，根據(jù)其值的大小關(guān)系可能有如下三種情況。C繼續(xù)A同時也往后移。表明A表中這一元素可能在B表當(dāng)前元素的后面,因此要往B表的后面搜索,故而執(zhí)行然后繼續(xù)搜索。表明A中這一元素在B以繼續(xù)對A表中下一個元素的判斷。反復(fù)執(zhí)行上述比較，直到至少有一個為空為止。此時，剩余的非空部分沒有所需要的公共元素，因

6、而搜索結(jié)束。程序清單：list();&x);i);&L2);list:list()x;*s;輸入一個值：;輸入一個值：;&L2)*u;p;NULL;&C)*u;*s;i)*u;u;L1,L2,L3;共有的元素為：;運行結(jié)果;第一組數(shù)據(jù)：第二組數(shù)據(jù)：實驗?zāi)康模赫莆斩鏄涞膭討B(tài)鏈表存儲結(jié)構(gòu)及表示。掌握二叉樹的三種遍歷算法。運用二叉樹三種遍歷的方法求解有關(guān)問題。二叉樹。后序遍歷。結(jié)點的數(shù)目。前k（）個結(jié)點的值。包括存儲結(jié)點值的數(shù)據(jù)部分及指向兩個孩子結(jié)點的指針，不妨設(shè)為和。對二叉樹的遍歷是在對各子樹分別遍歷的基礎(chǔ)之上法來實現(xiàn)對左、右子樹的遍歷。程序清單：;*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();后序序列：二叉樹的高度為：結(jié)點數(shù)為：運行結(jié)果：實驗?zāi)康模赫莆請D的基本概念。掌握圖的存儲結(jié)構(gòu)的設(shè)計與實現(xiàn)，基本運算的實現(xiàn)。掌握圖的兩種遍歷算法，以及遍歷算法的應(yīng)用。實驗任務(wù)：以鄰接矩陣鄰接表的存儲結(jié)構(gòu)建立圖。對圖進行深度優(yōu)先遍歷廣度優(yōu)先遍歷。求圖中邊的數(shù)目。判斷無向圖是否是連通的

8、。A為階的，其中Aij表示頂點到vj之間是否有邊或?。喝舸嬖?，則Aij為，否則為。鄰接表的表示方式是將每個頂點的鄰接點連成執(zhí)行遍歷時，搜索下一個訪問頂點是從當(dāng)前訪問頂點到一個鄰接點即意味著搜索到一條以為一個端點的邊或弧，故應(yīng)在算法中計數(shù)。程序清單：;E;);Travel_DFS();v););v););i,j;i,j,k;請輸入頂點數(shù)請輸入各頂點的值請輸入邊：ij，i為時結(jié)束w;i;i;k;無向圖不連通。無向圖連通。i;E=0;G;深度遍歷的訪問序列為：;無向圖G的邊數(shù)為：運行結(jié)果：實驗?zāi)康模赫莆枕樞虮淼牟檎曳椒?，尤其是二分查找方法。掌握二叉排序樹的建立及查找。實驗任?wù)：對下列數(shù)據(jù)表，分別采用

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