链式队列----用链表实现,链式队列就是一个操作受限的单向链表,如果读者了解单向链表的建立过程,那理解链式队列就很容易了,先回顾一下单向链表的建立过程
(不熟悉单向链表的可以先看看另一片随笔,再回来看链式队列理解起来更容易☺链表(单向链表的建立、删除、插入、打印)https://www.linuxidc.com/Linux/2019-08/159766.htm
单向链表
单向链表节点的组成部分
1 struct link
2 {
3 int data;
4 struct link *next;
5 };
数据域:data----用来存储节点数据
指针域:struct link *next----用来存储下一个节点的地址
链式队列和单向链表比就多了两个指针,头指针和尾指针(这里我多加了一个length来记录队列的长度)
typedef struct QNode /* 声明链式队列的结点 */
{
int data;
struct QNode *next;
}Node;
typedef struct QueuePoint /* 声明链式队列的首尾指针 */
{
Node *front;
Node *rear;
int length; /* 记录链式队列长度 */
}Queue;
后面就是单向链表的建立了,这里就不再赘述了,重点分析下头指针的尾指针的移动,为了方便理解先附上main函数部分的代码
main()
{
int i = 0;
char c;
Queue q; //链式队列首尾指针 和 长度
q.front = q.rear = NULL; /* 首尾指针初始化 */
q.length = 0; /* 链式队列长度初始化 */
q = init(q); /* 初始化队列 */
printf("Do you want to append a new node(Y/N)?");
scanf_s(" %c", &c);
while (c == 'Y' || c == 'y')
{
q = AppendNode(q); /* 入队*/
DisplyNode(q); /* 按先进先出对队列进行打印 */
printf("Do you want to append a new node(Y/N)?");
scanf_s(" %c", &c);
}
printf("Do you want to delete node(Y/N)?");
scanf_s(" %c", &c);
while (c == 'Y' || c == 'y')
{
q = DeletNode(q);
DisplyNode(q);
printf("Do you want to delete node(Y/N)?");
scanf_s(" %c", &c);
}
return 0;
}
下面上图
(灵魂画手已上线)
简单描述一下上图的步骤
第一步:初始化队列(就是添加一个头节点在队列中),头结点不存储数据,使队首指针和队尾指针都指向头结点
第二步:入队(添加节点),使队尾指针指向头新建的节点,队首指针不变仍然指向头结点
初始化队列和入队----实现代码
//函数功能:初始化队列(其实就是搞个头结点放在队列里面)
//单独弄个子函数来初始化队列是为了方便入队的时候判断队列是否为空
Queue init (Queue p)
{
p.front = p.rear = (Node *)malloc(sizeof(Node));
if (p.front == NULL && p.rear == NULL)
{
printf("initialization failed");
exit(0);
}
p.front->next = NULL;
return p;
}
//函数功能:新建节点并添加到队列中,记录队列长度
Queue AppendNode (Queue p)
{
int data;
Node *q;
q = (Node *)malloc(sizeof(Node));
if (q == NULL) /* 判断分配内存是否失败 */
{
printf("No enough memory to allocate");
exit(0);
}
p.rear->next = q; /* 最后一个节点的指针指向新建节点*/
p.rear = q; /* 队尾指针指向新建节点*/
printf("Input node data\n");
scanf("%d", &data);
p.rear->data = data;
p.rear->next = NULL;
p.length++;
return p;
}
后面来分析下出队时首尾指针的变化,因为后面出队时要用到判断队列是否为空的一个子函数,这里先附上子函数代码