数据结构课程设计 查找

发布 2022-10-05 02:26:28 阅读 7005

数据结构。

课程设计报告。

设计题目:查找。

专业:计算机科技。

院系:计算机学院。

姓名: 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 实验内容。...