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

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

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

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

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

5、intf(" Delete node (y/n):"); //輸入"y"或"n"去選擇是否刪除結(jié)點 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é)點 scanf("%s",nu

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

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

8、 //沒有重復的字符串，插入到鏈表中 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é)點的單鏈表=========== 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é)點，找到如此返回該結(jié)點的位置，否如此返回NULL========== ListNode *LocateNode(LinkList head, char *key) { ListNode *p=head->next; //從開始結(jié)點比擬 while(p!=NULL && strcmp(p

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

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

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

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

15、eAll(LinkList head) { ListNode *p=head,*r; while(p->next){ r=p->next; free(p); p=r; } free(p); } 實驗結(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 心得體會： 本次實驗使我們對鏈表的實質(zhì)了解更加明確了，對鏈表的一些根本操作也更加熟練了。另外實驗指導書上給出的代碼是有一些問題的，這使我們認識到實驗過程中不能想當然的直接編譯執(zhí)行，應當在閱讀并完全理解代碼的根底上再執(zhí)行，這才是實驗的意義所在。 實驗2 實驗題目：二叉樹操作設(shè)計和實現(xiàn) 實驗目的： 掌握二叉樹的定義、性質(zhì)與存儲方式，各種遍歷算法。 實驗要求： 采

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

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

21、 BinTree T; char ch; if((ch=getchar())=='#') return(NULL); //讀入#，返回空指針 else{ T= (BinTNode *)malloc(sizeof(BinTNode)); //生成結(jié)點 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é)點 Preorder(T->lchild); //先序遍歷左子樹 Preorder(T->rchild); //先序遍歷右子樹 } } //========LNR 中序遍歷=============== void Inorder(BinTree T) { if(T) { Inorder(T->lchild); //中序遍歷左子樹 printf("%c",T-

23、>data); //訪問結(jié)點 Inorder(T->rchild); //中序遍歷右子樹 } } //==========LRN 后序遍歷============ void Postorder(BinTree T) { if(T) { Postorder(T->lchild); //后序遍歷左子樹 Postorder(T->rchild); //后序遍歷右子樹 printf("%c",T->data); //訪問結(jié)點 } } //=====采用后序遍歷求二叉樹的深度、結(jié)點數(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é)點數(shù) if(hl==0&&hr==0) leaf=leaf+1; //假設(shè)左右深度為0，即為葉子。 return(max+1); } else return(0);

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

26、//出隊，輸出結(jié)點的值 if(p->lchild!=NULL){ rear=(rear+1)%NodeNum; cq[rear]=p->lchild; //左子樹入隊 } if(p->rchild!=NULL){ rear=(rear+1)%NodeNum; cq[rear]=p->rchild; //右子樹入隊 } } } //====數(shù)葉子節(jié)點個數(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é)點，如ABD###CE##F## root=CreatBinTree(); //創(chuàng)建二叉樹，返回根結(jié)點 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é)點數(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); } 實驗結(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è)計程序時輔以圖形化的描述是非常有用處的。 實驗3 實驗題目：圖的遍歷操作 實驗目的： 掌握有向圖和無向圖的概念；掌握鄰接矩陣和鄰接鏈表建立圖的存儲結(jié)構(gòu)；掌握DFS與BFS對圖的遍歷操作；了解圖結(jié)構(gòu)在人工智能、工程等領(lǐng)域的廣泛應用。 實驗要求： 采用鄰接矩陣和鄰接鏈表作為圖的存儲結(jié)構(gòu)，完成有向圖和無向圖的DFS和

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

37、int n,e; //圖中的頂點數(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); //輸入頂點數(shù)和邊數(shù) scanf("%c",&a);

38、 printf("Input Vertex string:"); for(i=0;in;i++) { scanf("%c",&a); G->vexs[i]=a; //讀入頂點信息，建立頂點表 } 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〕的頂點序號 G->edges[i][j]=1; G->edges[j][i]=1; //假設(shè)為無向圖，矩陣為對稱矩陣；假設(shè)建立有向圖，去掉該條語句 } } //=========定義標志向量，為全局變量======= typedef enum{FALSE,TRUE} Boolean; Boolean visited[MaxVertexNum]; //========DFS：深度優(yōu)先遍歷的遞歸算法====== voi

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

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

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

43、 //Vk已訪問，將其入隊。注意，實際上是將其序號入隊 while(cq[f]!=-1) { //隊非空如此執(zhí)行 i=cq[f]; f=f+1; //Vf出隊 for(j=0;jn;j++) //依次Vi的鄰接點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入隊 } } } //==========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的頂點開始廣度優(yōu)先遍歷 printf("\n"); } 2． 鄰接鏈表作為存儲結(jié)構(gòu) #include"stdio.h" #include"stdlib.h" #define MaxVertexNum 50 //定義最大頂點數(shù) typedef struct node{ //邊表結(jié)點 int adjvex; //鄰接點域 st

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

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

48、%c",&a); printf("Input Vertex string:"); for(i=0;in;i++) //建立邊表 { scanf("%c",&a); G->adjlist[i].vertex=a; //讀入頂點信息 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〕的頂點對序號 s=(EdgeNode *)malloc(sizeof(EdgeNode)); //生成邊表結(jié)點 s->adjvex=j; //鄰接點序號為j s->next=G->adjlist[i].firstedge; G->adjlist[i].firstedge=s; //將新結(jié)點*S插入頂點Vi的邊表頭部 s=(EdgeNode *)malloc(sizeof(EdgeNode)); s->adjvex=i;

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

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

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

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

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

55、le(p) { //依次搜索Vi的鄰接點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入隊 } p=p->next; //找Vi的下一個鄰接點 } }//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"); } 實驗結(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 心得體會： 這次實驗較以前的實驗難度加大，必須先理解深度優(yōu)先和廣度優(yōu)先兩種遍歷思

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

60、設(shè)文件長度 typedef struct{ //定義記錄類型 int key; //關(guān)鍵字項 }RecType; typedef RecType SeqList[Max+1]; //SeqList為順序表，表中第0個元素作為哨兵 int n; //順序表實際的長度 //==========直接插入排序法====== void InsertSort(SeqList R) { //對順序表R中的記錄R[1‥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; //交換標志 for(i=1;i

63、ange=FALSE; //本趟排序開始前，交換標志應為假 for(j=n-1;j>=i;j--) //對當前無序區(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]做一次劃分，并返回基準記錄的位置 RecType pivot=R[i]; //用第一個記錄作為基準 while(i=pivot.key) //基準記錄pivot相當與在位置i上 j--;

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

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