当前位置：首页 > news >正文

C 语言中经典的数据结构

news 2025/4/16 19:50:25

在 C 语言中，经典的数据结构通常包括以下几种，每种都有其特定的应用场景和实现方式：

1. 数组（Array）

定义：连续内存空间存储相同类型的数据。
特点：随机访问快（O(1)），插入/删除效率低（O(n)）。
应用场景：存储固定大小的数据集合。
示例代码：
```
int arr[5] = {1, 2, 3, 4, 5};
```

2. 链表（Linked List）

定义：通过指针连接的节点序列，分为单向链表、双向链表和循环链表。
特点：动态大小，插入/删除快（O(1)），访问慢（O(n)）。
应用场景：动态内存分配、实现栈/队列等。

示例代码（单向链表）：

typedef struct Node {int data;struct Node* next;
} Node;Node* create_node(int data) {Node* node = (Node*)malloc(sizeof(Node));node->data = data;node->next = NULL;return node;
}

3. 栈（Stack）

定义：后进先出（LIFO）的线性结构。
操作：push（入栈）、pop（出栈）、peek（查看栈顶）。
实现方式：数组或链表。
应用场景：函数调用栈、括号匹配、表达式求值。

示例代码（数组实现）：


#define MAX_SIZE 100
typedef struct Stack {int data[MAX_SIZE];int top;
} Stack;void push(Stack* s, int val) {if (s->top < MAX_SIZE) s->data[s->top++] = val;
}int pop(Stack* s) {if (s->top > 0) return s->data[--s->top];return -1;
}

4. 队列（Queue）

定义：先进先出（FIFO）的线性结构。
操作：enqueue（入队）、dequeue（出队）。
实现方式：数组（循环队列）或链表。
应用场景：任务调度、缓冲区管理。

示例代码（链表实现）：

typedef struct QueueNode {int data;struct QueueNode* next;
} QueueNode;typedef struct Queue {QueueNode *front, *rear;
} Queue;void enqueue(Queue* q, int data) {QueueNode* node = create_node(data);if (q->rear == NULL) {q->front = q->rear = node;return;}q->rear->next = node;q->rear = node;
}

5. 树（Tree）

定义：层次化的非线性结构，常见类型包括二叉树、二叉搜索树（BST）、AVL 树。
操作：插入、删除、遍历（前序、中序、后序）。
应用场景：文件系统、数据库索引、哈夫曼编码。

示例代码（二叉树节点）：


typedef struct TreeNode {int data;struct TreeNode* left;struct TreeNode* right;
} TreeNode;

6. 图（Graph）

定义：由顶点（Vertex）和边（Edge）组成的非线性结构。
实现方式：邻接矩阵或邻接表。
操作：遍历（DFS/BFS）、最短路径算法。
应用场景：社交网络、路径规划。

示例代码（邻接表）：

typedef struct GraphNode {int vertex;struct GraphNode* next;
} GraphNode;typedef struct Graph {int num_vertices;GraphNode** adj_list;
} Graph;

7. 哈希表（Hash Table）

定义：通过哈希函数将键映射到值的结构。
特点：理想情况下查找时间复杂度为 O(1)。
冲突解决：开放寻址法、链地址法。
应用场景：数据库索引、缓存实现。

示例代码（链地址法）：

#define TABLE_SIZE 10
typedef struct HashNode {int key;int value;struct HashNode* next;
} HashNode;typedef struct HashTable {HashNode* table[TABLE_SIZE];
} HashTable;