实验题9.1 设计一个程序exp9-1.cpp,输出在顺序表{3,6,2,10,1,8,5,7,4,9}中采用顺序方法找关键字5的过程。
程序如下:
//文件名:exp9-1.cpp
#include <stdio.h>
#define MAXL 100 //定义表中最多记录个数
typedef int KeyType;
typedef char InfoType[10];
typedef struct
{
KeyType key; //KeyType为关键字的数据类型
…… …… 余下全文
昆明理工大学信息工程与自动化学院学生实验报告
( 201 —201 学年第一学期)
课程名称:数据结构 开课实验室: 年 月 日
一.实验内容:
查找算法,其中线性表的查找包括顺序查找,二分查找,分块查找;树表的查找包括二叉排序树等;还有散列表的查找等等。
二.实验目的:
1.掌握各种查找算法理解和实现;
2.增强上机编程调试能力;
三.主要程序代码分析:
typedef struct
{
int Key; //关键项
…… …… 余下全文
实验报告
计算机科学与技术学院
实验教学中心
2014 年 12 月 10日
实验项目名称:查找( 2 学时)
一、实验目的
1. 掌握顺序表的查找算法在顺序存储结构上的实现。
2. 掌握建立二叉排序树和在二叉排序树上查找指定结点的算法在链式存储结构上的实现。
3. 掌握散列表的建立和查找算法在顺序存储结构上的实现。
4. 掌握散列表的建立和查找算法在链式存储结构上的实现。
二、实验内容
1 顺序表查找在顺序存储结构上的实现。其中函数sqsearch的功能是实现在顺序线性表中顺序查找关键字,函数bisearch的功能是实现在顺序线性表中折半查找关键字。
2. 建立二叉排序树和在二叉排序树上查找指定结点的算法在链式存储结构上的实现。其中函数bstsearch的功能是实现利用递归方法在二叉排序树上查找指定结点,函数bstsearch1的功能是实现利用非递归方法在二叉排序树上查找指定结点,函数bstinsert的功能是实现在二叉排序树上插入结点,函数createbsttree的功能是实现建立一棵二叉排序树,函数inorder的功能是实现中序遍历二叉树。
…… …… 余下全文
数据结构实验报告
实验第四章:
实验: 简单查找算法
一.需求和规格说明:
查找算法这里主要使用了顺序查找,折半查找,二叉排序树查找和哈希表查找四种方法。由于自己能力有限,本想实现其他算法,但没有实现。其中顺序查找相对比较简单,折半查找参考了书上的算法,二叉排序树查找由于有之前做二叉树的经验,因此实现的较为顺利,哈希表感觉做的并不成功,感觉还是应该可以进一步完善,应该说还有很大的改进余地。
二.设计思想:
开始的时候提示输入一组数据。并存入一维数组中,接下来调用一系列查找算法对其进行处理。顺序查找只是从头到尾进行遍历。二分查找则是先对数据进行排序,然后利用三个标志,分别指向最大,中间和最小数据,接下来根据待查找数据和中间数据的比较不断移动标志,直至找到。二叉排序树则是先构造,构造部分花费最多的精力,比根节点数据大的结点放入根节点的右子树,比根节点数据小的放入根节点的左子树,其实完全可以利用递归实现,这里使用的循环来实现的,感觉这里可以尝试用递归。当二叉树建好后,中序遍历序列即为由小到大的有序序列,查找次数不会超过二叉树的深度。这里还使用了广义表输出二叉树,以使得更直观。哈希表则是利用给定的函数式建立索引,方便查找。
…… …… 余下全文
实验四 ——查找
一、实验目的
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)
…… …… 余下全文
《数据结构》
第八次实验报告
一、实验内容
1) 有序表的二分查找
?建立有序表,然后进行二分查找
2) 二叉排序树的查找
?建立二叉排序树,然后查找
二、需求分析
二分查找的基本思想是将n个元素分成大致相等的两部分,取a[n/2]与x做比较,如果x=a[n/2],则找到x,算法中止;如果x<a[n/2],则只要在数组a的左半部分继续搜索x,如果x>a[n/2],则只要在数组a的右半部搜索x.
时间复杂度无非就是while循环的次数!
总共有n个元素,
渐渐跟下去就是n,n/2,n/4,....n/2^k(接下来操作元素的剩余个数),其中k就是循环的次数
由于你n/2^k取整后>=1
即令n/2^k=1
可得k=log2n,(是以2为底,n的对数)
所以时间复杂度可以表示O()=O(logn)
下面提供一段二分查找实现的伪代码:
BinarySearch(max,min,des)
mid-<(max+min)/2
while(min<=max)
mid=(min+max)/2
if mid=des then
…… …… 余下全文
成都信息工程学院计算机系
课程实验报告
1、 深入理解数据结构的算法思想,将算法理论与实际应用相结合,培养学生的编程能力与编程兴趣,让学生清楚从项目分析、编码 、调试、程序维护的整个程序开发流程。
2、 使学生清楚解决一个编程问题的基本流程,即首先确定逻辑结构,然后在逻辑结构的基础上确定相应的存储结构,最后在设计一套合理而简便实用的算法,整个过程都是在用到数据结构的事项解决问题,是学生能够对线性表、二叉树、图的基本操作较为熟悉,并轻松控制。
3、 让学生明白在编程调试的过程中学习程序设计的思想、分析方法,培养并提高编程能力。
PC机每人1台
.实现所有的动态查找表。
该部分算法有一定的难度,尤其二叉排序树与平衡二叉树,涉及树的插入与删除等复杂操作。实现不易,尽管书中给出的代码较为详细,主要是能较好的掌握二叉树的插入、删除、与遍历,并能很好说明平衡二叉树的动态查找效率明显高于二叉排序树。
1、 传参数时出现的问题、传递过去数值的话不能改变数据值,必须传递地址才行;
…… …… 余下全文
计算机科学与技术系
实 验 报 告
专业名称 计算机科学与技术 课程名称 数据结构与算法 项目名称 顺序表查找
班 级
学 号
姓 名
实验日期
格 式 要 求
实验报告注意格式规范,要求在word中编写,文中不要有空行,统一使用A4页面。
页边距:上2.5cm、下2cm、左2.5cm、右2cm。
标题:宋体、四号字、加粗、1.5倍行距。
正文:宋体、小四号字、1.2倍行距。
一、实验目的与要求:
(一)实验目的
1、掌握线性表中元素的前驱、后续的概念。
2、掌握顺序表与链表的建立、插入元素、删除表中某元素的算法。
3、掌握线性表三种查找的算法。
4、对线性表相应算法的时间复杂度进行分析。
5、理解顺序表数据结构的特点(优缺点)。
(二)实验要求
1.将实验中所要求的每个功能用一个函数实现。
2.每个输入前要有输入提示,每个输出数据都要求有内容说明(如:280和100的和是:380。)。
3.函数名称和变量名称等用英文或英文简写(每个单词第一个字母大写)形式说明。
…… …… 余下全文