企业网站推广解决方案,泰安哪个做网站,黄骗免费网站,昆明 网站 制作摘自#xff1a;数据结构学习——链式队列解析#xff08;C语言版#xff09; 作者#xff1a;正弦定理 发布时间#xff1a;2020-11-26 21:07:08 网址#xff1a;https://blog.csdn.net/chinesekobe/article/details/110203428 数据结构——链队列解析过程和简单代码实现… 摘自数据结构学习——链式队列解析C语言版 作者正弦定理 发布时间2020-11-26 21:07:08 网址https://blog.csdn.net/chinesekobe/article/details/110203428 数据结构——链队列解析过程和简单代码实现 一、简单概念动图展示(1)入队(2)出队 二、顺序队列思路步奏1入队操作2出队操作 简单实现代码 三、链式队列1声明2入队操作3出队操作4检查队列是否为空全部代码 一、简单概念 队列又称为伫列queue是先进先出FIFO,First-In-First-Out的线性表。在具体应用中通常用链表或者数组来实现。队列只允许在后端称为rear进行插入操作在前端称为front进行删除操作 队列的操作方式和堆栈类似唯一的区别在于队列只允许新数据在后端进行添加 与栈stack不同的是队列是FIFOFirst In First Out先进先出进入队列的一端叫尾部rear出队列的一端叫头部front。队列的主要操作也有两个入队offer、出队poll 动图展示 (1)入队 从图中可以看到A、B、C三个元素都是从队尾rear进入就像现实生活中的排队先来的就排在前面 (2)出队 从图中可以看出出队的顺序是A-B-C也就是入队的顺序即说明了队列是遵循FIFO的。队列的引用也十分广泛锁的实现、生产者-消费者模型等都离不开队列 队列也有两种实现方式顺序队列、链式队列 二、顺序队列 思路 在顺序队列中通常让队尾指针rear指向刚进队的元素的位置让队首指针 front 指向刚出队的元素的位置。因此元素进队的时候rear指针要向后移动元素出队的时候front指针也要向后移动。这样经过一系列的操作后两个指针最终会到达数组的末端处虽然队中已没有了元素但是仍然无法插入元素这就是所谓的“假溢出”。 为了解决假溢出的问题可以将数组弄成一个环状让 rear 和 front 指针沿着环走这样就不会出现无法继续走下去的情况这样就产生了循环队列如下图所示 : 队空状态 qu.rear qu.front 队满状态 (qu.rear 1) % Maxsize qu.front 元素的进队操作 qu.rear (qu.rear 1) % Maxsize ; qu.data[qu.rear] x ; 元素的出队操作 qu.front (qu.front 1) % Maxsize ; x qu.data[qu.front] ; 本次思路中 元素入队时先移动指针后存入元素元素出队时也是先移动指针后元素出队 步奏 1入队操作 int inQueue(Squeue qu,int x)
{//判断队列是否已满若满则无法入队if((qu.rear 1) % Maxsize qu.front){return 0;}//队列没有满则先移动指针在插入元素qu.rear (qu.rear 1) % Maxsize;qu.data[qu.rear] x;return 1;
}12345678910111213
2出队操作
int deQueue(Squeue qu,int x)
{//若队列已空则无法取出元素if(qu.front qu.rear){return 0;}//否则先移动指针再将元素取出qu.front (qu.front 1) % Maxsize;x qu.data[qu.front];return 1;
}12345678910111213
简单实现代码
//顺序队列
#include stdio.h
#include stdlib.h
#define Maxsize 20//定义队列的结构体
typedef struct Squeue{int data[Maxsize];int front;int rear;
}Squeue; //初始化队列
void InitQueue(Squeue qu)
{qu.front qu.rear 0;
}//判断队列是否为空
int isQueueEmpty(Squeue qu)
{if(qu.front qu.rear){return 1;}else{return 0;}
}//元素入队操作
int inQueue(Squeue qu,int x)
{//若队满则无法入队 if((qu.rear 1) % Maxsize qu.front){return 0;}qu.rear (qu.rear 1) % Maxsize;qu.data[qu.rear] x;return 1;
}//元素出队操作
int deQueue(Squeue qu,int x)
{//若队空则无法出队 if(qu.front qu.rear){return 0;}qu.front (qu.front 1) % Maxsize;x qu.data[qu.front];return 1;
}int main()
{Squeue q;int i , n , x , a;InitQueue(q);scanf(%d,n);for(i 0;i n;i){scanf(%d,a);inQueue(q,a);}//当队列非空时输出队列中所有数据 while(!isQueueEmpty(q)){deQueue(q,x);printf(%d ,x);}return 0;
}1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677
三、链式队列
以 模拟患者在医院等待就诊的情况为例子 实现链式队列
患者到达诊室将病历交给护士排到等待队列中候诊护士从等待队列中取出下一位患者的病历该患者进入诊室就诊功能如下 1排队 输入排队患者的病历号随机产生加入到就诊患者排队队列中 2就诊 患者队列中最前面的病人就诊并将其从队列中删除 3查看 从队首到队尾列出所有排队患者的病历号 4下班 退出运行 1声明
#includestdio.h
#includestdlib.h
#includestdbool.htypedef int ElementType;typedef struct Node{ElementType data; // 存放数据 struct Node *next; // 链表指针 }Node;typedef struct SeqQueue{Node *head; // 队列头部 Node *wei; // 队列尾巴 ElementType size; // 计算队列长度
}Seq; typedef struct SeqQueue* Queue; // 代表队列这个结构体指针1234567891011121314151617181920212223
2入队操作
// 创建链表存放数据
Node *Create_Link(ElementType data)
{Node * new (Node *)malloc(sizeof(Node)); // 开辟空间存数据 if(new NULL){printf(开辟空间失败\n);}new -data data; // 存放队列数据new -next NULL; // 让尾巴指向NULLreturn new; // 返回节点指针
}// 判断队列是否为空
bool QueueEmpty(Queue q) {if (q-head NULL)return true; // 队列为空return false;
}// 入队
Queue * Push(Queue sum,ElementType data)
{Node *LinkHead Create_Link(data); // 接收链表空间节点指针Queue p sum;if(QueueEmpty(p) true){p-head p-wei LinkHead; // 第一次赋值会进入 return p; // 返回值指向队列的头指针}else{p-wei-next LinkHead; // 让队尾next指针指向这个空间 p-wei LinkHead; // 队尾指针存入这个空间 }p-size; // 计算队伍长度
}
12345678910111213141516171819202122232425262728293031323334353637383940414243
3出队操作
// 出队
ElementType Pop(Queue q)
{ElementType count; // 取队列数据 Node *Link; if(QueueEmpty(q) true){printf(数据已经从队列出完\n);q-wei NULL;return -1;}Link q-head; // 让队列头给链表指针 count Link-data; // 链表头指针取出数据 q-head Link-next; // 让队列头指针移到链表头指针下一个节点位置并指向它 free(Link); // 释放已经出队的链表节点 return count; // 返回取出的数据
}123456789101112131415161718192021
4检查队列是否为空
// 判断队列是否为空
bool QueueEmpty(Queue q) {if (q-head NULL)return true; // 队列为空return false;
}12345678
全部代码
#includestdio.h
#includestdlib.h
#includestdbool.htypedef int ElementType;typedef struct Node{ElementType data; // 存放数据 struct Node *next; // 链表指针 }Node;typedef struct SeqQueue{Node *head; // 队列头部 Node *wei; // 队列尾巴 ElementType size; // 计算队列长度
}Seq; typedef struct SeqQueue* Queue;// 初始化队列
void Init_SeqQueue(Queue q)
{q-head NULL;q-wei NULL;q-size 0;
}// 创建链表存放数据
Node *Create_Link(ElementType data)
{Node * new (Node *)malloc(sizeof(Node)); // 开辟空间存数据 if(new NULL){printf(开辟空间失败\n);}new -data data; // 存放队列数据new -next NULL; // 让尾巴指向NULLreturn new; // 返回节点指针
}// 判断队列是否为空
bool QueueEmpty(Queue q) {if (q-head NULL)return true; // 队列为空return false;
}// 入队
Queue Push(Queue sum,ElementType data)
{Node *LinkHead Create_Link(data); // 接收链表空间节点指针Queue p sum;if(QueueEmpty(p) true){p-head p-wei LinkHead; // 第一次赋值会进入 return p; // 返回值指向队列的头指针}else{p-wei-next LinkHead; // 让队尾next指针指向这个空间 p-wei LinkHead; // 队尾指针存入这个空间 }p-size; // 计算队伍长度
}// 出队
ElementType Pop(Queue q)
{ElementType count; // 取队列数据 Node *Link; if(QueueEmpty(q) true){printf(数据已经从队列出完\n);q-wei NULL;return -1;}Link q-head; // 让队列头给链表指针 count Link-data; // 链表头指针取出数据 q-head Link-next; // 让队列头指针移到链表头指针下一个节点位置并指向它 free(Link); // 释放已经出队的链表节点 return count; // 返回取出的数据
}// 初始化菜单
void Init_Memu()
{printf(***********************************\n);printf(* 1.入队 *\n);printf(* 2.出队 *\n);printf(* 3.取队头元素 *\n);printf(* 4.查看队列是否为空 *\n);printf(* 5.插入队列(排队) *\n);printf(* 6.就诊 *\n);printf(* 7.查看 *\n);printf(* 8.下班 *\n);printf(***********************************\n);}//功能选择函数
ElementType Choose_GN()
{int flag;scanf(%d,flag);return flag;
}// 主函数
int main()
{Seq S_Queue; // 创建队列结构体对象 Init_SeqQueue(S_Queue); // 初始化队列 Queue q NULL; int temp;int num0;while(1){Init_Memu();printf(请选择你的需求:\n); temp Choose_GN();Node* p NULL;switch(temp){// 入队 case 1:{ElementType num;while(1){printf(请输入你要进队列的数据(输入0时结束输入):\n); scanf(%d,num);if( num 0){break;}q Push(S_Queue,num); // 接受队头指针head }}break;// 出队 case 2:{int flag;while(1){flag Pop(S_Queue);if(flag -1){printf(出队列完毕\n); break;}else{printf(出队数据为: %d\n,flag);}}}break;// 取队头元素 case 3:{ElementType sum;p q-head; // 取出队头指针 if( p NULL){printf(队伍已经出队没有数据\n);break;} sum p-data; // 队头指针取值 printf(队列头数据为: %d \n,sum);} break;// 查看队列是否为空 case 4:{if(QueueEmpty(q) true){printf(队伍为空\n);}else{printf(队伍还有数据,不为空\n); }}break;// 插入队列元素 case 5:{int s;printf(请输入你要添加到就诊队伍的病历号:\n);scanf(%d,s);q Push(q,s); // 把输入的数据插入队列中 printf(添加成功\n); } break;// 就诊 case 6:{ElementType count1;Node *Link1;Link1 q-head; // 取队头指针 count1 Link1-data; // 队头指针指向内容取值 q-head Link1-next; // 让队头指针移到下一个节点 free(Link1); // 释放刚才那个头节点printf(第%d 个患者开始就诊病历号为: %d\n,num,count1);if(QueueEmpty(q) true) // 判断队伍是否还有人 {printf(病人已经全部就诊完毕\n);break; }}break;// 查看相当于出队 case 7:{int flag1;int i0; while(1){flag1 Pop(S_Queue);if(flag1 -1){printf(查看完毕完毕\n); break;}else{printf(第%d 个患者病历号为: %d\n,i,flag1);}} }break;// 下班 case 8:printf(工作结束,打卡下班\n);exit(-1); // 结束进程 default:printf(选择功能错误请重新选择\n);break;}}return 0;
}
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261
学习笔记欢迎交流共同进步
