數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)報(bào)告-21

PAGEPAGE1浙師大數(shù)理與信息工程學(xué)院學(xué)生實(shí)驗(yàn)報(bào)告課程名稱數(shù)據(jù)結(jié)構(gòu)與算法專業(yè)姓名學(xué)號班級教師成績

目錄實(shí)驗(yàn)一線性表的實(shí)現(xiàn)-3實(shí)驗(yàn)二棧和隊(duì)列的應(yīng)用-14實(shí)驗(yàn)三二叉樹的建立與遍歷-20實(shí)驗(yàn)四圖的建立與遍歷-25

實(shí)驗(yàn)一線性表的實(shí)現(xiàn)一、

實(shí)驗(yàn)?zāi)康?1）掌握線性表的順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)；2）熟練掌握順序表和鏈表基本算法的實(shí)現(xiàn)；3）掌握利用線性表數(shù)據(jù)結(jié)構(gòu)解決實(shí)際問題的方法和基本技巧；4）按照實(shí)驗(yàn)題目要求獨(dú)立正確地完成實(shí)驗(yàn)內(nèi)容（編寫、調(diào)試算法程序，提交程序清單及及相關(guān)實(shí)驗(yàn)數(shù)據(jù)與運(yùn)行結(jié)果）；二、

實(shí)驗(yàn)內(nèi)容1、順序表的基本操作實(shí)現(xiàn)實(shí)驗(yàn)要求：數(shù)據(jù)元素類型ElemType取整型int。按照順序存儲(chǔ)結(jié)構(gòu)實(shí)現(xiàn)如下算法（各算法邊界條件和返回結(jié)果適當(dāng)給出）：1）創(chuàng)建任意整數(shù)線性表（即線性表的元素值隨機(jī)在鍵盤上輸入），長度限定在25之內(nèi)；2）打印（遍歷）該線性表（依次打印出表中元素值）；3）在線性表中查找第i個(gè)元素，并返回其值；4）在線性表中第i個(gè)元素之前插入一已知元素；5）在線性表中刪除第i個(gè)元素；6）求線性表中所有元素值（整數(shù)）之和；2、鏈表（帶頭結(jié)點(diǎn)）基本操作實(shí)驗(yàn)要求：數(shù)據(jù)元素類型ElemType取字符型char。按照動(dòng)態(tài)單循環(huán)鏈表結(jié)構(gòu)實(shí)現(xiàn)如下算法（各算法邊界條件適當(dāng)給出）：1）創(chuàng)建任意字符型有序（遞增排序）單循環(huán)鏈表（即鏈表的字符元素隨機(jī)在鍵盤上輸入），長度限定在15之內(nèi)；2）打印（遍歷）該鏈表（依次打印出表中元素值）；3）在鏈表中查找第i個(gè)元素，i合法返回元素值，否則，返回FALSE；4）在鏈表中查找與一已知字符相同的第一個(gè)結(jié)點(diǎn)，有則返回TRUE，否則，返回FALSE；5）在鏈表中按照有序方式插入一已知字符元素；6）在線性表中刪除第i個(gè)結(jié)點(diǎn)；7）計(jì)算鏈表的長度。8)將鏈表逆序。（選作）三、

實(shí)驗(yàn)原理順序表和鏈表的基本操作的實(shí)現(xiàn)算法。四、

實(shí)驗(yàn)方法與步驟首先定義順序表和鏈表的存儲(chǔ)結(jié)構(gòu)，根據(jù)基本操作的算法，實(shí)現(xiàn)各個(gè)基本操作的函數(shù)，并在主函數(shù)中調(diào)用這些操作進(jìn)行驗(yàn)證。五、程序代碼：1.線性表:#defineTRUE1#defineFALSE0#defineOK1#defineERROR0#defineINFEASIBLE-1#defineOVERFLOW-2#include<stdlib.h>#include<stdio.h>typedefintElemType;typedefintStatus;#defineLIST_INIT_SIZE100//線性表存儲(chǔ)空間的初始分配量#defineLISTINCREMEMT10//線性表存儲(chǔ)空間的分配增量typedefstruct{ ElemType*elem;//存儲(chǔ)空間基址 intlength;//當(dāng)前長度 intlistsize;//當(dāng)前分配的存儲(chǔ)容量（以sizeof(ElemType)為單位）}SqList;StatusInitList_Sq(SqList&L){ //構(gòu)造一個(gè)空的線性表 L.elem=(ElemType*)malloc(LIST_INIT_SIZE*sizeof(ElemType)); if(!L.elem)exit(OVERFLOW);//存儲(chǔ)分配失敗 L.length=0;//空表長度為0 L.listsize=LIST_INIT_SIZE;//初始存儲(chǔ)容量 returnOK;//初始化成功}//InitList_SqStatuscreatlist(SqList&L,intlen){//通過鍵盤隨機(jī)輸入創(chuàng)建一個(gè)線性表（長度小于80）printf("Pleaseinput%dintnumbers:\n",len);for(inti=0;i<len;i++){ fflush(stdin);scanf("%d",L.elem+i);}L.length=len;returnOK;}StatusListTraver(SqListL){ printf("thenumbers:\n"); for(inti=0;i<L.length;i++) printf("%d\t",L.elem[i]); returnOK;}StatusGetElem(SqListL,inti,ElemType&e){if(i>0&&i<=L.length)e=L.elem[i-1];printf("Thevalueof%dthelmentis%d\n",i,e);returnOK;}StatusListInsert_Sq(SqList&L,inti,ElemTypee){//在順序表L的第i個(gè)元素之前插入新的元素e,。i的合法范圍為1≤i≤L.length+1//int*q,*p;if(i<1||i>L.length+1)returnERROR;//i插入位置不合法if(L.length>=L.listsize){//當(dāng)前存儲(chǔ)空間已滿，增加分配ElemType*newbase=(ElemType*)realloc(L.elem, (L.listsize+LISTINCREMEMT)*sizeof(ElemType)); if(!newbase)exit(OVERFLOW);//存儲(chǔ)分配失敗 L.elem=newbase;//新基址 L.listsize+=LISTINCREMEMT;//增加存儲(chǔ)容量 } ElemType*q=&(L.elem[i-1]);//指示插入位置 for(ElemType*p=&(L.elem[L.length-1]);p>=q;--p) *(p+1)=*p;//插入位置及之后的元素右移 *q=e;//插入e ++L.length;//表長加1 returnOK;}//ListInsert_Sqint ListDelete_Sq(SqList&L,inti,ElemType&e){//在順序線性表L中刪除第i個(gè)元素，并用返回其值。i的合法值為1<=i<=ListLength(L)if((i<1)||(i>L.length))returnERROR;//刪除位置不合法ElemType*p=&(L.elem[i-1]);//p為被刪除元素的位置e=*p;//被刪除元素的值賦給eElemType*q=L.elem+L.length-1;//表尾元素的位置for(++p;p<=q;++p)*(p-1)=*p;//被刪除元素之后的元素左移--L.length;//表長減1returne;}//ListDelete_Sqint ListSum(SqList L){ ints=0;for(ElemTypei=0;i<L.length;i++)s=s+L.elem[i];returns;}voidmain(){SqListL;InitList_Sq(L);intlen;printf("PleaseinputthelengthoftheList:\n");fflush(stdin);scanf("%d",&len);creatlist(L,len);ListTraver(L);intpos;ElemTypee=0;printf("Pleaseinputthepositionitobesearched:\n");fflush(stdin);scanf("%d",&pos);GetElem(L,pos,e);printf("Thevalueof%dthelmentis%d\n",pos,e);ListTraver(L); printf("Pleaseinputthepositionitobeinserted:\n");fflush(stdin);scanf("%d",&pos);printf("Pleaseinputthevalueetobeinserted:\n");fflush(stdin);scanf("%d",&e);ListInsert_Sq(L,pos,e);ListTraver(L);printf("Pleaseinputthepositionitobedeleted:\n");fflush(stdin);scanf("%d",&pos);ListDelete_Sq(L,pos,e);printf("thevaluedeletedis%d\n",e);ListTraver(L);ints=ListSum(L);printf("sum:%d\n",s);}2．鏈表:#include<stdlib.h>#include<stdio.h>#include<string.h>#defineTRUE1#defineFALSE0#defineOK1#defineERROR0#defineINFEASIBLE-1#defineOVERFLOW-2#include<stdlib.h>typedefcharElemType;typedefintStatus;typedefstructLNode{ ElemTypedata;//數(shù)據(jù)域 structLNode*next;//指針域}LNode,*LinkList;StatusInitList_L(LinkList&L){//構(gòu)建一個(gè)空的單循環(huán)的鏈表L=(LinkList)malloc(sizeof(LNode));//L指向空鏈表if(!L)exit(OVERFLOW);L->next=L;//構(gòu)建循環(huán)鏈表表示：尾節(jié)點(diǎn)指針域指向頭結(jié)點(diǎn)returnOK;}//InitLinklistintcompare(ElemTypea,ElemTypeb){if(a>b)return1;if(a==b)return0;if(a<b)return-1;}Statusvisit(ElemTypee){printf("%c\t",e);printf("\n");returnOK;}StatusOrderListInsert_L(LinkList&L,ElemTypee,Status((*compare)(ElemTypea,ElemTypeb))){//按遞增順序插入eLNode*p=L;while(p->next!=L&&compare(p->next->data,e)<0)p=p->next;LNode*s=(LinkList)malloc(sizeof(LNode));//給新元素分配節(jié)點(diǎn)s->data=e;s->next=p->next;p->next=s;returnOK; }//OrderListInser_LStatusCreateList_L(LinkList&L,intn){//if(n<=o){printf("badnumber\n");returnERROR;//printf("\npleaseinput%d\n");for(inti=n;i>0;--i){ fflush(stdin);chare=getchar();OrderListInsert_L(L,e,compare);}returnOK;}//GreateList_LStatusListTraverse(LinkListL,Status(*visit)(ElemTypee)){for(LNode*p=L->next;p!=L;p=p->next)if(!visit(p->data))returnERROR;returnOK;}StatusGetElem(LinkListL,inti,ElemType&e){//L是帶頭結(jié)點(diǎn)的鏈表的頭指針，以e返回第i個(gè)元素LNode*p=L->next;intj=1;//初始化，p指向第一個(gè)結(jié)點(diǎn)，j為計(jì)數(shù)器while(p!=L&&j<i){p=p->next;j++;}//順指針向后查找，直到p指向第i個(gè)元素或p為空if(!p||j>i)returnERROR;//第i個(gè)元素不存在e=p->data;//取第i個(gè)元素returnOK;}//GetElemintLocateElem(LinkListL,ElemTypee,Status(*compare)(ElemType,ElemType)){//在順序表中查詢第一個(gè)滿足判定條件的數(shù)據(jù)元素， //若存在，則返回它的位序，否則返回FALSELNode*p=L->next;inti=1;//i的初值為第1元素的位序while(p!=L&&compare(p->data,e)<0){p=p->next;i++;}if(p!=L)returni;elsereturnFALSE;}//LocateElemStatusListDelete_L(LinkList&L,inti,ElemType&e){//在帶頭結(jié)點(diǎn)的循環(huán)鏈表中刪除i個(gè)元素，并由e返回其值LNode*p=L;intj=0;while(p->next!=L&&j<i-1){//尋找第i個(gè)結(jié)點(diǎn)，并令p指向其前趨p=p->next;++j;}if(p->next==L||j>i-1)returnERROR;//刪除位置不合理LNode*q=p->next;p->next=q->next;//刪除并釋放結(jié)點(diǎn)e=q->data;free(q);returnOK;}//ListDelete_LintListLenth_L(LinkListL){inti=0;LNode*p=L;while(p->next!=L){++i;p=p->next;}returni;}voidmain(){LinkListL;InitList_L(L);//intlen,i;printf("pleaseinputlen:\n"); fflush(stdin);scanf("%d",&len);printf("pleaseinputtheelem:\n");CreateList_L(L,len);printf("thenumber:\n");ListTraverse(L,visit);ElemTypee='a';for(i=1;i<=len;i++){ GetElem(L,i,e);}printf("pleaseinputthepositionyouwant:\n"); fflush(stdin);e=getchar();printf("thepositionofthe%cis%d",e,LocateElem(L,e,compare));printf("\n");printf("pleaseinputtheeleminsert:\n"); fflush(stdin);e=getchar();OrderListInsert_L(L,e,compare);ListTraverse(L,visit);printf("pleaseinputthepositiondelete:\n"); fflush(stdin);scanf("%d",&i);ListDelete_L(L,i,e);ListTraverse(L,visit);printf("thelenthofthelistis%d:",ListLenth_L(L));}運(yùn)行結(jié)果及結(jié)果分析 線性表PleaseinputthelengthoftheList:5Pleaseinput5intnumbers:245352511111453thenumbers:245352511111453Pleaseinputthepositionitobesearched:3Thevalueof3thelmentis25Thevalueof3thelmentis25thenumbers:245352511111453Pleaseinputthepositionitobeinserted:4Pleaseinputthevalueetobeinserted:22thenumbers:24535252211111453Pleaseinputthepositionitobedeleted:2thevaluedeletedis35thenumbers:245252211111453sum:11856請按任意鍵繼續(xù)...鏈表pleaseinputlen:4pleaseinputtheelem:gh75thenumber:57ghpleaseinputthepositionyouwant:2thepositionofthe2is1pleaseinputtheeleminsert:4457ghpleaseinputthepositiondelete:345ghthelenthofthelistis4:請按任意鍵繼續(xù)...

實(shí)驗(yàn)二棧和隊(duì)列的應(yīng)用一、實(shí)驗(yàn)?zāi)康?）掌握棧與隊(duì)列的數(shù)據(jù)類型描述及特點(diǎn)；2）熟練掌握棧的順序和鏈?zhǔn)酱鎯?chǔ)存表示與基本算法的實(shí)現(xiàn)；3）掌握隊(duì)列的鏈?zhǔn)酱鎯?chǔ)表示與基本操作算法實(shí)現(xiàn);4)掌握棧與隊(duì)列在實(shí)際問題中的應(yīng)用和基本編程技巧;5）按照實(shí)驗(yàn)題目要求獨(dú)立正確地完成實(shí)驗(yàn)內(nèi)容（提交程序清單及相關(guān)實(shí)驗(yàn)數(shù)據(jù)與運(yùn)行結(jié)果.二、

實(shí)驗(yàn)內(nèi)容1）利用棧深度優(yōu)先進(jìn)行迷宮求解。2）利用隊(duì)列寬度優(yōu)先進(jìn)行迷宮求解。(選作)三、

實(shí)驗(yàn)原理順序棧、鏈棧、順序隊(duì)列與鏈隊(duì)列的基本操作的實(shí)現(xiàn)算法，搜索的基本思想。四、

實(shí)驗(yàn)方法與步驟1)定義順序棧和順序隊(duì)列的存儲(chǔ)結(jié)構(gòu)；2)實(shí)現(xiàn)順序棧和順序隊(duì)列的基本操作；3)基于搜索的基本思想，實(shí)現(xiàn)迷宮求解算法。五、程序代碼：#include<iostream>usingnamespacestd;classT//定義描述迷宮中當(dāng)前位置的結(jié)構(gòu)類型{public:intx;//x代表當(dāng)前位置的行坐標(biāo)inty;//y代表當(dāng)前位置的列坐標(biāo)intdir;//0:無效,1:東,2:南,3:西,4:北};classLinkNode//鏈表結(jié)點(diǎn){friendclassStack;public:Tdata;LinkNode*next;};classStack{private:LinkNode*top;//指向第一個(gè)結(jié)點(diǎn)的棧頂指針public:Stack();//構(gòu)造函數(shù)，置空棧~Stack();//析構(gòu)函數(shù)voidPush(Te);//把元素data入棧TPop();//使棧頂元素出棧TGetPop();//取出棧頂元素voidClear();//把棧清空boolempty();//判斷棧是否為空，如果為空則返回1，否則返回0};Stack::Stack()//構(gòu)造函數(shù)，置空棧{top=NULL;}Stack::~Stack()//析構(gòu)函數(shù){}voidStack::Push(Te)//把元素x壓入棧中{LinkNode*P;P=newLinkNode;P->data=e;P->next=top;top=P;}TStack::Pop()//使棧頂元素出棧{TTemp;LinkNode*P;P=top;top=top->next;Temp=P->data;deleteP;returnTemp;}TStack::GetPop()//取出棧頂元素{returntop->data;}voidStack::Clear()//把棧清空{(diào)top=NULL;}boolStack::empty()//判斷棧是否為空，如果為空則返回1，否則返回0{if(top==NULL)return1;elsereturn0;}intmove[4][2]={{0,1},{1,0},{0,-1},{-1,0}};//定義當(dāng)前位置移動(dòng)的4個(gè)方向boolMazepath(int**maze,intm,intn);//尋找迷宮maze中從（0，0）到（m,n）的路徑//到則返回true,否則返回falsevoidPrintPath(Stackp);//輸出迷宮的路徑voidRestore(int**maze,intm,intn);//恢復(fù)迷宮int**GetMaze(int&m,int&n);//獲取迷宮//返回存取迷宮的二維指針intmain(){intm=0,n=0;//定義迷宮的長和寬int**maze;//定義二維指針存取迷宮maze=GetMaze(m,n);//調(diào)用GetMaze(int&m,int&n)函數(shù)，得到迷宮if(Mazepath(maze,m,n))//調(diào)用Mazepath(int**maze,intm,intn)函數(shù)獲取路徑cout<<"迷宮路徑探索成功!\n";elsecout<<"路徑不存在!\n";return0;}int**GetMaze(int&m,int&n)//返回存取迷宮的二維指針{int**maze;//定義二維指針存取迷宮inti=0,j=0;cout<<"請輸入迷宮的長和寬:";inta,b;cin>>a>>b;//輸入迷宮的長和寬cout<<"請輸入迷宮內(nèi)容:\n";m=a;n=b;//m,n分別代表迷宮的行數(shù)和列數(shù)maze=newint*[m+2];//申請長度等于行數(shù)加2的二級指針for(i=0;i<m+2;i++)//申請每個(gè)二維指針的空間{maze[i]=newint[n+2];}for(i=1;i<=m;i++)//輸入迷宮的內(nèi)容，0代表可通，1代表不通for(j=1;j<=n;j++)cin>>maze[i][j];for(i=0;i<m+2;i++)maze[i][0]=maze[i][n+1]=1;for(i=0;i<n+2;i++)maze[0][i]=maze[m+1][i]=1;returnmaze;//返回存貯迷宮的二維指針maze};boolMazepath(int**maze,intm,intn)//尋找迷宮maze中從（0，0）到（m,n）的路徑//到則返回true,否則返回false{Stackq,p;//定義棧p、q,分別存探索迷宮的過程和存儲(chǔ)路徑TTemp1,Temp2;intx,y,loop;Temp1.x=1;Temp1.y=1;q.Push(Temp1);//將入口位置入棧p.Push(Temp1);maze[1][1]=-1;//標(biāo)志入口位置已到達(dá)過while(!q.empty())//棧q非空，則反復(fù)探索{Temp2=q.GetPop();//獲取棧頂元素if(!(p.GetPop().x==q.GetPop().x&&p.GetPop().y==q.GetPop().y))p.Push(Temp2);//如果有新位置入棧，則把上一個(gè)探索的位置存入棧pfor(loop=0;loop<4;loop++)//探索當(dāng)前位置的4個(gè)相鄰位置{x=Temp2.x+move[loop][0];//計(jì)算出新位置x位置值y=Temp2.y+move[loop][1];//計(jì)算出新位置y位置值if(maze[x][y]==0)//判斷新位置是否可達(dá){Temp1.x=x;Temp1.y=y;maze[x][y]=-1;//標(biāo)志新位置已到達(dá)過q.Push(Temp1);//新位置入棧}if((x==(m))&&(y==(n)))//成功到達(dá)出口{Temp1.x=m;Temp1.y=n;Temp1.dir=0;p.Push(Temp1);//把最后一個(gè)位置入棧PrintPath(p);//輸出路徑Restore(maze,m,n);//恢復(fù)路徑return1;//表示成功找到路徑}}if(p.GetPop().x==q.GetPop().x&&p.GetPop().y==q.GetPop().y)//如果沒有新位置入棧，則返回到上一個(gè)位置{p.Pop();q.Pop();}}return0;//表示查找失敗，即迷宮無路經(jīng)}voidPrintPath(Stackp)//輸出路徑{cout<<"迷宮的路徑為\n";cout<<"括號內(nèi)的內(nèi)容分別表示為(行坐標(biāo),列坐標(biāo),數(shù)字化方向,方向)\n";Stackt;//定義一個(gè)棧，按從入口到出口存取路徑inta,b;Tdata;LinkNode*temp;temp=newLinkNode;//申請空間temp->data=p.Pop();//取棧p的頂點(diǎn)元素，即第一個(gè)位置t.Push(temp->data);//第一個(gè)位置入棧tdeletetemp;//釋放空間while(!p.empty())//棧p非空，則反復(fù)轉(zhuǎn)移{temp=newLinkNode;temp->data=p.Pop();//獲取下一個(gè)位置//得到行走方向a=t.GetPop().x-temp->data.x;//行坐標(biāo)方向b=t.GetPop().y-temp->data.y;//列坐標(biāo)方向if(a==1)temp->data.dir=1;//方向向下，用1表示elseif(b==1)temp->data.dir=2;//方向向右，用2表示elseif(a==-1)temp->data.dir=3;//方向向上，用3表示elseif(b==-1)temp->data.dir=4;//方向向左，用4表示t.Push(temp->data);//把新位置入棧deletetemp;}//輸出路徑，包括行坐標(biāo)，列坐標(biāo)，下一個(gè)位置方向while(!t.empty())//棧非空，繼續(xù)輸出{data=t.Pop();cout<<'('<<data.x<<','<<data.y<<','<<data.dir<<",";//輸出行坐標(biāo)，列坐標(biāo)switch(data.dir)//輸出相應(yīng)的方向{case1:cout<<"↓)\n";break;case2:cout<<"→)\n";break;case3:cout<<"↑)\n";break;case4:cout<<"←)\n";break;case0:cout<<")\n";break;}}}voidRestore(int**maze,intm,intn)//恢復(fù)迷宮{inti,j;for(i=0;i<m+2;i++)//遍歷指針for(j=0;j<n+2;j++){if(maze[i][j]==-1)//恢復(fù)探索過位置，即把-1恢復(fù)為0maze[i][j]=0;}}六、運(yùn)行結(jié)果及結(jié)果分析請輸入迷宮的長和寬:33請輸入迷宮內(nèi)容:0,0,0,1,1,0,1,1,0迷宮的路徑為括號內(nèi)的內(nèi)容分別表示為(行坐標(biāo),列坐標(biāo),數(shù)字化方向,方向)(1,1,2,→)(1,2,1,↓)(2,2,1,↓)(3,2,2,→)(3,3,0,)迷宮路徑探索成功!請按任意鍵繼續(xù)....

實(shí)驗(yàn)三二叉樹的建立與遍歷一、

實(shí)驗(yàn)?zāi)康?1）熟練掌握二叉樹的二叉鏈表表示創(chuàng)建算法與實(shí)現(xiàn)；2）熟練掌握先序、中序、后序和層次遍歷二叉樹的基本遞歸遍歷算法與實(shí)現(xiàn)；3）理解借用棧的先序、中序和后序非遞歸遍歷算法與實(shí)現(xiàn)；4）按照實(shí)驗(yàn)題目要求獨(dú)立正確地完成實(shí)驗(yàn)內(nèi)容（提交程序清單及相關(guān)實(shí)驗(yàn)數(shù)據(jù)與運(yùn)行結(jié)果）；二、

實(shí)驗(yàn)內(nèi)容1)創(chuàng)建二叉樹：先序創(chuàng)建；（比如給定先序序列字符串來創(chuàng)建等）2)遍歷二叉樹：先，中，后序遍歷，（選做）層次遍歷；3)遍歷過程中求解二叉樹的屬性：葉子結(jié)點(diǎn)數(shù)，結(jié)點(diǎn)數(shù)，深度，（選做）寬度4)打印某節(jié)點(diǎn)所在的二叉樹路徑：根結(jié)點(diǎn)到某節(jié)點(diǎn)的路徑；（選做）5）二叉樹置空：清空二叉樹；6)子樹互換：二叉樹所有左右子樹互換；(選作)7）二叉樹線索：中序線索二叉樹。(選作)三、

實(shí)驗(yàn)原理二叉樹的遍歷方法：1）先序(根)遍歷：(1)訪問根結(jié)點(diǎn)；(2)先序遍歷左子樹；(3)先序遍歷右子樹；2）中序(根)遍歷：(1)中序遍歷左子樹；(2)訪問根結(jié)點(diǎn)；(3)中序遍歷右子樹；3）后序(根)遍歷：(1)后序遍歷左子樹;(2)后序遍歷右子樹；(3)訪問根結(jié)點(diǎn);4）按層次遍歷：從上到下、從左到右訪問各結(jié)點(diǎn)（提示：借用隊(duì)列）四、

實(shí)驗(yàn)方法與步驟1）實(shí)現(xiàn)建立二叉樹的函數(shù)；2）重點(diǎn)實(shí)現(xiàn)4種二叉樹遍歷函數(shù)（層次遍歷為選做）；3）實(shí)現(xiàn)求二叉樹葉子結(jié)點(diǎn)數(shù)、結(jié)點(diǎn)數(shù)、深度等函數(shù)，（選做）寬度函數(shù)；4）實(shí)現(xiàn)求根結(jié)點(diǎn)到葉子結(jié)點(diǎn)的路徑函數(shù)；（選做）5）二叉樹置空函數(shù)6）學(xué)有余力的同學(xué)完成子樹互換函數(shù)和建立中序線索二叉樹并中序輸出。五、程序代碼：#include<stdlib.h>#include<stdio.h>#include<string.h>#defineTRUE1#defineFALSE0#defineOK1#defineERROR0#defineINFEASIBLE-1#defineOVERFLOW-2typedefintStatus;//typedefintElemType;typedefcharTElemType;typedefstructBiTNode{//結(jié)點(diǎn)結(jié)構(gòu)TElemTypedata;structBiTNode*lchild,*rchild;//左右孩子指針}BiTNode,*BiTree;StatusCreateBiTree(BiTree&T){ //非常重要的一點(diǎn)：沒有子在T前加&引用！?。?！charch;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)造左子樹CreateBiTree(T->rchild);//構(gòu)造右子樹}returnOK;}//CreateBiTreeStatusPrintElement(TElemTypee){printf("%c\t",e);returnOK;}voidPreorderT(BiTreeT,Status(*visit)(TElemTypee)){//先序遍歷二叉樹if(T){visit(T->data);//訪問結(jié)點(diǎn)PreorderT(T->lchild,visit);//先序遍歷左子樹PreorderT(T->rchild,visit);//先序遍歷右子樹}//if}voidInOrderT(BiTreeT,Status(*visit)(TElemTypee)){//中序遍歷二叉樹if(T){InOrderT(T->lchild,visit);//中序遍歷左子樹visit(T->data);//訪問結(jié)點(diǎn)InOrderT(T->rchild,visit);//中序遍歷右子樹}//if}voidPostOrderT(BiTreeT,Status(*visit)(TElemTypee)){//后序遍歷二叉樹 if(T){//注意都相應(yīng)地?fù)Q成PostPostOrderT(T->lchild,visit);//后序遍歷左子樹PostOrderT(T->rchild,visit);//后序遍歷右子樹visit(T->data);//訪問結(jié)點(diǎn)}//if}intCountLeaf(BiTreeT){intm=0,n=0; //賦初值//返回指針T所指二叉樹中所有葉子結(jié)點(diǎn)個(gè)數(shù)if(!T)return0;if(!T->lchild&&!T->rchild)return1;else{m=CountLeaf(T->lchild);n=CountLeaf(T->rchild);return(m+n);}//else}//CountLeafintCountNode(BiTreeT){//返回指針T所指二叉樹中所有葉子結(jié)點(diǎn)個(gè)數(shù)intm=0,n=0; //賦初值if(!T)return0;if(!T->lchild&&!T->rchild)return1;else{m=CountNode(T->lchild);n=CountNode(T->rchild);return(m+n+1);}//else}//CountNodevoidmain(){BiTreeT=NULL; //賦初值 CreateBiTree(T); PreorderT(T,PrintElement); puts("\n"); InOrderT(T,PrintElement); puts("\n"); PostOrderT(T,PrintElement); puts("\n"); printf("thenumberofleaves:%d,thenumberofnodes:%d\n",CountLeaf(T),CountNode(T));}運(yùn)行結(jié)果及結(jié)果分析abcdegfabcdegfcbegdfacgefdbathenumberofleaves:3,thenumberofnodes:7請按任意鍵繼續(xù)...

實(shí)驗(yàn)四圖的建立與遍歷一、

實(shí)驗(yàn)?zāi)康?）掌握圖的鄰接表存儲(chǔ)結(jié)構(gòu)表示和與圖創(chuàng)建算法的C語言實(shí)現(xiàn)；2）掌握圖的深度優(yōu)先及寬度優(yōu)先遍歷算法；3）按照實(shí)驗(yàn)題目要求獨(dú)立正確地完成實(shí)驗(yàn)內(nèi)容（提交程序清單及相關(guān)實(shí)驗(yàn)數(shù)據(jù)與運(yùn)行結(jié)果）。二、

實(shí)驗(yàn)內(nèi)容1）建立有向圖，利用鄰接表存儲(chǔ)該圖。輸入圖的頂點(diǎn)個(gè)數(shù)和邊數(shù)，以及邊集，建立圖的鄰接表的存儲(chǔ)表示；2）實(shí)現(xiàn)深度優(yōu)先遍歷和寬度優(yōu)先遍歷算法；3）求每一個(gè)節(jié)點(diǎn)的出度、入度、度；4）（選做）求出一個(gè)拓?fù)渑判蛐蛄小?/p>

三、

實(shí)驗(yàn)原理1.圖的存儲(chǔ)和遍歷: 1）圖可以使用鄰接表來存儲(chǔ)：頭結(jié)點(diǎn)序列以及相應(yīng)的鄰接點(diǎn)構(gòu)成的鏈表； 2）通過深度優(yōu)先或?qū)挾葍?yōu)先依次遍歷圖節(jié)點(diǎn)以及相關(guān)的鄰接點(diǎn)； 3）鄰接表存儲(chǔ)中包含了相關(guān)的出度、入度等信息。四、

實(shí)驗(yàn)方法與步驟1）實(shí)現(xiàn)建立有向圖函數(shù)；2）深度優(yōu)先和寬度優(yōu)先遍歷圖3）求每一個(gè)節(jié)點(diǎn)的出度、入度、度。五、程序代碼：#include<stdio.h>#defineOK1#defineERROR0#definemaxsize1000#definen100typedefstruct{charvexs[n];//頂點(diǎn)intarcs[n][n];//弧intnum;//頂點(diǎn)個(gè)數(shù)}G;//圖的結(jié)構(gòu)體typedefstruct{intdata[maxsize];intfront,rear;}V;//頂點(diǎn)的結(jié)構(gòu)體voidGInit(G*L){L->num=0;}//初始化圖(用鏈表表示)intGVexs(G*L){return(L->num);}//圖的頂點(diǎn)數(shù)voidGCreate(G*L){inti,j;GInit(L);printf("請輸入頂點(diǎn)數(shù)目：\n");scanf("%d",&L->num);printf("請輸入各頂點(diǎn)：\n");for(i=0;i<L->num;i++){fflush(stdin);scanf("%c",&L->vexs[i]);}printf("請輸入各頂點(diǎn)邊的關(guān)系（1是有關(guān)0是無關(guān)）：\n");for(i=0;i<L->num;i++){for(j=0;j<L->num;j++){scanf("%d",&L->arcs[i][j]);}}}//構(gòu)建圖voidGOut(GL){inti,j;printf("\n圖的頂點(diǎn)數(shù)目為：%d",L.num);printf("\n圖的各頂點(diǎn)的信息為：\n");for(i=0;i<L.num;i++)printf("%7c",L.vexs[i]);//輸出頂點(diǎn)printf("\n");for(i=0;i<L.num;i++){for(j=0;j<L.num;j++){printf("%7d",L.arcs[i][j]);//輸出弧}printf("\n");}}//圖的輸出voidDFS(Gg,intqidian,intmark[]){intv1;mark[qidian]=1;printf("%c",g.vexs[qidian]);for(v1=0;v1<g.num;v1++){if(g.arcs[qidian][v1]!=0&&mark[v1]==0)DFS(g,v1,mark);}}//深度優(yōu)先遍歷voidGDFS(Gg){intqidian,v,v1,mark[maxsize];printf("\n深度遍歷：");printf("\n請輸入起點(diǎn)的下標(biāo)：");scanf("%d",&qidian);getchar();for(v=0;v<g.num;v++){mark[v]=0;}for(v=qidian;v<g.num+qidian;v++){v1=v%g.num;if(mark[v1]==0)DFS(g,v1,mark);}}//使用深度優(yōu)先遍歷voidQueueInit(V*sq){sq->front=0;sq->rear=0;}//隊(duì)列intQueueIsEmpty(Vsq){if(sq.rear==sq.fron