目录
1. 线性表的定义和基本概念
- 线性表（List）是数据结构中的一种基本结构，是一组有序的数据元素的集合。线性表中的数据元素有且仅有一个前驱和一个后继（第一个元素没有前驱，最后一个元素没有后继）。线性表是实现其他数据结构（如堆栈、队列）的基础。
2. 顺序表
2.1 顺序表的定义
- 顺序表（Sequential List）是一种线性表，其存储结构为一块连续的内存空间。顺序表通过数组来实现，数组中的每个位置都存储线性表的一个元素。
2.2 顺序表的结构
顺序表一般包含以下几部分：
- 存储数组：存储线性表的元素。
- 最大容量：顺序表的最大存储容量。
- 当前长度：顺序表中当前存储的元素个数。
2.3 顺序表的优缺点
优点：
- 随机访问性能好：可以通过下标快速访问任意位置的元素。
- 查询效率高：在时间复杂度为O(1)的情况下访问元素。
缺点：
- 插入和删除操作效率低：需要移动大量元素，时间复杂度为O(n)。
- 内存浪费或溢出：数组大小固定，可能导致内存浪费或不足。
2.4 顺序表的操作
1、插入操作
- 在顺序表中插入一个元素，需要将插入位置及其后的所有元素向后移动一个位置。
2、删除操作
- 从顺序表中删除一个元素，需要将删除位置后的所有元素向前移动一个位置。
2.5 顺序表的代码实现
#include <stdio.h>
#include <stdlib.h>
typedef struct {
int *array;
int capacity;
int length;
} SequentialList;
SequentialList* create_list(int capacity) {
SequentialList* list = (SequentialList*)malloc(sizeof(SequentialList));
list->array = (int*)malloc(capacity * sizeof(int));
list->capacity = capacity;
list->length = 0;
return list;
}
void insert(SequentialList* list, int index, int value) {
if (list->length >= list->capacity) {
printf("List is full\n");
return;
}
if (index < 0 || index > list->length) {
printf("Index out of bounds\n");
return;
}
for (int i = list->length; i > index; --i) {
list->array[i] = list->array[i - 1];
}
list->array[index] = value;
list->length++;
}
void delete(SequentialList* list, int index) {
if (index < 0 || index >= list->length) {
printf("Index out of bounds\n");
return;
}
for (int i = index; i < list->length - 1; ++i) {
list->array[i] = list->array[i + 1];
}
list->length--;
}
void print_list(SequentialList* list) {
printf("[");
for (int i = 0; i < list->length; ++i) {
printf("%d", list->array[i]);
if (i < list->length - 1) {
printf(", ");
}
}
printf("]\n");
}
void free_list(SequentialList* list) {
free(list->array);
free(list);
}
int main() {
SequentialList* seq_list = create_list(10);
insert(seq_list, 0, 1);
insert(seq_list, 1, 2);
insert(seq_list, 2, 3);
print_list(seq_list); // 输出: [1, 2, 3]
delete(seq_list, 1);
print_list(seq_list); // 输出: [1, 3]
free_list(seq_list);
return 0;
}
代码说明：
- 创建顺序表：
create_list函数分配内存并初始化一个顺序表。- 插入节点：
insert函数在指定索引位置插入一个值。如果顺序表已满或索引超出范围，打印错误信息。- 删除节点：
delete函数删除指定索引位置的值。如果索引超出范围，打印错误信息。- 打印顺序表：
print_list函数打印顺序表中的元素。- 释放顺序表：
free_list函数释放分配的内存。
2.6 演示过程
顺序表插入节点
假设我们有一个顺序表，初始状态如下：
Index: 0 1 2
Data: [A] [B] [C]
我们要在索引位置1插入一个新节点D。步骤如下：
- 从最后一个元素开始，依次向右移动元素，直到达到插入位置。
- 在指定位置插入新元素D。
插入后的顺序表如下：
Index: 0 1 2 3
Data: [A] [D] [B] [C]
顺序表删除节点
接下来，我们删除索引位置2的节点B。步骤如下：
- 从删除位置的下一个元素开始，依次向左移动元素，覆盖删除位置的元素。
- 调整顺序表长度（在图示中表现为减少一个元素）。
删除后的顺序表如下：
Index: 0 1 2
Data: [A] [D] [C]
图示过程
初始顺序表：
Index: 0 1 2
Data: [A] [B] [C]
插入节点D的过程：
- 将索引2的元素[C]向右移动到索引3
- 将索引1的元素[B]向右移动到索引2
- 在索引1处插入新元素[D]
Index: 0 1 2 3
Data: [A] [D] [B] [C]
删除节点B的过程：
- 将索引2的元素[C]向左移动到索引1
- 删除原索引2的元素[B]（在顺序表中体现为长度减少1）
Index: 0 1 2
Data: [A] [D] [C]
3. 链表
3.1 链表的定义
- 链表（Linked List）是一种线性表，其存储结构为一组任意存储单元。链表中的每个元素称为结点（Node），每个结点包含数据域和指针域。指针域指向下一个结点的地址。
3.2 链表的类型
单链表（Singly Linked List）
- 每个结点只包含一个指向后继结点的指针。
双向链表（Doubly Linked List）
- 每个结点包含两个指针，分别指向前驱结点和后继结点。
循环链表（Circular Linked List）
- 链表的最后一个结点的指针指向第一个结点，形成一个环。
3.3 链表的优缺点
优点：
- 插入和删除操作效率高：不需要移动其他元素，只需修改指针即可。
- 动态内存分配：内存利用率高，不会出现内存浪费或不足的问题。
缺点：
- 随机访问性能差：无法通过下标快速访问任意位置的元素，必须从头结点开始遍历。
- 查询效率低：在最坏情况下，时间复杂度为O(n)。
3.4 链表的操作
插入操作
- 在链表中插入一个元素，只需修改相关结点的指针。
删除操作
- 从链表中删除一个元素，只需修改相关结点的指针。
3.5 链表的代码实现
#include <stdio.h>
#include <stdlib.h>
// 定义节点结构体
typedef struct Node {
int value;
struct Node* next;
} Node;
// 定义单链表结构体
typedef struct {
Node* head;
} SinglyLinkedList;
// 创建节点
Node* create_node(int value) {
Node* new_node = (Node*)malloc(sizeof(Node));
if (!new_node) {
printf("Memory allocation error\n");
exit(1);
}
new_node->value = value;
new_node->next = NULL;
return new_node;
}
// 初始化链表
SinglyLinkedList* create_list() {
SinglyLinkedList* list = (SinglyLinkedList*)malloc(sizeof(SinglyLinkedList));
if (!list) {
printf("Memory allocation error\n");
exit(1);
}
list->head = NULL;
return list;
}
// 插入节点
void insert(SinglyLinkedList* list, int index, int value) {
Node* new_node = create_node(value);
if (index == 0) {
new_node->next = list->head;
list->head = new_node;
} else {
Node* prev = list->head;
for (int i = 0; i < index - 1; ++i) {
if (prev == NULL) {
printf("Index out of bounds\n");
return;
}
prev = prev->next;
}
new_node->next = prev->next;
prev->next = new_node;
}
}
// 删除节点
void delete(SinglyLinkedList* list, int index) {
if (list->head == NULL) {
printf("List is empty\n");
return;
}
if (index == 0) {
Node* temp = list->head;
list->head = list->head->next;
free(temp);
} else {
Node* prev = list->head;
for (int i = 0; i < index - 1; ++i) {
if (prev == NULL) {
printf("Index out of bounds\n");
return;
}
prev = prev->next;
}
if (prev->next == NULL) {
printf("Index out of bounds\n");
return;
}
Node* temp = prev->next;
prev->next = temp->next;
free(temp);
}
}
// 打印链表
void print_list(SinglyLinkedList* list) {
Node* current = list->head;
printf("[");
while (current != NULL) {
printf("%d", current->value);
if (current->next != NULL) {
printf(", ");
}
current = current->next;
}
printf("]\n");
}
// 释放链表
void free_list(SinglyLinkedList* list) {
Node* current = list->head;
while (current != NULL) {
Node* temp = current;
current = current->next;
free(temp);
}
free(list);
}
int main() {
SinglyLinkedList* linked_list = create_list();
insert(linked_list, 0, 1);
insert(linked_list, 1, 2);
insert(linked_list, 2, 3);
print_list(linked_list); // 输出: [1, 2, 3]
delete(linked_list, 1);
print_list(linked_list); // 输出: [1, 3]
free_list(linked_list);
return 0;
}
代码说明：
创建节点：
create_node函数分配内存并初始化一个新节点。初始化链表：
create_list函数分配内存并初始化一个空的单链表。插入节点：
insert函数在指定索引位置插入一个值。如果索引超出范围，打印错误信息。删除节点：
delete函数删除指定索引位置的值。如果索引超出范围或链表为空，打印错误信息。打印链表：
print_list函数打印链表中的元素。释放链表：
free_list函数释放分配的内存，防止内存泄漏。
3.6 演示过程
链表插入节点
假设我们有一个链表，初始状态如下：
head -> [A] -> [B] -> [C]
我们要在节点B和节点C之间插入一个新节点D。步骤如下：
- 创建新节点D。
- 将新节点D的指针指向节点C。
- 将节点B的指针指向新节点D。
插入后的链表如下：
head -> [A] -> [B] -> [D] -> [C]
链表删除节点
接下来，我们删除节点B。步骤如下：
- 将节点A的指针从节点B指向节点D。
- 释放节点B的内存（在实际编程中需要释放，但在图示中不需要表现出来）。
删除后的链表如下：
head -> [A] -> [D] -> [C]
初始链表：
+------+ +-----+ +-----+
| head | -> | [A] | -> | [B] | -> | [C] |
+------+ +-----+ +-----+
插入节点D的过程：
+------+ +-----+ +-----+ +-----+
| head | -> | [A] | -> | [B] | -> | [C] |
+------+ +-----+ +-----+
|
V
+-----+
| [D] |
+-----+
完成插入后的链表：
+------+ +-----+ +-----+ +-----+ +-----+
| head | -> | [A] | -> | [B] | -> | [D] | -> | [C] |
+------+ +-----+ +-----+ +-----+
删除节点B的过程：
+------+ +-----+ +-----+ +-----+ +-----+
| head | -> | [A] | -> | [B] | -> | [D] | -> | [C] |
+------+ +-----+ +-----+
|
V
(delete)
完成删除后的链表：
+------+ +-----+ +-----+ +-----+
| head | -> | [A] | -> | [D] | -> | [C] |
+------+ +-----+ +-----+
4. 顺序表与链表的比较
| 特性 | 顺序表 | 链表 |
|---|---|---|
| 存储结构 | 连续内存 | 不连续内存（节点） |
| 访问时间复杂度 | O(1) | O(n) |
| 插入时间复杂度 | O(n) | O(1) |
| 删除时间复杂度 | O(n) | O(1) |
| 空间利用率 | 高 | 低 |
| 动态调整大小 | 困难 | 容易 |
| 内存开销 | 低 | 高（指针开销） |
实际应用场景举例
顺序表：
- 实现栈和队列：访问元素时间复杂度低。
- 需要频繁访问但插入删除较少的场景，如数组处理和矩阵运算。
链表：
- 实现链式队列和链式栈：插入删除时间复杂度低。
- 实现一些动态数据结构，如链表、哈希链表、图的邻接表表示。
希望这些能对刚学习算法的同学们提供些帮助哦！！！
