数据结构 C/C++(实验六:查找)
（大家好，今天分享的是数据结构的相关知识，大家可以在评论区进行互动答疑哦~加油！💕）
目录
提要：实验题目
一、实验目的
二、实验内容及要求
三、源程序及注释
实验1代码（折半查找）
实验2代码（排序二叉树进行中序遍历）
实验3代码（哈希表）
四、实验结果
实验1结果
实验2结果
实验3结果
提要：实验题目
- 折半查找
- 排序二叉树进行中序遍历
- 哈希表的基本操作
一、实验目的
- 掌握几种典型的查找方法（折半查找、二叉排序树的查找、哈希查找）。
- 对各种查找算法的特点、使用范围和效率有进一步的了解。
- 了解图的典型应用的算法程序。
二、实验内容及要求
- 编程实现折半查找。
- 读入一串整数构成一棵二叉排序树，对该排序二叉树进行中序遍历，输出其结果。
- 用除留余数法构造哈希函数，并用线性探测再散列处理冲突，实现哈希表的基本操作，即表的构造和查找。
注：前两个题目必做，第3题选做。
三、源程序及注释
实验1代码（折半查找）
#include <iostream>
using namespace std;
// 折半查找函数
int binarySearch(int arr[], int size, int target) {
int left = 0;
int right = size - 1;
cout << "查找过程如下：\n";
while (left <= right) {
int mid = left + (right - left) / 2; // 计算中间位置
// 打印当前查找区间及中间元素
cout << "当前查找区间：[" << left << ", " << right << "]，中间元素：arr[" << mid << "] = " << arr[mid] << endl;
// 如果目标值等于中间值，返回索引
if (arr[mid] == target) {
cout << "找到了目标元素 " << target << "，位置为：" << mid << endl;
return mid;
}
// 如果目标值小于中间值，缩小查找范围到左半部分
else if (arr[mid] > target) {
right = mid - 1;
}
// 如果目标值大于中间值，缩小查找范围到右半部分
else {
left = mid + 1;
}
}
cout << "未找到目标元素 " << target << endl;
return -1; // 如果未找到目标值，返回-1
}
int main() {
int size;
cout << "请输入数组的大小：";
cin >> size;
int arr[size];
cout << "请输入数组元素（要求数组是升序的）：" << endl;
for (int i = 0; i < size; i++) {
cin >> arr[i];
}
int target;
cout << "请输入要查找的目标值：";
cin >> target;
// 调用折半查找函数
int result = binarySearch(arr, size, target);
if (result != -1) {
cout << "元素 " << target << " 在数组中的索引位置是： " << result << endl;
} else {
cout << "元素 " << target << " 不在数组中。" << endl;
}
return 0;
}
//请输入数组的大小：6
//请输入数组元素（要求数组是升序的）：
//10 20 30 40 50 60
//请输入要查找的目标值：40
//查找过程如下：
//当前查找区间：[0, 5]，中间元素：arr[2] = 30
//当前查找区间：[3, 5]，中间元素：arr[4] = 50
//当前查找区间：[3, 3]，中间元素：arr[3] = 40
//找到了目标元素 40，位置为：3
//元素 40 在数组中的索引位置是： 3实验2代码（排序二叉树进行中序遍历）
#include <iostream>
using namespace std;
struct TreeNode {
int val;
TreeNode* left;
TreeNode* right;
TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};
// 插入节点到二叉排序树
TreeNode* insert(TreeNode* root, int val) {
if (root == nullptr) {
return new TreeNode(val);
}
if (val < root->val) {
root->left = insert(root->left, val);
} else {
root->right = insert(root->right, val);
}
return root;
}
// 中序遍历
void inorder(TreeNode* root) {
if (root != nullptr) {
inorder(root->left);
cout << root->val << " ";
inorder(root->right);
}
}
int main() {
int n, val;
TreeNode* root = nullptr;
cout << "Enter number of elements: ";
cin >> n;
cout << "Enter the elements: ";
for (int i = 0; i < n; ++i) {
cin >> val;
root = insert(root, val);
}
cout << "Inorder traversal: ";
inorder(root);
cout << endl;
return 0;
}
//Enter number of elements: 7
//Enter the elements: 50 30 20 40 70 60 80
//Inorder traversal: 20 30 40 50 60 70 80实验3代码（哈希表）
#include <stdio.h>
#include <stdlib.h>
// 哈希表的最大大小
#define MAX_SIZE 100
// 哈希表结构
typedef struct HashTable {
int *table;
int size;
} HashTable;
// 哈希函数：除留余数法
int hash(int key, int size) {
return key % size;
}
// 初始化哈希表
void initHashTable(HashTable *ht, int size) {
ht->size = size;
ht->table = (int *)malloc(sizeof(int) * size);
// 初始化哈希表中的所有槽为 -1，表示空槽
for (int i = 0; i < size; i++) {
ht->table[i] = -1;
}
}
// 线性探测法处理冲突
int linearProbe(HashTable *ht, int key) {
int index = hash(key, ht->size);
int i = 0;
// 查找空槽
while (i < ht->size && ht->table[(index + i) % ht->size] != -1) {
i++;
}
// 返回下一个空槽的索引
return (index + i) % ht->size;
}
// 插入操作
void insert(HashTable *ht, int key) {
int index = hash(key, ht->size);
// 如果当前槽位已经被占用，则进行线性探测
if (ht->table[index] != -1) {
index = linearProbe(ht, key);
}
// 将元素插入哈希表
ht->table[index] = key;
}
// 查找操作
int find(HashTable *ht, int key) {
int index = hash(key, ht->size);
int i = 0;
// 查找元素
while (i < ht->size) {
int probeIndex = (index + i) % ht->size;
if (ht->table[probeIndex] == -1) {
return 0; // 没有找到
}
if (ht->table[probeIndex] == key) {
return 1; // 找到元素
}
i++;
}
return 0; // 没有找到
}
// 打印哈希表
void printHashTable(HashTable *ht) {
for (int i = 0; i < ht->size; i++) {
if (ht->table[i] != -1) {
printf("Index %d: %d\n", i, ht->table[i]);
} else {
printf("Index %d: empty\n", i);
}
}
}
// 主函数
int main() {
int size, numElements, element, key;
// 用户输入哈希表大小
printf("Enter the size of the hash table: ");
scanf("%d", &size);
// 创建哈希表
HashTable ht;
initHashTable(&ht, size);
// 用户输入插入的元素数量
printf("Enter the number of elements you want to insert: ");
scanf("%d", &numElements);
// 插入元素
printf("Enter %d elements to insert into the hash table:\n", numElements);
for (int i = 0; i < numElements; i++) {
scanf("%d", &element);
insert(&ht, element);
}
// 打印哈希表内容
printf("\nHash Table contents:\n");
printHashTable(&ht);
// 查找操作
printf("\nEnter an element to search in the hash table: ");
scanf("%d", &key);
printf("Find %d: %s\n", key, find(&ht, key) ? "Found" : "Not Found");
// 释放内存
free(ht.table);
return 0;
}四、实验结果
实验1结果
实验2结果
实验3结果
（今日分享暂时到此为止啦！为不断努力的自己鼓鼓掌吧🥳。今日文案分享：行于途，不究终点，沿途皆终点。）