數(shù)據(jù)結(jié)構(gòu)C語言版實驗報告

1、實驗1實驗題目：單鏈表的插入和刪除實驗?zāi)康模毫私夂驼莆站€性表的邏輯結(jié)構(gòu)和鏈?zhǔn)酱鎯Y(jié)構(gòu)，掌握單鏈表的基本算法及相關(guān)的時間性能分析。實驗要求：建立一個數(shù)據(jù)域定義為字符串的單鏈表，在鏈表中不允許有重復(fù)的字符串；根據(jù)輸入的字符串，先找到相應(yīng)的結(jié)點，后刪除之。實驗主要步驟：1、 分析、理解給出的示例程序。2、 調(diào)試程序，并設(shè)計輸入數(shù)據(jù)（如：bat，cat，eat，fat，hat，jat，lat，mat，#），測試程序的如下功能：不允許重復(fù)字符串的插入；根據(jù)輸入的字符串，找到相應(yīng)的結(jié)點并刪除。3、 修改程序：（1） 增加插入結(jié)點的功能。（2） 將建立鏈表的方法改為頭插入法。程序代碼:#include&qu

2、ot;stdio.h"#include"string.h"#include"stdlib.h"#include"ctype.h"typedef struct node /定義結(jié)點char data10; /結(jié)點的數(shù)據(jù)域為字符串struct node *next; /結(jié)點的指針域listnode;typedef listnode * linklist; / 自定義linklist單鏈表類型linklist creatlistr1(); /函數(shù)，用尾插入法建立帶頭結(jié)點的單鏈表linklist creatlist(void); /

3、函數(shù)，用頭插入法建立帶頭結(jié)點的單鏈表listnode *locatenode(); /函數(shù)，按值查找結(jié)點void deletelist(); /函數(shù)，刪除指定值的結(jié)點void printlist(); /函數(shù)，打印鏈表中的所有值void deleteall(); /函數(shù)，刪除所有結(jié)點，釋放內(nèi)存listnode * addnode(); /修改程序：增加節(jié)點。用頭插法，返回頭指針/=主函數(shù)=void main()char ch10,num5;linklist head;head=creatlist(); /用頭插入法建立單鏈表，返回頭指針printlist(head); /遍歷鏈表輸出其值pri

4、ntf(" 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

5、node ? (y/n):"); /輸入"y"或"n"去選擇是否增加結(jié)點scanf("%s",num);if(strcmp(num,"y")=0 | strcmp(num,"y")=0)head=addnode(head);printlist(head);deleteall(head); /刪除所有結(jié)點，釋放內(nèi)存/=用尾插入法建立帶頭結(jié)點的單鏈表=linklist creatlistr1(void) char ch10; linklist head=(linklist)malloc(s

6、izeof(listnode); /生成頭結(jié)點 listnode *s,*r,*pp; r=head; r->next=null; printf("input # to end "); /輸入"#"代表輸入結(jié)束 printf("nplease input node_data:"); scanf("%s",ch); /輸入各結(jié)點的字符串 while(strcmp(ch,"#")!=0) pp=locatenode(head,ch); /按值查找結(jié)點，返回結(jié)點指針if(pp=null) /沒有

7、重復(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é)點的單鏈表=linklist creatlist(void)char ch100;linklist head,p;

8、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,ch);p=(linklist)malloc(sizeof(listnode); p->n

9、ext=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->data,key)!=0) /直到p為null或p->data為key止p=p->next; /掃描下一個結(jié)點 return p; /若p=null則查找失敗，否則p指向找到的值為key的結(jié)點/=修改程序：

10、增加節(jié)點=listnode * addnode(linklist head) char ch10;listnode *s,*pp; printf("nplease input a new node_data:"); scanf("%s",ch); /輸入各結(jié)點的字符串pp=locatenode(head,ch); /按值查找結(jié)點，返回結(jié)點指針printf("ok2n");if(pp=null) /沒有重復(fù)的字符串，插入到鏈表中s=(listnode *)malloc(sizeof(listnode);strcpy(s->data

11、,ch);printf("ok3n");s->next=head->next;head->next=s;return head;/=刪除帶頭結(jié)點的單鏈表中的指定結(jié)點=void deletelist(linklist head,char *key) listnode *p,*r,*q=head; p=locatenode(head,key); /按key值查找結(jié)點的 if(p=null ) /若沒有找到結(jié)點，退出printf("position error");exit(0); while(q->next!=p) /p為要刪除的結(jié)點

12、，q為p的前結(jié)點q=q->next; r=q->next; 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 deleteall(linklist head) listnode *p=head,*r; while(p-&

13、gt;next)r=p->next;free(p);p=r;free(p);實驗結(jié)果：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:hatinput # to end please input node_data:jatinput #

14、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):yplease input insert_data:putposition :5mat, la

15、t, jat, fat, eat, put, cat, bat,請按任意鍵繼續(xù). . .示意圖：latjathatfateatcatbatmatnullheadlatjathatfateatcatbatmatheadlatjatfateatputcatbatmatheadnullnull心得體會：本次實驗使我們對鏈表的實質(zhì)了解更加明確了，對鏈表的一些基本操作也更加熟練了。另外實驗指導(dǎo)書上給出的代碼是有一些問題的，這使我們認(rèn)識到實驗過程中不能想當(dāng)然的直接編譯執(zhí)行，應(yīng)當(dāng)在閱讀并完全理解代碼的基礎(chǔ)上再執(zhí)行，這才是實驗的意義所在。實驗2實驗題目：二叉樹操作設(shè)計和實現(xiàn)實驗?zāi)康模赫莆斩鏄涞亩x、性質(zhì)及存

16、儲方式，各種遍歷算法。實驗要求：采用二叉樹鏈表作為存儲結(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 st

17、ruct node 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) bintree t; char ch; if(ch=getchar()='#')return(null); /讀入#，返回空指

18、針 else t= (bintnode *)malloc(sizeof(bintnode); /生成結(jié)點t->data=ch;t->lchild=creatbintree(); /構(gòu)造左子樹t->rchild=creatbintree(); /構(gòu)造右子樹return(t); /=nlr 先序遍歷=void preorder(bintree t) if(t) printf("%c",t->data); /訪問結(jié)點preorder(t->lchild); /先序遍歷左子樹preorder(t->rchild); /先序遍歷右子樹 /=lnr

19、中序遍歷= void inorder(bintree t) if(t) inorder(t->lchild); /中序遍歷左子樹printf("%c",t->data); /訪問結(jié)點inorder(t->rchild); /中序遍歷右子樹 /=lrn 后序遍歷=void postorder(bintree t) if(t) postorder(t->lchild); /后序遍歷左子樹postorder(t->rchild); /后序遍歷右子樹printf("%c",t->data); /訪問結(jié)點 /=采用后序遍歷求二叉

20、樹的深度、結(jié)點數(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; /求結(jié)點數(shù)if(hl=0&&hr=0) leaf=leaf+1; /若左右深度為0，即為葉子。return(max+1); else return(0);/=利用"先進先出"（fifo）隊列，按層次遍歷二叉

21、樹=void levelorder(bintree t) int front=0,rear=1; bintnode *cqmax,*p; /定義結(jié)點的指針數(shù)組cq cq1=t; /根入隊 while(front!=rear) front=(front+1)%nodenum;p=cqfront; /出隊printf("%c",p->data); /出隊，輸出結(jié)點的值 if(p->lchild!=null) rear=(rear+1)%nodenum; cqrear=p->lchild; /左子樹入隊if(p->rchild!=null) rear=(r

22、ear+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() bintree root;char i; int depth; printf("n");

23、printf("creat bin_tree； input preorder:"); /輸入完全二叉樹的先序序列， / 用#代表虛結(jié)點，如abd#ce#f# root=creatbintree(); /創(chuàng)建二叉樹，返回根結(jié)點 do /從菜單中選擇遍歷方式，輸入序號。printf("t* select *n");printf("t1: preorder traversaln"); printf("t2: iorder traversaln");printf("t3: postorder traversaln

24、");printf("t4: posttreedepth,node number,leaf numbern");printf("t5: level depthn"); /按層次遍歷之前，先選擇4，求出該樹的結(jié)點數(shù)。printf("t0: exitn");printf("t*n");fflush(stdin);scanf("%c",&i); /輸入菜單序號（0-5）switch (i-'0')case 1: printf("print bin_tree

25、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ù)printf("bintree depth=%d bintree node number=%d

26、",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# * select * 1: preorder traversal 2:

27、 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 bintree leaf number=3 5 leveprint bin_tree: abcdef

28、0 press any key to continue 二叉樹示意圖abfedc心得體會：這次實驗加深了我對二叉樹的印象，尤其是對二叉樹的各種遍歷操作有了一定的了解。同時認(rèn)識到，在設(shè)計程序時輔以圖形化的描述是非常有用處的。實驗3實驗題目：圖的遍歷操作實驗?zāi)康模赫莆沼邢驁D和無向圖的概念；掌握鄰接矩陣和鄰接鏈表建立圖的存儲結(jié)構(gòu)；掌握dfs及bfs對圖的遍歷操作；了解圖結(jié)構(gòu)在人工智能、工程等領(lǐng)域的廣泛應(yīng)用。實驗要求：采用鄰接矩陣和鄰接鏈表作為圖的存儲結(jié)構(gòu)，完成有向圖和無向圖的dfs和bfs操作。實驗主要步驟：設(shè)計一個有向圖和一個無向圖，任選一種存儲結(jié)構(gòu)，完成有向圖和無向圖的dfs（深度優(yōu)先遍歷）和b

29、fs（廣度優(yōu)先遍歷）的操作。1 鄰接矩陣作為存儲結(jié)構(gòu)#include"stdio.h"#include"stdlib.h"#define maxvertexnum 100 /定義最大頂點數(shù)typedef struct char vexsmaxvertexnum; /頂點表 int edgesmaxvertexnummaxvertexnum; /鄰接矩陣，可看作邊表 int n,e; /圖中的頂點數(shù)n和邊數(shù)emgraph; /用鄰接矩陣表示的圖的類型/=建立鄰接矩陣=void creatmgraph(mgraph *g) int i,j,k; char a

30、; 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->vexsi=a; /讀入頂點信息，建立頂點表 for(i=0;i<g->n;i

31、+)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; /若為無向圖，矩陣為對稱矩陣；若建立有向圖，去掉該條語句 /=定義標(biāo)志向量，為全局變量=typedef enumfalse

32、,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; /置已訪問標(biāo)志 for(j=0;j<g->n;j+) /依次搜索vi的鄰接點if(g->edgesij=1 && ! visitedj) dfsm(g,j); /（vi，vj）e，且vj

33、未訪問過，故vj為新出發(fā)點void dfs(mgraph *g) int i; for(i=0;i<g->n;i+)visitedi=false; /標(biāo)志向量初始化 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 cqmaxvertexnum; /定義隊列 for(i=0;i<g->n;i+)visited

34、i=false; /標(biāo)志向量初始化 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 && !visitedj) /vj未訪問 printf("%c",g

35、->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("print graph bfs: "); bfs(g,3); /以序號為3的頂點

36、開始廣度優(yōu)先遍歷 printf("n");2 鄰接鏈表作為存儲結(jié)構(gòu)#include"stdio.h"#include"stdlib.h"#define maxvertexnum 50 /定義最大頂點數(shù)typedef struct node /邊表結(jié)點 int adjvex; /鄰接點域 struct node *next; /鏈域edgenode;typedef struct vnode /頂點表結(jié)點 char vertex; /頂點域 edgenode *firstedge; /邊表頭指針vertexnode;typedef ver

37、texnode adjlistmaxvertexnum; /adjlist是鄰接表類型typedef struct adjlist adjlist; /鄰接表 int n,e; /圖中當(dāng)前頂點數(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->

38、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 adjacency listn"); for(k=0;k<g->e;k+) /建立

39、邊表 scanf("%d%d",&i,&j); /讀入邊（vi，vj）的頂點對序號s=(edgenode *)malloc(sizeof(edgenode); /生成邊表結(jié)點s->adjvex=j; /鄰接點序號為js->next=g->adjlisti.firstedge;g->adjlisti.firstedge=s; /將新結(jié)點*s插入頂點vi的邊表頭部s=(edgenode *)malloc(sizeof(edgenode); s->adjvex=i; /鄰接點序號為is->next=g->adjlistj.

40、firstedge; g->adjlistj.firstedge=s; /將新結(jié)點*s插入頂點vj的邊表頭部 /=定義標(biāo)志向量，為全局變量=typedef enumfalse,true boolean;boolean visitedmaxvertexnum;/=dfs：深度優(yōu)先遍歷的遞歸算法=void dfsm(algraph *g,int i) /以vi為出發(fā)點對鄰接鏈表表示的圖g進行dfs搜索 edgenode *p; printf("%c",g->adjlisti.vertex); /訪問頂點vi visitedi=true; /標(biāo)記vi已訪問 p=g-&

41、gt;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; /標(biāo)志向量初始化 for(i=0;i<g->n;i+)if(!visitedi) /vi未訪問過 dfsm(g

42、,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; /標(biāo)志向量初始化 for(i=0;i<=g->n;i+)cqi=-1; /初始化標(biāo)志向量 printf("%c",g->adjlistk.vertex); /訪問源點vk visitedk=tr

43、ue; 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); /訪問vjvisitedp->adjvex=true;r=r+1; cqr=p->adjvex;

44、 /訪問過的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,3); printf("n");實驗結(jié)果：1. 鄰接矩陣作為存儲結(jié)構(gòu)執(zhí)行順序

45、：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. 鄰接鏈表作為存儲結(jié)構(gòu)執(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ù)結(jié)構(gòu)中隊列的基本操作，才能看懂理解代碼。同時圖這種數(shù)據(jù)結(jié)構(gòu)對抽象的能力要求非常高，代碼不容易看懂，排錯也比較麻煩，應(yīng)該多加練習(xí)，才能掌握。實驗4 實驗題目：排序?qū)嶒災(zāi)康模赫莆崭鞣N排序方法的基本思想、排序過程、算法實現(xiàn)，能進行時間和空間性能的分析，根據(jù)實