【数据结构之线性表】

一、线性表的基本概念

1. 定义

线性表是一种最基本的数据结构，它由相同类型的元素按顺序排列而成。在计算机内存中，这些元素被依次存放，形成一个线性序列。线性表可以用来表示一系列有序的数据，如整数、字符、对象等。

2. 特点

2.1 元素有序排列

线性表中的元素按照某种顺序依次排列。每个元素都有一个唯一的位置，通常从第一个元素到最后一个元素的顺序排列，这些位置用索引标识。在数组中，这种索引从0开始，而在链表中，则由节点指针来确定顺序。

2.2 元素类型相同

线性表中的所有元素必须是相同类型的。这种同质性保证了数据的一致性和操作的统一性。例如，一个整数型线性表只能存储整数，不能混合存储其他类型的数据。这个特点使得线性表在处理一类数据时具有很高的效率和简洁性。

2.3 元素之间存在一对一的关系

在线性表中，每个元素都有一个前驱（除了第一个元素）和一个后继（除了最后一个元素）。这种一对一的关系确保了线性表的结构简单明了。在内存中，这种关系可以通过数组的索引或者链表的节点指针来体现。这种特性使得线性表在执行插入、删除等操作时非常直观，但也使得某些操作（如中间插入和删除）可能比较耗时，特别是在顺序存储结构中。

二、线性表的实现方式（C++）

在C++中，线性表可以通过两种主要方式来实现：顺序表（数组）和链表。每种方式都有其独特的优点和缺点，根据不同的应用场景，选择合适的实现方式能够显著提高程序的效率和灵活性。

1. 顺序表（数组）

顺序表是一种使用连续的内存空间来存储数据的线性表。在C++中，顺序表通常通过数组来实现。

1.1 定义

顺序表通过一个数组来存储所有元素。每个元素都占据数组的一个位置，这些位置由连续的内存地址表示。顺序表的大小在初始化时确定，因此它的容量是固定的。

1.2 实现示例

#include <iostream>
using namespace std;

class SequenceList {
private:
    int *array;
    int capacity;
    int size;

public:
    SequenceList(int capacity) {
        this->capacity = capacity;
        size = 0;
        array = new int[capacity];
    }

    ~SequenceList() {
        delete[] array;
    }

    void insert(int value) {
        if (size < capacity) {
            array[size++] = value;
        } else {
            cout << "List is full" << endl;
        }
    }

    int get(int index) {
        if (index >= 0 && index < size) {
            return array[index];
        } else {
            throw out_of_range("Index out of range");
        }
    }

    void display() {
        for (int i = 0; i < size; ++i) {
            cout << array[i] << " ";
        }
        cout << endl;
    }
};

int main() {
    SequenceList list(10);
    list.insert(1);
    list.insert(2);
    list.insert(3);
    list.display();
    cout << "Element at index 1: " << list.get(1) << endl;

    return 0;
}

1.3 优点

• 随机访问速度快: 由于数组中的元素具有连续的内存地址，可以通过元素的索引直接访问，这使得随机访问非常高效，时间复杂度为O(1)。

1.4 缺点

• 插入和删除操作较慢: 由于数组大小固定，在进行插入或删除操作时，可能需要移动大量元素来腾出空间或填补空缺，这使得这些操作的时间复杂度为O(n)。
• 固定大小: 数组的大小在创建时确定，如果需要存储的元素超过了数组的容量，就需要重新分配内存，这可能导致性能开销。

2. 链表

链表是一种使用节点存储数据的线性表，每个节点包含数据和指向下一个节点的指针。在C++中，链表通常通过类或结构体来实现。

2.1 定义

链表由一系列节点组成，每个节点包含一个数据元素和一个指向下一个节点的指针。链表的第一个节点称为头节点，最后一个节点的指针为NULL，表示链表的结束。

2.2 实现示例

#include <iostream>
using namespace std;

class Node {
public:
    int data;
    Node* next;

    Node(int value) : data(value), next(nullptr) {}
};

class LinkedList {
private:
    Node* head;

public:
    LinkedList() : head(nullptr) {}

    ~LinkedList() {
        Node* current = head;
        Node* next;
        while (current != nullptr) {
            next = current->next;
            delete current;
            current = next;
        }
    }

    void insert(int value) {
        Node* newNode = new Node(value);
        newNode->next = head;
        head = newNode;
    }

    void display() {
        Node* current = head;
        while (current != nullptr) {
            cout << current->data << " ";
            current = current->next;
        }
        cout << endl;
    }
};

int main() {
    LinkedList list;
    list.insert(1);
    list.insert(2);
    list.insert(3);
    list.display();

    return 0;
}

2.3 优点

• 插入和删除操作快: 链表中的插入和删除操作只涉及节点指针的修改，不需要移动其他元素，因此这些操作的时间复杂度为O(1)（假设已找到插入或删除位置）。

2.4 缺点

• 随机访问速度慢: 链表不支持随机访问，要访问特定位置的元素，必须从头节点开始逐个遍历，时间复杂度为O(n)。
• 内存占用多: 每个节点除了存储数据外，还需要存储一个指针，这会增加额外的内存开销。

三、线性表的操作

1. 增加操作

1.1 在顺序表中增加元素

在顺序表（数组）中增加元素通常涉及将新元素插入到现有数据的指定位置，并调整数组中的元素。

实现示例

#include <iostream>
using namespace std;

class SequenceList {
private:
    int *array;
    int capacity;
    int size;

public:
    SequenceList(int capacity) {
        this->capacity = capacity;
        size = 0;
        array = new int[capacity];
    }

    ~SequenceList() {
        delete[] array;
    }

    void insert(int value, int index) {
        if (index < 0 || index > size || size >= capacity) {
            cout << "Invalid index or list is full" << endl;
            return;
        }
        for (int i = size; i > index; --i) {
            array[i] = array[i - 1];
        }
        array[index] = value;
        ++size;
    }

    void display() {
        for (int i = 0; i < size; ++i) {
            cout << array[i] << " ";
        }
        cout << endl;
    }
};

int main() {
    SequenceList list(10);
    list.insert(1, 0);
    list.insert(2, 1);
    list.insert(3, 1);  // Insert 3 at index 1
    list.display();

    return 0;
}

1.2 在链表中增加节点

在链表中增加节点通常涉及创建一个新节点，并将其插入到链表的指定位置。

实现示例

#include <iostream>
using namespace std;

class Node {
public:
    int data;
    Node* next;

    Node(int value) : data(value), next(nullptr) {}
};

class LinkedList {
private:
    Node* head;

public:
    LinkedList() : head(nullptr) {}

    ~LinkedList() {
        Node* current = head;
        Node* next;
        while (current != nullptr) {
            next = current->next;
            delete current;
            current = next;
        }
    }

    void insert(int value, int index) {
        Node* newNode = new Node(value);
        if (index == 0) {
            newNode->next = head;
            head = newNode;
            return;
        }
        Node* current = head;
        for (int i = 0; i < index - 1 && current != nullptr; ++i) {
            current = current->next;
        }
        if (current == nullptr) {
            cout << "Index out of bounds" << endl;
            delete newNode;
            return;
        }
        newNode->next = current->next;
        current->next = newNode;
    }

    void display() {
        Node* current = head;
        while (current != nullptr) {
            cout << current->data << " ";
            current = current->next;
        }
        cout << endl;
    }
};

int main() {
    LinkedList list;
    list.insert(1, 0);
    list.insert(2, 1);
    list.insert(3, 1);  // Insert 3 at index 1
    list.display();

    return 0;
}

2. 删除操作

2.1 删除顺序表中的元素

删除顺序表中的元素涉及将指定位置的元素移除，并调整其后的所有元素。

实现示例

#include <iostream>
using namespace std;

class SequenceList {
private:
    int *array;
    int capacity;
    int size;

public:
    SequenceList(int capacity) {
        this->capacity = capacity;
        size = 0;
        array = new int[capacity];
    }

    ~SequenceList() {
        delete[] array;
    }

    void remove(int index) {
        if (index < 0 || index >= size) {
            cout << "Invalid index" << endl;
            return;
        }
        for (int i = index; i < size - 1; ++i) {
            array[i] = array[i + 1];
        }
        --size;
    }

    void display() {
        for (int i = 0; i < size; ++i) {
            cout << array[i] << " ";
        }
        cout << endl;
    }
};

int main() {
    SequenceList list(10);
    list.insert(1, 0);
    list.insert(2, 1);
    list.insert(3, 2);
    list.remove(1);  // Remove element at index 1
    list.display();

    return 0;
}

2.2 删除链表中的节点

在链表中删除节点通常涉及调整指针以绕过被删除的节点。

实现示例

#include <iostream>
using namespace std;

class Node {
public:
    int data;
    Node* next;

    Node(int value) : data(value), next(nullptr) {}
};

class LinkedList {
private:
    Node* head;

public:
    LinkedList() : head(nullptr) {}

    ~LinkedList() {
        Node* current = head;
        Node* next;
        while (current != nullptr) {
            next = current->next;
            delete current;
            current = next;
        }
    }

    void remove(int index) {
        if (index < 0 || head == nullptr) {
            cout << "Invalid index or list is empty" << endl;
            return;
        }
        Node* temp;
        if (index == 0) {
            temp = head;
            head = head->next;
            delete temp;
            return;
        }
        Node* current = head;
        for (int i = 0; i < index - 1 && current != nullptr; ++i) {
            current = current->next;
        }
        if (current == nullptr || current->next == nullptr) {
            cout << "Index out of bounds" << endl;
            return;
        }
        temp = current->next;
        current->next = temp->next;
        delete temp;
    }

    void display() {
        Node* current = head;
        while (current != nullptr) {
            cout << current->data << " ";
            current = current->next;
        }
        cout << endl;
    }
};

int main() {
    LinkedList list;
    list.insert(1, 0);
    list.insert(2, 1);
    list.insert(3, 2);
    list.remove(1);  // Remove element at index 1
    list.display();

    return 0;
}

3. 查询操作

3.1 顺序访问和随机访问

在顺序表中，可以通过索引进行随机访问，而在链表中只能顺序访问。

顺序访问示例（链表）

#include <iostream>
using namespace std;

// 链表节点类
class Node {
public:
    int data;
    Node* next;
    Node(int value) : data(value), next(nullptr) {}
};

// 链表类
class LinkedList {
private:
    Node* head;
public:
    LinkedList() : head(nullptr) {}

    // 添加节点到链表末尾
    void append(int value) {
        Node* newNode = new Node(value);
        if (head == nullptr) {
            head = newNode;
        } else {
            Node* current = head;
            while (current->next != nullptr) {
                current = current->next;
            }
            current->next = newNode;
        }
    }

    // 顺序访问链表中的元素
    void sequentialAccess(int position) {
        if (position < 0) {
            cout << "Invalid position." << endl;
            return;
        }
        Node* current = head;
        int index = 0;
        while (current != nullptr) {
            if (index == position) {
                cout << "Element at position " << position << ": " << current->data << endl;
                return;
            }
            current = current->next;
            index++;
        }
        cout << "Position out of range." << endl;
    }

    // 打印链表中的所有元素
    void printList() {
        Node* current = head;
        while (current != nullptr) {
            cout << current->data << " -> ";
            current = current->next;
        }
        cout << "null" << endl;
    }
};

int main() {
    LinkedList list;
    list.append(10);
    list.append(20);
    list.append(30);
    list.append(40);

    list.printList();  // 输出链表中的所有元素

    list.sequentialAccess(2);  // 顺序访问链表中的第2个元素
    list.sequentialAccess(5);  // 尝试访问链表中超出范围的元素

    return 0;
}

随机访问示例（顺序表）

#include <iostream>
using namespace std;

class SequenceList {
private:
    int *array;
    int capacity;
    int size;

public:
    SequenceList(int capacity) {
        this->capacity = capacity;
        size = 0;
        array = new int[capacity];
    }

    ~SequenceList() {
        delete[] array;
    }

    int get(int index) {
        if (index < 0 || index >= size) {
            throw out_of_range("Index out of range");
        }
        return array[index];
    }

    void display() {
        for (int i = 0; i < size; ++i) {
            cout << array[i] << " ";
        }
        cout << endl;
    }
};

int main() {
    SequenceList list(10);
    list.insert(1, 0);
    list.insert(2, 1);
    list.insert(3, 2);
    cout << "Element at index 1: " << list.get(1) << endl;

    return 0;
}

3.2 查找特定元素的位置

在顺序表中可以直接使用索引获取元素，而在链表中则需要遍历链表。

查找特定元素位置示例（链表）

#include <iostream>
using namespace std;

class Node {
public:
    int data;
    Node* next;

    Node(int value) : data(value), next(nullptr) {}
};

class LinkedList {
private:
    Node* head;

public:
    LinkedList() : head(nullptr) {}

    ~LinkedList() {
        Node* current = head;
        Node* next;
        while (current != nullptr) {
            next = current->next;
            delete current;
            current = next;
        }
    }

    int find(int value) {
        Node* current = head;
        int index = 0;
        while (current != nullptr) {
            if (current->data == value) {
                return index;
            }
            current = current->next;
            ++index;
        }
        return -1;  // Element not found
    }

    void display() {
        Node* current = head;
        while (current != nullptr) {
            cout << current->data << " ";
            current =

 current->next;
        }
        cout << endl;
    }
};

int main() {
    LinkedList list;
    list.insert(1, 0);
    list.insert(2, 1);
    list.insert(3, 2);
    cout << "Index of element 2: " << list.find(2) << endl;

    return 0;
}

4. 修改操作

4.1 修改顺序表中某个位置的元素

在顺序表中，修改某个位置的元素非常简单，只需通过索引直接访问并赋值。

实现示例

#include <iostream>
using namespace std;

class SequenceList {
private:
    int *array;
    int capacity;
    int size;

public:
    SequenceList(int capacity) {
        this->capacity = capacity;
        size = 0;
        array = new int[capacity];
    }

    ~SequenceList() {
        delete[] array;
    }

    void set(int index, int value) {
        if (index < 0 || index >= size) {
            cout << "Index out of range" << endl;
            return;
        }
        array[index] = value;
    }

    void display() {
        for (int i = 0; i < size; ++i) {
            cout << array[i] << " ";
        }
        cout << endl;
    }
};

int main() {
    SequenceList list(10);
    list.insert(1, 0);
    list.insert(2, 1);
    list.set(1, 5);  // Change element at index 1 to 5
    list.display();

    return 0;
}

4.2 修改链表中某个位置的元素

在链表中，修改某个位置的元素需要遍历链表到达该位置，然后进行修改。

实现示例

#include <iostream>
using namespace std;

class Node {
public:
    int data;
    Node* next;

    Node(int value) : data(value), next(nullptr) {}
};

class LinkedList {
private:
    Node* head;

public:
    LinkedList() : head(nullptr) {}

    ~LinkedList() {
        Node* current = head;
        Node* next;
        while (current != nullptr) {
            next = current->next;
            delete current;
            current = next;
        }
    }

    void set(int index, int value) {
        Node* current = head;
        for (int i = 0; i < index && current != nullptr; ++i) {
            current = current->next;
        }
        if (current != nullptr) {
            current->data = value;
        } else {
            cout << "Index out of range" << endl;
        }
    }

    void display() {
        Node* current = head;
        while (current != nullptr) {
            cout << current->data << " ";
            current = current->next;
        }
        cout << endl;
    }
};

int main() {
    LinkedList list;
    list.insert(1, 0);
    list.insert(2, 1);
    list.set(1, 5);  // Change element at index 1 to 5
    list.display();

    return 0;
}

四、线性表的优势与局限

1. 优势

1.1 简单易用

线性表的结构非常直观，尤其是顺序表（如数组）和链表，其概念易于理解和实现。

• 顺序表: 使用连续的内存空间存储数据，数据存取简单，代码实现易于理解。
• 链表: 使用节点链式连接，可以灵活管理内存，无需考虑数组的容量限制。

示例:

• 顺序表：适用于对固定数量数据进行快速访问和操作的场景，如静态配置数据、日历数据等。
• 链表：适用于动态数据管理，如动态队列、链式栈等。

1.2 适合存储和管理有序数据

线性表中的元素具有明确的顺序，适合用于存储和管理有序数据集。

• 顺序性: 数据按照插入顺序存储，方便进行顺序遍历和操作。
• 一致性: 数据类型一致，便于进行批量操作和处理。

应用场景:

• 排序算法中的数据存储
• 图形绘制中的点阵数据
• 数据记录和日志管理

2. 局限

2.1 顺序表扩展性差

顺序表（数组）的大小通常是固定的，在插入新元素时可能需要重新分配内存空间，这会导致性能下降。

• 内存管理: 扩展顺序表的容量时，需要重新分配更大的数组，并将原数据复制到新数组中。
• 时间复杂度: 插入和删除操作可能导致大量数据移动，时间复杂度为 O(n)。

示例:

#include <iostream>
#include <vector>
using namespace std;

int main() {
    vector<int> vec;
    for (int i = 0; i < 100; ++i) {
        vec.push_back(i);  // 当容量不足时，vector 会自动扩展容量
    }
    cout << "Vector size: " << vec.size() << endl;
    return 0;
}

2.2 链表的随机访问效率低

链表不支持快速随机访问，需要从头节点开始顺序遍历到目标位置，访问效率较低。

• 遍历性能: 由于链表的节点是链式存储，无法直接访问任意位置的节点，只能逐一遍历，时间复杂度为 O(n)。
• 内存消耗: 链表的每个节点除了存储数据外，还需要存储指针信息，导致内存开销较大。

示例:

#include <iostream>
using namespace std;

class Node {
public:
    int data;
    Node* next;
    Node(int value) : data(value), next(nullptr) {}
};

int main() {
    Node* head = new Node(1);
    head->next = new Node(2);
    head->next->next = new Node(3);
    
    Node* current = head;
    int index = 0;
    int targetIndex = 2;
    while (current != nullptr && index < targetIndex) {
        current = current->next;
        index++;
    }
    if (current != nullptr) {
        cout << "Element at index " << targetIndex << ": " << current->data << endl;
    } else {
        cout << "Index out of range" << endl;
    }
    return 0;
}

五、线性表与其他数据结构的比较

线性表是基本的数据结构之一，在计算机科学中还有许多其他常用的数据结构，如栈、队列、树等。了解这些数据结构之间的差异和优缺点，可以帮助开发者在实际应用中选择最合适的结构。

1. 线性表 vs. 栈

线性表

• 操作: 支持在任意位置进行插入、删除、查询和修改操作。
• 访问: 可以随机访问任意位置的元素。
• 实现: 顺序表（数组）和链表是线性表的常见实现。

栈

• 操作: 仅支持在栈顶进行插入和删除操作，遵循后进先出（LIFO）的原则。
• 访问: 只能访问栈顶的元素，不支持随机访问。
• 实现: 通常使用数组或链表实现。

示例比较:

• 线性表: 可以访问和操作任意位置的元素，如array[3] = 10。
• 栈: 只能操作栈顶的元素，如stack.push(10)、stack.pop()。

// 栈的基本实现
#include <iostream>
#include <stack>
using namespace std;

int main() {
    stack<int> s;
    s.push(1);  // 压入栈顶
    s.push(2);
    cout << "Top element: " << s.top() << endl;  // 访问栈顶元素
    s.pop();  // 弹出栈顶元素
    cout << "Top element after pop: " << s.top() << endl;
    return 0;
}

2. 线性表 vs. 队列

线性表

• 操作: 支持任意位置的插入、删除、查询和修改操作。
• 访问: 可以随机访问任意位置的元素。

队列

• 操作: 仅支持在队列两端进行操作：一端入队（enqueue），另一端出队（dequeue），遵循先进先出（FIFO）的原则。
• 访问: 只能访问队头和队尾的元素，不支持随机访问。
• 实现: 通常使用数组或链表实现。

示例比较:

• 线性表: 可以对任意位置进行插入和删除，如list.insert(3, value)。
• 队列: 只能进行队列头尾的操作，如queue.push(value)、queue.pop()。

// 队列的基本实现
#include <iostream>
#include <queue>
using namespace std;

int main() {
    queue<int> q;
    q.push(1);  // 入队
    q.push(2);
    cout << "Front element: " << q.front() << endl;  // 访问队头元素
    q.pop();  // 出队
    cout << "Front element after pop: " << q.front() << endl;
    return 0;
}

3. 线性表 vs. 树

线性表

• 关系: 元素之间存在线性关系，只有前驱和后继元素。
• 结构: 简单的线性结构，不支持分支或层次结构。

树

• 关系: 支持层次和分支结构，节点之间有父子关系，可以有多个子节点。
• 结构: 复杂的数据结构，常见的有二叉树、B树等，支持更复杂的数据关系。

示例比较:

• 线性表: 用于存储简单的线性数据，如列表、队列。
• 树: 用于表示层次化的数据，如组织结构、文件系统目录。

// 二叉树的基本节点定义
#include <iostream>
using namespace std;

struct TreeNode {
    int data;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int value) : data(value), left(nullptr), right(nullptr) {}
};

int main() {
    TreeNode* root = new TreeNode(1);
    root->left = new TreeNode(2);
    root->right = new TreeNode(3);
    cout << "Root node data: " << root->data << endl;
    cout << "Left child data: " << root->left->data << endl;
    cout << "Right child data: " << root->right->data << endl;
    return 0;
}