C算法
线性表、顺序表与链表详解（C 语言版）
线性表的逻辑结构与物理实现方式，重点讲解了顺序表和链表的区别。内容包括线性表的定义、特性、顺序存储与链式存储的优缺点对比。提供了 C 语言实现的动态顺序表和单向链表代码示例，涵盖初始化、插入、删除、查找及反转等操作。最后通过课堂练习和作业设计巩固知识点，帮助读者理解不同数据结构的适用场景及性能差异。
线性表的逻辑结构与物理实现方式，重点讲解了顺序表和链表的区别。内容包括线性表的定义、特性、顺序存储与链式存储的优缺点对比。提供了 C 语言实现的动态顺序表和单向链表代码示例，涵盖初始化、插入、删除、查找及反转等操作。最后通过课堂练习和作业设计巩固知识点，帮助读者理解不同数据结构的适用场景及性能差异。
理论讲解 + 代码演示 + 对比分析 + 课堂练习
线性表是由 n 个具有相同特性的元素组成的有限序列，元素之间有明确的前后关系。每个元素有唯一的前驱和后继元素。线性表可以是顺序存储或链式存储。
线性表有两种常见的物理存储方式：顺序存储和链式存储。
顺序存储使用一段连续的内存空间存储数据，通常使用数组来实现。数据元素在内存中的地址是连续的，因此可以通过索引来直接访问。
链表使用非连续的内存空间存储数据，每个元素包含一个数据域和一个指向下一个元素的指针（或者同时包含指向前后节点的指针），因此数据元素的地址不一定是连续的。
#include <stdio.h>
#include <stdlib.h>
typedef struct {
int* array; // 动态分配的数组
int size; // 当前元素个数
int capacity; // 数组容量
} DynamicArray;
// 初始化动态数组
void init(DynamicArray* arr) {
arr->capacity = 2; // 初始容量为 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); // 扩容时容量变为 4
printf("动态顺序表的内容：\n");
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");
}
int main() {
int values[] = {1, 2, 3};
struct ListNode* head = create_linked_list_tail(values, 3);
print_linked_list(head);
return 0;
}
// 反转链表
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;
}
// 删除链表中所有值为 val 的节点
struct ListNode* remove_elements(struct ListNode* head, int val) {
struct ListNode* dummy = (struct ListNode*)malloc(sizeof(struct ListNode));
dummy->next = head;
struct ListNode* current = dummy;
while (current->next != NULL) {
if (current->next->val == val) {
struct ListNode* temp = current->next;
current->next = temp->next;
free(temp);
} else {
current = current->next;
}
}
return dummy->next;
}
| 特性 | 顺序表 | 链表 |
|---|---|---|
| 存储方式 | 连续内存块（数组） | 离散内存块（通过指针链接） |
| 随机访问 | O(1) | O(N) |
| 插入/删除操作 | O(N)（需移动元素） | O(1)（只需修改指针） |
| 扩容/缩容 | 动态扩容（可能浪费空间） | 不需要扩容，按需分配空间 |
| 内存空间使用 | 存储空间固定，可能造成浪费 | 每个节点动态分配内存 |
| 应用场景 | 适合频繁访问的场景 | 适合频繁插入和删除的场景 |
| 内存开销 | 低，只有存储元素的数据 | 较高，每个节点还需要存储指针 |
通过代码实现和对比分析，应掌握以下内容：
微信公众号「极客日志」，在微信中扫描左侧二维码关注。展示文案：极客日志 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