重庆建设工程信息网证书查询官网_应用商店下载安装正版最新版_app引流推广方法_网络推广自学

【数据结构与算法】线性表——顺序储存与单链表

---

一、线性表的基本概念

1. 线性表的定义

线性表是一种线性数据结构，由n（n ≥ 0）个数据元素构成的一个有限序列，每个数据元素都是相同类型的，称为线性表的元素，且数据元素之间具有一对一的线性关系，除第一个元素外，每个元素只有一个前驱；除最后一个元素外，每个元素只有一个后继。

形式化定义：
一个线性表可以表示为：(a1, a2, ..., an)

• a1 是第一个元素，没有前驱。
• an 是最后一个元素，没有后继。
• 其他元素 ai (1 < i < n) 有且只有一个前驱和一个后继。

线性表的特点：
线性表具有以下几个主要特点：

1. 有序性： 数据元素按照一定的线性顺序排列，顺序是固定的。
   例如，在线性表(a1, a2, a3)中，a1始终在a2之前，a2始终在a3之前。

2. 唯一性：每个数据元素在逻辑上是唯一的，表中的每个元素都可以通过其位置或值唯一确定。

3. 有限性：线性表中的元素个数是有限的，可以为空表（没有任何元素）。

4. 动态性：在线性表中，可以动态地插入或删除元素，但操作后仍需保持线性结构。

---

2. 线性表的分类

根据存储方式和实现方法，线性表可以分为两种主要形式：顺序存储的线性表和链式存储的线性表。这两种存储方式各有特点，适用于不同的场景。

顺序存储与链式存储的对比

比较维度	顺序存储	链式存储
存储方式	连续存储单元	非连续存储单元，通过指针连接
随机访问	支持，访问效率高	不支持，需从头节点遍历
插入与删除效率	低，需要移动大量数据	高，只需调整指针
内存利用率	固定大小，可能浪费或溢出	动态分配，内存利用率高
实现复杂度	简单	复杂，需操作指针
适用场景	数据量已知，访问操作频繁	数据量不定，插入删除频繁

---

二、线性表的顺序存储

顺序存储是线性表的一种存储形式，其数据元素按照逻辑顺序依次存储在连续的存储空间中，在顺序表中，每个数据元素均可通过数组下标进行访问，存储位置 i 的数据元素与逻辑位置 i 一一对应，通常使用数组实现。

顺序表的特点

1. 逻辑与物理地址一致：顺序表中，逻辑位置为 i 的数据元素直接存储在数组的第 i-1 个存储单元中。
2. 随机访问：由于存储空间是连续的，可以通过数组下标直接访问任意元素，时间复杂度为 O(1)。
3. 固定容量：顺序表的容量在初始化时确定，不能动态扩展或缩减。
4. 插入和删除效率低：插入元素时，需将插入位置之后的所有元素向后移动；删除元素时，需将删除位置之后的所有元素向前移动，时间复杂度为 O(n)。
5. 内存利用率低：需要预先分配连续的存储空间，若元素数量不足，可能造成内存浪费；若元素数量超出分配容量，需重新申请更大的内存并复制原数据。
6. 扩展性差：无法根据实际需求动态调整大小。

假设线性表中每个元素占k个单元，第一个元素的地址为loc(a1)，则第i个元素的地址为：

顺序储存结构示意图：

---

1. 顺序表的基本操作

顺序表的基本操作主要包括插入、删除和查找。

1.1 插入操作

在顺序表的指定位置插入一个新的数据元素。

步骤：

1. 检查是否有足够的存储空间，若顺序表已满，返回错误。
2. 检查插入位置是否合法（通常要求插入位置在 [1, n+1] 范围内）。
3. 将插入位置之后的所有元素向后移动一位。
4. 在插入位置存入新元素，并更新表长。

时间复杂度：

• 最坏情况（插入到表头）：O(n)。
• 最好情况（插入到表尾）：O(1)。
• 平均情况：O(n)。

C++实现：

void Insert(int A[], int &n, int pos, int value) {if (n >= Arr_SIZE) return; // 检查是否溢出for (int i = n - 1; i >= pos - 1; i--) {A[i + 1] = A[i]; // 向后移动元素}A[pos - 1] = value; // 插入新元素n++; // 表长加 1
}

---

1.2 删除操作

从顺序表的指定位置删除一个数据元素。

步骤：

1. 检查删除位置是否合法（通常要求删除位置在 [1, n] 范围内）。
2. 将删除位置之后的所有元素向前移动一位，覆盖被删除的元素。
3. 更新表长。

时间复杂度：

• 最坏情况（删除表头）：O(n)。
• 最好情况（删除表尾）：O(1)。
• 平均情况：O(n)。

C++实现：

void Delete(int A[], int &n, int pos) {if (pos < 1 || pos > n) return; // 检查位置合法性for (int i = pos - 1; i < n - 1; i++) {A[i] = A[i + 1]; // 向前移动元素}n--; // 表长减 1
}

---

1.3 查找操作

根据指定的条件（如值或位置）查找数据元素，并返回其位置或值。

步骤：

1. 若根据位置查找：直接通过数组下标访问元素。
2. 若根据值查找：依次遍历数组，找到与目标值匹配的元素。

时间复杂度：

• 根据位置查找：O(1)。
• 根据值查找：O(n)。

C++实现：

int FindByValue(int A[], int n, int value) {for (int i = 0; i < n; i++) {if (A[i] == value) return i + 1; // 返回逻辑位置}return -1; // 未找到
}int FindByPosition(int A[], int n, int pos) {if (pos < 1 || pos > n) return -1; // 检查位置合法性return A[pos - 1]; // 返回元素值
}

---

三、线性表的链式存储

链式存储是一种通过节点与指针动态存储线性表的实现方式。与顺序存储不同，链式存储不要求数据元素在物理存储上连续排列，而是通过指针连接每个节点。

1. 单链表的定义

单链表是一种链式存储的线性表，每个节点由两个部分组成：

1. 数据域（data）：存储数据元素的值。
2. 指针域（next）：存储指向下一个节点的地址。

通过指针将每个节点连接起来，形成一个单向的链式结构，首节点称为头节点，末尾节点的指针域为 NULL。

单链表的特点

1. 灵活性：内存可以动态分配，不需要提前预定存储空间，内存利用率高。
2. 插入和删除效率高：在指定位置进行插入和删除操作时，无需移动其他节点，只需改变指针指向即可，时间复杂度为 O(1)。
3. 无法随机访问：单链表不支持通过下标直接访问指定元素，只能从头节点开始依次遍历，访问效率低，时间复杂度为 O(n)。
4. 单向性：指针只能从头节点到尾节点单向移动，无法直接访问前驱节点。

---

2. 单链表的构建

单链表的创建是构建链式存储结构的第一步，它将一个线性表通过动态分配的方式分解为多个节点，并通过指针将这些节点链接起来。单链表的构建可以通过两种常用方法实现：头插法和尾插法。

2.1 头插法

头插法是将新节点插入到链表的头部，使新节点成为链表的第一个有效节点（即头节点之后的节点）。每次插入时，将新节点的 next 指针指向当前链表的头部，随后更新链表的头指针。

• 新节点总是插入到链表的最前面，适合生成逆序的链表。
• 时间复杂度为 O(1)，插入操作仅涉及修改少量指针。
• 适合当插入操作较频繁，且无需维护顺序时使用。

步骤：

1. 为新节点分配内存空间。
2. 将新节点的数据域赋值。
3. 修改新节点的 next 指针，使其指向当前链表的第一个节点。
4. 更新链表的头指针，使其指向新节点。

C++实现：

struct Node {int data;    // 数据域Node *next;  // 指针域
};Node* Create(int arr[], int n) {Node *head = new Node(); // 创建头节点head->next = NULL;       // 初始化头节点的指针域为空for (int i = 0; i < n; i++) {Node *newNode = new Node(); // 创建新节点newNode->data = arr[i];     // 赋值数据域newNode->next = head->next; // 新节点的next指向当前头节点的nexthead->next = newNode;       // 更新头节点的next指向新节点}return head; // 返回链表的头节点
}

若输入数组为 {1, 2, 3, 4}，则通过头插法创建的单链表为：

Head -> 4 -> 3 -> 2 -> 1 -> NULL

2.2 尾插法

尾插法是将新节点插入到链表的尾部，使新节点始终保持在链表的最后。每次插入时，找到当前链表的尾节点，将其 next 指针指向新节点，并更新尾指针。

• 新节点始终插入到链表的末尾，适合生成正序的链表。
• 时间复杂度为 O(1)（若维护尾指针），仅需修改当前尾节点的 next 指针。
• 适合当需要维护链表元素顺序时使用。

步骤：

1. 为新节点分配内存空间。
2. 将新节点的数据域赋值。
3. 修改当前尾节点的 next 指针，使其指向新节点。
4. 更新尾指针，使其指向新节点。

C++实现：

struct Node {int data;    // 数据域Node *next;  // 指针域
};Node* Create(int arr[], int n) {Node *head = new Node(); // 创建头节点head->next = NULL;       // 初始化头节点的指针域为空Node *tail = head;       // 初始化尾指针指向头节点for (int i = 0; i < n; i++) {Node *newNode = new Node(); // 创建新节点newNode->data = arr[i];     // 赋值数据域newNode->next = NULL;       // 新节点的next初始化为空tail->next = newNode;       // 当前尾节点的next指向新节点tail = newNode;             // 更新尾指针为新节点}return head; // 返回链表的头节点
}

若输入数组为 {1, 2, 3, 4}，则通过尾插法创建的单链表为：

Head -> 1 -> 2 -> 3 -> 4 -> NULL

单链表历遍

int main() {int arr[] = {1, 2, 3, 4};Node *head = CreateListTailInsert(arr, 4);Node *p = head->next; // 遍历链表输出while (p != NULL) {printf("%d ", p->data);p = p->next;}return 0;
}

输出：

1 2 3 4

---

3. 单链表的插入操作

插入操作是向单链表中某个指定位置插入一个新节点的过程。它需要根据指定的插入位置，调整链表中相应节点的指针，确保链表结构的完整性。

插入步骤

假设单链表的节点定义如下：

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

1. 找到插入位置的前驱节点

   • 从链表的头节点开始，依次遍历，找到插入位置的前驱节点（即目标位置前一个节点）。
   • 如果目标位置是第 1 个节点（即插入头部），则前驱节点是头节点。

2. 创建新节点

   • 为新节点分配内存空间，并将插入的值赋给新节点的 data。
   • 将新节点的 next 指针指向插入位置的原节点（即前驱节点的 next 所指向的节点）。

3. 调整指针

   • 将前驱节点的 next 指针指向新节点，从而将新节点插入到链表中。

4. 检查边界情况

   • 确保插入位置合法（如目标位置不超过链表长度）。
   • 注意处理空链表的特殊情况。

C++实现

以下为单链表插入操作的伪代码（以第 pos 个位置插入值 value 为例）：

void Insert(Node *head, int pos, int value) {// 找到插入位置的前驱节点Node *p = head;for (int i = 0; i < pos - 1 && p != NULL; i++) {p = p->next; // 遍历链表，找到第 pos-1 个节点}if (p == NULL) return; // 检查插入位置是否合法// 创建新节点Node *newNode = new Node();newNode->data = value; // 赋值新节点的数据域newNode->next = p->next; // 新节点的 next 指向插入位置的原节点// 修改前驱节点的指针域p->next = newNode;
}

---

代码实现：

#include <iostream>
using namespace std;struct Node {int data;    // 数据域Node *next;  // 指针域
};// 插入函数
void Insert(Node *head, int pos, int value) {Node *p = head;for (int i = 0; i < pos - 1 && p != NULL; i++) {p = p->next; // 找到前驱节点}if (p == NULL) return; // 检查位置是否合法Node *newNode = new Node();newNode->data = value;     // 创建新节点并赋值newNode->next = p->next;   // 新节点的 next 指向原节点p->next = newNode;         // 前驱节点指向新节点
}// 打印链表
void PrintList(Node *head) {Node *p = head->next; // 跳过头节点while (p != NULL) {cout << p->data << " ";p = p->next;}cout << endl;
}// 主函数
int main() {// 创建链表Node *head = new Node(); // 创建头节点head->next = NULL;// 添加初始数据Insert(head, 1, 1); // 插入到第1个位置Insert(head, 2, 2); // 插入到第2个位置Insert(head, 3, 3); // 插入到第3个位置// 插入新的节点cout << "链表插入前: ";PrintList(head);Insert(head, 2, 4); // 在第2个位置插入4cout << "链表插入后: ";PrintList(head);return 0;
}

运行结果：

链表插入前: 1 2 3 
链表插入后: 1 4 2 3 

---

4. 单链表的删除操作

单链表的删除操作是指移除链表中的某个节点。为了保证链表结构的完整性，删除一个节点后，需要调整相邻节点的指针并释放被删除节点的内存。

删除步骤

假设单链表的节点定义如下：

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

1. 找到删除位置的前驱节点

   • 从链表头节点开始，依次遍历，找到目标节点的前驱节点。
   • 如果目标节点是第一个有效节点，则前驱节点是头节点。

2. 调整指针

   • 将前驱节点的 next 指针指向目标节点的后继节点（即目标节点的 next 所指向的节点）。

3. 释放被删除节点的内存

   • 删除目标节点，释放其占用的内存，避免内存泄漏。

4. 边界检查

   • 确保删除位置合法（不能超过链表长度，不能为负值）。
   • 对空链表或删除超出范围节点的操作需要提前判断。

C++实现
以下为单链表删除操作的伪代码（以第 pos 个位置的节点为例）：

void Delete(Node *head, int pos) {Node *p = head;for (int i = 0; i < pos - 1 && p != NULL; i++) {p = p->next; // 找到前驱节点}if (p == NULL || p->next == NULL) return; // 检查位置是否合法Node *delNode = p->next; // 标记要删除的节点p->next = delNode->next; // 前驱节点指向后继节点delete delNode;          // 释放删除的节点
}

代码实现：

#include <iostream>
using namespace std;struct Node {int data;    // 数据域Node *next;  // 指针域
};// 删除函数
void Delete(Node *head, int pos) {Node *p = head;for (int i = 0; i < pos - 1 && p != NULL; i++) {p = p->next; // 找到前驱节点}if (p == NULL || p->next == NULL) return; // 检查位置是否合法Node *delNode = p->next; // 标记要删除的节点p->next = delNode->next; // 前驱节点指向后继节点delete delNode;          // 释放删除的节点
}// 打印链表
void PrintList(Node *head) {Node *p = head->next; // 跳过头节点while (p != NULL) {cout << p->data << " ";p = p->next;}cout << endl;
}// 主函数
int main() {// 创建链表Node *head = new Node(); // 创建头节点head->next = NULL;// 插入初始数据Node *p = head;for (int i = 1; i <= 3; i++) {Node *newNode = new Node();newNode->data = i;newNode->next = NULL;p->next = newNode;p = newNode;}// 打印链表cout << "链表删除前: ";PrintList(head);// 删除第2个节点Delete(head, 2);cout << "链表删除后: ";PrintList(head);return 0;
}

运行结果：

链表删除前: 1 2 3 
链表删除后: 1 3 

---

5. 查找操作

单链表的查找操作分为两种情况：

1. 按值查找：根据给定值，找到链表中第一个匹配该值的节点并返回。
2. 按位置查找：根据给定位置，找到链表中对应位置的节点并返回。

无论是哪种查找方式，都需要从头节点开始依次遍历链表，直到找到目标节点或者链表末尾。

按值查找步骤

1. 从头节点的下一个节点（第一个有效节点）开始遍历链表。
2. 将每个节点的 data 域与目标值进行比较。
3. 如果找到值相等的节点，返回该节点的地址。
4. 如果遍历完整个链表未找到，返回 NULL。

按位置查找步骤

1. 从头节点的下一个节点（第一个有效节点）开始遍历链表。
2. 使用计数器记录当前节点的位置。
3. 当计数器等于目标位置时，返回该节点的地址。
4. 如果遍历完整个链表未找到，或目标位置超出链表范围，返回 NULL。

---

C++实现

按值查找

Node* FindByValue(Node *head, int value) {Node *p = head->next; // 从第一个有效节点开始while (p != NULL && p->data != value) {p = p->next; // 遍历链表}return p; // 返回找到的节点地址，若未找到返回 NULL
}

按位置查找

Node* FindByPosition(Node *head, int pos) {Node *p = head->next; // 从第一个有效节点开始for (int i = 0; i < pos - 1 && p != NULL; i++) {p = p->next; // 遍历链表}return p; // 返回找到的节点地址，若未找到返回 NULL
}

---

代码实现

#include <iostream>
using namespace std;struct Node {int data;    // 数据域Node *next;  // 指针域
};// 按值查找
Node* FindByValue(Node *head, int value) {Node *p = head->next; // 从第一个有效节点开始while (p != NULL && p->data != value) {p = p->next; // 遍历链表}return p; // 返回找到的节点地址，若未找到返回 NULL
}// 按位置查找
Node* FindByPosition(Node *head, int pos) {Node *p = head->next; // 从第一个有效节点开始for (int i = 0; i < pos - 1 && p != NULL; i++) {p = p->next; // 遍历链表}return p; // 返回找到的节点地址，若未找到返回 NULL
}// 打印链表
void PrintList(Node *head) {Node *p = head->next; // 跳过头节点while (p != NULL) {cout << p->data << " ";p = p->next;}cout << endl;
}// 创建链表（尾插法）
Node* CreateList(int arr[], int n) {Node *head = new Node(); // 创建头节点head->next = NULL;Node *tail = head; // 尾指针指向头节点for (int i = 0; i < n; i++) {Node *newNode = new Node();newNode->data = arr[i];newNode->next = NULL;tail->next = newNode; // 尾节点指向新节点tail = newNode;       // 更新尾指针}return head; // 返回头节点
}// 主函数
int main() {// 初始化链表int arr[] = {10, 20, 30, 40, 50};Node *head = CreateList(arr, 5);// 打印链表cout << "链表内容: ";PrintList(head);// 按值查找int value = 30;Node *node1 = FindByValue(head, value);if (node1) {cout << "按值查找: 值 " << value << " 的节点地址为 " << node1 << endl;} else {cout << "按值查找: 值 " << value << " 未找到" << endl;}// 按位置查找int pos = 3;Node *node2 = FindByPosition(head, pos);if (node2) {cout << "按位置查找: 第 " << pos << " 个节点的值为 " << node2->data << endl;} else {cout << "按位置查找: 位置 " << pos << " 不存在" << endl;}return 0;
}

---

运行结果
假设链表为 {10, 20, 30, 40, 50}：

输入查找值为 30，位置为 3：

链表内容: 10 20 30 40 50 
按值查找: 值 30 的节点地址为 0x55d8b7f04b60
按位置查找: 第 3 个节点的值为 30

输入查找值为 60，位置为 6：

链表内容: 10 20 30 40 50 
按值查找: 值 60 未找到
按位置查找: 位置 6 不存在

---

其他

【数据结构与算法】数据结构与算法的基本概念