數(shù)據(jù)結(jié)構(gòu)實驗指導書及其答案

1、PAGE PAGE 60數(shù)據(jù)結(jié)構(gòu)實驗指導及報告書 / 學年 第 學期姓 名：_學 號：_班 級：_指導教師：_計算機科學與工程學院2011預備實驗 C語言的函數(shù)數(shù)組指針結(jié)構(gòu)體知識一、實驗目的1、復習C語言中函數(shù)、數(shù)組、指針和結(jié)構(gòu)體的概念。2、熟悉利用C語言進行程序設計的一般方法。二、實驗內(nèi)容和要求1、調(diào)試程序：輸出100以內(nèi)所有的素數(shù)（用函數(shù)實現(xiàn)）。#include/*判斷一個數(shù)是否為素數(shù)*/int isprime(int n)for(int m=2;m*m=n;m+)if(n%m= =0) return 0;return 1;/*輸出100以內(nèi)所有素數(shù)*/int main()int i;fo

2、r(i=2;i100;i+)if(isprime(i)= =1) printf(“%4d”,i);return 0;運行結(jié)果：2、 調(diào)試程序：對一維數(shù)組中的元素進行逆序排列。#include#define N 10int main()int aN=0,1,2,3,4,5,6,7,8,9,i,temp;printf(“the original Array is:n ”);for(i=0;iN;i+)printf(“%4d”,ai);for(i=0;iN/2;i+)/*交換數(shù)組元素使之逆序*/temp=ai;ai=aN-i-1;aN-i-1=temp;printf(“nthe changed Ar

3、ray is:n”);for(i=0;iN;i+)printf(“%4d”,ai);return 0;運行結(jié)果：3、 調(diào)試程序：在二維數(shù)組中，若某一位置上的元素在該行中最大，而在該列中最小，則該元素即為該二維數(shù)組的一個鞍點。要求從鍵盤上輸入一個二維數(shù)組，當鞍點存在時，把鞍點找出來。#include#define M 3#define N 4int main()int aMN,i,j,k;printf(“請輸入二維數(shù)組的數(shù)據(jù)：n”);for(i=0;iM;i+)for(j=0;jN;j+)scanf(“%d”,&aij);for(i=0;iM;i+)/*輸出矩陣*/for(j=0;jN;j+)p

4、rintf(“%4d”,aij);printf(“n”);for(i=0;iM;i+)k=0;for(j=1;jaik)k=j;for(j=0;jM;j+)/*判斷第i行的最大值是否為該列的最小值*/if(ajkaik)break;if(j=M)/*在第i行找到鞍點*/printf(“%d,%d,%dn”),aik,i,k);return 0;運行結(jié)果：4、 調(diào)試程序：利用指針輸出二維數(shù)組的元素。#includeint main()int a34=1,3,5,7,9,11,13,15,17,19,21,23;int *p;for(p=a0;pa0+12;p+)if(p-a0)%4= =0) p

5、rintf(“n”);printf(%4d”,*p);return 0;運行結(jié)果：5、 調(diào)試程序：輸入10個學生的成績，每個學生成績包括學號、姓名和三門課的成績。要求打印出三門課的平均成績及成績最高者的姓名和成績。#include#define N 10;struct studentchar num6;/*學號*/char name8;/*姓名*/int score3;/*成績*/float avr;/*平均成績*/stuN;int main()int i,j,max,maxi,sum;float average;for(i=0;iN;i+)/*輸入10個學生的成績信息*/printf(“n請

6、輸入第%d學生的成績：n”,i+1);printf(“學號：”);scanf(“%s”,stui.num);printf(“姓名”);scanf(“%s”,);for(j=0;j3;j+)printf(“成績%d”,j+1);scanf(“%d”,&stui.scorej);average=0;max=0;maxi=0;for(i=0;iN;i+)/*計算平均成績，找出成績最高的學生*/sum=0;for(j=0;jmax)max=sum;maxi=i;average/=10;printf(“ 學號 姓名 成績1 成績2 成績3 平均分n);for(i=0;i10;i+)pr

7、intf(“%8s%10s”,stui.num,);for(j=0;j3;j+)printf(“%7d”,stui.scorej);printf(“%6.2fn”,stui.avr);printf(“平均成績是：%5.2fn”,average);printf(“最好成績的學生是：%s，總分是%d”,,max);return 0;三、實驗小結(jié)四、教師評語實驗一 順序表與鏈表一、實驗目的1、掌握線性表中元素的前驅(qū)、后續(xù)的概念。2、掌握順序表與鏈表的建立、插入元素、刪除表中某元素的算法。3、對線性表相應算法的時間復雜度進行分析。4、理解順序表、鏈表數(shù)據(jù)結(jié)構(gòu)的

8、特點（優(yōu)缺點）。 二、實驗內(nèi)容和要求1、閱讀下面程序，在橫線處填寫函數(shù)的基本功能。并運行程序，寫出結(jié)果。#include#include#define ERROR 0#define OK 1#define INIT_SIZE 5 /*初始分配的順序表長度*/#define INCREM 5 /*溢出時，順序表長度的增量*/typedef int ElemType; /*定義表元素的類型*/typedef struct SqlistElemType *slist; /*存儲空間的基地址*/int length; /*順序表的當前長度*/int listsize; /*當前分配的存儲空間*/Sql

9、ist;int InitList_sq(Sqlist *L); /* 初始化順序表L，并將其長度設為0 */int CreateList_sq(Sqlist *L,int n); /* 構(gòu)造順序表的長度為n */int ListInsert_sq(Sqlist *L,int i,ElemType e);/*在順序線性表L中第i個 元素之前插入新的元素e */int PrintList_sq(Sqlist *L); /*輸出順序表的元素*/int ListDelete_sq(Sqlist *L,int i); /*刪除第i個元素*/int ListLocate(Sqlist *L,ElemTyp

10、e 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; /*InitList*/int CreateList_sq(Sqlist *L,int n) ElemType e; int i; for(i=0;in;i+) printf(input data %d,i+1); scanf(%d,&e); if(!Lis

11、tInsert_sq(L,i+1,e) return ERROR; return OK;/*CreateList*/*輸出順序表中的元素*/int PrintList_sq(Sqlist *L) int i; for(i=1;ilength;i+) printf(%5d,L-slisti-1); return OK;/*PrintList*/int ListInsert_sq(Sqlist *L,int i,ElemType e) int k;if(iL-length+1) return ERROR; if(L-length=L-listsize) L-slist=(ElemType*)rea

12、lloc(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-slistk+1=k; L-slisti-1=e; L-length+; return OK;/*ListInsert*/*在順序表中刪除第i個元素*/int ListDelete_sq(Sqlist *L,int i) if(iL-length) return ERROR; for(p=i-1;plength-1;p+) L-slistp=L-

13、slistp+1; L-length-; return OK;/*在順序表中查找指定值元素，返回其序號*/int ListLocate(Sqlist *L,ElemType e) int main() Sqlist sl; int n; printf(please input n:); /*輸入順序表的元素個數(shù)*/ scanf(%d,&n); if(n0) printf(n1-Create Sqlist:n); InitList_sq(&sl); CreateList_sq(&sl,n); printf(n2-Print Sqlist:n); PrintList_sq(&sl); else p

14、rintf(ERROR); return 0;算法分析與運行結(jié)果please input n:51-Create Sqlist:input data 10input data 25input data 38input data 43input data 562-Print Sqlist: 0 5 8 3 6Press any key to continue2、為第1題補充刪除和查找功能函數(shù)，并在主函數(shù)中補充代碼驗證算法的正確性。算法代碼：3、閱讀下面程序，在橫線處填寫函數(shù)的基本功能。并運行程序，寫出結(jié)果。#include#include#define ERROR 0#define OK 1ty

15、pedef int ElemType; /*定義表元素的類型*/typedef struct LNode /*線性表的單鏈表存儲*/ ElemType data; struct LNode *next;LNode,*LinkList;LinkList CreateList(int n);/構(gòu)造順序表的長度 */void PrintList(LinkList L); /*輸出帶頭結(jié)點單鏈表的所有元素*/int GetElem(LinkList L,int i,ElemType *e); /*在順序線性表L中 ，當?shù)趇個元素存在時，將其賦值為e */LinkList CreateList(int

16、n) LNode *p,*q,*head; int i; head=(LinkList)malloc(sizeof(LNode); head-next=NULL; p=head; for(i=0;idata); /*輸入元素值*/ q-next=NULL; /*結(jié)點指針域置空*/ p-next=q; /*新結(jié)點連在表末尾*/ p=q; return head;/*CreateList*/void PrintList(LinkList L) LNode *p; p=L-next; /*p指向單鏈表的第1個元素*/ while(p!=NULL) printf(%5d,p-data); p=p-ne

17、xt; /*PrintList*/int GetElem(LinkList L,int i,ElemType *e) LNode *p;int j=1; p=L-next; while(p&jnext;j+; if(!p|ji) 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(n0) printf(n1-Creat

18、e LinkList: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); else printf(not exists); else printf(ERROR); return 0;算法分析與運行結(jié)果please input n:51-Create LinkList:input data 1:8inp

19、ut data 2:6input data 3:3input data 4:5input data 5:42-Print LinkList: 8 6 3 5 43-GetElem from LinkList:input i=2No2 is 6Press any key to continue4、為第3題補充插入功能函數(shù)和刪除功能函數(shù)。并在主函數(shù)中補充代碼驗證算法的正確性。算法代碼以下為選做實驗：5、循環(huán)鏈表的應用（約瑟夫回環(huán)問題）n個數(shù)據(jù)元素構(gòu)成一個環(huán)，從環(huán)中任意位置開始計數(shù)，計到m將該元素從表中取出，重復上述過程，直至表中只剩下一個元素。提示：用一個無頭結(jié)點的循環(huán)單鏈表來實現(xiàn)n個元素的存儲。

20、算法代碼6、設一帶頭結(jié)點的單鏈表，設計算法將表中值相同的元素僅保留一個結(jié)點。提示：指針p從鏈表的第一個元素開始，利用指針q從指針p位置開始向后搜索整個鏈表，刪除與之值相同的元素；指針p繼續(xù)指向下一個元素，開始下一輪的刪除，直至pnull為至，既完成了對整個鏈表元素的刪除相同值。算法代碼三、實驗小結(jié)四、教師評語實驗二 棧和隊列一、實驗目的1、掌握棧的結(jié)構(gòu)特性及其入棧，出棧操作；2、掌握隊列的結(jié)構(gòu)特性及其入隊、出隊的操作，掌握循環(huán)隊列的特點及其操作。二、實驗內(nèi)容和要求1、閱讀下面程序，將函數(shù)Push和函數(shù)Pop補充完整。要求輸入元素序列1 2 3 4 5 e，運行結(jié)果如下所示。#include#i

21、nclude#define ERROR 0#define OK 1#define STACK_INT_SIZE 10 /*存儲空間初始分配量*/#define STACKINCREMENT 5 /*存儲空間分配增量*/typedef int ElemType; /*定義元素的類型*/typedef struct ElemType *base; ElemType *top; int stacksize; /*當前已分配的存儲空間*/SqStack;int InitStack(SqStack *S); /*構(gòu)造空棧*/int push(SqStack *S,ElemType *e); /*入棧*/

22、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-top=S-base; S-stacksize=STACK_INT_SIZE; return OK;/*InitStack*/int Pu

23、sh(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 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*

24、/void PrintStack(SqStack *S) ElemType e; while(Pop(S,&e) printf(%3d,e);/*Pop_and_Print*/int main() SqStack ss; printf(n1-createStackn); CreateStack(&ss); printf(n2-Pop&Printn); PrintStack(&ss); return 0; 算法分析：輸入元素序列1 2 3 4 5，為什么輸出序列為5 4 3 2 1？體現(xiàn)了棧的什么特性？2、在第1題的程序中，編寫一個十進制轉(zhuǎn)換為二進制的數(shù)制轉(zhuǎn)換算法函數(shù)（要求利用棧來實現(xiàn)），并驗證

25、其正確性。實現(xiàn)代碼3、閱讀并運行程序，并分析程序功能。#include#include#include#define M 20#define elemtype chartypedef struct elemtype stackM; int top;stacknode;void init(stacknode *st);void push(stacknode *st,elemtype x);void pop(stacknode *st);void init(stacknode *st) st-top=0;void push(stacknode *st,elemtype x) if(st-top=M

26、) printf(the stack is overflow!n); else st-top=st-top+1; st-stackst-top=x; void pop(stacknode *st) st-top=st-top-1;int main() char sM; int i; printf(create a empty stack!n); stacknode *sp; sp=malloc(sizeof(stacknode); init(sp); printf(input a expression:n); gets(s); for(i=0;itop=0) printf(match)!n);

27、 else printf(not match)!n); return 0;輸入：2+(c-d)*6-(f-7)*a)/6運行結(jié)果：輸入：a-(c-d)*6-(s/3-x)/2運行結(jié)果：程序的基本功能：以下為選做實驗：4、設計算法，將一個表達式轉(zhuǎn)換為后綴表達式，并按照后綴表達式進行計算，得出表達式得結(jié)果。實現(xiàn)代碼5、假設以帶頭結(jié)點的循環(huán)鏈表表示隊列，并且只設一個指針指向隊尾結(jié)點（不設隊頭指針），試編寫相應的置空隊列、入隊列、出隊列的算法。實現(xiàn)代碼：三、實驗小結(jié)四、教師評語實驗三 串的模式匹配一、實驗目的1、了解串的基本概念2、掌握串的模式匹配算法的實現(xiàn) 二、實驗內(nèi)容和要求1、閱讀并運行下面程序，

28、根據(jù)輸入寫出運行結(jié)果。#include#include#define MAXSIZE 100typedef structchar dataMAXSIZE;int length;SqString;int strCompare(SqString *s1,SqString *s2); /*串的比較*/void show_strCompare();void strSub(SqString *s,int start,int sublen,SqString *sub); /*求子串*/void show_subString();int strCompare(SqString *s1,SqString *s

29、2)int i;for(i=0;ilength&ilength;i+)if(s1-datai!=s2-datai)return s1-datai-s2-datai;return s1-length-s2-length;void show_strCompare() SqString s1,s2; int k; printf(n*show Compare*n); printf(input string s1:); gets(s1.data); s1.length=strlen(s1.data); printf(input string s2:); gets(s2.data); s2.length=

30、strlen(s2.data); if(k=strCompare(&s1,&s2)=0) printf(s1=s2n); else if(k0) printf(s1s2n); printf(n*show over*n);void strSub(SqString *s,int start,int sublen,SqString *sub)int i;if(starts-length|sublens-length-start+1)sub-length=0;for(i=0;idatai=s-datastart+i-1;sub-length=sublen;void show_subString() S

31、qString 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); printf(input sublen:); scanf(%d,&sublen); strSub(&s,start,sublen,&sub); if(sub.length=0) printf(ERROR!n); else printf(subString is :)

32、; for(i=0;isublen;i+) printf(%c,sub.datai); printf(n*show over*n);int main() int n; do printf(nStringn); printf(1. strComparen); printf(2. subStringn); printf(0. EXITn); printf(ninput choice:); scanf(%d,&n); getchar(); switch(n) case 1:show_strCompare();break; case 2:show_subString();break; default:

33、n=0;break; while(n); return 0;運行程序輸入：1studentstudents2Computer Data Stuctures104運行結(jié)果：2、實現(xiàn)串的模式匹配算法。補充下面程序，實現(xiàn)串的BF和KMP算法。#include#include#define MAXSIZE 100typedef structchar dataMAXSIZE;int length;SqString;int index_bf(SqString *s,SqString *t,int start);void getNext(SqString *t,int next);int index_kmp

34、(SqString *s,SqString *t,int start,int next);void show_index();int index_bf(SqString *s,SqString *t,int start)補充代碼void getNext(SqString *t,int next)int i=0,j=-1;next0=-1;while(ilength)if(j=-1)|(t-datai=t-dataj)i+;j+;nexti=j;elsej=nextj; int index_kmp(SqString *s,SqString *t,int start,int next)補充代碼vo

35、id show_index() SqString s,t; int k,nextMAXSIZE=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 start position:); scanf(%d,&k); printf(BF:nthe result of BF is %dn,index_bf(&s,&t,

36、k); getNext(&t,next); printf(KMP:n); printf(next:); for(i=0;it.length;i+) printf(%3d,nexti); printf(n); printf(the result of KMP is %dn,index_kmp(&s,&t,k,next); printf(n*show over*n);int main()show_index();return 0;輸入：abcaabbabcabaacbacbaabcabaa1運行結(jié)果：三、實驗小結(jié)四、教師評語實驗四 二叉樹一、實驗目的1、掌握二叉樹的基本特性2、掌握二叉樹的遞歸遍歷

37、算法 3、理解二叉樹的非遞歸算法4、通過二叉樹的深度和層次遍歷算法，理解二叉樹的基本特性二、實驗內(nèi)容和要求1、閱讀并運行下面程序，根據(jù)輸入寫出運行結(jié)果，并畫出二叉樹的形態(tài)。#include#include#define MAX 20typedef struct BTNode /*節(jié)點結(jié)構(gòu)聲明*/char data ; /*節(jié)點數(shù)據(jù)*/struct BTNode *lchild;struct BTNode *rchild ; /*指針*/*BiTree;void createBiTree(BiTree *t) /* 先序遍歷創(chuàng)建二叉樹*/char s;BiTree q;printf(npleas

38、e 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;createBiTree(&q-lchild); /*遞歸建立左子樹*/createBiTree(&q-rchild); /*遞歸建立右子樹*/void PreOrder(BiTree p) /* 先序遍歷二叉樹*/ if ( p!= NULL ) printf(%c, p-

39、data); PreOrder( p-lchild ) ; PreOrder( p-rchild) ; void InOrder(BiTree p) /* 中序遍歷二叉樹*/ if( p!= 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

40、_n(BiTree p) /*先序遍歷的非遞歸算法*/ BiTree stackMAX,q; int top=0,i; for(i=0;idata); if(q-rchild!=NULL) stacktop+=q-rchild; if(q-lchild!=NULL) q=q-lchild; else if(top0) 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=

41、NULL; createBiTree(&t); printf(nnPreOrder the tree is:); PreOrder(t); printf(nnInOrder the tree is:); InOrder(t); printf(nnPostOrder the tree is:); PostOrder(t); printf(nn先序遍歷序列（非遞歸）:); Preorder_n(t); release(t); return 0;運行程序輸入：ABC#DE#G#F#運行結(jié)果：2、在上題中補充求二叉樹中求結(jié)點總數(shù)算法（提示：可在某種遍歷過程中統(tǒng)計遍歷的結(jié)點數(shù)），并在主函數(shù)中補充相應的調(diào)

42、用驗證正確性。算法代碼：3、在上題中補充求二叉樹中求葉子結(jié)點總數(shù)算法（提示：可在某種遍歷過程中統(tǒng)計遍歷的葉子結(jié)點數(shù)），并在主函數(shù)中補充相應的調(diào)用驗證正確性。算法代碼：4、在上題中補充求二叉樹深度算法，并在主函數(shù)中補充相應的調(diào)用驗證正確性。算法代碼：選做實驗：（代碼可另附紙）5、補充二叉樹層次遍歷算法。（提示：利用隊列實現(xiàn)）6、補充二叉樹中序、后序非遞歸算法。三、實驗小結(jié)四、教師評語實驗五 圖的表示與遍歷一、實驗目的1、掌握圖的鄰接矩陣和鄰接表表示2、掌握圖的深度優(yōu)先和廣度優(yōu)先搜索方法 3、理解圖的應用方法二、實驗內(nèi)容和要求1、閱讀并運行下面程序，根據(jù)輸入寫出運行結(jié)果。#include#defi

43、ne N 20#define TRUE 1#define FALSE 0int visitedN; typedef struct /*隊列的定義*/ int dataN; int front,rear;queue;typedef struct /*圖的鄰接矩陣*/ int vexnum,arcnum; char vexsN; int arcsNN;graph;void createGraph(graph *g); /*建立一個無向圖的鄰接矩陣*/void dfs(int i,graph *g); /*從第i個頂點出發(fā)深度優(yōu)先搜索*/void tdfs(graph *g); /*深度優(yōu)先搜索整個

44、圖*/void bfs(int k,graph *g); /*從第k個頂點廣度優(yōu)先搜索*/void tbfs(graph *g); /*廣度優(yōu)先搜索整個圖*/void init_visit(); /*初始化訪問標識數(shù)組*/void createGraph(graph *g) /*建立一個無向圖的鄰接矩陣*/ int i,j; char v; g-vexnum=0; g-arcnum=0; i=0; printf(輸入頂點序列(以#結(jié)束)：n); while(v=getchar()!=#) g-vexsi=v; /*讀入頂點信息*/ i+; g-vexnum=i; /*頂點數(shù)目*/ for(i=

45、0;ivexnum;i+) /*鄰接矩陣初始化*/ for(j=0;jvexnum;j+) g-arcsij=0; printf(輸入邊的信息：n); scanf(%d,%d,&i,&j); /*讀入邊i,j*/ while(i!=-1) /*讀入i,j為1時結(jié)束*/ g-arcsij=1; g-arcsji=1; scanf(%d,%d,&i,&j); void dfs(int i,graph *g) /*從第i個頂點出發(fā)深度優(yōu)先搜索*/ int j; printf(%c,g-vexsi); visitedi=TRUE; for(j=0;jvexnum;j+) if(g-arcsij=1)&

46、(!visitedj) dfs(j,g);void tdfs(graph *g) /*深度優(yōu)先搜索整個圖*/ int i; printf(n從頂點%C開始深度優(yōu)先搜索序列：,g-vexs0); for(i=0;ivexnum;i+) if(visitedi!=TRUE) dfs(i,g);void bfs(int k,graph *g) /*從第k個頂點廣度優(yōu)先搜索*/ int i,j; queue qlist,*q; q=&qlist; q-rear=0; q-front=0; printf(%c,g-vexsk); visitedk=TRUE; q-dataq-rear=k; q-rear

47、=(q-rear+1)%N; while(q-rear!=q-front) i=q-dataq-front; q-front=(q-front+1)%N; for(j=0;jvexnum;j+) if(g-arcsij=1)&(!visitedj) printf(%c,g-vexsj); visitedj=TRUE; q-dataq-rear=j; q-rear=(q-rear+1)%N; void tbfs(graph *g) /*廣度優(yōu)先搜索整個圖*/ int i; printf(n從頂點%C開始廣度優(yōu)先搜索序列：,g-vexs0); for(i=0;ivexnum;i+) if(visi

48、tedi!=TRUE) bfs(i,g);void init_visit() /*初始化訪問標識數(shù)組*/ int i; for(i=0;iN;i+) visitedi=FALSE;int main() graph ga; int i,j; createGraph(&ga); printf(無向圖的鄰接矩陣：n);for(i=0;iga.vexnum;i+) for(j=0;jga.vexnum;j+) printf(%3d,ga.arcsij); printf(n); init_visit(); tdfs(&ga); init_visit(); tbfs(&ga); return 0;根據(jù)右圖

49、的結(jié)構(gòu)驗證實驗，輸入：ABCDEFGH#0,10,20,51,31,42,52,63,74,7-1,-1運行結(jié)果：2、閱讀并運行下面程序，補充拓撲排序算法。#include#include#define N 20typedef struct edgenode /*圖的鄰接表：鄰接鏈表結(jié)點*/ int adjvex; /*頂點序號*/ struct edgenode *next; /*下一個結(jié)點的指針*/edgenode;typedef struct vnode /*圖的鄰接表：鄰接表*/ char data; /*頂點信息*/ int ind; /*頂點入度*/ struct edgenode

50、 *link; /*指向鄰接鏈表指針*/vnode;void createGraph_list(vnode adjlist,int *p)； /*建立有向圖的鄰接表*/void topSort(vnode g,int n)； /*拓撲排序*/void createGraph_list(vnode adjlist,int *p) /*建立有向圖的鄰接表*/ int i,j,n,e; char v; edgenode *s; i=0;n=0;e=0; printf(輸入頂點序列(以#結(jié)束)：n); while(v=getchar()!=#) adjlisti.data=v; /*讀入頂點信息*/

51、adjlisti.link=NULL; adjlisti.ind=0; i+; n=i; *p=n; /*建立鄰接鏈表*/ printf(n請輸入弧的信息(i=-1結(jié)束)：i,j:n); scanf(%d,%d,&i,&j); while(i!=-1) s=(struct edgenode*)malloc(sizeof(edgenode); s-adjvex=j; s-next=adjlisti.link; adjlisti.link=s; adjlistj.ind+; /*頂點j的入度加1*/ e+; scanf(%d,%d,&i,&j); printf(鄰接表:); for(i=0;i%d

52、,s-adjvex); s=s-next; void topSort(vnode g,int n) /*拓撲排序*/ int main() vnode adjlistN; int n,*p; p=&n; createGraph_list(adjlist,p); return 0;根據(jù)輸入，輸出有向圖的拓撲排序序列。并畫出有向圖。輸入:ABCDEF#0,11,22,34,14,5-1,-1運行結(jié)果：3、閱讀并運行下面程序。#include#define N 20#define TRUE 1#define INF 32766 /*鄰接矩陣中的無窮大元素*/#define INFIN 32767 /

53、*比無窮大元素大的數(shù)*/typedef struct /*圖的鄰接矩陣*/ int vexnum,arcnum; char vexsN; int arcsNN;graph;void createGraph_w(graph *g,int flag);void prim(graph *g,int u);void dijkstra(graph g,int v);void showprim();void showdij();/*建帶權(quán)圖的鄰接矩陣,若flag為1則為無向圖，flag為0為有向圖*/void createGraph_w(graph *g,int flag) int i,j,w; char

54、 v; g-vexnum=0; g-arcnum=0; i=0; printf(輸入頂點序列(以#結(jié)束)：n); while(v=getchar()!=#) g-vexsi=v; /*讀入頂點信息*/ i+; g-vexnum=i; for(i=0;i6;i+) /*鄰接矩陣初始化*/ for(j=0;jarcsij=INF; printf(輸入邊的信息：n); scanf(%d,%d,%d,&i,&j,&w); /*讀入邊(i,j,w)*/ while(i!=-1) /*讀入i為1時結(jié)束*/ g-arcsij=w; if(flag=1) g-arcsji=w; scanf(%d,%d,%d,

55、&i,&j,&w); void prim(graph *g,int u)/*出發(fā)頂點u*/ int lowcostN,closestN,i,j,k,min; for(i=0;ivexnum;i+) /*求其他頂點到出發(fā)頂點u的權(quán)*/ lowcosti=g-arcsui; closesti=u; lowcostu=0; for(i=1;ivexnum;i+) /*循環(huán)求最小生成樹中的各條邊*/ min=INFIN; for(j=0;jvexnum;j+) /*選擇得到一條代價最小的邊*/ if(lowcostj!=0&lowcostjvexsclosestk,g-vexsk,lowcostk);

56、 /*輸出該邊*/ lowcostk=0; /*頂點k納入最小生成樹 */ for(j=0;jvexnum;j+) /*求其他頂點到頂點k 的權(quán)*/ if(g-arcskj!=0&g-arcskjarcskj; closestj=k; void dijkstra(graph g,int v) /*dijkstra算法求單源最短路徑*/ int pathNN,distN,sN; int mindis,i,j,u,k; for(i=0;ig.vexnum;i+) disti=g.arcsvi; si=0; for(j=0;jg.vexnum;j+) pathij=0; if(distiINF) p

57、athiv=1; pathii=1; distv=0; sv=1; for(i=0,u=1;ig.vexnum;i+) mindis=INFIN; for(j=0;jg.vexnum;j+) if(sj=0) if(distjmindis) u=j; mindis=distj; su=1; for(j=0;jg.vexnum;j+) if(sj=0)&distu+g.arcsujdistj) distj=distu+g.arcsuj; for(k=0;k到各頂點的最短路徑n,g.vexsv); for(i=0;i頂點%c：,g.vexsv,g.vexsi); if(disti=INF) pri

58、ntf(無路徑); else printf(%d ,disti); printf(經(jīng)過頂點：); for(j=0;j%c,g.vexsj); printf(-%cn,g.vexsi); void showprim()/*最小生成樹prim算法演示*/ graph ga; createGraph_w(&ga,1); prim(&ga,0);void showdij() /*dijstra算法演示*/ graph ga; createGraph_w(&ga,0); dijkstra(ga,0);int main()showprim(); /*prim算法演示*/getchar(); showdij

59、(); /*dijstra算法演示*/ return 0;下面的輸入分別驗證prim算法和dijstra算法。輸入的第一部分為無向圖，求其最小生成樹；輸入的第二部分為有向圖，求其最短路徑。ABCDEF#0,1,60,2,10,3,51,2,51,4,32,3,52,4,62,5,43,5,24,5,6-1,-1,-1ABCDEF#0,2,100,5,1000,4,301,2,52,3,503,4,203,5,104,3,204,5,60-1,-1,-1運行結(jié)果：（并畫出兩個圖）三、實驗小結(jié)四、教師評語實驗六 查找一、實驗目的1、掌握查找表、動態(tài)查找表、靜態(tài)查找表和平均查找長度的概念。2、掌握線

60、性表中順序查找和折半查找的方法。3、學會哈希函數(shù)的構(gòu)造方法，處理沖突的機制以及哈希表的查找。二、實驗內(nèi)容和要求1. 靜態(tài)查找表技術依據(jù)順序查找算法和折半查找算法的特點，對下面的兩個查找表選擇一個合適的算法，設計出完整的C源程序。并完成問題：查找表1 ： 8 ，15 ，19 ，26 ，33 ，41 ，47 ，52 ，64 ，90 ，查找key = 41查找表2 ： 12 ，76 ，29 ，15 ，62 ，35 ，33 ，89 ，48 ，20 ，查找key =35查找key=41的比較次數(shù)：查找key=35的比較次數(shù)：算法實現(xiàn)代碼2、哈希表的構(gòu)造與查找/* 采用開放地址法構(gòu)造哈希表*/#inclu