2024.3.19

1.哈希表

代码：

#include"hash.h"

//申请结点
node_p create_node(int data)
{
	node_p new = (node_p)malloc(sizeof(node));
	new->data = data;
	return new;
}
//存入哈希表
void insert(node_p H[],int key)
{
	//数据要存入哈希表中指定下标的位置
	int i = key%MAX;
	//申请结点
	node_p new = create_node(key);
	//头插
	new->next = H[i];
	H[i] = new;
}
//输出哈希表
void show(node_p *H)
{
	if(H==NULL)
	{
		printf("入参为空，请检查\n");
		return;
	}
	for(int i=0;i<MAX;i++)
	{
		//输出指针数组所指向的链表
		node_p p = H[i];
		while(p!=NULL)
		{
			printf("%d->",p->data);
			p=p->next;
		}
		printf("NULL\n");
	}
}
//查找元素
void search(node_p H[],int key)
{
	if (H==NULL)
	{
		printf("入参为空，请检查\n");
		return;
	}
	int i = key%MAX;
	node_p p = H[i];
	if(p->data==key)
	{
		printf("该元素下标为：%d\n",i);
		return;
	}
	else
	{
		p = p->next;
		printf("该元素下标为：%d\n",i);
		return;
	}
	if(p->data!=key)
	{
		printf("没有该元素\n");
		return;
	}
}

结果：

2.快速排序和折半（二分）查找

快速排序

代码：

#include<myhead.h>

//一次快排的代码，需要返回基准最后的位置
int one_sort(int *arr,int low,int high)
{
	//定义一个基准元素，每次的基准元素是序列中low下标的元素
	int base = arr[low];
	while(high>low)
	{
		while(high>low&&arr[high]>base)
		{
			high--;
		}
		arr[low] = arr[high];
		while(high>low&&arr[low]<base)
		{
			low++;
		}
		arr[high] = arr[low];
	}
	arr[low] = base;
	return low;
}
//整体快排
void sort(int *arr,int low,int high)
{
	if(high>low)
	{
		int ret = one_sort(arr,low,high);
		sort(arr,low,ret-1);
		sort(arr,ret+1,high);
	}
}

int main(int argc, const char *argv[])
{
	int arr[]={98,72,65,43,12,66,25,39};
	int len = sizeof(arr)/sizeof(arr[0]);
	//one_sort(arr,0,len-1);    一次快排
	sort(arr,0,len-1);
	//输出
	for(int i=0;i<len;i++)
	{
		printf("%d\n",arr[i]);
	}
	return 0;
}

结果：

折半查找

代码：

#include<myhead.h>

//折半查找的函数
int half_search(int *arr,int low,int high,int key)
{
	while(high>=low)//查找算法，一个数也要查
	{
		int mid = (low+high)/2;
		if(arr[mid]==key)
		{
			return mid;
		}
		else if(arr[mid]>key)
		{
			high = mid-1;
		}
		else if(arr[mid]<key)
		{
			low = mid+1;
		}
	}
	printf("没有该元素\n");
	return -1;
}

int main(int argc, const char *argv[])
{
	int arr[]={12,25,36,47,58,89,92};//需要数组有序，逻辑有序即可
	int len = sizeof(arr)/sizeof(arr[0]);
	int n;
	printf("请输入想要查找到的元素：");
	scanf("%d",&n);
	printf("查找到的数据下标为：%d\n",half_search(arr,0,len-1,n));
	return 0;
}

结果：

3.思维导图