数据结构。
课程设计报告。
设计题目:查找。
专业:计算机科技。
院系:计算机学院。
姓名: xx xx
学号: xxxxxxxxx
时间:2024年10月7日。
目录。一实践目的与要求 - 2-
1.1实践目的 - 2 -
1.2实践要求 - 2 -
二顺序查找的分析、程序、及运行结果 - 2 -
2.1系统简介 - 2 -
2.2 设计思路 - 2 -
2.3顺序查找算法描述 - 2 -
三折半查找的分析、程序、及运行结果 - 4 -
3.1系统简介 - 4 -
3.2设计思路 - 4 -
3.3折半查找算法描述 - 5 -
四二叉排序树查找的分析、程序、及运行结果 - 5 -
4.1系统简介 - 5 -
4.2设计思路 - 5 -
4.3二叉排序树算法描述 - 6 -
五哈希查找的分析、程序、及运行结果 - 8 -
5.1系统简介 - 8 -
5.2设计思路 - 9 -
5.3哈希查找算法描述 - 9 -
六用户手册 - 11-
七附件 - 13-
八参考文献 - 17-
1) 掌握各种查找算法的思想及其使用条件;
2) 掌握上机实现各种查找算法的基本思想;
3) 熟练掌握二叉排序树的构造和查找方法;
4) 掌握散列表存储结构的思想,能选择合适的散列表函数,实现不同冲突处理方法的散列表的查找与建立;
1) 掌握实践是算法。
2) 上机运行程序,保存和打印运行结果,并结合程序进行分析。
3) 注意理解折半查找的适用条件。
4) 建立二叉排序树、散列表是相同元素的处理。
5) 比较各种查找算法的各自特点,能够结合实际情况选择合适的查找方式。
一次输入顺序表中的各个元素,然后进行关键字查找。如果存在则返回待查元素的位置。
1)顺序查找的思想。
对于给定的关键字k,从表中的一端开始,逐个进行数据元素的关键字和给定值的比较,若当前扫描到的关键字与k 相等则查找成功;若扫描结束后,仍未找到关键字等于k的节点,则查找失败。
建立一个顺序表,数据元素从下标为1的单元开始放入,下标为0的元素起哨兵作用,将待查的关键字存入下标为0的单元,顺序表从后向前查找,若直到下标为0时才找到关键字则说明查找失败,若不到下标为0时就找到关键字,则查找成功。
*顺序表结构体定义*/
typedef struct
keytype key[maxsize];
int len;
stable;
*建立线性表*/
stable create_s(stable r)
int i,j=0,k=1;
printf("请输入顺序表元素,要为整形,用空格分开,-99为结束标志:");
scanf("%d",&i);
while(i!=-99)
return r;
*顺序表查找*/
int search_s(keytype k,stable *r)
int j;
j=r->len;
r->key[0]=k;
while(r->key[j]!=k)
j--;return j;
一次输入顺序表中的各个元素,然后进行关键字查找。如果存在则返回待查元素的位置,否则显示不存在。
1) 折半查找的基本思想。
设查找表中的元素存放在数组r中,数据元素的下标范围为[low,high],查找的关键字值为key,中间元素的下标为mid=(low+high)/2,(向下取整),令key与r[mid]的关键字比较:
若key=r[mid].key,查找成功,下标为m的记录即为所求,返回mid。
若key若key>r[mid].key, 所要找的记录只能在右半部分记录中,在对右半部分记录中,再对右半部分使用折半查找法继续进行查找,搜索区间缩小一半。
重复上述过程,直到找到查找表中某个数据元素的关键字的值等于给定的值key说明查找成功,若出现low的值大于high的情况,说明查找不成功。
建立一个有序表,数据元素从下标为1的单元开始放入。实现查找算法时,首先将low赋值为1,high等于最后一个数据元素的下标,然后将给定的关键字与查找区间[low,high]中间的数据元素的关键字比较,实现查找过程。
*顺序表结构体定义*/
typedef struct
keytype key[maxsize];
int len;
stable;
*折半查找*/
int search_bin(keytype k,stable *r)
int low,high,mid;
low=1;
high=r->len;
while(low<=high)
return 0;
依次输入关键字并建立二叉排序树,实现二叉排序树的插入和查找功能。
1) 二叉排序树的基本思想。
二叉排序树就是将原来的数据根据大小构成一棵二叉树,二叉树中的所有节点数据满足一定的大小关系,所有的左自述中的节点均比根节点小,所有的右子树的节点均比根结点大。
二叉排序树查找是指按照二叉排序树中结点的关系进行查找,查找的关键字首先同根结点比较,如果相等则查找成功;如果比根结点小,则在左子树中查找;如果比根结点大,则在右子树中查找。这种查找方法可以快速缩小查找范围,大大减小查找关键字的比较次数,从而提高查找效率。
2)算法分析。
算法的关键过程实际上就是二叉排序树的创建和查找两个步骤。首先创建一个根结点,第二步就是将其他结点不断插入到二叉树中的合适位置。二叉排序树进行结点插入时,首先要为结点寻找合适的位置插入。
这个过程实际上就是关键字不断比较的过程。如果比根结点小,则在左子树中插入;如果比根结点大,则在右子树中插入。
然后在二叉排序树中查找关键字的结点存在。
*二叉排序树结构体定义*/
typedef struct bsnode
keytype data;
struct bsnode *lchild;
struct bsnode *rchild;
bnode;
bnode * bsp;
bnode bst;
*为关键字key建立一个二叉排序树结点*/
bnode * createbst(keytype key)
bnode *s;
s=(bnode *)malloc(sizeof(bst));
s->data=key;
s->lchild=s->rchild=null;
return (s);
*将s指向的结点插入到t指向的二叉树中*/
bnode * bstinsert(bnode * t,bnode * s)
bnode * q,*p;
if(t==null)
return(s);
elseif(s->datadata)
q->lchild=s;
else q->rchild=s;
return (t);
*输出二叉排序树*/
void bstprint(bnode * t)
if(t)*在二叉排序树中查找关键字*/
void search(bnode * t,keytype x)
bnode * p;
if(t==null)else
p=t;while(p)
if(p->data==x)
printf("search success!");
return;
else if(xdata)
p=p->lchild;
数据结构查找算法课程设计
存档编号。西安 课程设计说明书。设计题目 查找算法性能分析。2015年 01月07 日。一需求分析。1.1问题描述。查找又称检索,是指在某种数据结构中找出满足给定条件的元素。查找是一种十分有用的操作。而查找也有内外之分,若整个查找过程只在内存中进行称为内查找 若查找过程中需要访问外存,则称为外查找,...
数据结构课程设计
课程设计说明书 题目哈夫曼编码问题的设计和实现。课程名称数据结构课程设计。院 系 部 中心。专业。班级。学生姓名。学号。设计地点。指导教师。设计起止时间 2008 年6月 2日至 2008 年 6月 6 日。目录。1 问题描述 2 1.1 题目内容 2 1.2 基本要求 2 1.3 测试数据 2 2...
数据结构课程设计
数据结构 课程设计。实验报告。学院 信息工程学院。班级 姓名 学号 指导老师 题目2 一元多项式的计算。1 实验目的。1 掌握链表的灵活运用 2 学习链表初始化和建立一个新的链表 3 知道怎样去实现链表删除结点操作与插入结点 4 理解链表的基本操作 包括数据域数据的相加 并能灵活运用。2 实验内容。...