數(shù)據(jù)結構(C語言版)實驗報告

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

2、1） 增加插入結點的功能。（2） 將建立鏈表的方法改為頭插入法。程序代碼:#include"stdio.h"#include"string.h"#include"stdlib.h"#include"ctype.h"typedef struct node /定義結點char data10; /結點的數(shù)據(jù)域為字符串struct node *next; /結點的指針域ListNode;typedef ListNode * LinkList; / 自定義LinkList單鏈表類型LinkList CreatListR1()

3、; /函數(shù)，用尾插入法建立帶頭結點的單鏈表LinkList CreatList(void); /函數(shù)，用頭插入法建立帶頭結點的單鏈表ListNode *LocateNode(); /函數(shù)，按值查找結點void DeleteList(); /函數(shù)，刪除指定值的結點void printlist(); /函數(shù)，打印鏈表中的所有值void DeleteAll(); /函數(shù)，刪除所有結點，釋放內(nèi)存ListNode * AddNode(); /修改程序：增加節(jié)點。用頭插法，返回頭指針/=主函數(shù)=void main()char ch10,num5;LinkList head;head=CreatList()

4、; /用頭插入法建立單鏈表，返回頭指針printlist(head); /遍歷鏈表輸出其值printf(" Delete node (y/n):"); /輸入"y"或"n"去選擇是否刪除結點scanf("%s",num);if(strcmp(num,"y")=0 | strcmp(num,"Y")=0)printf("Please input Delete_data:");scanf("%s",ch); /輸入要刪除的字符串Delete

5、List(head,ch);printlist(head);printf(" Add node ? (y/n):"); /輸入"y"或"n"去選擇是否增加結點scanf("%s",num);if(strcmp(num,"y")=0 | strcmp(num,"Y")=0)head=AddNode(head);printlist(head);DeleteAll(head); /刪除所有結點，釋放內(nèi)存/=用尾插入法建立帶頭結點的單鏈表=LinkList CreatListR1(v

6、oid) char ch10; LinkList head=(LinkList)malloc(sizeof(ListNode); /生成頭結點 ListNode *s,*r,*pp; r=head; r->next=NULL; printf("Input # to end "); /輸入"#"代表輸入結束 printf("nPlease input Node_data:"); scanf("%s",ch); /輸入各結點的字符串 while(strcmp(ch,"#")!=0) pp=Lo

7、cateNode(head,ch); /按值查找結點，返回結點指針if(pp=NULL) /沒有重復的字符串，插入到鏈表中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; /返回頭指針/=用頭插入法建立帶頭結點的單鏈表=Lin

8、kList CreatList(void)char ch100;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->data,

9、ch);p=(LinkList)malloc(sizeof(ListNode); p->next=head;head=p;else break;return head; /=按值查找結點，找到則返回該結點的位置，否則返回NULL=ListNode *LocateNode(LinkList head, char *key) ListNode *p=head->next; /從開始結點比較 while(p!=NULL && strcmp(p->data,key)!=0) /直到p為NULL或p->data為key止p=p->next; /掃描下一個結點

10、 return p; /若p=NULL則查找失敗，否則p指向找到的值為key的結點/=修改程序：增加節(jié)點=ListNode * AddNode(LinkList head) char ch10;ListNode *s,*pp; printf("nPlease input a New Node_data:"); scanf("%s",ch); /輸入各結點的字符串pp=LocateNode(head,ch); /按值查找結點，返回結點指針printf("ok2n");if(pp=NULL) /沒有重復的字符串，插入到鏈表中s=(List

11、Node *)malloc(sizeof(ListNode);strcpy(s->data,ch);printf("ok3n");s->next=head->next;head->next=s;return head;/=刪除帶頭結點的單鏈表中的指定結點=void DeleteList(LinkList head,char *key) ListNode *p,*r,*q=head; p=LocateNode(head,key); /按key值查找結點的 if(p=NULL ) /若沒有找到結點，退出printf("position erro

12、r");exit(0); while(q->next!=p) /p為要刪除的結點，q為p的前結點q=q->next; r=q->next; q->next=r->next; free(r); /釋放結點/=打印鏈表=void printlist(LinkList head) ListNode *p=head->next; /從開始結點打印 while(p)printf("%s, ",p->data);p=p->next; printf("n");/=刪除所有結點，釋放空間=void DeleteA

13、ll(LinkList head) ListNode *p=head,*r; while(p->next)r=p->next;free(p);p=r;free(p);實驗結果：Input # to end Please input Node_data:batInput # to end Please input Node_data:catInput # to end Please input Node_data:eatInput # to end Please input Node_data:fatInput # to end Please input Node_data:hatI

14、nput # to end Please input Node_data:jatInput # to end Please input Node_data:latInput # to end Please input Node_data:matInput # to end Please input Node_data:#mat, lat, jat, hat, fat, eat, cat, bat, Delete node (y/n):yPlease input Delete_data:hatmat, lat, jat, fat, eat, cat, bat, Insert node (y/n)

15、:yPlease input Insert_data:putposition :5mat, lat, jat, fat, eat, put, cat, bat,請按任意鍵繼續(xù). . .示意圖：latjathatfateatcatbatmatNULLheadlatjathatfateatcatbatmatheadlatjatfateatputcatbatmatheadNULLNULL心得體會：本次實驗使我們對鏈表的實質(zhì)了解更加明確了，對鏈表的一些基本操作也更加熟練了。另外實驗指導書上給出的代碼是有一些問題的，這使我們認識到實驗過程中不能想當然的直接編譯執(zhí)行，應當在閱讀并完全理解代碼的基礎上再執(zhí)行

16、，這才是實驗的意義所在。實驗2實驗題目：二叉樹操作設計和實現(xiàn)實驗目的：掌握二叉樹的定義、性質(zhì)及存儲方式，各種遍歷算法。實驗要求：采用二叉樹鏈表作為存儲結構，完成二叉樹的建立，先序、中序和后序以及按層次遍歷的操作，求所有葉子及結點總數(shù)的操作。實驗主要步驟：1、 分析、理解程序。2、 調(diào)試程序，設計一棵二叉樹，輸入完全二叉樹的先序序列，用#代表虛結點（空指針），如ABD#CE#F#，建立二叉樹，求出先序、中序和后序以及按層次遍歷序列，求所有葉子及結點總數(shù)。實驗代碼#include"stdio.h"#include"stdlib.h"#include"

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

18、ch=getchar()='#')return(NULL); /讀入#，返回空指針 else T= (BinTNode *)malloc(sizeof(BinTNode); /生成結點T->data=ch;T->lchild=CreatBinTree(); /構造左子樹T->rchild=CreatBinTree(); /構造右子樹return(T); /=NLR 先序遍歷=void Preorder(BinTree T) if(T) printf("%c",T->data); /訪問結點Preorder(T->lchild);

19、 /先序遍歷左子樹Preorder(T->rchild); /先序遍歷右子樹 /=LNR 中序遍歷= void Inorder(BinTree T) if(T) Inorder(T->lchild); /中序遍歷左子樹printf("%c",T->data); /訪問結點Inorder(T->rchild); /中序遍歷右子樹 /=LRN 后序遍歷=void Postorder(BinTree T) if(T) Postorder(T->lchild); /后序遍歷左子樹Postorder(T->rchild); /后序遍歷右子樹prin

20、tf("%c",T->data); /訪問結點 /=采用后序遍歷求二叉樹的深度、結點數(shù)及葉子數(shù)的遞歸算法=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; /求結點數(shù)if(hl=0&&hr=0) leaf=leaf+1; /若左右深度為0，即為葉子。return(max+1); els

21、e return(0);/=利用"先進先出"（FIFO）隊列，按層次遍歷二叉樹=void Levelorder(BinTree T) int front=0,rear=1; BinTNode *cqMax,*p; /定義結點的指針數(shù)組cq cq1=T; /根入隊 while(front!=rear) front=(front+1)%NodeNum;p=cqfront; /出隊printf("%c",p->data); /出隊，輸出結點的值 if(p->lchild!=NULL) rear=(rear+1)%NodeNum; cqrear=p-

22、>lchild; /左子樹入隊if(p->rchild!=NULL) rear=(rear+1)%NodeNum; cqrear=p->rchild; /右子樹入隊 /=數(shù)葉子節(jié)點個數(shù)=int countleaf(BinTree T)int hl,hr; if(T)hl=countleaf(T->lchild);hr=countleaf(T->rchild);if(hl=0&&hr=0) /若左右深度為0，即為葉子。return(1);else return hl+hr; else return 0;/=主函數(shù)=void main() BinTre

23、e root;char i; int depth; printf("n");printf("Creat Bin_Tree； Input preorder:"); /輸入完全二叉樹的先序序列， / 用#代表虛結點，如ABD#CE#F# root=CreatBinTree(); /創(chuàng)建二叉樹，返回根結點 do /從菜單中選擇遍歷方式，輸入序號。printf("t* select *n");printf("t1: Preorder Traversaln"); printf("t2: Iorder Travers

24、aln");printf("t3: Postorder traversaln");printf("t4: PostTreeDepth,Node number,Leaf numbern");printf("t5: Level Depthn"); /按層次遍歷之前，先選擇4，求出該樹的結點數(shù)。printf("t0: Exitn");printf("t*n");fflush(stdin);scanf("%c",&i); /輸入菜單序號（0-5）switch (i-

25、'0')case 1: printf("Print Bin_tree Preorder: ");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ù)prin

26、tf("BinTree Depth=%d BinTree Node 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); 實驗結果：Creat Bin_Tree； Input preord

27、er:ABD#CE#F# * select * 1: Preorder Traversal 2: Iorder Traversal 3: Postorder traversal 4: PostTreeDepth,Node number,Leaf number 5: Level Depth 0: Exit * 1 Print Bin_tree Preorder: ABDCEF 2 Print Bin_Tree Inorder: DBAECF 3 Print Bin_Tree Postorder: DBEFCA 4 BinTree Depth=3 BinTree Node number=6 Bin

28、Tree Leaf number=3 5 LevePrint Bin_Tree: ABCDEF 0 Press any key to continue 二叉樹示意圖ABFEDC心得體會：這次實驗加深了我對二叉樹的印象，尤其是對二叉樹的各種遍歷操作有了一定的了解。同時認識到，在設計程序時輔以圖形化的描述是非常有用處的。實驗3實驗題目：圖的遍歷操作實驗目的：掌握有向圖和無向圖的概念；掌握鄰接矩陣和鄰接鏈表建立圖的存儲結構；掌握DFS及BFS對圖的遍歷操作；了解圖結構在人工智能、工程等領域的廣泛應用。實驗要求：采用鄰接矩陣和鄰接鏈表作為圖的存儲結構，完成有向圖和無向圖的DFS和BFS操作。實驗主要步

29、驟：設計一個有向圖和一個無向圖，任選一種存儲結構，完成有向圖和無向圖的DFS（深度優(yōu)先遍歷）和BFS（廣度優(yōu)先遍歷）的操作。1 鄰接矩陣作為存儲結構#include"stdio.h"#include"stdlib.h"#define MaxVertexNum 100 /定義最大頂點數(shù)typedef struct char vexsMaxVertexNum; /頂點表 int edgesMaxVertexNumMaxVertexNum; /鄰接矩陣，可看作邊表 int n,e; /圖中的頂點數(shù)n和邊數(shù)eMGraph; /用鄰接矩陣表示的圖的類型/=建立鄰接

30、矩陣=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); printf("Input Vertex string:"); for(i=0;i<G->n;i+) scanf("%c",&a); G-&

31、gt;vexsi=a; /讀入頂點信息，建立頂點表 for(i=0;i<G->n;i+)for(j=0;j<G->n;j+) G->edgesij=0; /初始化鄰接矩陣 printf("Input edges,Creat Adjacency Matrixn"); for(k=0;k<G->e;k+) /讀入e條邊，建立鄰接矩陣 scanf("%d%d",&i,&j); /輸入邊（Vi，Vj）的頂點序號 G->edgesij=1; G->edgesji=1; /若為無向圖，矩陣為對稱矩

32、陣；若建立有向圖，去掉該條語句 /=定義標志向量，為全局變量=typedef enumFALSE,TRUE Boolean;Boolean visitedMaxVertexNum;/=DFS：深度優(yōu)先遍歷的遞歸算法=void DFSM(MGraph *G,int i) /以Vi為出發(fā)點對鄰接矩陣表示的圖G進行DFS搜索，鄰接矩陣是0，1矩陣 int j; printf("%c",G->vexsi); /訪問頂點Vi visitedi=TRUE; /置已訪問標志 for(j=0;j<G->n;j+) /依次搜索Vi的鄰接點if(G->edgesij=1

33、 && ! visitedj) DFSM(G,j); /（Vi，Vj）E，且Vj未訪問過，故Vj為新出發(fā)點void DFS(MGraph *G) int i; for(i=0;i<G->n;i+)visitedi=FALSE; /標志向量初始化 for(i=0;i<G->n;i+)if(!visitedi) /Vi未訪問過 DFSM(G,i); /以Vi為源點開始DFS搜索/=BFS：廣度優(yōu)先遍歷=void BFS(MGraph *G,int k) /以Vk為源點對用鄰接矩陣表示的圖G進行廣度優(yōu)先搜索 int i,j,f=0,r=0; int cqMax

34、VertexNum; /定義隊列 for(i=0;i<G->n;i+)visitedi=FALSE; /標志向量初始化 for(i=0;i<G->n;i+)cqi=-1; /隊列初始化 printf("%c",G->vexsk); /訪問源點Vk visitedk=TRUE; cqr=k; /Vk已訪問，將其入隊。注意，實際上是將其序號入隊 while(cqf!=-1) /隊非空則執(zhí)行 i=cqf; f=f+1; /Vf出隊 for(j=0;j<G->n;j+) /依次Vi的鄰接點Vj if(G->edgesij=1 &

35、;& !visitedj) /Vj未訪問 printf("%c",G->vexsj); /訪問Vj visitedj=TRUE; r=r+1; cqr=j; /訪問過Vj入隊 /=main=void main() int i; MGraph *G; G=(MGraph *)malloc(sizeof(MGraph); /為圖G申請內(nèi)存空間 CreatMGraph(G); /建立鄰接矩陣 printf("Print Graph DFS: "); DFS(G); /深度優(yōu)先遍歷 printf("n"); printf(&qu

36、ot;Print Graph BFS: "); BFS(G,3); /以序號為3的頂點開始廣度優(yōu)先遍歷 printf("n");2 鄰接鏈表作為存儲結構#include"stdio.h"#include"stdlib.h"#define MaxVertexNum 50 /定義最大頂點數(shù)typedef struct node /邊表結點 int adjvex; /鄰接點域 struct node *next; /鏈域EdgeNode;typedef struct vnode /頂點表結點 char vertex; /頂點域 E

37、dgeNode *firstedge; /邊表頭指針VertexNode;typedef VertexNode AdjListMaxVertexNum; /AdjList是鄰接表類型typedef struct AdjList adjlist; /鄰接表 int n,e; /圖中當前頂點數(shù)和邊數(shù) ALGraph; /圖類型/=建立圖的鄰接表=void CreatALGraph(ALGraph *G) int i,j,k; char a; EdgeNode *s; /定義邊表結點 printf("Input VertexNum(n) and EdgesNum(e): ");

38、scanf("%d,%d",&G->n,&G->e); /讀入頂點數(shù)和邊數(shù) scanf("%c",&a); printf("Input Vertex string:"); for(i=0;i<G->n;i+) /建立邊表 scanf("%c",&a);G->adjlisti.vertex=a; /讀入頂點信息G->adjlisti.firstedge=NULL; /邊表置為空表 printf("Input edges,Creat Adja

39、cency Listn"); for(k=0;k<G->e;k+) /建立邊表 scanf("%d%d",&i,&j); /讀入邊（Vi，Vj）的頂點對序號s=(EdgeNode *)malloc(sizeof(EdgeNode); /生成邊表結點s->adjvex=j; /鄰接點序號為js->next=G->adjlisti.firstedge;G->adjlisti.firstedge=s; /將新結點*S插入頂點Vi的邊表頭部s=(EdgeNode *)malloc(sizeof(EdgeNode); s-

40、>adjvex=i; /鄰接點序號為is->next=G->adjlistj.firstedge; G->adjlistj.firstedge=s; /將新結點*S插入頂點Vj的邊表頭部 /=定義標志向量，為全局變量=typedef enumFALSE,TRUE Boolean;Boolean visitedMaxVertexNum;/=DFS：深度優(yōu)先遍歷的遞歸算法=void DFSM(ALGraph *G,int i) /以Vi為出發(fā)點對鄰接鏈表表示的圖G進行DFS搜索 EdgeNode *p; printf("%c",G->adjlist

41、i.vertex); /訪問頂點Vi visitedi=TRUE; /標記Vi已訪問 p=G->adjlisti.firstedge; /取Vi邊表的頭指針 while(p) /依次搜索Vi的鄰接點Vj，這里j=p->adjvexif(! visitedp->adjvex) /若Vj尚未被訪問 DFSM(G,p->adjvex); /則以Vj為出發(fā)點向縱深搜索p=p->next; /找Vi的下一個鄰接點 void DFS(ALGraph *G) int i; for(i=0;i<G->n;i+)visitedi=FALSE; /標志向量初始化 for(

42、i=0;i<G->n;i+)if(!visitedi) /Vi未訪問過 DFSM(G,i); /以Vi為源點開始DFS搜索/=BFS：廣度優(yōu)先遍歷=void BFS(ALGraph *G,int k) /以Vk為源點對用鄰接鏈表表示的圖G進行廣度優(yōu)先搜索 int i,f=0,r=0; EdgeNode *p; int cqMaxVertexNum; /定義FIFO隊列 for(i=0;i<G->n;i+)visitedi=FALSE; /標志向量初始化 for(i=0;i<=G->n;i+)cqi=-1; /初始化標志向量 printf("%c&q

43、uot;,G->adjlistk.vertex); /訪問源點Vk visitedk=TRUE; cqr=k; /Vk已訪問，將其入隊。注意，實際上是將其序號入隊 while(cqf!=-1) 隊列非空則執(zhí)行i=cqf; f=f+1; /Vi出隊p=G->adjlisti.firstedge; /取Vi的邊表頭指針while(p) /依次搜索Vi的鄰接點Vj（令p->adjvex=j） if(!visitedp->adjvex) /若Vj未訪問過printf("%c",G->adjlistp->adjvex.vertex); /訪問Vjv

44、isitedp->adjvex=TRUE;r=r+1; cqr=p->adjvex; /訪問過的Vj入隊 p=p->next; /找Vi的下一個鄰接點 /endwhile/=主函數(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,

45、3); printf("n");實驗結果：1. 鄰接矩陣作為存儲結構執(zhí)行順序：V6V4V5V7V2V3V1V0VoInput VertexNum(n) and EdgesNum(e): 8，9Input Vertex string: 01234567Input edges,Creat Adjacency Matrix0 10 21 31 42 52 63 74 75 6Print Graph DFS: 01374256Print Graph BFS: 317042562. 鄰接鏈表作為存儲結構執(zhí)行順序：Input VertexNum(n) and EdgesNum(e): 8，9Input Vertex string: 01234567V6V4V5V7V2V3V1V0VoInput edges,Creat Adjacency List0 10 21 31 42 52 63 74 75 6Print Graph DFS: 02651473Print Graph BFS: 37140265心得體會：這次實驗較以前的實驗難度加大，必須先理解深度優(yōu)先和廣度優(yōu)先兩種遍歷思路，和數(shù)據(jù)結構中隊列的基本操作，才能看懂理解代碼。同時圖這種數(shù)據(jù)結構對抽象的能力要求非常高，代碼不容易看懂，排錯也比較麻煩，應該多加