数据结构5-（队列与哈希存储）网站首页 技术交流

数据结构5-（队列与哈希存储）

哲学表 2026-04-04 12:01:05

简介数据结构5-（队列与哈希存储）

一、队列（先进先出）

1.定义：从一端进行数据插入、另一端进行数据删除的线性存储结构

2.应用：进行数据缓存

缓冲区的作用：当低速设备与高速设备之间进行数据交换利用缓冲区来提高效率

3.分类

顺序表：顺序队列（问题：假溢出）

循环队列：解决假溢出问题

空：队头和队尾相遇

满：队尾+1等于队头（牺牲一个存储空间）

4.链式队列的实现

#include "queue.h"
#include <stdlib.h>
#include <stdio.h>
 
 
 
Queue *create_queue()
{
	Queue *pque = malloc(sizeof(Queue));
	if (NULL == pque)
	{
		printf("fail malloc
");
		return NULL;
	}
	pque->pfront = NULL;
	pque->ptail = NULL;
	pque->clen = 0;
 
	return pque;
		
}
int enter_queue(Queue *pque, Data_type data)
{
	Que_node *pnode = malloc(sizeof(Que_node));	
	if (NULL == pnode)
	{
		printf("fail malloc
");
		return -1;
	}
	pnode->data = data;
	pnode->pnext = NULL;
	
	if (is_empty_queue(pque))
	{
		pque->ptail = pnode;
		pque->pfront = pnode;
	}
	else
	{
		pque->ptail->pnext = pnode;
		pque->ptail = pnode;
	}
	pque->clen++;
 
	return 0;
}
/**************************
 *返回值：返回出队的元素个数
 *   为空：0
 *   成功：1
 * ************************/
int out_queue(Queue *pque, Data_type *pdata)
{
	if (is_empty_queue(pque))
	{
		return 0;
	}
	
	if (pdata != NULL)
	{
		*pdata = pque->pfront->data;
	}
	Que_node *pdel = pque->pfront;
	pque->pfront = pdel->pnext;
	free(pdel);
	if (NULL == pque->pfront)
	{
		pque->ptail = NULL;
	}
 
	pque->clen--;
	return 1;
}
int is_empty_queue(Queue *pque)
{
	return NULL == pque->pfront;
}
void clear_queue(Queue *pque)
{
	while (!is_empty_queue(pque))
	{
		out_queue(pque, NULL);
	}
}
void destroy_queue(Queue **ppque)
{
	clear_queue(*ppque);
	free(*ppque);
	*ppque = NULL;
}
void queue_for_each(Queue *pque)
{
	Que_node *p = pque->pfront;
	while (p != NULL)
	{
		printf("%d ", p->data);
		p = p->pnext;
	}
	printf("
");
}
int get_front_queue(Queue *pque, Data_type *pdata)
{
	if (is_empty_queue(pque))
	{
		return 0;
	}
	if (pdata != NULL)
	{
		*pdata = pque->pfront->data;
	}
 
	return 1;
}

二、哈希存储(散列存储)

1.定义

将要存储的数据的关键字和数据的存储位置之间建立关系，存储数据时，按照函数关系寻找存储位置；数据查找时，根据关键字进行函数映射得到数据的存储位置。

2.哈希函数的常见举例

addr=key % 10;（求余法）

f(addr)=a*key+b;(一次函数法)

3.哈希矛盾/哈希冲突

定义：

数据通过哈希函数的操作，映射到同一地址

解决办法：

地址开放法：发生冲突后在冲突位置往下遍历第一个空地址存储数据。

链地址法：

4.目的

提高数据的查找效率

三、指针数组与数组指针

指针数组

-定义：

指针数组是一个数组，其数组元素都是指针类型。一般定义形式为数据类型 *数组名[数组长度] ，如 int *ptr_array[5] ，表示一个包含5个指向 int 类型数据的指针的数组。

- 用途：

常用于处理多个字符串，可将每个字符串的首地址存于指针数组中，方便操作和管理，如 char *str_array[] = {"hello", "world"} 。也可用于动态分配二维数组内存，通过指针数组中每个指针指向不同的一维数组，实现类似二维数组的功能。

数组指针

- 定义：

数组指针是一个指针，它指向一个数组。定义形式为数据类型 (*指针名)[数组长度] ，如 int (*ptr)[5] ，表示 ptr 是一个指向包含5个 int 类型元素的数组的指针。

- 用途：

在函数传参中，若要传递二维数组给函数，可使用数组指针作为参数，让函数能正确访问和操作二维数组元素。也可用于更灵活地操作二维数组，通过移动数组指针遍历二维数组的行。

两者区别

- 概念本质：指针数组是数组，是多个指针的集合，数组名代表数组首地址，即第一个指针元素的地址。数组指针是指针，其指向整个数组，指针变量存储的是数组的首地址。

- 内存布局：指针数组的元素是指针，每个指针需占用一定内存空间存储地址，整体内存布局是连续存储多个指针。数组指针只占一个指针大小的内存空间，用于存储它所指向的数组的首地址。

- 访问方式：访问指针数组元素需先通过数组下标找到对应的指针，再通过指针访问其所指向的数据，如 ptr_array[i] 先取第 i 个指针，再用 *ptr_array[i] 访问指向的数据。访问数组指针所指数组元素时，可将数组指针看作数组名，用 (*ptr)[i] 访问指向数组的第 i 个元素。