C语言常用的数据结构
C语言常用的数据结构
1. 数组（Array）
一组固定大小的连续存储的元素，所有元素类型相同，可以通过索引访问。
特点：快速读取、固定大小；
使用场景：用于需要频繁访问元素的场景，例如，查表等。
int arr[5] = {0, 1, 2, 3, 4};
printf("%d", arr[2]);
2. 链表（Linked List）
一系列节点组成的线型结构，每个节点包含数据和一个指向下一个节点的指针。
特点：动态大小，方便插入和删除操作。
使用场景：需要频繁插入/删除元素的场景，例如队列、栈的实现。
struct Node{int data;struct Node* next;
};
struct Node* head = NULL; // 初始化链表头指针
3. 栈（Stack）
一种后进先出（LIFO，Last In First Out）的数据结构。
特点：只允许一端进行插入和删除操作，即栈顶。
使用场景：用于实现递归、表达式求值、括号匹配等。
#include <stdio.h>
#define MAX 100
int stack[MAX];
int top = -1;void push(int value){if(top < MAX -1){stack[++top] = value;}
}int pop(){if(top >= 0 ){teturn stack[top--];}return -1; // 栈空
}
4. 队列（Queue）
一种先进先出（FIFO，First In First Out）的数据结构。
特点：元素从一端进入，从另一端离开。
使用场景：用于任务调度、缓存等。
#define MAX 100
int queue[MAX];
void enqueue(int value){if(rear < MAX){queue[rear++] = value;}
}int dequeue(){if(front < rear){return queue[front++];}return -1; // 队列为空
}
5. 二叉树（Binary Tree）
每个节点最多有两个子节点的树结构，分别称为左子节点和右字节点。
特点：结构灵活，时和多种操作，如查找、插入、删除。
使用场景：用于实现二叉树、堆、表达式树等。
struct TreeNode{int data;struct TreeNode* left;struct TreeNode* right;
};struct TreeNode* root = NULL; // 初始化二叉树根节点
6. 哈希表（Hash Table）
通过哈希函数将键值映射到数组中的位置，以实现快速查找。
特点：平均情况下，插入、删除和查找操作的时间复杂度为O（1）。
使用场景：用于快速查找，如数据库索引、缓存实现。
#define SIZE 100int hashTable[SIZE];int hashFunction(int key){return key % SIZE;
}void insert(int key){int index = hashFunction(key);hashTable[index] = key;
}
7. 图（graph）
由一组顶点和这些顶点之间的边组成的结构，可以是有向或无向的。
特点：适合表示多对多关系，入社交网络、道路网络。
使用场景：用于路径查找、网络流、最短路径等。
#define V 5int graph[V][V] = {{0, 1, 0, 0, 1},{1, 0, 1, 0, 1},{0, 1, 0, 1, 0},{0, 0, 1, 0, 1},{1, 1, 0, 1, 0}
};
8. 堆 (Heap)
- 简介: 一种特殊的二叉树，满足堆性质：最大堆中每个节点都大于等于其子节点，最小堆中每个节点都小于等于其子节点。
- 特点: 适合实现优先队列，支持高效的最大/最小值获取。
- 使用场景: 用于排序（堆排序）、优先队列实现等。
void heapify(int arr[], int n, int i) {int largest = i;int left = 2 * i + 1;int right = 2 * i + 2;if (left < n && arr[left] > arr[largest])largest = left;if (right < n && arr[right] > arr[largest])largest = right;if (largest != i) {int temp = arr[i];arr[i] = arr[largest];arr[largest] = temp;heapify(arr, n, largest);}
}
9. 集合 (Set)
- 简介: 一种无序且不重复的元素集合。
- 特点: 主要用于判断元素是否存在、集合操作（并集、交集、差集）。
- 使用场景: 用于集合操作、去重、快速查找元素。
#include <stdio.h>
#include <stdbool.h>bool set[1000] = {false};void insert(int value) {set[value] = true;
}bool contains(int value) {return set[value];
}