存档编号。
西安***课程设计说明书。
设计题目：查找算法性能分析。
2023年 01月07 日。
一需求分析。
1. 1问题描述。
查找又称检索，是指在某种数据结构中找出满足给定条件的元素。查找是一种十分有用的操作。而查找也有内外之分，若整个查找过程只在内存中进行称为内查找；若查找过程中需要访问外存，则称为外查找，若在查找的同时对表做修改运算（插入或删除），则相应的表成为动态查找表，反之称为静态查找表。
由于查找运算的主要运算是关键字的比较，所以通常把查找过程中对关键字的平均比较次数（也叫平均查找长度）作为一个查找算法效率优劣的标准。平均查找程度asl定义为：
asl=∑pici（i从1到n）
其中pi代表查找第i个元素的概率，一般认为每个元素的查找概率相等，ci代表找到第i个元素所需要比较的次数。
查找算法有顺序查找、折半查找、索引查找、二叉树查找和散列查找（又叫哈希查找），它们的性能各有千秋，对数据的存储结构要求也不同，譬如在顺序查找中对表的结果没有严格的要求，无论用顺序表或链式表存储元素都可以查找成功；折半查找要求则是需要顺序表；索引表则需要建立索引表；动态查找需要的树表查找则需要建立建立相应的二叉树链表；哈希查找相应的需要建立一个哈希表。
1. 2基本要求。
1） 输入的形式和输入值的范围；
在设计查找算法性能分析的过程中，我们调用产生随机数函数：
srand((int)time(0));
产生n个随机数。
注：折半查找中需要对产生的随机数进行排序，需要进行排序后再进行输入，n<50;
2） 输出形式；
查找算法分析过程中，只要对查找算法稍作修改就可以利用平均查找长度的公式：
asl=∑pici（i从1到n）
输出各种查找算法的平均查找长度。
注：平均查找长度=总的平均查找长度/n；
3） 程序所能达到的功能。
通过输出几种查找算法的asl，我们很显然能得在数据量较小时（n<100）我们在实现静态查找时应该选择如何调用哪种查找算法。
二概要设计。
说明本程序中用到的所有抽象数据类型的定义。主程序的流程以及各程序模块之间的层次(调用)关系。
1、 数据结构。
顺序查找：在进行顺序查找顺序表类型定时需要定义typedef int keytype；
顺序表类型为seqlist类型。 typedef nodetype seqlist【maxsize】；/
它的基本思路是：从表的一端开始，顺序扫描线性表，依次将扫描到的关键字和给定值k相比较，若当前扫描到的关键字与k相等，查找成功。
折半查找：在进行顺序查找顺序表类型定时需要定义typedef int keytype，并且需要调用排序函数对其进行排序。
折半查找类型为seqlist类型。 typedef nodetype seqlist【maxsize】；
折半查找又叫二分查找，效率较高，但折半查找要求被查找的表示顺序表，它的基本思路是：设r【low…..high】是当前的查找区间，首先确定该区间的中点位置mid= ┖low+high）/2 ┘，然后将待查的k值与r【mid】.
key。
1 如果中点值的值是k，返回该元素的逻辑符号；
2 如果中点值》k，则中点值之后的数都大于k，所以k值在该表的左边，所以确定一个新的查找区间；
3 如果中点值4 依次循环。
索引查找：/索引存储结构是在存储数据的同时还建立附加的索引表，索引表包括关键字和地址。索引表的数据类型 keytype key、int link，link代表对应块的起始下标。
typedef idxtype idx[maxsize] /索引表的类型。
分块查找又称索引顺序查找，它的性能介于顺序查找和折半查找之间的一种算法，它的分块的思想是：
1 将表均分成b块，前b-1块中的关键字个数为s=┏n/b┐；
2 每一块的关键字不一定有序，但前一块中的最大关键字必须小于后一块中的最小关键字；
3 取各块中最大的关键字及该块在r中的起始位置。
注：索引表是一个递增有序表。
分块查找的基本思路是：
1 首先查找索引表，因为索引表是有序表，所以可以采用折半查找或者顺序查找，来确定待查元素在哪一块；
2 再已确定的块中进行顺序查找（因为块内元素无序，所以只能用顺序查找）
列：设有一个线性表采用顺序存储，有20个元素，将其分成4（b=4）部分，每部分有5个元素（s=5），该索引表的存储结构如下图所示：
在如图所示的存储结构中，查找关键字k=80时，首先将k和索引表中个关键字比较，直到找到大于等于k的值，因此若关键字k=80存在则必定在第四块中，由 idx[3].link找到起始地址15，从该地址开始在r【15…19】中进行查找，直到找到关r【8】.key=k为止，如果查找不成功说明不存在关键字k=80。
二叉树查找：
线性表可以有三种查找法，其中折半查找的效率最高，但是折半查找要求元素时顺序表，而且不能用链式存储结构，因此有表的插入或删除操作时，需要移动大量元素，这时候二叉树查找的优势就体现出来了。即动态查找时就需要用到链式存储结构。
二叉排序树（bst）又称二叉查找树，其定义为：二叉排序树或者是空树，或者是满足如下性质的二叉树：
1 若它的左孩子非空，则左子树上的所有元素的值均小于根元素的值；
2 若它的右孩子非空，则左子树上的所有元素的值均大于根元素的值；
3 左右子树本身是一颗二叉树。
重要性质：中序遍历二叉排序树所得到中序序列是以一个递增有序序列。
二叉排序树算法思想：它可以看做是一个有序表，所以在二叉树上查找，和折半查找类似，也是一个逐步缩小查找范围的过程，运用递归查找算法searchbst（）。
哈希表查找：
在用哈希表查找时先建立一个哈希表，哈希表主要用于快速查找，哈希表的查找过程和建表过程类似。
它的算法是：
1 设给定的值为k，根据建表时设定的散列函数h（k）计算哈希地址；
2 存储的个数为n，设置一个长度为m（m>n）的连续内存单元，以线性表中的每个对象ki为自变量，通过h（k）把ki映射为内存单元的地址，并把该对象存储字这个内存单元中。
哈希函数的构造有直接定址法、除留余数法和数字分析法，常用的是除留余数法，它是用关键字k除以某个不大于哈希表长度m的数p，将所得到的余数作为哈希地址。除留余数法的哈希函数h（k）：
h（k）=k mod p（mod为取余运算，p<=m）
2、 程序模块。
顺序查找：int seqsearch(seqlist r,int n,keytype k) /函数的返回值是整型，有三个参数分别是顺序表seqlist、元素个数n和需要查找的关键字k*/
int i=0;
while (i i++;
if(i>=n) /未找到返回0/*
return 0;
elsereturn i+1; /找到时返回逻辑符号i+1*/
折半查找：int binsearch(seqlist r,int n,keytype k)/*函数的返回值是整型，有三个参数分别是顺序表seqlist、元素个数n和需要查找的关键字*/
int low=0,high=n-1,mid;
int count=0;
while(low<=high) /当前区域存在元素时循环*/
索引查找：int idxsearch(idx i,int b,seqlist r,int n,keytype k) /索引查找函数值返回的是整型，函数有五个参数，分别是索引表i、分的块数b、顺序表r、关键字个数和关键字*/
int low=0,high=b-1,mid,i,count=0;
int s=n/bs为每块的元素个数，应为n/b的向上取整*/
while(low<=high) /索引表中进行折半查找、找到的位置为high+1*/
* 应在索引表的high+1中，再在对应的线性表中进行顺序查找*/
i=i[high+1].link;
while(i<=i[high+1].link+s-1&&r[i].key!=k)
if(i<=i[high+1].link+s-1) /查找成功*/
return count+1;
int searchbst(bstnode *bt,keytype k) /二叉排序树查找函数的返回值是bstnode类型，函数有两个参数分别是二叉排序树bt和关键字k*/
数据结构课程设计 查找
数据结构。课程设计报告。设计题目 查找。专业 计算机科技。院系 计算机学院。姓名 xx xx 学号 xxxxxxxxx 时间 2013年10月7日。目录。一实践目的与要求 2 1.1实践目的 2 1.2实践要求 2 二顺序查找的分析 程序 及运行结果 2 2.1系统简介 2 2.2 设计思路 2 2...
数据结构课程设计 排序算法
排序算法。1 需求分析。输入部分 要求用户能从屏幕上格式化输入元素个数。系统将自动生成用户输入的元素个数，存储 性表list中。要求用户选择用插入排序 冒泡排序 选择排序及快速排序中的一种，然后程序根据用户的选择对线性表list从小到大进行排序。最终，输出排序结果。1.1插入排序。思路 设有一组关键...
算法与数据结构课程设计
编号 120 说明书。进销存货物管理系统。学院 计算机科学与工程学院 专业 计算机科学与技术 学生姓名。学号。指导教师。2016年 6 月 26 日。摘要。本课程设计报告系统地阐述了我使用c 编写的进销存货物管理系统。首先，我对系统进行一个简要的概述。然后，我就系统的需求进行了详细的分析，这是设计工...