C语言中常见的数据结构及其代码实现
C语言中常见的数据结构及其代码实现
摘要：以下是C语言中常见的数据结构及其实现代码，包括队列、堆栈、单链表、双链表和二叉树。每种数据结构都包括基本的操作，如插入、删除等。
1. 队列 (Queue)队列是一种先进先出 (FIFO) 的数据结构。
#include
#include
#define MAX_SIZE 10
typedef struct {
int items[MAX_SIZE];
int front;
int rear;
} Queue;
void initialize(Queue *q) {
q->front = -1;
q->rear = -1;
}
int is_empty(Queue *q) {
return q->front == -1;
}
int is_full(Queue *q) {
return q->rear == MAX_SIZE - 1;
}
void enqueue(Queue *q, int value) {
if (is_full(q)) {
printf("Queue is full\n");
return;
}
if (is_empty(q)) {
q->front = 0;
}
q->rear++;
q->items[q->rear] = value;
}
int dequeue(Queue *q) {
int item;
if (is_empty(q)) {
printf("Queue is empty\n");
return -1;
}
item = q->items[q->front];
q->front++;
if (q->front > q->rear) {
initialize(q);
}
return item;
}
int main() {
Queue q;
initialize(&q);
enqueue(&q, 1);
enqueue(&q, 2);
printf("%d\n", dequeue(&q)); // 输出 1
printf("%d\n", dequeue(&q)); // 输出 2
return 0;
}
2. 堆栈 (Stack)堆栈是一种后进先出 (LIFO) 的数据结构。
#include
#include
#define MAX_SIZE 10
typedef struct {
int items[MAX_SIZE];
int top;
} Stack;
void initialize(Stack *s) {
s->top = -1;
}
int is_empty(Stack *s) {
return s->top == -1;
}
int is_full(Stack *s) {
return s->top == MAX_SIZE - 1;
}
void push(Stack *s, int value) {
if (is_full(s)) {
printf("Stack is full\n");
return;
}
s->top++;
s->items[s->top] = value;
}
int pop(Stack *s) {
int item;
if (is_empty(s)) {
printf("Stack is empty\n");
return -1;
}
item = s->items[s->top];
s->top--;
return item;
}
int main() {
Stack s;
initialize(&s);
push(&s, 1);
push(&s, 2);
printf("%d\n", pop(&s)); // 输出 2
printf("%d\n", pop(&s)); // 输出 1
return 0;
}
3. 单链表 (Singly Linked List)单链表是一种线性数据结构，其中每个节点包含一个数据项和一个指向下一个节点的指针。
#include
#include
typedef struct Node {
int data;
struct Node *next;
} Node;
Node* create_node(int data) {
Node *new_node = (Node*)malloc(sizeof(Node));
if (new_node == NULL) {
printf("Memory allocation failed\n");
return NULL;
}
new_node->data = data;
new_node->next = NULL;
return new_node;
}
void insert_at_beginning(Node **head, int data) {
Node *new_node = create_node(data);
if (new_node == NULL) return;
new_node->next = *head;
*head = new_node;
}
void insert_at_end(Node **head, int data) {
Node *new_node = create_node(data);
if (new_node == NULL) return;
if (*head == NULL) {
*head = new_node;
return;
}
Node *current = *head;
while (current->next != NULL) {
current = current->next;
}
current->next = new_node;
}
void delete_node(Node **head, int data) {
if (*head == NULL) return;
if ((*head)->data == data) {
Node *temp = *head;
*head = (*head)->next;
free(temp);
return;
}
Node *current = *head;
while (current->next != NULL && current->next->data != data) {
current = current->next;
}
if (current->next == NULL) return;
Node *temp = current->next;
current->next = current->next->next;
free(temp);
}
void print_list(Node *head) {
Node *current = head;
while (current != NULL) {
printf("%d -> ", current->data);
current = current->next;
}
printf("NULL\n");
}
int main() {
Node *head = NULL;
insert_at_end(&head, 1);
insert_at_end(&head, 2);
insert_at_beginning(&head, 0);
print_list(head); // 输出 0 -> 1 -> 2 -> NULL
delete_node(&head, 1);
print_list(head); // 输出 0 -> 2 -> NULL
return 0;
}
4. 双链表 (Doubly Linked List)双链表是一种线性数据结构，其中每个节点包含一个数据项和两个指针，一个指向前一个节点，一个指向后一个节点。
#include
#include
typedef struct Node {
int data;
struct Node *prev;
struct Node *next;
} Node;
Node* create_node(int data) {
Node *new_node = (Node*)malloc(sizeof(Node));
if (new_node == NULL) {
printf("Memory allocation failed\n");
return NULL;
}
new_node->data = data;
new_node->prev = NULL;
new_node->next = NULL;
return new_node;
}
void insert_at_beginning(Node **head, int data) {
Node *new_node = create_node(data);
if (new_node == NULL) return;
new_node->next = *head;
if (*head != NULL) {
(*head)->prev = new_node;
}
*head = new_node;
}
void insert_at_end(Node **head, int data) {
Node *new_node = create_node(data);
if (new_node == NULL) return;
if (*head == NULL) {
*head = new_node;
return;
}
Node *current = *head;
while (current->next != NULL) {
current = current->next;
}
current->next = new_node;
new_node->prev = current;
}
void delete_node(Node **head, int data) {
if (*head == NULL) if ((*head)->data == data) {
Node *temp = *head;
*head = (*head)->next;
if (*head != NULL) {
(*head)->prev = NULL;
}
free(temp);
return;
}
Node *current = *head;
while (current != NULL && current->data != data) {
current = current->next;
}
if (current == NULL) return;
if (current->next != NULL) {
current->next->prev = current->prev;
}
if (current->prev != NULL) {
current->prev->next = current->next;
}
free(current);
}
void print_list(Node *head) {
Node *current = head;
while (current != NULL) {
printf("%d ", current->data);
current = current->next;
}
printf("NULL\n");
}
int main() {
Node *head = NULL;
insert_at_end(&head, 1);
insert_at_end(&head, 2);
insert_at_beginning(&head, 0);
print_list(head); // 输出 0 1 2 NULL
delete_node(&head, 1);
print_list(head); // 输出 0 2 NULL
return 0;
}
5. 二叉树 (Binary Tree)二叉树是一种树形数据结构，其中每个节点最多有两个子节点，分别称为左子节点和右子节点。
#include
#include
typedef struct Node {
int data;
struct Node *left;
struct Node *right;
} Node;
Node* create_node(int data) {
Node *new_node = (Node*)malloc(sizeof(Node));
if (new_node == NULL) {
printf("Memory allocation failed\n");
return NULL;
}
new_node->data = data;
new_node->left = NULL;
new_node->right = NULL;
return new_node;
}
void insert(Node **root, int data) {
if (*root == NULL) {
*root = create_node(data);
return;
}
if (data data) {
insert(&((*root)->left), data);
} else if (data > (*root)->data) {
insert(&((*root)->right), data);
}
}
void inorder_traversal(Node *root) {
if (root != NULL) {
inorder_traversal(root->left);
printf("%d ", root->data);
inorder_traversal(root->right);
}
}
void preorder_traversal(Node *root) {
if (root != NULL) {
printf("%d ", root->data);
preorder_traversal(root->left);
preorder_traversal(root->right);
}
}
void postorder_traversal(Node *root) {
if (root != NULL) {
postorder_traversal(root->left);
postorder_traversal(root->right);
printf("%d ", root->data);
}
}
int main() {
Node *root = NULL;
insert(&root, 5);
insert(&root, 3);
insert(&root, 7);
insert(&root, 1);
insert(&root, 9);
printf("Inorder traversal: ");
inorder_traversal(root); // 输出 1 3 5 7 9
printf("\n");
printf("Preorder traversal: ");
preorder_traversal(root); // 输出 5 3 1 7 9
printf("\n");
printf("Postorder traversal: ");
postorder_traversal(root); // 输出 1 3 9 7 5
printf("\n");
return 0;
}
上面这些代码展示了如何在C语言中实现常见的数据结构，并提供了基本的操作方法。