《大數(shù)據(jù)結(jié)構(gòu)》(C語言版)嚴(yán)蔚敏著_實驗指導(dǎo)

上傳人:痛*** 文檔編號:85511578 上傳時間:2022-05-05 格式:DOC 頁數(shù):48 大?。?48KB
收藏 版權(quán)申訴 舉報 下載
《大數(shù)據(jù)結(jié)構(gòu)》(C語言版)嚴(yán)蔚敏著_實驗指導(dǎo)_第1頁
第1頁 / 共48頁
《大數(shù)據(jù)結(jié)構(gòu)》(C語言版)嚴(yán)蔚敏著_實驗指導(dǎo)_第2頁
第2頁 / 共48頁
《大數(shù)據(jù)結(jié)構(gòu)》(C語言版)嚴(yán)蔚敏著_實驗指導(dǎo)_第3頁
第3頁 / 共48頁

下載文檔到電腦,查找使用更方便

10 積分

下載資源

還剩頁未讀,繼續(xù)閱讀

資源描述:

《《大數(shù)據(jù)結(jié)構(gòu)》(C語言版)嚴(yán)蔚敏著_實驗指導(dǎo)》由會員分享,可在線閱讀,更多相關(guān)《《大數(shù)據(jù)結(jié)構(gòu)》(C語言版)嚴(yán)蔚敏著_實驗指導(dǎo)(48頁珍藏版)》請在裝配圖網(wǎng)上搜索。

1、word 《數(shù)據(jù)結(jié)構(gòu)》實驗指導(dǎo)與報告書 /學(xué)年 第學(xué)期 姓 名:______________ 學(xué) 號:______________ 班 級:______________ 指導(dǎo)教師:______________ 數(shù)學(xué)與統(tǒng)計學(xué)院 2011 預(yù)備實驗 C語言的函數(shù)數(shù)組指針結(jié)構(gòu)體知識 一、實驗?zāi)康? 1、復(fù)習(xí)C語言中函數(shù)、數(shù)組、指針、結(jié)構(gòu)體與共用體等的概念。 2、熟悉利用C語言進(jìn)展程序設(shè)計的一般方法。 二、實驗預(yù)習(xí) 說明以下C語言中的概念 1、 函數(shù): 2、 數(shù)組: 3、指針: 4、結(jié)

2、構(gòu)體 5、共用體 三、實驗容和要求 1、調(diào)試程序:輸出100以所有的素數(shù)〔用函數(shù)實現(xiàn)〕。 #include int isprime(int n){ /*判斷一個數(shù)是否為素數(shù)*/ int m; for(m=2;m*m<=n;m++) if(n%m==0) return 0; return 1; } int main(){ /*輸出100以所有素數(shù)*/ int i;printf("\n"); for(i=2;i<100;i++) if(isprime(i)==1) printf("%

3、4d",i); return 0; } 運(yùn)行結(jié)果: 2、 調(diào)試程序:對一維數(shù)組中的元素進(jìn)展逆序排列。 #include #define N 10 int main(){ int a[N]={0,1,2,3,4,5,6,7,8,9},i,temp; printf("\nthe original Array is:\n "); for(i=0;i

4、; a[N-i-1]=temp; } printf("\nthe changed Array is:\n"); for(i=0;i #define M 3 #define N 4 int main(){ int a[M][N],i,j,k;

5、printf("\n請輸入二維數(shù)組的數(shù)據(jù):\n"); for(i=0;ia[i][k]) k=j; for(j=0;j

6、;j++) /*判斷第i行的最大值是否為該列的最小值*/ if(a[j][k] int main(){ int a[3][4]={1,3,5,7,9,11,13,15,17,19,21,23}; int *p; for(p=a[0];p

7、++){ if((p-a[0])%4==0) printf("\n"); printf("%4d",*p); } return 0; } 運(yùn)行結(jié)果: 5、 調(diào)試程序:設(shè)有一個教師與學(xué)生通用的表格,教師的數(shù)據(jù)有、年齡、職業(yè)、教研室四項,學(xué)生有、年齡、專業(yè)、班級四項,編程輸入人員的數(shù)據(jù),再以表格輸出。 #include #define N 10 struct student{ char name[8]; /**/ int age; /*年齡*/ char job; /*職業(yè)或?qū)I(yè),用s或t表示學(xué)生或教師*/ union {

8、 int class; /*班級*/ char office[10]; /*教研室*/ }depa; }stu[N]; int main(){ int i; int n; printf(“\n請輸入人員數(shù)(<10):\n〞); scanf(“%d〞,&n); for(i=0;i

9、; if(stu[i].job==’s’) scanf("%d",&stu[i].); else scanf("%s",stu[i].); } printf(“name age job class/office〞); for(i=0;i

10、stu[i].name, stu[i].age, stu[i].job, stu[i].); } } 輸入的數(shù)據(jù):2 Wang 19 s 99061 Li 36 t puter 運(yùn)行結(jié)果: 四、實驗小結(jié) 五、教師評語 實驗一 順序表與鏈表 一、實驗?zāi)康? 1、掌握線性表中元素的前驅(qū)、后續(xù)的概念。 2、掌握順序表與鏈表的建立、插入元素、刪除表中某元素的算法。 3、對線性表相應(yīng)算法的時間復(fù)雜度進(jìn)展分析。 4、理解順序表、鏈表數(shù)據(jù)結(jié)構(gòu)的特點(diǎn)〔優(yōu)缺點(diǎn)〕。 二、實驗預(yù)習(xí) 說明以下概念 1、線性表: 2、順序表

11、: 3、鏈表: 三、實驗容和要求 1、閱讀下面程序,在橫線處填寫函數(shù)的根本功能。并運(yùn)行程序,寫出結(jié)果。 #include #include #define ERROR 0 #define OK 1 #define INIT_SIZE 5 /*初始分配的順序表長度*/ #define INCREM 5 /*溢出時,順序表長度的增量*/ typedef int ElemType; /*定義表元素的類型*/ typedef struct Sqlist{ ElemType *slist; /*存

12、儲空間的基地址*/ int length; /*順序表的當(dāng)前長度*/ int listsize; /*當(dāng)前分配的存儲空間*/ }Sqlist; int InitList_sq(Sqlist *L); /**/ int CreateList_sq(Sqlist *L,int n); /**/ int ListInsert_sq(Sqlist *L,int i,ElemType e);/**/ int PrintList_sq(Sqlist *L); /*輸出順序表的元素*/ int ListDelete_sq(Sqlist *L,in

13、t i); /*刪除第i個元素*/ int ListLocate(Sqlist *L,ElemType e);/*查找值為e的元素*/ int InitList_sq(Sqlist *L){ L->slist=(ElemType*)malloc(INIT_SIZE*sizeof(ElemType)); if(!L->slist) return ERROR; L->length=0; L->listsize=INIT_SIZE; return OK;

14、 }/*InitList*/ int CreateList_sq(Sqlist *L,int n){ ElemType e; int i; for(i=0;i

15、*/ int PrintList_sq(Sqlist *L){ int i; for(i=1;i<=L->length;i++) printf("%5d",L->slist[i-1]); return OK; }/*PrintList*/ int ListInsert_sq(Sqlist *L,int i,ElemType e){ int k; if(i<1||i>L->length+1) return ERROR; if(L->length>=L->listsize){ L->slist=(ElemTy

16、pe*)realloc(L->slist, (INIT_SIZE+INCREM)*sizeof(ElemType)); if(!L->slist) return ERROR; L->listsize+=INCREM; } for(k=L->length-1;k>=i-1;k--){ L->slist[k+1]=L->slist[k]; } L->slist[i-1]=e; L->length++;

17、 return OK; }/*ListInsert*/ /*在順序表中刪除第i個元素*/ int ListDelete_sq(Sqlist *L,int i){ } /*在順序表中查找指定值元素,返回其序號*/ int ListLocate(Sqlist *L,ElemType e){ } int main(){ Sqlist sl; int n,m,k; printf("please input n:"); /*輸入順序表的元素個數(shù)*/ scanf("%d",&n); if(n>0){

18、 printf("\n1-Create Sqlist:\n"); InitList_sq(&sl); CreateList_sq(&sl,n); printf("\n2-Print Sqlist:\n"); PrintList_sq(&sl); printf("\nplease input insert location and data:(location,data)\n"); scanf("%d,%d",&m,&k); ListInsert_sq(&sl,m,k); printf("\n3-P

19、rint Sqlist:\n"); PrintList_sq(&sl); printf("\n"); } else printf("ERROR"); return 0; } l 運(yùn)行結(jié)果 l 算法分析 2、為第1題補(bǔ)充刪除和查找功能函數(shù),并在主函數(shù)中補(bǔ)充代碼驗證算法的正確性。 刪除算法代碼: l 運(yùn)行結(jié)果 l 算法分析 查找算法代碼: l 運(yùn)行結(jié)果 l 算法分析

20、 3、閱讀下面程序,在橫線處填寫函數(shù)的根本功能。并運(yùn)行程序,寫出結(jié)果。 #include #include #define ERROR 0 #define OK 1 typedef int ElemType; /*定義表元素的類型*/ typedef struct LNode{ /*線性表的單鏈表存儲*/ ElemType data; struct LNode *next; }LNode,*LinkList; LinkList CreateList(int n); /**/ void PrintList(Li

21、nkList L); /*輸出帶頭結(jié)點(diǎn)單鏈表的所有元素*/ int GetElem(LinkList L,int i,ElemType *e);/**/ LinkList CreateList(int n){ LNode *p,*q,*head; int i; head=(LinkList)malloc(sizeof(LNode)); head->next=NULL; p=head; for(i=0;i

22、ntf("input data %i:",i+1); scanf("%d",&q->data); /*輸入元素值*/ q->next=NULL; /*結(jié)點(diǎn)指針域置空*/ p->next=q; /*新結(jié)點(diǎn)連在表末尾*/ p=q; } return head; }/*CreateList*/ void PrintList(LinkList L){ LNode *p; p=L->next

23、; /*p指向單鏈表的第1個元素*/ while(p!=NULL){ printf("%5d",p->data); p=p->next; } }/*PrintList*/ int GetElem(LinkList L,int i,ElemType *e){ LNode *p;int j=1; p=L->next; while(p&&jnext;j++; } if(!p||j>i)

24、return ERROR; *e=p->data; return OK; }/*GetElem*/ int main(){ int n,i;ElemType e; LinkList L=NULL; /*定義指向單鏈表的指針*/ printf("please input n:"); /*輸入單鏈表的元素個數(shù)*/ scanf("%d",&n); if(n>0){ printf("\n1-Create LinkLis

25、t:\n"); L=CreateList(n); printf("\n2-Print LinkList:\n"); PrintList(L); printf("\n3-GetElem from LinkList:\n"); printf("input i="); scanf("%d",&i); if(GetElem(L,i,&e)) printf("No%i is %d",i,e);

26、 else printf("not exists"); }else printf("ERROR"); return 0; } l 運(yùn)行結(jié)果 l 算法分析 4、為第3題補(bǔ)充插入功能函數(shù)和刪除功能函數(shù)。并在主函數(shù)中補(bǔ)充代碼驗證算法的正確性。 插入算法代碼: l 運(yùn)行結(jié)果 l 算法分析 刪除算法代碼: l 運(yùn)行結(jié)果 l 算法分析

27、 以下為選做實驗: 5、循環(huán)鏈表的應(yīng)用〔約瑟夫回環(huán)問題〕 n個數(shù)據(jù)元素構(gòu)成一個環(huán),從環(huán)中任意位置開始計數(shù),計到m將該元素從表中取出,重復(fù)上述過程,直至表中只剩下一個元素。 提示:用一個無頭結(jié)點(diǎn)的循環(huán)單鏈表來實現(xiàn)n個元素的存儲。 l 算法代碼 6、設(shè)一帶頭結(jié)點(diǎn)的單鏈表,設(shè)計算法將表中值一樣的元素僅保存一個結(jié)點(diǎn)。 提示:指針p從鏈表的第一個元素開始,利用指針q從指針p位置開始向后搜索整個鏈表,刪除與之值一樣的元素;指針p繼續(xù)指向下一個元素,開始下一輪的刪除,直至p==null為至,既完成了對整個鏈表元素的刪除一樣值。 l 算法代碼

28、 四、實驗小結(jié) 五、教師評語 實驗二 棧和隊列 一、實驗?zāi)康? 1、掌握棧的結(jié)構(gòu)特性與其入棧,出棧操作; 2、掌握隊列的結(jié)構(gòu)特性與其入隊、出隊的操作,掌握循環(huán)隊列的特點(diǎn)與其操作。 二、實驗預(yù)習(xí) 說明以下概念 1、順序棧: 2、鏈棧: 3、循環(huán)隊列: 4、鏈隊 三、實驗容和要求 1、閱讀下面程序,將函數(shù)Push和函數(shù)Pop補(bǔ)充完整。要求輸入元素序列1 2 3 4 5 e,運(yùn)行結(jié)果如下所示。 #include #include #de

29、fine ERROR 0 #define OK 1 #define STACK_INT_SIZE 10 /*存儲空間初始分配量*/ #define STACKINCREMENT 5 /*存儲空間分配增量*/ typedef int ElemType; /*定義元素的類型*/ typedef struct{ ElemType *base; ElemType *top; int stacksize; /*當(dāng)前已分配的存儲空間*/ }SqStack; int InitStack(SqStack *S); /*構(gòu)造空棧*/ int p

30、ush(SqStack *S,ElemType e); /*入棧*/ int Pop(SqStack *S,ElemType *e); /*出棧*/ int CreateStack(SqStack *S); /*創(chuàng)建棧*/ void PrintStack(SqStack *S); /*出棧并輸出棧中元素*/ int InitStack(SqStack *S){ S->base=(ElemType *)malloc(STACK_INT_SIZE *sizeof(ElemType)); if(!S->base) return ERROR; S

31、->top=S->base; S->stacksize=STACK_INT_SIZE; return OK; }/*InitStack*/ int Push(SqStack *S,ElemType e){ }/*Push*/ int Pop(SqStack *S,ElemType *e){ }/*Pop*/ int CreateStack(SqStack *S){ int e; if(InitStack(S)) printf("Init Success!\n"); else{

32、printf("Init Fail!\n"); return ERROR; } printf("input data:(Terminated by inputing a character)\n"); while(scanf("%d",&e)) Push(S,e); return OK; }/*CreateStack*/ void PrintStack(SqStack *S){ ElemType e; while(Pop(S,&e)) printf("%3d",e); }/*Po

33、p_and_Print*/ int main(){ SqStack ss; printf("\n1-createStack\n"); CreateStack(&ss); printf("\n2-Pop&Print\n"); PrintStack(&ss); return 0; } l 算法分析:輸入元素序列1 2 3 4 5,為什么輸出序列為5 4 3 2 1?表現(xiàn)了棧的什么特性? 2、在第1題的程序中,編寫一個十進(jìn)制轉(zhuǎn)換為二進(jìn)制的數(shù)制轉(zhuǎn)換算法函數(shù)〔要求利用棧來實現(xiàn)〕,并驗證其正確性。 l 實現(xiàn)代碼

34、 l 驗證 3、閱讀并運(yùn)行程序,并分析程序功能。 #include #include #include #define M 20 #define elemtype char typedef struct { elemtype stack[M]; int top; } stacknode; void init(stacknode *st); void push(stacknode *st,elemtype x); void pop(sta

35、cknode *st); void init(stacknode *st) { st->top=0; } void push(stacknode *st,elemtype x) { if(st->top==M) printf("the stack is overflow!\n"); else { st->top=st->top+1; st->stack[st->top]=x; } } void pop(stacknode *st) { if(st->top>0)

36、 st->top--; else printf(“Stack is Empty!\n〞); } int main() { char s[M]; int i; stacknode *sp; printf("create a empty stack!\n"); sp=malloc(sizeof(stacknode)); init(sp); printf("input a expression:\n"); gets(s); for(i=0;i

37、 if(s[i]=='(') push(sp,s[i]); if(s[i]==')') pop(sp); } if(sp->top==0) printf("'('match')'!\n"); else printf("'('not match')'!\n"); return 0; } l 輸入:2+((c-d)*6-(f-7)*a)/6 l 運(yùn)行結(jié)果: l 輸入:a-((c-d)*6-(s/3-x)/2 l 運(yùn)行結(jié)果: l 程

38、序的根本功能: 以下為選做實驗: 4、設(shè)計算法,將一個表達(dá)式轉(zhuǎn)換為后綴表達(dá)式,并按照后綴表達(dá)式進(jìn)展計算,得出表達(dá)式得結(jié)果。 l 實現(xiàn)代碼 5、假設(shè)以帶頭結(jié)點(diǎn)的循環(huán)鏈表表示隊列,并且只設(shè)一個指針指向隊尾結(jié)點(diǎn)〔不設(shè)隊頭指針〕,試編寫相應(yīng)的置空隊列、入隊列、出隊列的算法。 實現(xiàn)代碼: 四、實驗小結(jié) 五、教師評語 實驗三串的模式匹配 一、實驗?zāi)康? 1、了解串的根本概念 2、掌握串的模式匹配算法的實現(xiàn) 二、實驗預(yù)習(xí) 說明以下概念

39、 1、模式匹配: 2、BF算法: 3、KMP算法: 三、實驗容和要求 1、閱讀并運(yùn)行下面程序,根據(jù)輸入寫出運(yùn)行結(jié)果。 #include #include #define MAXSIZE 100 typedef struct{ char data[MAXSIZE]; int length; }SqString; int strpare(SqString *s1,SqString *s2); /*串的比擬*/ void show_strpare(); void strSub(SqString *s,int st

40、art,int sublen,SqString *sub); /*求子串*/ void show_subString(); int strpare(SqString *s1,SqString *s2){ int i; for(i=0;ilength&&ilength;i++) if(s1->data[i]!=s2->data[i]) return s1->data[i]-s2->data[i]; return s1->length-s2->length; } void show_strpare(){ SqString s1

41、,s2; int k; printf("\n***show pare***\n"); printf("input string s1:"); gets(s1.data); s1.length=strlen(s1.data); printf("input string s2:"); gets(s2.data); s2.length=strlen(s2.data); if((k=strpare(&s1,&s2))==0) printf("s1=s2\n"); else if(k<0

42、) printf("s1s2\n"); printf("\n***show over***\n"); } void strSub(SqString *s,int start,int sublen,SqString *sub){ int i; if(start<1||start>s->length||sublen>s->length-start+1){ sub->length=0; } for(i=0;idata[i]=

43、s->data[start+i-1]; sub->length=sublen; } void show_subString(){ SqString s,sub; int start,sublen,i; printf("\n***show subString***\n"); printf("input string s:"); gets(s.data); s.length=strlen(s.data); printf("input start:"); scanf("%d",&start); prin

44、tf("input sublen:"); scanf("%d",&sublen); strSub(&s,start,sublen,&sub); if(sub.length==0) printf("ERROR!\n"); else{ printf("subString is :"); for(i=0;i

45、nt main(){ int n; do { printf("\n---String---\n"); printf("1. strpare\n"); printf("2. subString\n"); printf("0. EXIT\n"); printf("\ninput choice:"); scanf("%d",&n); getchar(); switch(n){ case 1:show_strpare();break;

46、 case 2:show_subString();break; default:n=0;break; } }while(n); return 0; } l 運(yùn)行程序 輸入: 1 student students 2 puter Data Stuctures 10 4 運(yùn)行結(jié)果: 2、實現(xiàn)串的模式匹配算法。補(bǔ)充下面程序,實現(xiàn)串的BF和KMP算法。 #include #include #define MAXSIZE 100 ty

47、pedef struct{ char data[MAXSIZE]; int length; }SqString; int index_bf(SqString *s,SqString *t,int start); void getNext(SqString *t,int next[]); int index_kmp(SqString *s,SqString *t,int start,int next[]); void show_index(); int index_bf(SqString *s,SqString *t,int start){ 補(bǔ)充代碼.....

48、 } void getNext(SqString *t,int next[]){ int i=0,j=-1; next[0]=-1; while(ilength){ if((j==-1)||(t->data[i]==t->data[j])){ i++;j++;next[i]=j; }else j=next[j]; } } int index_kmp(SqString *s,SqString *t,int start,int next[]){ 補(bǔ)充代碼.....

49、 } void show_index(){ SqString s,t; int k,next[MAXSIZE]={0},i; printf("\n***show index***\n"); printf("input string s:"); gets(s.data); s.length=strlen(s.data); printf("input string t:"); gets(t.data); t.length=strlen(t.data); printf("input star

50、t position:"); scanf("%d",&k); printf("BF:\nthe result of BF is %d\n",index_bf(&s,&t,k)); getNext(&t,next); printf("KMP:\n"); printf("next[]:"); for(i=0;i

51、&s,&t,k,next)); printf("\n***show over***\n"); } int main(){ show_index(); return 0; } 輸入: abcaabbabcabaacbacba abcabaa 1 運(yùn)行結(jié)果: 四、實驗小結(jié) 五、教師評語 實驗四二叉樹 一、實驗?zāi)康? 1、掌握二叉樹的根本特性 2、掌握二叉樹的先序、中序、后序的遞歸遍歷算法 3、理解二叉樹的先序、中序、后序的非遞歸遍歷算法 4、通過求二叉樹的深度、葉子結(jié)點(diǎn)數(shù)和層序遍歷等算法,理解二叉樹的根本特性

52、 二、實驗預(yù)習(xí) 說明以下概念 1、二叉樹: 2、遞歸遍歷: 3、 非遞歸遍歷: 4、層序遍歷: 三、實驗容和要求 1、閱讀并運(yùn)行下面程序,根據(jù)輸入寫出運(yùn)行結(jié)果,并畫出二叉樹的形態(tài)。 #include #include #define MAX 20 typedef struct BTNode{ /*節(jié)點(diǎn)結(jié)構(gòu)聲明*/ char data ; /*節(jié)點(diǎn)數(shù)據(jù)*/ struct BTNode *lchild; struct BTNode *rchild ; /*指針*/

53、 }*BiTree; void createBiTree(BiTree *t){ /* 先序遍歷創(chuàng)建二叉樹*/ char s; BiTree q; printf("\nplease input data:(exit for #)"); s=getche(); if(s=='#'){*t=NULL; return;} q=(BiTree)malloc(sizeof(struct BTNode)); if(q==NULL){printf("Memory alloc failure!"); exit(0);} q->data=s; *t=q; crea

54、teBiTree(&q->lchild);/*遞歸建立左子樹*/ createBiTree(&q->rchild); /*遞歸建立右子樹*/ } void PreOrder(BiTree p){ /* 先序遍歷二叉樹*/ if ( p!= NULL ) { printf("%c", p->data); PreOrder( p->lchild ) ; PreOrder( p->rchild) ; } } void InOrder(BiTree p){ /* 中序遍歷二叉樹*/ if( p!=

55、NULL ) { InOrder( p->lchild ) ; printf("%c", p->data); InOrder( p->rchild) ; } } void PostOrder(BiTree p){ /* 后序遍歷二叉樹*/ if ( p!= NULL ) { PostOrder( p->lchild ) ; PostOrder( p->rchild) ; printf("%c", p->data); } } void Preorder_n(BiTree p)

56、{ /*先序遍歷的非遞歸算法*/ BiTree stack[MAX],q; int top=0,i; for(i=0;idata); if(q->rchild!=NULL) stack[top++]=q->rchild; if(q->lchild!=NULL) q=q->lchild; else if(top>0

57、) q=stack[--top]; else q=NULL; } } void release(BiTree t){ /*釋放二叉樹空間*/ if(t!=NULL){ release(t->lchild); release(t->rchild); free(t); } } int main(){ BiTree t=NULL; createBiTree(&t); printf("\n\nPreOrder the tree is:"); PreOrder(

58、t); printf("\n\nInOrder the tree is:"); InOrder(t); printf("\n\nPostOrder the tree is:"); PostOrder(t); printf("\n\n先序遍歷序列〔非遞歸〕:"); Preorder_n(t); release(t); return 0; } l 運(yùn)行程序 輸入: ABC##DE#G##F### 運(yùn)行結(jié)果: 2、在上題中補(bǔ)充求二叉樹中求結(jié)點(diǎn)總數(shù)算法〔提示:可在某種遍歷過程中統(tǒng)計遍歷的結(jié)點(diǎn)數(shù)〕

59、,并在主函數(shù)中補(bǔ)充相應(yīng)的調(diào)用驗證正確性。 算法代碼: 3、在上題中補(bǔ)充求二叉樹中求葉子結(jié)點(diǎn)總數(shù)算法〔提示:可在某種遍歷過程中統(tǒng)計遍歷的葉子結(jié)點(diǎn)數(shù)〕,并在主函數(shù)中補(bǔ)充相應(yīng)的調(diào)用驗證正確性。 算法代碼: 4、在上題中補(bǔ)充求二叉樹深度算法,并在主函數(shù)中補(bǔ)充相應(yīng)的調(diào)用驗證正確性。 算法代碼: 選做實驗:〔代碼可另附紙〕 4、 補(bǔ)充二叉樹層次遍歷算法?!蔡崾荆豪藐犃袑崿F(xiàn)〕 5、補(bǔ)充二叉樹中序、后序非遞歸算法。 四、實驗小結(jié)

60、五、教師評語 實驗五圖的表示與遍歷 一、實驗?zāi)康? 1、掌握圖的鄰接矩陣和鄰接表表示 2、掌握圖的深度優(yōu)先和廣度優(yōu)先搜索方法 3、理解圖的應(yīng)用方法 二、實驗預(yù)習(xí) 說明以下概念 1、深度優(yōu)先搜索遍歷: 2、廣度優(yōu)先搜索遍歷: 3、拓?fù)渑判颍? 4、最小生成樹: 5、最短路徑: 三、實驗容和要求 1、閱讀并運(yùn)行下面程序,根據(jù)輸入寫出運(yùn)行結(jié)果。 #include #define N 20 #define TRUE 1 #define FALSE 0 int visited[N]; typedef struct /*隊

61、列的定義*/ { int data[N]; int front,rear; }queue; typedef struct /*圖的鄰接矩陣*/ { int vexnum,arum; char vexs[N]; int arcs[N][N]; } graph; void createGraph(graph *g); /*建立一個無向圖的鄰接矩陣*/ void dfs(int i,graph *g); /*從第i個頂點(diǎn)出發(fā)深度優(yōu)先搜索*/ void tdfs(graph *g); /*深度優(yōu)先搜索整個圖*/

62、 void bfs(int k,graph *g); /*從第k個頂點(diǎn)廣度優(yōu)先搜索*/ void tbfs(graph *g); /*廣度優(yōu)先搜索整個圖*/ void init_visit(); /*初始化訪問標(biāo)識數(shù)組*/ void createGraph(graph *g) /*建立一個無向圖的鄰接矩陣*/ { int i,j; char v; g->vexnum=0; g->arum=0; i=0; printf("輸入頂點(diǎn)序列(以#完畢):\n"); while((v=

63、getchar())!='#') { g->vexs[i]=v; /*讀入頂點(diǎn)信息*/ i++; } g->vexnum=i; /*頂點(diǎn)數(shù)目*/ for(i=0;ivexnum;i++) /*鄰接矩陣初始化*/ for(j=0;jvexnum;j++) g->arcs[i][j]=0; printf("輸入邊的信息:\n"); scanf("%d,%d",&i,&j); /*讀入邊i,j*/

64、 while(i!=-1) /*讀入i,j為-1時完畢*/ { g->arcs[i][j]=1; g->arcs[j][i]=1; scanf("%d,%d",&i,&j); } } void dfs(int i,graph *g) /*從第i個頂點(diǎn)出發(fā)深度優(yōu)先搜索*/ { int j; printf("%c",g->vexs[i]); visited[i]=TRUE; for(j=0;jvexnum;j++) if((g->a

65、rcs[i][j]==1)&&(!visited[j])) dfs(j,g); } void tdfs(graph *g) /*深度優(yōu)先搜索整個圖*/ { int i; printf("\n從頂點(diǎn)%C開始深度優(yōu)先搜索序列:",g->vexs[0]); for(i=0;ivexnum;i++) if(visited[i]!=TRUE) dfs(i,g); } void bfs(int k,graph *g) /*從第k個頂點(diǎn)廣度優(yōu)先搜索*/ { i

66、nt i,j; queue qlist,*q; q=&qlist; q->rear=0; q->front=0; printf("%c",g->vexs[k]); visited[k]=TRUE; q->data[q->rear]=k; q->rear=(q->rear+1)%N; while(q->rear!=q->front) { i=q->data[q->front]; q->front=(q->front+1)%N; for(j=0;jvexnum;j++) if((g->arcs[i][j]==1)&&(!visited[j])) { printf("%c",g->vexs[j]); visited[j]=TRUE; q->data[q->rear]=j; q->rear=(q-

展開閱讀全文
溫馨提示:
1: 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
2: 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
3.本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
5. 裝配圖網(wǎng)僅提供信息存儲空間,僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對任何下載內(nèi)容負(fù)責(zé)。
6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請與我們聯(lián)系,我們立即糾正。
7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時也不承擔(dān)用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。

相關(guān)資源

更多
正為您匹配相似的精品文檔
關(guān)于我們 - 網(wǎng)站聲明 - 網(wǎng)站地圖 - 資源地圖 - 友情鏈接 - 網(wǎng)站客服 - 聯(lián)系我們

copyright@ 2023-2025  zhuangpeitu.com 裝配圖網(wǎng)版權(quán)所有   聯(lián)系電話:18123376007

備案號:ICP2024067431-1 川公網(wǎng)安備51140202000466號


本站為文檔C2C交易模式,即用戶上傳的文檔直接被用戶下載,本站只是中間服務(wù)平臺,本站所有文檔下載所得的收益歸上傳人(含作者)所有。裝配圖網(wǎng)僅提供信息存儲空間,僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對上載內(nèi)容本身不做任何修改或編輯。若文檔所含內(nèi)容侵犯了您的版權(quán)或隱私,請立即通知裝配圖網(wǎng),我們立即給予刪除!