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

标签：Node head 单链 线性表 int next 链表 数据结构 节点

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

文章目录

• 【数据结构与算法】线性表——顺序储存与单链表
• • 一、线性表的基本概念
  • • 1. 线性表的定义
    • 2. 线性表的分类
  • 二、线性表的顺序存储
  • • 1. 顺序表的基本操作
    • • 1.1 插入操作
      • 1.2 删除操作
      • 1.3 查找操作
  • 三、线性表的链式存储
  • • 1. 单链表的定义
    • 2. 单链表的构建
    • • 2.1 头插法
      • 2.2 尾插法
    • 3. 单链表的插入操作
    • 4. 单链表的删除操作
    • 5. 查找操作
  • 其他

---

一、线性表的基本概念

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指向当前头节点的next
        head->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个位置插入4
    cout << "链表插入后: ";
    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 不存在

---

其他

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

标签：Node,head,单链,线性表,int,next,链表,数据结构,节点
From： https://blog.csdn.net/2302_80127404/article/details/144720165