C语言实现常见的数据结构

栈

栈是一种后进先出（LIFO, Last In First Out）的数据结构

#include <stdio.h>
#include <stdlib.h>#define MAX 100typedef struct {int data[MAX];int top;
} Stack;// 初始化栈
void init(Stack *s) {s->top = -1;
}// 判断栈是否为空
int isEmpty(Stack *s) {return s->top == -1;
}// 判断栈是否满
int isFull(Stack *s) {return s->top == MAX - 1;
}// 入栈
void push(Stack *s, int value) {if (isFull(s)) {printf("Stack overflow!\n");return;}s->data[++s->top] = value;
}// 出栈
int pop(Stack *s) {if (isEmpty(s)) {printf("Stack underflow!\n");exit(1);}return s->data[s->top--];
}// 打印栈
void printStack(Stack *s) {for (int i = 0; i <= s->top; i++) {printf("%d ", s->data[i]);}printf("\n");
}int main() {Stack s;init(&s);push(&s, 10);push(&s, 20);push(&s, 30);printStack(&s);pop(&s);printStack(&s);return 0;
}

队列

队列是一种先进先出（FIFO, First In First Out）的数据结构。

循环队列

#include <stdio.h>
#include <stdlib.h>#define MAX 100typedef struct {int data[MAX];int front;int rear;
} Queue;// 初始化队列
void init(Queue *q) {q->front = 0;q->rear = 0;
}// 判断队列是否为空
int isEmpty(Queue *q) {return q->front == q->rear;
}// 判断队列是否满
int isFull(Queue *q) {return (q->rear + 1) % MAX == q->front;
}// 入队
void enqueue(Queue *q, int value) {if (isFull(q)) {printf("Queue overflow!\n");return;}q->data[q->rear] = value;q->rear = (q->rear + 1) % MAX;
}// 出队
int dequeue(Queue *q) {if (isEmpty(q)) {printf("Queue underflow!\n");exit(1);}int value = q->data[q->front];q->front = (q->front + 1) % MAX;return value;
}// 打印队列
void printQueue(Queue *q) {for (int i = q->front; i != q->rear; i = (i + 1) % MAX) {printf("%d ", q->data[i]);}printf("\n");
}int main() {Queue q;init(&q);enqueue(&q, 10);enqueue(&q, 20);enqueue(&q, 30);printQueue(&q);dequeue(&q);printQueue(&q);return 0;
}

平衡二叉树 (AVL Tree)

AVL树是一种自平衡二叉搜索树，任何节点的左右子树高度差不超过1。

#include <stdio.h>
#include <stdlib.h>// 定义节点
typedef struct Node {int key;struct Node *left;struct Node *right;int height;
} Node;// 获取节点的高度
int height(Node *n) {if (n == NULL) return 0;return n->height;
}// 创建新节点
Node* newNode(int key) {Node* node = (Node*)malloc(sizeof(Node));node->key = key;node->left = node->right = NULL;node->height = 1;return node;
}// 右旋转
Node* rightRotate(Node* y) {Node* x = y->left;Node* T2 = x->right;x->right = y;y->left = T2;y->height = 1 + fmax(height(y->left), height(y->right));x->height = 1 + fmax(height(x->left), height(x->right));return x;
}// 左旋转
Node* leftRotate(Node* x) {Node* y = x->right;Node* T2 = y->left;y->left = x;x->right = T2;x->height = 1 + fmax(height(x->left), height(x->right));y->height = 1 + fmax(height(y->left), height(y->right));return y;
}// 获取平衡因子
int getBalance(Node* n) {if (n == NULL) return 0;return height(n->left) - height(n->right);
}// 插入节点
Node* insert(Node* node, int key) {if (node == NULL) return newNode(key);if (key < node->key)node->left = insert(node->left, key);else if (key > node->key)node->right = insert(node->right, key);elsereturn node;node->height = 1 + fmax(height(node->left), height(node->right));int balance = getBalance(node);// 平衡调整if (balance > 1 && key < node->left->key)return rightRotate(node);if (balance < -1 && key > node->right->key)return leftRotate(node);if (balance > 1 && key > node->left->key) {node->left = leftRotate(node->left);return rightRotate(node);}if (balance < -1 && key < node->right->key) {node->right = rightRotate(node->right);return leftRotate(node);}return node;
}// 中序遍历
void inorder(Node* root) {if (root != NULL) {inorder(root->left);printf("%d ", root->key);inorder(root->right);}
}int main() {Node* root = NULL;root = insert(root, 10);root = insert(root, 20);root = insert(root, 30);root = insert(root, 40);root = insert(root, 50);inorder(root);return 0;
}

最优二叉树（哈夫曼树）的实现

哈夫曼树是一种用于数据压缩的二叉树。它是一种最优的前缀编码树，使用频率最低的字符分配最长的编码，从而达到压缩的效果。

#include <stdio.h>
#include <stdlib.h>// 定义哈夫曼树的节点
typedef struct Node {char data;int freq;struct Node *left, *right;
} Node;// 创建一个新的节点
Node* newNode(char data, int freq) {Node* node = (Node*)malloc(sizeof(Node));node->data = data;node->freq = freq;node->left = node->right = NULL;return node;
}// 交换两个节点
void swap(Node** a, Node** b) {Node* temp = *a;*a = *b;*b = temp;
}// 小顶堆 (Min Heap) 结构
typedef struct MinHeap {int size;int capacity;Node** array;
} MinHeap;// 创建一个小顶堆
MinHeap* createMinHeap(int capacity) {MinHeap* minHeap = (MinHeap*)malloc(sizeof(MinHeap));minHeap->size = 0;minHeap->capacity = capacity;minHeap->array = (Node**)malloc(minHeap->capacity * sizeof(Node*));return minHeap;
}// 堆化 (Heapify)
void minHeapify(MinHeap* minHeap, int idx) {int smallest = idx;int left = 2 * idx + 1;int right = 2 * idx + 2;if (left < minHeap->size && minHeap->array[left]->freq < minHeap->array[smallest]->freq)smallest = left;if (right < minHeap->size && minHeap->array[right]->freq < minHeap->array[smallest]->freq)smallest = right;if (smallest != idx) {swap(&minHeap->array[smallest], &minHeap->array[idx]);minHeapify(minHeap, smallest);}
}// 提取最小值节点
Node* extractMin(MinHeap* minHeap) {Node* temp = minHeap->array[0];minHeap->array[0] = minHeap->array[minHeap->size - 1];--minHeap->size;minHeapify(minHeap, 0);return temp;
}// 插入节点到堆
void insertMinHeap(MinHeap* minHeap, Node* node) {++minHeap->size;int i = minHeap->size - 1;while (i && node->freq < minHeap->array[(i - 1) / 2]->freq) {minHeap->array[i] = minHeap->array[(i - 1) / 2];i = (i - 1) / 2;}minHeap->array[i] = node;
}// 创建并构建小顶堆
MinHeap* buildMinHeap(char data[], int freq[], int size) {MinHeap* minHeap = createMinHeap(size);for (int i = 0; i < size; ++i)minHeap->array[i] = newNode(data[i], freq[i]);minHeap->size = size;for (int i = (minHeap->size - 2) / 2; i >= 0; --i)minHeapify(minHeap, i);return minHeap;
}// 构建哈夫曼树
Node* buildHuffmanTree(char data[], int freq[], int size) {Node *left, *right, *top;MinHeap* minHeap = buildMinHeap(data, freq, size);while (minHeap->size != 1) {left = extractMin(minHeap);right = extractMin(minHeap);top = newNode('$', left->freq + right->freq);top->left = left;top->right = right;insertMinHeap(minHeap, top);}return extractMin(minHeap);
}// 打印哈夫曼编码
void printCodes(Node* root, int arr[], int top) {if (root->left) {arr[top] = 0;printCodes(root->left, arr, top + 1);}if (root->right) {arr[top] = 1;printCodes(root->right, arr, top + 1);}if (!root->left && !root->right) {printf("%c: ", root->data);for (int i = 0; i < top; ++i)printf("%d", arr[i]);printf("\n");}
}// 哈夫曼编码主函数
void HuffmanCodes(char data[], int freq[], int size) {Node* root = buildHuffmanTree(data, freq, size);int arr[100], top = 0;printCodes(root, arr, top);
}int main() {char arr[] = { 'a', 'b', 'c', 'd', 'e', 'f' };int freq[] = { 5, 9, 12, 13, 16, 45 };int size = sizeof(arr) / sizeof(arr[0]);HuffmanCodes(arr, freq, size);return 0;
}

B树的实现

B树是一种多路自平衡的搜索树，常用于数据库和文件系统。以下是B树的基本实现。

#include <stdio.h>
#include <stdlib.h>#define T 3  // B树的最小度数// 定义B树的节点
typedef struct BTreeNode {int keys[2*T-1];     // 存储键struct BTreeNode* C[2*T]; // 存储子节点指针int n;            // 当前节点存储的键数量int leaf;         // 是否为叶子节点
} BTreeNode;// 创建一个B树节点
BTreeNode* createNode(int leaf) {BTreeNode* node = (BTreeNode*)malloc(sizeof(BTreeNode));node->leaf = leaf;node->n = 0;for (int i = 0; i < 2*T; i++) {node->C[i] = NULL;}return node;
}// 在非满节点插入键
void insertNonFull(BTreeNode* node, int k) {int i = node->n - 1;if (node->leaf) {while (i >= 0 && node->keys[i] > k) {node->keys[i + 1] = node->keys[i];i--;}node->keys[i + 1] = k;node->n++;} else {while (i >= 0 && node->keys[i] > k) {i--;}i++;if (node->C[i]->n == 2*T-1) {splitChild(node, i, node->C[i]);if (node->keys[i] < k) {i++;}}insertNonFull(node->C[i], k);}
}// 分裂子节点
void splitChild(BTreeNode* parent, int i, BTreeNode* fullChild) {BTreeNode* newChild = createNode(fullChild->leaf);newChild->n = T - 1;for (int j = 0; j < T-1; j++) {newChild->keys[j] = fullChild->keys[j + T];}if (!fullChild->leaf) {for (int j = 0; j < T; j++) {newChild->C[j] = fullChild->C[j + T];}}fullChild->n = T - 1;for (int j = parent->n; j >= i + 1; j--) {parent->C[j + 1] = parent->C[j];}parent->C[i + 1] = newChild;for (int j = parent->n - 1; j >= i; j--) {parent->keys[j + 1] = parent->keys[j];}parent->keys[i] = fullChild->keys[T - 1];parent->n++;
}// 插入一个键到B树
void insert(BTreeNode** root, int k) {BTreeNode* r = *root;if (r->n == 2*T-1) {BTreeNode* s = createNode(0);*root = s;s->C[0] = r;splitChild(s, 0, r);insertNonFull(s, k);} else {insertNonFull(r, k);}
}// 中序遍历B树
void traverse(BTreeNode* root) {int i;// 中序遍历节点中的所有键for (i = 0; i < root->n; i++) {// 如果不是叶子节点，先遍历子树if (!root->leaf) {traverse(root->C[i]);}printf("%d ", root->keys[i]);}// 最后遍历最右子树if (!root->leaf) {traverse(root->C[i]);}
}// 搜索键 k
BTreeNode* search(BTreeNode* root, int k) {int i = 0;// 查找当前节点中的键while (i < root->n && k > root->keys[i]) {i++;}// 找到键，返回当前节点if (i < root->n && k == root->keys[i]) {return root;}// 如果是叶子节点，说明键不存在if (root->leaf) {return NULL;}// 继续在子树中查找return search(root->C[i], k);
}int main() {BTreeNode* root = createNode(1); // 创建一个空的B树节点作为根节点// 插入一些键到B树中insert(&root, 10);insert(&root, 20);insert(&root, 5);insert(&root, 6);insert(&root, 12);insert(&root, 30);insert(&root, 7);insert(&root, 17);printf("Traversal of the constructed B-Tree is:\n");traverse(root);printf("\n");int key = 6;BTreeNode* result = search(root, key);if (result != NULL) {printf("Key %d found in B-Tree.\n", key);} else {printf("Key %d not found in B-Tree.\n", key);}return 0;
}