C语言单链队列的表示与实现实例详解
什么是队列？
在计算机科学中，队列（Queue）是一种特殊的数据结构，它只允许在一端进行插入操作，在另一端进行删除操作。将新元素插入队列的过程可以称之为入队，而将元素从队列中删除的过程则可以称之为出队。队列的核心思想是“先进先出”（First In First Out，FIFO），即先入队的元素先出队。
单链队列的表示方式
单链队列（Linked Queue）是一种基于链表的队列实现方式，它由若干个结点构成，每个结点至少需要包含两个部分：数据域和指针域。数据域用于存储实际数据，指针域则用于指向下一个结点。在单链队列中，队首指针指向链表头结点，队尾指针则指向链表尾结点。
单链队列的基本操作包括以下几个方面：
- 初始化队列
- 判断队列是否为空
- 获取队列长度
- 入队操作
- 出队操作
- 清空队列
- 销毁队列
下面根据C语言代码实现这些操作。
单链队列的初始化操作
typedef struct QueueNode {
int data; // 数据域
struct QueueNode *next; // 指针域
} QueueNode, *QueueNodePtr;
typedef struct {
QueueNodePtr front; // 队首指针
QueueNodePtr rear; // 队尾指针
int length; // 队列长度
} LinkedQueue;
// 初始化队列
void initQueue(LinkedQueue *queue) {
queue->front = queue->rear = (QueueNodePtr) malloc(sizeof(QueueNode));
if (NULL == queue->front) {
exit(1); // 内存分配失败，退出程序
}
queue->front->next = NULL; // 队列为空，指向空指针
queue->length = 0;
}
在队列初始化时，我们需要分配一个头结点，同时将队首和队尾指针都指向这个头结点，表示队列空。由于初始化操作有可能分配失败，因此需要进行内存异常处理。
单链队列的入队操作
// 入队操作
void enQueue(LinkedQueue *queue, int data) {
QueueNodePtr p;
p = (QueueNodePtr) malloc(sizeof(QueueNode));
if (NULL == p) {
exit(1); // 内存分配失败，退出程序
}
p->data = data;
p->next = NULL;
queue->rear->next = p;
queue->rear = p;
queue->length++;
}
在入队操作中，我们需要新建一个结点，为其赋值后再插入到队列的尾部。为此需要指针操作，将尾指针指向新结点即可。同时还需要维护队列长度变量。
单链队列的出队操作
// 出队操作
int deQueue(LinkedQueue *queue) {
int data;
QueueNodePtr p;
if (queue->front == queue->rear) {
printf("队列为空\n");
exit(1);
}
p = queue->front->next;
data = p->data;
queue->front->next = p->next; // 将头结点的指针指向下一个结点
if (queue->rear == p) { // 最后一个结点出队，需要更新队尾指针
queue->rear = queue->front;
}
free(p);
queue->length--;
return data;
}
在出队操作中，我们需要先判断队列是否为空。如果不为空，我们需要获取队列头结点的下一个结点，并将头结点的指针指向这个结点即可。如果出队的是队列中唯一的结点，则需要同时更新队首和队尾指针。
示例1：用单链队列求解斐波那契数列
下面我们来看一个具体的示例，在这个例子中，我们将使用单链队列来求解斐波那契数列。
斐波那契数列是指这样一个数列：0、1、1、2、3、5、8、13、21、34、…… 它从第三项开始，每一项都等于前两项之和，即 f(n) = f(n-1) + f(n-2)。用数学公式来表示，就是：
f(0) = 0
f(1) = 1
f(n) = f(n-1) + f(n-2) , n>=2
我们可以定义一个单链队列来保存前两个数，然后循环计算下一个数，并将其加入到队列中，直至计算出需要的数。
以下是用单链队列求解斐波那契数列的C语言代码：
// 用单链队列求解斐波那契数列
void fibonacciByLinkedQueue(int n) {
LinkedQueue queue;
initQueue(&queue);
enQueue(&queue, 0);
enQueue(&queue, 1);
for (int i = 0; i < n; i++) {
int x = deQueue(&queue);
int y = deQueue(&queue);
printf("%d ", x);
enQueue(&queue, y);
enQueue(&queue, x+y);
}
printf("\n");
clearQueue(&queue);
}
这个例子中，我们需要初始化一个队列，并将前两个斐波那契数列中的值入队。然后在循环中计算下一个数，同时将新计算出来的数加入到队列中即可。
示例2：用单链队列解决迷宫问题
下面我们来看另一个例子，它展示了单链队列在解决迷宫问题时的应用。
在迷宫问题中，我们需要遍历迷宫的所有路径，并找到从起点到终点的一条路径。这个过程可以使用深度优先搜索算法来实现。当然，我们也可以使用广度优先搜索算法来解决这个问题。
广度优先搜索算法使用队列来进行遍历，具体实现方式是：先将起点入队，然后每次出队一个节点，检查它的邻居是否可以到达终点，如果可以就入队，如果不行就弹出继续遍历下一个节点，直至遇到终点。
以下是用单链队列解决迷宫问题的C语言代码：
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define ROW 8
#define COL 8
typedef struct Point {
int x;
int y;
} Point;
// 定义迷宫的矩阵
int map[ROW][COL] = {
{0, 0, 0, 0, 0, 0, 0, 0},
{0, 1, 1, 0, 1, 1, 1, 0},
{0, 1, 1, 0, 1, 1, 1, 0},
{0, 1, 1, 1, 1, 0, 0, 1},
{0, 1, 0, 0, 0, 1, 1, 1},
{0, 1, 1, 1, 0, 1, 1, 1},
{0, 1, 0, 1, 1, 1, 0, 0},
{0, 1, 1, 1, 0, 1, 1, 0}
};
// 定义单链队列的结构体
typedef struct QueueNode {
Point data;
struct QueueNode *next;
} QueueNode, *QueueNodePtr;
typedef struct {
QueueNodePtr front;
QueueNodePtr rear;
int length;
} LinkedQueue;
// 初始化队列
void initQueue(LinkedQueue *queue) {
queue->front = queue->rear = (QueueNodePtr) malloc(sizeof(QueueNode));
if (NULL == queue->front) {
exit(1);
}
queue->front->next = NULL;
queue->length = 0;
}
// 入队操作
void enQueue(LinkedQueue *queue, Point data) {
QueueNodePtr p;
p = (QueueNodePtr) malloc(sizeof(QueueNode));
if (NULL == p) {
exit(1);
}
p->data = data;
p->next = NULL;
queue->rear->next = p;
queue->rear = p;
queue->length++;
}
// 出队操作
Point deQueue(LinkedQueue *queue) {
Point data;
QueueNodePtr p;
if (queue->length == 0) {
printf("队列为空\n");
exit(1);
}
p = queue->front->next;
data = p->data;
queue->front->next = p->next;
if (queue->rear == p) {
queue->rear = queue->front;
}
free(p);
queue->length--;
return data;
}
// 判断是否越界
int isOutOfBounds(int x, int y) {
if (x < 0 || x >= ROW || y < 0 || y >= COL) {
return 1;
}
return 0;
}
// 判断当前点是否为终点
int isEndpoint(Point point) {
return point.x == 6 && point.y == 7;
}
// 判断是否为障碍物
int isObstacle(Point point) {
return map[point.x][point.y] == 1;
}
// 解决迷宫问题
void mazeSolution() {
LinkedQueue queue;
initQueue(&queue);
Point start = {1, 0};
Point end = {6, 7};
enQueue(&queue, start);
int book[ROW][COL]; // 记录每个点是否被走过
memset(book, 0, ROW*COL*sizeof(int)); // 初始化为0
int next[4][2] = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}}; // 右、左、下、上
while (queue.length > 0) {
Point current = deQueue(&queue);
if (isEndpoint(current)) {
printf("解：%d,%d\n", current.x, current.y);
int x = current.x;
int y = current.y;
while (x != start.x || y != start.y) {
// 逆推路径
for (int i = 0; i < 4; i++) {
int tx = x - next[i][0];
int ty = y - next[i][1];
if (!isOutOfBounds(tx, ty) && book[tx][ty] == book[x][y]-1) {
printf("解：%d,%d\n", tx, ty);
x = tx;
y = ty;
break;
}
}
}
clearQueue(&queue);
return;
}
for (int i = 0; i < 4; i++) {
int nx = current.x + next[i][0];
int ny = current.y + next[i][1];
Point nextPoint = {nx, ny};
if (!isOutOfBounds(nx, ny) && !isObstacle(nextPoint) && book[nx][ny] == 0) {
book[nx][ny] = book[current.x][current.y] + 1;
enQueue(&queue, nextPoint);
}
}
}
printf("无解\n");
clearQueue(&queue);
}
int main() {
mazeSolution();
return 0;
}
这个例子中，我们使用单链队列来实现广度优先搜索算法，求解迷宫问题。其中需要用到元素类型为Point的队列，因此需要在队列中进行相应的修改。通过遍历矩阵中的每个点，我们可以找到从起点到终点的一条路径。在遍历过程中，我们需要注意的是先入队后出队，同时在每个点上将路径距离的长度记录下来，以便之后回推路径。
以上代码可能有些长，但只要代码实现细节都注意到位，就可以很好地解决相关问题。
本站文章如无特殊说明，均为本站原创，如若转载，请注明出处：C语言单链队列的表示与实现实例详解 - Python技术站
微信扫一扫 
支付宝扫一扫 