重庆网络干部学院,汕头百度快速优化排名,58同城找工作app下载,wordpress优惠券插件一 队列(先进先出)
1.定义#xff1a;从一端进行数据插入#xff0c;另一端进行删除的线性存储结构 队列类型 常见操作
- 入队#xff08;Enqueue#xff09;#xff1a;将新元素添加到队列的尾部。若队列有空间#xff0c;新元素会成为队列的新尾部元素#xff1b;若…一 队列(先进先出)
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]; //pheadhash_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];}}
}
