队列（Queue）的知识点：「概念」：队列是一种先进先出（FIFO）的数据结构，类似于排队的概念。「基本操作」：enqueue(item): 将元素添加到队列的末尾。dequeue(): 从队列的头部移除并返回元素。isEmpty(): 检查队列是否为空。size(): 返回队列中元素的数量。「代码示例」：#include <stdio.h>
#include <stdlib.h>
#define MAX_SIZE 100
typedef struct {
int items[MAX_SIZE];
int front;
int rear;
} Queue;
void enqueue(Queue *q, int item) {
if (q->rear == MAX_SIZE - 1) {
printf("Queue is full\n");
return;
}
q->items[++(q->rear)] = item;
}
int dequeue(Queue *q) {
if (q->front > q->rear) {
printf("Queue is empty\n");
exit(1);
}
return q->items[(q->front)++];
}
int isEmpty(Queue *q) {
return q->front > q->rear;
}
int size(Queue *q) {
return q->rear - q->front + 1;
}
int main() {
Queue q = {{0}, -1, -1};
enqueue(&q, 1);
enqueue(&q, 2);
enqueue(&q, 3);
printf("%d\n", dequeue(&q)); // 输出：1
printf("%d\n", size(&q)); // 输出：2
return 0;
}
优先级队列（Priority Queue）的知识点：「概念」：优先级队列是一种队列，每个元素都有一个优先级。具有最高优先级的元素先出队。「基本操作」：insert(item, priority): 将元素以及其优先级插入队列。extractMax(): 返回具有最高优先级的元素并将其从队列中移除。isEmpty(): 检查队列是否为空。size(): 返回队列中元素的数量。「代码示例」：#include <stdio.h>
#include <stdlib.h>
typedef struct {
int priority;
int data;
} Node;
typedef struct {
Node *nodes;
int capacity;
int size;
} PriorityQueue;
PriorityQueue* createPriorityQueue(int capacity) {
PriorityQueue *pq = (PriorityQueue*)malloc(sizeof(PriorityQueue));
pq->nodes = (Node*)malloc(capacity * sizeof(Node));
pq->capacity = capacity;
pq->size = 0;
return pq;
}
void insert(PriorityQueue *pq, int data, int priority) {
if (pq->size == pq->capacity) {
printf("Priority Queue is full\n");
return;
}
int i = pq->size;
while (i > 0 && pq->nodes[(i - 1) / 2].priority < priority) {
pq->nodes[i] = pq->nodes[(i - 1) / 2];
i = (i - 1) / 2;
}
pq->nodes[i].data = data;
pq->nodes[i].priority = priority;
pq->size++;
}
int extractMax(PriorityQueue *pq) {
if (pq->size == 0) {
printf("Priority Queue is empty\n");
exit(1);
}
int max = pq->nodes[0].data;
pq->size--;
int i = 0;
Node lastNode = pq->nodes[pq->size];
int child;
while (2 * i + 1 < pq->size) {
child = 2 * i + 1;
if (child + 1 < pq->size && pq->nodes[child + 1].priority > pq->nodes[child].priority) {
child++;
}
if (lastNode.priority >= pq->nodes[child].priority) {
break;
}
pq->nodes[i] = pq->nodes[child];
i = child;
}
pq->nodes[i] = lastNode;
return max;
}
int isEmpty(PriorityQueue *pq) {
return pq->size == 0;
}
int size(PriorityQueue *pq) {
return pq->size;
}
int main() {
PriorityQueue *pq = createPriorityQueue(5);
insert(pq, 1, 3);
insert(pq, 2, 1);
insert(pq, 3, 5);
printf("%d\n", extractMax(pq)); // 输出：3
printf("%d\n", size(pq)); // 输出：2
return 0;
} |
楼主
标题置顶
标题高亮
