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

資料內(nèi)容僅供您學(xué)習(xí)參考，如有不當(dāng)之處，請(qǐng)聯(lián)系改正或者刪除。南陽(yáng)理工學(xué)院數(shù)據(jù)結(jié)構(gòu)上機(jī)實(shí)驗(yàn)指導(dǎo)書(shū)()軟件學(xué)院·軟件工程教研室.3目錄TOC\o"1-1"\h\u實(shí)驗(yàn)1線性表應(yīng)用 2實(shí)驗(yàn)2棧和隊(duì)列的應(yīng)用 2實(shí)驗(yàn)3線性表應(yīng)用 3實(shí)驗(yàn)4圖論及其應(yīng)用 3實(shí)驗(yàn)5查找 4實(shí)驗(yàn)6排序 4實(shí)驗(yàn)1線性表應(yīng)用一、實(shí)驗(yàn)?zāi)康牧私夂驼莆站€性表順序存儲(chǔ)和鏈?zhǔn)酱鎯?chǔ)在計(jì)算機(jī)中的表示,基本操做在計(jì)算機(jī)中的實(shí)現(xiàn)。能夠利用線性表結(jié)構(gòu)對(duì)實(shí)際問(wèn)題進(jìn)行分析建模,利用計(jì)算機(jī)求解。能夠從時(shí)間和空間復(fù)雜度的角度綜合比較線性表兩種存儲(chǔ)結(jié)構(gòu)的不同特點(diǎn)及其適用場(chǎng)合。二、實(shí)驗(yàn)內(nèi)容及步驟利用程序設(shè)計(jì)語(yǔ)言分別實(shí)現(xiàn)順序表和鏈表的抽象數(shù)據(jù)類型。掌握程序分文件(頭文件和實(shí)現(xiàn)文件)書(shū)寫(xiě)的方式。分別用順序表和鏈表實(shí)現(xiàn)課本算法2.2:合并兩個(gè)非遞減有序序列,并對(duì)其時(shí)間性能做出分析。P21#include"c1.h"typedefintElemType;#include"c2-1.h"#include"bo2-1.c"#include"func2-3.c"/*包括equal()、comp()、print()、print2()和print1()函數(shù)*/voidMergeList(SqListLa,SqListLb,SqList*Lc)/*算法2.2*/{/*已知線性表La和Lb中的數(shù)據(jù)元素按值非遞減排列。*//*歸并La和Lb得到新的線性表Lc,Lc的數(shù)據(jù)元素也按值非遞減排列*/inti=1,j=1,k=0;intLa_len,Lb_len;ElemTypeai,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{ListInsert(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);}}voidmain(){SqListLa,Lb,Lc;intj,a[4]={3,5,8,11},b[7]={2,6,8,9,11,15,20};InitList(&La);/*創(chuàng)立空表La*/for(j=1;j<=4;j++)/*在表La中插入4個(gè)元素*/ListInsert(&La,j,a[j-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,b[j-1]);printf("Lb=");/*輸出表Lb的內(nèi)容*/ListTraverse(Lb,print1);MergeList(La,Lb,&Lc);printf("Lc=");/*輸出表Lc的內(nèi)容*/ListTraverse(Lc,print1);}實(shí)驗(yàn)2棧和隊(duì)列的應(yīng)用一、實(shí)驗(yàn)?zāi)康恼莆諚：完?duì)列這兩種抽象數(shù)據(jù)類型的特點(diǎn),并能在相應(yīng)的應(yīng)用問(wèn)題中正確選用它們。熟練掌握棧類型的兩種實(shí)現(xiàn)方法。熟練掌握循環(huán)隊(duì)列和鏈隊(duì)列的基本操作實(shí)現(xiàn)算法。二、實(shí)驗(yàn)內(nèi)容及步驟用程序設(shè)計(jì)語(yǔ)言實(shí)現(xiàn)棧和隊(duì)列的抽象數(shù)據(jù)類型。在第一題的基礎(chǔ)上完成以下選擇:選擇一:設(shè)計(jì)并實(shí)現(xiàn)括號(hào)匹配算法。用隊(duì)列實(shí)現(xiàn)在屏幕上打印楊輝三角。選擇二:分別用棧和隊(duì)列實(shí)現(xiàn)迷宮問(wèn)題求解。選擇三:分別用棧和隊(duì)列實(shí)現(xiàn)一個(gè)列車調(diào)度系統(tǒng)。1.importjava.util.Scanner;publicclass括號(hào)配對(duì){publicstaticvoidmain(Stringargs[]){inttop=0;//堆指針booleanend=true;//不匹配時(shí)只輸出一次charstack[]=newchar[100];//存括號(hào)Strings;System.out.println("請(qǐng)輸入表示式:");Scannerscanner=newScanner(System.in);s=scanner.next();//表示式charbiao[]=s.toCharArray();//將字符串轉(zhuǎn)化成字符數(shù)組System.out.println("表示式:"+s);for(inti=0;i<biao.length&&end;i++)//遍歷表示式中所有字符{if(biao[i]=='(')//如果是(則入棧{stack[top]='(';top++;}elseif(biao[i]==')')//如果是)則出棧{if(!(top==0))top--;else{System.out.println("括號(hào)不匹配");end=false;}}}//除循環(huán)兩種可能if(top==0&&end)System.out.println("括號(hào)匹配");//出循環(huán)stack空elseif(top!=0&&end)System.out.println("括號(hào)不匹配");//出循環(huán)時(shí)stack不空}}2.#include<stdio.h>#defineN11voidmain(){inti,j,a[N][N];for(i=1;i<N;i++){a[i][i]=1;a[i][1]=1;}for(i=3;i<N;i++)for(j=2;j<i;j++)a[i][j]=a[i-1][j-1]+a[i-1][j];for(i=1;i<N;i++){for(j=1;j<=i;j++)printf("%6d",a[i][j]);printf("\n");}}實(shí)驗(yàn)3線性表應(yīng)用一、實(shí)驗(yàn)?zāi)康念I(lǐng)會(huì)并理解二叉樹(shù)的類型定義。熟練掌握二叉樹(shù)的主要特性,。熟練掌握二叉樹(shù)的各種遍歷算法,并能靈活運(yùn)用遍歷算法實(shí)現(xiàn)二叉樹(shù)的其它操作。熟練掌握二叉樹(shù)和樹(shù)的各種存儲(chǔ)結(jié)構(gòu)及其建立的算法。二、實(shí)驗(yàn)內(nèi)容及步驟實(shí)現(xiàn)二叉樹(shù)的抽象數(shù)據(jù)類型。構(gòu)造一棵二叉樹(shù)并用遞歸實(shí)現(xiàn)其先序、中序、后序遍歷算法并驗(yàn)證。用非遞歸算法實(shí)現(xiàn)二叉樹(shù)的中序遍歷。一、二叉樹(shù)的抽象數(shù)據(jù)類型:

ADTBinaryTree{

//數(shù)據(jù)對(duì)象D:D是具有相同特性的數(shù)據(jù)元素的集合。

//數(shù)據(jù)關(guān)系R:

//

若D=Φ,則R=Φ,稱BinaryTree為空二叉樹(shù);

//

若D≠Φ,則R={H},H是如下二元關(guān)系;

//

(1)在D中存在惟一的稱為根的數(shù)據(jù)元素root,它在關(guān)系H下無(wú)前驅(qū);

//

(2)若D-{root}≠Φ,則存在D-{root}={D1,Dr},且D1∩Dr=Φ;

//

(3)若D1≠Φ,則D1中存在惟一的元素x1,<root,x1>∈H,且存在D1上的關(guān)系H1?H;若Dr≠Φ,則Dr中存在惟一的元素xr,<root,xr>∈H,且存在上的關(guān)系Hr?H;H={<root,x1>,<root,xr>,H1,Hr};

//

(4)(D1,{H1})是一棵符合本定義的二叉樹(shù),稱為根的左子樹(shù);(Dr,{Hr})是一棵符合本定義的二叉樹(shù),稱為根的右子樹(shù)。

//基本操作:

InitBiTree(&T)

//操作結(jié)果:構(gòu)造空二叉樹(shù)T。

DestroyBiTree(&T)

//

初始條件:二叉樹(shù)T已存在。

//

操作結(jié)果:銷毀二叉樹(shù)T。

CreateBiTree(&T,definition)

//

初始條件:definition給出二叉樹(shù)T的定義。

//

操作結(jié)果:按definiton構(gòu)造二叉樹(shù)T。

ClearBiTree(&T)

//

初始條件:二叉樹(shù)T存在。

//

操作結(jié)果:將二叉樹(shù)T清為空樹(shù)。

BiTreeEmpty(T)

//

初始條件:二叉樹(shù)T存在。

//

操作結(jié)果:若T為空二叉樹(shù),則返回TRUE,否則返回FALSE。

BiTreeDepth(T)

//

初始條件:二叉樹(shù)T存在。

//

操作結(jié)果:返回T的深度。

Root(T)

//

初始條件:二叉樹(shù)T存在。

//

操作結(jié)果:返回T的根。

Value(T,e)

//

初始條件:二叉樹(shù)T存在,e是T中某個(gè)結(jié)點(diǎn)。

//

操作結(jié)果:返回e的值。

Assign(T,&e,value)

//

初始條件:二叉樹(shù)T存在,e是T中某個(gè)結(jié)點(diǎn)。

//

操作結(jié)果:結(jié)點(diǎn)e賦值為value。

Parent(T,e)

//

初始條件:二叉樹(shù)T存在,e是T中某個(gè)結(jié)點(diǎn)。

//

操作結(jié)果:若e是T的非根結(jié)點(diǎn),則返回它的雙親,否則返回”空”。

LeftChild(T,e)

//

初始條件:二叉樹(shù)T存在,e是T中某個(gè)結(jié)點(diǎn)。

//

操作結(jié)果:返回e的左孩子。若e無(wú)左孩子,則返回”空”。

RightChild(T,e)

//

初始條件:二叉樹(shù)T存在,e是T中某個(gè)結(jié)點(diǎn)。

//

操作結(jié)果:返回e的右孩子。若e無(wú)右孩子,則返回”空”。

LeftSibling(T,e)

//

初始條件:二叉樹(shù)T存在,e是T中某個(gè)結(jié)點(diǎn)。

//

操作結(jié)果:返回e的左兄弟。若e是T的左孩子或無(wú)左兄弟,則返回”空”。

RightSibling(T,e)

//

初始條件:二叉樹(shù)T存在,e是T中某個(gè)結(jié)點(diǎn)。

//

操作結(jié)果:返回e的右兄弟。若e是T的右孩子或無(wú)右兄弟,則返回”空”。

InsertChild(T,p,LR,c)

//

初始條件:二叉樹(shù)T存在,p指向T中某個(gè)結(jié)點(diǎn),LR為0或1,非空二叉樹(shù)c與T不相交且右子樹(shù)為空。

//

操作結(jié)果:根據(jù)LR為0或1,插入c為T中p所指結(jié)點(diǎn)的左或右子樹(shù)。p所指結(jié)點(diǎn)的原有左或右子樹(shù)則成為c的右子樹(shù)。

DeleteChild(T,p,LR)

//

初始條件:二叉樹(shù)T存在,p指向T中某個(gè)結(jié)點(diǎn),LR為0或1。

//

操作結(jié)果:根據(jù)LR為0或1,刪除T中p所指結(jié)點(diǎn)的左或右子樹(shù)。

PreOrderTraverse(T,visit())

//

初始條件:二叉樹(shù)T存在,Visit是對(duì)結(jié)點(diǎn)操作的應(yīng)用函數(shù)。

//

操作結(jié)果:先序遍歷T,對(duì)每個(gè)結(jié)點(diǎn)調(diào)用函數(shù)Visit一次且僅一次。一旦visit()失敗,則操作失敗。

InOrderTraverse(T,visit())

//

初始條件:二叉樹(shù)T存在,Visit是對(duì)結(jié)點(diǎn)操作的應(yīng)用函數(shù)。

//

操作結(jié)果:中序遍歷T,對(duì)每個(gè)結(jié)點(diǎn)調(diào)用函數(shù)Visit一次且僅一次。一旦visit()失敗,則操作失敗。

PostOrderTraverse(T,visit())

//

初始條件:二叉樹(shù)T存在,Visit是對(duì)結(jié)點(diǎn)操作的應(yīng)用函數(shù)。

//

操作結(jié)果:后序遍歷T,對(duì)每個(gè)結(jié)點(diǎn)調(diào)用函數(shù)Visit一次且僅一次。一旦visit()失敗,則操作失敗。

LevelOrderTraverse(T,visit())

//

初始條件:二叉樹(shù)T存在,Visit是對(duì)結(jié)點(diǎn)操作的應(yīng)用函數(shù)。

//

操作結(jié)果:層次遍歷T,對(duì)每個(gè)結(jié)點(diǎn)調(diào)用函數(shù)Visit一次且僅一次。一旦visit()失敗,則操作失敗。

}ADTBinaryTree

//

//二、基本操作的實(shí)現(xiàn):

//二叉樹(shù)的結(jié)點(diǎn)結(jié)構(gòu)體:typedefstruct{

TElemTypedata;

structBiTNode*lchild,*rchild;

}BiTNode,*BiTree;//二叉樹(shù)的創(chuàng)立:

/*******************************************/

/*

按照前序遍歷建立二叉樹(shù)

*/

/*******************************************/

StatusCreateBiTree(BiTree&T)

{

//按先序次序輸入二叉樹(shù)中結(jié)點(diǎn)的值(一個(gè)字符),

//空格字符表示空樹(shù),構(gòu)造二叉鏈表表示的二叉樹(shù)T。

charch;

ch=getchar();//scanf("%c",&ch);

if(ch=='')

T=NULL;

else

{

if(!(T=(BiTNode*)malloc(sizeof(BiTNode))))

exit(OVERFLOW);

T->data=ch;

//生成根結(jié)點(diǎn)

CreateBiTree(T->lchild);

//構(gòu)造左子樹(shù)

CreateBiTree(T->rchild);

//構(gòu)造右子樹(shù)

}

returnOK;

}

/************************************************************/

/*

按層次順序建立一棵二叉樹(shù):隊(duì)列

*/

/************************************************************/

StatusLevelCreateBiTree(BiTree&T)

{

BiTreep,s;//p指向父親結(jié)點(diǎn),s指向孩子結(jié)點(diǎn)

QueueBiNodeQueue;

charch;

ch=getchar();

if(ch=='')

{

returnNULL;

}

T=(BiTNode*)malloc(sizeof(BiTNode));//生成根結(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!='')//子樹(shù)不空則進(jìn)隊(duì)列進(jìn)行擴(kuò)充。下同

{

s=(BiTNode*)malloc(sizeof(BiTNode));

s->data=ch;

p->lchild=s;

EnQueue(BiNodeQueue,s);

}

else

{

p->lchild=NULL;

}

ch=getchar();

if(ch!='')

{

s=(BiTNode*)malloc(sizeof(BiTNode));

s->data=ch;

p->rchild=s;

EnQueue(BiNodeQueue,s);

}

else

{

p->rchild=NULL;

}

}

returnOK;

}

//2.二叉樹(shù)的前序遍歷:

/*******************************************/

/*

按照前序遞歸遍歷二叉樹(shù)

*/

/*******************************************/

StatusPreOrderTraverse(BiTreeT)

{

if(T)

{

printf("%d",T->data);

PreOrderTraverse(T->lchild);

PreOrderTraverse(T->rchild);

}

returnOK;

}

/*******************************************/

/*

按照前序非遞歸遍歷二叉樹(shù):棧

*/

/*******************************************/

StatusPreOrderTraverse(BiTreeT)

{

stackS;

InitStack(S);

BiTreep=T;

//p指向當(dāng)前訪問(wèn)的結(jié)點(diǎn)

while(p||!StackEmpty(S))

{

if(p)

{

printf("%c",p->data);

Push(S,p);

p=p->lchild;

}

else

{

Pop(S,p);

p=p->rchild;

}

}

returnOK;

}

//3.二叉樹(shù)的中序遍歷:

/*******************************************/

/*

按照中序遞歸遍歷二叉樹(shù)

*/

/*******************************************/

StatusInOrderTraverse(BiTreeT)

{

if(T)

{

InOrderTraverse(T->lchild);

printf("%d",T->data);

InOrderTraverse(T->rchild);

}

returnOK;

}

/*******************************************/

/*

按照中序非遞歸遍歷二叉樹(shù)

*/

/*******************************************/

StatusInOrderTraverse(BiTreeT)

{

stackS;

BiTreep;

InitStack(S);

Push(S,T);

while(!StackEmpty(S))

{

while(GetTop(S,p)&&p)

Push(S,p->lchild);

//向左走到盡頭

Pop(S,p);

//空指針退棧(葉子的左孩子)

if(!StackEmpty(S))

{

//訪問(wèn)結(jié)點(diǎn),向右一步

Pop(S,p);

printf("%d",p->data);

//當(dāng)前根結(jié)點(diǎn)

Push(S,p->rchild);

}

}

returnOK;

}

/*******************************************/

/*

按照中序非遞歸遍歷二叉樹(shù)

*/

/*******************************************/

StatusInOrderTraverse(BiTreeT)

{

stackS;

InitStack(S);

BiTreep=T;

while(p||!StackEmpty(S))

{

if(p)

{

Push(S,p);

p=p->lchild;

}

//非空指針進(jìn)棧,繼續(xù)左進(jìn)

else

{

//上層指針退棧,訪問(wèn)其所指結(jié)點(diǎn),再向右進(jìn)

Pop(S,p);

printf("%d",p->data);

p=p->rchild;

}

}

returnOK;

}

//二叉樹(shù)的后序遍歷:

/*******************************************/

/*

按照后序遞歸遍歷二叉樹(shù)

*/

/*******************************************/

StatusPostOrderTraverse(BiTreeT)

{

if(T)

{

PostOrderTraverse(T->lchild);

PostOrderTraverse(T->rchild);

printf("%d",T->data);

}

returnOK;

}

/*******************************************/

/*

按照后序非遞歸遍歷二叉樹(shù)

*/

/*******************************************/

StatusPostOrderTraverse(BiTreeT)

{

stackS;

InitStack(S);

BiTreep=T,pre=NULL;

while(p||!StackEmpty(S))

{

if(p)

{

Push(S,p);

p=p->left;

}

else

{

Pop(S,p);

if(p->right!=NULL&&pre!=p->right)

{//pre指向上次訪問(wèn)的右結(jié)點(diǎn),避免再次訪問(wèn)

p=p->right;

}

else

{

printf("%d",p->data);

pre=p;

p=NULL;

}

}

}

}

/*******************************************/

/*

按照后序非遞歸遍歷二叉樹(shù)

*/

/*******************************************/

StatusPostOrderTraverse(BiTreeT)

{

BiTreep=T,last=NULL;

stackS;

InitStack(S);

Push(S,p);

while(!StackEmpty(S))

{

Pop(S,p);

if(last==p->left||last==p->right)//左右子樹(shù)已經(jīng)訪問(wèn)完了,該訪問(wèn)根節(jié)點(diǎn)了

{

printf("%d",p->data);

last=p;

}

elseif(p->left||p->right)//左右子樹(shù)未訪問(wèn),當(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),訪問(wèn)

{

printf("%d",p->data);

last=p;

}

}

}

//二叉樹(shù)的層次遍歷:

/*******************************************/

/*

按照層次遍歷二叉樹(shù)

*/

/*******************************************/

voidLevelOrderTraverse(BiTreeT)

{

QueueBiNodeQueue;

BiTreep=T;

EnQueue(BiNodeQueue,p);

while(!BiNodeQueue.Empty())

{

DeQueue(BiNodeQueue,p);

if(p)

{

printf("%c",p->data);

EnQueue(BiNodeQueue,p->lchild);

EnQueue(BiNodeQueue,p->rchild);

}

}

}

//交換左右子樹(shù):

/*******************************************/

/*

遞歸法將二叉樹(shù)的左右子樹(shù)互換

*/

/*******************************************/

voidExchange(BiTreeT)

{

BiTreetemp;

if(T)

{

Exchange1(T->lchild);

Exchange1(T->rchild);

temp=T->lchild;

T->lchild=T->rchild;

T->rchild=temp;

}

}

/*******************************************/

/*

非遞歸法將二叉樹(shù)的左右子樹(shù)互換

*/

/*******************************************/

voidExchange(BiTreeT)

{

stackS;

InitStack(S);

BiTreep=T,temp;

while(p||!StackEmpty(S))

{

if(p)

{

Push(S,p);

temp=p->lchild;

p->lchild=p->rchild;

p->rchild=temp;

p=p->lchild;

}

else

{

Pop(S,p);

p->rchild;

}

}

}給出一段報(bào)文和每個(gè)字符出現(xiàn)的概率,對(duì)其進(jìn)行哈夫曼編碼和解碼。實(shí)驗(yàn)4圖論及其應(yīng)用一、實(shí)驗(yàn)?zāi)康牧私鈭D的基本概念及術(shù)語(yǔ),并能夠熟練掌握?qǐng)D的兩種存儲(chǔ)結(jié)構(gòu)(鄰接矩陣和鄰接表)。理解最小生成樹(shù)的概念,能按Prim算法構(gòu)造最小生成樹(shù)。掌握?qǐng)D的兩種遍歷(深度優(yōu)先搜索遍歷和廣度優(yōu)先搜索遍歷)、拓?fù)渑判?、關(guān)鍵路徑、最短路徑的算法思想。二、實(shí)驗(yàn)內(nèi)容及步驟實(shí)現(xiàn)網(wǎng)(有權(quán)圖)的存儲(chǔ)結(jié)構(gòu)。利用prim算法構(gòu)造它的最小生成樹(shù)。選擇一個(gè)源點(diǎn),尋找從原點(diǎn)出發(fā)到達(dá)其它頂點(diǎn)的最短路徑。

實(shí)驗(yàn)5查找一、實(shí)驗(yàn)?zāi)康睦斫?查找表"的結(jié)構(gòu)特點(diǎn)以及各種表示方法的適用性。熟練掌握順序查找和折半查找,并對(duì)其性能做出分析。熟練掌握哈希表的構(gòu)造方法,深刻理解哈希表與其它結(jié)構(gòu)的表的實(shí)質(zhì)性的差別。實(shí)驗(yàn)內(nèi)容及步驟實(shí)現(xiàn)查找表的順序查找和折半查找算法。#include<stdio.h>#include<stdlib.h>#include<time.h>constintARRSIZE=10015;//從小到大排序數(shù)組元素voidasort(int*a,ints){inti,j,k,t;for(i=0;i<s-1;++i){k=i;for(j=i+1;j<s;++j){if(a[k]>a[j]){k=j;}}if(k!=i)