动态查找表实验报告材料
动态查找表实验报告 一. 1 、实验概要 实验项目名称: 抽象数据类型的实现 实验项目性质: 设计性实验 所属课程名称: 数据结构 实验计划学时: 6 2、实验目的 对某个具体的抽象数据类型,运用课程所学的知识和方法,设计合理的数据结构,并在此基础上实现该抽象数据类型的全部基本操作。通过本设计性实验,检验所学知识和能力,发现学习中存在的问题。进而达到熟练地运用本课程中的基础知识及技术的目的。 实验要求如下: 1.参加实验的学生应首先了解设计的任务,然后根据自己的基础和能力从中选择一题。一般来说,选择题目应以在规定的时间内能完成,并能得到应有的锻炼为原则。若学生对教材以外的相关题目较感兴趣,希望选作实验的题目时,应征得指导教师的认可,并写出明确的抽象数据类型定义及说明。 2. 实验前要作好充分准备,包括:理解实验要求,掌握辅助工具的使用,了解该抽象数据类型的定义及意义,以及其基本操作的算法并设计合理的存储结构。 3. 实验时严肃认真,要严格按照要求独立进行设计,不能随意更改。注意观察并记录各种错误现象,纠正错误,使程序满足预定的要求,实验记录应作为实验报告的一部分。 4. 实验后要及时总结,写出实验报告,并附所打印的问题解答、程序清单,所输入的数据及相应的运行结果。 所用软件环境或工具:DEV-C++5可视化编程环境. 3.动态查找表的抽象数据类型 ADT DynamicSearchTable { 数据对象D:D是具有相同特性的数据元素的集合。每个数据元素含有类型相同的关键字,可唯一 标识数据元素。 数据关系R:数据元素同属一个集合。 基本操作P: InitDSTable(&DT); 操作结果:构造一个空的动态查找表DT。 DestroyDSTable(&DT); 初始条件:动态查找表DT存在; 操作结果:销毁动态查找表DT。 SearchDSTable(DT, key); 初始条件:动态查找表DT存在,key为和关键字类型相同的给定值; 操作结果:若DT中存在其关键字等于key的数据元素,则函数值为该元素的值或在表中的
数据结构二叉排序树实验报告
实验报告 课程名:数据结构(C语言版)实验名:二叉排序树 : 班级: 学号: 撰写时间:2014.12.18
一实验目的与要求 1.掌握二叉排序树上进行插入和删除的操作 2.利用C 语言实现该操作 二实验内容 ?对于一个线形表, 利用不断插入的方法, 建立起一株二叉排序树 ?从该二叉排序树中删除一个叶子节点, 一个只有一个子树的非叶子节,一个有两个子树的非叶子节点。 三实验结果与分析 #include #include //二叉查找树结点描述 typedef int KeyType; typedef struct Node { KeyType key; //关键字 struct Node * left; //左孩子指针 struct Node * right; //右孩子指针 struct Node * parent; //指向父节点指针 }Node,*PNode;
//往二叉查找树中插入结点 //插入的话,可能要改变根结点的地址,所以传的是二级指针void inseart(PNode * root,KeyType key) { //初始化插入结点 PNode p=(PNode)malloc(sizeof(Node)); p->key=key; p->left=p->right=p->parent=NULL; //空树时,直接作为根结点 if((*root)==NULL){ *root=p; return; } //插入到当前结点(*root)的左孩子 if((*root)->left == NULL && (*root)->key > key){ p->parent=(*root); (*root)->left=p; return; } //插入到当前结点(*root)的右孩子 if((*root)->right == NULL && (*root)->key < key){ p->parent=(*root);
查找与排序实验报告
实验四:查找与排序 【实验目的】 1.掌握顺序查找算法的实现。 2.掌握折半查找算法的实现。 【实验内容】 1.编写顺序查找程序,对以下数据查找37所在的位置。 5,13,19,21,37,56,64,75,80,88,92 2.编写折半查找程序,对以下数据查找37所在的位置。 5,13,19,21,37,56,64,75,80,88,92 【实验步骤】 1.打开VC++。 2.建立工程:点File->New,选Project标签,在列表中选Win32 Console Application,再在右边的框里为工程起好名字,选好路径,点OK->finish。 至此工程建立完毕。 3.创建源文件或头文件:点File->New,选File标签,在列表里选C++ Source File。给文件起好名字,选好路径,点OK。至此一个源文件就被添加到了你刚创建的工程之中。 4.写好代码 5.编译->链接->调试 #include "stdio.h" #include "malloc.h" #define OVERFLOW -1 #define OK 1 #define MAXNUM 100 typedef int Elemtype; typedef int Status; typedef struct {
Elemtype *elem; int length; }SSTable; Status InitList(SSTable &ST ) { int i,n; ST.elem = (Elemtype*) malloc (MAXNUM*sizeof (Elemtype)); if (!ST.elem) return(OVERFLOW); printf("输入元素个数和各元素的值:"); scanf("%d\n",&n); for(i=1;i<=n;i++) { scanf("%d",&ST.elem[i]); } ST.length = n; return OK; } int Seq_Search(SSTable ST,Elemtype key) { int i; ST.elem[0]=key; for(i=ST.length;ST.elem[i]!=key;--i); return i; } int BinarySearch(SSTable ST,Elemtype key) { int low,high,mid; low=1; high=ST.length;
顺序表的查找、插入与删除实验报告
《数据结构》实验报告一 学院:班级: 学号:姓名: 日期:程序名 一、上机实验的问题和要求: 顺序表的查找、插入与删除。设计算法,实现线性结构上的顺序表的产生以及元素的查找、插入与删除。具体实现要求: 1.从键盘输入10个整数,产生顺序表,并输入结点值。 2.从键盘输入1个整数,在顺序表中查找该结点的位置。若找到,输出结点的位置;若找 不到,则显示“找不到”。 3.从键盘输入2个整数,一个表示欲插入的位置i,另一个表示欲插入的数值x,将x插 入在对应位置上,输出顺序表所有结点值,观察输出结果。 4.从键盘输入1个整数,表示欲删除结点的位置,输出顺序表所有结点值,观察输出结果。 二、源程序及注释: #include #include /*顺序表的定义:*/ #include #define ListSize 100 /*表空间大小可根据实际需要而定,这里假设为100*/ typedef int DataType; /*DataType可以是任何相应的数据类型如int, float或char*/ typedef struct { DataType data[ListSize]; /*向量data用于存放表结点*/ int length; /*当前的表长度*/ }SeqList; void main() { SeqList L; int i,x; int n=10; /*欲建立的顺序表长度*/ L.length=0; void CreateList(SeqList *L,int n); void PrintList(SeqList L,int n); int LocateList(SeqList L,DataType x); void InsertList(SeqList *L,DataType x,int i); void DeleteList(SeqList *L,int i);
河南工业大学实验报告——查找和排序(排序)——张伟龙
河南工业大学实验报告 课程名称数据结构实验项目实验三查找和排序(二)——排序院系信息学院计科系专业班级计科1203 姓名张伟龙学号 201216010313 指导老师范艳峰日期 2013.6.5 批改日期成绩 一实验目的 掌握希尔排序、快速排序、堆排序的算法实现。 二实验内容及要求 实验内容:1.实现希尔排序。 2.实现快速排序。 3. 实现堆排序。 (三选一) 实验要求:1. 根据所选题目,用C语言编写程序源代码。 2. 源程序必须编译调试成功,独立完成。 三实验过程及运行结果 选择第三题: Source Code: #include #include using namespace std; void HeapAdjust(int *a,int i,int size) //调整堆 { int lchild=2*i; //i的左孩子节点序号
int rchild=2*i+1; //i的右孩子节点序号 int max=i; //临时变量 if(i<=size/2) //如果i是叶节点就不用进行调整 { if(lchild<=size&&a[lchild]>a[max]) { max=lchild; } if(rchild<=size&&a[rchild]>a[max]) { max=rchild; } if(max!=i) { swap(a[i],a[max]); HeapAdjust(a,max,size); //避免调整之后以max为父节点的子树不是堆 } } } void BuildHeap(int *a,int size) //建立堆 { int i; for(i=size/2;i>=1;i--) //非叶节点最大序号值为size/2 { HeapAdjust(a,i,size); } }
北邮数据结构实验—二叉排序树
数据结构 实 验 报 告 实验名称:______二叉排序树___________ 学生姓名:____________________ 班级:_______________ 班内序号:_______________________ 学号:________________ 日期:________________
1.实验要求 根据二叉排序树的抽象数据类型的定义,使用二叉链表实现一个二叉排序树。 二叉排序树的基本功能: 1.二叉排序树的建立 2.二叉排序树的查找 3.二叉排序树的插入 4.二叉排序树的删除 5.二叉排序树的销毁 6.其他:自定义操作编写 测试main()函数测试二叉排序树的正确性 2. 程序分析 2.1 存储结构 二叉链表 2.2 程序流程(或程序结构、或类关系图等表明程序构成的内容,一般为流程图等) 2.2.1.
2.2.2.伪代码 1.从文件读取待建树元素 2.建树,若待插入元素比根节点小,向左子树前进并重复比较左子树根节点,若待插入元素比根节点大,向右子树前进并重复比较右子树根节点,直至找到空节点则插入该元素,不断插入直至不剩下元素。 3.用户选择操作。 4.若用户选择查找,则现由用户输入待查找数值。从根节点开始比较,若较小则移至左子树,若较大则移至右子树,直至关键码相等,则输出节点情况。 5.若用户选择插入,则现由用户输入待插入数值。从根节点开始比较,若较小则移至左子树,若较大则移至右子树,直至到空节点,则插入该元素。 6.若用户选择删除,则现由用户输入待删除数值。从根节点开始比较,若较小则移至左子树,若较大则移至右子树,直至关键码相等; 1).若该节点为叶子节点,则直接删除; 2).若该节点无左子树,则其双亲节点直接与其右子树根节点连接,再删除该节点; 3).若该节点有左子树,则其左子树的最右节点数值直接覆盖该节点数值,再删除最后节点。 7.若用户选择销毁,则不断执行删除操作直至不剩余节点。 8.若用户选择退出,则程序结束。 2.3 关键算法分析 关键代码即删除操作,代码如下: void Delete(BiNode* &R) { BiNode* q=new BiNode; BiNode *s=new BiNode; if(R->lch==NULL){ q=R; R=R->rch; delete q;} else if(R->rch==NULL){ q=R; R=R->lch; delete q; } else{ q=R; s=R->lch; while(s->rch!=NULL) { q=s; s=s->rch;} R->data=s->data; if(q!=R)
《数据结构》实验报告查找
实验四——查找 一、实验目的 1.掌握顺序表的查找方法,尤其是折半查找方法; 2.掌握二叉排序树的查找算法。 二、实验内容 1.建立一个顺序表,用顺序查找的方法对其实施查找; 2.建立一个有序表,用折半查找的方法对其实施查找; 3.建立一个二叉排序树,根据给定值对其实施查找; 4.对同一组数据,试用三种方法查找某一相同数据,并尝试进行性能分析。 三、实验预习内容 实验一包括的函数有:typedef struct ,创建函数void create(seqlist & L),输出函数void print(seqlist L),顺序查找int find(seqlist L,int number),折半查找int halffind(seqlist L,int number) 主函数main(). 实验二包括的函数有:结构体typedef struct,插入函数void insert(bnode * & T,bnode * S),void insert1(bnode * & T),创建函数void create(bnode * & T),查找函数bnode * search(bnode * T,int number),主函数main(). 四、上机实验 实验一: 1.实验源程序。 #include<> #define N 80 typedef struct { int number; umber; for(i=1;[i].number!=0;) { cin>>[i].name>>[i].sex>>[i].age; ++; cout<>[++i].number; } } umber<<"\t"<<[i].name<<"\t"<<[i].sex<<"\t"<<[i].age<数据结构实验报告九
数据结构实验报告 查找 1.实验目的 (1) 掌握顺序表的查找方法,尤其是二分查找方法。 (2) 掌握二叉排序树的建立及查找。 查找是软件设计中的最常用的运算,查找所涉及到的表结构的不同决定了查找的方法及其性能。二分查找是顺序表的查找中的最重要的方法,应能充分理解其实现方法和有关性能,并能借助其判定树结构来加深理解。二叉排序树结构在实验时具有一定的难度,可结合二叉树的有关内容和方法来实现。 2.实验内容和要求 编写算法实现下列问题的求解。 (1) 对下列数据表,分别采用二分查找算法实现查找,给出查找过程依次所比较的元素(的下标),并以二分查找的判定树来解释。 第一组测试数据: 数据表为(1,2,3,4,6,7,8,9,10,11,12,13,17,18,19,20,24,25,26,30,35,40,45,50,,100) 查找的元素分别为:2,8,20, 30,50,5,15,33,110 第二组数据: 数据表为(2,3,5,7,8,10,12,15,18,20,22,25,30,35,40,45,50,55,60, 80,100) 查找的元素分别为:22,8,80,3,100,1,13,120 (2) 设计出在二叉排序树中插入结点的算法,在此基础上实现构建二叉排序树的算法。 测试数据:构建二叉排序树的输入序列如下: 第一组数据: 100,150,120,50,70,60,80,170,180,160,110,30,40,35,175 第二组数据: 100,70,60,80,150,120,50,160,30,40,170,180,175,35 (3) 设计算法在二叉排序树中查找指定值的结点。 测试数据:在任务<1>中第一组测试数据所构造的二叉排序树中,分别查找下列元素:150,70,160,190,10,55,175 (4) 设计算法在二叉排序树中删除特定值的结点。 测试数据:在任务(1)中第一组测试数据所构造的二叉排序树中,分别删除下列元素:30,150,100
查找排序实验报告
《编程实训》 实验报告书 专业:计算机科学与技术 班级:151班 学号: 姓名: 指导教师: 日期:2016年6月30日
目录 一、需求分析 (3) 1.任务要求 (3) 2.软件功能分析 (3) 3.数据准备 (3) 二、概要设计 (3) 1.功能模块图 (4) 2.模块间调用关系 (4) 3.主程序模块 (5) 4.抽象数据类型描述 (5) 三、详细设计 (6) 1.存储结构定义 (6) 2.各功能模块的详细设计 (7) 四、实现和调试 (7) 1.主要的算法 (7) 2.主要问题及解决 (8) 3.测试执行及结果 (8) 五、改进 (9) 六、附录 (9) 1.查找源程序 (9) 2.排序源程序 (9)
目录 1 需求分析 1.1 任务要求 对于从键盘随机输入的一个序列的数据,存入计算机内,给出各种查找算法的实现; 以及各种排序算法的实现。 1.2 软件功能分析 任意输入n个正整数,该程序可以实现各类查找及排序的功能并将结果输出。 1.3 数据准备 任意输入了5个正整数如下: 12 23 45 56 78 2 概要设计(如果2,3合并可以省略2.4) 2.1 功能模块图(注:含功能说明) 2.2 模块间调用关系 2.3 主程序模块 2.4 抽象数据类型描述 存储结构:数据结构在计算机中的表示(也称映像)叫做物理结构。又称为存储结构。数据类型(data type)是一个“值”的集合和定义在此集合上的一组操作的总称。 3 详细设计 3.1 存储结构定义 查找: typedef int ElemType ; //顺序存储结构 typedef struct { ElemType *elem; //数据元素存储空间基址,建表时按实际长度分配,号单元留空 int length; //表的长度
实验报告
实验报告 实验题目:二叉树 实验目的: 1、熟悉二叉树的结点类型和二叉树的基本操作。 2、掌握二叉树的前序、中序和后序遍历的算法。 3、加深对二叉树的理解,逐步培养解决实际问题的编程能力。 基本要求: 1.编写程序bitree.cpp实现ADTBiTree,要求使用二叉链表存储。实现基本操作:InitBiTree(&T); DestroyBiTree(&T); PreOrder(T,visit()); InOrder(T,visit()); PostOrder(T,visit()); 2.编码实现以下算法: 1)创建二叉树。(以先序扩展序列给出) 2)输出先序、中序和后序序列。 3)计算二叉树结点数、叶子结点数、高度。 测试数据:先序扩展序列:ABDF##G##E#H##C##输出:先序ABDFGEHC中序FDGBEHAC后序FGDHEBCA结点数:8叶子结点数:4高度:4。
实验拓展 1)实现层次遍历。 2)查找:查值为X的结点、双亲结点、孩子结点、兄弟结点 3)判断:判断一个二叉树是否为二叉排序树、完全二叉树、平衡和二叉树 4)处理:左右子树互换、复制、删除子树、插入子树 设计思路: 1.在二叉树的存储结构为链式存储结构。 2.在具体实现的时候建立不同函数,在主程序中用循环菜单的形式调用函数提高了效率。 概要分析: 二叉链表结构定义: typedef struct BiNode{ ElemType data; struct BiNode *lchild,*rchild; }BiNode,*BiTree; CreatBiTree(BiTree &T);先序建立二叉树。 DestroyBiTree(BiTree &T);销毁二叉树; PreOrder(BiTree &T);先序遍历二叉树 InOrder(BiTree &T);中序遍历二叉树 PostOrder (BiTree &T);后序遍历二叉树 PrintbyLev(BiTree &T);按层次遍历二叉树,利用队列的思想,从根结点开始将其放入一
各种排序实验报告
【一】需求分析 课程题目是排序算法的实现,课程设计一共要设计八种排序算法。这八种算法共包括:堆排序,归并排序,希尔排序,冒泡排序,快速排序,基数排序,折半插入排序,直接插入排序。 为了运行时的方便,将八种排序方法进行编号,其中1为堆排序,2为归并排序,3为希尔排序,4为冒泡排序,5为快速排序,6为基数排序,7为折半插入排序8为直接插入排序。 【二】概要设计 1.堆排序 ⑴算法思想:堆排序只需要一个记录大小的辅助空间,每个待排序的记录仅占有一个存储空间。将序列所存储的元素A[N]看做是一棵完全二叉树的存储结构,则堆实质上是满足如下性质的完全二叉树:树中任一非叶结点的元素均不大于(或不小于)其左右孩子(若存在)结点的元素。算法的平均时间复杂度为O(N log N)。 ⑵程序实现及核心代码的注释: for(j=2*i+1; j<=m; j=j*2+1) { if(j=su[j]) break; su[i]=su[j]; i=j; } su[i]=temp; } void dpx() //堆排序 { int i,temp; cout<<"排序之前的数组为:"<=0; i--) { head(i,N); } for(i=N-1; i>0; i--) {
temp=su[i]; su[i]=su[0]; su[0]=temp; head(0,i-1); } cout<<"排序之后的数组为:"<数据结构实验三——二叉树基本操作及运算实验报告
《数据结构与数据库》 实验报告 实验题目 二叉树的基本操作及运算 一、需要分析 问题描述: 实现二叉树(包括二叉排序树)的建立,并实现先序、中序、后序和按层次遍历,计算叶子结点数、树的深度、树的宽度,求树的非空子孙结点个数、度为2的结点数目、度为2的结点数目,以及二叉树常用运算。 问题分析: 二叉树树型结构是一类重要的非线性数据结构,对它的熟练掌握是学习数据结构的基本要求。由于二叉树的定义本身就是一种递归定义,所以二叉树的一些基本操作也可采用递归调用的方法。处理本问题,我觉得应该:
1、建立二叉树; 2、通过递归方法来遍历(先序、中序和后序)二叉树; 3、通过队列应用来实现对二叉树的层次遍历; 4、借用递归方法对二叉树进行一些基本操作,如:求叶子数、树的深度宽度等; 5、运用广义表对二叉树进行广义表形式的打印。 算法规定: 输入形式:为了方便操作,规定二叉树的元素类型都为字符型,允许各种字符类型的输入,没有元素的结点以空格输入表示,并且本实验是以先序顺序输入的。 输出形式:通过先序、中序和后序遍历的方法对树的各字符型元素进行遍历打印,再以广义表形式进行打印。对二叉树的一些运算结果以整型输出。 程序功能:实现对二叉树的先序、中序和后序遍历,层次遍历。计算叶子结点数、树的深度、树的宽度,求树的非空子孙结点个数、度为2的结点数目、度为2的结点数目。对二叉树的某个元素进行查找,对二叉树的某个结点进行删除。 测试数据:输入一:ABC□□DE□G□□F□□□(以□表示空格),查找5,删除E 预测结果:先序遍历ABCDEGF 中序遍历CBEGDFA 后序遍历CGEFDBA 层次遍历ABCDEFG 广义表打印A(B(C,D(E(,G),F))) 叶子数3 深度5 宽度2 非空子孙数6 度为2的数目2 度为1的数目2 查找5,成功,查找的元素为E 删除E后,以广义表形式打印A(B(C,D(,F))) 输入二:ABD□□EH□□□CF□G□□□(以□表示空格),查找10,删除B 预测结果:先序遍历ABDEHCFG 中序遍历DBHEAGFC 后序遍历DHEBGFCA 层次遍历ABCDEFHG 广义表打印A(B(D,E(H)),C(F(,G))) 叶子数3 深度4 宽度3 非空子孙数7 度为2的数目2 度为1的数目3 查找10,失败。
查询与排序 实验报告
学院专业班学号 协作者_____________教师评定_________________ 实验题目查询与排序 综合实验评分表
实验报告 一、实验目的与要求 1、掌握散列表的构造及实现散列查找; 2、掌握堆排序的算法; 3、综合比较各类排序算法的性能。 二、实验容 #include"stdio.h" #include"stdlib.h" #include"string.h" #include"windows.h" #define MAX 20 typedef struct{ unsigned long key; int result; char name[30];}RNode; RNode t[MAX],r[MAX]; int h(unsigned long k) /*散列函数*/ { return((k-3109005700)%11); } void insert(RNode t[],RNode x) /*插入函数,以线性探查方法解决冲突*/ {
int i,j=0; i=h(x.key); while((j0)) j++; if(j==MAX) printf("full\n"); i=(i+j)%MAX; if(t[i].key==0) {t[i]=x;} else { if(t[i].key==x.key) printf("记录已存在!\n"); } } int search(RNode t[],unsigned long k) /*插入函数,以线性探查方法解决冲突*/ { int i,j=0; i=h(k); while((j河南工业大学实验报告_实验三 查找和排序(一)——查找
xxx大学实验报告 课程名称数据结构实验项目实验三查找和排序(一)——查找 院系信息学院计类系专业班级计类1501 姓名学号 指导老师日期 批改日期成绩 一实验目的 1.掌握哈希函数——除留余数法的应用; 2. 掌握哈希表的建立; 3. 掌握冲突的解决方法; 4. 掌握哈希查找算法的实现。 二实验内容及要求 实验内容:已知一组关键字(19,14,23,1,68,20,84,27,55,11,10,79),哈希 函数定义为:H(key)=key MOD 13, 哈希表长为m=16。实现该哈希表的散列,并 计算平均查找长度(设每个记录的查找概率相等)。 实验要求:1. 哈希表定义为定长的数组结构;2. 使用线性探测再散列或链 地址法解决冲突;3. 散列完成后在屏幕上输出数组内容或链表;4. 输出等概率 查找下的平均查找长度;5. 完成散列后,输入关键字完成查找操作,要分别测 试查找成功与不成功两种情况。 注意:不同解决冲突的方法会使得平均查找长度不同,可尝试使用不同解决 冲突的办法,比较平均查找长度。(根据完成情况自选,但至少能使用一种方法 解决冲突) 三实验过程及运行结果 #include #include #include #define hashsize 16
#define q 13 int sign=2; typedef struct Hash { int date; //值域 int sign; //标记 }HashNode; void compare(HashNode H[],int p,int i,int key[]) //线性冲突处理{ p++; if(H[p].sign!=0) { sign++; compare(H,p,i,key); } else { H[p].date=key[i]; H[p].sign=sign; sign=2; } } void Hashlist(HashNode H[],int key[]) { int p; for(int i=0;i<12;i++) { p=key[i]%q; if(H[p].sign==0) { H[p].date=key[i]; H[p].sign=1; } else compare(H,p,i,key); } } int judge(HashNode H[],int num,int n) //查找冲突处理 {
数据结构内排序实验报告
一、实验目的 1、了解内排序都是在内存中进行的。 2、为了提高数据的查找速度,需要对数据进行排序。 3、掌握内排序的方法。 二、实验内容 1、设计一个程序e xp10—1.cpp实现直接插入排序算法,并输出{9,8,7,6,5,4,3,2,1,0}的排序 过程。 (1)源程序如下所示: //文件名:exp10-1.cpp #include #define MAXE 20 //线性表中最多元素个数 typedef int KeyType; typedef char InfoType[10]; typedef struct //记录类型 { KeyType key; //关键字项 InfoType data; //其他数据项,类型为InfoType } RecType; void InsertSort(RecType R[],int n) //对R[0..n-1]按递增有序进行直接插入排序 { int i,j,k; RecType temp; for (i=1;i=0 && temp.key