常见的数据结构---数组、链表、栈的深入剖析

目录

一、数组（Array）

二、链表（Linked List）

三、栈（Stack）

四、总结

---

 数据结构是算法的基石，是程序设计的核心基础。不同的数据结构适用于不同的场景和需求，选择合适的数据结构能显著提升程序的效率和可读性。在众多的数据结构中，数组、链表和栈是最基本、最常用的三种。它们各具特色，不仅应用广泛，也是更复杂数据结构的基础。 

一、数组（Array）

1. 什么是数组

数组是一种用于存储一组具有相同数据类型元素的数据结构。这些元素在内存中按照顺序连续存储，可以通过索引访问每个元素。

定义：

int arr[5]; // 定义一个包含5个整数的数组

特点：

连续存储：所有元素占用的内存是连续的。

固定大小：数组声明后，其大小不能改变。

快速访问：可以通过索引快速访问任意元素，时间复杂度为 O(1)O(1)O(1)。

类型一致性：数组中的元素必须是相同的数据类型。

2. 数组的内存布局

数组在内存中是连续分配的。假设一个数组存储在地址 0x1000 开始，并且元素大小为 4 字节，则：

第一个元素的地址为 0x1000

第二个元素的地址为 0x1004

第 n 个元素的地址计算公式： 元素地址=基地址+(索引×元素大小)

示例：

int arr[3] = {1, 2, 3};
// 内存布局:
// 0x1000: 1
// 0x1004: 2
// 0x1008: 3

3. 数组的基本操作

3.1 声明与初始化

静态声明：

int arr[5];         // 声明大小为5的整型数组
int arr[5] = {1, 2, 3}; // 部分初始化，未赋值的元素默认为0
int arr[] = {4, 5, 6};  // 根据初始化列表自动推断大小

动态分配：

int *arr = (int *)malloc(sizeof(int) * 5); // 动态分配大小为5的整型数组

3.2 访问与修改

数组元素通过索引访问，索引从0开始：

int arr[3] = {10, 20, 30};
arr[1] = 40;  // 修改第二个元素
printf("%d", arr[1]); // 输出40

3.3 遍历数组

使用循环遍历：

for (int i = 0; i < 5; i++) {printf("%d ", arr[i]);
}

4. 数组的种类

4.1 一维数组

最简单的数组类型，用来表示线性数据结构。

int arr[5] = {1, 2, 3, 4, 5};

4.2 多维数组

用于表示多维数据，如矩阵。

int matrix[3][3] = {{1, 2, 3},{4, 5, 6},{7, 8, 9}
};
printf("%d", matrix[1][2]); // 输出6

4.3 动态数组

通过指针动态分配内存的数组。

int *arr = (int *)malloc(sizeof(int) * 5);
// 使用完成后记得释放内存
free(arr);

5. 数组的优缺点

优点：

1. 快速访问：通过索引可以直接访问任意元素。
2. 存储效率高：由于元素连续存储，硬件可以高效缓存和访问。
3. 简单易用：语法简单，操作直观。

缺点：

1. 大小固定：声明后无法动态扩展或收缩。
2. 插入与删除效率低：需要移动大量元素。
3. 内存连续性要求高：对于大数组，可能会因内存碎片而分配失败。

6. 数组的应用场景与注意事项

1. 数据存储与排序：适合存储大小固定的数据，并对其进行排序操作。
2. 快速索引场景：如哈希表中的直接寻址。
3. 矩阵操作：如图像处理中的像素存储。
4. 实现其他数据结构：如栈、队列和字符串。

注意事项

1. 数组越界：访问索引超出范围会导致未定义行为。
2. 内存管理：动态数组需要手动释放分配的内存。
3. 性能优化：频繁的插入或删除操作不适合使用数组。

7. 数组与其他数据结构的对比

8.小结

数组是一种高效的、简单的数据结构，适用于存储固定大小的数据并进行快速访问。然而，其固定大小和插入删除效率低的限制，在一些动态需求下需要其他数据结构（如链表、动态数组）替代。深入理解数组的特性和限制，可以帮助我们更好地在实际开发中合理使用这一基本工具。

二、链表（Linked List）

1. 什么是链表

链表是一种动态数据结构，由多个节点（Node）按线性顺序链接而成。每个节点包含两个部分：

1. 数据域（Data）：存储节点的数据。
2. 指针域（Next）：存储指向下一个节点的地址。

链表通过指针连接形成一个线性结构，常用于需要频繁插入或删除操作的场景。

节点结构：

struct Node {int data;           // 数据域struct Node *next;  // 指针域
};

2. 链表的分类

2.1 单向链表（Singly Linked List）

每个节点只有一个指针，指向下一个节点。

最后一个节点的指针为 NULL，表示链表结束。

示例：

Head -> [Data | Next] -> [Data | Next] -> NULL

2.2 双向链表（Doubly Linked List）

每个节点包含两个指针：一个指向前驱节点，一个指向后继节点。

可以从任意节点向前或向后遍历。

示例：

NULL <- [Prev | Data | Next] <-> [Prev | Data | Next] -> NULL

2.3 循环链表（Circular Linked List）

链表的最后一个节点指向头节点，使链表形成一个环。可为单向或双向。

示例：

[Data | Next] -> [Data | Next] -> [Data | Next] -> ...↑----------------------------------------↑

3. 链表的基本操作

3.1 创建链表

通过动态分配内存创建节点，并将节点链接起来。

struct Node* createNode(int value) {struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));newNode->data = value;newNode->next = NULL;return newNode;
}

3.2 插入节点

1. 头插法：在链表头部插入节点。

   void insertAtHead(struct Node** head, int value) {struct Node* newNode = createNode(value);newNode->next = *head;*head = newNode;
   }
   

2. 尾插法：在链表尾部插入节点。

   void insertAtTail(struct Node** head, int value) {struct Node* newNode = createNode(value);if (*head == NULL) {*head = newNode;return;}struct Node* temp = *head;while (temp->next != NULL) {temp = temp->next;}temp->next = newNode;
   }
   

3.3 删除节点

1. 按值删除：

   void deleteByValue(struct Node** head, int value) {struct Node* temp = *head;struct Node* prev = NULL;// 若删除头节点if (temp != NULL && temp->data == value) {*head = temp->next;free(temp);return;}// 查找要删除的节点while (temp != NULL && temp->data != value) {prev = temp;temp = temp->next;}if (temp == NULL) return; // 值不存在// 重新链接并释放内存prev->next = temp->next;free(temp);
   }
   

3.4 遍历链表

void traverse(struct Node* head) {while (head != NULL) {printf("%d -> ", head->data);head = head->next;}printf("NULL\n");
}

3.5 反转链表

struct Node* reverseList(struct Node* head) {struct Node* prev = NULL;struct Node* current = head;struct Node* next = NULL;while (current != NULL) {next = current->next;current->next = prev;prev = current;current = next;}return prev;
}

4. 链表的优缺点

优点：

1. 动态大小：不需要预先分配固定大小，可以动态增减节点。
2. 高效插入与删除：不需要移动其他元素，时间复杂度为 O(1)O(1)。
3. 节省内存：适合存储大小不确定的数据。

缺点：

1. 随机访问效率低：无法通过索引直接访问元素，需从头遍历，时间复杂度为 O(n)O(n)。
2. 额外内存开销：每个节点都需要存储指针。
3. 实现复杂性高：操作链表需要处理指针，容易引发错误（如野指针、内存泄漏等）。

5. 链表的使用场景

1. 动态内存需求：如实现队列、栈、哈希表等需要动态扩展的结构。
2. 频繁插入与删除：如处理任务队列、缓冲区。
3. 内存碎片化环境：连续存储难以满足时，链表可以更好地利用内存。

---

6. 链表与数组的对比

7. 注意事项

1. 内存管理：动态分配的内存需要手动释放，防止内存泄漏。
2. 指针处理：链表操作需要谨慎处理指针，避免野指针或空指针。
3. 遍历复杂度：链表不适合需要频繁访问特定位置的场景。

8.小结

链表作为一种灵活且动态的数据结构，在处理动态数据、内存碎片化环境中非常实用。通过理解其基本操作与优缺点，开发者可以在合适的场景中高效地使用链表。同时，链表的概念是进一步学习更复杂数据结构（如树和图）的基础，非常重要。

三、栈（Stack）

1. 什么是栈

栈是一种抽象数据类型，遵循后进先出（LIFO, Last In First Out）**的线性数据结构。栈中的数据只能通过一端进行插入和删除，这一端被称为栈顶（Top）。

栈顶（Top）：表示栈中最新加入的元素。

栈底（Bottom）：表示栈中最早加入的元素。

关键操作：

入栈（Push）：将数据插入栈顶。

出栈（Pop）：从栈顶删除数据。

查看栈顶元素（Peek/Top）：访问栈顶数据但不删除。

2. 栈的实现

2.1 使用数组实现栈

栈可以通过数组来实现，栈顶通过数组的索引表示。

示例代码：

#include <stdio.h>
#include <stdlib.h>
#define MAX 100typedef struct Stack {int arr[MAX];int top;
} Stack;// 初始化栈
void initStack(Stack* stack) {stack->top = -1;
}// 入栈
void push(Stack* stack, int value) {if (stack->top == MAX - 1) {printf("Stack Overflow\n");return;}stack->arr[++stack->top] = value;
}// 出栈
int pop(Stack* stack) {if (stack->top == -1) {printf("Stack Underflow\n");return -1;}return stack->arr[stack->top--];
}// 查看栈顶
int peek(Stack* stack) {if (stack->top == -1) {printf("Stack is empty\n");return -1;}return stack->arr[stack->top];
}

2.2 使用链表实现栈

链表实现栈可以动态调整大小，不受固定容量限制。

示例代码：

#include <stdio.h>
#include <stdlib.h>typedef struct Node {int data;struct Node* next;
} Node;// 入栈
void push(Node** top, int value) {Node* newNode = (Node*)malloc(sizeof(Node));newNode->data = value;newNode->next = *top;*top = newNode;
}// 出栈
int pop(Node** top) {if (*top == NULL) {printf("Stack Underflow\n");return -1;}Node* temp = *top;int popped = temp->data;*top = temp->next;free(temp);return popped;
}// 查看栈顶
int peek(Node* top) {if (top == NULL) {printf("Stack is empty\n");return -1;}return top->data;
}

3. 栈的应用场景

3.1 函数调用栈

编程语言运行时会使用栈存储函数的局部变量、返回地址等信息。

函数的调用和返回严格遵循后进先出原则。

3.2 表达式求值

栈用于处理中缀表达式到后缀表达式的转换，以及后缀表达式的求值。

例如：算术表达式计算。

3.3 括号匹配

检查字符串中的括号是否成对匹配，常用于编译器和代码编辑器的语法检查。

3.4 深度优先搜索（DFS）

栈在实现深度优先搜索算法时用于存储路径信息。

3.5 撤销操作

栈记录用户操作的历史，用于实现撤销（Undo）功能。

4. 栈的优缺点

优点：

1. 操作简单：只需要维护栈顶，插入和删除操作时间复杂度均为 O(1)O(1)。
2. 内存管理：内存分配集中在栈顶，易于管理。
3. 适用场景广泛：特别适合递归和后进先出的场景。

缺点：

1. 容量有限：基于数组的栈需要预先分配固定大小，可能造成溢出。
2. 非灵活访问：只能访问栈顶元素，无法随机访问栈中其他元素。

5. 栈的实现方式对比

1. 数组实现：
   • 使用一个数组来存储栈中的元素，并使用一个变量来跟踪栈顶的位置。
   • 优点是访问速度快，因为直接通过索引访问；缺点是在预先定义的大小之外添加元素可能会导致问题。
2. 链表实现：
   • 使用链表来存储栈中的元素，每个节点包含元素值和指向下一个节点的指针。
   • 优点是可以动态地增加或减少栈的大小；缺点是访问速度相对较慢，因为需要遍历链表。

6. 栈与队列的对比

7. 栈的注意事项

1. 溢出问题：基于数组的栈在容量满时会发生溢出，需要提前处理。
2. 递归深度限制：递归调用过深可能导致函数调用栈溢出。
3. 内存管理：链表实现的栈需要手动释放节点内存，防止内存泄漏。
4. 最小栈：在栈中以常数时间获取当前栈的最小值。
5. 双栈模拟队列：使用两个栈实现队列操作。
6. 多栈共享数组：一个数组同时存储多个栈的数据。

8.小结

栈是一种重要的数据结构，其后进先出的特性使得它在递归、表达式求值、括号匹配等场景中应用广泛。通过理解栈的基本操作和实现方式，可以帮助开发者灵活应用栈，并掌握其在算法和系统设计中的重要作用。

四、总结

数组、链表和栈是编程中最基础的数据结构，它们各具特色，适用于不同的场景：

数组提供高效的随机访问，但大小固定且不适合频繁增删。

链表适合动态存储和频繁插入删除，但随机访问效率较低。

栈专注于后进先出的顺序操作，应用场景广泛。

数组、链表和栈作为程序设计中最基础的数据结构，各自有着独特的优势与应用场景。数组因其固定的内存分配和高效的随机访问能力，适合用于数据规模确定的场景；链表因其灵活的内存管理，适用于频繁插入和删除的需求；而栈则以其后进先出的特性，在递归、表达式求值等领域扮演着不可或缺的角色。熟练掌握这三种数据结构，是深入理解算法和设计更高效程序的必经之路。