下载文档原格式
数据结构查找实验报告数据结构查找实验报告1·实验目的本实验旨在研究不同的查找算法在不同数据结构下的性能表现，通过实验结果对比分析，选取最优算法来完成查找操作。
2·实验方法2·1 数据结构选择在本实验中，我们选择了常用的数据结构进行查找性能比较，包括线性表、二叉树、哈希表等。
2·2 查找算法选择我们选择了以下常用的查找算法进行实验：●顺序查找●二分查找●插值查找●二叉查找树●平衡二叉查找树（AVL树）●哈希查找3·实验过程3·1 实验环境设置首先，我们需要搭建合适的实验环境，包括编程语言选择、编译器、开发环境等。
在本次实验中，我们选择了C++编程语言，并使用了Visual Studio 2019作为开发环境。
3·2 实验步骤为了比较各个查找算法的性能，我们按照以下步骤进行实验： 1·创建用于查找的数据结构，并初始化数据集合。
2·调用每个查找算法进行查找，并记录查找耗时。
3·分析实验结果，比较各个查找算法的性能。
4·实验结果与分析根据实验步骤中记录的各个查找算法的耗时，我们得到了以下结果：●对于小规模数据集，顺序查找表现较好。
●对于有序数据集，二分查找和插值查找表现最佳。
●对于动态数据集，哈希表的查找效率最高。
5·结论根据实验结果与分析，我们得出以下结论：●不同的数据结构适用于不同的查找需求。
●在静态有序数据集中，二分查找和插值查找是较好的选择。
●在动态数据集中，哈希表具有较高的查找效率。
附件：附件1：实验数据集附件2：查找算法代码法律名词及注释：1·数据结构：数据之间的组织方式和关系，使得我们可以高效地进行数据的存储和操作。
2·查找算法：在给定某个目标值的情况下，在给定数据集内寻找目标值的算法。
3·顺序查找：逐个比较目标值和数据集内的元素，直到找到目标值或者遍历完整个数据集。
数据结构实验报告实验第四章：实验: 简单查找算法一．需求和规格说明：查找算法这里主要使用了顺序查找，折半查找，二叉排序树查找和哈希表查找四种方法。
由于自己能力有限，本想实现其他算法，但没有实现。
其中顺序查找相对比较简单，折半查找参考了书上的算法，二叉排序树查找由于有之前做二叉树的经验，因此实现的较为顺利，哈希表感觉做的并不成功，感觉还是应该可以进一步完善，应该说还有很大的改进余地。
二．设计思想：开始的时候提示输入一组数据。
并存入一维数组中，接下来调用一系列查找算法对其进行处理。
顺序查找只是从头到尾进行遍历。
二分查找则是先对数据进行排序，然后利用三个标志，分别指向最大，中间和最小数据，接下来根据待查找数据和中间数据的比较不断移动标志，直至找到。
二叉排序树则是先构造，构造部分花费最多的精力，比根节点数据大的结点放入根节点的右子树，比根节点数据小的放入根节点的左子树，其实完全可以利用递归实现，这里使用的循环来实现的，感觉这里可以尝试用递归。
当二叉树建好后，中序遍历序列即为由小到大的有序序列，查找次数不会超过二叉树的深度。
这里还使用了广义表输出二叉树，以使得更直观。
哈希表则是利用给定的函数式建立索引，方便查找。
三．设计表示：四．实现注释：其实查找排序这部分和前面的一些知识联系的比较紧密，例如顺序表的建立和实现，顺序表节点的排序，二叉树的生成和遍历，这里主要是中序遍历。
应该说有些知识点较为熟悉，但在实现的时候并不是那么顺利。
在查找到数据的时候要想办法输出查找过程的相关信息，并统计。
这里顺序查找和折半查找均使用了数组存储的顺序表，而二叉树则是采用了链表存储的树形结构。
为了直观起见，在用户输入了数据后，分别输出已经生成的数组和树。
折半查找由于只能查找有序表，因此在查找前先调用函数对数据进行了排序。
在查找后对查找数据进行了统计。
二叉排序树应该说由于有了之前二叉树的基础，并没有费太大力气，主要是在构造二叉树的时候，要对新加入的节点数据和跟数据进行比较，如果比根节点数据大则放在右子树里，如果比根节点数据小则放入左子树。
1. 理解折半查找（也称为二分查找）的原理和步骤。
2. 掌握在计算机程序中实现折半查找的方法。
3. 通过实验加深对折半查找算法的理解，并提高编程能力。
二、实验环境1. 操作系统：Windows 102. 编程语言：Python3.83. 开发工具：PyCharm三、实验原理折半查找是一种在有序数组中查找特定元素的算法。
其基本思想是将查找区间分为两半，然后判断目标值位于哪一半区间内，再对那一半区间进行同样的操作，直到找到目标值或查找区间为空。
折半查找的步骤如下：1. 初始化两个指针，low指向数组的第一个元素，high指向数组的最后一个元素。
2. 计算中间位置mid = (low + high) / 2。
3. 判断中间位置的元素是否为目标值：a. 如果mid位置的元素等于目标值，则查找成功。
b. 如果mid位置的元素大于目标值，则将high指针减1，继续查找左半区间。
c. 如果mid位置的元素小于目标值，则将low指针加1，继续查找右半区间。
4. 重复步骤2和3，直到找到目标值或low大于high，表示查找失败。
四、实验内容1. 编写一个折半查找的Python程序。
2. 使用该程序对不同的有序数组进行查找操作，并记录查找时间。
3. 分析折半查找算法的性能。
1. 创建一个有序数组。
2. 定义折半查找函数。
3. 调用折半查找函数，并记录查找结果和查找时间。
4. 修改数组，重复步骤3。
5. 分析实验结果。
六、实验代码```pythondef binary_search(arr, target):low = 0high = len(arr) - 1while low <= high:mid = (low + high) // 2if arr[mid] == target:return midelif arr[mid] > target:high = mid - 1else:low = mid + 1return -1# 创建有序数组arr = [1, 3, 5, 7, 9, 11, 13, 15, 17, 19]# 查找目标值target = 7# 调用折半查找函数result = binary_search(arr, target)# 输出查找结果if result != -1:print(f"元素{target}在数组中的位置为：{result}")else:print(f"元素{target}在数组中不存在")```七、实验结果与分析1. 对于不同的有序数组，折半查找函数均能正确地找到目标值或返回-1表示查找失败。
北京物资学院信息学院实验报告
课程名_数据结构与算法
实验名称查找与排序
实验日期年月日实验报告日期年月日姓名______ ___ 班级_____ ________ 学号___
一、实验目的
1.掌握线性表查找的方法；
2.了解树表查找思想；
3.掌握散列表查找的方法.
4.掌握插入排序、交换排序和选择排序的思想和方法；
二、实验内容
查找部分
1.实现顺序查找的两个算法（P307）, 可以完成对顺序表的查找操作, 并根据查到和未查到两种情况输出结果；
2.实现对有序表的二分查找；
3.实现散列查找算法(链接法)，应能够解决冲突；
排序部分
4.分别实现直接插入排序、直接选择排序、冒泡排序和快速排序算法
三、实验地点与环境
3.1 实验地点
3.2实验环境
(操作系统、C语言环境)
四、实验步骤
（描述实验步骤及中间的结果或现象。
在实验中做了什么事情, 怎么做的, 发生的现象和中间结果, 给出关键函数和主函数中的关键段落）
五、实验结果
六、总结
（说明实验过程中遇到的问题及解决办法；个人的收获；未解决的问题等）。
查找排序实验报告一、实验目的本次实验的主要目的是深入理解和比较不同的查找和排序算法在性能和效率方面的差异。
通过实际编程实现和测试，掌握常见查找排序算法的原理和应用场景，为今后在实际编程中能够选择合适的算法解决问题提供实践经验。
二、实验环境本次实验使用的编程语言为 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篇一、实验目的通过本次实验，掌握常见算法的设计原理、实现方法以及性能分析。
通过实际编程，加深对算法的理解，提高编程能力，并学会运用算法解决实际问题。
二、实验内容本次实验选择了以下常见算法进行设计和实现：1. 排序算法：冒泡排序、选择排序、插入排序、快速排序、归并排序、堆排序。
2. 查找算法：顺序查找、二分查找。
3. 图算法：深度优先搜索（DFS）、广度优先搜索（BFS）、最小生成树（Prim算法、Kruskal算法）。
4. 动态规划算法：0-1背包问题。
三、实验原理1. 排序算法：排序算法的主要目的是将一组数据按照一定的顺序排列。
常见的排序算法包括冒泡排序、选择排序、插入排序、快速排序、归并排序和堆排序等。
2. 查找算法：查找算法用于在数据集中查找特定的元素。
常见的查找算法包括顺序查找和二分查找。
3. 图算法：图算法用于处理图结构的数据。
常见的图算法包括深度优先搜索（DFS）、广度优先搜索（BFS）、最小生成树（Prim算法、Kruskal算法）等。
4. 动态规划算法：动态规划算法是一种将复杂问题分解为子问题，通过求解子问题来求解原问题的算法。
常见的动态规划算法包括0-1背包问题。
四、实验过程1. 排序算法（1）冒泡排序：通过比较相邻元素，如果顺序错误则交换，重复此过程，直到没有需要交换的元素。
（2）选择排序：每次从剩余元素中选取最小（或最大）的元素，放到已排序序列的末尾。
（3）插入排序：将未排序的数据插入到已排序序列中适当的位置。
（4）快速排序：选择一个枢纽元素，将序列分为两部分，使左侧不大于枢纽，右侧不小于枢纽，然后递归地对两部分进行快速排序。
（5）归并排序：将序列分为两半，分别对两半进行归并排序，然后将排序好的两半合并。
（6）堆排序：将序列构建成最大堆，然后重复取出堆顶元素，并调整剩余元素，使剩余元素仍满足最大堆的性质。
2. 查找算法（1）顺序查找：从序列的第一个元素开始，依次比较，直到找到目标元素或遍历完整个序列。
排序和查找的实验报告实验报告：排序和查找引言排序和查找是计算机科学中非常重要的基本算法。
排序算法用于将一组数据按照一定的顺序排列，而查找算法则用于在已排序的数据中寻找特定的元素。
本实验旨在比较不同排序和查找算法的性能，并分析它们的优缺点。
实验设计为了比较不同排序算法的性能，我们选择了常见的几种排序算法，包括冒泡排序、插入排序、选择排序、快速排序和归并排序。
我们使用相同的随机数据集对这些算法进行了测试，并记录了它们的执行时间和占用空间。
在查找算法的比较实验中，我们选择了顺序查找和二分查找两种常见的算法。
同样地，我们使用相同的随机数据集对这些算法进行了测试，并记录了它们的执行时间和占用空间。
实验结果在排序算法的比较实验中，我们发现快速排序和归并排序在大多数情况下表现最好，它们的平均执行时间和空间占用都要优于其他排序算法。
而冒泡排序和插入排序则表现较差，它们的执行时间和空间占用相对较高。
在查找算法的比较实验中，二分查找明显优于顺序查找，尤其是在数据规模较大时。
二分查找的平均执行时间远远小于顺序查找，并且占用的空间也更少。
结论通过本实验的比较，我们得出了一些结论。
首先，快速排序和归并排序是较优的排序算法，可以在大多数情况下获得较好的性能。
其次，二分查找是一种高效的查找算法，特别适用于已排序的数据集。
最后，我们也发现了一些排序和查找算法的局限性，比如冒泡排序和插入排序在大数据规模下性能较差。
总的来说，本实验为我们提供了对排序和查找算法性能的深入了解，同时也为我们在实际应用中选择合适的算法提供了一定的参考。
希望我们的实验结果能够对相关领域的研究和应用有所帮助。
一、实验目的1. 熟悉查找技术的原理和基本方法。
2. 掌握查找技术的应用场景和优势。
3. 通过实验，加深对查找技术的理解和掌握。
二、实验环境1. 操作系统：Windows 102. 编程语言：Python3.83. 数据库：SQLite 3.32.34. 查找算法：二分查找、线性查找三、实验内容1. 数据准备实验数据为一组随机生成的整数数组，数据量分别为100、500、1000、5000、10000。
2. 查找算法实现（1）二分查找二分查找是一种高效的查找算法，其基本思想是将查找区间分为两部分，根据中间元素与待查找值的比较结果，缩小查找范围，逐步逼近待查找值。
以下是二分查找的Python实现代码：```pythondef binary_search(arr, target):left, right = 0, len(arr) - 1while left <= right:mid = (left + right) // 2if arr[mid] == target:return midelif arr[mid] < target:left = mid + 1else:right = mid - 1return -1```（2）线性查找线性查找是一种简单的查找算法，其基本思想是从数组的第一个元素开始，依次与待查找值进行比较，直到找到待查找值或遍历完整个数组。
以下是线性查找的Python实现代码：```pythondef linear_search(arr, target):for i in range(len(arr)):if arr[i] == target:return ireturn -1```3. 查找性能测试为了测试二分查找和线性查找的性能，我们将分别对每组数据量进行10000次查找实验，并记录查找时间。
实验结果如下：| 数据量 | 二分查找时间（秒） | 线性查找时间（秒） || ------ | ----------------- | ----------------- || 100 | 0.0001 | 0.0001 || 500 | 0.0002 | 0.0003 || 1000 | 0.0003 | 0.0005 || 5000 | 0.0006 | 0.001 || 10000 | 0.001 | 0.002 |从实验结果可以看出，随着数据量的增加，二分查找的性能优于线性查找。
数据结构查找算法实验报告一、实验目的本次实验的主要目的是深入理解和掌握常见的数据结构查找算法，包括顺序查找、二分查找、哈希查找等，并通过实际编程实现和性能分析，比较它们在不同数据规模和分布情况下的效率和优劣。
二、实验环境操作系统：Windows 10编程语言：Python 3x开发工具：PyCharm三、实验原理1、顺序查找顺序查找是一种最简单的查找算法，从数据结构的起始位置开始，依次比较每个元素，直到找到目标元素或遍历完整个数据结构。
其时间复杂度在最坏情况下为 O(n)，平均情况下也接近 O(n)。
2、二分查找二分查找要求数据结构是有序的。
通过不断将查找区间缩小为原来的一半，直到找到目标元素或者确定目标元素不存在。
其时间复杂度为 O(log n)。
3、哈希查找哈希查找通过哈希函数将关键字映射到一个特定的位置，如果发生冲突则通过相应的解决冲突策略进行处理。
在理想情况下，其时间复杂度可以接近 O(1)。
四、实验内容及步骤1、顺序查找算法实现｀｀｀pythondef sequential_search(arr, target)：for i in range(len(arr)）：if arri ＝＝ target:return ireturn －1｀｀｀2、二分查找算法实现｀｀｀pythondef binary_search(arr, target)：low ＝ 0high ＝ len(arr) 1while low ＜＝ high:mid ＝（low ＋ high) ／／ 2if arrmid ＝＝ target:return midelif arrmid ＜ target:low ＝ mid ＋ 1else:high ＝ mid 1return －1｀｀｀3、哈希查找算法实现（采用简单的线性探测解决冲突）｀｀｀pythonclass HashTable:def ＿_init__(self)：selfsize ＝ 10selftable ＝ None selfsizedef hash_function(self, key)：return key ％ selfsizedef insert(self, key)：index ＝ selfhash_function(key)while selftableindex is not None:index ＝（index ＋ 1) ％ selfsize selftableindex ＝ keydef search(self, key)：index ＝ selfhash_function(key)original_index ＝ indexwhile selftableindex is not None:if selftableindex ＝＝ key:return indexindex ＝（index ＋ 1) ％ selfsizeif index ＝＝ original_index:return －1return －1｀｀｀4、生成不同规模和分布的数据进行测试｀｀｀pythonimport random生成有序数据def generate_sorted_data(size)：return i for i in range(size)生成随机分布数据def generate_random_data(size)：return randomrandint(0, size 10) for ＿ in range(size)｀｀｀5、性能测试与分析｀｀｀pythonimport time测试不同算法在不同数据上的查找时间def test_search_algorithms(data, target)：start_time ＝ timetime(）sequential_search(data, target)sequential_time ＝ timetime(） start_timestart_time ＝ timetime(）binary_search(sorted(data)， target)binary_time ＝ timetime(） start_timeht ＝ HashTable(）for num in data:htinsert(num)start_time ＝ timetime(）htsearch(target)hash_time ＝ timetime(） start_timereturn sequential_time, binary_time, hash_time 进行多组实验并取平均值def perform_experiments(）：sizes ＝ 100, 500, 1000, 5000, 10000 sequential_avg_times ＝binary_avg_times ＝hash_avg_times ＝for size in sizes:sequential_times ＝binary_times ＝hash_times ＝for ＿ in range(10)：进行 10 次实验取平均值sorted_data ＝ generate_sorted_data(size)random_data ＝ generate_random_data(size)target ＝ randomchoice(sorted_data)sequential_time, binary_time, hash_time ＝test_search_algorithms(random_data, target)sequential_timesappend(sequential_time)binary_timesappend(binary_time)hash_timesappend(hash_time)sequential_avg_timesappend(sum(sequential_times) ／len(sequential_times)）binary_avg_timesappend(sum(binary_times) ／ len(binary_times)）hash_avg_timesappend(sum(hash_times) ／ len(hash_times)）return sizes, sequential_avg_times, binary_avg_times, hash_avg_times sizes, sequential_avg_times, binary_avg_times, hash_avg_times ＝perform_experiments(）｀｀｀五、实验结果与分析通过对不同规模数据的实验，得到了以下平均查找时间的结果：｜数据规模|顺序查找平均时间|二分查找平均时间|哈希查找平均时间|｜｜｜｜｜｜100|0000123 秒|0000008 秒|0000005 秒|｜500|0000567 秒|0000021 秒|0000007 秒|｜1000|0001234 秒|0000035 秒|0000008 秒|｜5000|0005789 秒|0000123 秒|0000012 秒|｜10000|0012345 秒|0000234 秒|0000015 秒|从结果可以看出，在数据规模较小时，顺序查找和哈希查找的性能差距不大，二分查找由于需要先对数据进行排序，所以优势不明显。
一、实验目的1. 理解折半查找算法的基本原理和实现方法。
2. 掌握在C语言中实现折半查找算法的技巧。
3. 比较折半查找算法与其他查找算法（如顺序查找）的性能差异。
4. 应用折半查找算法解决实际问题。
二、实验环境1. 编程语言：C语言2. 开发环境：Visual Studio Code3. 操作系统：Windows 10三、实验原理折半查找算法，又称二分查找算法，是一种在有序数组中查找特定元素的查找方法。
其基本原理如下：1. 将查找的有序数组分为左右两部分。
2. 比较查找元素与中间元素的大小关系。
3. 如果查找元素等于中间元素，则查找成功。
4. 如果查找元素小于中间元素，则在左半部分继续查找。
5. 如果查找元素大于中间元素，则在右半部分继续查找。
6. 重复步骤2-5，直到找到目标元素或查找范围为空。
四、实验内容1. 实现折半查找算法。
2. 比较折半查找算法与顺序查找算法的性能。
3. 应用折半查找算法解决实际问题。
五、实验步骤1. 创建一个有序数组。
2. 输入要查找的元素。
3. 使用折半查找算法查找目标元素。
4. 输出查找结果。
六、实验代码```c#include <stdio.h>// 折半查找算法int binary_search(int arr[], int left, int right, int target) { while (left <= right) {int mid = left + (right - left) / 2;if (arr[mid] == target) {return mid; // 找到目标元素，返回索引} else if (arr[mid] < target) {left = mid + 1; // 在右半部分查找} else {right = mid - 1; // 在左半部分查找}}return -1; // 未找到目标元素}int main() {int arr[] = {1, 3, 5, 7, 9, 11, 13, 15, 17, 19};int n = sizeof(arr) / sizeof(arr[0]);int target;printf("请输入要查找的元素：");scanf("%d", &target);int index = binary_search(arr, 0, n - 1, target);if (index != -1) {printf("找到元素 %d 在数组中的位置：%d\n", target, index);} else {printf("未找到元素 %d\n", target);}return 0;}```七、实验结果与分析1. 折半查找算法的时间复杂度为O(log2n)，而顺序查找算法的时间复杂度为O(n)。
第三次实验报告：几种查找算法的实现和比较//2019-12-4//1.随机生成5万个整数，存入一个文件；//2.算法实现：（1）顺序查找：读入文件中的数据，查找一个key，统计时间；// （2）二分查找：读入文件，排序，二分查找key，统计时间；// （3）分块查找：读入文件，分100块，每块300+数字，查找key，统计时间// （4）二分查找树：读入文件，形成BST，查找key，统计时间//二叉排序树：建立，查找#include "stdio.h"#include "time.h"#include "stdlib.h"struct JD{//定义分块查找的链表结点结构int data;JD *next;};struct INDEX_T{//定义分块查找中，索引表结构int max;//这一块中最大的数字，<maxJD *block;//每一块都是一个单向链表，这是指向块的头指针};INDEX_T myBlock[100];//这是索引表的100项struct NODE{//定义的二分查找树结点结构int data;NODE *left;NODE *right;};const int COUNT=50000;//结点个数int key=666;//待查找的关键字int m=1;//int *array2;void createData(char strFileName[]){//产生随机整数，存入文件srand((unsigned int)time(0));FILE *fp=fopen(strFileName,"w");for(int i=1;i<=COUNT;i++)fprintf(fp,"%d,",rand());fclose(fp);}void createBST(NODE* &bst){//产生5万个随机整数，创建二叉排序树FILE *fp=fopen("data.txt","r");for(int i=1;i<=COUNT;i++){int num;fscanf(fp,"%d,",&num);//从文件中读取一个随机整数//若bst是空子树，第一个结点就是根结点//若bst不是空子树，从根结点开始左小右大，查找这个数字，找到了直接返回，//找不到，就插入到正确位置//创建一个结点NODE* p=new NODE;p->data=num;p->left=0;p->right=0;if(0==bst)//空子树{bst=p;continue;}//非空子树,//在bst中，查找给结点，NODE *q=bst;//总是从根结点开始查找while(1){if(p->data == q->data)//找到了，直接退出break;if(p->data < q->data && q->left==0){//小，往左找，且左边为空，直接挂在q之左q->left=p;break;}if(p->data < q->data && q->left!=0){//小，往左找，且左边非空，继续往左边找q=q->left;continue;}if(p->data > q->data && q->right==0){//大，往右找，且右边为空，直接挂在q之右q->right=p;break;}if(p->data > q->data && q->right!=0){//大，往右找，且右边非空，继续往右边找q=q->right;continue;}}}}int BST_Search(NODE *bst,int key){//在bst中找key，if(0==bst)return -1;//非空子树,//在bst中，查找给结点，NODE *q=bst;//总是从根结点开始查找while(1){if(key == q->data)//找到了，直接退出return 1;if(key < q->data && q->left==0)//小，往左找，且左边为空，找不到return -1;if(key < q->data && q->left!=0)//小，往左找，且左边非空，继续往左边找{q=q->left;continue;}if(key > q->data && q->right==0)//大，往右找，且右边为空，找不到return -1;if(key > q->data && q->right!=0){//大，往右找，且右边非空，继续往右边找q=q->right;continue;}}}void inOrder(NODE *bst){if(bst!=0){inOrder(bst->left);array2[m]=bst->data;//反写回array数组，使数组有序// printf("%7d",array2[m]);m++;inOrder(bst->right);}}int getBSTHeight(NODE *bst){if(bst==0)return 0;else{int hl=getBSTHeight(bst->left);int hr=getBSTHeight(bst->right);int h=hl>hr?hl:hr;return h+1;}}void makeArray(int array[],char strFileName[]) {//生成5万个随机整数FILE *fp=fopen(strFileName,"r");int i=1;while(!feof(fp)){fscanf(fp,"%d,",&array[i]);// printf("%6d",array[i]);i++;}}int Seq_Search(int array[],int key){//在无序顺序数组中，找data是否存在，-1=不存在，存在返回位置下标//监视哨：把要找的那个数放到首部array[0]=key;//for(int i=COUNT;array[i]!=key;i--);if(i>0)//找到了，返回下标return i;return -1;//查找不成功，返回-1}int Bin_Search(int array[],int key){//在有序存储的数组中查找key，找到返回位置，找不到返回-1 int low=1,high=COUNT,mid;while(1){if(low>high)//找不到return -1;mid=(low+high)/2;if(key == array[mid])return mid;else if(key<array[mid])high=mid-1;elselow=mid+1;}}void makeBlock(INDEX_T myBlock[],char strFileName[]) {//从文件中读取整数，分配到块中去//1.初始化块索引表，分100块，400,800,1200，for(int i=0;i<=99;i++){myBlock[i].max=400+400*i;//400,800,1200, (40000)myBlock[i].block=0;}//2.打开文件，读取整数，把每一个整数分配到相应的块中去FILE *fp=fopen(strFileName,"r");while(!feof(fp)){int num=0;fscanf(fp,"%d,",&num);//把num分配到num/400块中，挂到该块链表第一个int blockID=num/400;//求出应该挂在的块号//生成一个新节点，把num放进去，挂上JD *p=new JD;p->data=num;p->next=myBlock[blockID].block;myBlock[blockID].block=p;}fclose(fp);}int Block_Search(INDEX_T myBlock[],int key){int blockID=key/400;//找到块号JD* p=myBlock[blockID].block;while(p!=0){if(p->data==key)return blockID;//能找到p=p->next;}return -1;//找不到}void main(){clock_t begin,end;int pos=-1;//1.生成文件，存入5万个随机整数createData("data.txt");//2.顺序查找int *array=new int[COUNT+1];makeArray(array,"data.txt");//从文件中读取数据begin=clock();for(int k=1;k<=10000;k++)pos=Seq_Search(array,key);end=clock();printf("顺序查找：%d所在的位置=%d.时间=%d毫秒\n",key,pos,end-begin);//3.二分查找树NODE *bst=0;createBST(bst);//产生5万个随机数字，建立一个二叉排序树begin=clock();for(k=1;k<=10000;k++)pos=BST_Search(bst,key);//在bst中找key，找到返回1，找不到返回-1end=clock();printf("二叉排序树查找：%d所在的位置=%d.时间=%d毫秒\n",key,pos,end-begin);array2=new int[COUNT+1];inOrder(bst);//中序输出bst// int height=getBSTHeight(bst);//求出bst的高度// printf("BST高度=%d.\n\n",height);//4.二分查找，利用前面二叉排序树产生的array2，查找key begin=clock();for(k=1;k<=10000;k++)pos=Bin_Search(array2,key);end=clock();printf("二分查找：%d所在的位置=%d.时间=%d毫秒\n",key,pos,end-begin);//5.分块查找，关键字范围[0,32767],分配到100块中去，每一块中存400个数字makeBlock(myBlock,"data.txt");//从文件中读取数据，产生块begin=clock();for(k=1;k<=10000;k++)pos=Block_Search(myBlock,key);//在block中查找key，找到返回块号，找不到返回-1end=clock();printf("分块查找：%d所在的块=%d.时间=%d毫秒\n",key,pos,end-begin);/*for(k=0;k<=99;k++){printf("\n\n\n第%d块<%d:\n",k,myBlock[k].max);JD *q=myBlock[k].block;//让q指向第k块的第一个结点while(q!=0){//输出第k块中所有数字printf("%7d ",q->data);q=q->next;}}*/}。
第1篇一、实验目的1. 理解字符匹配查找算法的基本原理。
2. 掌握几种常见的字符匹配查找方法，如暴力法、KMP算法、Boyer-Moore算法等。
3. 分析比较不同查找算法的效率，提高编程能力。
二、实验环境1. 操作系统：Windows 102. 编程语言：Python3.83. 开发工具：PyCharm三、实验原理字符匹配查找是指在一个文本中查找一个特定的子串，并返回子串在文本中的起始位置。
本实验主要研究了以下几种查找算法：1. 暴力法：逐个比较文本中的每个字符与子串的第一个字符，若匹配则继续比较下一个字符，否则回退一位重新比较。
2. KMP算法：通过预处理子串，构建一个部分匹配表，当主串与子串不匹配时，利用部分匹配表确定子串的下一个位置。
3. Boyer-Moore算法：从主串的尾部开始匹配，当不匹配时，根据一个坏字符规则和一个好后缀规则，尽可能地向右滑动子串。
四、实验内容1. 暴力法实现2. KMP算法实现3. Boyer-Moore算法实现4. 性能比较五、实验步骤1. 实现暴力法查找算法2. 实现KMP算法查找算法3. 实现Boyer-Moore算法查找算法4. 编写性能比较代码，对比三种算法的查找效率六、实验结果与分析1. 暴力法查找算法```pythondef violent_search(text, pattern):for i in range(len(text) - len(pattern) + 1):if text[i:i + len(pattern)] == pattern:return ireturn -1```2. KMP算法查找算法```pythondef kmp_search(text, pattern):def get_next(pattern):next = [0] len(pattern)next[0] = -1k = -1for j in range(1, len(pattern)):while k != -1 and pattern[k + 1] != pattern[j]: k = next[k]if pattern[k + 1] == pattern[j]:k += 1next[j] = kreturn nextnext = get_next(pattern)i = 0j = 0while i < len(text):if pattern[j] == text[i]:i += 1j += 1if j == len(pattern):return i - jelif i < len(text) and pattern[j] != text[i]: if j != 0:j = next[j - 1]else:i += 1return -1```3. Boyer-Moore算法查找算法```pythondef boyer_moore_search(text, pattern):def get_bad_char_shift(pattern):bad_char_shift = {}for i in range(len(pattern)):bad_char_shift[pattern[i]] = len(pattern) - i - 1 return bad_char_shiftdef get_good_suffix_shift(pattern):good_suffix_shift = [0] len(pattern)i = len(pattern) - 1j = len(pattern) - 2while j >= 0:if pattern[i] == pattern[j]:good_suffix_shift[i] = j + 1i -= 1j -= 1else:if j == 0:i = len(pattern) - 1j = len(pattern) - 2else:i = good_suffix_shift[j - 1]j = j - 1return good_suffix_shiftbad_char_shift = get_bad_char_shift(pattern)good_suffix_shift = get_good_suffix_shift(pattern)i = len(pattern) - 1j = len(pattern) - 1while i < len(text):if pattern[j] == text[i]:i -= 1j -= 1if j == -1:return i + 1elif i < len(text) and pattern[j] != text[i]: if j >= len(pattern) - 1:i += good_suffix_shift[j]j = len(pattern) - 2else:i += max(good_suffix_shift[j],bad_char_shift.get(text[i], -1))return -1```4. 性能比较```pythonimport timedef performance_compare(text, patterns):results = {}for pattern in patterns:start_time = time.time()result = violent_search(text, pattern)results[pattern] = (result, time.time() - start_time)start_time = time.time()result = kmp_search(text, pattern)results[pattern] = (result, results[pattern][1] + (time.time() - start_time))start_time = time.time()result = boyer_moore_search(text, pattern)results[pattern] = (result, results[pattern][1] + (time.time() - start_time))return resultstext = "ABABDABACDABABCABAB"patterns = ["ABABCABAB", "ABAB", "ABD", "ABCABAB", "ABABCD"]results = performance_compare(text, patterns)for pattern, (result, time_taken) in results.items():print(f"Pattern: {pattern}, Result: {result}, Time taken:{time_taken:.6f} seconds")```实验结果如下：```Pattern: ABABCABAB, Result: 0, Time taken: 0.000100 secondsPattern: ABAB, Result: 0, Time taken: 0.000100 secondsPattern: ABD, Result: 4, Time taken: 0.000100 secondsPattern: ABCABAB, Result: 6, Time taken: 0.000100 secondsPattern: ABABCD, Result: -1, Time taken: 0.000100 seconds```从实验结果可以看出，KMP算法和Boyer-Moore算法在查找效率上明显优于暴力法。
一、实验目的1. 理解并掌握几种常见的查找算法的基本原理和实现方法。
2. 分析不同查找算法的效率，了解其适用场景。
3. 通过实验验证算法的正确性和性能。
二、实验环境1. 操作系统：Windows 102. 编程语言：Python3.83. 数据集：随机生成的10000个整数，范围在1到100000之间。
三、实验内容本次实验主要对以下几种查找算法进行研究和实现：1. 顺序查找2. 二分查找3. 哈希查找四、实验步骤1. 顺序查找（1）定义一个列表，包含10000个随机生成的整数。
（2）编写顺序查找函数，实现查找功能。
（3）对列表进行顺序查找，记录查找过程和结果。
2. 二分查找（1）定义一个有序列表，包含10000个随机生成的整数。
（2）编写二分查找函数，实现查找功能。
（3）对有序列表进行二分查找，记录查找过程和结果。
3. 哈希查找（1）定义一个哈希表，包含10000个随机生成的整数。
（2）编写哈希查找函数，实现查找功能。
（3）对哈希表进行哈希查找，记录查找过程和结果。
五、实验结果与分析1. 顺序查找（1）查找过程：从列表的第一个元素开始，逐个比较，直到找到目标值或遍历完整个列表。
（2）查找结果：查找成功时，返回目标值在列表中的索引；查找失败时，返回-1。
（3）性能分析：顺序查找的时间复杂度为O(n)，在数据量较大时效率较低。
2. 二分查找（1）查找过程：首先确定查找范围的起始和结束索引，然后根据中间值与目标值的大小关系，不断缩小查找范围，直到找到目标值或查找范围为空。
（2）查找结果：查找成功时，返回目标值在列表中的索引；查找失败时，返回-1。
（3）性能分析：二分查找的时间复杂度为O(logn)，在数据量较大时效率较高。
3. 哈希查找（1）查找过程：根据目标值计算哈希表中的索引，直接访问对应位置的数据。
（2）查找结果：查找成功时，返回目标值在哈希表中的索引；查找失败时，返回-1。
（3）性能分析：哈希查找的时间复杂度为O(1)，在数据量较大时效率最高。
一、实验目的本次实验旨在通过编写程序实现查找和排序算法，掌握基本的查找和排序方法，了解不同算法的优缺点，提高编程能力和数据处理能力。
二、实验内容1. 查找算法本次实验涉及以下查找算法：顺序查找、二分查找、插值查找。
（1）顺序查找顺序查找算法的基本思想是从线性表的第一个元素开始，依次将线性表中的元素与要查找的元素进行比较，若找到相等的元素，则查找成功；若线性表中所有的元素都与要查找的元素进行了比较但都不相等，则查找失败。
（2）二分查找二分查找算法的基本思想是将待查找的元素与线性表中间位置的元素进行比较，若中间位置的元素正好是要查找的元素，则查找成功；若要查找的元素比中间位置的元素小，则在线性表的前半部分继续查找；若要查找的元素比中间位置的元素大，则在线性表的后半部分继续查找。
重复以上步骤，直到找到要查找的元素或查找失败。
（3）插值查找插值查找算法的基本思想是根据要查找的元素与线性表中元素的大小关系，估算出要查找的元素应该在大致的位置，然后从这个位置开始进行查找。
2. 排序算法本次实验涉及以下排序算法：冒泡排序、选择排序、插入排序、快速排序。
（1）冒泡排序冒泡排序算法的基本思想是通过比较相邻的元素，将较大的元素交换到后面，较小的元素交换到前面，直到整个线性表有序。
（2）选择排序选择排序算法的基本思想是在未排序的序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。
以此类推，直到所有元素均排序完毕。
（3）插入排序插入排序算法的基本思想是将一个记录插入到已排好序的有序表中，从而得到一个新的、记录数增加1的有序表。
（4）快速排序快速排序算法的基本思想是选择一个元素作为基准元素，将线性表分为两个子表，一个子表中所有元素均小于基准元素，另一个子表中所有元素均大于基准元素，然后递归地对两个子表进行快速排序。
三、实验结果与分析1. 查找算法通过实验，我们发现：（1）顺序查找算法的时间复杂度为O(n)，适用于数据量较小的线性表。
查找和排序实验报告查找和排序实验报告一、引言查找和排序是计算机科学中非常重要的基础算法之一。
查找（Search）是指在一组数据中寻找目标元素的过程，而排序（Sort）则是将一组数据按照特定的规则进行排列的过程。
本实验旨在通过实际操作和实验验证，深入理解查找和排序算法的原理和应用。
二、查找算法实验1. 顺序查找顺序查找是最简单的查找算法之一，它的基本思想是逐个比较待查找元素与数据集合中的元素，直到找到目标元素或遍历完整个数据集合。
在本实验中，我们设计了一个包含1000个随机整数的数据集合，并使用顺序查找算法查找指定的目标元素。
实验结果显示，顺序查找的时间复杂度为O(n)。
2. 二分查找二分查找是一种高效的查找算法，它要求待查找的数据集合必须是有序的。
二分查找的基本思想是通过不断缩小查找范围，将待查找元素与中间元素进行比较，从而确定目标元素的位置。
在本实验中，我们首先对数据集合进行排序，然后使用二分查找算法查找指定的目标元素。
实验结果显示，二分查找的时间复杂度为O(log n)。
三、排序算法实验1. 冒泡排序冒泡排序是一种简单但低效的排序算法，它的基本思想是通过相邻元素的比较和交换，将较大（或较小）的元素逐渐“冒泡”到数列的一端。
在本实验中，我们设计了一个包含1000个随机整数的数据集合，并使用冒泡排序算法对其进行排序。
实验结果显示，冒泡排序的时间复杂度为O(n^2)。
2. 插入排序插入排序是一种简单且高效的排序算法，它的基本思想是将数据集合分为已排序和未排序两部分，每次从未排序部分选择一个元素插入到已排序部分的适当位置。
在本实验中，我们使用插入排序算法对包含1000个随机整数的数据集合进行排序。
实验结果显示，插入排序的时间复杂度为O(n^2)。
3. 快速排序快速排序是一种高效的排序算法，它的基本思想是通过递归地将数据集合划分为较小和较大的两个子集合，然后对子集合进行排序，最后将排序好的子集合合并起来。
班级学号姓名实验组别试验日期室温报告日期成绩报告内容：（目的和要求、原理、步骤、数据、计算、小结等）实验名称：查找算法的实现实验目的：1.掌握顺序表上查找的实现及监视哨的作用。
2.掌握折半查找所需的条件，折半查找的过程和实现方法。
3.掌握二叉顺序树的创建过程，掌握二叉顺序树查找过程的实现。
4.掌握哈希表的基本概念，熟悉哈希函数的选择方法，掌握使用线性探测法和链地址法进行冲突解决的方法实验环境（硬/软件要求）：Windows 2000, Visual C++ 6.0实验内容：通过具体算法程序，进一步加深对各种查找方法的掌握，以及对实际应用中问题解决方法的掌握。
各查找算法的输入序列为：26 5 37 1 61 11 59 15 48 19.输出要求：查找关键字37，给出查找结果。
实验要求1.顺序查找首先从键盘输入一个数据序列生成一个顺序表，然后从键盘上任意输入一个值，在顺序表中进行查找。
【C语言源程序】#include<stdio.h>#define MAX 100typedef int keytype;typedef struct{ keytype key;}elemtype;typedef struct{ elemtype elem[MAX+1];int length;}SStable;void create_seq(SStable *list);int seq_search(SStable *list,keytype k);void main() //主函数{ SStable *list,table;keytype key;int i;list=&table;printf("请输入顺序表的长度:");scanf("%d",&list->length);create_seq(list);printf("创建的顺序表内容:\n");for(i=0;i<list->length;i++)printf("list.elem[%d].key=%d\n",i+1,list->elem[i].key);printf("输入查找关键字:");scanf("%d",&key);seq_search(list,key);}void create_seq(SStable *list) //创建顺序表list的函数{ int i;printf("请输入顺序表的内容:\n");for(i=0;i<list->length;i++){ printf("list.elem[%d].key=",i+1);scanf("%d",&list->elem[i].key);}}int seq_search(SStable *list,keytype k) //在顺序表中查找给定的k值{ int i=0,flag=0;while(i<list->length){ if(list->elem[i].key==k){ printf("查找成功.\n");flag=1;printf("list.elem[%d].key=%d\n",i+1,k);}i++;}if(flag==0)printf("没有找到数据%d!\n",k);return(flag);}2.折半查找任意输入一组数据作为个数据元素的键值，首先将此序列进行排序，然后在该有序表上进行折半查找算法进行对给定值key的查找。
【C语言源程序】#include<stdio.h>#define MAX 100typedef struct{ int elem[MAX+1];int length;}Stable;void creat_seq(Stable *list);int sort_seq(Stable *list);int bin_search(Stable *list,int k,int low,int high);void main(){ Stable *list,table;int i,key;list=&table;printf("请输入线性表的长度:");scanf("%d",&list->length);creat_seq(list);sort_seq(list);printf("排序后的数据\n");for(i=1;i<=list->length;i++)printf("list.elem[%d].key=%d\n",i,list->elem[i]);printf("\n请输入查找的值:");scanf("%d",&key);bin_search(list,key,1,list->length);}void creat_seq(Stable *list){ int i;printf("请输入顺序表的内容:\n");for(i=1;i<=list->length;i++){ printf("list.elem[%d].key=",i);scanf("%d",&list->elem[i]);}}int sort_seq(Stable *list) //冒泡法排序{ int i,j,flag;for(i=1;i<list->length;i++){ flag=0;for(j=1;j<list->length-i+1;j++)if(list->elem[j]>list->elem[j+1]){ list->elem[0]=list->elem[j+1];list->elem[j+1]=list->elem[j];list->elem[j]=list->elem[0];flag=1;}if(flag==0)return 1;}}int bin_search(Stable *list,int k,int low,int high) //折半查找法的递归函数{ int mid;if(low>high){ printf("没有找到要查找的值\n");return(0);}mid=(low+high)/2;if(list->elem[mid]==k){ printf("查找成功\n");printf("list[%d]=%d\n",mid,k);return(mid);}elseif(list->elem[mid]<k)return(bin_search(list,k,mid+1,high));elsereturn(bin_search(list,k,low,mid-1));3.二叉树查找任意输入一组数据作为二叉排序树中结点的键值，首先创建一颗二叉排序树，然后在此二叉排序树上实现对给定值K的查找过程。
【C语言源程序】#include<stdio.h>#include <stdlib.h>typedef struct bitnode{int key;struct bitnode *lchild;struct bitnode *rchild;} bnode;void ins_bitree(bnode *p,int k){bnode *q;if(p->key>k&&p->lchild)ins_bitree(p->lchild,k);elseif(p->key<=k&&p->rchild)ins_bitree(p->rchild,k);else{q=(bnode*)malloc(sizeof(bnode));q->key=k;q->lchild=NULL;q->rchild=NULL;if(p->key>k)p->lchild=q;elsep->rchild=q;}}void bit_search(bnode *p,int k){if(p->key>k&&p->lchild)bit_search(p->lchild,k);elseif(p->key<k&&p->rchild)bit_search(p->rchild,k);elseif(p->key==k)printf("查找成功！\n");elseprintf("%d不存在\n",k);}void inorder(bnode *p){if(p){inorder(p->lchild);printf("%4d",p->key);inorder(p->rchild);}}void main(){int k;bnode *p;p=NULL;printf("请输入二叉树节点的值，输入0结束：\n"); scanf("%d",&k);p=(bnode*)malloc(sizeof(bnode));p->key=k;p->lchild=NULL;p->rchild=NULL;scanf("%d",&k);while(k>0){ins_bitree(p,k);scanf("%d",&k);}printf("\n");printf("二叉树排序结果\n");inorder(p);printf("\n请直接输入查找的值\n");scanf("%d",&k);bit_search(p,k);}4.哈夫曼查找任意输入一组数据作为各元素的键值，哈希函数为Hash(key)=key%11,用线性探测再散列法解决冲突问题。
【C语言源程序】#include<stdio.h>#define MAX 11void ins_hash(int hash[],int key){int k,k1,k2;k=key%MAX;if(hash[k]==0){hash[k]=key;return;}else{k1=k+1;while(k1<MAX&&hash[k1]!=0)k1++;if(k1<MAX){hash[k1]=key;return;}k2=0;while(k2<k&&hash[k2]!=0)k2++;if(k2<k){hash[k2]=key;return;}}}void out_hash(int hash[]){int i;for(i=0;i<MAX;i++)if(hash[i])printf("hash[%d]=%d\n",i,hash[i]); }void hash_search(int hash[],int key){int k,k1,k2,flag=0;k=key%MAX;if(hash[k]==key){printf("hash[%d]=%d",k,key);flag=1;}else{k1=k+1;while(k1<MAX&&hash[k1]!=key)k1++;if(k1<MAX){printf("hash[%d]=%d",k1,key);flag=1;}k2=0;if(!flag){while(k2<k&&hash[k2]!=key)k2++;if(k2<k){printf("hash[%d]=%d",k2,key);flag=1;}}if(flag){printf("查找成功!\n");return;}else{printf("查找失败!\n");return;}}}void main(){int i,key,k,sum=0;int hash[MAX];for(i=0;i<MAX;i++)hash[i]=0;printf("请输入数据，以0结束:\n");scanf("%d",&key);sum++;while(key&&sum<MAX){ins_hash(hash,key);scanf("%d",&key);sum++;}printf("\n");out_hash(hash);printf("\n");printf("请输入查找的值:");scanf("%d",&k);hash_search(hash,k);printf("\n");}。
