C++实现数据结构——线性表

buyue__

302人浏览 · 2025-11-25 15:14:46

buyue__ · 2025-11-25 15:14:46 发布

线性表的顺序存储表示
线性表的顺序存储结构指的是把线性表的数据元素按逻辑顺序依次存放在一组地址连续的存储单元里，用这种方法存储的线性表简称为顺序表(Sequential List)。
顺序表的特点是，表中逻辑上相邻的数据元素，存储时在物理位置上也一定相邻。
换句话说，顺序表以数据元素在计算机内“物理位置相邻”来表示线性表中数据元素之间在“逻辑关系上相邻”。

顺序表的类定义和基本操作

顺序表的类定义
在高级语言中，一维数组也具有和顺序表相同的以下3个特性，

一维数组的存储对象也是一组相同类型的数据。
一维数组也是用一组地址连续的存储单元存放数据。
一维数组中的数据元素也可以通过数组下标随机存取。
因此，可以用数组类型来描述顺序表。

因此，可以用数组类型来描述顺序表。
此外，C++语言中，一维数组的定义有以下两种方式。
方式一：<数据类型><数组名> [<常量表达式>]
例如:

int a[5];
float x[100];

采用方式一定义的数组，数组的容量是确定的(不能扩充)，如上述示例中，数组a最多可存放5个数据元素，其数据元素的下标从0开始，数据元素分别为 a[0]，a[1]，a[2]，a[3]，a[4]。

方式二：<数据类型> * <指针变量> = new <数据类型>[<常量表达式>]
例如:

int* p = new int[5];
//等价于
int* p;p = new int[5];

由于采用指针来指向数组，因此存储空间可以动态分配，即指针所表示的数组空间容量可以变化，这样更符合线性表长度可变的情况。

顺序表的基本操作

创建顺序表
销毁顺序表
插入数据元素
删除数据元素
返回数据元素的位置i（按值查找）
返回第i位数据元素的值（按位查找）

由于方式二的顺序表比较实用和常见，所以这里只实现方式二的顺序表
SequentialList.h

//
// 顺序表【方式二】
//

#ifndef DS_SEQUENTIALLIST_H
#define DS_SEQUENTIALLIST_H

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

template <class T>
class SequentialList {
    private:
        //指向一维数组的指针
        //通过指针可以访问数组的元素
        //例如，pointer[0]和elements[0]是等价的，都表示数组的第一个元素。
        T* pointer;
        size_t capacity = 0;//容量（一维数组的实际大小）
        size_t currentSize = 0;//当前的元素数量

        //扩容
        void expand() {
            capacity += INCREMENT;
            auto tmp = new T[capacity];  //申请增量的新数组
            for (int i = 0; i < currentSize; ++i)
                tmp[i] = pointer[i];  //将数据从旧数组复制到新数组
            delete[] pointer;//回收旧数组
            pointer = tmp;
        }
    public:
        static constexpr size_t INCREMENT = 10;//增量

        SequentialList(size_t initialCapacity = INCREMENT) {
            capacity = initialCapacity;
            auto elements = new T[initialCapacity];
            pointer = elements;
        }
        ~SequentialList() {
            delete[] pointer;
            capacity = 0;
            currentSize = 0;
        }
        //在i位插入元素
        void insert(size_t i,const T& value) {
            if (i > capacity) {
                cout << "Out of range(insert\n";
                return;
            }
            if (currentSize == capacity) { //如果当前大小等于容量，则扩容
                expand();
            }
            //将第i个元素到最后一个元素全部后移一个位置
            for (auto j = currentSize; j > i; j--){
                pointer[j] = pointer[j - 1];
            }
            pointer[i] = value;
            ++currentSize;
        }
        //删除第i位的元素
        void remove(size_t i) {
            if (i >= currentSize) {
                cout << "Out of range(remove\n";
                return;
            }
            //将第i+1个元素到最后一个元素全部前移一个位置
            for (auto j = i;j<currentSize - 1;++j) {
                pointer[j] = pointer[j + 1];
            }
        }

        T getElement(size_t i) const{
            return pointer[i];
        }
        //得到元素数量
        size_t getSize() const {
            return currentSize;
        }
};
#endif //DS_SEQUENTIALLIST_H

main.cpp测试

//
// SequentialList的测试
//

#include <iostream>

using namespace std;
#include "SequentialList.h"

int main() {

    auto sl = new SequentialList<int>(10);

    sl->insert(0,1);
    sl->insert(1,2);
    sl->insert(1,3);
    sl->insert(1,4);

    sl->remove(0);

    cout << sl->getSize() << endl;
    cout << sl->getElement(1) << endl;
    return 0;
}

C++标准库中的顺序表
std::vector是C++标准库中的顺序表实现，是一种动态数组容器，可以根据需要动态调整大小。

//
// C++标准库中的顺序表std::vector
//

#include <iostream>

using namespace std;

int main() {

    std::vector<int> vec;
    for (int i = 0; i < 10; i++) {
        vec.push_back(i);
        std::cout << "Size: " << vec.size() << ", Capacity: " << vec.capacity() << std::endl;
    }
    return 0;

}

std::array是C++标准库中的顺序表的另一种实现，是一种固定大小的数组容器，不能动态调整大小。

//
// C++标准库中的顺序表std::array
//

#include <iostream>

using namespace std;

int main() {

    std::array<int, 5> intArray = {1, 2, 3, 4, 5};
    for(int num : intArray) {
        cout << num << endl;
    }
    return 0;

}

顺序表的优点

节省存储空间。由于结点之间的相邻逻辑关系可以用物理位置上的相邻关系表示，因此不需增加额外的存储空间来表示此关系(如链表则需利用指针来表示逻辑相邻关系)。
随机存取。由于表中任意数据元素的存储位置可通过公式计算得到，因此可直接访问表中任一位置的数据元素进行存取。

顺序表的缺点
3. 插入和删除数据时必须移动大量数据元素。
4. 必须预先为顺序表准备存储空间。当表长小于数组长度时，部分空间闲置浪费；当表长大于数组长度时，需要扩容。

链表（Linked List）：线性表的链式存储表示
线性表的链式存储结构是指用一组地址任意的存储单元来依次存放线性表中的数据元素，这组存储单元既可以是连续的，也可以是不连续的，甚至可以零散分布在内存中的任意位置上。因此链式存储结构中的数据元素的逻辑次序和物理次序不一定相同。
由于数据元素的逻辑次序和物理次序不一定相同，因此，在线性表的链式存储结构中，为了表示数据元素之间的逻辑关系，对于每个数据元素，除了存储其结点本身的信息外，还需存储指示其前驱或后继结点的信息。因此，链表中的每个数据结点都需要保存以下两部分信息。

存储数据元素自身信息的部分，称为数据域。
存储与前驱或后继结点的逻辑关系，称为指针域。

由于链表不要求逻辑上相邻的数据元素在物理位置上也相邻，因此它没有顺序存储结构所具有的缺点，但同时也失去了顺序表可随机存取的优点。

根据结点中指针域存储的指针个数和类型的不同，链表还可细分为单链表、双向链表、循环链表以及静态链表。

单向链表
如果结点只包含一个指针域，则称该链表为单向链表(Singly Linked List)。单向链表的结点结构如图所示。

在这里插入图片描述
其中，data为数据域，用来存储数据元素自身的信息;next为指针域(也称链域 )，用来存放结点的后继结点的地址。

单链表正是通过每个结点的链域next将线性表的n个结点按其逻辑次序链接在一起的。显然，单链表中每个结点的存储地址是存放在其前驱结点的next域中的，而表中的第一个结点a₁无前驱，故应设置一个头指针(Head Pointer)head指向a₁。此外，由于最后一个结点a_n无后继，故a_n的指针域为空，即 NULL(在图示中常用符号^表示 )。单链表的结构如图所示。
在这里插入图片描述

单链表的类定义和基本操作

单链表的结点通常采用结构体类型定义。

template <class T>
struct Node{
    T data;
    Node* next;
    Node(const T& value, Node* n = nullptr) {
        data = value;
        next = n;
    }
};

SinglyLinkedList.h完整代码

//
// 单链表
//

#ifndef DS_SINGLYLINKEDLIST_H
#define DS_SINGLYLINKEDLIST_H

#include <iostream>
using namespace std;

template <class T>
struct Node{
    T data;
    Node* next;
    Node(const T& value, Node* n = nullptr) {
        data = value;
        next = n;
    }
};

template <class T>
class SinglyLinkedList {
    private:
        Node<T>* head;
    public:
        SinglyLinkedList():head(nullptr){}
        ~SinglyLinkedList() {
            while (head != nullptr) { //遍历并删除每个节点，直到链表为空
                Node<T>* temp = head; //保存当前头节点指针
                head = head->next; //移动头节点到下一个节点
                delete temp; // 释放当前节点
            }
        }
        //在链表头部添加一个元素
        void prepend(const T &data) {
            Node<T>* newNode = new Node(data);
            newNode->next = head; //新节点指向原头节点
            head = newNode; //更新头节点为新节点
        }
        //向链表末尾添加一个元素
        void append(const T &data) {
            Node<T>* newNode = new Node(data);
            if (head == nullptr) {
                head = newNode;
            } else {
                Node<T>* temp = head;
                while (temp->next != nullptr) {
                    temp = temp->next;
                }
                temp->next = newNode;
            }
        }
        //按data查找节点，返回指针
        Node<T>* findNode(const T &data) {
            Node<T>* currentNode = head;//从头节点开始遍历
            while (currentNode != nullptr) {
                if (currentNode->data == data) {
                    return currentNode;
                }
                currentNode = currentNode->next;//继续遍历下一个节点
            }
            return nullptr;//如果未找到返回nullptr
        }
        //按data删除节点
        void remove(const T &data) {
            if (!head ) return;//链表为空直接返回
            Node<T>* temp = head; //用于遍历的临时节点指针
            Node<T>* prev = nullptr; //用于记录前一个节点，以便删除节点时修改其next指针
            if (temp != nullptr && temp->data == data) { //删除头节点的情况
                head = temp->next; //直接将头指针指向下一个节点
                delete temp; //释放原头节点
                return;
            }
            while (temp != nullptr && temp->data != data) { //查找值为data的节点
                prev = temp; //更新前一个节点指针
                temp = temp->next; //移动到下一个节点
            }
            if (temp == nullptr) return; //如果未找到值为data的节点，直接返回
            prev->next = temp->next; //将前一个节点的next指向要删除节点的下一个节点，实现删除操作
            delete temp; //释放要删除的节点
        }


        //显示链表中的所有元素
        void display() const {
            Node<T>* temp = head;
            while (temp != nullptr) {
                cout << temp->data << " -> ";
                temp = temp->next;
            }
            cout << "nullptr" << endl;
        }
};
#endif //DS_SINGLYLINKEDLIST_H

main.cpp测试

//
// SinglyLinkedList的测试
//

#include <iostream>

using namespace std;
#include "SinglyLinkedList.h"
int main() {

    SinglyLinkedList<string> sll;
    sll.append("b");
    sll.prepend("a");
    sll.append("c");
    sll.append("d");
    sll.append("e");
    sll.display();
    sll.remove("d");
    sll.display();
    sll.remove("a");
    sll.display();
    sll.remove("e");
    sll.display();
    cout << sll.findNode("c");
    return 0;
}

双向链表

如果希望快速确定表中任一结点的前驱结点，可以在单链表的每个结点中再设置一个指向其前驱结点的指针域，这样形成的链表中有两个方向不同的链，故称为双向链表(Double Linked List)，简称双链表，其结点结构如图所示。

在这里插入图片描述
其中
data：数据域，用来存储数据元素自身的信息;
prior：前驱指针域，存放该结点的前驱结点的地址;
next：后继指针域，存放该结点的后继结点的地址。

双向链表的类定义和基本操作
和单链表类似，双链表一般也是由头指针唯一确定，增加头结点也能使双链表的某些操作变得方便，将头结点和尾结点链接起来也能构成双循环链表，这样，无论是插入还是删除操作，对链表中的开始结点、尾结点和中间任意结点的操作过程都相同。
实际应用中常采用带头结点的双循环链表，如图所示。

在这里插入图片描述
DoubleLinkedList.h代码实现

//
// 双向链表
//

#ifndef DS_DOUBLELINKEDLIST_H
#define DS_DOUBLELINKEDLIST_H

#include <iostream>
using namespace std;

template <class T>
struct Node{
    T data;//数据域
    Node<T>* prev;//指向前一个节点的指针
    Node<T>* next;//指向后一个节点的指针

    Node<T>(const T &value, Node* p = nullptr, Node* n = nullptr) {
        data = value;
        prev = p;
        next = n;
    }

};

template <class T>
class DoubleLinkedList {
private:
    Node<T>* head; // 指向链表头部的指针
    Node<T>* tail; // 指向链表尾部的指针
public:
    //构造函数
    DoubleLinkedList() : head(nullptr), tail(nullptr) {}

    //析构函数，释放链表占用的内存
    ~DoubleLinkedList() {
        while (head != nullptr) {
            Node<T>* temp = head;
            head = head->next;
            delete temp;
        }
        tail = nullptr;
    }

    // 在链表末尾添加新节点
    void append(const T &data) {
        Node<T>* newNode = new Node(data);
        if (tail == nullptr) { // 如果链表为空，新节点同时是头节点和尾节点
            head = tail = newNode;
        } else { // 如果链表非空，新节点添加到尾部并更新尾部指针
            tail->next = newNode;
            newNode->prev = tail;
            tail = newNode;
        }
    }

    // 在链表头部添加新节点
    void prepend(const T &data) {
        Node<T>* newNode = new Node(data);
        if (head == nullptr) { // 如果链表为空，新节点同时是头节点和尾节点
            head = tail = newNode;
        } else { // 如果链表非空，新节点添加到头部并更新头部指针
            newNode->next = head;
            head->prev = newNode;
            head = newNode;
        }
    }

    // 删除指定值的节点（只删除第一个匹配的节点）
    void remove(const T &data) {
        Node<T>* current = head;
        while (current != nullptr) {
            if (current->data == data) { // 找到匹配的节点，进行删除操作
                if (current->prev != nullptr) { // 如果不是头节点，则重新链接前一个节点和后一个节点
                    current->prev->next = current->next;
                } else { // 是头节点的情况，更新头指针
                    head = current->next;
                }
                if (current->next != nullptr) { // 如果不是尾节点，则重新链接前一个节点和后一个节点
                    current->next->prev = current->prev;
                } else { // 是尾节点的情况，更新尾指针
                    tail = current->prev;
                }
                delete current; // 删除当前节点并退出循环（因为我们只删除第一个匹配的节点）
                return; // 删除操作完成，退出函数
            }
            current = current->next; // 继续搜索下一个节点
        }
    }
    //按data查找节点，返回指针
    Node<T>* findNode(const T &data) {
        Node<T>* currentNode = head;//从头节点开始遍历
        while (currentNode != nullptr) {
            if (currentNode->data == data) {
                return currentNode;
            }
            currentNode = currentNode->next;//继续遍历下一个节点
        }
        return nullptr;//如果未找到返回nullptr
    }
    //显示链表中的所有元素
    void display() const {
        Node<T>* current = head;
        while (current != nullptr) {
            cout << current->data << " -> ";
            current = current->next; //移动到下一个节点
        }
        cout << endl;
    }
};

#endif //DS_DOUBLELINKEDLIST_H

main.cpp测试

//
// DoubleLinkedList的测试
//

#include <iostream>

using namespace std;
#include "DoubleLinkedList.h"
int main() {

    DoubleLinkedList<string> dll;

    dll.append("b");
    dll.prepend("a");
    dll.append("c");
    dll.append("d");
    dll.append("e");
    dll.display();
    dll.remove("d");
    dll.display();
    dll.remove("a");
    dll.display();
    dll.remove("e");

    dll.display();
    cout << dll.findNode("c");
    return 0;
}