C算法
线性表、顺序表与链表详解（C 语言实现）
线性表是数据结构基础，包含顺序表和链表两种主要实现。顺序表基于连续内存，支持 O(1) 随机访问但插入删除需移动元素；链表基于非连续内存，插入删除高效但访问需遍历。文章通过 C 语言代码演示了动态顺序表的扩容机制及单向链表的创建、反转与删除操作，对比了两者在时间复杂度、空间开销及应用场景上的差异，帮助读者理解底层存储原理并掌握核心算法逻辑。
线性表是数据结构基础，包含顺序表和链表两种主要实现。顺序表基于连续内存，支持 O(1) 随机访问但插入删除需移动元素；链表基于非连续内存，插入删除高效但访问需遍历。文章通过 C 语言代码演示了动态顺序表的扩容机制及单向链表的创建、反转与删除操作，对比了两者在时间复杂度、空间开销及应用场景上的差异，帮助读者理解底层存储原理并掌握核心算法逻辑。
线性表是由 n 个具有相同特性的元素组成的有限序列，元素之间有明确的前后关系。每个元素有唯一的前驱和后继元素。
基本特性：
线性表主要有两种物理存储方式：顺序存储和链式存储。
使用一段连续的内存空间存储数据，通常使用数组实现。数据元素地址连续，可通过索引直接访问。
使用非连续的内存空间，每个元素包含数据域和指针域。
#include <stdio.h>
#include <stdlib.h>
typedef struct {
int* array;
int size;
int capacity;
} DynamicArray;
void init(DynamicArray* arr) {
arr->capacity = 2;
arr->size = 0;
arr->array = (int*)malloc(arr->capacity * sizeof(int));
}
void resize(DynamicArray* arr, int new_capacity) {
arr->array = (int*)realloc(arr->array, new_capacity * sizeof(int));
arr->capacity = new_capacity;
}
void append(DynamicArray* arr, int value) {
if (arr->size == arr->capacity) {
resize(arr, 2 * arr->capacity);
}
arr->array[arr->size] = value;
arr->size++;
}
void print_array(DynamicArray* arr) {
for (int i = 0; i < arr->size; i++) {
printf("%d ", arr->array[i]);
}
printf("\n");
}
void free_array(DynamicArray* arr) {
free(arr->array);
}
int main() {
DynamicArray arr;
init(&arr);
append(&arr, 1);
append(&arr, 2);
append(&arr, 3);
append(&arr, 4); // 触发扩容
print_array(&arr);
free_array(&arr);
return 0;
}
#include <stdio.h>
#include <stdlib.h>
struct ListNode {
int val;
struct ListNode* next;
};
// 尾插法创建链表
struct ListNode* create_linked_list_tail(int* values, int size) {
struct ListNode* dummy = (struct ListNode*)malloc(sizeof(struct ListNode));
struct ListNode* tail = dummy;
for (int i = 0; i < size; i++) {
struct ListNode* new_node = (struct ListNode*)malloc(sizeof(struct ListNode));
new_node->val = values[i];
tail->next = new_node;
tail = tail->next;
}
return dummy->next;
}
void print_linked_list(struct ListNode* head) {
struct ListNode* current = head;
while (current != NULL) {
printf("%d ", current->val);
current = current->next;
}
printf("\n");
}
// 反转链表
struct ListNode* reverse_linked_list(struct ListNode* head) {
struct ListNode* prev = NULL;
struct ListNode* curr = head;
while (curr != NULL) {
struct ListNode* next_node = curr->next;
curr->next = prev;
prev = curr;
curr = next_node;
}
return prev;
}
int main() {
int values[] = {1, 2, 3};
struct ListNode* head = create_linked_list_tail(values, 3);
print_linked_list(head);
return 0;
}
| 特性 | 顺序表 | 链表 |
|---|---|---|
| 存储方式 | 连续内存块 | 离散内存块，通过指针链接 |
| 随机访问 | O(1) | O(N) |
| 插入/删除 | O(N)（需移动元素） | O(1)（只需修改指针） |
| 空间管理 | 动态扩容可能浪费空间 | 按需分配 |
| 缓存局部性 | 高 | 低 |
本文通过 C 语言代码演示了顺序表和链表的实现原理。顺序表适合频繁读取场景，链表适合频繁增删场景。掌握指针操作与内存管理是理解数据结构的关键。
微信公众号「极客日志」，在微信中扫描左侧二维码关注。展示文案：极客日志 zeeklog
使用加密算法（如AES、TripleDES、Rabbit或RC4）加密和解密文本明文。 在线工具，加密/解密文本在线工具，online
将字符串编码和解码为其 Base64 格式表示形式即可。 在线工具，Base64 字符串编码/解码在线工具，online
将字符串、文件或图像转换为其 Base64 表示形式。 在线工具，Base64 文件转换器在线工具，online
将 Markdown（GFM）转为 HTML 片段，浏览器内 marked 解析；与 HTML转Markdown 互为补充。 在线工具，Markdown转HTML在线工具，online
将 HTML 片段转为 GitHub Flavored Markdown，支持标题、列表、链接、代码块与表格等；浏览器内处理，可链接预填。 在线工具，HTML转Markdown在线工具，online
通过删除不必要的空白来缩小和压缩JSON。 在线工具，JSON 压缩在线工具，online