• C++

  • 📚 C++ 线性表（Linear List）：顺序表和单链表

  • @ 2025-5-22 22:55:29

📚 C++线性表完全教程：从入门到精通（结构体实现版）

🌟 欢迎进入数据结构的世界

在编程的世界里，我们经常需要处理大量的数据。如何高效地存储、管理和操作这些数据呢？这就需要用到数据结构。而线性表作为最基础、最常用的数据结构之一，是我们必须掌握的核心知识！

今天，我们就来系统学习C++中的线性表，使用结构体实现且不使用函数模板，从概念到实现，从理论到实战，一步一步揭开它的神秘面纱！

🧩 什么是线性表？

线性表是一种数据元素按顺序排列的线性结构，它具有以下特点：

  • 元素有序：元素之间存在一对一的前驱和后继关系
  • 有限个元素：线性表的长度是有限的
  • 同构性：所有元素的类型相同

🌰 生活中的线性表比喻

线性表就像一列火车：

  • 每个车厢是一个数据元素
  • 车厢之间按照顺序连接
  • 可以在任意位置添加或移除车厢
  • 可以从头或尾依次访问每个车厢

线性表的分类

线性表主要分为两种实现方式：

  1. 顺序表：用数组实现，元素存储在连续的内存空间中
  2. 链表：用节点实现，每个节点包含数据和指向下一个节点的指针

下面我们分别深入学习这两种实现方式！

📦 顺序表（Array List）

🔧 基本概念

顺序表是线性表的顺序存储结构，它使用数组来存储元素。

🌟 优点

  • 随机访问效率高（O(1)时间复杂度）
  • 实现简单
  • 内存空间连续，缓存利用率高

🚫 缺点

  • 插入和删除操作效率低（平均O(n)时间复杂度）
  • 需要预先分配固定大小的内存空间
  • 扩展容量时需要重新分配内存并复制数据

🛠️ C++结构体实现顺序表（以int类型为例）

下面是一个使用结构体实现的顺序表：

#include <iostream>
using namespace std;

// 定义顺序表结构体（存储int类型数据）
struct ArrayList {
    int* data;          // 存储数据的数组
    int capacity;     // 数组容量
    int size;         // 当前元素个数
    
    // 初始化顺序表
    void init(int initCapacity = 10) {
        data = new int[initCapacity];
        capacity = initCapacity;
        size = 0;
    }
    
    // 销毁顺序表
    void destroy() {
        delete[] data;
        capacity = 0;
        size = 0;
    }
    
    // 获取元素个数
    int getSize() const {
        return size;
    }
    
    // 判断是否为空
    bool isEmpty() const {
        return size == 0;
    }
    
    // 在末尾添加元素
    void add(int element) {
        if (size == capacity) {
            resize(2 * capacity);  // 扩容为原来的2倍
        }
        data[size++] = element;
    }
    
    // 在指定位置插入元素
    void insert(int index, int element) {
        if (index < 0 || index > size) {
            cout << "插入位置不合法" << endl;
            return;
        }
        
        if (size == capacity) {
            resize(2 * capacity);
        }
        
        // 将index及其后面的元素后移一位
        for (int i = size; i > index; i--) {
            data[i] = data[i - 1];
        }
        
        data[index] = element;
        size++;
    }
    
    // 删除指定位置的元素
    int remove(int index) {
        if (index < 0 || index >= size) {
            cout << "删除位置不合法" << endl;
            return -1;  // 返回错误值
        }
        
        int removed = data[index];
        
        // 将index后面的元素前移一位
        for (int i = index; i < size - 1; i++) {
            data[i] = data[i + 1];
        }
        
        size--;
        
        // 如果元素个数小于容量的1/4，则缩容为原来的1/2
        if (size <= capacity / 4 && capacity > 10) {
            resize(capacity / 2);
        }
        
        return removed;
    }
    
    // 获取指定位置的元素
    int get(int index) const {
        if (index < 0 || index >= size) {
            cout << "访问位置不合法" << endl;
            return -1;  // 返回错误值
        }
        return data[index];
    }
    
    // 修改指定位置的元素
    void set(int index, int element) {
        if (index < 0 || index >= size) {
            cout << "修改位置不合法" << endl;
            return;
        }
        data[index] = element;
    }
    
    // 查找元素第一次出现的位置
    int find(int element) const {
        for (int i = 0; i < size; i++) {
            if (data[i] == element) {
                return i;
            }
        }
        return -1;  // 未找到
    }
    
    // 打印所有元素
    void print() const {
        cout << "ArrayList: size = " << size << ", capacity = " << capacity << endl;
        cout << "[";
        for (int i = 0; i < size; i++) {
            cout << data[i];
            if (i != size - 1) {
                cout << ", ";
            }
        }
        cout << "]" << endl;
    }
    
private:
    // 扩容函数（私有方法）
    void resize(int newCapacity) {
        int* newData = new int[newCapacity];
        for (int i = 0; i < size; i++) {
            newData[i] = data[i];
        }
        delete[] data;
        data = newData;
        capacity = newCapacity;
    }
};

int main() {
    ArrayList list;
    list.init();  // 初始化顺序表
    
    // 添加元素
    list.add(10);
    list.add(20);
    list.add(30);
    list.print();  // 输出: [10, 20, 30]
    
    // 插入元素
    list.insert(1, 15);
    list.print();  // 输出: [10, 15, 20, 30]
    
    // 删除元素
    list.remove(2);
    list.print();  // 输出: [10, 15, 30]
    
    // 修改元素
    list.set(0, 100);
    list.print();  // 输出: [100, 15, 30]
    
    // 查找元素
    cout << "元素15的位置是: " << list.find(15) << endl;  // 输出: 1
    
    list.destroy();  // 销毁顺序表
    
    return 0;
}

🔗 链表（Linked List）

🔧 基本概念

链表是线性表的链式存储结构，它由一系列节点组成，每个节点包含：

  • 数据域：存储元素的值
  • 指针域：指向下一个节点的指针（单链表）

🌟 优点

  • 插入和删除操作效率高（O(1)时间复杂度，前提是已知插入/删除位置）
  • 动态分配内存，无需预先分配固定大小
  • 适合频繁插入和删除的场景

🚫 缺点

  • 随机访问效率低（O(n)时间复杂度）
  • 需要额外的空间存储指针
  • 缓存利用率低

链表的分类

链表可以分为：

  1. 单链表：每个节点只有一个指向下一个节点的指针
  2. 双向链表：每个节点有两个指针，分别指向前驱和后继节点
  3. 循环链表：尾节点的指针指向头节点，形成一个环

🛠️ C++结构体实现单链表（以int类型为例）

下面是一个使用结构体实现的单链表：

#include <iostream>
using namespace std;

// 定义链表节点结构体（存储int类型数据）
struct Node {
    int data;
    Node* next;
    
    Node(int value) : data(value), next(nullptr) {}
};

// 定义链表结构体
struct LinkedList {
    Node* head;  // 头指针
    int size;    // 链表长度
    
    // 初始化链表
    void init() {
        head = nullptr;
        size = 0;
    }
    
    // 销毁链表
    void destroy() {
        while (head != nullptr) {
            Node* temp = head;
            head = head->next;
            delete temp;
        }
        size = 0;
    }
    
    // 判断链表是否为空
    bool isEmpty() const {
        return size == 0;
    }
    
    // 获取链表长度
    int getSize() const {
        return size;
    }
    
    // 在头部插入元素
    void insertAtHead(int element) {
        Node* newNode = new Node(element);
        newNode->next = head;
        head = newNode;
        size++;
    }
    
    // 在尾部插入元素
    void insertAtTail(int element) {
        if (isEmpty()) {
            insertAtHead(element);
            return;
        }
        
        Node* current = head;
        while (current->next != nullptr) {
            current = current->next;
        }
        
        Node* newNode = new Node(element);
        current->next = newNode;
        size++;
    }
    
    // 在指定位置插入元素
    void insert(int index, int element) {
        if (index < 0 || index > size) {
            cout << "插入位置不合法" << endl;
            return;
        }
        
        if (index == 0) {
            insertAtHead(element);
            return;
        }
        
        Node* current = head;
        for (int i = 0; i < index - 1; i++) {
            current = current->next;
        }
        
        Node* newNode = new Node(element);
        newNode->next = current->next;
        current->next = newNode;
        size++;
    }
    
    // 删除头部元素
    void removeAtHead() {
        if (isEmpty()) {
            cout << "链表为空，无法删除" << endl;
            return;
        }
        
        Node* temp = head;
        head = head->next;
        delete temp;
        size--;
    }
    
    // 删除尾部元素
    void removeAtTail() {
        if (isEmpty()) {
            cout << "链表为空，无法删除" << endl;
            return;
        }
        
        if (size == 1) {
            removeAtHead();
            return;
        }
        
        Node* current = head;
        while (current->next->next != nullptr) {
            current = current->next;
        }
        
        delete current->next;
        current->next = nullptr;
        size--;
    }
    
    // 删除指定位置的元素
    void remove(int index) {
        if (index < 0 || index >= size) {
            cout << "删除位置不合法" << endl;
            return;
        }
        
        if (index == 0) {
            removeAtHead();
            return;
        }
        
        Node* current = head;
        for (int i = 0; i < index - 1; i++) {
            current = current->next;
        }
        
        Node* temp = current->next;
        current->next = temp->next;
        delete temp;
        size--;
    }
    
    // 获取指定位置的元素
    int get(int index) const {
        if (index < 0 || index >= size) {
            cout << "访问位置不合法" << endl;
            return -1;  // 返回错误值
        }
        
        Node* current = head;
        for (int i = 0; i < index; i++) {
            current = current->next;
        }
        
        return current->data;
    }
    
    // 查找元素第一次出现的位置
    int find(int element) const {
        Node* current = head;
        int index = 0;
        
        while (current != nullptr) {
            if (current->data == element) {
                return index;
            }
            current = current->next;
            index++;
        }
        
        return -1;  // 未找到
    }
    
    // 打印链表
    void print() const {
        Node* current = head;
        
        cout << "LinkedList: size = " << size << endl;
        cout << "[";
        
        while (current != nullptr) {
            cout << current->data;
            if (current->next != nullptr) {
                cout << " -> ";
            }
            current = current->next;
        }
        
        cout << "]" << endl;
    }
};

int main() {
    LinkedList list;
    list.init();  // 初始化链表
    
    // 添加元素
    list.insertAtTail(10);
    list.insertAtTail(20);
    list.insertAtTail(30);
    list.print();  // 输出: [10 -> 20 -> 30]
    
    // 插入元素
    list.insert(1, 15);
    list.print();  // 输出: [10 -> 15 -> 20 -> 30]
    
    // 删除元素
    list.remove(2);
    list.print();  // 输出: [10 -> 15 -> 30]
    
    // 查找元素
    cout << "元素15的位置是: " << list.find(15) << endl;  // 输出: 1
    
    list.destroy();  // 销毁链表
    
    return 0;
}

📊 顺序表 vs 链表

特性 顺序表 (数组) 链表 (Linked List)
存储结构 连续内存空间 离散内存空间，通过指针连接
随机访问 O(1)（高效） O(n)（低效）
插入/删除操作 O(n)（平均需移动元素） O(1)（已知位置时）
内存利用率 预分配可能导致浪费 按需分配，无内存浪费
空间开销 仅数据存储 数据 + 指针（额外开销）
适用场景 频繁随机访问，较少插入删除 频繁插入删除，较少随机访问

💡 线性表的应用场景

线性表是许多复杂数据结构的基础，常见应用场景包括：

  1. 数组、列表：存储和管理批量数据
  2. 栈和队列：基于线性表实现的受限访问数据结构
  3. 哈希表：处理冲突时可能使用链表
  4. 图的邻接表表示：使用链表存储图的边信息
  5. 文件系统：目录结构通常使用线性表组织

掌握线性表的基础知识，对于学习更高级的数据结构和算法至关重要！

🌟 总结与鼓励

恭喜你完成了C++线性表的学习！现在你已经掌握了：

  1. 线性表的基本概念和两种主要实现方式
  2. 使用结构体实现顺序表和链表的方法（不使用函数模板）
  3. 顺序表和链表的优缺点及适用场景
  4. 线性表的常见操作和应用场景

线性表是数据结构的基础，希望你能够熟练掌握并灵活运用。继续加油，你一定能在编程的道路上越走越远！ 💪

📚 拓展学习

  • 学习双向链表和循环链表的实现
  • 探索线性表在实际项目中的应用
  • 研究基于线性表实现的其他数据结构（如栈、队列）
  • 练习线性表相关的算法题（如反转链表、合并有序链表等）

记住，编程的进步源于不断的实践和思考。继续加油，你一定能成为编程高手！ 🚀

1 条评论

  • @ 2025-5-22 22:57:02

    🧠 C++ 线性表（Linear List）通俗易懂教程 🚀

    📌 使用结构体实现顺序表与单链表，不使用类和函数模板！适合初学者理解！

    🎯 一、什么是线性表？

    线性表 是一种最基础的数据结构，表示 一组数据元素的有限序列。

    你可以把它想象成：

    🧩 一条队伍：每个人站在一个位置上，有前一个人和后一个人。
    🔢 每个数据之间有“顺序”关系。

    ✅ 线性表的特点：

    • 数据元素是同一类型
    • 元素之间是一对一的关系（前驱 & 后继）
    • 存储方式可以是连续的（顺序表）或不连续的（链表）

    🧱 二、线性表的分类 🔍

    类型 描述
    顺序表（Array-based List） 使用数组存储，物理地址连续
    链表（Linked List） 使用指针连接节点，物理地址不连续

    📈 三、线性表的基本操作 🛠️

    操作 功能说明
    Insert(i, x) 在第 i 个位置插入元素 x
    Delete(i) 删除第 i 个位置的元素
    Get(i) 获取第 i 个位置的元素
    Locate(x) 查找值为 x 的元素的位置
    Length() 返回线性表当前长度
    Empty() 判断是否为空表

    🧪 四、顺序表实现（使用结构体）📦

    我们使用结构体来封装顺序表的信息，并通过函数对其进行操作。

    ✅ 示例代码：

    #include <iostream>
using namespace std;

#define MAX_SIZE 100

// 定义顺序表结构体
typedef struct {
    int data[MAX_SIZE]; // 数据域
    int length;         // 当前长度
} SeqList;

// 初始化顺序表
void initList(SeqList* list) {
    list->length = 0;
}

// 插入元素
bool insert(SeqList* list, int index, int value) {
    if (index < 0 || index > list->length || list->length >= MAX_SIZE)
        return false;
    
    for (int i = list->length; i > index; --i)
        list->data[i] = list->data[i - 1];
    
    list->data[index] = value;
    list->length++;
    return true;
}

// 删除元素
bool remove(SeqList* list, int index) {
    if (index < 0 || index >= list->length)
        return false;
    
    for (int i = index; i < list->length - 1; ++i)
        list->data[i] = list->data[i + 1];
    
    list->length--;
    return true;
}

// 获取元素
int get(SeqList* list, int index) {
    if (index < 0 || index >= list->length)
        return -1;
    return list->data[index];
}

// 查找元素位置
int locate(SeqList* list, int value) {
    for (int i = 0; i < list->length; ++i)
        if (list->data[i] == value)
            return i;
    return -1;
}

// 获取长度
int length(SeqList* list) {
    return list->length;
}

// 是否为空
bool empty(SeqList* list) {
    return list->length == 0;
}

// 打印线性表
void printList(SeqList* list) {
    for (int i = 0; i < list->length; ++i)
        cout << list->data[i] << " ";
    cout << endl;
}

    🧪 主函数测试：

    int main() {
    SeqList list;
    initList(&list);

    insert(&list, 0, 10);
    insert(&list, 1, 20);
    insert(&list, 2, 30);

    cout << "当前线性表：" << endl;
    printList(&list);

    cout << "查找 20 的位置：" << locate(&list, 20) << endl;

    remove(&list, 1);
    cout << "删除第1个元素后的线性表：" << endl;
    printList(&list);

    return 0;
}

    📌 输出：

    当前线性表：
10 20 30 
查找 20 的位置：1
删除第1个元素后的线性表：
10 30

    🔗 五、单链表实现（使用结构体）🔗

    我们使用结构体来定义节点，并用指针连接起来。

    ✅ 示例代码：

    #include <iostream>
using namespace std;

// 定义链表节点结构体
typedef struct Node {
    int data;
    struct Node* next;
} Node;

// 初始化带头结点的链表
Node* initList() {
    Node* head = (Node*)malloc(sizeof(Node));
    head->next = nullptr;
    return head;
}

// 插入元素（在第 index 个位置插入）
bool insert(Node* head, int index, int value) {
    Node* p = head;
    for (int i = 0; i < index && p != nullptr; ++i)
        p = p->next;
    
    if (p == nullptr)
        return false;

    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->data = value;
    newNode->next = p->next;
    p->next = newNode;

    return true;
}

// 删除元素（删除第 index 个位置的元素）
bool remove(Node* head, int index) {
    Node* p = head;
    for (int i = 0; i < index && p != nullptr; ++i)
        p = p->next;
    
    if (p == nullptr || p->next == nullptr)
        return false;

    Node* del = p->next;
    p->next = del->next;
    free(del);
    return true;
}

// 获取元素
int get(Node* head, int index) {
    Node* p = head->next;
    for (int i = 0; i < index && p != nullptr; ++i)
        p = p->next;
    if (p == nullptr)
        return -1;
    return p->data;
}

// 查找元素位置
int locate(Node* head, int value) {
    Node* p = head->next;
    int index = 0;
    while (p != nullptr) {
        if (p->data == value)
            return index;
        p = p->next;
        index++;
    }
    return -1;
}

// 获取长度
int length(Node* head) {
    int count = 0;
    Node* p = head->next;
    while (p != nullptr) {
        count++;
        p = p->next;
    }
    return count;
}

// 是否为空
bool empty(Node* head) {
    return head->next == nullptr;
}

// 打印链表
void printList(Node* head) {
    Node* p = head->next;
    while (p != nullptr) {
        cout << p->data << " ";
        p = p->next;
    }
    cout << endl;
}

    🧪 主函数测试：

    int main() {
    Node* head = initList();

    insert(head, 0, 10);
    insert(head, 1, 20);
    insert(head, 2, 30);

    cout << "当前链表：" << endl;
    printList(head);

    cout << "查找 20 的位置：" << locate(head, 20) << endl;

    remove(head, 1);
    cout << "删除第1个元素后的链表：" << endl;
    printList(head);

    return 0;
}

    📌 输出：

    当前链表：
10 20 30 
查找 20 的位置：1
删除第1个元素后的链表：
10 30

    📌 六、注意事项 ❗

    注意项 说明
    下标从 0 开始 和数组一致，注意边界检查
    插入删除效率 顺序表在中间插入/删除慢；链表快
    内存分配 静态数组大小固定；链表动态增长
    头结点设计 单链表中加入头结点能简化操作逻辑

    🧠 七、应用场景举例 💡

    场景 示例
    学生成绩管理 存储学生成绩并进行增删改查
    编辑器文本行 文本编辑器中的每一行内容
    浏览器历史记录 前进/后退功能实现
    播放列表 音乐播放器的歌曲队列管理

    🎁 八、加油鼓励语 💪

    👋 亲爱的同学，你已经掌握了 C++ 中非常实用的线性表知识！这是你通往算法高手之路的重要一步！

    🎯 线性表是所有复杂数据结构的基础，无论是栈、队列、树还是图，都离不开它。
    🧠 掌握它，你会发现自己能轻松应对很多看似复杂的编程挑战！

    🚀 继续努力，坚持练习，你一定能在编程世界中大放异彩！我们在这里为你打call！👏👏👏

    📅 最后更新时间：2025年5月22日 22:52

    🎉 祝你学习愉快，早日成为编程高手！🌟

    • 1
    428
    已通过
    0
    题解被赞
    1. 关于
    2. 联系我们
    3. 隐私
    4. 服务条款
    5. 版权申诉
    6. Language
    7. 兼容模式
    8. 主题
    4. 在线咨询
    5. Worker 0, 35ms
    6. Powered by Hydro v4.13.3 Community