数据结构实验报告.doc

_院 系： 计算机科学学院 专 业： 网络工程 年 级： 2012 课程名称： 数据结构 学 号： 2012213773 姓 名： 黄勇 指导教师： 吴立锋 2014年6月日年级2012班号1201组号学号2012213773专业网络工程姓名黄勇实验名称第二章 线性表实验室实验目的或要求 了解线性表的逻辑结构和各种存储表示方法，以及定义在逻辑结构上的各种基本运算及其在某种存储结构上如何实现这些基本运算。在熟悉上述内容的基础上，能够针对具体应用问题的要求和性质，选择合适的存储结构设计出相应的有效算法，解决与线性表相关的实际问题。实验原理（算法流程）1、 实验内容单链表的各种基本操作，包括创建，查找，插入，删除，输出，合并等2、存储结构描述及说明链式存储结构typedef struct node char data; struct node *next; linklist;3、函数说明linklist *rcrect(linklist *head) 尾插法建立单链表void print(linklist *head) 输出函数，输出单链表。linklist location(linklist *head) 按序号查找函数，按序号查找单链表中数据。linklist inset(linklist *head) 插入函数，在单链表中插入数据。linklist delet(linklist *head) 删除函数，删除单链表中的数据。int main() 主函数，程序运行调用各子函数。4、模块之间的调用关系开 始主函数创建单链表查找单链表数据删除数据输出函数插入函数程序清单：#include#include#include typedef struct node /定义节点类型 char data; struct node *next; /因为上面结构体的类型名是struct node linklist是别名 linklist; /一般List顺序表，linklist链表int main() int a; linklist *head; head=(linklist *)malloc(sizeof(linklist); printf(请先建立单链表!n); linklist *rcrect(linklist *head); /调用尾插法 rcrect(head); /*linklist *hcrect(); /或者调用头插法 hcrect();*/ for(;) printf(n您想要对此单链表表做何种操作:n0.退出t1.查找t2.插入t3.删除n); scanf(%d,&a); if(a3) printf(您输入的数字有误，请重新输入!n); if(a=0) /退出 exit(0); if(a=1) linklist location(linklist *head); /调用按序号查找函数 location(head); if(a=2) linklist inset(linklist *head); /调用插入函数 inset(head); if(a=3)/调用删除函数 linklist delet(linklist *head); /调用删除函数 delet(head); return 0;/1.尾插法建立单链表linklist *rcrect(linklist *head) /尾插法 链接到已经建立好的单链表的末尾 linklist *p,*last; char ch; /用于输入字符 last=head; printf(请输入你要存储的字符,以!号结束：n); while(ch!=!) p=(linklist *)malloc(sizeof(linklist); scanf(%c,&ch); p-data=ch; /每次都申请一个节点，数据域存放数据，指针域为空 / printf(%ct,p-data); 可以用来测试存储是否正确 last-next=p; last=p; /上一次的最后一个元素的地址赋给last p-next=NULL; void print(linklist *head); /调用输出函数 print(head); return head;/2.输出函数函数void print(linklist *head) linklist *p; p=head-next; printf(n你存储的数据为:n); while(p!=NULL) printf(%ct,p-data); p=p-next; /3.按序号查找函数linklist location(linklist *head) linklist *p; int i,k=0; p=head; printf(n请输入你要查找链表中第几个元素：n); scanf(%d,&i); while(p&knext; k+; if(ki|!p) printf(输入的序号有误，查找失败！n); exit(0); else printf(第%d个元素的值为：%cn,i,p-data); return *head;/4.插入函数linklist inset(linklist *head) linklist *p,*p1; int i,k=0; char ch; p=head; /不能为head-next printf(请输入你要在链表的第几个位置?t插入什么元素?n); scanf(%d %c,&i,&ch); p1=(linklist *)malloc(sizeof(linklist); /新建一个节点 p1-data=ch; p1-next=NULL; while(p&knext; k+; if(ki-1|!p) printf(输入的序号有误，插入失败！n); exit(0); else p1-next=p-next; p-next=p1; printf(插入后的新数据为:n); /输出插入后的新数据 p=head-next; while(p!=NULL) printf(%ct,p-data); p=p-next; printf(n); return *head;/5.删除函数linklist delet(linklist *head) linklist *p,*p1,*p2; p=head; int i,k=0; printf(请输入你要删除第几个元素:n); scanf(%d,&i); while(p&knext; k+; if(ki-1|!p) printf(输入的序号有误，删除失败！n); exit(0); else p2=p-next; p-next=p2-next; free(p2); printf(删除后的新数据为:n); /输出插入后的新数据 p=head-next; while(p!=NULL) printf(%ct,p-data); p=p-next; printf(n); return *head;精品资料组内分工（可选）无实验结果分析及心得体会实验结果截图：心得体会：通过本次实验对于线性表的运用更熟练了，对于单链表的建立，删除，插入，输出更加熟悉。成绩评定教师签名： 年 月 日年级2012班号1201组号学号2012213773专业网络工程姓名黄勇实验名称第三章 栈和队列实验室实验目的或要求 在掌握栈（队列）特点的基础上，懂得在什么样的情况下能够使用栈（队列）。能熟练使用栈（队列）的一种存储表示，以及在该存储结构上如何实现栈（队列）的基本操作。在熟悉上述内容的基础上，能够针对具体应用问题的特点，选择栈（队列）设计出相应的有效算法，解决与栈（队列）相关的实际问题。实验原理（算法流程）1、实验内容括号匹配的检验。合法的括号包括（）和【】两类，利用栈判断任意输入的一个括号序列是否匹配对出现，若是输出“right“，否则输出”error！“。且提示错误原因。2、 存储结构描述及说明typedef struct int *base;int *top;int stacksize; SqStack;顺序存储结构3、函数说明int InitStack(SqStack *S) 构造函数，构造一个空栈S，该栈预定义大小为STACK_INIT_SIZEint push(SqStack *S,int e) 插入函数，在栈S中插入元素e为新的栈顶元素。int pop(SqStack *S,int *e) 删除函数，若栈不空，则删除S的栈顶元素，用e返回其值，并返回1；否则返回ERRORvoid match(char str) 检测函数，对输入的表达式进行检测，括号是否匹配，匹配则返回配对，否则返回不配对。int main() 主函数。4、模块之间的调用关系主函数构造函数插入函数删除函数检测函数程序清单：#include stdio.h#include conio.h #include stdlib.h #define ERROR -1 #define STACK_INIT_SIZE 100 #define STACKINCREMENT 10 typedef struct int *base;int *top;int stacksize; SqStack; int InitStack(SqStack *S) S-base=(int *)malloc(STACK_INIT_SIZE*sizeof(int); if(!S-base) printf(n磁盘不足.n); getch(); exit(ERROR); S-top=S-base; S-stacksize=STACK_INIT_SIZE; return 1; int push(SqStack *S,int e) if(S-top-S-base=S-stacksize) S-base=(int *)realloc(S-base,(S-stacksize+STACKINCREMENT)*sizeof(int); if(!S-base) printf(n磁盘不足.n); getch(); exit(ERROR); S-top=S-base+S-stacksize; S-stacksize+=STACKINCREMENT; *S-top+=e; return 1; int pop(SqStack *S,int *e) if(S-top=S-base) printf(n栈已满.n); return ERROR; *e=*-S-top; return 1; void match(char str) SqStack S; char *p; int e; InitStack(&S); p=str; while(*p) if(*p=(|*p=|*p=) push(&S,*p); else if(*p=)|*p=|*p=) if(*(S.top-1)+1=*p|*(S.top-1)+2=*p) pop(&S,&e); else printf(n不配对.n); return; p+; if(S.top=S.base) printf(n配对.n); else printf(n不配对！n); int main() char str100; printf(n输入表达式:n); gets(str); match(str); getch(); return 0; 组内分工（可选）无实验结果分析及心得体会实验结果截图：心得体会：通过本次实验，对于栈的运用更加熟练，对于栈的应用有了初步认识，在以后的学习中加深对于栈的认识，对于数据结构有了更深刻的印象。成绩评定教师签名： 年 月 日年级2012班号1201组号学号2012213773专业网络工程姓名黄勇实验名称第六章 树和二叉树实验室实验目的或要求了解二叉树的定义、性质、存储结构等相关知识，在熟悉这些内容的基础上掌握二叉树在某种存储结构下遍历以及相关算法的实现及应用，能根据本章所学到的有关知识设计出有效的算法。实验原理（算法流程）1、实验内容二叉树的相关演示操作。自定义结点结构，以二叉链表为存储结构，完成以下功能：1）以先序递归放松创建一棵二叉树。2）输出二叉树的先序、中序和后序递归或非递归遍历下的结点访问次序；3）输出二叉树所有的叶子节点和叶子节点个数；4）输出二叉树的高度；5）输出二叉树的按层次遍历序列（选作）6）输出二叉树的形状(选作)2、存储结构描述及说明二叉链表存储结构。3、函数说明BinTree CreatBinTree(void) 输入先序序列，其中加入虚结点#以示空指针的位置构造二叉树void Preorder(BinTree T) 先序遍历二叉树函数，以先序递归遍历二叉树，输出先序遍历。void Inorder(BinTree T) 中序遍历二叉树函数，以中序递归遍历二叉树，输出中序遍历。void Postorder(BinTree T) 后序遍历二叉树函数，以后序递归遍历二叉树，输出后序遍历。 int TreeDepth(BinTree T) 求二叉树深度及叶子节点数函数，采用后序遍历求二叉树的深度、结点数及叶子数并输出。后序遍历二叉树void main() 主函数。4、模块之间的调用关系中序遍历函数先序遍历函数主函数求叶子节点及深度函数先序创建二叉树函数程序清单：#includestdio.h#includestring.h#includestdlib.h#define Max 20 /结点的最大个数typedef struct nodechar 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); /读入#，返回空指针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 中序遍历=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); /访问结点/=采用后序遍历求二叉树的深度、结点数及叶子数的递归算法=int TreeDepth(BinTree T)int hl,hr,max;if(T)hl=TreeDepth(T-lchild); /求左深度hr=TreeDepth(T-rchild); /求右深度max=hlhr? hl:hr; /取左右深度的最大值NodeNum=NodeNum+1; /求结点数if(hl=0&hr=0) leaf=leaf+1; /若左右深度为0，即为叶子。return(max+1);else return(0);/=主函数=void main()BinTree root;int i,depth;printf(n);printf(输入二叉树的先序序列创建二叉树，用#代表空结点:); /输入完全二叉树的先序序列，/ 用#代表虚结点，如ABD#CE#F#root=CreatBinTree(); /创建二叉树，返回根结点/do /从菜单中选择遍历方式，输入序号。printf(t* 菜单 *n);printf(t1: 先序遍历n); printf(t2: 中序遍历n);printf(t3: 后序遍历n);printf(t4: 求树的深度及叶子节点数n);printf(t0: 退出n);printf(t*n);do /从菜单中选择遍历方式，输入序号。scanf(%d,&i); /输入菜单序号（0-5） switch (i)case 1: printf(先序遍历为: );Preorder(root); /先序遍历break;case 2: printf(中序遍历为: );Inorder(root); /中序遍历break;case 3: printf(后序遍历为: );Postorder(root); /后序遍历break;case 4: depth=TreeDepth(root); /求树的深度及叶子节点数printf(树的深度=%d 树的叶子节点=%d,depth,NodeNum);break;default: exit(1);printf(n); while(i!=0);（写不完时，可另加附页。）组内分工（可选）无实验结果分析及心得体会实验结果截图：心得体会：通过本次实验对于二叉树的运用更熟练，对于二叉树的先序、中序和后序遍历更加熟悉。成绩评定教师签名： 年 月 日年级2012班号1201组号学号2012213773专业网络工程姓名黄勇实验名称第七章 图实验室 实验目的或要求了解图的基本概念，理解几种常用的存储结构、两种遍历算法以及图的应用算法，在熟悉这些内容的基础上，重点掌握图在邻接表这种存储结构下遍历算法的实现。实验原理（算法流程）1、实验内容图在采用邻接表的存储结构下的基本操作，包括图的创建、图的深度优先搜索和广度优先搜索。 2、存储结构描述及说明邻接表存储结构。typedef struct st_arcint adjvex; int weight; struct st_arc *nextarc;arcnode;typedef structint vertex; struct st_arc *firstarc;vernode;typedef vernode adjlistmaxnode;int queuemaxnode;3、函数说明void dfs(adjlist g,int k,int visited) 深度优先搜索函数，从顶点k出发，深度优先搜索。void bfs(adjlist g,int k,int visited) 广度优先搜索函数，从顶点k出发，广度优先搜索。void trave_bfs(adjlist g,int n) 广度优先搜索函数void trave_dfs(adjlist g,int n) 深度优先搜索函数， 4、模块之间的调用关系主函数创建图广度优先搜索深度优先搜索程序清单：#include iostream#include stdlib.h#include stdio.h#include malloc.h#define maxnode 40#define null 0#define m 20typedef struct st_arcint adjvex; int weight; struct st_arc *nextarc;arcnode;typedef structint vertex; struct st_arc *firstarc;vernode;typedef vernode adjlistmaxnode;int queuemaxnode;void dfs(adjlist g,int k,int visited) /从顶点k出发，深度优先搜索arcnode *p; int w; visitedk=1;printf(%d,gk.vertex); p=gk.firstarc;while(p!=null) w=p-adjvex; if(visitedw=0) dfs(g,w,visited); p=p-nextarc;void bfs(adjlist g,int k,int visited) /从顶点k出发，广度优先搜索int front=0,rear=1,w;arcnode *p;visitedk=1; /访问初始顶点printf(%d,k);queuerear=k; /初始顶点入队列while(front!=rear) /队列不为空 front=(front+1)%m; w=queuefront; /按访问次序依次出队列 p=gw.firstarc; while(p!=null) if(visitedp-adjvex=0) visitedp-adjvex=1; printf(%d,p-adjvex); rear=(rear=1)%m; queuerear=p-adjvex; p=p-nextarc; void trave_bfs(adjlist g,int n)int i,visitedmaxnode; /数组visited标志图中的顶点是否已被访问for(i=1;i=n;i+) visitedi=0;for(i=1;i=n;i+) if(visitedi=0)