《数据结构》实验报告模板(级计算机科学与技术专业).doc

院 系： 计算机科学学院 专 业： 计算机科学与技术 年 级： 课程名称： 数据结构 学 号： 姓 名： 指导教师： 201年 3 月 1日年级班号学号专业计算机科学与技术姓名实验名称顺序表的相关操作演示实验类型设计型综合型创新型实验目的或要求实验目的：通过上机实践，使学生进一步掌握线性表的逻辑定义、存储结构以及相关应用。 实验要求：自定义存储结构，用c或c+语言编写程序，要求程序模块清晰，菜单界面，有运行结果。四个题目任选一个写入实验报告。实验原理（算法流程） 1.编写头文件。定义数据类型。分别写各个函数如listinsern_sq，listdelete_sq，locateelem等函数。2.编写主函数。在主函数里构造空的线性表，然后利用listinsert函数使用户初始化线性表。然后调用函数操作，操作结果用printlist_sq打印出线性表的内容3.运行程序组内分工（可选） 无实验结果分析及心得体会函数头，是一个函数指针，值向调用的函数，这个调用的函数即为主函数中的上面一段的意思即：在主函数中调用这个locateelem_sq函数，然后其中就是的*compare指向cmp这个函数的入口，所以compare=cmp，locateelem_sq函数中将调用cmp函数。2.使用malloc函数需要包含一个头文件#include成绩评定教师签名： 2014年 月 日备注：源代码附后，源代码要求有注释说明年级班号学号专业计算机科学与技术姓名实验名称括号匹配的检验实验类型设计型综合型创新型实验目的或要求实验目的：通过上机实践，使学生进一步掌握栈这种特殊线性表的逻辑定义、存储结构以及初始化栈、入栈、出栈、栈判空等基本操作的具体实现，使学生能够应用栈的思想解决相关实际问题。 实验要求：自定义存储结构，用c或c+语言编写程序，要求程序应用栈的操作，模块清晰，菜单界面，有运行结果。三个题目任选一个写入实验报告。实验原理（算法流程） 假设表达式中允许包括两种括号：圆括号和方括号，其嵌套的顺序随意，即（【】（）或【（【】【】）】等为正确的格式，【（】）或（【（）等均为不正确格式。在设计程序的时候，借助于栈，将每个元素遍历一遍，根据一定的条件来确定是出栈还是入栈，如果最后栈为空，则括号是匹配的，否则不会匹配。组内分工（可选） 无实验结果分析及心得体会数据结构是一个栈遇到左括号，括号进栈遇到一个右括号，栈顶括号出栈，只到输入结束，检查栈是否空只是最简单的括号匹配坚持成绩评定教师签名： 年 月 日备注：源代码附后，源代码要求有注释说明年级班号学号专业计算机科学与技术姓名实验名称二叉树的基本操作演示 实验类型设计型综合型创新型实验目的或要求实验目的：通过上机实践，使学生进一步掌握二叉树的递归结构定义、存储结构、二叉树的创建、遍历等相关操作及其应用。 实验要求： 用c或c+语言编写程序，要求程序模块清晰，菜单界面，有运行结果。1、自定义结点结构，以二叉链表为存储结构(1) 创建二叉树(2) 输出二叉树的先序、中序和后序递归和非递归遍历下的结点访问次序(3) 输出二叉树所有的叶子节点和叶子节点个数(4) 输出二叉树的按层次遍历序列。(5) 输出二叉树的高度2、任意给定一段电文，为其中出现的字符设计赫夫曼编码，使总电文编码长度最短。两个题目任选一个写入实验报告。实验原理（算法流程） （1）输入字符序列，建立二叉链表。（2）先序、中序、后序遍历二叉树:递归算法。（3）中序遍历二叉树:非递归算法。（最好也能实现先序、后序非递归算法）（4）求二叉树的高度 。（5）求二叉树的叶子个数。（6）借助队列实现二叉树的层次遍历。（7）在主函数中设计一个简单的菜单，分别调试上述算法。 组内分工（可选） 无实验结果分析及心得体会实现了实验的基本要求，对于二叉树也有了更深的了解，其中对于递归的应用真是太奇妙了，花了很长时间才搞出来，递归果然是天才想出来的算法。对于算法的研究真是无止境啊。成绩评定教师签名： 年 月 日备注：源代码附后，源代码要求有注释说明年级班号学号专业计算机科学与技术姓名实验名称图遍历的演示 实验类型设计型综合型创新型实验目的或要求实验目的：通过上机实践，使学生进一步掌握图的逻辑结构、存储结构和图在采用领接表的存储结构下的深度优先搜索和广度优先搜索算法以及图的相关应用。 实验要求： 自定义存储结构，用c或c+语言编写程序，要求程序模块清晰，菜单界面，有运行结果。三个题目任选一个写入实验报告。实验原理（算法流程）首先从图中某个顶点v0出发，访问此顶点，然后依次从v0相邻的顶点出发深度优先遍历，直至图中所有与v0路径相通的顶点都被访问了；若此时尚有顶点未被访问，则从中选一个顶点作为起始点，重复上述过程，直到所有的顶点都被访问。可以看出深度优先遍历是一个递归的过程 广度优先遍历 基本思想：首先，从图的某个顶点v0出发，访问了v0之后，依次访问与v0相邻的未被访问的顶点，然后分别从这些顶点出发，广度优先遍历，直至所有的顶点都被访问完。 组内分工（可选） 无实验结果分析及心得体会图的遍历是这一章所有算法的基础。虽然图的拓扑排序算法在结构上与遍历算法不同，可是拓扑排序的过程仍然或多或少有着遍历的影子。对遍历算法的深刻认识直接决定了图的算法设计的成败。遍历算法分两种，深度遍历和广度遍历。深度遍历是重点。书上算法7.5给出的是一个简单深度优先遍历。所谓简单深度优先遍历，是没有回溯，严格的先根遍历。它的解题能力很有限，大约只能解决判断vi,vj之间是否连通之类的问题。成绩评定教师签名： 年 月 日备注：源代码附后，源代码要求有注释说明程序代码1#include /顺序表的 创建 查找 插入 删除 输出 合并#define listsize 100/最大的顺序表的长度宏定义 有点浪费内存 后期可以改动typedef struct int datalistsize;/数值 int length;/长度seqlist;/结构体的定义及其名称的更改int nmax;/全局变量来存放用户定义的顺序表的长度int list = 0 ;void main()/主程序 void createlist(seqlist *l,int n); void printlist(seqlist *l); void locateelem(seqlist *l); void listinsert(seqlist *l); void listdelete(seqlist *l); void exlist(seqlist *l, int list); void mixlist(seqlist *l0,seqlist *l1); int i=0; seqlist l2; /新建一个结构体来存放必要的数据 l0.length=0; /初始化结构体的长度标示，默认为0 int flag = 0; /定义标志符 /是否创建顺序表的标示符char flagc = n; /标示符用于判断用户的字符输入 int choose; /标示符标示用户的输入if(flag = 0) /默认为没有顺序表达的创建 printf(还未创建顺序表是否创建（n/y）？n); scanf_s( %c ,& flagc); /询问用户是否创建顺序表，并修改创建标示 if(flagc = n| flagc = n)/exit(); /如果用户不创建则退出程序 else flag = 1; createlist(&l0,1); /修改标示符并开始创建顺序表 for(i = 0 ; i 2) printf (超出可建表的范围n); printf(请输入线性表长度:); scanf_s(%d,&nmax); n = nmax; printf(请输入顺序表元素：n); for(i=0,j= 1 ; i datai); l - length = j; /输出顺序表void printlist(seqlist *l) int i; printf(顺序表为：); for( i = 0 ;i length ;i+) printf(%d ,l-datai); /查找元素void locateelem(seqlist *l) int i,*p,n,flag = 0; p = l-data; printf(请输入要查找的元素n:); scanf_s(%d,&n); for( i = 0 ; i length ; i + ) if(n = l-datai) printf(要查找的数的位置为第 %d 个n,i+1); flag = 1; if(flag = 0) printf(未查找到 d% 元素n,n); /插入元素void listinsert(seqlist *l) int in,n,i,j; printf(n请输入要插入的数：); scanf_s(%d,&n); printf(请输入要插入的的位置如（想将插入的数设为第一个请输入1）n); scanf_s(%d,&in); if ( in l-length + 1) printf(输入的数值无效，请重新输入); printf(请输入要插入的的位置如（想将插入的数设为第一个请输入1）n); scanf_s(%d,&in); else + l-length ; /容量增加一个 for( i = 1,j = l- length ; i length + 1 ; i +) / if ( i = in ) /找到插入位置 while(j != in - 1) l-dataj = l-dataj-1; /将元素依次向后移 j-; /直到插入的位置停止 l-datai-1 = n ; printf(输出新表:n); for(i=0;i length;i+) printf(%d ,l-datai); /删除元素void listdelete(seqlist *l)int i,j; printf(n请输入要删除的数的位置：如删除第一个请输入1n); scanf_s(%d,&i); if(i l - length ) printf(输入数值无效删除元素失败!); else for( j = 0 ; j length ; j + ) if(i = j ) l-datai-1 = l-datai; i +; - l - length; for(i = 0 ; i length; i + ) printf(%d ,l-datai); /切换线性表void exlist(seqlist *l ,int n) if(n = 0) list = 1; else list = 0 ;void mixlist(seqlist *l0,seqlist *l1) int length,i; length = l0-length; l0-length += l1 - length; for(i = 0 ;length length ;i+ ,length +) l0-datalength = l1-datai; printlist(l0);2#include #include #include #define maxlen 50 typedef struct stack char ch50; int top; st; /栈的初始化 st *st_init() st *st; if (st=(st *)malloc(sizeof(st) st-top=0; return st; return null; /出栈操作 int st_pop(st *st) if (st-top=0) printf(栈为空n); return 0; st-top-; return st-chst-top; void st_push(st *st,char c) if (st-top=maxlen) printf(栈溢出n); return ; st-chst-top=c; st-top+; /符号检验函数 void check_symbol(st *st,char *a) int i; st_push(st,a0); for (i=1;ichst-top-1=)|(ai=)&st-chst-top-1=()/出栈的条件 st_pop(st); else st_push(st,ai); if(st-top=0) printf(括号是匹配的nn); else printf(括号不匹配nn); void main() while (1) char s50; st *st; st=st_init(); printf(请输入一串括号：n); scanf(%s,s); if(s0=e) return; check_symbol(st,s); 3#include stdio.h#include malloc.h#definemaxsize 20/二叉树结点的结构体表示形式typedef structnodechardata;structnode*left,*right;btree;/栈的结构体表示形式typedef structstackelem btree*amaxsize;inttop;stack;/队列的结构体的表示形式typedef structqueueelem btree*bmaxsize;intfront,rear;queue;/创建二叉树，利用递归的方法btree*create()charch; scanf_s(%c,&ch); getchar();if(ch=#) returnnull; else btree*btree=(btree*)malloc(sizeof(btree);if(null=btree) returnnull; btree-data=ch; btree-left=create(); btree-right=create();returnbtree; /前序遍历，递归的方法voidpreorder(btree*bt)if(null!=bt) printf(%c ,bt-data); preorder(bt-left); preorder(bt-right); /前序遍历的非递归实现/* 思想：利用栈来实现；根结点进栈，之后栈非空，弹出，接着根节点的右结点进栈，之后，左节点进栈；接着，弹出栈顶元素（输出）, 此结点的右结点进栈，之后左节点进栈，弹出栈顶元素（输出）.一直这样下去，直到栈为空。*/voidpreorder2(btree*bt) btree*p; stack st; st.top=-1;if(null=bt) return; else st.top+; st.ast.top=bt;while(st.top!=-1) p=st.ast.top; st.top-; printf(%c ,p-data);if(p-right!=null) st.top+; st.ast.top=p-right; if(p-left!=null) st.top+; st.ast.top=p-left; /中序遍历，递归实现voidinorder(btree*bt)if(null!=bt) inorder(bt-left); printf(%c ,bt-data); inorder(bt-right); /中序遍历，非递归实现/* 思想：利用栈。从根节点开始，循环，只要有左子节点则进栈，直到左子节点为空。接着弹出栈顶输出，判断该结点是否有右子节点， 若有则进栈，若没有继续弹栈。有右子节点的情况，判断该节点是否有左子节点，有则进栈，直到左子节点为空；若该右子节点没有 左子节点，则弹栈；判断弹出的节点，是否有右子节点，若有则进栈，没有继续弹栈；接着又要判断刚进栈的这个节点，是否有左子节点， 有则进栈，没有则继续弹栈。重复下去. btree*p,*q; stack st; st.top=-1;if(null=bt) return; else while(bt!=null) st.top+; st.ast.top=bt; bt=bt-left; while(st.top!=-1) p=st.ast.top; st.top-; printf(%c ,p-data);while( p-right!=null ) st.top+; st.ast.top=p-right; q=p-right;while(q-left!=null) st.top+; st.ast.top=q-left; q=q-left; break; /后序遍历，递归实现voidpostorder(btree*bt)if(bt!=null) postorder(bt-left); postorder(bt-right); printf(%c ,bt-data); /后序遍历，非递归实现/* 算法思想：利用栈来实现。从根结点开始，只要左子节点非空，则进栈，直到左子节点为空为止。取出栈顶元素（只是取，并去弹栈），判断 1:取出的栈顶元素是否有右子节点，或者右子节点是否被访问过，若满足条件（无右子节点，或者右子节点被访问过），则输出该结点， 同时弹栈，并且记录下该访问的节点。 2:取出的栈顶元素，若有右子节点，且未被访问过，则指针继续移动到右子节点，重复一开始是否又左子节点的判断。*/voidpostorder2(btree*bt) stack st; st.top=-1; btree*t;intflag;do while(bt!=null) st.top+; st.ast.top=bt; bt=bt-left; t=null; flag=1;while(st.top!=-1&flag) bt=st.ast.top;if(bt-right=t) /t:表示为null，或者右子节点被访问过了。 printf(%c ,bt-data); st.top-; t=bt; /t记录下刚刚访问的节点else bt=bt-right; flag=0; while(st.top!=-1);/求二叉树的高度，递归实现intheight(btree*bt)intdepth1,depth2;if(null=bt) return0; else depth1=height(bt-left); depth2=height(bt-right);if(depth1depth2) return(depth1+1); else return(depth2+1); /层次遍历二叉树,用队列来实现voidtraversaloflevel(btree*bt) queue q; q.front=q.rear=0;if(bt!=null) printf(%c ,bt-data); q.bq.front=bt; q.rear=q.rear+1;while(q.frontleft!=null) printf(%c ,bt-left-data); q.bq.rear=bt-left; q.rear=q.rear+1; if(bt-right!=null) printf(%c ,bt-right-data); q.bq.rear=bt-right; q.rear=q.rear+1; intmain() btree*btr=create(); printf(前序遍历：递归和非递归实现：n); preorder(btr); printf(n); preorder2(btr); printf(n); printf(中序遍历：递归和非递归实现：n); inorder(btr); printf(n); inorder2(btr); printf(n); printf(后序遍历：递归和非递归实现：n); postorder(btr); printf(n); postorder2(btr); printf(n); printf(二叉树的高度：n);inthgt=height(btr); printf(%d n,hgt); printf(层次遍历二叉树:n); traversaloflevel(btr); printf(n);return0;4#define max 20#include#include typedef struct qnodeint data;struct qnode *next;qnode;typedef struct qnode *front;qnode *rear;queue;/定义一个队列typedef struct arcnode int adjvex;/邻接点顶点的位置struct arcnode *nextarc;/指向下一条弧的指针arcnode;typedef struct vnode/头结点char data;arcnode *firstarc;/邻接链表头指针vnode;typedef structvnode adjlistmax;int v,a;/图的顶点数和边数algraph;int initqueue(queue *s)/构造一个空的对列s-front=s-rear=(qnode*)malloc(sizeof(qnode);if(!s-front)return(0);s-front-next=null;return 1; enqueue (queue *s,int e)/入队列 qnode *p;p=(qnode*)malloc (sizeof(qnode);if (!p)return(0);p-data=e;p-next=null;s-rear-next=p;s-rear=p;return 1;dequeue (queue *q, int *e)/出队列qnode *p;if (q-front=q-rear)return 1;/表示这是空对列p=q-front-next;*e=p-data;/附值q-front-next=p-next;if (q-rear=p)q-rear=q-front;free(p);return 1;int emptyqueue(queue *q)/判断队列是否为空if(q-front=q-rear)return 1;elsereturn 0;void buildalgraph(algraph *s)/构建图int i,m,n;arcnode *p; printf(请输入图的顶点数和边数:);scanf(%d%d,&s-v,&s-a);getchar();printf(请输入%d个顶点的信息:,s-v);/注意输入的时候空格隔开每个顶点之间for(i=0;iv;i+)scanf(%s,&s-adjlisti.data); /*读入顶点信息*/s-adjlisti.firstarc=null; /*边表置为空表*/for(i=0;ia;i+)printf(输入第%d条边(起点序号，终点序号):