项目开发中经常使用循环队列,请制作可伸缩循环队列的静态库和动态库。至少包括以下功能: (1)创建循环队列; (2)入队和出队; (3)根据需要自动伸缩; (4)循环队列销毁。 编写测试程序对静态库和动态库进行测试。
时间: 2024-01-17 07:06:17 浏览: 30
好的,我可以为您提供一个可伸缩循环队列的静态库和动态库的实现,并且包括您所需的功能。以下是基本的代码实现:
```
// scalable_circular_queue.h
#ifndef SCALABLE_CIRCULAR_QUEUE_H
#define SCALABLE_CIRCULAR_QUEUE_H
#include <stdbool.h>
typedef struct {
int *data; // 队列数组指针
int front; // 队首指针
int rear; // 队尾指针
int size; // 当前队列大小
int capacity; // 当前队列容量
int capacity_max; // 队列最大容量
} SCQ;
// 创建一个可伸缩循环队列
SCQ *SCQ_create(int capacity_max);
// 销毁可伸缩循环队列
void SCQ_destroy(SCQ *scq);
// 入队
bool SCQ_enqueue(SCQ *scq, int value);
// 出队
int SCQ_dequeue(SCQ *scq);
#endif // SCALABLE_CIRCULAR_QUEUE_H
// scalable_circular_queue.c
#include "scalable_circular_queue.h"
#include <stdlib.h>
#define INIT_CAPACITY 8 // 初始容量
#define GROWTH_FACTOR 2 // 扩容因子
#define SHRINK_FACTOR 4 // 缩容因子
// 创建一个可伸缩循环队列
SCQ *SCQ_create(int capacity_max) {
SCQ *scq = (SCQ *)malloc(sizeof(SCQ));
scq->capacity = INIT_CAPACITY;
while (scq->capacity < capacity_max) {
scq->capacity *= GROWTH_FACTOR;
}
scq->data = (int *)malloc(scq->capacity * sizeof(int));
scq->capacity_max = capacity_max;
scq->front = 0;
scq->rear = 0;
scq->size = 0;
return scq;
}
// 销毁可伸缩循环队列
void SCQ_destroy(SCQ *scq) {
free(scq->data);
free(scq);
}
// 入队
bool SCQ_enqueue(SCQ *scq, int value) {
if (scq->size == scq->capacity) {
// 需要扩容
int new_capacity = scq->capacity * GROWTH_FACTOR;
if (new_capacity > scq->capacity_max) {
new_capacity = scq->capacity_max;
}
int *new_data = (int *)malloc(new_capacity * sizeof(int));
int i = 0;
while (scq->size--) {
new_data[i++] = scq->data[scq->front];
scq->front = (scq->front + 1) % scq->capacity;
}
scq->front = 0;
scq->rear = i;
scq->capacity = new_capacity;
free(scq->data);
scq->data = new_data;
}
scq->data[scq->rear] = value;
scq->rear = (scq->rear + 1) % scq->capacity;
scq->size++;
return true;
}
// 出队
int SCQ_dequeue(SCQ *scq) {
if (scq->size == 0) {
// 队列为空
return INT_MIN;
}
int value = scq->data[scq->front];
scq->front = (scq->front + 1) % scq->capacity;
scq->size--;
if (scq->size > 0 && scq->size == scq->capacity / SHRINK_FACTOR) {
// 需要缩容
int new_capacity = scq->capacity / GROWTH_FACTOR;
if (new_capacity < INIT_CAPACITY) {
new_capacity = INIT_CAPACITY;
}
int *new_data = (int *)malloc(new_capacity * sizeof(int));
int i = 0;
while (scq->size--) {
new_data[i++] = scq->data[scq->front];
scq->front = (scq->front + 1) % scq->capacity;
}
scq->front = 0;
scq->rear = i;
scq->capacity = new_capacity;
free(scq->data);
scq->data = new_data;
}
return value;
}
```
这里是一个简单的测试程序,用于测试可伸缩循环队列的静态库和动态库:
```
// test.c
#include "scalable_circular_queue.h"
#include <stdio.h>
int main() {
SCQ *scq = SCQ_create(100);
for (int i = 0; i < 100; i++) {
SCQ_enqueue(scq, i);
}
for (int i = 0; i < 100; i++) {
printf("%d ", SCQ_dequeue(scq));
}
printf("\n");
SCQ_destroy(scq);
return 0;
}
```
编译静态库的命令:
```
gcc -c scalable_circular_queue.c -o scalable_circular_queue.o
ar rcs libscq.a scalable_circular_queue.o
```
编译动态库的命令:
```
gcc -c -fPIC scalable_circular_queue.c -o scalable_circular_queue.o
gcc -shared -o libscq.so scalable_circular_queue.o
```
编译测试程序的命令:
```
gcc test.c -L. -lscq -o test
```
运行测试程序:
```
./test
```
请注意,这里只是一个基本的代码实现,您可以根据自己的需求进行修改和优化。