实验12：顺序查找实验

实验名称：查找算法性能分析实验目的：比较不同查找算法的效率，并分析其性能。

实验时间：2022年3月15日实验地点：计算机实验室实验器材：计算机、实验软件一、实验背景随着计算机技术的发展，数据量越来越大，查找算法在数据处理中的应用越来越广泛。

查找算法的效率直接影响到数据处理的速度，因此研究不同查找算法的性能具有重要意义。

本实验旨在比较几种常见的查找算法的效率，并分析其性能。

二、实验内容1. 算法介绍（1）顺序查找顺序查找是一种最简单的查找方法，其基本思想是从线性表的第一个元素开始，依次将线性表中的元素与要查找的元素进行比较，直到找到目标元素或者查找结束。

（2）二分查找二分查找是一种效率较高的查找方法，其基本思想是将待查找的序列分为两半，每次将中间位置的元素与要查找的元素进行比较，如果相等，则查找成功；如果中间位置的元素大于要查找的元素，则将查找范围缩小到左半部分；如果中间位置的元素小于要查找的元素，则将查找范围缩小到右半部分。

重复此过程，直到找到目标元素或者查找结束。

（3）散列查找散列查找是一种基于散列函数的查找方法，其基本思想是将要查找的元素通过散列函数映射到散列表中的一个位置，然后直接访问该位置，如果找到目标元素，则查找成功；如果未找到，则查找失败。

2. 实验步骤（1）生成随机数据使用实验软件生成一组随机数据，包括顺序查找和二分查找的数据。

（2）编写查找算法根据上述算法介绍，编写顺序查找、二分查找和散列查找的代码。

（3）测试算法性能分别对三种查找算法进行测试，记录查找成功和失败的情况，统计查找成功和失败的平均时间。

三、实验结果与分析1. 顺序查找（1）查找成功实验结果显示，顺序查找在查找成功的情况下，平均查找时间为0.1秒。

（2）查找失败实验结果显示，顺序查找在查找失败的情况下，平均查找时间为0.2秒。

2. 二分查找（1）查找成功实验结果显示，二分查找在查找成功的情况下，平均查找时间为0.05秒。

数据结构查找算法实验报告关键信息项：1、实验目的2、实验环境3、实验原理4、实验内容5、实验步骤6、实验结果7、结果分析8、遇到的问题及解决方法9、总结与体会1、实验目的11 熟悉常见的数据结构查找算法，如顺序查找、二分查找、哈希查找等。

111 掌握不同查找算法的基本原理和实现方法。

112 通过实验比较不同查找算法的性能，分析其时间复杂度和空间复杂度。

113 培养运用数据结构和算法解决实际问题的能力。

2、实验环境21 操作系统：具体操作系统名称211 编程语言：具体编程语言名称212 开发工具：具体开发工具名称3、实验原理31 顺序查找顺序查找是从数据结构的一端开始，依次逐个比较给定的关键字与数据元素的关键字，直到找到相等的元素或者遍历完整个数据结构为止。

其时间复杂度为 O(n)。

32 二分查找二分查找要求数据结构是有序的。

通过不断将待查找区间缩小为原来的一半，直到找到目标元素或者确定目标元素不存在。

其时间复杂度为 O(log n)。

33 哈希查找哈希查找通过哈希函数将关键字映射到一个特定的位置，然后在该位置进行比较。

如果发生冲突，则通过解决冲突的方法来查找目标元素。

其平均时间复杂度接近O(1)，但在最坏情况下可能会退化为O(n)。

4、实验内容41 实现顺序查找算法，并对给定的无序数组进行查找操作。

411 实现二分查找算法，并对给定的有序数组进行查找操作。

412 实现哈希查找算法，并对给定的数据集进行查找操作。

413 对不同规模的数据集，分别使用上述三种查找算法进行查找，并记录查找时间和比较次数。

5、实验步骤51 顺序查找算法实现511 定义顺序查找函数，接受数组和要查找的关键字作为参数。

512 从数组的第一个元素开始，逐个比较关键字与数组元素的关键字。

513 如果找到相等的元素，返回该元素的索引；如果遍历完数组都未找到，返回－1。

52 二分查找算法实现521 定义二分查找函数，接受有序数组、要查找的关键字以及数组的起始和结束索引作为参数。

一、实验目的1. 理解查找算法的基本原理和实现方法。

2. 掌握常用查找算法的优缺点。

3. 学会使用查找算法解决实际问题。

二、实验环境1. 操作系统：Windows 102. 编程语言：Python3.73. 开发工具：PyCharm三、实验内容1. 实现顺序查找算法。

2. 实现二分查找算法。

3. 实现哈希查找算法。

4. 对比分析三种查找算法的性能。

四、实验步骤1. 实现顺序查找算法（1）创建一个顺序查找函数，输入待查找数组和一个目标值，返回目标值在数组中的索引。

（2）编写主函数，生成一个随机数组，调用顺序查找函数，并打印结果。

2. 实现二分查找算法（1）创建一个二分查找函数，输入待查找数组、目标值和数组的起始和结束索引，返回目标值在数组中的索引。

（2）编写主函数，生成一个有序数组，调用二分查找函数，并打印结果。

3. 实现哈希查找算法（1）创建一个哈希函数，输入一个整数，返回其在哈希表中的索引。

（2）创建一个哈希表，初始化长度为10。

（3）创建一个哈希查找函数，输入待查找数组、目标值和哈希表，返回目标值在哈希表中的索引。

（4）编写主函数，生成一个随机数组，调用哈希查找函数，并打印结果。

4. 对比分析三种查找算法的性能（1）分别使用三种查找算法在随机数组、有序数组和哈希表中查找相同的元素，记录查找次数。

（2）分析查找次数与数组大小、数组元素数量和查找元素位置的关系。

五、实验结果与分析1. 顺序查找算法在随机数组中，查找次数与数组大小成正比，平均查找次数约为数组长度的倒数。

在有序数组和哈希表中，查找次数与数组大小无关，平均查找次数为1。

2. 二分查找算法在有序数组中，查找次数与数组大小成对数关系，平均查找次数约为log2(数组大小)。

在随机数组和哈希表中，查找次数与数组大小无关，平均查找次数为1。

3. 哈希查找算法在哈希表中，查找次数与数组大小无关，平均查找次数为1。

六、实验结论1. 顺序查找算法简单易实现，但查找效率较低，不适用于大数据量的查找。

实验五查找的应用一、实验目的：1、掌握各种查找方法及适用场合，并能在解决实际问题时灵活应用。

2、增强上机编程调试能力。

二、问题描述1.分别利用顺序查找和折半查找方法完成查找。

有序表（3,4,5,7,24,30,42,54,63,72,87,95）输入示例：请输入查找元素：52输出示例：顺序查找：第一次比较元素95第二次比较元素87 ……..查找成功，i=**/查找失败折半查找：第一次比较元素30第二次比较元素63 …..2.利用序列（12,7,17,11,16,2,13,9,21,4）建立二叉排序树，并完成指定元素的查询。

输入输出示例同题1的要求。

三、数据结构设计（选用的数据逻辑结构和存储结构实现形式说明）（1）逻辑结构设计顺序查找和折半查找采用线性表的结构，二叉排序树的查找则是建立一棵二叉树，采用的非线性逻辑结构。

（2）存储结构设计采用顺序存储的结构，开辟一块空间用于存放元素。

（3）存储结构形式说明分别建立查找关键字，顺序表数据和二叉树数据的结构体进行存储数据四、算法设计（1）算法列表（说明各个函数的名称，作用，完成什么操作）序号 名称 函数表示符 操作说明1 顺序查找 Search_Seq 在顺序表中顺序查找关键字的数据元素2 折半查找 Search_Bin 在顺序表中折半查找关键字的数据元素3 初始化 Init 对顺序表进行初始化，并输入元素4 树初始化 CreateBST 创建一棵二叉排序树5 插入 InsertBST 将输入元素插入到二叉排序树中6 查找 SearchBST在根指针所指二叉排序树中递归查找关键字数据元素 （2）各函数间调用关系（画出函数之间调用关系）typedef struct { ElemType *R; int length;}SSTable;typedef struct BSTNode{Elem data; //结点数据域 BSTNode *lchild,*rchild; //左右孩子指针}BSTNode,*BSTree; typedef struct Elem{ int key; }Elem;typedef struct {int key;//关键字域}ElemType;（3）算法描述int Search_Seq(SSTable ST, int key){//在顺序表ST中顺序查找其关键字等于key的数据元素。

查找排序实验报告一、实验目的本次实验的主要目的是深入理解和比较不同的查找和排序算法在性能和效率方面的差异。

通过实际编程实现和测试，掌握常见查找排序算法的原理和应用场景，为今后在实际编程中能够选择合适的算法解决问题提供实践经验。

二、实验环境本次实验使用的编程语言为 Python，开发环境为 PyCharm。

计算机配置为：处理器_____，内存_____，操作系统_____。

三、实验内容1、查找算法顺序查找二分查找2、排序算法冒泡排序插入排序选择排序快速排序四、算法原理1、顺序查找顺序查找是一种最简单的查找算法。

它从数组的一端开始，依次比较每个元素，直到找到目标元素或者遍历完整个数组。

其时间复杂度为 O(n)，在最坏情况下需要遍历整个数组。

2、二分查找二分查找适用于已排序的数组。

它通过不断将数组中间的元素与目标元素进行比较，将查找范围缩小为原来的一半，直到找到目标元素或者确定目标元素不存在。

其时间复杂度为 O(log n)，效率较高。

3、冒泡排序冒泡排序通过反复比较相邻的两个元素并交换它们的位置，将最大的元素逐步“浮”到数组的末尾。

每次遍历都能确定一个最大的元素，经过 n-1 次遍历完成排序。

其时间复杂度为 O(n^2)。

4、插入排序插入排序将数组分为已排序和未排序两部分，每次从未排序部分取出一个元素，插入到已排序部分的合适位置。

其时间复杂度在最坏情况下为 O(n^2)，但在接近有序的情况下性能较好。

5、选择排序选择排序每次从待排序数组中选择最小的元素，与当前位置的元素交换。

经过 n-1 次选择完成排序。

其时间复杂度为 O(n^2)。

6、快速排序快速排序采用分治的思想，选择一个基准元素，将数组分为小于基准和大于基准两部分，然后对这两部分分别递归排序。

其平均时间复杂度为 O(n log n)，在大多数情况下性能优异。

五、实验步骤1、算法实现使用Python 语言实现上述六种查找排序算法，并分别封装成函数，以便后续调用和测试。

查找算法实验报告查找算法实验报告一、引言查找算法是计算机科学中的一个重要概念，它在数据处理和信息检索中起着关键作用。

本实验旨在探究几种常见的查找算法，并对它们的性能进行比较和分析。

二、顺序查找算法顺序查找算法是最简单直观的一种查找方法，它逐个比较待查找元素与数据集中的元素，直到找到匹配项或遍历完整个数据集。

该算法的时间复杂度为O(n)，其中n为数据集的大小。

尽管顺序查找算法的效率较低，但在小规模数据集或无序数据集中仍然具有一定的应用价值。

三、二分查找算法二分查找算法是一种高效的查找算法，它要求数据集必须是有序的。

该算法通过将待查找元素与数据集的中间元素进行比较，从而将查找范围缩小一半。

如果中间元素与待查找元素相等，则查找成功；如果中间元素大于待查找元素，则在左半部分继续查找；如果中间元素小于待查找元素，则在右半部分继续查找。

通过不断缩小查找范围，二分查找算法的时间复杂度为O(log n)，其中n为数据集的大小。

二分查找算法在大规模有序数据集中具有较高的查找效率。

四、哈希查找算法哈希查找算法是一种基于哈希表的查找方法，它通过将待查找元素映射到哈希表中的一个位置，从而快速定位到目标元素。

哈希查找算法的时间复杂度为O(1)，即常数级别。

然而，哈希查找算法对哈希函数的选择和哈希冲突的处理有一定的要求。

如果哈希函数设计不合理或哈希冲突过多，可能会导致查找效率下降。

五、比较与分析在本实验中，我们对上述三种查找算法进行了性能比较和分析。

实验结果表明，在小规模数据集或无序数据集中，顺序查找算法的效率较高；而在大规模有序数据集中，二分查找算法的效率最高。

哈希查找算法虽然具有常数级别的时间复杂度，但在哈希函数和哈希冲突处理上需要额外的开销。

因此，在实际应用中，我们需要根据具体需求选择合适的查找算法。

六、实验总结通过本次实验，我们深入了解了查找算法的原理和应用。

顺序查找算法、二分查找算法和哈希查找算法各具特点，在不同场景下有不同的优劣势。

一、实验目的1. 理解索引顺序查找的基本原理。

2. 掌握索引顺序查找的实现方法。

3. 分析索引顺序查找的时间复杂度和效率。

二、实验原理索引顺序查找是一种基于索引的查找方法，它将数据分为两部分：索引和数据。

索引部分存储了数据中各个元素的位置信息，而数据部分则存储了实际的数据。

在查找过程中，首先通过索引找到目标元素的位置，然后再从数据部分中获取该元素。

索引顺序查找的基本步骤如下：1. 遍历索引，找到目标元素的位置。

2. 根据找到的位置，从数据部分获取目标元素。

三、实验环境1. 操作系统：Windows 102. 编程语言：Python3.83. 开发工具：PyCharm四、实验步骤1. 创建一个数据集，包括1000个随机整数。

2. 创建一个索引，记录每个元素在数据集中的位置。

3. 编写索引顺序查找函数。

4. 对数据集中的元素进行查找，并记录查找时间。

5. 分析查找结果，评估查找效率。

五、实验代码```pythonimport randomimport time# 创建数据集data_set = [random.randint(0, 10000) for _ in range(1000)]# 创建索引index = {data_set[i]: i for i in range(len(data_set))}# 索引顺序查找函数def index_search(data, target):if target in index:return index[target]else:return -1# 查找过程start_time = time.time()for target in data_set:index_search(data_set, target)end_time = time.time()# 输出查找时间print("查找时间：", end_time - start_time)```六、实验结果与分析1. 查找时间：实验结果显示，在数据集中进行1000次查找操作所需的时间为0.0009秒，平均每次查找所需时间为0.000009秒。

排序和查找的实验报告实验报告：排序和查找引言排序和查找是计算机科学中非常重要的基本算法。

排序算法用于将一组数据按照一定的顺序排列，而查找算法则用于在已排序的数据中寻找特定的元素。

本实验旨在比较不同排序和查找算法的性能，并分析它们的优缺点。

实验设计为了比较不同排序算法的性能，我们选择了常见的几种排序算法，包括冒泡排序、插入排序、选择排序、快速排序和归并排序。

我们使用相同的随机数据集对这些算法进行了测试，并记录了它们的执行时间和占用空间。

在查找算法的比较实验中，我们选择了顺序查找和二分查找两种常见的算法。

同样地，我们使用相同的随机数据集对这些算法进行了测试，并记录了它们的执行时间和占用空间。

实验结果在排序算法的比较实验中，我们发现快速排序和归并排序在大多数情况下表现最好，它们的平均执行时间和空间占用都要优于其他排序算法。

而冒泡排序和插入排序则表现较差，它们的执行时间和空间占用相对较高。

在查找算法的比较实验中，二分查找明显优于顺序查找，尤其是在数据规模较大时。

二分查找的平均执行时间远远小于顺序查找，并且占用的空间也更少。

结论通过本实验的比较，我们得出了一些结论。

首先，快速排序和归并排序是较优的排序算法，可以在大多数情况下获得较好的性能。

其次，二分查找是一种高效的查找算法，特别适用于已排序的数据集。

最后，我们也发现了一些排序和查找算法的局限性，比如冒泡排序和插入排序在大数据规模下性能较差。

总的来说，本实验为我们提供了对排序和查找算法性能的深入了解，同时也为我们在实际应用中选择合适的算法提供了一定的参考。

希望我们的实验结果能够对相关领域的研究和应用有所帮助。

数据结构查找实验报告数据结构查找实验报告1. 简介查找是计算机科学中一种常见的操作，它用于在一组数据中快速定位特定的元素。

数据结构是计算机存储、组织数据的方式，可以有效地支持查找操作。

本实验报告将介绍查找算法的原理和实现，以及实验结果的分析和总结。

2. 查找算法2.1 顺序查找顺序查找是一种简单直观的查找算法，它从数据集的第一个元素开始逐个比较，直至找到目标元素或遍历完所有元素。

顺序查找的时间复杂度为O(n)，其中n是数据集的大小。

2.2 二分查找二分查找是一种高效的查找算法，它要求数据集必须是有序的。

它通过将数据集分成两部分，并与目标元素进行比较，以确定目标元素所在的区间，然后在该区间内继续二分查找，直至找到目标元素或确定目标元素不存在。

二分查找的时间复杂度为O(log n)，其中n是数据集的大小。

2.3 插值查找插值查找是对二分查找的一种改进，它根据目标元素的估计位置来确定比较的起始位置。

它适用于数据集分布均匀的情况，可以进一步减少查找的次数。

插值查找的时间复杂度为O(log(log n))。

3. 实验结果本次实验我们使用了三种查找算法（顺序查找、二分查找和插值查找）在不同大小的数据集上进行了性能测试。

实验结果如下表所示：---- 数据集大小 ---- 顺序查找时间（ms） ---- 二分查找时间（ms） ---- 插值查找时间（ms） ---------------------------------------------------------------------------------------------- 1000 ---- 10 ---- 2 ---- 1 -------- 10000 ---- 100 ---- 4 ---- 2 -------- 100000 ---- 1000 ---- 6 ---- 3 -------- 1000000 ---- 10000 ---- 8 ---- 4 ----从实验结果可以看出，随着数据集的增大，顺序查找的时间成正比增加，而二分查找和插值查找的时间相对较稳定。

淮海工学院计算机科学系实验报告书课程名：《数据结构》题目：查找、排序的应用实验班级：软件112学号：2011122635姓名：排序、查找的应用实验报告要求1目的与要求:1）查找、排序是日常数据处理过程中经常要进行的操作和运算，掌握其算法与应用对于提高学生数据处理能力和综合应用能力显得十分重要。

2）本次实验前，要求同学完整理解有关排序和查找的相关算法和基本思想以及种算法使用的数据存储结构；3）利用C或C++语言独立完成本次实验内容或题目，程序具有良好的交互性（以菜单形式列出实验排序和显示命令，并可进行交互操作）和实用性；4）本次实验为实验成绩评定主要验收内容之一，希望同学们认真对待，并按时完成实验任务；5）本次实验为综合性实验，请于2012年12月23日按时提交实验报告（纸质报告每班10份）；6）下周开始数据结构课程设计，务必按时提交实验报告，任何同学不得拖延。

2 实验内容或题目题目：对记录序列（查找表）：{287，109，063，930，589，184，505，269,008，083}分别实现如下操作：1)分别使用直接插入排序、冒泡排序、快速排序、简单选择排序、堆排序（可选）、链式基数排序算法对纪录序列进行排序，并显示排序结果；2)对上述纪录列表排好序，然后对其进行折半查找或顺序查找；3 实验步骤与源程序#include "stdio.h"#include "stdlib.h"#define LIST_SIZE 20#define TRUE 1#define FALSE 0typedef int KeyType;typedef struct{KeyType key;}RecordType;typedef struct{RecordType r[LIST_SIZE+1];int length;}RecordList;void seqSearch(RecordList *l){KeyType k; int i;printf("请输出要查询的元素k:");fflush(stdin);scanf("%d",&k);i=l->length;while (i>=0&&l->r[i].key!=k)i--;printf("该元素的位置是");printf("%d",i+1);//cout<<"该元素在图中第"<<i<<"个位置"<<endl; printf("\n");}void BinSrch(RecordList *l){KeyType q;int mid;printf("请输入要查询的元素k:");fflush(stdin);scanf("%d",&q);int low=1;int high=l->length;while(low<=high){mid=(low+high)/2;if(q==l->r[mid].key){printf("该元素的位置为:");printf("%d",mid+1);//注意不能随便使用&printf("\n");break;}else if(q<l->r[mid].key)high=mid-1;elselow=mid+1;}}void inputkey(RecordList *l){int i;printf("请输入线性表长度:");//遇到错误：1.print用法scanf("%d",&(l->length));//&将变量的地址赋值，而不是变量的值for(i=1;i<=l->length ;i++){printf("请输入第%d个元素的值:",i);fflush(stdin);scanf("%d",&(l->r[i].key));}}void InsSort(RecordList *l){for(int i=2;i<=l->length;i++){l->r[0].key=l->r[i].key;int j=i-1;while(l->r[0].key<l->r[j].key){l->r[j+1].key=l->r[j].key;j=j-1;}l->r[j+1].key=l->r[0].key;}}//直接插入排序void BubbleSort(RecordList *l){int x,i,n,change,j;n=l->length;change=TRUE;for(i=1;i<=n-1&&change;++i){change=FALSE;for(j=1;j<=n-i;++j)if(l->r[j].key>l->r[j+1].key){x=l->r[j].key;l->r[j].key=l->r[j+1].key ;l->r[j+1].key=x;change=TRUE;}}}//冒泡排序法int QKPass(RecordList *l,int left,int right) {int x;x=l->r[left].key ;int low=left;int high=right;while(low<high){while(low<high&&l->r[high].key>=x)high--;if(low<high){l->r[low].key=l->r[high].key;low++;}while(low<high&&l->r[low].key<=x)low++;if(low<high){l->r[high].key=l->r[low].key;high--;}}l->r[low].key=x;return(low);}void QKSort(RecordList *l,int low,int high){int pos;if(low<high){pos=QKPass(l,low,high);QKSort(l,low,pos-1);QKSort(l,pos+1,high);}}//快速排序void SelectSort(RecordList *l){int n,i,k,j,x;n=l->length;for(i=1;i<=n-1;++i){k=i;for(j=i+1;j<=n;++j)if(l->r[j].key<l->r[k].key) k=j;if(k!=i){x=l->r[i].key;l->r[i].key=l->r[k].key;l->r[k].key=x;} }}void output(RecordList *l){for(int i=1;i<=l->length;i++){printf("%d",l->r[i].key);printf("\n");}}void main(){RecordList *l,*t,*m,*n;l=(RecordList *)malloc(sizeof(RecordList));int low;int high;int flag=1;int xuanze;while(flag!=0){printf("####################################################\n");printf("###### 请选择你要进行的操作! #########\n");printf("###### 1.直接插入排序; #########\n");printf("###### 2.冒泡排序; #########\n");printf("###### 3.快速排序; #########\n");printf("###### 4.简单选择排序; #########\n");printf("###### 5.顺序查找; #########\n");printf("###### 6.折半查找; #########\n");printf("###### 7.退出! #########\n");printf("####################################################\n");scanf("%d",&xuanze);switch(xuanze){case 1:inputkey(l);InsSort(l);printf("直接插入排序结果是:\n");output(l);break;case 2:inputkey(l);BubbleSort(l);printf("冒泡排序结果是:\n");output(l);break;case 3:inputkey(l);low=1;high=l->length;QKSort(l,low,high);printf("快速排序结果是:\n");output(l);break;case 4:inputkey(l);SelectSort(l);printf("简单选择排序结果是:\n");output(l);break;case 5:inputkey(l);InsSort(l);printf("排序结果是:\n");output(l);seqSearch(l);break;case 6:inputkey(l);InsSort(l);printf("排序结果是:\n");output(l);break;BinSrch(l);case 7:flag=0;break;}}}4 测试数据与实验结果（可以抓图粘贴）《数据结构》实验报告- 10 -5 结果分析与实验体会1.编程时要细心，避免不必要的错误；2.要先熟悉书本上的内容，否则编译会有困难；3.不能太过死板，要灵活运用所学知识。