数据结构与算法

「 数据结构 」 一月 09, 2021

数据结构与算法

文章字数 21k 阅读约需 39 mins. 阅读次数 0

Program = Data Structure + Algorithm

引言

对实际问题进行缜密解析，并辅以优雅的代码进行编写。
本篇整理了我学习数据结构与算法时的一些笔记，相关源码已上传Github托管。

  • Program = Data Structure + Algorithm
    “程序 = 数据结构 + 算法”，这句出自Nicklaus Wirth教授的经典名言，使其一举夺得计算机的诺贝尔奖 - 图灵奖，该公式对于计算机科学的影响几乎等同于Albert Einstein最为著名的质能等价理论：”E = mc²”，通过这短短的一个公式，便展露出程序的本质。

  • Data Structure
    “数据结构(Data Structure)”是计算机程序设计的重要理论基础，是计算机专业最为核心的一门专业课程，同是也是一门考研课程。

基本概念

数据

数据是信息的载体，是描述客观事物的数字、字符，以及所有能输入计算机中的、被计算机程序识别和处理的符号的集合。包括数值型数据：整数、实数等，与非数值型数据
：文字、图像、图形、声音等。

数据元素

数据元素是数据中的一个"个体"，是数据的基本单位。在有些情况下，数据元素也被称为元素、结点、顶点、记录等。数据元素用于完整地描述一个对象。如：一个学生记录、一张图片、图的一个顶点等。

数据项

数据项是组成数据元素的有特定意义的不可分割的最小单位。如构成一个数据元素的字段、域、属性等都可称之为数据项。数据元素是数据项的集合。

简而言之，如上述举例中若要组成一个学生记录，那么一个学生可能包含有学号、姓名、性别、班级等属性，这些学号、姓名就是构成一个学生记录的数据项。

数据对象

数据对象是具有相同性质的数据元素的集合，是数据的一个子集。

如：计算机专业的全体学生(其中全体学生为一个集合，计算机专业为每个学生个体的相同性质)。

数据的逻辑结构

数据的逻辑结构讨论的是元素之间的逻辑关系，与存储结构无关，是独立于计算机的。常见的逻辑结构有：

  • 集合结构

  • 线性结构 – (1 : 1)

  • 树结构(层次结构) – (1 : n)

  • 图结构 – (n : m)

数据的存储结构(物理结构)

数据的存储结构(物理结构)研究的是数据及其逻辑关系如何在计算机中存储与实现。常见的存储结构有：

  • 顺序存储结构 (Sequential storage structure)

借助元素在存储器中的相对位置表示数据元素之间的关系，通常用数组来实现。

数组下标 0 1 2 3
数组元素 A B C D
  • 链式存储结构

借助表示数据元素存储地址的指针显式地指出数据元素之间的逻辑关系。

  • 散列(哈希)存储方式 (Hash (hash) storage method)

是专用于集合的数据存储方式。用一个哈希函数将数据元素按关键字和一个唯一的存储位置关联起来。

  • 索引存储方式

数据元素被排成一个序列：d1,d2,d3,…,dn，每个结点di在序列里都有相应的位序i(1 <= i <= n>)，位序可以作为结点的索引
存储在索引表中。检索时利用结点的顺序号i来确定结点的存储地址。(类似图书的目录。)

算法

算法是指令的有限序列，是对特定问题求解步骤的描述。算法具有下列五种特性：

  • (1) 有穷性

步骤有限，执行时间有限。

  • (2) 确定性

有确切的含义，无二义性，算法只有唯一的一条执行路径。

  • (3) 可行性

可以通过已经实现的基本运算执行有限次来实现。

  • (4) 输入

算法具有0个或多个输入。

  • (5) 输出

算法具有1个或多个输出。(一个算法不能没有输出。)

int sum(int num)
{
    int result = 0;
    for (int i = 1; i <= num; i++)
        result += i;

    return result;
}

算法与程序十分类似，但也有区别：

  • 在执行时间上：

算法所描述的步骤是一定有限的，但程序可以无限执行下去。如：一个操作系统是在一个无限循环中执行的，而不是一个算法。

  • 在语言描述上：

程序必须采用规定的程序设计语言来实现，而算法没有这种限制。

算法的设计要求

  • 正确性

算法应该能正确地实现预定功能；

  • 易读性

算法应易于阅读和理解，以便与调试、修改和扩充；

  • 健壮性

当环境发生变化(如非法输入)时，能正确作出反应或进行处理，不产生不正确的运算结果；

  • 高效性

算法应有效地使用存储空间并且有较高的时间效率。

算法效率的衡量方法

  • 事前分析法

在忽略计算机硬件、软件的因素后，一个特定算法”工作量”的大小，只依赖于问题的规模。

  • 事后统计法(后期估算)

通过编写实际操作代码，并将其在计算机上进行运行，通过计算机的时钟进行算法执行时间的统计。但由于时间统计依赖于硬件与软件环境，容易掩盖算法本身的优劣。

时间复杂度

O(N)是指该算法的时间耗费，是其所求解问题规模N的函数。当问题规模N趋于无穷大时，不考虑具体的运行时间函数，只考虑运行时间函数的数量级(阶)，这称为算法的渐进时间复杂度。

即：忽略低阶部分，只保留高阶部分，并忽略系数。

  • 常量阶
{
   ++x; s = 0; // 选取++x为基本操作，语句频度1，则时间复杂度O(n) = 1，即常量阶。
}

for (j = 1; j <= 10000; ++j)
    {
        ++x; // 选取++x为基本操作，语句频度为10000(即：1 * 10000)，但需要忽略系数，则时间复杂度为O(n) = 1，即常量阶。
        s += x;
    }
  • 对数阶
s = 0;
for (int j = 1; j <= n; j *= 2)
    ++x;// 选取++x为基本操作，语句频度为log2n(以2为底的对数阶)，则时间复杂度为O(log2n)，即对数阶。
  • 线性阶
for (int i = 1; i <= 2 * n; ++i)
    {
        ++x;// 选取++x为基本操作，则语句频度为2 * n，但需要忽略系数，则时间复杂度为O(n)，即线性阶。
        s += x;
    }
  • 平方阶
for (j = 1; j <= n; ++j)
    {// n + 1
        for (k = 1; k <= n / 4; ++k)
        {
            // n * (n/4 + 1)
            ++x;// 选取++x为基本操作，则语句频度为n * n/4，忽略系数1/4，则时间复杂度为O(n^2)，即平方阶。
            s += x;
        }
    }
  • 线性对数阶
for (int j = 1; j <= n; j *= 2)
    {// 执行log2n次
        for (int k = 1; k <= n; ++k)
        {
            ++x;// 选取++x为基本操作，则时间复杂度为O(nlog2n)，即线性对数阶。
            s += x;
        }
    }
  • 立方阶
for (int i = 1; i <= n; i++)
    {// 执行n次
        for (int j = 1; j <= n; j++)
        {// 执行n^2次
            c[i][j] = 0;
            for (int k = 1; k <= n; k++)
            {// 执行n^3次，语句频度为n * n^2 * n^ 3，但只取最高阶，即时间复杂度为O(n^3)，即立方阶。
                c[i][j] = c[i][j] + a[i][k] * b[k][j];
            }
        }
    }

空间复杂度

如果所需额外空间相对于输入数据量来说只是一个常数，则称此算法为"原地工作"，此时的空间复杂度为O(1)。

例：问题规模为n，

(1)若使用大小为n的辅助一唯数组，则空间复杂度为：O(n)

(2)若使用大小为n * n的辅助一唯数组，则空间复杂度为：O(n^2)

(3)若使用了100个辅助变量，则空间复杂度为：O(1),即”原地工作”

抽象数据类型

抽象数据类型和高级语言中的数据类型实质上是一个概念，抽象数据类型包含一般数据类型的概念，但含义比一般数据类型更广、更抽象。

抽象类型的伪代码定义格式如：

ADT 抽象数据类型名 {
    数据对象 D: <数据对象的定义>
    数据对象 R: <数据对象的定义>
    数据对象 P: <数据对象的定义>
} ADT 抽象数据类型名

线性表

基本定义

线性表(List)，作为最简单、最基本，也是最常用的一种线性结构。线性表是n个数据元素的有限序列。元素可以是各种各样的，但必须有相同性质，属于同一种数据对象。

例，XX学校设有n个学院，可用线性表表示如下：

{ “数学学院” , “外国语学院” , “声乐学院” , “计算机学院” , … }

表中的元素都是文本类型的字符型值，不允许出现非文本类型的数据。

当需要使用线性表存储较为复杂的数据时，一个元素也可有多个数据项构成，这种元素在线性表中通常被称为"记录 (record)"

例，XX学校计算机学院的学生成绩表可表示为：

ID Name Data Structure Software Engineering Discrete Mathematics Computer Network …
001 Mike 95 90 85 80 …
002 Jack 90 85 80 75 …
003 Alice 85 80 75 70 …
… … … … … … …

该线性表中的每一个元素都是一个学生的成绩，也可看成一个记录，由n个科目成绩的数据项构成。从表中可以看出，每个元素都有相同的数据项，而各个数据项都有自己的数据类型。

线性表的抽象数据类型

template <class T>
class List
{
public:
    virtual void clear() = 0;                          //* 清空顺序表
    virtual bool empty() const = 0;                    //* 判空，空为true，非空false
    virtual int size() const = 0;                      //* 表长
    virtual void insert(int position, const T &value); //* 在position位置插入值为value的元素
    virtual void remove(int position) = 0;             //* 删除第position的位置的元素
    virtual int search(const T &value);                //* 查找传入值value在顺序表中的位置
    virtual T visit(int position) const = 0;           //* 查找position位置的元素的值
    virtual void traverse() const = 0;                 //* 遍历当前顺序表
    virtual void inverse() = 0;                        //* 逆置当前顺序表
    virtual ~List(){};
};

自定义的异常处理类

class outOfRange : public exception
{
public:
    //* 检查范围有效性
    const char *checkRange() const throw()
    {
        return "OUT of RANGE";
    }
};

class errorSize : public exception
{
public:
    //* 检查长度有效性
    const char *checkSize() const throw()
    {
        return "ERROR size";
    }
};

线性表的【顺序】表示

线性表 (List) 在计算机内部有多种表示方法，最简单最常用的方法即用顺序表示。即在内存中用地址连续的一块有限的表空间，存储线性表的各种元素
，这种形式存储的线性表称为顺序表。

顺序表用物理上的相邻(即内存中的地址是连续的，如：同一批产品的生产序号)实现元素之间的逻辑相邻关系。

假定顺序表中的每个元素占k个存储单元(如：一个元素占8个存储单元)，若知道第一个元素的地址(如：1000，即基地址)为Loc(a0)，则位序为i的元素的地址为：

Loc(ai) = Loc(a0) + i * k (0 <= i <= n-1)

此时查找位序为i的元素的时间复杂度为O(1)，可得顺序表具有按元素位序，进行随机存取的特点。

template <class T>
class seqList : public List<T>
{
private:
    T *data;       //* 动态数组
    int length;    //* 当前顺序表表长
    int maxSize;   //* 顺序表最大长度
    void resize(); //* 表满时扩大表空间

public:
    seqList(int initSize = 10);   //* 构造函数
    seqList(seqList &list);       //* 拷贝构造
    ~seqList() { delete[] data; } //* 析构函数

    void clear() { length = 0; }               //* 置空
    bool empty() const { return length == 0; } //* 判空
    int size() const { return length; }        //* 返回表长
    void traverse() const;                     //* 遍历当前表
    void inverse();                            //* 逆置当前表

    void insert(int position, const T &value); //* 在position位置插入值为value的元素
    void remove(int position);                 //* 删除位于position的元素，length - 1
    int search(const T &value) const;          //* 查找值为value的元素在表中的值
    T visit(int position) const;               //* 访问position位置元素的值

    bool Union(seqList<T> &list);
};

顺序表的运算

  • 构造函数
template <class T>
seqList<T>::seqList(int initSize)
{
    if (initSize <= 0)
        throw errorSize();

    maxSize = initSize;
    data = new T[maxSize];
    length = 0;
}
  • 拷贝构造函数(动态分配存储空间)
template <class T>
seqList<T>::seqList(seqList &seqList)
{
    maxSize = seqList.maxSize;
    length = seqList.length;
    data = new T[maxSize];
    for (int i = 0; i < length; ++i)
        data[i] = seqList.data[i];
}
  • 遍历顺序表

依次输出顺序表的所有元素。

时间复杂度：O(n)

空间复杂度：O(1)

template <class T>
void seqList<T>::traverse() const
{
    if (empty())
    {
        cout << "Empty List" << endl;
    }
    else
    {
        cout << "current Element: " << endl;
        for (int i = 0; i < maxSize; i++)
            cout << data[i] << " ";

        cout << endl;
    }
}
  • 查找运算

在顺序表中查找值为value的元素的下标。

时间复杂度：O(n)

空间复杂度：O(1)

平均期望值：(n+1)/2，其中n为顺序表的元素个数。

template <class T>
int seqList<T>::search(const T &value) const
{
    for (int i = 0; i < length; i++)
        if (value == data[i])
            return i;

    return -1;
}
  • 插入运算

在顺序表下标为position的位置插入值为value的元素。

时间复杂度：O(n)

空间复杂度：O(1)

平均移动元素次数(期望值)：n/2，其中n为顺序表的元素个数。

template <class T>
void seqList<T>::insert(int position, const T &value)
{
    if (position < 0 || position > length)
        //* 判断是否越界
        throw outOfRange();

    if (length == maxSize)
        //* 当表满时，扩大表容量
        resize();

    for (int j = length; j > position; j--)
        //* 向后移动在插入位置position之后的所有元素
        //* 注意此处移动的第一个元素下标为表尾元素下标
        data[j] = data[j - 1];

    //* 在空出位置插入值为value的元素
    data[position] = value;

    //* 表长 +1
    ++length;
}
  • 删除运算

删除在顺序表下标为position的元素。

时间复杂度：O(n)

空间复杂度：O(1)

平均移动元素次数(期望值)：(n-1)/2，其中n为顺序表的元素个数。

template <class T>
void seqList<T>::remove(int position)
{
    if (position < 0 || position > length - 1)
        //* 判断是否越界
        throw outOfRange();

    for (int j = position; j < length - 1; j++)
        //* 前移在删除位置position之后的所有元素
        //* 注意此处移动的第一个元素下标为待删除元素的下标
        data[j] = data[j + 1];

    //* 表长 -1
    --length;
};
  • 逆置顺序表

调整线性表的顺序，可用于倒序输出顺序表元素。

如：原顺序表为5，4，3，2，1，逆置后顺序表为1，2，3，4，5

时间复杂度：O(n)

空间复杂度：O(1)

平均移动元素次数(期望值)：n/2，其中n为顺序表的元素个数。

template <class T>
void seqList<T>::inverse()
{
    T temp;
    for (int i = 0; i < length / 2; i++) //* 控制交换次数
    {
        temp = data[i];
        data[i] = data[length - i - 1];
        data[length - i - 1] = temp;
    }
}
  • 扩大表空间

算法思想：
由于数组空间在内存中必须是连续的，因此，扩大数组空间的操作需要：(1)重新申请一个更大规模的新数组，(2)将原有数组的内容复制到新数组中，(3)
释放原有数组空间，(4)将新数组作为线性表的存储区。

时间复杂度：O(n)

template <class T>
void seqList<T>::resize()
{
    T *p = data;           //* 指针p指向原顺序表空间
    maxSize *= 2;          //* 扩大2倍表空间
    data = new T[maxSize]; //* 将旧的数据指向新的表空间

    for (int i = 0; i < length; ++i) //* 复制元素至扩大后的新表
        data[i] = p[i];

    delete[] p;
}

线性表的【链式】表示

链式存储线性表时，不需要使用地址连续的存储单元，即不需要逻辑上相邻的元素在物理位置上也相邻，它通过“链”建立起数据元素之间的逻辑关系，因此插入和删除操作不需要移动元素
，则只需要修改指针，但会失去顺序表随机存储的特点。

template <class T>
class linkList : public List<T>
{
private:
    struct Node
    {
        T data;     //* 结点数据域
        Node *next; //* 结点指针域
        Node(const T value, Node *p = NULL)
        {
            data = value;
            next = p;
        }

        Node(Node *p = NULL)
        {
            next = p;
        }
    };

    Node *head; //* 单链表头指针
    Node *tail; //* 单链表尾指针
    int length; //* 单链表表长

    Node *getPosition(int position) const; //* 返回指向position元素的指针

    void traverseRecursive(Node *p);
    void traverseNonRecursive1();
    void traverseNonRecursive2();
    void traverseNonRecursive3();

public:
    linkList();  //* 构造函数
    ~linkList(); //* 析构函数

    void clear();                                     //* 清空单链表，使其成为空表
    bool empty() const { return head->next == NULL; } //* 判空
    int size() const { return length; }               //* 返回单链表的当前实际长度
    void insert(int position, const T &value);        //* 在位置position上插入一个新元素，表长+1
    void remove(int position);                        //* 删除位于position的元素
    int search(const T &value) const;                 //* 查找值为value的元素在单链表中第一次出现的位置
    T visit(int position) const;                      //* 访问在position位置上的单链表的值

    void traverse() const;           //* 遍历单链表
    void inverse();                  //* 逆置单链表
    void headCreate();               //* 头插法创建单链表
    void tailCreate();               //* 尾插法创建单链表
    int prior(const T &value) const; //* 查找值为value的元素的前驱结点
    linkList *Union(linkList<T> *list);

    void outPut();
};

单链表的运算

  • 构造函数
//** 时间复杂度：O(1)
template <class T>
linkList<T>::linkList()
{
    head = tail = new Node();
    length = 0;
}
  • 析构函数

时间复杂度：O(n)


template <class T>
linkList<T>::~linkList()
{
    clear();
    delete head;
}
  • 清空单链表

清空链表中所有元素。

时间复杂度：O(n)

template <class T>
void linkList<T>::clear()
{
    Node *p, *temp;   //* p为工作指针，指向首元结点
    p = head->next;   //* 防止意外修改头指针
    while (p != NULL) //* 等效于：while(p){}
    {
        temp = p;
        p = p->next; //* 指针后移
        delete temp;
    }

    head->next = NULL; //* 头结点指针域置空
    tail = head;       //* 头尾指针均指向头结点
    length = 0;
}
  • 求表长

算法思想：
与遍历单链表类似，均需要从第一个元素开始遍历并记录临时存储的长度，直到最后一个元素结束。

时间复杂度：O(n)


template <class T>
int linkList<T>::size() const
{
    return length; //* 直接返回length
}
*** 若单链表中未设置变量length存储当前表长，则需要遍历整个单链表以计算表长
template <class T>
int linkList<T>::size() const
{
    Node *p = head->next; //* 从头到尾遍历整个单链表
    int count = 0;
    while (p != NULL)
    {
        count++;
        p = p->next;
    }

    return count;
}
  • 遍历单链表

时间复杂度：O(n)

空间复杂度：O(1)

template <class T>
void linkList<T>::traverse() const
{
    Node *p = head->next;
    cout << "traverse: ";
    while (p != NULL)
    {
        cout << p->data << " ";
        p = p->next;
    }

    cout << endl;
}
  • 头插法创建单链表，可用于逆置链表

Example：根据线性表(5,4,3,2,1)创建单链表，则读入数据的顺序应为：1,2,3,4,5，和线性表中的逻辑顺序正好相反。

元素插入在链表头部，从后往前插入元素。

时间复杂度：O(n)

template <class T>
void linkList<T>::headCreate()
{
    Node *p;
    T value, flag;
    cout << "input Elements, ended with: ";
    cin >> flag; //* 输入结束标志

    while (cin >> value, value != flag)
    {
        p = new Node(value, head->next);
        head->next = p;   //* 结点p插入到头结点后面
        if (head == tail) //* 原链表为空，则结点p为尾结点
            tail = p;

        length++;
    }
}
  • 尾插法创建单链表

Example：根据线性表(1,2,3,4,5)创建单链表，则读入顺序应为：1,2,3,4,5，读入顺序与单链表的结点顺序相同

元素依次从尾部插入。

时间复杂度：O(n)

template <class T>
void linkList<T>::tailCreate()
{
    Node *p;
    T value, flag;
    cout << "input Elements, ended with: ";
    cin >> flag; //* 输入结束标志

    while (cin >> value, value != flag)
    {
        p = new Node(value, NULL);
        tail->next = p; //* 给尾指针的指针域赋值新的元素，结点p插入到尾结点的后面
        tail = p;       //* 结点p成为新的尾结点
        length++;
    }
}
  • 查找位于position位置的元素（按序号查找）

时间复杂度：O(n)

template <class T>
typename linkList<T>::Node *linkList<T>::getPosition(int position) const
{
    Node *p = head; //* 查找指针p初始指向头节点
    int count = 0;

    if (position < -1 || position > length - 1) //* 合法查找位置为(-1..n-1)
        return NULL;                            //* 当要查找的position非法时返回NULL

    while (count <= position)
    {
        p = p->next;
        count++;
    }

    return p; //* 返回位于position位置的结点的指针
}
  • 查找值为value的元素（按值查找）

时间复杂度：O(n)

空间复杂度：O(1)

template <class T>
int linkList<T>::search(const T &value) const
{
    Node *p = head->next; //* 从头结点开始扫描链表
    int count = 0;

    //* 当p不为空与p所指向的data域的值不等于value时，继续扫描链表
    //* 结束循环条件：指针p为NULL 或 指针p的数据域不等于期望值value
    while (p != NULL && p->data != value)
    {
        p = p->next;
        count++;
    }

    if (p == NULL) //* 当p为空时(空表)，直接返回非法值
        return -1;
    else
        return count; //* 返回value在链表中的位置
}
  • 在单链表的position位置插入值为value的元素，挂链

时间复杂度：O(n)

空间复杂度：O(1)

算法思想：
s为指向新结点的指针，p为指向position-1位置元素的指针
(1) s->next = p->next
(2) p->next = s

上述也可表示为：
p指向当前结点，pre表示前一个结点的指针，在p前（pre后）插入元素q
(1) q->next = pre->next
(2) pre->next = q

template <class T>
void linkList<T>::insert(int position, const T &value)
{
    Node *p, *q;
    if (position < 0 || position > length) //* 合法位置(0..n)
        throw outOfRange();

    p = getPosition(position - 1); //* p为指向position-1位置的指针
    q = new Node(value, p->next);  //* 生成新结点
    p->next = q;                   //* q结点插入到p结点的后面
    if (p == tail)                 //* 若在表尾插入
        tail = q;                  //* 则修改表尾指针即可

    length++;
}
  • 在单链表中删除位于position位置的元素（按序号删除）

时间复杂度：O(n)

空间复杂度：O(1)

算法思想：
p指向当前结点(即待删除结点)，pre表示前一个结点的指针
(1) pre->next = p->next || 也可写成：pre->next = pre->next->next，其中将pre->next看成一个结点(即待删除结点)指针
(2) delete p

template <class T>
void linkList<T>::remove(int position)
{
    Node *pre, *p;
    if (position < 0 || position > length - 1)
        throw outOfRange();

    pre = getPosition(position - 1); //* pre为指向position-1位置，即待删除元素的前一个元素的指针
    p = pre->next;                   //* p为指向pre指针的下一个结点的指针，即指向待删除结点
    if (p == tail)                   //* 若删除元素位于表尾
    {
        tail = pre;       //* 则直接修改表尾
        pre->next = NULL; //* 并将待删除元素的前一个元素的指针域指向NULL
        delete p;         //* 释放待删除结点
    }
    else //* 若删除元素位于表间
    {
        pre->next = p->next; //* 将待删除结点的next指针交付给前一个结点的指针域
        delete p;            //* 释放待删除结点
    }

    length--;
}
  • 逆置单链表（头插法实现）

时间复杂度：O(n)

空间复杂度：O(1)

算法思想：

  1. 断开链接，构造空链表
  2. 将原链表中元素用头插法重新插入head链表
template <class T>
void linkList<T>::inverse()
{
    Node *p, *temp;    //* p用于遍历单链表，temp用于保存后继结点
    p = head->next;    //* 指向首元结点
    head->next = NULL; //* 头结点指针域置空，构成空链表
    if (p)
        tail = p; //* 更新尾结点

    while (p)
    {
        temp = p->next;       //* 暂存p的后继
        p->next = head->next; //* 修改首元结点
        head->next = p;       //* 修改头结点
        p = temp;             //* 处理下一结点
    }
}
  • 查找值为value的前驱（按值查找）
template <class T>
int linkList<T>::prior(const T &value) const
{
    Node *p = head->next;
    Node *pre = NULL;
    int count = -1;
    while (p && p->data != value)
    {
        pre = p;
        p = p->next;
        count++;
    }

    if (p == NULL)
        return -1;
    else
        return count;
}

顺序表、链表的比较

数据结构 存取（读写）方式 逻辑结构与物理结构 查找、插入和删除操作 空间分配
顺序存储 顺序存取、随机存取（O(1)） 逻辑相邻，物理相邻 按值查找：无序（O(n)），有序（折半查找，O(log2n)）；按序查找：随机访问，O(1) 预分配空间，易出现空间浪费与溢出
链式存储 从头顺序存取（O(n)） 逻辑相邻，物理不一定相邻 按值查找：O(n)；按序查找：O(n) 动态分配，但插入删除需要移动大量元素，操作效率低

实际应用

数据结构 基于存储考虑 基于运算考虑 基于环境考虑
顺序存储 未知存储规模时，不宜采用顺序表 按序号访问时优于链式存储结构，时间复杂度：O(1)；但在插入与删除操作时劣于链式存储，需要移动大量元素，且平均移动一半元素 实现较为简单，任何高级语言中都有数组类型，适合稳定存储的线性表
链式存储 动态分配存储空间，但存储密度低 按序号访问时，时间复杂度：O(n)；插入删除时优于顺序存储，虽要先查找位置，但总体优于顺序存储 基于指针，适合动态性较强（插入删除操作频繁）的线性表

栈

基本定义

栈 (Stack) 是只允许在一端进行插入或删除操作的线性表。

首先栈是一种线性表，但限定这种线性表只能在某一端进行插入和删除操作。

栈的规律类似手枪的弹夹，羽毛球桶。

栈顶：指线性表允许进行插入删除的一端

栈底：固定的，不允许进行插入删除的另一端

栈规则：后进先出

栈的抽象数据类型

template <class T>
class Stack
{
public:
    virtual bool empty() const = 0;        //* 判栈空
    virtual int size() const = 0;          //* 返回栈大小
    virtual void push(const T &value) = 0; //* 进栈
    virtual T pop() = 0;                   //* 出栈
    virtual T getTop() const = 0;          //* 返回栈顶元素
    virtual void clear() = 0;              //* 清空栈
    virtual ~Stack(){};
};

自定义的异常处理类


class outOfRange : public exception
{
public:
    const char *what() const throw()
    {
        return "OUT of RANGE";
    }
};

class errorSize : public exception
{
public:
    const char *what() const throw()
    {
        return "ERROR size";
    }
};

栈的【顺序】表示

采用顺序存储的栈称为顺序栈，利用一组地址连续的存储单元存放自栈底到栈顶的数据元素，同时附设 top 指针指向当前栈顶元素位置。

template <class T>
class seqStack : public Stack<T>
{
private:
    T *data;       //* 顺序栈中元素的数组
    int top;       //* 顺序栈顶指针，指向栈顶元素
    int maxSize;   //* 顺序栈的大小
    void resize(); //* 扩顺序栈空间

public:
    //* 构造函数
    seqStack(int initSize = 100)
    {
        if (initSize <= 0)
            throw errorSize();

        data = new T[initSize]; //* 数组
        maxSize = initSize;     //* 当top == maxSize - 1，则表示栈满
        top = -1;               //* 初始时top = -1，表示栈空
    }

    ~seqStack() { delete[] data; };          //* 析构函数
    bool empty() const { return top == -1; } //* 判栈空
    int size() const { return top + 1; }     //* 返回顺序栈大小
    void clear()                             //* 清空顺序栈
    {
        //* 直接将top指针初始化即可清空栈
        top = -1;
    };
    void push(const T &value); //* 顺序栈进栈
    T pop();                   //* 顺序栈出栈
    T getTop() const;          //* 获取顺序栈栈顶元素
};

顺序栈的运算

  • 入栈，进栈

从栈顶依次将元素按后进先出的规则填充入栈。
需注意：入栈时，栈顶指针先 +1，后元素入栈。

时间复杂度：栈满时：O(n)，栈未满时：O(1)

template <class T>
void seqStack<T>::push(const T &value)
{
    //* 当top == maxSize - 1，表示栈满
    if (top == maxSize - 1)
        resize(); //* 若栈满仍插入，则会导致上溢

    // ++top;
    // data[top] = value;
    //* --- 等效于下方代码 ---
    data[++top] = value; //* 修改栈顶指针，元素进栈，先+1后写入
}
  • 出栈，弹栈

将栈顶元素按后进先出的规则依次弹出。
需注意：出栈时，元素先出栈，后栈顶元素 -1。

时间复杂度：O(1)

template <class T>
T seqStack<T>::pop()
{
    if (empty()) //* 空栈无法出栈，即下溢
        throw outOfRange();

    // --top;
    // return data[top]
    //* --- 等效于下方代码 ---
    return data[top--]; //* 修改栈顶指针，元素出栈，先出栈后-1
}
  • 取栈顶元素

输出栈顶元素的值。

时间复杂度：O(1)

template <class T>
T seqStack<T>::getTop() const
{
    if (empty())
        throw outOfRange();

    return data[top]; //* 直接返回栈顶元素
}
  • 扩大栈空间

算法思想：

  1. 遍历旧栈元素并临时存储。
  2. 申请新栈（容量大于旧栈，如申请两倍、三倍空间）。
  3. 将临时存放的旧栈元素依次重新填充进入新栈。
  4. 释放旧栈空间。

时间复杂度：O(n)

template <class T>
void seqStack<T>::resize()
{
    T *temp = data;                  //* 将旧栈区数据临时存储
    data = new T[2 * maxSize];        //* 扩大栈区大小
    for (int i = 0; i < maxSize; ++i) //* 将旧栈区的数据赋值到新栈区
        data[i] = temp[i];

    maxSize *= 2;
    delete[] temp; //* 释放旧栈区
}

栈的【链式】表示

链栈的优点是便于多个栈共享存储空间和使用效率，且不存在栈满上溢的现象。
链栈通常采用单链表表示，并规定所有操作均在单链表表头进行。

template <class T>
class linkStack : public Stack<T>
{
private:
    struct Node
    {
        T data;
        Node *next;
        Node() { next = NULL; }
        Node(const T &value, Node *p = NULL)
        {
            data = value;
            next = p;
        }
    };
    Node *top;

public:
    linkStack() { top = NULL; };               //* 初始化空栈
    ~linkStack() { clear(); };                 //* 析构函数
    void clear();                              //* 清空栈
    bool empty() const { return top == NULL; } //* 判栈空，时间复杂度：O(n)
    int size() const;                          //* 返回链栈长度
    void push(const T &value);                 //* 进栈
    T pop();                                   //* 出栈
    T getTop() const;                          //* 返回栈顶元素
};

链栈的运算

  • 栈长度

时间复杂度：O(n)

template <class T>
int linkStack<T>::size() const
{
    Node *p = top;
    int count = 0;
    while (p) //* 遍历栈，统计元素个数
    {
        count++;
        p = p->next;
    }

    return count;
}
  • 入栈，进栈

时间复杂度：O(1)

template <class T>
void linkStack<T>::push(const T &value)
{
    Node *p = new Node(value, top); //* 在栈顶插入元素
    top = p;                        //* 更新栈顶指针
}
  • 出栈，弹栈

时间复杂度：O(1)

template <class T>
T linkStack<T>::pop()
{
    if (empty())
        throw outOfRange();

    Node *p = top;
    T value = p->data; //* 保留栈顶元素的值
    top = top->next;   //* 更新栈顶指针至下一个栈顶元素
    delete p;          //* 释放出栈的栈顶元素
    return value;      //* 返回出栈元素值
}
  • 取栈顶元素

时间复杂度：O(1)

template <class T>
T linkStack<T>::getTop() const
{
    if (empty())
        throw outOfRange();

    return top->data; //* 返回栈顶元素值
}
  • 清空栈

时间复杂度：O(n)

template <class T>
void linkStack<T>::clear()
{
    Node *p;
    while (top != NULL)
    {
        p = top;         //* p指向当前栈顶元素
        top = top->next; //*top指针依次指向写一个栈顶元素
        delete p;        //* 释放p指向的当前元素
    }
}

队列

基本定义

队列（Queue），是一种操作受限的线性表，只允许在表的一端进行插入，在表的另一端进行删除。

向队列中插入元素的操作成为入队或进队。

删除元素称为出队或离队。

参考现实中排队的例子不难总结队列的规律：先进先出

队列的抽象数据类型

template <class T>
class Queue
{
public:
    virtual bool empty() const = 0;           //* 判队空
    virtual int size() const = 0;             //* 求队长
    virtual void clear() = 0;                 //* 清空队列
    virtual void enQueue(const T &value) = 0; //* 入队
    virtual T deQueue() = 0;                  //* 出队
    virtual T getHead() const = 0;            //* 获取队头元素
    virtual ~Queue();                         //* 析构函数
};

自定义的异常处理类

class outOfRange : public exception
{
public:
    const char *what() const throw()
    {
        return "ERROR, out of range";
    }
};

class errorSize : public exception
{
public:
    const char *what() const throw()
    {
        return "ERROR, error size";
    }
};

队列的【顺序】表示

队列的顺序实现是指分配一块连续的存储单元存放队列中的元素，并附设两个指针：

队头指针 front 指向队头元素

队尾指针 rear 指向队尾元素的下一个位置

template <class T>
class seqQueue : public Queue<T>
{
private:
    T *data;       //* 存放数据的数组
    int maxSize;   //* 队列大小
    int front;     //* 队首指针
    int rear;      //* 队尾指针
    void resize(); //* 扩大队列容量

public:
    seqQueue(int size = 100);
    ~seqQueue() { delete[] data; }
    void clear() { front = rear = 1; }
    bool empty() const { return front == rear; }
    bool full() const { (rear + 1) % maxSize == front; }
    int size() const { return (rear - front + maxSize) % maxSize; }
    void enQueue(const T &value);
    T deQueue();
    T getHead() const;
};

顺序队列的运算

  • 初始化
template <class T>
seqQueue<T>::seqQueue(int initSize)
{
    if (initSize <= 0)
        throw errorSize();

    data = new T[initSize];
    maxSize = initSize;
    front = rear = -1;
}
  • 进队，入队
template <class T>
void seqQueue<T>::enQueue(const T &value)
{
    if ((rear + 1) % maxSize == front)
        resize();

    rear = (rear + 1) % maxSize;
    data[rear] = value;
}
  • 出队，离队
template <class T>
T seqQueue<T>::deQueue()
{
    if (empty())
        throw outOfRange();

    front = (front + 1) % maxSize;
    return data[front];
}
  • 取队头元素
template <class T>
T seqQueue<T>::getHead() const
{
    if (empty())
        throw outOfRange();

    return data[(front + 1) % maxSize];
}
  • 扩大队列容量
template <class T>
void seqQueue<T>::resize()
{
    T *p = data;
    data = new T[2 * maxSize];
    for (int i = 1; i < maxSize; ++i)
        data[i] = p[(front + i) % maxSize];

    front = 0;
    rear = maxSize - 1;
    maxSize *= 2;
    delete p;
}

队列的【链式】表示

队列的链式表示成为链队列，它实际上是一个同时带有队头指针和队尾指针的单链表。

头指针指向对头结点

尾指针指向队尾结点

template <class T>
class linkQueue : public Queue<T>
{
private:
    struct Node
    {
        T data;
        Node *next;
        Node(const T &value, Node *n = NULL)
        {
            data = value;
            next = n;
        }

        Node() : next(NULL) {}
        ~Node();
    };

    Node *front, *rear;

public:
    linkQueue() { front = rear = NULL; }
    ~linkQueue();
    void clear();
    bool empty() const { return front == NULL; };
    int size() const;
    void enQueue(const T &value);
    T deQueue();
    T getHead() const;
};

链队列的运算

  • 析构
template <class T>
linkQueue<T>::~linkQueue<T>()
{
    Node *p;
    while (front != NULL)
    {
        p = front;
        front = front->next;
        delete p;
    }
}
  • 清空链队列
template <class T>
void linkQueue<T>::clear()
{
    Node *p;
    while (front != NULL)
    {
        p = front;
        front = front->next;
        delete p;
    }

    rear = NULL;
}
  • 求队长
template <class T>
int linkQueue<T>::size() const
{
    Node *p = front;
    int count = 0;
    while (p)
    {
        count++;
        p = p->next;
    }

    return count;
}
  • 入队，进队
template <class T>
void linkQueue<T>::enQueue(const T &value)
{
    if (rear == NULL)
    {
        front = rear = new Node(value);
    }
    else
    {
        rear->next = new Node(value);
        rear = rear->next;
    }
}
  • 出队
template <class T>
T linkQueue<T>::deQueue()
{
    if (empty())
        throw outOfRange();

    Node *p = front;
    T value = front->data;
    front = front->next;
    
    if (front == NULL)
        rear = NULL;

    delete p;
    return value;
}
  • 输出队头元素
template <class T>
T linkQueue<T>::getHead() const
{
    if (empty())
        throw outOfRange();

    return front->data;
}

有关树、图、查找与排序算法请直接参阅 Github 源码

PhoenixNest

用实力让情怀落地
0%