数据结构C语言版实验报告

1、实验1实验题目：单链表的插入和删除实验目的：了解和掌握线性表的逻辑结构和链式存储结构，掌握单链表的基本算法及相关的时间性能分析。实验要求：建立一个数据域定义为字符串的单链表，在链表中不允许有重复的字符串；根据输入的字符串，先找到相应的结点，后删除之。实验主要步骤：1、 分析、理解给出的示例程序。2、 调试程序，并设计输入数据（如：bat，cat，eat，fat，hat，jat，lat，mat，#），测试程序的如下功能：不允许重复字符串的插入；根据输入的字符串，找到相应的结点并删除。3、 修改程序：（1） 增加插入结点的功能。（2） 将建立链表的方法改为头插入法。程序代码:#include&qu

2、ot;stdio.h"#include"string.h"#include"stdlib.h"#include"ctype.h"typedef struct node /定义结点char data10; /结点的数据域为字符串struct node *next; /结点的指针域listnode;typedef listnode * linklist; / 自定义linklist单链表类型linklist creatlistr1(); /函数，用尾插入法建立带头结点的单链表linklist creatlist(void); /

3、函数，用头插入法建立带头结点的单链表listnode *locatenode(); /函数，按值查找结点void deletelist(); /函数，删除指定值的结点void printlist(); /函数，打印链表中的所有值void deleteall(); /函数，删除所有结点，释放内存listnode * addnode(); /修改程序：增加节点。用头插法，返回头指针/=主函数=void main()char ch10,num5;linklist head;head=creatlist(); /用头插入法建立单链表，返回头指针printlist(head); /遍历链表输出其值pri

4、ntf(" 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); /输入要删除的字符串deletelist(head,ch);printlist(head);printf(" add

5、node ? (y/n):"); /输入"y"或"n"去选择是否增加结点scanf("%s",num);if(strcmp(num,"y")=0 | strcmp(num,"y")=0)head=addnode(head);printlist(head);deleteall(head); /删除所有结点，释放内存/=用尾插入法建立带头结点的单链表=linklist creatlistr1(void) char ch10; linklist head=(linklist)malloc(s

6、izeof(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=locatenode(head,ch); /按值查找结点，返回结点指针if(pp=null) /没有

7、重复的字符串，插入到链表中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; /返回头指针/=用头插入法建立带头结点的单链表=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; /=按值查找结点，找到则返回该结点的位置，否则返回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; /扫描下一个结点 return p; /若p=null则查找失败，否则p指向找到的值为key的结点/=修改程序：

10、增加节点=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=(listnode *)malloc(sizeof(listnode);strcpy(s->data

11、,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 error");exit(0); while(q->next!=p) /p为要删除的结点

12、，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 deleteall(linklist head) listnode *p=head,*r; while(p-&

13、gt;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: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,请按任意键继续. . .示意图：latjathatfateatcatbatmatnullheadlatjathatfateatcatbatmatheadlatjatfateatputcatbatmatheadnullnull心得体会：本次实验使我们对链表的实质了解更加明确了，对链表的一些基本操作也更加熟练了。另外实验指导书上给出的代码是有一些问题的，这使我们认识到实验过程中不能想当然的直接编译执行，应当在阅读并完全理解代码的基础上再执行，这才是实验的意义所在。实验2实验题目：二叉树操作设计和实现实验目的：掌握二叉树的定义、性质及存

16、储方式，各种遍历算法。实验要求：采用二叉树链表作为存储结构，完成二叉树的建立，先序、中序和后序以及按层次遍历的操作，求所有叶子及结点总数的操作。实验主要步骤：1、 分析、理解程序。2、 调试程序，设计一棵二叉树，输入完全二叉树的先序序列，用#代表虚结点（空指针），如abd#ce#f#，建立二叉树，求出先序、中序和后序以及按层次遍历序列，求所有叶子及结点总数。实验代码#include"stdio.h"#include"stdlib.h"#include"string.h"#define max 20 /结点的最大个数typedef st

17、ruct node char data; struct node *lchild,*rchild;bintnode; /自定义二叉树的结点类型typedef bintnode *bintree; /定义二叉树的指针int nodenum,leaf; /nodenum为结点数，leaf为叶子数/=基于先序遍历算法创建二叉树=/=要求输入先序序列，其中加入虚结点"#"以示空指针的位置=bintree creatbintree(void) bintree t; char ch; if(ch=getchar()='#')return(null); /读入#，返回空指

18、针 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); /先序遍历左子树preorder(t->rchild); /先序遍历右子树 /=lnr

19、中序遍历= 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); /后序遍历右子树printf("%c",t->data); /访问结点 /=采用后序遍历求二叉

20、树的深度、结点数及叶子数的递归算法=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; /求结点数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; /定义结点的指针数组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->lchild; /左子树入队if(p->rchild!=null) rear=(r

22、ear+1)%nodenum; cqrear=p->rchild; /右子树入队 /=数叶子节点个数=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;/=主函数=void main() bintree root;char i; int depth; printf("n");

23、printf("creat bin_tree； input preorder:"); /输入完全二叉树的先序序列， / 用#代表虚结点，如abd#ce#f# root=creatbintree(); /创建二叉树，返回根结点 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，求出该树的结点数。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); /求树的深度及叶子数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); 实验结果：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心得体会：这次实验加深了我对二叉树的印象，尤其是对二叉树的各种遍历操作有了一定的了解。同时认识到，在设计程序时辅以图形化的描述是非常有用处的。实验3实验题目：图的遍历操作实验目的：掌握有向图和无向图的概念；掌握邻接矩阵和邻接链表建立图的存储结构；掌握dfs及bfs对图的遍历操作；了解图结构在人工智能、工程等领域的广泛应用。实验要求：采用邻接矩阵和邻接链表作为图的存储结构，完成有向图和无向图的dfs和bfs操作。实验主要步骤：设计一个有向图和一个无向图，任选一种存储结构，完成有向图和无向图的dfs（深度优先遍历）和b

29、fs（广度优先遍历）的操作。1 邻接矩阵作为存储结构#include"stdio.h"#include"stdlib.h"#define maxvertexnum 100 /定义最大顶点数typedef struct char vexsmaxvertexnum; /顶点表 int edgesmaxvertexnummaxvertexnum; /邻接矩阵，可看作边表 int n,e; /图中的顶点数n和边数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); /输入顶点数和边数 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; /若为无向图，矩阵为对称矩阵；若建立有向图，去掉该条语句 /=定义标志向量，为全局变量=typedef enumfalse

32、,true boolean;boolean visitedmaxvertexnum;/=dfs：深度优先遍历的递归算法=void dfsm(mgraph *g,int i) /以vi为出发点对邻接矩阵表示的图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 && ! visitedj) dfsm(g,j); /（vi，vj）e，且vj

33、未访问过，故vj为新出发点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：广度优先遍历=void bfs(mgraph *g,int k) /以vk为源点对用邻接矩阵表示的图g进行广度优先搜索 int i,j,f=0,r=0; int cqmaxvertexnum; /定义队列 for(i=0;i<g->n;i+)visited

34、i=false; /标志向量初始化 for(i=0;i<g->n;i+)cqi=-1; /队列初始化 printf("%c",g->vexsk); /访问源点vk visitedk=true; cqr=k; /vk已访问，将其入队。注意，实际上是将其序号入队 while(cqf!=-1) /队非空则执行 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申请内存空间 creatmgraph(g); /建立邻接矩阵 printf("print graph dfs: "); dfs(g); /深度优先遍历 printf("n"); printf("print graph bfs: "); bfs(g,3); /以序号为3的顶点

36、开始广度优先遍历 printf("n");2 邻接链表作为存储结构#include"stdio.h"#include"stdlib.h"#define maxvertexnum 50 /定义最大顶点数typedef struct node /边表结点 int adjvex; /邻接点域 struct node *next; /链域edgenode;typedef struct vnode /顶点表结点 char vertex; /顶点域 edgenode *firstedge; /边表头指针vertexnode;typedef ver

37、texnode adjlistmaxvertexnum; /adjlist是邻接表类型typedef struct adjlist adjlist; /邻接表 int n,e; /图中当前顶点数和边数 algraph; /图类型/=建立图的邻接表=void creatalgraph(algraph *g) int i,j,k; char a; edgenode *s; /定义边表结点 printf("input vertexnum(n) and edgesnum(e): "); scanf("%d,%d",&g->n,&g->

38、e); /读入顶点数和边数 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); /生成边表结点s->adjvex=j; /邻接点序号为js->next=g->adjlisti.firstedge;g->adjlisti.firstedge=s; /将新结点*s插入顶点vi的边表头部s=(edgenode *)malloc(sizeof(edgenode); s->adjvex=i; /邻接点序号为is->next=g->adjlistj.

40、firstedge; g->adjlistj.firstedge=s; /将新结点*s插入顶点vj的边表头部 /=定义标志向量，为全局变量=typedef enumfalse,true boolean;boolean visitedmaxvertexnum;/=dfs：深度优先遍历的递归算法=void dfsm(algraph *g,int i) /以vi为出发点对邻接链表表示的图g进行dfs搜索 edgenode *p; printf("%c",g->adjlisti.vertex); /访问顶点vi visitedi=true; /标记vi已访问 p=g-&

41、gt;adjlisti.firstedge; /取vi边表的头指针 while(p) /依次搜索vi的邻接点vj，这里j=p->adjvexif(! visitedp->adjvex) /若vj尚未被访问 dfsm(g,p->adjvex); /则以vj为出发点向纵深搜索p=p->next; /找vi的下一个邻接点 void dfs(algraph *g) int i; for(i=0;i<g->n;i+)visitedi=false; /标志向量初始化 for(i=0;i<g->n;i+)if(!visitedi) /vi未访问过 dfsm(g

42、,i); /以vi为源点开始dfs搜索/=bfs：广度优先遍历=void bfs(algraph *g,int k) /以vk为源点对用邻接链表表示的图g进行广度优先搜索 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",g->adjlistk.vertex); /访问源点vk visitedk=tr

43、ue; cqr=k; /vk已访问，将其入队。注意，实际上是将其序号入队 while(cqf!=-1) 队列非空则执行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/=主函数=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");实验结果：1. 邻接矩阵作为存储结构执行顺序

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. 邻接链表作为存储结构执行顺序：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心得体会：这次实验较以前的实验难度加大，必须先理解深度优先和广度优先两种遍历思路，和数据结构中队列的基本操作，才能看懂理解代码。同时图这种数据结构对抽象的能力要求非常高，代码不容易看懂，排错也比较麻烦，应该多加练习，才能掌握。实验4 实验题目：排序实验目的：掌握各种排序方法的基本思想、排序过程、算法实现，能进行时间和空间性能的分析，根据实