云南大学数学与统计学实验教学中心实验报告
课程名称：
数据结构与算法学期：
2011-2012学年第二学期
成绩：
指导教师：xxx学生姓名：xxx学生学号：xxxxx
实验名称：哈希表及其查找实验要求：必做实验学时：4（+2）学时
实验编号：4（及5）实验日期：第6-8周完成日期：2012.5.10
学院：数学与统计学院专业：信息与计算科学年级：2010级
一、实验目的
通过实验掌握散列存储的基本概念，进行哈希问题的处理，同时附带进行字符串的处理的练习。
二、实验内容
为某单位的人名（n=30人）设计一个哈希表，使得平均查找长度<2，要求完成相应的哈希建表和查表。。
三、实验环境
Windows XP
程序设计语言C
四、实验过程
1．实验要求：
1、设人名长度<10个字符，用二维字符数组存储哈希表：char hash[ ][10];
2、要求哈希函数用除留余数法，并用人名的10个字符代码和作为分子；
用（补偿性）线性探测再散列处理冲突。
3、依题意有：平均查找长度=（1+1/(1-α)）/2< 2，∴取α=0.6，
由此哈希表长m=n/α=30/0.6=50; 所以有char hashlist [ 50][10]；
令：除留余数法中的P取47；
（补偿性）线性探测再散列的地址：j=(j+Q)% m中的Q取17。
4、对程序结构的要求：
①要求为哈希建表和哈希查表分别编写和设计相应的函数：
createhash( ... ... ); hashsearch(... ...)；
②再设计一个哈希函数表的输出函数printhash( )，对构造的哈希表进行输出，注
意输出格式要在屏幕好看，先输出序号（1~30），再输出该序号
的人名或null，每行输出10项，共输出5行。
③还应有一个初始化char hashlist [ 50][10]的函数Inithashlist( )，
初始时将50个人名全赋值为null.
5、在主函数中：
调用Inithashlist( )初始化哈希表；
调用createhash( hashlist，30 )构造哈希表；
调用printhash( )输出所建立的哈希表；
接受待查找人名到字符数组name[ ]；
调用hashsearch(hashlist，name )进行查找，若查到显示"found！"并显示
人名在数组中的序号；若未查到显示"no found！"
[测试数据]：健表时输入以下数据：
January February march april may june july august september
October November December
Sunday Monday Tuesday wednesday thurday f riday Saturday
One two three four five six serve eight nine ten data
[实现提示]：
参照杨秀清主编《数据结构》西安电子科技大学出版社P171。
[附加要求]：
1．在哈希查表时考虑插入。当查找失败，且查找时的冲突次数<规定数字(如表长之半)时插入待查找的字符串，并给出“已插入”的显示；
2．在哈希查表时考虑删除。接受待删除人名到字符数组name[ ]；在hash表中找到，并删除之。须注意，删除后不能影响以后的查找。
2．实验设计的（各）流程图：（以下内容请同学认真填写）
3．程序设计的关键代码及解释：（注意对程序代码给出必要的注解，保证可读性）
#include
#define N 50
#define D 30
#define M 10
int m,hi;
/*-------------------------------------------------------------------*/
main(){
void Inithashlist(char a[N][M]);
void createhash(char a[D][M],char h[N][M]);
void hashsearch(char h[N][M],char a[1][M]);
void printhash(char a[][M],int n);
char a[M],
hashlist[N][M],
data[D][M]={
/*----------------------------------------------------------*/
"January", "February", "March", "April", "May",
"June", "July", "August", "September", "October",
"November", "December", "Sunday", "Monday", "Tuesday",
"Wednesday","Thursday", "Friday", "Saturday", "One",
"Two", "Three", "Four", "Five", "Six",
"Serve", "Eight", "Nine", "Ten", "Data"};
/*----------------------------------------------------------*/
Inithashlist(hashlist);
createhash(data,hashlist);
printhash(hashlist,50);
printf("please enter the name:\n");
gets(a);
hashsearch(hashlist,a);
getchar();
getchar();
}
/*-------------------------------------------------------------------*/
void Inithashlist(char a[N][M]){
int i;
for(i=0;i } /*-------------------------------------------------------------------*/ /*-------------------------------------------------------------------*/ int H(int key,int p){ return(key%p); } /*-------------------------------------------------------------------*/ /*-------------------------------------------------------------------*/ void createhash(char a[D][M],char h[N][M]){ int i,j,key=0,hi=0,di[N-1]; for(i=0;i for(i=0;i key=0;j=0; while(a[i][j]) key+=a[i][j++]; hi=H(key,47); if(!strcmp(h[hi-1],"null")) strcpy(h[hi-1],a[i]); else{ m=0; while(strcmp(h[hi-1],"null")) hi=H(hi+17,N); strcpy(h[hi-1],a[i]); } } } /*-------------------------------------------------------------------*/ /*-------------------------------------------------------------------*/ void hashsearch(char h[N][M],char a[M]){ char ch2,ch[M]="yes",ch1[M]="yes"; int i=0,j,key=0,hi=0; for(;a[i]!='\0';) key+=a[i++]; hi=H(key,47); m=0; while(strcmp(h[hi-1],"null")&&strcmp(h[hi-1],a)&&(strcmp(h[hi-1],"Deleted"))) while(strcmp(h[hi-1],"null")) hi=H(hi+17,N); if(!strcmp(h[hi-1],a)){ printf("**************\n"); printf("found! \n"); printf("[%d]%s\n",hi,h[hi-1]); printf("**************\n"); while(strcmp(ch1,"No")&&strcmp(ch1,"no")){ printf("Delete it?(Y/N)\n"); scanf("%s",ch1); ch2=getchar(); if(!strcmp(ch1,"Yes")||!strcmp(ch1,"yes")){ strcpy(h[hi-1],"Deleted"); printf("**************\n"); printf("Deleted! \n"); printf("**************\n"); printhash(h,N); break; } } } else if(m<(N/2)||!(strcmp(h[hi-1],"Deleted"))){ strcpy(h[hi-1],a); printf("**************\n"); printf("已插入！\n"); printf("[%d]%s\n",hi,h[hi-1]); printf("**************\n"); printhash(h,N);} else{ printf("**************\n"); printf("no found!\n"); printf("**************\n");} while(strcmp(ch,"No")&&strcmp(ch,"no")){ printf("continue to search?(Yes/No)\n"); scanf("%s",ch); ch2=getchar(); if(!strcmp(ch,"Yes")||!strcmp(ch,"yes")){ printf("please enter the name:\n"); gets(a); hashsearch(h,a); } } } /*-------------------------------------------------------------------*/ /*-------------------------------------------------------------------*/ void printhash(char a[][M],int n){ int i; for(i=0;i<=8;i++){ system("color 03"); printf("[0%-d] %-11s",i+1,a[i]); if((i+1)%5==0) printf("\n");} for(i=9;i printf("[%-d] %-11s",i+1,a[i]); if((i+1)%5==0) printf("\n");} printf("---------------------"); printf("-----------------END-----------------"); printf("---------------------\n\n"); } /*-------------------------------END---------------------------------*/ 4．实验（程序运行）结果的粘贴：（必需是你的程序运行结果） [01] Three [02] Nine [03] null [04] null [05] Monday [06] Wednesday [07] null [08] One [09] null [10] Six [11] null [12] null [13] May [14] Ten [15] null [16] null [17] Sunday [18] Five [19] Data [20] null [21] March [22] August [23] Thursday [24] null [25] January [26] June [27] Eight [28] null [29] null [30] October [31] November [32] Two [33] February [34] April [35] Serve [36] Four [37] null [38] null [39] December [40] null [41] null [42] September [43] Friday [44] July [45] null [46] Saturday [47] Tuesday [48] null [49] null [50] null --------------------------------------END-------------------------------------- please enter the name: friday ************** 已插入！ [28]friday ************** ......... [26] June [27] Eight [28] friday [29] null [30] October ......... --------------------------------------END-------------------------------------- continue to search?(Yes/No) yes please enter the name: friday ************** found! [28]friday ************** Delete it?(Y/N) yes ************** Deleted! ************** ......... [26] June [27] Eight [28] Deleted [29] null [30] October ......... continue to search?(Yes/No) please enter the name: friday ************** 已插入！ [28]friday ************** ......... [26] June [27] Eight [28] friday [29] null [30] October ......... continue to search?(Yes/No) no 五、实验总结 1．遇到的问题及分析：（请结合你的试验过程认真总结） ①没采用（补偿性）线性探测再散列，导致第二次查找同一元素不能够找到； ②删除元素之后用null代替，导致之后的查找操作失败 2．解决方案（列出遇到的问题和解决办法，列出没有解决的问题）： ①改用（补偿性）线性探测再散列； ②改用Deleted代替被删元素 3．体会和收获。 利用哈希表可以提高一组数据中查找、插入、删除的效率； 六、参考文献 [1] 严蔚敏、吴伟民编著数据结构C语言版清华大学出版社出版（国家级规划教材） [2] 严蔚敏、吴伟民编著数据结构题集C语言版清华大学出版社出版 [3] 汪萍、陆正福等数据结构与算法的问题与实验云南大学出版社 [4] 徐孝凯编著数据结构实用教程C/C++描述清华大学出版社出版 [5] 许卓群、张乃孝等编著数据结构高等教育出版社出版 七、教师评语： 《数据结构课程实验》大纲 一、《数据结构课程实验》的地位与作用 “数据结构”是计算机专业一门重要的专业技术基础课程，是计算机专业的一门核心的关键性课程。本课程较系统地介绍了软件设计中常用的数据结构以及相应的存储结构和实现算法，介绍了常用的多种查找和排序技术，并做了性能分析和比较，内容非常丰富。本课程的学习将为后续课程的学习以及软件设计水平的提高打下良好的基础。 由于以下原因，使得掌握这门课程具有较大的难度： （1）内容丰富，学习量大，给学习带来困难； （2）贯穿全书的动态链表存储结构和递归技术是学习中的重点也是难点； （3）所用到的技术多，而在此之前的各门课程中所介绍的专业性知识又不多，因而加大了学习难度； （4）隐含在各部分的技术和方法丰富，也是学习的重点和难点。 根据《数据结构课程》课程本身的技术特性，设置《数据结构课程实验》实践环节十分重要。通过实验实践内容的训练，突出构造性思维训练的特征, 目的是提高学生组织数据及编写大型程序的能力。实验学时为18。 二、《数据结构课程实验》的目的和要求 不少学生在解答习题尤其是算法设计题时，觉得无从下手，做起来特别费劲。实验中的内容和教科书的内容是密切相关的，解决题目要求所需的各种技术大多可从教科书中找到，只不过其出现的形式呈多样化，因此需要仔细体会，在反复实践的过程中才能掌握。 为了帮助学生更好地学习本课程，理解和掌握算法设计所需的技术，为整个专业学习打好基础，要求运用所学知识，上机解决一些典型问题，通过分析、设计、编码、调试等各环节的训练，使学生深刻理解、牢固掌握所用到的一些技术。数据结构中稍微复杂一些的算法设计中可能同时要用到多种技术和方法，如算法设计的构思方法，动态链表，算法的编码，递归技术，与特定问题相关的技术等，要求重点掌握线性链表、二叉树和树、图结构、数组结构相关算法的设计。在掌握基本算法的基础上，掌握分析、解决实际问题的能力。 三、《数据结构课程实验》内容 课程实验共18学时，要求完成以下六个题目： 实习一约瑟夫环问题（2学时） 数据结构实验报告全集 实验一线性表基本操作和简单程序 1 ．实验目的 （1 ）掌握使用Visual C++ 6.0 上机调试程序的基本方法； （2 ）掌握线性表的基本操作：初始化、插入、删除、取数据元素等运算在顺序存储结构和链表存储结构上的程序设计方法。 2 ．实验要求 （1 ）认真阅读和掌握和本实验相关的教材内容。 （2 ）认真阅读和掌握本章相关内容的程序。 （3 ）上机运行程序。 （4 ）保存和打印出程序的运行结果，并结合程序进行分析。 （5 ）按照你对线性表的操作需要，重新改写主程序并运行，打印出文件清单和运行结果 实验代码： 1）头文件模块 #include iostream.h>// 头文件 #include nodetype *create()// 建立单链表，由用户输入各结点data 域之值， // 以0 表示输入结束 { elemtype d;// 定义数据元素d nodetype *h=NULL,*s,*t;// 定义结点指针 int i=1; cout<<" 建立一个单链表"< 《数据结构》实验报告 班级： 学号： 姓名： 实验四二叉树的基本操作实验环境：Visual C++ 实验目的： 1、掌握二叉树的二叉链式存储结构； 2、掌握二叉树的建立，遍历等操作。 实验内容： 通过完全前序序列创建一棵二叉树，完成如下功能： 1)输出二叉树的前序遍历序列； 2)输出二叉树的中序遍历序列； 3)输出二叉树的后序遍历序列； 4)统计二叉树的结点总数； 5)统计二叉树中叶子结点的个数； 实验提示： //二叉树的二叉链式存储表示 typedef char TElemType; typedef struct BiTNode{ TElemType data; struct BiTNode *lchild,*rchild; }BiTNode,*BiTree; 一、程序源代码 #include } void Create_BiTree(BiTree *T){ char ch; ch = getchar(); //当输入的是"#"时，认为该子树为空 if(ch == '#') *T = NULL; //创建树结点 else{ *T = (BiTree)malloc(sizeof(struct TNode)); (*T)->data = ch; //生成树结点 //生成左子树 Create_BiTree(&(*T)->lchild); //生成右子树 Create_BiTree(&(*T)->rchild); } } void TraverseBiTree(BiTree T) { //先序遍历 if(T == NULL) return; 实验三二叉树的遍历 一、实验目的 １、熟悉二叉树的结点类型和二叉树的基本操作。 ２、掌握二叉树的前序、中序和后序遍历的算法。 3、加深对二叉树的理解，逐步培养解决实际问题的编程能力。 二、实验环境 运行Ｃ或VC++的微机。 三、实验内容 1、依次输入元素值，以链表方式建立二叉树，并输出结点的值。 2、分别以前序、中序和后序遍历二叉树的方式输出结点内容。 四、设计思路 1. 对于这道题，我的设计思路是先做好各个分部函数，然后在主函数中进行顺序排列，以此完成实验要求 2．二叉树采用动态数组 3.二叉树运用9个函数，主要有主函数、构建空二叉树函数、建立二叉树函数、访问节点函数、销毁二叉树函数、先序函数、中序函数、后序函数、范例函数，关键在于访问节点 五、程序代码 #include int data; //数据域 struct TNode *lchild,*rchild; // 指针域包括左右孩子指针 }TNode,*Tree; void CreateT(Tree *T)//创建二叉树按,依次输入二叉树中结点的值 { int a; scanf("%d",&a); if(a==00) // 结点的值为空 *T=NULL; else // 结点的值不为空 { *T=(Tree)malloc(sizeof(TNode)); if(!T) { printf("分配空间失败！！TAT"); exit(ERROR); } (*T)->data=a; CreateT(&((*T)->lchild)); // 递归调用函数，构造左子树 CreateT(&((*T)->rchild)); // 递归调用函数，构造右子树 } } void InitT(Tree *T)//构建空二叉树 { T=NULL; } void DestroyT(Tree *T)//销毁二叉树 { if(*T) // 二叉树非空 { DestroyT(&((*T)->lchild)); // 递归调用函数，销毁左子树 DestroyT(&((*T)->rchild)); // 递归调用函数，销毁右子树 free(T); T=NULL; } } void visit(int e)//访问结点 { printf("%d ",e); } 数据结构实验报告 一．题目要求 1）编程实现二叉排序树，包括生成、插入，删除； 2）对二叉排序树进行先根、中根、和后根非递归遍历； 3）每次对树的修改操作和遍历操作的显示结果都需要在屏幕上用树的形状表示出来。 4）分别用二叉排序树和数组去存储一个班(50人以上)的成员信息(至少包括学号、姓名、成绩3项),对比查找效率，并说明在什么情况下二叉排序树效率高,为什么? 二．解决方案 对于前三个题目要求，我们用一个程序实现代码如下 #include 图实验一，邻接矩阵的实现 1.实验目的 （1）掌握图的逻辑结构 （2）掌握图的邻接矩阵的存储结构 （3）验证图的邻接矩阵存储及其遍历操作的实现 2.实验内容 （1）建立无向图的邻接矩阵存储 （2）进行深度优先遍历 （3）进行广度优先遍历 3．设计与编码 MGraph.h #ifndef MGraph_H #define MGraph_H const int MaxSize = 10; template #include 实验项目名称：图的遍历 一、实验目的 应用所学的知识分析问题、解决问题，学会用建立图并对其进行遍历，提高实际编程能力及程序调试能力。 二、实验容 问题描述：建立有向图，并用深度优先搜索和广度优先搜素。输入图中节点的个数和边的个数，能够打印出用邻接表或邻接矩阵表示的图的储存结构。 三、实验仪器与设备 计算机，Code::Blocks。 四、实验原理 用邻接表存储一个图，递归方法深度搜索和用队列进行广度搜索，并输出遍历的结果。 五、实验程序及结果 #define INFINITY 10000 /*无穷大*/ #define MAX_VERTEX_NUM 40 #define MAX 40 #include typedef struct ArCell{ int adj; }ArCell,AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; typedef struct { char name[20]; }infotype; typedef struct { infotype vexs[MAX_VERTEX_NUM]; AdjMatrix arcs; int vexnum,arcnum; }MGraph; int LocateVex(MGraph *G,char* v) { int c = -1,i; for(i=0;i 《数据结构》第六次实验报告 学生姓名 学生班级 学生学号 指导老师 一、实验内容 1) 采用二叉树链表作为存储结构，完成二叉树的建立，先序、中序和后序 以及按层次遍历的操作，求所有叶子及结点总数的操作。 2) 输出树的深度，最大元，最小元。 二、需求分析 遍历二叉树首先有三种方法，即先序遍历，中序遍历和后序遍历。 递归方法比较简单，首先获得结点指针如果指针不为空，且有左子，从左子递归到下一层，如果没有左子，从右子递归到下一层，如果指针为空，则结束一层递归调用。直到递归全部结束。 下面重点来讲述非递归方法： 首先介绍先序遍历： 先序遍历的顺序是根左右，也就是说先访问根结点然后访问其左子再然后访问其右子。具体算法实现如下：如果结点的指针不为空，结点指针入栈，输出相应结点的数据，同时指针指向其左子，如果结点的指针为空，表示左子树访问结束，栈顶结点指针出栈，指针指向其右子，对其右子树进行访问，如此循环，直至结点指针和栈均为空时，遍历结束。 再次介绍中序遍历： 中序遍历的顺序是左根右，中序遍历和先序遍历思想差不多，只是打印顺序稍有变化。具体实现算法如下：如果结点指针不为空，结点入栈，指针指向其左子，如果指针为空，表示左子树访问完成，则栈顶结点指针出栈，并输出相应结点的数据，同时指针指向其右子，对其右子树进行访问。如此循环直至结点指针和栈均为空，遍历结束。 最后介绍后序遍历： 后序遍历的顺序是左右根，后序遍历是比较难的一种，首先需要建立两个栈，一个用来存放结点的指针，另一个存放标志位，也是首先访问根结点，如果结点的指针不为空，根结点入栈，与之对应的标志位也随之入标志位栈，并赋值0，表示该结点的右子还没有访问，指针指向该结点的左子，如果结点指针为空，表示左子访问完成，父结点出栈，与之对应的标志位也随之出栈，如果相应的标志位值为0，表示右子树还没有访问，指针指向其右子，父结点再次入栈，与之对应的标志位也入栈，但要给标志位赋值为1，表示右子访问过。如果相应的标志位值为1，表示右子树已经访问完成，此时要输出相应结点的数据，同时将结点指针赋值为空，如此循环直至结点指针和栈均为空，遍历结束。 三、详细设计 源代码： 2009级数据结构实验报告 实验名称：约瑟夫问题 学生姓名：李凯 班级：21班 班内序号：06 学号：09210609 日期：2010年11月5日 1．实验要求 1）功能描述：有n个人围城一个圆圈，给任意一个正整数m，从第一个人开始依次报数，数到m时则第m个人出列，重复进行，直到所有人均出列为止。请输出n个人的出列顺序。 2）输入描述：从源文件中读取。 输出描述：依次从显示屏上输出出列顺序。 2. 程序分析 1）存储结构的选择 单循环链表 2）链表的ADT定义 ADT List{ 数据对象：D={a i|a i∈ElemSet,i=1,2,3,…n,n≧0} 数据关系：R={< a i-1, a i>| a i-1 ,a i∈D,i=1,2,3,4….,n} 基本操作： ListInit(&L)；//构造一个空的单链表表L ListEmpty(L); //判断单链表L是否是空表，若是，则返回1，否则返回0. ListLength(L); //求单链表L的长度 GetElem（L，i）；//返回链表L中第i个数据元素的值； ListSort(LinkList [内容要求] 1、存储结构：顺序表、单链表或其他存储结构，需要画示意图，可参考书上P59 页图2-9 2.2 关键算法分析 结点类： template 邻接矩阵的实现 1. 实验目的 （1）掌握图的逻辑结构 （2）掌握图的邻接矩阵的存储结构 （3）验证图的邻接矩阵存储及其遍历操作的实现2. 实验内容 （1）建立无向图的邻接矩阵存储 （2）进行深度优先遍历 （3）进行广度优先遍历3．设计与编码MGraph.h #ifndef MGraph_H #define MGraph_H const int MaxSize = 10; template int vertexNum, arcNum; }; #endif MGraph.cpp #include 实验一约瑟夫问题 实验学时：3学时 实验类型：设计 实验要求：必修 一、实验目的 熟练掌握线性链表的基础知识； 能够使用C++或其他程序设计语言编程实现线性链表； 能够使用线性链表构造正确而且时间复杂度低的算法解决实际问题； 锻炼程序设计能力。 二、实验内容 M个教徒和N个非教徒在深海上遇险，必须将N个人投入海中，其余的人才能幸免于难，于是想了一个办法：所有人围成一圆圈，从第一个人开始依次报数，每数到第K个人就将他扔入大海，如此循环进行直到仅余M个人为止。设计一个算法，找出这样一个排序：使每次被扔进大海的都是非教徒。并用程序设计语言实现。 三、实验原理、方法和手段 使用循环单链表，将每个人作为一个结点，每个结点的指针域指向下一个人，采用循环链表的遍历对每隔N-1个结点的结点进行标记，直至标记出N个结点为止。该实验亦可用顺序表实现。 四、实验组织运行要求 本实验采用集中授课形式，每个同学独立完成上述实验要求。 五、实验条件 每人一台计算机独立完成实验，有如下条件： （1）硬件：联想高性能PC机； （2）软件：VC++ 6.0、VC++.Net。 六、实验步骤 （1）编写循环链表构造函数Node *Create( )，使链表中每个结点的数据域值为0，并让最后一个结点的指针域指向第一个结点； （2）编写约瑟夫问题函数 Node *Move(Node *H,int n); void Insert(Node *H,int pos,int data); （5）主函数中调用Create，Move和Insert，采用具体数据计算，输出结果。 七、实验程序 // stdafx.h : 标准系统包含文件的包含文件， // 或是经常使用但不常更改的 // 特定于项目的包含文件 // #pragma once #include"targetver.h" #include ******************************* 实验题目：二叉树的操作 实验者信息：班级13007102，姓名庞文正，学号1300710226 实验完成的时间3:00 ****************************** 一、实验目的 1,掌握二叉树链表的结构和二叉树的建立过程。 2,掌握队列的先进先出的运算原则在解决实际问题中的应用。 3,进一步掌握指针变量、指针数组、动态变量的含义。 4,掌握递归程序设计的特点和编程方法。 二、实验内容 已知以二叉链表作存储结构，试编写按层次遍历二叉树的算法。（所谓层次遍历，是指从二叉树的根结点开始从上到下逐层遍历二叉树，在同一层次中从左到右依次访问各个节点。）调试程序并对相应的输出作出分析；修改输入数据，预期输出并验证输出的结果。加深对算法的理解。 三、算法设计与编码 1.本实验用到的理论知识 总结本实验用到的理论知识，实现理论与实践相结合。总结尽量简明扼要，并与本次实验密切相关，最好能加上自己的解释。 本算法要采用一个循环队列que，先将二叉树根结点入队列，然后退队列，输出该结点；若它有左子树，便将左子树根结点入队列；若它有右子树，便将右子树根结点入队列，直到队列空为止。因为队列的特点是先进先出，从而达到按层次顺序遍历二叉的目的。2.算法概要设计 给出实验的数据结构描述，程序模块、功能及调用关系 #include 本科实验报告 课程名称：数据结构（C语言版） 实验项目：线性表、树、图、查找、内排序实验地点：明向校区实验楼208 专业班级：学号： 学生姓名： 指导教师：杨永强 2019 年 1 月10日 #include 学生实验报告 学院：软通学院 课程名称：数据结构与算法 专业班级：软件142 班 姓名：邹洁蒙 学号： 0143990 学生实验报告 （二） 一、实验综述 1、实验目的及要求 目的：1）掌握树与二叉树的基本概念； 2）掌握二叉树的顺序存储，二叉链表的先序遍历中序遍历和后序遍历算法； 3）掌握树的双亲表示法。 要求：1）编程：二叉树的顺序存储实现； 2）编程：二叉链表的先序遍历中序遍历和后序遍历实现； 3）编程：树的双亲表示法实现。 2、实验仪器、设备或软件 设备：PC 软件：VC6 二、实验过程(编程，调试，运行；请写上源码，要求要有注释) 1.编程：二叉树的顺序存储实现 代码： BiTree::BiTree()//建立存储空间 { data = new int[MAXSIZE]; count = 0; } void BiTree::AddNode(int e)//加结点 { int temp = 0; data[count] = e; count++;//从编号0开始保存 } 运行截图： 2.编程：二叉链表的先序遍历中序遍历和后序遍历实现代码： void InOrderTraverse(BiTree* Head)//中序遍历 { if (Head) { InOrderTraverse(Head->LeftChild); cout << Head->data<<" "; InOrderTraverse(Head->RightChild); } } void PreOrderTraverse(BiTree* Head)//先序遍历 { if (Head) { cout << Head->data << " "; PreOrderTraverse(Head->LeftChild); PreOrderTraverse(Head->RightChild); } } void PostOrderTraverse(BiTree* Head)//后序遍历 { if (Head) { PostOrderTraverse(Head->LeftChild); PostOrderTraverse(Head->RightChild); cout << Head->data << " "; } } 运行截图： 《数据结构》实验报告 ◎实验题目: 无向图的建立与遍历 ◎实验目的：掌握无向图的邻接链表存储，熟悉无向图的广度与深度优先遍历。 ◎实验内容：对一个无向图以邻接链表存储，分别以深度、广度优先非递归遍历输出。 一、需求分析 1.本演示程序中，输入的形式为无向图的邻接链表形式，首先输入该无向图的顶点数和边数，接着输入顶点信息，再输入每个边的顶点对应序号。 2.该无向图以深度、广度优先遍历输出。 3.本程序可以实现无向图的邻接链表存储，并以深度、广度优先非递归遍历输出。 4.程序执行的命令包括：（1）建立一个无向图的邻接链表存储（2）以深度优先遍历输出（3）以广度优先遍历输出（4）结束 5.测试数据： 顶点数和边数：6,5 顶点信息：a b c d e f 边的顶点对应序号： 0,1 0,2 0,3 2,4 3,4 深度优先遍历输出： a d e c b f 广度优先遍历输出： a d c b e f 二概要设计 为了实现上述操作，应以邻接链表为存储结构。 1.基本操作： void createalgraph(algraph &g) 创建无向图的邻接链表存储 void dfstraverseal(algraph &g,int v) 以深度优先遍历输出 void bfstraverseal(algraph &g,int v) 以广度优先遍历输出 2.本程序包含四个模块： （1）主程序模块 （2）无向图的邻接链表存储模块 （3）深度优先遍历输出模块 （4）广度优先遍历输出模块 3.模块调用图： 三详细设计 1.元素类型，结点类型和指针类型：typedef struct node { int adjvex; struct node *next; }edgenode; typedef struct vnode { char vertex; edgenode *firstedge; }vertxnode; typedef vertxnode Adjlist[maxvernum]; typedef struct { Adjlist adjlist; int n,e; }algraph; edgenode *s; edgenode *stack[maxvernum],*p; 2.每个模块的分析： （1）主程序模块 int main() 算法与数据结构》课程实验报告 一、实验目的 1、实现二叉树的存储结构 2、熟悉二叉树基本术语的含义 3、掌握二叉树相关操作的具体实现方法 二、实验内容及要求 1. 建立二叉树 2. 计算结点所在的层次 3. 统计结点数量和叶结点数量 4. 计算二叉树的高度 5. 计算结点的度 6. 找结点的双亲和子女 7. 二叉树前序、中序、后序遍历的递归实现和非递归实现及层次遍历 8. 二叉树的复制 9. 二叉树的输出等 三、系统分析 （1）数据方面：该二叉树数据元素采用字符char 型，并且约定“ #”作为二叉树输入结束标识符。并在此基础上进行二叉树相关操作。 （2）功能方面：能够实现二叉树的一些基本操作，主要包括： 1. 采用广义表建立二叉树。 2. 计算二叉树高度、统计结点数量、叶节点数量、计算每个结点的度、结点所在层次。 3. 判断结点是否存在二叉树中。 4. 寻找结点父结点、子女结点。 5. 递归、非递归两种方式输出二叉树前序、中序、后序遍历。 6. 进行二叉树的复制。 四、系统设计 （1）设计的主要思路 二叉树是的结点是一个有限集合，该集合或者为空，或者是由一个根节点加上两棵分别称为左子树和右子树、互不相交的二叉树组成。根据实验要求，以及课上老师对于二叉树存储结构、基本应用的讲解，同时课后研究书中涉及二叉树代码完成二叉树模板类，并将所需实现各个功能代码编写完成，在建立菜单对功能进行调试。 （2）数据结构的设计 二叉树的存储结构有数组方式和链表方式。但用数组来存储二叉树有可能会消耗大量的存储空间，故在此选用链表存储，提高存储空间的利用率。根据二叉树的定义，二叉 2011~2012第一学期数据结构实验报告 班级：信管一班 学号：201051018 姓名：史孟晨 实验报告题目及要求 一、实验题目 设某班级有M（6）名学生，本学期共开设N（3）门课程，要求实现并修改如下程序（算法）。 1. 输入学生的学号、姓名和 N 门课程的成绩（输入提示和输出显示使用汉字系统）， 输出实验结果。（15分） 2. 计算每个学生本学期 N 门课程的总分，输出总分和N门课程成绩排在前 3 名学 生的学号、姓名和成绩。 3. 按学生总分和 N 门课程成绩关键字升序排列名次，总分相同者同名次。 二、实验要求 1．修改算法。将奇偶排序算法升序改为降序。（15分） 2．用选择排序、冒泡排序、插入排序分别替换奇偶排序算法,并将升序算法修改为降序算法；。（45分）） 3．编译、链接以上算法，按要求写出实验报告（25）。 4. 修改后算法的所有语句必须加下划线，没做修改语句保持按原样不动。 5．用A4纸打印输出实验报告。 三、实验报告说明 实验数据可自定义，每种排序算法数据要求均不重复。 (1) 实验题目：《N门课程学生成绩名次排序算法实现》； (2) 实验目的：掌握各种排序算法的基本思想、实验方法和验证算法的准确性； (3) 实验要求：对算法进行上机编译、链接、运行； (4) 实验环境（Windows XP-sp3,Visual c++)； (5) 实验算法（给出四种排序算法修改后的全部清单）； (6) 实验结果（四种排序算法模拟运行后的实验结果）； (7) 实验体会（文字说明本实验成功或不足之处）。 三、实验源程序（算法） Score.c #include "stdio.h" #include "string.h" #define M 6 #define N 3 struct student { char name[10]; int number; int score[N+1]; /*score[N]为总分,score[0]-score[2]为学科成绩*/ }stu[M]; void changesort(struct student a[],int n,int j) {int flag=1,i; struct student temp; while(flag) { flag=0; for(i=1;i 图实验 一，邻接矩阵的实现 1.实验目的 （1）掌握图的逻辑结构 （2）掌握图的邻接矩阵的存储结构 （3）验证图的邻接矩阵存储及其遍历操作的实现 2.实验内容 （1）建立无向图的邻接矩阵存储 （2）进行深度优先遍历 （3）进行广度优先遍历 3．设计与编码 #ifndef MGraph_H #define MGraph_H const int MaxSize = 10; template 浙江科技学院《数据结构》实验报告 年级班级 学号 姓名 任课老师 实验指导教师 实验地点 信息学院 实验一线性表操作（一元多项式的运算） 实验目的： 1、定义线性表的链式存储 2、实现对线性表的一些基本操作和具体函数定义 实验要求： 1、定义线性表的链式存储； 2、实现对线性表的一些基本操作和具体函数定义。 3、定义输出一元多项式的函数； 4、编写主程序调用上面的函数实现一元多项式的加减。 数据输入输出要求： 输入示例： 3 2 3 3 4 5 7 5 2 1 3 3 -3 4 4 6 5 7 （说明：第一个数据3表示该第一个一元多项式的项数为3，后面的2 3 表示第一项的系数为2 指数为3；按指数递增的次序输入） 输出示例： 一元多项式1： 2x(3)+3x(4)+5x(7) 一元多项式2： 2x(1)+3x(3)-3x(4)+4x(6)+5x(7) 加的结果：2x(1)+5x(3) +4x(6)+10x(7) 减的结果：-2x(1)-1x(3)＋6x(4)-4x(6) 程序代码： #include #include数据结构实验报告格式
(完整版)数据结构实验报告全集
数据结构实验报告(四)
数据结构二叉树实验报告
数据结构实验报告
数据结构实验报告图实验
数据结构图的遍历实验报告
数据结构实验报告-二叉树的实现与遍历
数据结构实验报告模板
数据结构实验报告图实验
数据结构实验报告
数据结构实验-二叉树的操作
数据结构实验报告
数据结构实验报告之树与二叉树
数据结构实验报告无向图
数据结构实验报告—二叉树
数据结构实验报告及心得体会
数据结构实验报告图实验
数据结构实验报告
相关主题
文本预览