《大數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)資料報(bào)告材料 - 問題詳解》由會員分享，可在線閱讀，更多相關(guān)《大數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)資料報(bào)告材料 - 問題詳解（25頁珍藏版）》請?jiān)谘b配圖網(wǎng)上搜索。

1、word 數(shù)據(jù)結(jié)構(gòu)(C語言版) 實(shí)驗(yàn)報(bào)告 專業(yè) 班級學(xué)號 實(shí)驗(yàn)1 實(shí)驗(yàn)題目：單鏈表的插入和刪除 實(shí)驗(yàn)?zāi)康模? 了解和掌握線性表的邏輯結(jié)構(gòu)和鏈?zhǔn)酱鎯Y(jié)構(gòu)，掌握單鏈表的根本算法與相關(guān)的時(shí)間性能分析。 實(shí)驗(yàn)要求： 建立一個(gè)數(shù)據(jù)域定義為字符串的單鏈表，在鏈表中不允許有重復(fù)的字符串；根據(jù)輸入的字符串，先找到相應(yīng)的結(jié)點(diǎn)，后刪除之。 實(shí)驗(yàn)主要步驟： 1、 分析、理解給出的示例程序。 2、 調(diào)試程序，并設(shè)計(jì)輸入數(shù)據(jù)〔如：bat，cat，eat，fat，hat，jat，lat，mat，#〕，測試程序的如下功能：不允許重復(fù)字

2、符串的插入；根據(jù)輸入的字符串，找到相應(yīng)的結(jié)點(diǎn)并刪除。 3、 修改程序： （1） 增加插入結(jié)點(diǎn)的功能。 （2） 將建立鏈表的方法改為頭插入法。 程序代碼: #include"stdio.h" #include"string.h" #include"stdlib.h" #include"ctype.h" typedef struct node //定義結(jié)點(diǎn) { char data[10]; //結(jié)點(diǎn)的數(shù)據(jù)域?yàn)樽址? struct node *next; //結(jié)點(diǎn)的指針域 }ListNode; typedef L

3、istNode * LinkList; // 自定義LinkList單鏈表類型 LinkList CreatListR1(); //函數(shù)，用尾插入法建立帶頭結(jié)點(diǎn)的單鏈表 LinkList CreatList(void); //函數(shù)，用頭插入法建立帶頭結(jié)點(diǎn)的單鏈表 ListNode *LocateNode(); //函數(shù)，按值查找結(jié)點(diǎn) void DeleteList(); //函數(shù)，刪除指定值的結(jié)點(diǎn) void printlist();

4、 //函數(shù)，打印鏈表中的所有值 void DeleteAll(); //函數(shù)，刪除所有結(jié)點(diǎn)，釋放存 ListNode * AddNode(); //修改程序：增加節(jié)點(diǎn)。用頭插法，返回頭指針 //==========主函數(shù)============== void main() { char ch[10],num[5]; LinkList head; head=CreatList(); //用頭插入法建立單鏈表，返回頭指針 printlist(head); //遍歷鏈表輸出其值 pr

5、intf(" Delete node (y/n):"); //輸入"y"或"n"去選擇是否刪除結(jié)點(diǎn) scanf("%s",num); if(strcmp(num,"y")==0 || strcmp(num,"Y")==0){ printf("Please input Delete_data:"); scanf("%s",ch); //輸入要刪除的字符串 DeleteList(head,ch); printlist(head); } printf(" Add node ? (y/n):"); //輸入"y"或"n"去選擇是否增加結(jié)點(diǎn) scanf("%s",nu

6、m); if(strcmp(num,"y")==0 || strcmp(num,"Y")==0) { head=AddNode(head); } printlist(head); DeleteAll(head); //刪除所有結(jié)點(diǎn)，釋放存 } //==========用尾插入法建立帶頭結(jié)點(diǎn)的單鏈表=========== LinkList CreatListR1(void) { char ch[10]; LinkList head=(LinkList)malloc(sizeof(ListNode)); //生成頭結(jié)點(diǎn) L

7、istNode *s,*r,*pp; r=head; r->next=NULL; printf("Input # to end "); //輸入"#"代表輸入完畢 printf("\nPlease input Node_data:"); scanf("%s",ch); //輸入各結(jié)點(diǎn)的字符串 while(strcmp(ch,"#")!=0) { pp=LocateNode(head,ch); //按值查找結(jié)點(diǎn)，返回結(jié)點(diǎn)指針 if(pp==NULL) {

8、 //沒有重復(fù)的字符串，插入到鏈表中 s=(ListNode *)malloc(sizeof(ListNode)); strcpy(s->data,ch); r->next=s; r=s; r->next=NULL; } printf("Input # to end "); printf("Please input Node_data:"); scanf("%s",ch); } return head; //返回頭指針 } //==========用頭插入法建立帶頭結(jié)點(diǎn)的單鏈表=========== LinkList Cre

9、atList(void) { char ch[100]; LinkList head,p; head=(LinkList)malloc(sizeof(ListNode)); head->next=NULL; while(1) { printf("Input # to end "); printf("Please input Node_data:"); scanf("%s",ch); if(strcmp(ch,"#")) { if(LocateNode(head,ch)==NULL) { strcpy(head

10、->data,ch); p=(LinkList)malloc(sizeof(ListNode)); p->next=head; head=p; } } else break; } return head; } //==========按值查找結(jié)點(diǎn)，找到如此返回該結(jié)點(diǎn)的位置，否如此返回NULL========== ListNode *LocateNode(LinkList head, char *key) { ListNode *p=head->next; //從開始結(jié)點(diǎn)比擬 while(p!=NULL && strcmp(p

11、->data,key)!=0) //直到p為NULL或p->data為key止 p=p->next; //掃描下一個(gè)結(jié)點(diǎn) return p; //假設(shè)p=NULL如此查找失敗，否如此p指向找到的值為key的結(jié)點(diǎn) } //==========修改程序：增加節(jié)點(diǎn)======= ListNode * AddNode(LinkList head) { char ch[10]; ListNode *s,*pp; printf("\nPlease input a New Node_data:"); scanf("%s",ch

12、); //輸入各結(jié)點(diǎn)的字符串 pp=LocateNode(head,ch); //按值查找結(jié)點(diǎn)，返回結(jié)點(diǎn)指針 printf("ok2\n"); if(pp==NULL) { //沒有重復(fù)的字符串，插入到鏈表中 s=(ListNode *)malloc(sizeof(ListNode)); strcpy(s->data,ch); printf("ok3\n"); s->next=head->next; head->next=s; } return head; } //==========刪除帶頭結(jié)

13、點(diǎn)的單鏈表中的指定結(jié)點(diǎn)======= void DeleteList(LinkList head,char *key) { ListNode *p,*r,*q=head; p=LocateNode(head,key); //按key值查找結(jié)點(diǎn)的 if(p==NULL ) { //假設(shè)沒有找到結(jié)點(diǎn)，退出 printf("position error"); exit(0); } while(q->next!=p) //p為要刪除的結(jié)點(diǎn)，q為p的前結(jié)點(diǎn) q=q->next; r=q->ne

14、xt; q->next=r->next; free(r); //釋放結(jié)點(diǎn) } //===========打印鏈表======= void printlist(LinkList head) { ListNode *p=head->next; //從開始結(jié)點(diǎn)打印 while(p){ printf("%s, ",p->data); p=p->next; } printf("\n"); } //==========刪除所有結(jié)點(diǎn)，釋放空間=========== void Delet

15、eAll(LinkList head) { ListNode *p=head,*r; while(p->next){ r=p->next; free(p); p=r; } free(p); } 實(shí)驗(yàn)結(jié)果： Input # to end Please input Node_data:bat Input # to end Please input Node_data:cat Input # to end Please input Node_data:eat Input # to end Please input Node_data:fat

16、 Input # to end Please input Node_data:hat Input # to end Please input Node_data:jat Input # to end Please input Node_data:lat Input # to end Please input Node_data:mat Input # to end Please input Node_data:# mat, lat, jat, hat, fat, eat, cat, bat, Delete node (y/n):y Ple

17、ase input Delete_data:hat mat, lat, jat, fat, eat, cat, bat, Insert node (y/n):y Please input Insert_data:put position :5 mat, lat, jat, fat, eat, put, cat, bat, 請按任意鍵繼續(xù). . . 示意圖： lat jat hat fat eat cat bat mat NULL head lat jat hat

18、fat eat cat bat mat head lat jat fat eat put cat bat mat head NULL NULL 心得體會： 本次實(shí)驗(yàn)使我們對鏈表的實(shí)質(zhì)了解更加明確了，對鏈表的一些根本操作也更加熟練了。另外實(shí)驗(yàn)指導(dǎo)書上給出的代碼是有一些問題的，這使我們認(rèn)識到實(shí)驗(yàn)過程中不能想當(dāng)然的直接編譯執(zhí)行，應(yīng)當(dāng)在閱讀并完全理解代碼的根底上再執(zhí)行，這才是實(shí)驗(yàn)的意義所在。 實(shí)驗(yàn)2 實(shí)驗(yàn)題目：二叉樹操作設(shè)計(jì)和實(shí)現(xiàn) 實(shí)驗(yàn)?zāi)康模? 掌握二叉樹的定義、性質(zhì)與存儲方式，各種遍歷算法。 實(shí)驗(yàn)要求： 采

19、用二叉樹鏈表作為存儲結(jié)構(gòu)，完成二叉樹的建立，先序、中序和后序以與按層次遍歷的操作，求所有葉子與結(jié)點(diǎn)總數(shù)的操作。 實(shí)驗(yàn)主要步驟： 1、 分析、理解程序。 2、 調(diào)試程序，設(shè)計(jì)一棵二叉樹，輸入完全二叉樹的先序序列，用#代表虛結(jié)點(diǎn)〔空指針〕，如ABD###CE##F##，建立二叉樹，求出先序、中序和后序以與按層次遍歷序列，求所有葉子與結(jié)點(diǎn)總數(shù)。 實(shí)驗(yàn)代碼 #include"stdio.h" #include"stdlib.h" #include"string.h" #define Max 20 //結(jié)點(diǎn)的最大個(gè)數(shù) typedef struct node{

20、 char data; struct node *lchild,*rchild; }BinTNode; //自定義二叉樹的結(jié)點(diǎn)類型 typedef BinTNode *BinTree; //定義二叉樹的指針 int NodeNum,leaf; //NodeNum為結(jié)點(diǎn)數(shù)，leaf為葉子數(shù) //==========基于先序遍歷算法創(chuàng)建二叉樹============== //=====要求輸入先序序列，其中參加虛結(jié)點(diǎn)"#"以示空指針的位置========== BinTree CreatBinTree(void) {

21、 BinTree T; char ch; if((ch=getchar())=='#') return(NULL); //讀入#，返回空指針 else{ T= (BinTNode *)malloc(sizeof(BinTNode)); //生成結(jié)點(diǎn) T->data=ch; T->lchild=CreatBinTree(); //構(gòu)造左子樹 T->rchild=CreatBinTree(); //構(gòu)造右子樹 return(T); } } //========NLR 先

22、序遍歷============= void Preorder(BinTree T) { if(T) { printf("%c",T->data); //訪問結(jié)點(diǎn) Preorder(T->lchild); //先序遍歷左子樹 Preorder(T->rchild); //先序遍歷右子樹 } } //========LNR 中序遍歷=============== void Inorder(BinTree T) { if(T) { Inorder(T->lchild); //中序遍歷左子樹 printf("%c",T-

23、>data); //訪問結(jié)點(diǎn) Inorder(T->rchild); //中序遍歷右子樹 } } //==========LRN 后序遍歷============ void Postorder(BinTree T) { if(T) { Postorder(T->lchild); //后序遍歷左子樹 Postorder(T->rchild); //后序遍歷右子樹 printf("%c",T->data); //訪問結(jié)點(diǎn) } } //=====采用后序遍歷求二叉樹的深度、結(jié)點(diǎn)數(shù)與葉子數(shù)的遞歸算法========

24、int TreeDepth(BinTree T) { int hl,hr,max; if(T){ hl=TreeDepth(T->lchild); //求左深度 hr=TreeDepth(T->rchild); //求右深度 max=hl>hr? hl:hr; //取左右深度的最大值 NodeNum=NodeNum+1; //求結(jié)點(diǎn)數(shù) if(hl==0&&hr==0) leaf=leaf+1; //假設(shè)左右深度為0，即為葉子。 return(max+1); } else return(0);

25、 } //====利用"先進(jìn)先出"〔FIFO〕隊(duì)列，按層次遍歷二叉樹========== void Levelorder(BinTree T) { int front=0,rear=1; BinTNode *cq[Max],*p; //定義結(jié)點(diǎn)的指針數(shù)組cq cq[1]=T; //根入隊(duì) while(front!=rear) { front=(front+1)%NodeNum; p=cq[front]; //出隊(duì) printf("%c",p->data);

26、//出隊(duì)，輸出結(jié)點(diǎn)的值 if(p->lchild!=NULL){ rear=(rear+1)%NodeNum; cq[rear]=p->lchild; //左子樹入隊(duì) } if(p->rchild!=NULL){ rear=(rear+1)%NodeNum; cq[rear]=p->rchild; //右子樹入隊(duì) } } } //====數(shù)葉子節(jié)點(diǎn)個(gè)數(shù)========== int countleaf(BinTree T) { int hl,hr; if(T){ hl=countleaf(T->lc

27、hild); hr=countleaf(T->rchild); if(hl==0&&hr==0) //假設(shè)左右深度為0，即為葉子。 return(1); else return hl+hr; } else return 0; } //==========主函數(shù)================= void main() { BinTree root; char i; int depth; printf("\n"); printf("Creat Bin_Tree； Input preorder:"); //輸入完全二叉樹的先序

28、序列， // 用#代表虛結(jié)點(diǎn)，如ABD###CE##F## root=CreatBinTree(); //創(chuàng)建二叉樹，返回根結(jié)點(diǎn) do { //從菜單中選擇遍歷方式，輸入序號。 printf("\t********** select ************\n"); printf("\t1: Preorder Traversal\n"); printf("\t2: Iorder Traversal\n"); printf("\t3: Postorder t

29、raversal\n"); printf("\t4: PostTreeDepth,Node number,Leaf number\n"); printf("\t5: Level Depth\n"); //按層次遍歷之前，先選擇4，求出該樹的結(jié)點(diǎn)數(shù)。 printf("\t0: Exit\n"); printf("\t*******************************\n"); fflush(stdin); scanf("%c",&i); //輸入菜單序號〔0-5〕 switch (i-'0'){ case 1: printf("Print Bin_tree Pr

30、eorder: "); Preorder(root); //先序遍歷 break; case 2: printf("Print Bin_Tree Inorder: "); Inorder(root); //中序遍歷 break; case 3: printf("Print Bin_Tree Postorder: "); Postorder(root); //后序遍歷 break; case 4: depth=TreeDepth(root); //求樹的深度與葉子數(shù) printf("BinTree Depth=%d BinTree No

31、de number=%d",depth,NodeNum); printf(" BinTree Leaf number=%d",countleaf(root)); break; case 5: printf("LevePrint Bin_Tree: "); Levelorder(root); //按層次遍歷 break; default: exit(1); } printf("\n"); } while(i!=0); } 實(shí)驗(yàn)結(jié)果： Creat Bin_Tree； Input preorder:ABD###CE##F##

32、 ********** select ************ 1: Preorder Traversal 2: Iorder Traversal 3: Postorder traversal 4: PostTreeDepth,Node number,Leaf number 5: Level Depth

33、 0: Exit ******************************* 1 Print Bin_tree Preorder: ABDCEF 2 Print Bin_Tree Inorder:

34、 DBAECF 3 Print Bin_Tree Postorder: DBEFCA 4 BinTree Depth=3 BinTree Node number=6 BinTree Leaf number=3 5 LevePrint Bin_Tree: ABCDEF 0

35、 Press any key to continue 二叉樹示意圖 A B F E D C 心得體會： 這次實(shí)驗(yàn)加深了我對二叉樹的印象，尤其是對二叉樹的各種遍歷操作有了一定的了解。同時(shí)認(rèn)識到，在設(shè)計(jì)程序時(shí)輔以圖形化的描述是非常有用處的。 實(shí)驗(yàn)3 實(shí)驗(yàn)題目：圖的遍歷操作 實(shí)驗(yàn)?zāi)康模? 掌握有向圖和無向圖的概念；掌握鄰接矩陣和鄰接鏈表建立圖的存儲結(jié)構(gòu)；掌握DFS與BFS對圖的遍歷操作；了解圖結(jié)構(gòu)在人工智能、工程等領(lǐng)域的廣泛應(yīng)用。 實(shí)驗(yàn)要求： 采用鄰接矩陣和鄰接鏈表作為圖的存儲結(jié)構(gòu)，完成有向圖和無向圖的DFS和

36、BFS操作。 實(shí)驗(yàn)主要步驟： 設(shè)計(jì)一個(gè)有向圖和一個(gè)無向圖，任選一種存儲結(jié)構(gòu)，完成有向圖和無向圖的DFS〔深度優(yōu)先遍歷〕和BFS〔廣度優(yōu)先遍歷〕的操作。 1． 鄰接矩陣作為存儲結(jié)構(gòu) #include"stdio.h" #include"stdlib.h" #define MaxVertexNum 100 //定義最大頂點(diǎn)數(shù) typedef struct{ char vexs[MaxVertexNum]; //頂點(diǎn)表 int edges[MaxVertexNum][MaxVertexNum]; //鄰接矩陣，可看作邊表

37、int n,e; //圖中的頂點(diǎn)數(shù)n和邊數(shù)e }MGraph; //用鄰接矩陣表示的圖的類型 //=========建立鄰接矩陣======= void CreatMGraph(MGraph *G) { int i,j,k; char a; printf("Input VertexNum(n) and EdgesNum(e): "); scanf("%d,%d",&G->n,&G->e); //輸入頂點(diǎn)數(shù)和邊數(shù) scanf("%c",&a);

38、 printf("Input Vertex string:"); for(i=0;in;i++) { scanf("%c",&a); G->vexs[i]=a; //讀入頂點(diǎn)信息，建立頂點(diǎn)表 } for(i=0;in;i++) for(j=0;jn;j++) G->edges[i][j]=0; //初始化鄰接矩陣 printf("Input edges,Creat Adjacency Matrix\n"); for(k=0;ke;k+

39、+) { //讀入e條邊，建立鄰接矩陣 scanf("%d%d",&i,&j); //輸入邊〔Vi，Vj〕的頂點(diǎn)序號 G->edges[i][j]=1; G->edges[j][i]=1; //假設(shè)為無向圖，矩陣為對稱矩陣；假設(shè)建立有向圖，去掉該條語句 } } //=========定義標(biāo)志向量，為全局變量======= typedef enum{FALSE,TRUE} Boolean; Boolean visited[MaxVertexNum]; //========DFS：深度優(yōu)先遍歷的遞歸算法====== voi

40、d DFSM(MGraph *G,int i) { //以Vi為出發(fā)點(diǎn)對鄰接矩陣表示的圖G進(jìn)展DFS搜索，鄰接矩陣是0，1矩陣 int j; printf("%c",G->vexs[i]); //訪問頂點(diǎn)Vi visited[i]=TRUE; //置已訪問標(biāo)志 for(j=0;jn;j++) //依次搜索Vi的鄰接點(diǎn) if(G->edges[i][j]==1 && ! visited[j]) DFSM(G,j); //〔Vi，Vj〕∈E，且Vj未訪問過，故V

41、j為新出發(fā)點(diǎn) } void DFS(MGraph *G) { int i; for(i=0;in;i++) visited[i]=FALSE; //標(biāo)志向量初始化 for(i=0;in;i++) if(!visited[i]) //Vi未訪問過 DFSM(G,i); //以Vi為源點(diǎn)開始DFS搜索 } //===========BFS：廣度優(yōu)先遍歷======= void BFS(MGraph *G,int k) {

42、 //以Vk為源點(diǎn)對用鄰接矩陣表示的圖G進(jìn)展廣度優(yōu)先搜索 int i,j,f=0,r=0; int cq[MaxVertexNum]; //定義隊(duì)列 for(i=0;in;i++) visited[i]=FALSE; //標(biāo)志向量初始化 for(i=0;in;i++) cq[i]=-1; //隊(duì)列初始化 printf("%c",G->vexs[k]); //訪問源點(diǎn)Vk visited[k]=TRUE; cq[r]=k;

43、 //Vk已訪問，將其入隊(duì)。注意，實(shí)際上是將其序號入隊(duì) while(cq[f]!=-1) { //隊(duì)非空如此執(zhí)行 i=cq[f]; f=f+1; //Vf出隊(duì) for(j=0;jn;j++) //依次Vi的鄰接點(diǎn)Vj if(G->edges[i][j]==1 && !visited[j]) { //Vj未訪問 printf("%c",G->vexs[j]); //訪問Vj visited[j]=TRU

44、E; r=r+1; cq[r]=j; //訪問過Vj入隊(duì) } } } //==========main===== void main() { int i; MGraph *G; G=(MGraph *)malloc(sizeof(MGraph)); //為圖G申請存空間 CreatMGraph(G); //建立鄰接矩陣 printf("Print Graph DFS: "); DFS(G); //深度優(yōu)先遍歷

45、 printf("\n"); printf("Print Graph BFS: "); BFS(G,3); //以序號為3的頂點(diǎn)開始廣度優(yōu)先遍歷 printf("\n"); } 2． 鄰接鏈表作為存儲結(jié)構(gòu) #include"stdio.h" #include"stdlib.h" #define MaxVertexNum 50 //定義最大頂點(diǎn)數(shù) typedef struct node{ //邊表結(jié)點(diǎn) int adjvex; //鄰接點(diǎn)域 st

46、ruct node *next; //鏈域 }EdgeNode; typedef struct vnode{ //頂點(diǎn)表結(jié)點(diǎn) char vertex; //頂點(diǎn)域 EdgeNode *firstedge; //邊表頭指針 }VertexNode; typedef VertexNode AdjList[MaxVertexNum]; //AdjList是鄰接表類型 typedef struct { AdjList adjlist; //鄰接表 int n,e;

47、 //圖中當(dāng)前頂點(diǎn)數(shù)和邊數(shù) } ALGraph; //圖類型 //=========建立圖的鄰接表======= void CreatALGraph(ALGraph *G) { int i,j,k; char a; EdgeNode *s; //定義邊表結(jié)點(diǎn) printf("Input VertexNum(n) and EdgesNum(e): "); scanf("%d,%d",&G->n,&G->e); //讀入頂點(diǎn)數(shù)和邊數(shù) scanf("

48、%c",&a); printf("Input Vertex string:"); for(i=0;in;i++) //建立邊表 { scanf("%c",&a); G->adjlist[i].vertex=a; //讀入頂點(diǎn)信息 G->adjlist[i].firstedge=NULL; //邊表置為空表 } printf("Input edges,Creat Adjacency List\n"); for(k=0;ke;k++) { //建立邊表

49、 scanf("%d%d",&i,&j); //讀入邊〔Vi，Vj〕的頂點(diǎn)對序號 s=(EdgeNode *)malloc(sizeof(EdgeNode)); //生成邊表結(jié)點(diǎn) s->adjvex=j; //鄰接點(diǎn)序號為j s->next=G->adjlist[i].firstedge; G->adjlist[i].firstedge=s; //將新結(jié)點(diǎn)*S插入頂點(diǎn)Vi的邊表頭部 s=(EdgeNode *)malloc(sizeof(EdgeNode)); s->adjvex=i;

50、 //鄰接點(diǎn)序號為i s->next=G->adjlist[j].firstedge; G->adjlist[j].firstedge=s; //將新結(jié)點(diǎn)*S插入頂點(diǎn)Vj的邊表頭部 } } //=========定義標(biāo)志向量，為全局變量======= typedef enum{FALSE,TRUE} Boolean; Boolean visited[MaxVertexNum]; //========DFS：深度優(yōu)先遍歷的遞歸算法====== void DFSM(ALGraph *G,int i) {

51、 //以Vi為出發(fā)點(diǎn)對鄰接鏈表表示的圖G進(jìn)展DFS搜索 EdgeNode *p; printf("%c",G->adjlist[i].vertex); //訪問頂點(diǎn)Vi visited[i]=TRUE; //標(biāo)記Vi已訪問 p=G->adjlist[i].firstedge; //取Vi邊表的頭指針 while(p) { //依次搜索Vi的鄰接點(diǎn)Vj，這里j=p->adjvex if(! visited[p->adjvex])

52、 //假設(shè)Vj尚未被訪問 DFSM(G,p->adjvex); //如此以Vj為出發(fā)點(diǎn)向縱深搜索 p=p->next; //找Vi的下一個(gè)鄰接點(diǎn) } } void DFS(ALGraph *G) { int i; for(i=0;in;i++) visited[i]=FALSE; //標(biāo)志向量初始化 for(i=0;in;i++) if(!visited[i]) //Vi未訪問過 DFSM(G,i);

53、 //以Vi為源點(diǎn)開始DFS搜索}//==========BFS：廣度優(yōu)先遍歷========= void BFS(ALGraph *G,int k){ //以Vk為源點(diǎn)對用鄰接鏈表表示的圖G進(jìn)展廣度優(yōu)先搜索 int i,f=0,r=0; EdgeNode *p; int cq[MaxVertexNum]; //定義FIFO隊(duì)列 for(i=0;in;i++) visited[i]=FALSE; //標(biāo)志向量初始化 for(i=0;i<=G

54、->n;i++) cq[i]=-1; //初始化標(biāo)志向量 printf("%c",G->adjlist[k].vertex); //訪問源點(diǎn)Vk visited[k]=TRUE; cq[r]=k; //Vk已訪問，將其入隊(duì)。注意，實(shí)際上是將其序號入隊(duì) while(cq[f]!=-1) { 隊(duì)列非空如此執(zhí)行 i=cq[f]; f=f+1; //Vi出隊(duì) p=G->adjlist[i].firstedge; //取Vi的邊表頭指針 whi

55、le(p) { //依次搜索Vi的鄰接點(diǎn)Vj〔令p->adjvex=j〕 if(!visited[p->adjvex]) { //假設(shè)Vj未訪問過 printf("%c",G->adjlist[p->adjvex].vertex); //訪問Vj visited[p->adjvex]=TRUE; r=r+1; cq[r]=p->adjvex; //訪問過的Vj入隊(duì) } p=p->next; //找Vi的下一個(gè)鄰接點(diǎn) } }//endwhi

56、le } //==========主函數(shù)=========== void main() { int i; ALGraph *G; G=(ALGraph *)malloc(sizeof(ALGraph)); CreatALGraph(G); printf("Print Graph DFS: "); DFS(G); printf("\n"); printf("Print Graph BFS: "); BFS(G,3); printf("\n"); } 實(shí)驗(yàn)結(jié)果： 1. 鄰接

57、矩陣作為存儲結(jié)構(gòu) 執(zhí)行順序： V6 V4 V5 V7 V2 V3 V1 V0 Vo Input VertexNum(n) and EdgesNum(e): 8，9 Input Vertex string: 01234567 Input edges,Creat Adjacency Matrix 0 1 0 2 1 3 1 4 2 5 2 6 3 7 4 7 5 6 Print Graph DFS: 01374256 Print Graph BFS: 31704256 2. 鄰接鏈表作為存儲結(jié)構(gòu) 執(zhí)行順序：

58、Input VertexNum(n) and EdgesNum(e): 8，9 Input Vertex string: 01234567 V6 V4 V5 V7 V2 V3 V1 V0 Vo Input edges,Creat Adjacency List 0 1 0 2 1 3 1 4 2 5 2 6 3 7 4 7 5 6 Print Graph DFS: 02651473 Print Graph BFS: 37140265 心得體會： 這次實(shí)驗(yàn)較以前的實(shí)驗(yàn)難度加大，必須先理解深度優(yōu)先和廣度優(yōu)先兩種遍歷思

59、路，和數(shù)據(jù)結(jié)構(gòu)中隊(duì)列的根本操作，才能看懂理解代碼。同時(shí)圖這種數(shù)據(jù)結(jié)構(gòu)對抽象的能力要求非常高，代碼不容易看懂，排錯(cuò)也比擬麻煩，應(yīng)該多加練習(xí)，才能掌握。 實(shí)驗(yàn)4 實(shí)驗(yàn)題目：排序 實(shí)驗(yàn)?zāi)康模? 掌握各種排序方法的根本思想、排序過程、算法實(shí)現(xiàn)，能進(jìn)展時(shí)間和空間性能的分析，根據(jù)實(shí)際問題的特點(diǎn)和要求選擇適宜的排序方法。 實(shí)驗(yàn)要求： 實(shí)現(xiàn)直接排序、冒泡、直接選擇、快速、堆、歸并排序算法。比擬各種算法的運(yùn)行速度。 實(shí)驗(yàn)主要步驟： 實(shí)驗(yàn)代碼 #include"stdio.h" #include"stdlib.h" #define Max 100 //假

60、設(shè)文件長度 typedef struct{ //定義記錄類型 int key; //關(guān)鍵字項(xiàng) }RecType; typedef RecType SeqList[Max+1]; //SeqList為順序表，表中第0個(gè)元素作為哨兵 int n; //順序表實(shí)際的長度 //==========直接插入排序法====== void InsertSort(SeqList R) { //對順序表R中的記錄R[1‥n]按遞增序進(jìn)展插入排序 int i,j; for(i=2;

61、i<=n;i++) //依次插入R[2]，……，R[n] if(R[i].key

62、j].key 是終止 R[j+1]=R[0]; //R[i]插入到正確的位置上 }//endif } //==========冒泡排序======= typedef enum {FALSE,TRUE} Boolean; //FALSE為0，TRUE為1 void BubbleSort(SeqList R) { //自下向上掃描對R做冒泡排序 int i,j; Boolean exchange; //交換標(biāo)志 for(i=1;i

63、ange=FALSE; //本趟排序開始前，交換標(biāo)志應(yīng)為假 for(j=n-1;j>=i;j--) //對當(dāng)前無序區(qū)R[i‥n] 自下向上掃描 if(R[j+1].key

64、 return; }//endfor〔為循環(huán)〕 } //1.========一次劃分函數(shù)===== int Partition(SeqList R,int i,int j) { // 對R[i‥j]做一次劃分，并返回基準(zhǔn)記錄的位置 RecType pivot=R[i]; //用第一個(gè)記錄作為基準(zhǔn) while(i=pivot.key) //基準(zhǔn)記錄pivot相當(dāng)與在位置i上 j--;

65、 //從右向左掃描，查找第一個(gè)關(guān)鍵字小于pivot.key的記錄R[j] if(i pivot.key，如此 R[j--]=R[i]; //交換R[i]和R[j]，交換后j

66、指針減1 } R[i]=pivot; //此時(shí)，i=j，基準(zhǔn)記錄已被最后定位 return i; //返回基準(zhǔn)記錄的位置 } //2.=====快速排序=========== void QuickSort(SeqList R,int low,int high) { //R[low..high]快速排序 int pivotpos; //劃分后基準(zhǔn)記錄的位置 if(low