NYIST-數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)指導(dǎo)書

1、精品文檔南陽理工學(xué)院數(shù)據(jù)結(jié)構(gòu)上機(jī)實(shí)驗(yàn)指導(dǎo)書（2011 版）軟件學(xué)院軟件工程教研室2011.3。I 歡迎下載精品文檔目錄實(shí)驗(yàn) 1 線性表應(yīng)用2實(shí)驗(yàn) 2 棧和隊(duì)列的應(yīng)用3實(shí)驗(yàn) 3 線性表應(yīng)用6實(shí)驗(yàn) 4 圖論及其應(yīng)用17實(shí)驗(yàn) 5 查找19實(shí)驗(yàn) 6 排序22。I 歡迎下載精品文檔實(shí)驗(yàn) 1 線性表應(yīng)用一、實(shí)驗(yàn)?zāi)康?. 了解和掌握線性表順序存儲(chǔ)和鏈?zhǔn)酱鎯?chǔ)在計(jì)算機(jī)中的表示，基本操做在計(jì)算機(jī)中的實(shí)現(xiàn)。2. 能夠利用線性表結(jié)構(gòu)對(duì)實(shí)際問題進(jìn)行分析建模，利用計(jì)算機(jī)求解。3. 能夠從時(shí)間和空間復(fù)雜度的角度綜合比較線性表兩種存儲(chǔ)結(jié)構(gòu)的不同特點(diǎn)及其適用場(chǎng)合。二、實(shí)驗(yàn)內(nèi)容及步驟1. 利用程序設(shè)計(jì)語言分別實(shí)現(xiàn)順序表和鏈表的抽

2、象數(shù)據(jù)類型。2. 掌握程序分文件（頭文件和實(shí)現(xiàn)文件）書寫的方式。3. 分別用順序表和鏈表實(shí)現(xiàn)課本算法 2.2 ：合并兩個(gè)非遞減有序序列，并對(duì)其時(shí)間性能做出分析。 P21#includec1.htypedef int ElemType;#includec2-1.h#includebo2-1.c#includefunc2-3.c/*包括 equal() 、comp() 、print()、print2()和 print1()函數(shù) */void MergeList(SqList La,SqList Lb,SqList *Lc) /*算法 2.2 */ /*已知線性表 La 和 Lb 中的數(shù)據(jù)元素按值非

3、遞減排列。*/*歸并 La 和 Lb 得到新的線性表Lc，Lc 的數(shù)據(jù)元素也按值非遞減排列*/int i=1,j=1,k=0;int La_len,Lb_len;ElemType ai,bj;InitList(Lc); /*創(chuàng)建空表 Lc */La_len=ListLength(La);Lb_len=ListLength(Lb);while(i=La_len&j=Lb_len) /*表 La 和表 Lb 均非空 */GetElem(La,i,&ai);GetElem(Lb,j,&bj);if(ai=bj)ListInsert(Lc,+k,ai);+i;else。2歡迎下載精品文檔ListIns

4、ert(Lc,+k,bj);+j; /*以下兩個(gè) while 循環(huán)只會(huì)有一個(gè)被執(zhí)行 */while(i=La_len) /*表 La 非空且表 Lb 空 */GetElem(La,i+,&ai);ListInsert(Lc,+k,ai);while(j=Lb_len) /*表 Lb 非空且表 La 空 */GetElem(Lb,j+,&bj);ListInsert(Lc,+k,bj);void main()SqList La,Lb,Lc;int j,a4=3,5,8,11,b7=2,6,8,9,11,15,20;InitList(&La); /*創(chuàng)建空表 La */for(j=1;j=4;j+

5、) /*在表 La 中插入 4 個(gè)元素 */ListInsert(&La,j,aj-1);printf(La= ); /*輸出表 La 的內(nèi)容 */ListTraverse(La,print1);InitList(&Lb); /*創(chuàng)建空表 Lb */for(j=1;j=7;j+) /*在表 Lb 中插入 7 個(gè)元素 */ListInsert(&Lb,j,bj-1);printf(Lb= ); /*輸出表 Lb 的內(nèi)容 */ListTraverse(Lb,print1);MergeList(La,Lb,&Lc);printf(Lc= ); /*輸出表 Lc 的內(nèi)容 */ListTraverse(

6、Lc,print1);實(shí)驗(yàn) 2 棧和隊(duì)列的應(yīng)用一、實(shí)驗(yàn)?zāi)康?. 掌握棧和隊(duì)列這兩種抽象數(shù)據(jù)類型的特點(diǎn)，并能在相應(yīng)的應(yīng)用問題中正確選用它們。3歡迎下載精品文檔2. 熟練掌握棧類型的兩種實(shí)現(xiàn)方法。3. 熟練掌握循環(huán)隊(duì)列和鏈隊(duì)列的基本操作實(shí)現(xiàn)算法。二、實(shí)驗(yàn)內(nèi)容及步驟1. 用程序設(shè)計(jì)語言實(shí)現(xiàn)棧和隊(duì)列的抽象數(shù)據(jù)類型。2. 在第一題的基礎(chǔ)上完成以下選擇：選擇一：1) 設(shè)計(jì)并實(shí)現(xiàn)括號(hào)匹配算法。2) 用隊(duì)列實(shí)現(xiàn)在屏幕上打印楊輝三角。選擇二：分別用棧和隊(duì)列實(shí)現(xiàn)迷宮問題求解。選擇三：分別用棧和隊(duì)列實(shí)現(xiàn)一個(gè)列車調(diào)度系統(tǒng)。1.import java.util.Scanner;public class括號(hào)配對(duì) publ

7、ic static void main(String args)int top=0;/堆指針boolean end=true;/不匹配時(shí)只輸出一次char stack=new char100;/存括號(hào)String s;System.out.println(請(qǐng)輸入表達(dá)式： );Scanner scanner=new Scanner(System.in);s=scanner.next();/表達(dá)式char biao=s.toCharArray();/將字符串轉(zhuǎn)化成字符數(shù)組System.out.println(表達(dá)式 :+s);for(inti=0;ibiao.length&end;i+)/遍歷表達(dá)

8、式中所有字符if(biaoi=()/如果是 ( 則入棧stacktop=(;top+;else if(biaoi=)/如果是 ) 則出棧。4歡迎下載精品文檔if(!(top=0)top-;elseSystem.out.println(括號(hào)不匹配 );end=false;/除循環(huán)兩種可能if(top=0&end)System.out.println(括號(hào)匹配 );/出循環(huán) stack 空else if(top!=0&end)System.out.println(括號(hào)不匹配 );/出循環(huán)時(shí) stack 不空2. #include #define N 11void main()int i,j,aNN

9、;for(i=1;iN;i+)aii=1;ai1=1;for(i=3;iN;i+)for(j=2;ji;j+)aij=ai-1j-1+ai-1j;for(i=1;iN;i+)for(j=1;j=i;j+)printf(%6d,aij);printf(n);。5歡迎下載精品文檔實(shí)驗(yàn) 3 線性表應(yīng)用一、實(shí)驗(yàn)?zāi)康?. 領(lǐng)會(huì)并理解二叉樹的類型定義。2. 熟練掌握二叉樹的主要特性， 。3. 熟練掌握二叉樹的各種遍歷算法，并能靈活運(yùn)用遍歷算法實(shí)現(xiàn)二叉樹的其它操作。4. 熟練掌握二叉樹和樹的各種存儲(chǔ)結(jié)構(gòu)及其建立的算法。二、實(shí)驗(yàn)內(nèi)容及步驟1. 實(shí)現(xiàn)二叉樹的抽象數(shù)據(jù)類型。2. 構(gòu)造一棵二叉樹并用遞歸實(shí)現(xiàn)其先序、

10、中序、后序遍歷算法并驗(yàn)證。3. 用非遞歸算法實(shí)現(xiàn)二叉樹的中序遍歷。一、二叉樹的抽象數(shù)據(jù)類型：ADT BinaryTree/ 數(shù)據(jù)對(duì)象 D： D是具有相同特性的數(shù)據(jù)元素的集合。/ 數(shù)據(jù)關(guān)系 R：/ 若 D=，則 R=，稱 BinaryTree 為空二叉樹；/ 若 D，則 R=H，H是如下二元關(guān)系；/（1）在 D 中存在惟一的稱為根的數(shù)據(jù)元素root ，它在關(guān)系 H 下無前驅(qū)；/（2）若 D-root，則存在 D-root=D1,Dr，且 D1Dr = ；/ （3）若 D1，則 D1中存在惟一的元素 x1， H，且存在 D1 上的關(guān)系 H1 ? H；若Dr，則 Dr 中存在惟一的元素xr ，H，且

11、存在上的關(guān)系Hr ? H；H=,H1,Hr；/ （ 4）(D1,H1) 是一棵符合本定義的二叉樹，稱為根的左子樹； (Dr,Hr) 是一棵符合本定義的二叉樹，稱為根的右子樹。/ 基本操作：InitBiTree( &T )/操作結(jié)果：構(gòu)造空二叉樹T。6歡迎下載精品文檔DestroyBiTree( &T )/ 初始條件：二叉樹 T 已存在。/ 操作結(jié)果：銷毀二叉樹 T。CreateBiTree( &T, definition )/初始條件： definition給出二叉樹 T 的定義。/ 操作結(jié)果：按 definiton 構(gòu)造二叉樹 T。ClearBiTree( &T )/ 初始條件：二叉樹 T

12、存在。/ 操作結(jié)果：將二叉樹 T 清為空樹。BiTreeEmpty( T )/ 初始條件：二叉樹 T 存在。/ 操作結(jié)果：若 T 為空二叉樹，則返回 TRUE，否則返回 FALSE。BiTreeDepth( T )/ 初始條件：二叉樹 T 存在。/ 操作結(jié)果：返回 T 的深度。Root( T )/ 初始條件：二叉樹 T 存在。/ 操作結(jié)果：返回 T 的根。Value( T, e )/ 初始條件：二叉樹 T 存在， e 是 T 中某個(gè)結(jié)點(diǎn)。/ 操作結(jié)果：返回 e 的值。Assign( T, &e, value )/ 初始條件：二叉樹 T 存在， e 是 T 中某個(gè)結(jié)點(diǎn)。/ 操作結(jié)果：結(jié)點(diǎn) e 賦

13、值為 value 。Parent( T, e )/ 初始條件：二叉樹 T 存在， e 是 T 中某個(gè)結(jié)點(diǎn)。/操作結(jié)果：若e 是 T 的非根結(jié)點(diǎn)，則返回它的雙親，否則返回“空 ”。LeftChild( T, e )/ 初始條件：二叉樹 T 存在， e 是 T 中某個(gè)結(jié)點(diǎn)。/ 操作結(jié)果：返回 e 的左孩子。若 e 無左孩子，則返回 “空 ”。7歡迎下載精品文檔RightChild( T, e )/ 初始條件：二叉樹 T 存在， e 是 T 中某個(gè)結(jié)點(diǎn)。/ 操作結(jié)果：返回 e 的右孩子。若 e 無右孩子，則返回 “空 ”。LeftSibling( T, e )/ 初始條件：二叉樹 T 存在， e 是

14、 T 中某個(gè)結(jié)點(diǎn)。/ 操作結(jié)果：返回 e 的左兄弟。若 e 是 T 的左孩子或無左兄弟，則返回 “空 ”。RightSibling( T, e )/ 初始條件：二叉樹 T 存在， e 是 T 中某個(gè)結(jié)點(diǎn)。/ 操作結(jié)果：返回 e 的右兄弟。若 e 是 T 的右孩子或無右兄弟，則返回 “空 ”。InsertChild( T, p, LR, c )/初始條件：二叉樹T 存在， p 指向 T 中某個(gè)結(jié)點(diǎn)， LR為 0 或 1，非空二叉樹c 與 T 不相交且右子樹為空。/操作結(jié)果：根據(jù)LR為 0 或 1，插入 c 為 T 中 p 所指結(jié)點(diǎn)的左或右子樹。p 所指結(jié)點(diǎn)的原有左或右子樹則成為c 的右子樹。De

15、leteChild( T, p, LR )/ 初始條件：二叉樹 T 存在， p 指向 T 中某個(gè)結(jié)點(diǎn)， LR為 0 或 1。/ 操作結(jié)果：根據(jù) LR為 0 或 1，刪除 T 中 p 所指結(jié)點(diǎn)的左或右子樹。PreOrderTraverse( T, visit() )/初始條件：二叉樹T 存在， Visit是對(duì)結(jié)點(diǎn)操作的應(yīng)用函數(shù)。/ 操作結(jié)果：先序遍歷 T，對(duì)每個(gè)結(jié)點(diǎn)調(diào)用函數(shù) Visit 一次且僅一次。一旦 visit() 失敗，則操作失敗。InOrderTraverse( T, visit() )/初始條件：二叉樹T 存在， Visit是對(duì)結(jié)點(diǎn)操作的應(yīng)用函數(shù)。/ 操作結(jié)果：中序遍歷 T，對(duì)每個(gè)結(jié)

16、點(diǎn)調(diào)用函數(shù) Visit 一次且僅一次。一旦 visit() 失敗，則操作失敗。PostOrderTraverse( T, visit() )/初始條件：二叉樹T 存在， Visit是對(duì)結(jié)點(diǎn)操作的應(yīng)用函數(shù)。/ 操作結(jié)果：后序遍歷 T，對(duì)每個(gè)結(jié)點(diǎn)調(diào)用函數(shù) Visit 一次且僅一次。一旦 visit() 失敗，則操作失敗。LevelOrderTraverse( T, visit() )/初始條件：二叉樹T 存在， Visit是對(duì)結(jié)點(diǎn)操作的應(yīng)用函數(shù)。/ 操作結(jié)果：層次遍歷 T，對(duì)每個(gè)結(jié)點(diǎn)調(diào)用函數(shù) Visit 一次且僅一次。一旦 visit() 失敗，則操作失敗。8歡迎下載精品文檔ADT BinaryT

17、ree/ 二、基本操作的實(shí)現(xiàn)：/ 二叉樹的結(jié)點(diǎn)結(jié)構(gòu)體：typedef structTElemType data;struct BiTNode *lchild,*rchild;BiTNode,*BiTree;/ 二叉樹的創(chuàng)建：/*/*按照前序遍歷建立二叉樹*/*/Status CreateBiTree(BiTree &T)/ 按先序次序輸入二叉樹中結(jié)點(diǎn)的值（一個(gè)字符），/ 空格字符表示空樹，構(gòu)造二叉鏈表表示的二叉樹T。char ch;ch = getchar();/scanf(%c,&ch);if(ch = )T = NULL;elseif(!(T = (BiTNode*)malloc(size

18、of(BiTNode)exit(OVERFLOW);T-data = ch;/生成根結(jié)點(diǎn)CreateBiTree(T-lchild);/構(gòu)造左子樹CreateBiTree(T-rchild);/構(gòu)造右子樹return OK;/*/*按層次順序建立一棵二叉樹：隊(duì)列*/。9歡迎下載精品文檔/*/Status LevelCreateBiTree(BiTree &T)BiTree p,s;/p指向父親結(jié)點(diǎn)， s 指向孩子結(jié)點(diǎn)Queue BiNodeQueue;char ch;ch=getchar();if(ch= )return NULL;T=(BiTNode*)malloc(sizeof(BiTNo

19、de); /生成根結(jié)點(diǎn)T-data=ch;EnQueue(BiNodeQueue,T); /用隊(duì)列實(shí)現(xiàn)層次遍歷while(!BiNodeQueue.Empty()DeQueue(BiNodeQueue,p);ch=getchar(); /為了簡(jiǎn)化操作，分別對(duì)左右子結(jié)點(diǎn)進(jìn)行賦值。if(ch!= )/子樹不空則進(jìn)隊(duì)列進(jìn)行擴(kuò)充。下同s=(BiTNode*)malloc(sizeof(BiTNode);s-data=ch;p-lchild=s;EnQueue(BiNodeQueue,s);elsep-lchild=NULL;ch=getchar();if(ch!= )s=(BiTNode*)mallo

20、c(sizeof(BiTNode);s-data=ch;p-rchild=s;EnQueue(BiNodeQueue,s);else。10歡迎下載精品文檔p-rchild=NULL;return OK;/2. 二叉樹的前序遍歷：/*/*按照前序遞歸遍歷二叉樹*/*/Status PreOrderTraverse(BiTree T)if(T)printf(%d,T-data);PreOrderTraverse(T-lchild);PreOrderTraverse(T-rchild);return OK;/*/*按照前序非遞歸遍歷二叉樹：棧*/*/Status PreOrderTraverse(B

21、iTree T)stack S;InitStack(S);BiTree p=T;/p指向當(dāng)前訪問的結(jié)點(diǎn)while(p|!StackEmpty(S)if(p)printf(%c,p-data);Push(S,p);p=p-lchild;else。11歡迎下載精品文檔Pop(S,p);p=p-rchild;return OK;/3.二叉樹的中序遍歷：/*/*按照中序遞歸遍歷二叉樹*/*/Status InOrderTraverse(BiTree T)if(T)InOrderTraverse(T-lchild);printf(%d,T-data);InOrderTraverse(T-rchild);

22、return OK;/*/*按照中序非遞歸遍歷二叉樹*/*/Status InOrderTraverse(BiTree T)stack S;BiTree p;InitStack(S);Push(S, T);while (!StackEmpty(S)while (GetTop(S, p) & p)Push(S, p-lchild);/向左走到盡頭Pop(S, p);/空指針退棧 ( 葉子的左孩子 )if (!StackEmpty(S) / 訪問結(jié)點(diǎn)，向右一步Pop(S, p);。12歡迎下載精品文檔printf(%d,p-data);/ 當(dāng)前根結(jié)點(diǎn)Push(S, p-rchild);return

23、 OK;/*/*按照中序非遞歸遍歷二叉樹*/*/Status InOrderTraverse(BiTree T)stack S;InitStack(S);BiTree p=T;while (p | !StackEmpty(S)if (p)Push(S, p);p = p-lchild; / 非空指針進(jìn)棧，繼續(xù)左進(jìn)else / 上層指針退棧，訪問其所指結(jié)點(diǎn)，再向右進(jìn)Pop(S, p);printf(%d,p-data);p = p-rchild;return OK;/ 二叉樹的后序遍歷：/*/*按照后序遞歸遍歷二叉樹*/*/Status PostOrderTraverse(BiTree T)if

24、(T)。13歡迎下載精品文檔PostOrderTraverse(T-lchild);PostOrderTraverse(T-rchild);printf(%d,T-data);return OK;/*/*按照后序非遞歸遍歷二叉樹*/*/Status PostOrderTraverse(BiTree T)stack S;InitStack(S);BiTree p=T,pre=NULL;while ( p | !StackEmpty(S)if (p)Push(S,p);p = p-left;elsePop(S,p);if (p-right!=NULL & pre!=p-right) /pre指向上

25、次訪問的右結(jié)點(diǎn)，避免再次訪問p=p-right;elseprintf(%d,p-data);pre=p;p=NULL;。14歡迎下載精品文檔/*/*按照后序非遞歸遍歷二叉樹*/*/Status PostOrderTraverse(BiTree T)BiTree p = T,last = NULL;stack S;InitStack(S);Push(S,p);while(!StackEmpty(S)Pop(S,p);if(last = p-left | last = p-right)/左右子樹已經(jīng)訪問完了，該訪問根節(jié)點(diǎn)了printf(%d,p-data);last = p;else if(p-l

26、eft | p-right) /左右子樹未訪問，當(dāng)前節(jié)點(diǎn)入棧，左右節(jié)點(diǎn)入棧Push(S,p);if(p-right)Push(S,p-right);if(p-left)Push(S,p-left);else /當(dāng)前節(jié)點(diǎn)為葉節(jié)點(diǎn)，訪問printf(%d,p-data);last = p;/ 二叉樹的層次遍歷：/*/*按照層次遍歷二叉樹*/。15歡迎下載精品文檔/*/void LevelOrderTraverse(BiTree T)Queue BiNodeQueue;BiTree p=T;EnQueue(BiNodeQueue,p);while(!BiNodeQueue.Empty()DeQueu

27、e(BiNodeQueue,p);if(p)printf(%c,p-data);EnQueue(BiNodeQueue,p-lchild);EnQueue(BiNodeQueue,p-rchild);/ 交換左右子樹：/*/*遞歸法將二叉樹的左右子樹互換*/*/void Exchange(BiTree T)BiTree temp;if(T)Exchange1(T-lchild);Exchange1(T-rchild);temp=T-lchild;T-lchild=T-rchild;T-rchild=temp;/*/*非遞歸法將二叉樹的左右子樹互換*/*/void Exchange(BiTree

28、 T)。16歡迎下載精品文檔stack S;InitStack(S);BiTree p=T,temp;while(p|!StackEmpty(S)if(p)Push(S,p);temp=p-lchild;p-lchild=p-rchild;p-rchild=temp;p=p-lchild;elsePop(S,p);p-rchild;4. 給出一段報(bào)文和每個(gè)字符出現(xiàn)的概率，對(duì)其進(jìn)行哈夫曼編碼和解碼。實(shí)驗(yàn) 4 圖論及其應(yīng)用一、實(shí)驗(yàn)?zāi)康?. 了解圖的基本概念及術(shù)語 , 并能夠熟練掌握?qǐng)D的兩種存儲(chǔ)結(jié)構(gòu) ( 鄰接矩陣和鄰接表 ) 。2. 理解最小生成樹的概念，能按 Prim 算法構(gòu)造最小生成樹。3. 掌

29、握?qǐng)D的兩種遍歷 ( 深度優(yōu)先搜索遍歷和廣度優(yōu)先搜索遍歷 ) 、拓?fù)渑判颉㈥P(guān)鍵路徑、最短路徑的算法思想。17歡迎下載精品文檔二、實(shí)驗(yàn)內(nèi)容及步驟1. 實(shí)現(xiàn)網(wǎng)（有權(quán)圖）的存儲(chǔ)結(jié)構(gòu)。2. 利用 prim 算法構(gòu)造它的最小生成樹。3. 選擇一個(gè)源點(diǎn)，尋找從原點(diǎn)出發(fā)到達(dá)其它頂點(diǎn)的最短路徑。18歡迎下載精品文檔實(shí)驗(yàn)5查找一、實(shí)驗(yàn)?zāi)康?. 理解 查找表 的結(jié)構(gòu)特點(diǎn)以及各種表示方法的適用性。2. 熟練掌握順序查找和折半查找，并對(duì)其性能做出分析。3. 熟練掌握哈希表的構(gòu)造方法，深刻理解哈希表與其它結(jié)構(gòu)的表的實(shí)質(zhì)性的差別。二、 實(shí)驗(yàn)內(nèi)容及步驟1. 實(shí)現(xiàn)查找表的順序查找和折半查找算法。#include #includ

30、e #include const int ARRSIZE= 10015;/ 從小到大排序數(shù)組元素void asort(int *a, int s)int i, j, k, t;for (i = 0; i s-1; +i)k = i;for (j = i + 1; j aj)k = j;if (k != i)t = ai;ai = ak;ak = t;。19歡迎下載精品文檔/ 順序查找，找到返回該元素?cái)?shù)組下標(biāo)，否則返回 -1 int SeqSearch(int *a, int s, int k)int i;for (i = 0; i s; +i)if (k = ai)return i;retur

31、n -1;/ 折半查找，找到返回該元素?cái)?shù)組下標(biāo)，否則返回 -1 int BinSearch(int *a, int s, int k)int low = 0;int high = s - 1;while (low = high)int mid = (low + high) / 2;if (k = amid)return mid;elseif (k amid)high = mid - 1;elselow = mid + 1;return -1;/分塊查找，找到返回該元素?cái)?shù)組下標(biāo)，否則返回-1 ，bs 表示數(shù)列分成的塊數(shù)。20歡迎下載精品文檔int BlkSearch(int *a, int s,