一 队列(先进先出)
1.定义：从一端进行数据插入，另一端进行删除的线性存储结构
队列类型
常见操作
- 入队（Enqueue）：将新元素添加到队列的尾部。若队列有空间，新元素会成为队列的新尾部元素；若队列已满，可能会触发队列已满的处理机制。
- 出队（Dequeue）：从队列的头部移除元素。执行后，原队头元素被删除，原队头的下一个元素成为新队头。若队列为空，可能会触发队列空的处理机制。
- 获取队头元素（Front）：返回队列头部的元素，但不删除它，以便查看即将被处理的元素。
- 判断队列是否为空（IsEmpty）：检查队列中是否有元素，若没有则返回真，否则返回假。
- 获取队列大小（Size）：返回队列中元素的数量。
Queue *create_queue() //创建队列
{
Queue *pque = malloc(sizeof(Queue));
if (NULL == pque)
{
printf("fail malloc\n");
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\n");
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("\n");
}
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;
}二 队列与栈的区别
队列和栈都是常见的数据结构，它们既有区别又有联系，具体如下：
区别
- 操作规则：队列遵循先进先出（FIFO）原则，如排队买票，先到的人先买。在队列中，新元素从队尾进入，从队头出。栈遵循后进先出（LIFO）原则，像堆叠盘子，后放的先取。在栈中，元素从栈顶进，也从栈顶出。
- 操作位置：队列的插入操作在队尾，删除操作在队头。栈的插入和删除操作都在栈顶。
- 应用场景：队列常用于任务排队、消息传递等场景，如打印机任务队列。栈常用于函数调用、表达式求值、括号匹配等，如计算表达式时用栈存储操作数和运算符。
- 数据访问方式：队列通常只能访问队头和队尾元素。栈只能访问栈顶元素。
联系
- 数据结构类型：队列和栈都是线性数据结构，数据元素间呈线性关系，一个接一个排列，有前驱和后继（除首尾元素）。
- 基本操作：都有插入和删除数据的操作，尽管操作规则和位置不同，但都是对数据的基本增删操作。
- 存储实现：都可以用数组或链表实现。用数组实现时，都要考虑边界条件和空间大小；用链表实现时，都要操作节点的指针来实现数据的插入和删除。
三 哈希存储(散列存储)
哈希存储是一种重要的数据存储和检索技术，以下是相关介绍：
基本概念：
哈希存储，也叫散列存储，是根据关键码值（key）直接访问数据的存储结构。它通过一个哈希函数，把关键码值映射到一个有限的、连续的地址空间，这个地址空间称为哈希表或散列表。哈希函数的作用是将任意长度的输入数据，转换为固定长度的输出，这个输出就是数据在哈希表中的存储位置，也叫哈希值或散列值。
关键特点
- 快速查找：理想情况下，哈希存储能在接近常数的时间复杂度内完成查找、插入和删除操作，效率极高。
- 无需数据有序：数据在哈希表中的存储位置与数据本身的大小、顺序等无关，只取决于哈希函数和关键码值。
- 存储空间相对固定：哈希表的大小通常在创建时就确定或有一定的扩展策略，不随数据量的增加而无限增长。
哈希函数的设计原则
- 一致性：相同的输入必须产生相同的输出。
- 高效性：计算哈希值的过程应尽量简单快速，以减少时间开销。
- 均匀性：理想情况下，哈希函数应将不同的关键码值均匀地分布在哈希表的地址空间中，减少冲突的发生。
处理冲突的方法
- 开放定址法：当冲突发生时，通过某种探测序列在哈希表中寻找下一个可用的空闲位置来存储数据。比如线性探测法，就是依次检查下一个位置，直到找到空闲位置。
- 链地址法：将所有哈希值相同的数据存储在一个链表中，哈希表中的每个位置指向一个链表，链表中的节点存储具有相同哈希值的数据。
应用场景
- 数据库索引：数据库系统常使用哈希索引来快速定位数据记录，提高数据查询效率。
- 缓存系统：在缓存中，哈希存储用于快速查找缓存数据，判断数据是否已在缓存中，提高数据访问性能。
API接口实现
int hash_function(char key)
{
if (key >= 'a' && key <= 'z')
{
return key - 'a';
}
else if (key >= 'A' && key <= 'Z')
{
return key - 'A';
}
else
{
return HASH_TABLE_MAX_SIZE-1;
}
}
int insert_hash_table(Hash_node **hash_table, Data_type data)
{
int addr = hash_function(data.name[0]);
Hash_node *pnode = malloc(sizeof(Hash_node));
if (NULL == pnode)
{
printf("fail malloc\n");
return -1;
}
pnode->data = data;
pnode->pnext = NULL;
/*
pnode->pnext = hash_table[addr]; //phead
hash_table[addr] = pnode;
*/
if (NULL == hash_table[addr])
{
hash_table[addr] = pnode;
}
else if (strcmp(hash_table[addr]->data.name, data.name) >= 0)
{
pnode->pnext = hash_table[addr];
hash_table[addr] = pnode;
}
else
{
Hash_node *p = hash_table[addr];
while (p->pnext != NULL && strcmp(p->pnext->data.name, pnode->data.name) < 0)
{
p = p->pnext;
}
pnode->pnext = p->pnext;
p->pnext = pnode;
}
return 0;
}
void hash_table_for_each(Hash_node **hash_table)
{
for (int i = 0; i < HASH_TABLE_MAX_SIZE; i++)
{
Hash_node *p = hash_table[i];
while (p != NULL)
{
printf("%s: %s\n", p->data.name, p->data.tel);
p = p->pnext;
}
printf("\n");
}
}
Hash_node *find_hash_by_name(Hash_node **hash_table, char *name)
{
int addr = hash_function(name[0]);
Hash_node *p = hash_table[addr];
while (p)
{
if (0 == strcmp(p->data.name, name))
{
return p;
}
p = p->pnext;
}
return NULL;
}
void destroy_hash_table(Hash_node **hash_table)
{
for (int i = 0; i < HASH_TABLE_MAX_SIZE; i++)
{
Hash_node *p = hash_table[i];
while (p != NULL)
{
hash_table[i] = p->pnext;
free(p);
p = hash_table[i];
}
}
}