应用:广搜
总结:链表总的来说比较灵活,普通的顺序表有一头是固定的,因此对于队列这种两端都存在数据变化的情况,使用链表实现会比较自然,而使用顺序表实现则要用循环队列的方式来弥补普通顺序表的不足。
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define COLOR(a, b) "\033[" #b "m" a "\033[0m"
#define RED(a) COLOR(a, 31)
#define GREEN(a) COLOR(a, 32)
//结构定义:队列(顺序表)
typedef struct Queue {
int *data;
int head, tail, size, length;
} Queue;
//结构操作
Queue *init(int size);
void clear(Queue *que);
int expand(Queue *que);
int push(Queue *que, int val);
int front(Queue *que);
int empty(Queue *que);
int pop(Queue *que);
void output(Queue *que);
int main() {
srand(time(0));
#define MAX_N 20
Queue *que = init(1);
for (int i = 0; i < MAX_N; i++) {
int op = rand() % 4;
int val = rand() % 100;
switch (op) {
case 0:
case 1:
case 2: {
printf("push %d to the Queue = %d\n", val, push(que, val));
} break;
case 3: {
if (empty(que)) {
printf("pop from the Queue = 0\n");
} else {
printf("pop %d from the Queue = ", front(que));
printf("%d\n", pop(que));
}
} break;
}
output(que), printf("\n");
}
#undef MAX_N
clear(que);
return 0;
}
//结构操作:初始化队列
Queue *init(int size) {
Queue *que = (Queue *)malloc(sizeof(Queue));
que->data = (int *)malloc(sizeof(int) * size);
que->head = que->tail = que->length = 0;
que->size = size;
return que;
}
//结构操作:销毁队列
void clear(Queue *que) {
if (que == NULL) return;
free(que->data);
free(que);
return;
}
//结构操作:队列扩容
int expand(Queue *que) {
int extra_size = que->size;
int *temp;
while (extra_size) {
temp = (int *)malloc(sizeof(int) * (que->size + extra_size));
if (temp != NULL) break;
extra_size >>= 1;
}
if (temp == NULL) return 0;
for (int i = 0; i < que->length; i++) {
temp[i] = que->data[(que->head + i) % que->size];
}
free(que->data);
que->data = temp;
que->head = 0;
que->tail = que->length;
que->size += extra_size;
return 1;
}
//结构操作:入队
int push(Queue *que, int val) {
if (que == NULL) return 0;
if (que->length == que->size) {
if (!expand(que)) {
printf(RED("fail to expand!\n"));
return 0;
}
printf(GREEN("success to expand! the new size = %d\n"), que->size);
}
que->data[que->tail++] = val;
if (que->tail == que->size) que->tail = 0;
que->length += 1;
return 1;
}
//结构操作:访问队首元素
int front(Queue *que) {
return que->data[que->head];
}
//结构操作:队列判空
int empty(Queue *que) {
return que->length == 0;
}
//结构操作:出队
int pop(Queue *que) {
if (que == NULL) return 0;
if (empty(que)) return 0;
que->head += 1;
if (que->head == que->size) que->head = 0;
que->length -= 1;
return 1;
}
//结构操作:输出所有元素
void output(Queue *que) {
printf("Queue(%d): [", que->length);
for (int i = 0; i < que->length; i++) {
i && printf(", ");
printf("%d", que->data[(que->head + i) % que->size]);
}
printf("]\n");
return;
}
链队列
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define COLOR(a, b) "\033[" #b "m" a "\033[0m"
#define RED(a) COLOR(a, 31)
#define GREEN(a) COLOR(a, 32)
//结构定义:链表节点
typedef struct Node {
int data;
Node *next;
} Node;
//结构定义:队列(链表)
typedef struct Queue {
Node head, *tail; // 定义虚拟头节点 (index = -1) for 入队时可以统一操作
int length;
} Queue;
//结构操作
Node *getNewNode(int val);
Queue *init();
void clear_node(Node *node);
void clear(Queue *que);
int push(Queue *que, int val);
int front(Queue *que);
int empty(Queue *que);
int pop(Queue *que);
void output(Queue *que);
int main() {
srand(time(0));
#define MAX_N 20
Queue *que = init();
for (int i = 0; i < MAX_N; i++) {
int op = rand() % 4;
int val = rand() % 100;
switch (op) {
case 0:
case 1:
case 2: {
printf("push %d to the Queue = %d\n", val, push(que, val));
} break;
case 3: {
if (empty(que)) {
printf("pop from the Queue = 0\n");
} else {
printf("pop %d from the Queue = ", front(que));
printf("%d\n", pop(que));
}
} break;
}
output(que), printf("\n");
}
#undef MAX_N
clear(que);
return 0;
}
//结构操作:获得一个新节点
Node *getNewNode(int val) {
Node *node = (Node *)malloc(sizeof(Node));
node->data = val;
node->next = NULL;
return node;
}
//结构操作:初始化队列
Queue *init() {
Queue *que = (Queue *)malloc(sizeof(Queue));
que->head.next = NULL;
que->tail = &(que->head);
que->length = 0;
return que;
}
//结构操作:释放一个节点
void clear_node(Node *node) {
if (node == NULL) return;
free(node);
return;
}
//结构操作:销毁队列
void clear(Queue *que) {
if (que == NULL) return;
Node *node = que->head.next, *post_node;
while (node != NULL) {
post_node = node->next;
clear_node(node);
node = post_node;
}
free(que);
return;
}
//结构操作:入队
int push(Queue *que, int val) {
if (que == NULL) return 0;
Node *node = getNewNode(val);
que->tail->next = node;
que->tail = node;
que->length += 1;
return 1;
}
//结构操作:访问队首元素
int front(Queue *que) {
return que->head.next->data;
}
//结构操作:队列判空
int empty(Queue *que) {
return que->length == 0;
}
//结构操作:出队
int pop(Queue *que) {
if (que == NULL) return 0;
if (empty(que)) return 0;
Node *node = que->head.next;
que->head.next = node->next;
clear_node(node);
que->length -= 1;
if (que->length == 0) que->tail = &(que->head);
return 1;
}
//结构操作:输出所有元素
void output(Queue *que) {
printf("Queue(%d): [", que->length);
for (Node *node = que->head.next; node != NULL; node = node->next) {
node != que->head.next && printf(", ");
printf("%d", node->data);
}
printf("]\n");
return;
}
标签:node,return,队列,Queue,int,que,size
From: https://www.cnblogs.com/Kelvin-Wu/p/16795297.html