C 语言中的高级数据结构与内存管理

一、引言

C 语言作为一种广泛应用的系统级编程语言，以其高效性和灵活性著称。在 C 语言编程中，高级数据结构和内存管理是两个至关重要的方面。高级数据结构能够帮助我们更高效地组织和处理数据，而合理的内存管理则是保证程序性能和稳定性的关键。本文将深入探讨 C 语言中的高级数据结构和内存管理，结合丰富的代码示例和高级知识点，为读者提供全面而深入的理解。

二、高级数据结构

2.1 图（Graph）

2.1.1 图的基本概念

图是一种由节点（顶点）和连接这些节点的边组成的数据结构。图可以用来表示各种实际问题，如社交网络、交通网络等。图分为有向图和无向图，有向图的边有方向，而无向图的边没有方向。此外，图还可以分为加权图和无权图，加权图的边带有权重，而无权图的边没有权重。

2.1.2 图的表示方法

在 C 语言中，常用的图的表示方法有邻接矩阵和邻接表。

邻接矩阵

邻接矩阵是一个二维数组，其中 matrix[i][j] 表示顶点 i 到顶点 j 是否有边相连。如果是无权图，matrix[i][j] 可以用 0 或 1 表示；如果是加权图，matrix[i][j] 可以用边的权重表示。

#include <stdio.h>
#define MAX_VERTICES 100// 邻接矩阵表示图
typedef struct {int vertices;int matrix[MAX_VERTICES][MAX_VERTICES];
} Graph;// 初始化图
void initGraph(Graph *g, int v) {g->vertices = v;for (int i = 0; i < v; i++) {for (int j = 0; j < v; j++) {g->matrix[i][j] = 0;}}
}// 添加边
void addEdge(Graph *g, int src, int dest) {g->matrix[src][dest] = 1;// 如果是无向图，还需要添加反向边g->matrix[dest][src] = 1;
}// 打印图
void printGraph(Graph *g) {for (int i = 0; i < g->vertices; i++) {for (int j = 0; j < g->vertices; j++) {printf("%d ", g->matrix[i][j]);}printf("\n");}
}int main() {Graph g;int vertices = 5;initGraph(&g, vertices);addEdge(&g, 0, 1);addEdge(&g, 0, 4);addEdge(&g, 1, 2);addEdge(&g, 1, 3);addEdge(&g, 1, 4);addEdge(&g, 2, 3);addEdge(&g, 3, 4);printGraph(&g);return 0;
}

邻接表

邻接表是一种链表数组，每个数组元素对应一个顶点，链表中存储与该顶点相邻的顶点。

#include <stdio.h>
#include <stdlib.h>// 邻接表节点
typedef struct AdjListNode {int dest;struct AdjListNode* next;
} AdjListNode;// 邻接表头节点
typedef struct AdjList {AdjListNode *head;
} AdjList;// 图
typedef struct {int vertices;AdjList* array;
} Graph;// 创建新的邻接表节点
AdjListNode* newAdjListNode(int dest) {AdjListNode* newNode = (AdjListNode*)malloc(sizeof(AdjListNode));newNode->dest = dest;newNode->next = NULL;return newNode;
}// 创建图
Graph* createGraph(int vertices) {Graph* graph = (Graph*)malloc(sizeof(Graph));graph->vertices = vertices;graph->array = (AdjList*)malloc(vertices * sizeof(AdjList));for (int i = 0; i < vertices; i++) {graph->array[i].head = NULL;}return graph;
}// 添加边
void addEdge(Graph* graph, int src, int dest) {AdjListNode* newNode = newAdjListNode(dest);newNode->next = graph->array[src].head;graph->array[src].head = newNode;// 如果是无向图，添加反向边newNode = newAdjListNode(src);newNode->next = graph->array[dest].head;graph->array[dest].head = newNode;
}// 打印图
void printGraph(Graph* graph) {for (int i = 0; i < graph->vertices; i++) {AdjListNode* pCrawl = graph->array[i].head;printf("\n Adjacency list of vertex %d\n head ", i);while (pCrawl) {printf("-> %d", pCrawl->dest);pCrawl = pCrawl->next;}printf("\n");}
}int main() {int vertices = 5;Graph* graph = createGraph(vertices);addEdge(graph, 0, 1);addEdge(graph, 0, 4);addEdge(graph, 1, 2);addEdge(graph, 1, 3);addEdge(graph, 1, 4);addEdge(graph, 2, 3);addEdge(graph, 3, 4);printGraph(graph);return 0;
}

2.1.3 图的遍历算法

图的遍历算法主要有深度优先搜索（DFS）和广度优先搜索（BFS）。

深度优先搜索（DFS）

深度优先搜索是一种递归的遍历算法，它从一个顶点开始，沿着一条路径尽可能深地访问顶点，直到无法继续，然后回溯到上一个顶点，继续探索其他路径。

#include <stdio.h>
#include <stdlib.h>// 邻接表节点
typedef struct AdjListNode {int dest;struct AdjListNode* next;
} AdjListNode;// 邻接表头节点
typedef struct AdjList {AdjListNode *head;
} AdjList;// 图
typedef struct {int vertices;AdjList* array;
} Graph;// 创建新的邻接表节点
AdjListNode* newAdjListNode(int dest) {AdjListNode* newNode = (AdjListNode*)malloc(sizeof(AdjListNode));newNode->dest = dest;newNode->next = NULL;return newNode;
}// 创建图
Graph* createGraph(int vertices) {Graph* graph = (Graph*)malloc(sizeof(Graph));graph->vertices = vertices;graph->array = (AdjList*)malloc(vertices * sizeof(AdjList));for (int i = 0; i < vertices; i++) {graph->array[i].head = NULL;}return graph;
}// 添加边
void addEdge(Graph* graph, int src, int dest) {AdjListNode* newNode = newAdjListNode(dest);newNode->next = graph->array[src].head;graph->array[src].head = newNode;// 如果是无向图，添加反向边newNode = newAdjListNode(src);newNode->next = graph->array[dest].head;graph->array[dest].head = newNode;
}// 深度优先搜索辅助函数
void DFSUtil(Graph* graph, int v, int visited[]) {visited[v] = 1;printf("%d ", v);AdjListNode* pCrawl = graph->array[v].head;while (pCrawl) {int adjVertex = pCrawl->dest;if (!visited[adjVertex]) {DFSUtil(graph, adjVertex, visited);}pCrawl = pCrawl->next;}
}// 深度优先搜索
void DFS(Graph* graph, int startVertex) {int* visited = (int*)calloc(graph->vertices, sizeof(int));DFSUtil(graph, startVertex, visited);free(visited);
}int main() {int vertices = 5;Graph* graph = createGraph(vertices);addEdge(graph, 0, 1);addEdge(graph, 0, 4);addEdge(graph, 1, 2);addEdge(graph, 1, 3);addEdge(graph, 1, 4);addEdge(graph, 2, 3);addEdge(graph, 3, 4);printf("深度优先搜索从顶点 0 开始：\n");DFS(graph, 0);return 0;
}

广度优先搜索（BFS）

广度优先搜索是一种基于队列的遍历算法，它从一个顶点开始，逐层地访问相邻的顶点。

#include <stdio.h>
#include <stdlib.h>// 邻接表节点
typedef struct AdjListNode {int dest;struct AdjListNode* next;
} AdjListNode;// 邻接表头节点
typedef struct AdjList {AdjListNode *head;
} AdjList;// 图
typedef struct {int vertices;AdjList* array;
} Graph;// 创建新的邻接表节点
AdjListNode* newAdjListNode(int dest) {AdjListNode* newNode = (AdjListNode*)malloc(sizeof(AdjListNode));newNode->dest = dest;newNode->next = NULL;return newNode;
}// 创建图
Graph* createGraph(int vertices) {Graph* graph = (Graph*)malloc(sizeof(Graph));graph->vertices = vertices;graph->array = (AdjList*)malloc(vertices * sizeof(AdjList));for (int i = 0; i < vertices; i++) {graph->array[i].head = NULL;}return graph;
}// 添加边
void addEdge(Graph* graph, int src, int dest) {AdjListNode* newNode = newAdjListNode(dest);newNode->next = graph->array[src].head;graph->array[src].head = newNode;// 如果是无向图，添加反向边newNode = newAdjListNode(src);newNode->next = graph->array[dest].head;graph->array[dest].head = newNode;
}// 广度优先搜索
void BFS(Graph* graph, int startVertex) {int* visited = (int*)calloc(graph->vertices, sizeof(int));int* queue = (int*)malloc(graph->vertices * sizeof(int));int front = 0, rear = 0;visited[startVertex] = 1;queue[rear++] = startVertex;while (front < rear) {int currentVertex = queue[front++];printf("%d ", currentVertex);AdjListNode* pCrawl = graph->array[currentVertex].head;while (pCrawl) {int adjVertex = pCrawl->dest;if (!visited[adjVertex]) {visited[adjVertex] = 1;queue[rear++] = adjVertex;}pCrawl = pCrawl->next;}}free(visited);free(queue);
}int main() {int vertices = 5;Graph* graph = createGraph(vertices);addEdge(graph, 0, 1);addEdge(graph, 0, 4);addEdge(graph, 1, 2);addEdge(graph, 1, 3);addEdge(graph, 1, 4);addEdge(graph, 2, 3);addEdge(graph, 3, 4);printf("广度优先搜索从顶点 0 开始：\n");BFS(graph, 0);return 0;
}

2.2 堆（Heap）

2.2.1 堆的基本概念

堆是一种特殊的树形数据结构，它通常是一个完全二叉树。堆分为最大堆和最小堆，最大堆的每个节点的值都大于或等于其子节点的值，最小堆的每个节点的值都小于或等于其子节点的值。

2.2.2 堆的实现

在 C 语言中，可以使用数组来实现堆。

#include <stdio.h>
#include <stdlib.h>// 交换两个元素
void swap(int *a, int *b) {int temp = *a;*a = *b;*b = temp;
}// 最大堆化
void maxHeapify(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) {swap(&arr[i], &arr[largest]);maxHeapify(arr, n, largest);}
}// 构建最大堆
void buildMaxHeap(int arr[], int n) {for (int i = n / 2 - 1; i >= 0; i--) {maxHeapify(arr, n, i);}
}// 堆排序
void heapSort(int arr[], int n) {buildMaxHeap(arr, n);for (int i = n - 1; i > 0; i--) {swap(&arr[0], &arr[i]);maxHeapify(arr, i, 0);}
}// 打印数组
void printArray(int arr[], int n) {for (int i = 0; i < n; i++) {printf("%d ", arr[i]);}printf("\n");
}int main() {int arr[] = {12, 11, 13, 5, 6, 7};int n = sizeof(arr) / sizeof(arr[0]);printf("排序前的数组：\n");printArray(arr, n);heapSort(arr, n);printf("排序后的数组：\n");printArray(arr, n);return 0;
}

2.2.3 堆的应用

堆的常见应用包括堆排序、优先队列等。优先队列是一种特殊的队列，它的元素按照优先级进行排序，优先级高的元素先出队。可以使用堆来实现优先队列。

#include <stdio.h>
#include <stdlib.h>// 交换两个元素
void swap(int *a, int *b) {int temp = *a;*a = *b;*b = temp;
}// 最小堆化
void minHeapify(int arr[], int n, int i) {int smallest = i;int left = 2 * i + 1;int right = 2 * i + 2;if (left < n && arr[left] < arr[smallest]) {smallest = left;}if (right < n && arr[right] < arr[smallest]) {smallest = right;}if (smallest != i) {swap(&arr[i], &arr[smallest]);minHeapify(arr, n, smallest);}
}// 插入元素到最小堆
void insertMinHeap(int arr[], int *n, int key) {(*n)++;int i = *n - 1;arr[i] = key;while (i > 0 && arr[(i - 1) / 2] > arr[i]) {swap(&arr[i], &arr[(i - 1) / 2]);i = (i - 1) / 2;}
}// 从最小堆中提取最小元素
int extractMin(int arr[], int *n) {if (*n <= 0) {return -1;}if (*n == 1) {(*n)--;return arr[0];}int root = arr[0];arr[0] = arr[*n - 1];(*n)--;minHeapify(arr, *n, 0);return root;
}int main() {int arr[100];int n = 0;insertMinHeap(arr, &n, 3);insertMinHeap(arr, &n, 2);insertMinHeap(arr, &n, 15);insertMinHeap(arr, &n, 5);insertMinHeap(arr, &n, 4);insertMinHeap(arr, &n, 45);printf("最小元素：%d\n", extractMin(arr, &n));printf("最小元素：%d\n", extractMin(arr, &n));return 0;
}

三、内存管理

3.1 动态内存分配

在 C 语言中，动态内存分配允许程序在运行时分配和释放内存。常用的动态内存分配函数有 malloc、calloc、realloc 和 free。

3.1.1 malloc 函数

malloc 函数用于分配指定大小的内存块，返回一个指向该内存块的指针。

#include <stdio.h>
#include <stdlib.h>int main() {int n = 5;int *arr = (int*)malloc(n * sizeof(int));if (arr == NULL) {printf("内存分配失败\n");return 1;}for (int i = 0; i < n; i++) {arr[i] = i + 1;}for (int i = 0; i < n; i++) {printf("%d ", arr[i]);}printf("\n");free(arr);return 0;
}

3.1.2 calloc 函数

calloc 函数用于分配指定数量和大小的内存块，并将其初始化为 0。

#include <stdio.h>
#include <stdlib.h>int main() {int n = 5;int *arr = (int*)calloc(n, sizeof(int));if (arr == NULL) {printf("内存分配失败\n");return 1;}for (int i = 0; i < n; i++) {printf("%d ", arr[i]);}printf("\n");free(arr);return 0;
}

3.1.3 realloc 函数

realloc 函数用于调整已分配内存块的大小。

#include <stdio.h>
#include <stdlib.h>int main() {int n = 5;int *arr = (int*)malloc(n * sizeof(int));if (arr == NULL) {printf("内存分配失败\n");return 1;}for (int i = 0; i < n; i++) {arr[i] = i + 1;}int newSize = 10;arr = (int*)realloc(arr, newSize * sizeof(int));if (arr == NULL) {printf("内存重新分配失败\n");return 1;}for (int i = n; i < newSize; i++) {arr[i] = i + 1;}for (int i = 0; i < newSize; i++) {printf("%d ", arr[i]);}printf("\n");free(arr);return 0;
}

3.1.4 free 函数

free 函数用于释放之前分配的内存块。

#include <stdio.h>
#include <stdlib.h>int main() {int *ptr = (int*)malloc(sizeof(int));if (ptr == NULL) {printf("内存分配失败\n");return 1;}*ptr = 10;printf("分配的内存中存储的值：%d\n", *ptr);free(ptr);return 0;
}

3.2 内存泄漏与避免

内存泄漏是指程序在运行过程中分配了内存，但在不再使用时没有释放，导致可用内存不断减少。为了避免内存泄漏，需要遵循以下原则：

• 确保每次调用 malloc、calloc 或 realloc 后，都有对应的 free 调用。
• 在函数返回之前，释放函数内部分配的动态内存。
• 避免在循环中不断分配内存而不释放。

#include <stdio.h>
#include <stdlib.h>// 错误示例：存在内存泄漏
void memoryLeakExample() {int *ptr = (int*)malloc(sizeof(int));// 没有释放内存
}// 正确示例：避免内存泄漏
void noMemoryLeakExample() {int *ptr = (int*)malloc(sizeof(int));if (ptr != NULL) {*ptr = 10;free(ptr);}
}int main() {memoryLeakExample();noMemoryLeakExample();return 0;
}

3.3 内存对齐

内存对齐是指数据在内存中的存储方式，它要求数据的起始地址必须是其大小的整数倍。内存对齐可以提高内存访问效率，但会增加内存的使用量。

#include <stdio.h>// 未对齐的结构体
struct UnalignedStruct {char c;int i;short s;
};// 对齐的结构体
#pragma pack(1)
struct AlignedStruct {char c;int i;short s;
};
#pragma pack()int main() {printf("未对齐结构体的大小：%zu\n", sizeof(struct UnalignedStruct));printf("对齐结构体的大小：%zu\n", sizeof(struct AlignedStruct));return 0;
}

3.4 内存池技术

内存池技术是一种优化内存分配和释放的技术，它预先分配一块较大的内存块，然后在需要时从这块内存块中分配小块内存，避免了频繁的系统调用，提高了内存分配和释放的效率。

#include <stdio.h>
#include <stdlib.h>#define BLOCK_SIZE 1024
#define POOL_SIZE 10// 内存块
typedef struct MemoryBlock {struct MemoryBlock *next;char data[BLOCK_SIZE];
} MemoryBlock;// 内存池
typedef struct MemoryPool {MemoryBlock *head;int count;
} MemoryPool;// 初始化内存池
void initMemoryPool(MemoryPool *pool) {pool->head = NULL;pool->count = 0;for (int i = 0; i < POOL_SIZE; i++) {MemoryBlock *block = (MemoryBlock*)malloc(sizeof(MemoryBlock));block->next = pool->head;pool->head = block;pool->count++;}
}// 从内存池分配内存
void* allocateFromPool(MemoryPool *pool) {if (pool->head == NULL) {return NULL;}MemoryBlock *block = pool->head;pool->head = block->next;pool->count--;return (void*)block->data;
}// 将内存块返回给内存池
void freeToPool(MemoryPool *pool, void *ptr) {MemoryBlock *block = (MemoryBlock*)((char*)ptr - offsetof(MemoryBlock, data));block->next = pool->head;pool->head = block;pool->count++;
}// 销毁内存池
void destroyMemoryPool(MemoryPool *pool) {MemoryBlock *current = pool->head;while (current != NULL) {MemoryBlock *next = current->next;free(current);current = next;}pool->head = NULL;pool->count = 0;
}int main() {MemoryPool pool;initMemoryPool(&pool);void *ptr1 = allocateFromPool(&pool);void *ptr2 = allocateFromPool(&pool);if (ptr1 != NULL) {printf("从内存池分配的内存地址：%p\n", ptr1);}if (ptr2 != NULL) {printf("从内存池分配的内存地址：%p\n", ptr2);}freeToPool(&pool, ptr1);freeToPool(&pool, ptr2);destroyMemoryPool(&pool);return 0;
}

四、高级数据结构与内存管理的结合应用

4.1 图的内存管理

在实现图的过程中，需要合理管理内存。例如，在使用邻接表表示图时，每个顶点的邻接表节点都需要动态分配内存，在不再使用图时，需要释放这些内存。

#include <stdio.h>
#include <stdlib.h>// 邻接表节点
typedef struct AdjListNode {int dest;struct AdjListNode* next;
} AdjListNode;// 邻接表头节点
typedef struct AdjList {AdjListNode *head;
} AdjList;// 图
typedef struct {int vertices;AdjList* array;
} Graph;// 创建新的邻接表节点
AdjListNode* newAdjListNode(int dest) {AdjListNode* newNode = (AdjListNode*)malloc(sizeof(AdjListNode));newNode->dest = dest;newNode->next = NULL;return newNode;
}// 创建图
Graph* createGraph(int vertices) {Graph* graph = (Graph*)malloc(sizeof(Graph));graph->vertices = vertices;graph->array = (AdjList*)malloc(vertices * sizeof(AdjList));for (int i = 0; i < vertices; i++) {graph->array[i].head = NULL;}return graph;
}// 添加边
void addEdge(Graph* graph, int src, int dest) {AdjListNode* newNode = newAdjListNode(dest);newNode->next = graph->array[src].head;graph->array[src].head = newNode;// 如果是无向图，添加反向边newNode = newAdjListNode(src);newNode->next = graph->array[dest].head;graph->array[dest].head = newNode;
}// 释放图的内存
void freeGraph(Graph* graph) {for (int i = 0; i < graph->vertices; i++) {AdjListNode* current = graph->array[i].head;while (current != NULL) {AdjListNode* next = current->next;free(current);current = next;}}free(graph->array);free(graph);
}int main() {int vertices = 5;Graph* graph = createGraph(vertices);addEdge(graph, 0, 1);addEdge(graph, 0, 4);addEdge(graph, 1, 2);addEdge(graph, 1, 3);addEdge(graph, 1, 4);addEdge(graph, 2, 3);addEdge(graph, 3, 4);// 使用图...freeGraph(graph);return 0;
}

4.2 堆的内存管理

在实现堆的过程中，同样需要注意内存的分配和释放。例如，在使用数组实现堆时，需要确保数组的内存分配和释放正确。

#include <stdio.h>
#include <stdlib.h>// 交换两个元素
void swap(int *a, int *b) {int temp = *a;*a = *b;*b = temp;
}// 最大堆化
void maxHeapify(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) {swap(&arr[i], &arr[largest]);maxHeapify(arr, n, largest);}
}// 构建最大堆
void buildMaxHeap(int arr[], int n) {for (int i = n / 2 - 1; i >= 0; i--) {maxHeapify(arr, n, i);}
}// 堆排序
void heapSort(int arr[], int n) {buildMaxHeap(arr, n);for (int i = n - 1; i > 0; i--) {swap(&arr[0], &arr[i]);maxHeapify(arr, i, 0);}
}int main() {int n = 5;int *arr = (int*)malloc(n * sizeof(int));if (arr == NULL) {printf("内存分配失败\n");return 1;}for (int i = 0; i < n; i++) {arr[i] = n - i;}heapSort(arr, n);for (int i = 0; i < n; i++) {printf("%d ", arr[i]);}printf("\n");free(arr);return 0;
}

五、总结

本文深入探讨了 C 语言中的高级数据结构和内存管理。高级数据结构如 图和堆，为我们解决复杂的问题提供了强大的工具。图可以用于表示各种关系，通过不同的遍历算法可以对图进行有效的操作；堆则在排序和优先队列等方面有重要应用。

内存管理是 C 语言编程中不可忽视的部分，动态内存分配函数如 malloc、calloc、realloc 和 free 为我们提供了灵活的内存使用方式。但同时，我们需要注意避免内存泄漏，合理进行内存对齐，并可以采用内存池技术优化内存分配和释放的效率。