C语言圆环结构及相关函数实现124

在C语言中，并没有直接的“圆环”数据结构。但是，我们可以通过多种方法模拟和实现圆环结构，并在此基础上编写相应的函数来操作它。本文将详细介绍几种实现C语言圆环结构的方法，以及相关的函数，包括创建、插入、删除、查找等操作。

一、基于循环链表实现圆环

循环链表是最常见且最有效的模拟圆环结构的方法。在循环链表中，最后一个节点的指针指向第一个节点，形成一个闭环。这种结构天然地适合表示圆环。

首先，我们需要定义一个节点结构体：```c
typedef struct Node {
int data;
struct Node *next;
} Node;
```

然后，我们可以实现创建圆环链表的函数：```c
Node* createCircularList(int data[]) {
int n = sizeof(data) / sizeof(data[0]); // 错误，sizeof(data)会返回指针大小
if (n data = data[0];
head->next = head; // 首尾相连
Node *current = head;
for (int i = 1; i < n; i++) {
Node *newNode = (Node*)malloc(sizeof(Node));
newNode->data = data[i];
newNode->next = head; //所有节点的next都指向head
current->next = newNode;
current = newNode;
}
return head;
}
```

注意：上述代码中 `sizeof(data)` 的用法是错误的，因为 `data` 是一个数组指针，`sizeof(data)` 返回的是指针大小，而不是数组大小。正确的做法是预先知道数组大小或者在函数参数中传入数组大小。以下是一个更正后的版本，通过传入数组大小：

```c
Node* createCircularList(int data[], int n) {
if (n data = data[0];
head->next = head;
Node *current = head;
for (int i = 1; i < n; i++) {
Node *newNode = (Node*)malloc(sizeof(Node));
if (newNode == NULL) {
//释放已分配的内存，避免内存泄漏
while (current != head){
Node* temp = current;
current = current->next;
free(temp);
}
free(head);
return NULL;
}
newNode->data = data[i];
newNode->next = head;
current->next = newNode;
current = newNode;
}
return head;
}
```

接下来，我们可以实现插入、删除和查找节点的函数。这些函数的实现需要考虑循环链表的特殊性，确保操作后链表仍然保持循环。```c
// 在指定节点后插入新节点
void insertNode(Node *prev, int data) {
Node *newNode = (Node*)malloc(sizeof(Node));
newNode->data = data;
newNode->next = prev->next;
prev->next = newNode;
}
// 删除指定节点
void deleteNode(Node *head, Node *nodeToDelete) {
if (nodeToDelete == NULL || head == NULL) return;
Node *current = head;
while (current->next != nodeToDelete && current->next != head) {
current = current->next;
}
if (current->next == nodeToDelete) {
current->next = nodeToDelete->next;
free(nodeToDelete);
}
}
// 查找值为data的节点
Node* findNode(Node *head, int data) {
Node *current = head;
do {
if (current->data == data) {
return current;
}
current = current->next;
} while (current != head);
return NULL;
}
// 打印圆环链表
void printCircularList(Node *head) {
if (head == NULL) return;
Node *current = head;
do {
printf("%d ", current->data);
current = current->next;
} while (current != head);
printf("");
}
//释放所有节点内存
void freeCircularList(Node* head){
if(head == NULL) return;
Node* current = head;
Node* next;
do{
next = current->next;
free(current);
current = next;
}while(current != head);
}
```

二、基于数组实现圆环

另一种实现圆环的方法是使用数组。我们可以用数组的下标模拟节点的顺序，并用模运算来实现循环。```c
#define MAX_SIZE 100
typedef struct {
int data[MAX_SIZE];
int head;
int tail;
int size;
} CircularArray;
//初始化圆环数组
void initCircularArray(CircularArray *arr) {
arr->head = 0;
arr->tail = -1;
arr->size = 0;
}
//插入元素
void insertCircularArray(CircularArray *arr, int data) {
if (arr->size == MAX_SIZE) return; // 数组已满
arr->tail = (arr->tail + 1) % MAX_SIZE;
arr->data[arr->tail] = data;
arr->size++;
if (arr->size == 1) arr->head = arr->tail;
}
//删除元素
int deleteCircularArray(CircularArray *arr) {
if (arr->size == 0) return -1; // 数组为空
int data = arr->data[arr->head];
arr->head = (arr->head + 1) % MAX_SIZE;
arr->size--;
if (arr->size == 0) arr->tail = -1; // 数组为空
return data;
}
//打印圆环数组
void printCircularArray(CircularArray *arr) {
if (arr->size == 0) return;
int i = arr->head;
for (int j = 0; j < arr->size; j++) {
printf("%d ", arr->data[i]);
i = (i + 1) % MAX_SIZE;
}
printf("");
}
```