数据结构-实验四

查找和排序算法实现

1、各种排序算法的实现

用随机函数生成16个2位正整数(10~99)，对同一组数据分别实现直接插入排序、 折半插入排序、希尔排序；冒泡排序、快速排序；选择排序、堆排序；二路归并排序； 基数排序等多种排序算法，输出排序中间过程、统计关键字的比较次数和记录的移动次 数。

#include<iostream>// 注意这里采用的全部都是升序
#include<cstdlib>
#include<ctime>
#include<cmath>

#define datatype int
#define length_arr 16
#define random(a,b) (rand()%(b-a)+a)

int QuickSortnums = 0;
int HeapSortnums = 0;
int MergingSortnums = 0;

using namespace std;

void printarr(datatype[]);

//1直接插入排序
void InsertionSort(datatype arr[]) {
	int length = length_arr;int k;
	int nums = 0;
	int movenums = 0;
	for (int i = 1;i < length;i++) {// 从第二个开始循环比较,避免出现数组越界
		if (arr[i] < arr[i - 1]) {
			datatype temp = arr[i];// 先暂存起来
			arr[i] = arr[i - 1];// 大的那个数先先后填补一下后面的小的数的值的地方
			for (k = i - 1;k>=0&&temp < arr[k];k--) {// 倒着往前面走,找到合适的地方插,还没有找到的话就是把当前的往后面移动
				arr[k + 1] = arr[k];// k可以处理边界问题,因为k为0的时候就结束循环
				nums++;
				movenums++;
			}
			arr[k + 1] = temp;
		}
	}
	cout << "总共比较" << nums << "次;" << "移动" << movenums << "次" << endl;
	cout << "直接插入排序:";
	printarr(arr);
}
//2折半插入排序
void BinaryInsertionSort(datatype arr[]) {
	int length = length_arr;int k;
	int nums = 0;
	int movenums = 0;
	for (int i = 1;i < length;i++) {// 从第二个开始循环比较,避免出现数组越界
		datatype temp = arr[i];// 先暂存起来
		int left = 0;
		int right = i - 1;
		while (right >= left) {// 二分查找,找到要插入的地方
			int middle = left + (right - left) / 2;
			nums++;
			if (temp >= arr[middle]) {
				left = middle + 1;
			}
			else {
				right = middle - 1;
			}
		}
		for (k = i - 1;k >= right+1 && temp < arr[k];k--) {// 倒着往前面走,找到合适的地方插,还没有找到的话就是把当前的往后面移动
			arr[k + 1] = arr[k];// k可以处理边界问题,因为k为0的时候就结束循环
			movenums++;
		}
		arr[k + 1] = temp;
	}
	cout << "总共比较" << nums << "次;" << "移动" << movenums << "次" << endl;
	cout << "折半插入排序:";
	printarr(arr);
}
//3希尔排序
void ShellSort(datatype arr[]) {
	int length = length_arr;int k;
	int nums = 0;
	int movenums = 0;
	int opp = log(length) / log(2) - 1;
	int f = pow(2, opp) - 1;
		while (f >= 1) {// 对数据进行分组
			for (int i = f;i < length;i++) {// 从第二个开始循环比较,避免出现数组越界
				if (arr[i] < arr[i - f]) {
					datatype temp = arr[i];// 先暂存起来
					arr[i] = arr[i - f];// 大的那个数先先后填补一下后面的小的数的值的地方
					for (k = i - f;k >= 0 && temp < arr[k];k--) {// 倒着往前面走,找到合适的地方插,还没有找到的话就是把当前的往后面移动
						arr[k + f] = arr[k];// k可以处理边界问题,因为k为0的时候就结束循环
						movenums++;
					}
					arr[k + f] = temp;
					nums++;
				}
			}
			opp--;
			f = pow(2, opp) - 1;
		}
		

	
	cout << "总共比较:" << nums << "次" << "移动:" << movenums << "次" << endl;
	cout << "希尔排序:";
	printarr(arr);
}
//4冒泡排序
void BubbleSort(datatype arr[]) {// 采用了flag的标志是否被交换过的标志
	int length = length_arr;
	int flag = 1;
	int nums = 0;
	while (length > 0 && flag) {
		flag = 0;
		for (int i = 0;i < length - 1;i++) {
			if (arr[i] > arr[i + 1]) {
				flag = 1;
				int temp = arr[i];
				arr[i] = arr[i + 1];
				arr[i + 1] = temp;
			}
				nums++;
		}
	}
	cout << "总共比较:" << nums << "次" << endl;
	cout << "冒泡排序:";
	printarr(arr);
}
//5快速排序
// 我的不是从第一个元素作为基准点,考虑到最坏的情况,已经排好序了,那么选择第一个是最坏的结果,所有我试着选择中间的节点
void QuickSort(datatype arr[],int left,int right) {// 在这里我采用的是从中间作为基准点,而不是书上的从第一个作为基准点,我认为书本上的做法不够最优,本身就多增加了一个内存用来存储第一个数据
	// 最为递归退出的条件
	if (left >= right) {
		return;
	}
	datatype targetnumber = arr[(left + right) / 2];
	int leftnumber = left;
	int rigthnumber = right;
	while (rigthnumber >= leftnumber) {
		while (arr[leftnumber] < targetnumber)leftnumber++, QuickSortnums++;// 如果满足条件,小的在左边,就移动指针
		while (arr[rigthnumber] > targetnumber)rigthnumber--, QuickSortnums;// 如果满足条件,大的在右边,就移动指针
		if (rigthnumber > leftnumber) {// 如果最后还是没能移动完指针的话,就说明需要交换一下顺序了
			datatype data = arr[rigthnumber];
			arr[rigthnumber] = arr[leftnumber];
			arr[leftnumber] = data;
			leftnumber++;
			rigthnumber--;
		}
		else if (rigthnumber == leftnumber) {
			break;
		}
	}
	//然后对左边还有右边进行新的一轮排序
	QuickSort(arr, left, leftnumber-1);
	QuickSort(arr, rigthnumber+1, right);
}
//6选择排序
void SelectSort(datatype arr[]) {
	int length = length_arr;
	int nums1 = 0;
	for (int i = 0;i < length;i++) {
		int nums = i;// 先保存好第i躺的数据i
		for (int k = i + 1;k < length;k++) {
			if (arr[k] < arr[nums]) {// 如果找到了比第nums还要小的数据,先保存好下标
				nums = k;
			}
			nums1++;
		}
		if (nums != i) {// for循环完毕,如果nums还是i,说明后面的数据没有最小的了,也就是遍历完了
			datatype data = arr[i];// 交换最小值
			arr[i] = arr[nums];
			arr[nums] = data;
		}
	}
	cout << "总共比较" << nums1 << "次" << endl;
	cout << "选择排序:";
	printarr(arr);
}
//7堆排序
void Headadjust(datatype arr[], int length, int i) {
	int topnumber = i;// 表示的是这个二叉树的一个两个子树的父节点
	int leftnumber = 2 * i + 1;// 左子树
	int rightnumber = 2 * i + 2;// 右子树
	//int max_number =(leftnumber < length && arr[leftnumber] >= arr[rightnumber]) ? arr[leftnumber] : arr[rightnumber];// 先判断左子树和右子树哪一个的值更大
	//int max_index = (leftnumber < length && arr[leftnumber] >= arr[rightnumber]) ? leftnumber : rightnumber;// 获取值更大的那个下标
	//topnumber = arr[topnumber] >= max_number ? i : max_index; // 如果在不超过界限的情况下, 左右子树的最大的哪一个值比父亲节点的值还要大的话, 就进行交换处理
	if (leftnumber<length && arr[leftnumber]>arr[topnumber]) {
		topnumber = leftnumber;
		HeapSortnums++;
	}
	if (rightnumber<length && arr[rightnumber]>arr[topnumber]) {
		topnumber = rightnumber;
		HeapSortnums++;
	}
	if (topnumber != i) {// 如果这个下标值改变的话,就说明这个树没有实现大堆化,进行交换数据
		datatype data = arr[topnumber];
		arr[topnumber] = arr[i];
		HeapSortnums++;
		arr[i] = data;
		Headadjust(arr, length, topnumber);//进行递归,解决因为父亲节点的问题而引发的一系列问题导致下面已经排好大堆顺序因为父亲交换的缘故让下面的节点不在是大堆的排序状态
	}
}
void HeapSort(datatype arr[]) {// 堆排序的主要的函数部分
	int length = length_arr;
	for (int i = length / 2-1; i >= 0; i--) {//完全二叉树的叶子节点数量大约等于所有节点的一半,而叶子节点是可以看作是一个正确的堆的
		Headadjust(arr, length, i);
	}
	for (int i = length-1; i > 0; i--) {// 这个就是对数组进行排序了,从小到大
		datatype data = arr[0];
		arr[0] = arr[i];
		arr[i] = data;
		HeapSortnums++;
		Headadjust(arr, i, 0);
	}
}
//8二路归并排序
// 两个有序表的合并
void Merging(datatype arr[], datatype temparr[], int leftnumber, int middlebumber, int rightnumber) {
	// 使用指针类似的东西
	int left = leftnumber;// 这个代表的是左边的第一个数组的第一个元素所指向的下标索引
	int middle = middlebumber + 1;//这个代表的是左边的第二个数组的第一个元素所指向的下标索引
	int start = leftnumber;
	while (left != middlebumber + 1 && middle != rightnumber + 1) {
		if (arr[left] <= arr[middle]) {// 说明的就是左边的值比右边的值还要小
			temparr[start++] = arr[left++];
			MergingSortnums++;
		}
		else {
			temparr[start++] = arr[middle++];
			MergingSortnums++;
		}
	}
	while (left != middlebumber + 1) {// 说明左边的值还有,可是右边的值已经没有了
		temparr[start++] = arr[left++];
		MergingSortnums++;
	}
	while (middle != rightnumber + 1) {// 说明右边的值还有,可是左边的值已经没有了
		temparr[start++] = arr[middle++];
		MergingSortnums++;
	}
	for (int i = leftnumber;i <= rightnumber;i++) {
		arr[i] = temparr[i];
	}
}
void MergingSort(datatype arr[],datatype temparr[],int leftnumber,int rightnumber) {
	int middlenumber;// 划分为两个数组的关键之处为middlenumber,作为分割线
	if (rightnumber > leftnumber) {// 直到划分到只有一个数据为止
		middlenumber = (rightnumber + leftnumber) / 2;
		MergingSort(arr, temparr, leftnumber, middlenumber);// 递归左边的,直到只有一个数据为止
		MergingSort(arr, temparr, middlenumber+1, rightnumber);// 递归右边的
		Merging(arr, temparr, leftnumber, middlenumber, rightnumber);// 合并数组
	}
}
//9基数排序
int maxdatabit(datatype arr[]) {// 返回最大位数
	int length = length_arr;
	datatype data = 0;// 寻找最大值
	int databit = 0;
	for (int i = 0;i < length;i++) {
		if (arr[i] > data) {
			data = arr[i];
		}
	}
	while (data) {// 寻找最大位数
		databit++;
		data /= 10;
	}
	return databit;// 返回最大的位数
}
void RadixSort(datatype arr[]) {
	int length = length_arr;
	int indexnubmer = 1;//用来弄位数的
	int max_bit = maxdatabit(arr);// 获取最大的位数
	// 对这个数组进行基数排序
	for (int i = 0;i < max_bit;i++) { // 对相应的每一个位数进行排序
		int collectdata[10] = { 0 };// 用来计数[记录数据的个数
		int temparr[length_arr];
		for (int j = 0;j < length;j++) { // 对相应的位数的数据进行计数
			int index = (arr[j] / indexnubmer) % 10;
			collectdata[index]++;
		}
		// 将计数器转为累积计数
		for (int j = 1; j < 10; j++) {
			collectdata[j] += collectdata[j - 1];
		}
		// 将数据按当前位数排序到临时数组
		for (int j = length - 1; j >= 0; j--) { // 倒序遍历保持稳定性
			int index = (arr[j] / indexnubmer) % 10;
			temparr[collectdata[index] - 1] = arr[j];
			collectdata[index]--;
		}
		for (int k = 0;k < length;k++) { // 更新数组,对数组进行对位数的排序
			arr[k] = temparr[k];
		}
		indexnubmer = indexnubmer * 10;
	}
}
void swerarr(datatype arr1[], datatype arr2[]) {
	for (int i = 0;i < length_arr;i++) {
		arr1[i] = arr2[i];
	}
}
void printarr(datatype arr[]) {
	for (int i = 0;i < length_arr;i++) {
		cout << arr[i] << "   ";
	}
	cout << endl;
	cout << endl;
}
int main() {
	srand((unsigned)time(NULL));
	int arr[16];
	int arr2[16];
	datatype temparr[16];
	for (int i = 0;i < 16;i++) {
		arr[i] = random(10, 100);
		arr2[i] = arr[i];
	}
	cout << "原来的数组为:";
	printarr(arr);

	//1直接插入排序
	InsertionSort(arr);
	swerarr(arr, arr2);

	//2折半插入排序
	BinaryInsertionSort(arr);
	swerarr(arr, arr2);

	//3希尔排序
	ShellSort(arr);
	swerarr(arr, arr2);

	//4冒泡排序
	BubbleSort(arr);
	swerarr(arr, arr2);

	//5快速排序
	QuickSort(arr, 0, length_arr - 1);
	cout << "总共比较:" << QuickSortnums << "次" << endl;
	cout << "快速排序";
	printarr(arr);
	swerarr(arr, arr2);

	//6选择排序
	SelectSort(arr);
	swerarr(arr, arr2);

	//7堆排序
	HeapSort(arr);
	cout << "总共比较:" << HeapSortnums << "次" << endl;
	cout << "堆排序";
	printarr(arr);
	swerarr(arr, arr2);

	//8二路归并排序
	MergingSort(arr, temparr, 0, length_arr - 1);
	cout << "总共比较:" << MergingSortnums << "次" << endl;
	cout << "二路归并排序";
	printarr(arr);
	swerarr(arr, arr2);

	//9基数排序
	RadixSort(arr);
	cout << "基数排序";
	printarr(arr);
	return 0;
}

2、各种查找算法实现

(1) 顺序查找：

用随机函数生成16 个不重复的字母(’a’~’z’)，键盘输入待查找的字 母，返回查找成功与否，并计算比较次数；成功则返回该字母所在的位置(序号)。

(1.1) 使用链表实现；

#include<iostream>
#include<cstdlib>
#include<ctime>
#define datatype char
#define random(a,b) (rand()%(b-a)+a)
using namespace std;

int numsnumber = 0;

typedef struct listArr {// 初始化链表的结构体数据
	datatype data;// 存储数据
	struct listArr* next;// 指向下一个节点
};
listArr* addlist(datatype data[],int size) {
	listArr* head = new listArr{ data[0],NULL };// 不使用头节点,将第一个节点用来保存第一个值
	listArr* current = head;
	for (int i = 1;i < size;i++) {
		current->next = new listArr{ data[i],NULL };
		current = current->next;
	}
	current = NULL;// 最后更新最后的节点为NULL
	return head;
}
int sversedata(listArr* app,datatype data) {// 查找这个链表中是否有这个数据,如果有的话就会返回的是这个数据的下标值
	listArr* current = app;
	int postion = 0;// 存储的是用来表示下标的数据
	while (current) {
		if (current->data == data) {
			return postion;
		}
		current = current->next;
		postion++;
		numsnumber++;
	}
	return -1;
}
void printlist(listArr* app) {// 打印这个链表
	listArr* current = app;
	while (current) {
		cout << current->data << "   ";
		current = current->next;
	}
	cout << "end" << endl;
}
int main() {
	srand((unsigned)time(NULL));// 生成随机数
	datatype arr[16];// 初始化随机数组
	bool used[26] = { false };
	for (int i = 0; i < 16; i++) {
		char c;
		do {
			c = random('a', 'z');
		} while (used[c - 'a']);
		used[c - 'a'] = true;
		arr[i] = c;
	}
	listArr* head = addlist(arr, 16);
	printlist(head);
	datatype data;
	cout << "请输入要查找的数字:";
	cin >> data;
	cout << sversedata(head, data) << endl;
	cout << "查找的次数为:" << numsnumber << endl;
	return 0;
}

(1.2) 使用数组实现，并设置哨兵机制。

#include<iostream>
#include<cstdlib>
#include<ctime>
#define random(a,b) (rand()%(b-a)+a)
#define keytype char
using namespace std;

int numsnumber = 0;

typedef struct Element {// 在这个结构体里面可以增加数据,目前只有增加了一个数据
	keytype data;
};
typedef struct List {// 用来存储这个数据的,就像数组一样
	Element* list;
	int length;
	int nums = 1;
};
void initList(List* app,int length) {
	app->length = length;
	app->list = new Element[app->length + 1];//第一个0号单元用来存储哨兵
}
void addList(List* app, int data) {
	app->list[app->nums++].data = data;//nums++,先用后加,这样就可以少些一步
}
keytype serachList(List* app, keytype key) {
	app->list[0].data = key;
	for (int i = app->length;i >= 0;i--) {// 我i什么要等于app->lenght,因为有哨兵
		numsnumber++;
		if (app->list[i].data == key) {
			return i;
		}
	}
}
void printList(List* app) {
	for (int i = 1;i < app->length;i++) {
		cout << app->list[i].data << "    ";
	}
	cout << endl;
}
int main() {
	srand((unsigned)time(NULL));	
	List* list = new List;
	initList(list, 16);
	bool used[26] = { false };
	for (int i = 0;i < 16;i++) {
		char c;
		do {
			c = random('a', 'z');
		} while (used[c - 'a']);
		used[c - 'a'] = true;
		addList(list, c);// 初始化随机数组
	}
	printList(list);
	cout << "请输入要查找的key:";
	keytype key;cin >> key;
	int data = serachList(list, key);
	if (!data) {
		cout << "返回0,查无此数!!!!!!" << endl;
	}
	else {
		cout << data << endl;
	}
	cout << "比较的次数为:" << numsnumber << endl;
	delete[] list->list;  // 释放内存
	delete list;  // 释放list指针
	return 0;
}

(2) 折半查找：

用数组实现，查找前元素先排序。计算比较次数。分别用查找成功、 不成功进行测试。

#include<iostream>
#include<cstdlib>
#include<ctime>
#define random(a,b) (rand()%(b-a)+a)
#define datatype char
#define length_arr 16// 之前采用sizeof的方法,因为传入的是指针,不是真正的数组长度,而且懒得传长度进去,就写个宏定义
using namespace std;

int numsnumber = 0;

void sortarr(datatype app[]) {// 采用了flag的标志是否被交换过的标志
	int length = length_arr;
	int flag = 1;
	while (length > 0 && flag) {
		flag = 0;
		for (int i = 0;i < length - 1;i++) {
			if (app[i] > app[i + 1]) {
				flag = 1;
				datatype temp = app[i];
				app[i] = app[i + 1];
				app[i + 1] = temp;
			}
		}
	}
}
int BinarySearch(datatype app[], datatype key) {// 二分查找
	int rigth = length_arr;
	int left = 0;
	while (rigth >= left) {
		numsnumber++;
		int middle = (rigth + left) / 2;
		if (key == app[middle]) {
			return middle;
		}
		else if(key>app[middle]) {
			left = middle + 1;
		}
		else {
			rigth = middle - 1;
		}
	}
	return -1;
}
void printarr(datatype app[]) {
	int length = length_arr;
	for (int i = 0;i < length;i++) {
		cout << app[i] << "    ";
	}
	cout << endl;
}
int main() {
	srand((unsigned)time(NULL));// 生成随机数
	datatype arr[16];// 初始化随机数组
	bool used[26] = { false };
	for (int i = 0; i < 16; i++) {
		char c;
		do {
			c = random('a', 'z'+1);
		} while (used[c - 'a']);
		used[c - 'a'] = true;
		arr[i] = c;
	}
	sortarr(arr);
	printarr(arr);
	cout << "请输入要查找的key:";
	datatype key;cin >> key;
	int data = BinarySearch(arr, key);
	cout << data << endl;
	cout << "查找比较的次数为:" << numsnumber << endl;
	return 0;
}

(3) 二叉查找树：

手工输入10个字母，生成一棵二叉查找树，用递归算法打印树结 构或分别输出先序和中序遍历序列以确认其结构。键盘输入待查找的字母，计算比较次 数，并删除该字母。分别用查找成功、不成功进行测试。

#include<iostream>
using namespace std;

#define datatype char
int BSTnums = 0;

//二叉查找树：手工输入10个字母，生成一棵二叉查找树，用递归算法打印树结
//构或分别输出先序和中序遍历序列以确认其结构。键盘输入待查找的字母，计算比较次
//数，并删除该字母。分别用查找成功、不成功进行测试。

typedef struct BSTtree { // 定义二叉排序树的结构
	datatype data;
	struct BSTtree* leftchild;
	struct BSTtree* rightchild;
};
void insertBST(BSTtree*& root, datatype app) { // 修改为引用传递
	if (root == NULL) {
		root = new BSTtree;
		root->data = app;
		root->leftchild = root->rightchild = NULL;
	}
	else if (app > root->data) { // 如果是大于的话就在其右边
		insertBST(root->rightchild, app);
	}
	else { // 不大于的话就是在左边
		insertBST(root->leftchild, app);
	}
}
void createBSTtree(BSTtree*& root) { // 创建二叉排序树
	datatype data;
	cin >> data;
	while (data != '#') { // 规定输入9999就完毕创建一个二叉树
		insertBST(root, data); // 插入一个值到这个排序二叉树当中去
		cin >> data;
	}
}
int SearchBST(BSTtree*& root, datatype data) { // 修改为引用传递
	if (root == NULL) {
		BSTnums++;
		return -1;
	}
	else if (root->data == data) {
		BSTnums++;
		// 找到要删除的节点
		if (root->leftchild == NULL && root->rightchild == NULL) { // 无子树
			delete root;
			root = NULL;
		}
		else if (root->leftchild == NULL) { // 只有右子树
			BSTtree* temp = root;
			root = root->rightchild;
			delete temp;
		}
		else if (root->rightchild == NULL) { // 只有左子树
			BSTtree* temp = root;
			root = root->leftchild;
			delete temp;
		}
		else { // 有左右子树
			// 找到右子树中的最小节点
			BSTtree* temp = root->rightchild;
			while (temp->leftchild != NULL) {
				temp = temp->leftchild;
			}
			root->data = temp->data; // 用最小节点值替代当前节点
			SearchBST(root->rightchild, temp->data); // 删除最小节点
		}
		return 0;
	}
	else if (data > root->data) {
		BSTnums++;
		return SearchBST(root->rightchild, data);
	}
	else {
		BSTnums++;
		return SearchBST(root->leftchild, data);
	}
}
// 先序遍历
void preorder(BSTtree* root) {
	if (root == NULL) return;
	cout << root->data << " ";
	preorder(root->leftchild);
	preorder(root->rightchild);
}
// 中序遍历
void inorder(BSTtree* root) {
	if (root == NULL) return;
	inorder(root->leftchild);
	cout << root->data << " ";
	inorder(root->rightchild);
}
int main() {
	BSTtree* root = NULL;
	cout << "请输入值:";
	createBSTtree(root);
	cout << "先序遍历:";
	preorder(root);
	cout << endl;
	cout << "后序遍历:";
	inorder(root); cout << endl;
	datatype data;
	cout << "输入要查找而且会被删除的值:";
	cin >> data;
	if (SearchBST(root, data) == 0) {
		cout << "删除成功！" << endl;
	}
	else {
		cout << "未找到该字母！" << endl;
	}
	cout << "先序遍历:";
	preorder(root); cout << endl;
	cout << "后序遍历:";
	inorder(root);
	cout << "查找的比较次数为:" << BSTnums << endl;
	return 0;
}

(4) 哈希查找：

用随机函数生成16个2位正整数（10～99），键盘输入待查找的数 据，使用除留余数法、开放地址法中的线性探测法。分别用查找成功、不成功进行测试， 并计算比较次数。

#include<iostream>
#include<cstdlib>
#include<ctime>

#define random(a,b) (rand()%(b-a)+a)
#define datatype int
#define hash_length 18// 之前采用sizeof的方法,因为传入的是指针,不是真正的数组长度,而且懒得传长度进去,就写个宏定义

int hashnums = 0;
using namespace std;

//哈希查找：用随机函数生成16个2位正整数（10～99），键盘输入待查找的数
//据，使用除留余数法、开放地址法中的线性探测法。分别用查找成功、不成功进行测试，
//并计算比较次数

// 定义哈希表
typedef struct HashTable {
	int data;
	bool havavalue;
};
int gethashvalue(datatype data) {
	return data % 17;
}
//初始化哈希表
HashTable* inithashtable() {
	HashTable* arr = new HashTable[hash_length];
	for (int i = 0;i < hash_length;i++) {
		arr[i].havavalue = false;// 初始化这个哈希表中都没有值
		arr[i].data = -1;// 先赋值,万一出问题
	}
	return arr;
}
//把值插入到哈希表中去
void insertvalue(HashTable app[], datatype data) {
	int indexnumber = gethashvalue(data);// 得到楚留余数法的哈希关键值
	while (app[indexnumber].havavalue) {// 如果这个未知已经有了值的话,就是说明要下一位进发
		indexnumber = (indexnumber + 1) % hash_length;
	}
	app[indexnumber].data = data;
	app[indexnumber].havavalue = true;// 标记已经在这个位置有值了的
}
// 哈希查找函数
int SearchHash(HashTable app[], datatype data) {
	int indexnumber = gethashvalue(data);// 和上面的相差不大
	while (app[indexnumber].havavalue) {
		hashnums++;
		if (app[indexnumber].data == data) {
			return indexnumber;// 找到就返回下标
		}
		indexnumber = (indexnumber + 1) % hash_length;
	}
	return -1;// 找不到就返回-1
}
void printhashtable(HashTable arr[]) {
	for (int i = 0;i < hash_length;i++) {
		cout << "键为:" << i << "---" << "值为:" << arr[i].data << endl;
	}
}
int main() {
	srand((unsigned)time(NULL));
	HashTable* table_arr = inithashtable();
	for (int i = 0;i < 16;i++) {

		insertvalue(table_arr, random(10, 100));
	}
	printhashtable(table_arr);
	datatype data;
	cout << "输入要查找的值:";
	cin >> data;
	cout << SearchHash(table_arr, data);
	cout << "查找的次数为:" << hashnums << endl;
	return 0;
}