你好赵伟

这个屌丝很懒，什么也没留下！

热门标签

数据结构-线性表及其应用(C++)

作者：你好赵伟 | 2024-07-09 05:51:26

踩

数据结构-线性表及其应用(C++)

线性表是最基本、最简单、也是最常用的一种数据结构。它是由n个具有相同特性的数据元素的有限序列。其数据元素之间的关系是一对一的关系，即除了第一个和最后一个数据元素之外，其它数据元素都是首尾相接的。其主要的物理存储方式分为顺序表(相邻数据元素在底层结构上是连续的)和链表(一般是不连续的)。

顺序表

顺序表实际上就是数组存储。为了使程序的应用范围更广，用类模板的方式将其进行封装。

构造与析构

首先先搭建类体，并利用C++运算符new和delete实现构造与析构。这部分中值得注意的是在拷贝构造时要采用深拷贝，避免浅拷贝造成的重复释放内存的问题。

#include <initializer_list>
template <typename T>
class mylist
{
protected:
    T *b, *e;
    mylist(T *p, T *q) : b(p), e(q) {}

public:
    mylist() : b(nullptr), e(nullptr) {}
    ~mylist()
    {
        if (b)
            delete[] b;
    }
    mylist(T x, unsigned n)
    {
        if (n)
        {
            *(e = b = new T[n]) = x;
            while (--n)
                *++e = x;
            ++e;
        }
    }
    mylist(std::initializer_list<T> x)
    {
        const T *p(x.begin());
        *(e = b = new T[x.size()]) = *p;
        while (++p < x.end())
            *++e = *p;
        ++e;
    }
    mylist(const mylist &x) // 深拷贝
    {
        if (x.b == x.e)
            b = e = nullptr;
        else
        {
            T *p(x.b);
            *(e = b = new T[x.e - x.b]) = *p;
            while (++p < x.e)
                *++e = *p;
            ++e;
        }
    }
    mylist &operator=(const mylist &x)
    {
        if (x.b == x.e)
        {
            if (b != e)
                delete[] b;
            b = e = nullptr;
            return *this;
        }
        T *p(x.b);
        *(e = b = new T[x.e - x.b]) = *p;
        while (++p < x.e)
            *++e = *p;
        ++e;
        return *this;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63

判断线性表是否为空表

由于是类外函数，因此要在类内加入如下友元声明：

template <typename D>
friend bool listempty(const mylist<D> &);
1
2

直接判断数组指针是否为空即可，程序如下：

template <typename T>
inline bool listempty(const mylist<T> &x)
{
    return x.b == x.e;
}
1
2
3
4
5

求线性表的长度

直接返回尾后指针和头指针之间的距离即可，程序如下：

template <typename T>
inline unsigned listlength(const mylist<T> &x)
{
    return x.e - x.b;
}
1
2
3
4
5

输出线性表

从头指针开始遍历整个顺序表。程序如下：

#include <iostream>
template <typename T>
void displist(const mylist<T> &x)
{
    if (!x.b)
    {
        std::cout << "\t[空]\n";
        return;
    }
    T *p(x.b);
    unsigned i(1);
    std::cout << "序号" << '\t' << "元素" << std::endl;
    std::cout << i << '\t' << *p << std::endl;
    while (++p < x.e)
        std::cout << ++i << '\t' << *p << std::endl;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

下标访问的实现

由于是顺序表，从头指针开始直接加上下标的值即可。程序如下：

template <typename T>
inline bool getelem(const mylist<T> &x, unsigned i, T &e)
{
    if (!i || i > listlength(x))
        return false;
    e = x.b[i - 1];
    return true;
}
1
2
3
4
5
6
7
8

出于后续程序的方便考虑，还重载了[]运算符，但这是一个不安全的成员函数¹。程序如下：

T &operator[](unsigned n)
{
    return *(b + n);
}
1
2
3
4

按元素值查找

由于数据未必有序，因此利用顺序查找：

template <typename T>
unsigned locateelem(const mylist<T> &x, T e)
{
    if (!x.b)
        return 0; // x为空
    T *p(x.b);
    do
        if (*p == e)
            return ++p - x.b;
    while (++p < x.e);
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12

插入数据元素

逐个“后移”，给“空”出来的位置赋值即可。程序如下：

template <typename T>
bool listinsert(mylist<T> &x, unsigned i, T e)
{ // 插入以后在第i+1个位置，因此允许i=0
    if (i > listlength(x))
        return false;
    T *p(x.b), *q(x.e);
    if (!i) // 在第1个位置插入
    {
        *(x.e = x.b = new T[q - p + 1]) = e;
        if (p) // 有可能为空表
        {
            T *t(p);
            do
                *++x.e = *p;
            while (++p < q);
            delete[] t;
        }
        ++x.e;
        return true;
    }
    *(x.e = x.b = new T[q - p + 1]) = *p;
    T *t(p);
    while (--i)
        *++x.e = *++p;
    *++x.e = e;
    while (++p < q)
        *++x.e = *p;
    delete[] t;
    ++x.e;
    return true;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

删除数据元素

逐个“前移”，遇到待删除元素直接跳过，不拷贝即可。程序如下：

template <typename T>
bool listdelete(mylist<T> &x, unsigned i)
{
    if (!i || i > listlength(x))
        return false;
    T *p(x.b), *q(x.e), *t(p);
    if (i == 1)
    {
        if (q == ++p) // 只有一个元素
        {
            delete[] t;
            x.e = x.b = nullptr;
            return true;
        }
        *(x.e = x.b = new T[q - p]) = *p;
        while (++p < q)
            *++x.e = *p;
        delete[] t;
        ++x.e;
        return true;
    }
    *(x.e = x.b = new T[--q - p]) = *p;
    --i;
    while (--i)
        *++x.e = *++p;
    ++p;
    while (++p <= q)
        *++x.e = *p;
    ++x.e;
    delete[] t;
    return true;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

清空线性表

类似于析构：

template <typename T>
inline void listclear(mylist<T> &x)
{
    if (x.b)
    {
        delete[] x.b;
        x.b = x.e = nullptr;
    }
}
1
2
3
4
5
6
7
8
9

链表

链表是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。

准备工作

链表的元素并不是单独的数据元素，而是由数据域和指针域构成的结构体。因此首先编写如下的结构体：

template <typename T>
struct myelem
{
    T data;
    myelem *next;
    // 为了方便，写个构造函数
    myelem(T a, myelem *p = nullptr) : data(a), next(p) {}
};
1
2
3
4
5
6
7
8

构造与析构

template <typename T>
class mylink
{
    myelem<T> *head;

public:
    mylink() : head(nullptr) {}
    mylink(std::initializer_list<T> x)
    {
        const T *p(x.begin()), *q(x.end());
        if (p != q)
        {
            myelem<T> *a(head = new myelem<T>(*p));
            while (++p < q)
                a = a->next = new myelem<T>(*p);
        }
        else
            head = nullptr;
    }
    ~mylink()
    {
        myelem<T> *p(head);
        while (p)
        {
            p = p->next;
            delete head;
            head = p;
        }
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

判断链表是否为空

直接对头指针判断即可。程序如下：

template <typename T>
inline bool linkempty(const mylink<T> &x)
{
    return !x.head;
}
1
2
3
4
5

求链表的长度

利用循环及计数器直到指针域为空即可。程序如下：

template <typename T>
unsigned linklength(const mylink<T> &x)
{
    const myelem<T> *p(x.head);
    unsigned n(0);
    if (p)
        do
            ++n;
        while (p = p->next);
    return n;
}
1
2
3
4
5
6
7
8
9
10
11

输出链表

为了与顺序表保持一致，因此写了普通函数而不是重载<<运算符。程序如下：

template <typename T>
void displink(const mylink<T> &x)
{
    const myelem<T> *p(x.head);
    if (p)
    {
        unsigned n(0);
        std::cout << "序号\t元素值" << std::endl;
        do
            std::cout << ++n << '\t' << p->data << std::endl;
        while (p = p->next);
    }
    else
        std::cout << "\t[空]" << std::endl;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

下标访问的实现

由于链表以指针方式存储，物理结构上不相连，因此利用循环来得到元素值。程序如下：

template <typename T>
bool getelem(const mylink<T> &x, unsigned i, T &e)
{
    if (!i)
        return false;
    const myelem<T> *p(x.head);
    if (!p)
        return false;
    while (--i)
        if (!(p = p->next))
            return false;
    if (p)
    {
        e = p->data;
        return true;
    }
    return false;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

查找元素

同顺序表，顺序查找。程序如下：

template <typename T>
unsigned locateelem(const mylink<T> &x, T e)
{
    const myelem<T> *p(x.head);
    if (!p)
        return 0;
    if (p->data == e)
        return 1;
    unsigned k(2);
    while (p = p->next)
    {
        if (p->data == e)
            return k;
        ++k;
    }
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

插入元素

先找位置，直接插入即可，不必再像顺序表一样逐个后移：

template <typename T>
bool linkinsert(mylink<T> &x, unsigned i, T e)
{
    if (!i)
    {
        x.head = new myelem<T>(e, x.head);
        return true;
    }
    myelem<T> *p(x.head);
    if (!p)
        return false;
    while (--i)
        if (!(p = p->next))
            return false;
    p->next = new myelem<T>(e, p->next);
    return true;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

删除元素

同理，先找位置，再删除：

template <typename T>
bool linkdelete(mylink<T> &x, unsigned i)
{
    if (!i)
        return false;
    myelem<T> *p(x.head);
    if (!p)
        return false;
    while (--i)
        if (!(p = p->next))
            return false;
    if (!p->next)
        return false;
    myelem<T> *q(p->next);
    p->next = q->next;
    delete q;
    return true;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

线性表的应用

有了顺序表和链表两种类以后，来看看它们的应用。

最大子列问题

给定 $n$ 个整数组成的序列 ${N_k\}_{k=1}^n$ 。“连续子列”被定义为 ${N_k\}_{k=i}^j$ ，其中 $1\leqslant i\leqslant j\leqslant n$ 。“最大子列和”则被定义为所有连续子列元素的和中最大者。现要求计算给定整数序列的最大子列和。

求解算法

暴力求解

遍历所有子列：

#include "list.h"
template <typename T>
T MaxSubseqSum(const mylist<T> &x)
{
    T max(0), p, t;
    for (unsigned i(1); i <= listlength(x); ++i)
        for (unsigned j(i); j <= listlength(x); ++j)
        {
            p = 0;
            for (unsigned k(i); k <= j; ++k)
            {
                getelem(x, k, t);
                p += t;
            }
            if (p > max)
                max = p;
        }
    return max;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

时间复杂度： $O(n^3)$

在线处理

由于最大子列是线性表中连续的序列，故可以将其转化为部分和序列的差的最大值问题。记

$S_k=$

{\begin{cases} \sum_{i = 1}^{k} N_{i}, & 1 ⩽ k ⩽ n \\ 0, & k = 0 \end{cases}

$\begin{cases} \sum\limits_{i=1}^kN_i,&1\leqslant k\leqslant n\\0,&k=0 \end{cases}$

S_{k} = ⎩ ⎨ ⎧ i = 1 \sum k N_{i}, 0, 1 ⩽ k ⩽ n k = 0

则问题转化为求 $\max\limits_{i\geqslant j}S_i-S_j$ 。

#include "list.h"
template <typename T>
T MaxSubseqSum(const mylist<T> &x)
{
    unsigned i(0);
    T a(0), max(a), min(a), temp, result(a);
    while (++i <= listlength(x))
    {
        getelem(x, i, temp);
        if ((a += temp) > max)
        {
            if (result < (max = a) - min)
                result = max - min;
        }
        else if (a < min)
            min = a;
    }
    return result;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

时间复杂度： $O (n)$

测试程序

using namespace std;
int main()
{
    mylist<int> x;
    char ch;
    unsigned a;
    int b;
    while (true)
    {
        cout << "请选择操作:\nA-判断线性表是否为空\nB-求线性表的长度\nC-输出线性表\nD-求线性表中某个元素的值\nE-按元素值查找\nF-插入数据元素\nG-删除数据元素\nH-求线性表的最大子列\nI-清空线性表\nJ-退出程序" << endl;
        cin >> ch;
        switch (ch)
        {
        case 'A':
            if (listempty(x))
                cout << "线性表为空!" << endl;
            else
                cout << "线性表非空!" << endl;
            break;
        case 'B':
            cout << "线性表长度为" << listlength(x) << endl;
            break;
        case 'C':
            cout << "线性表为:" << endl;
            displist(x);
            break;
        case 'D':
            cout << "请输入要获取的元素编号:";
            cin >> a;
            if (getelem(x, a, b))
                cout << "获取成功!\n元素值为:" << b << endl;
            else
                cout << "获取失败!" << endl;
            break;
        case 'E':
            cout << "请输入待查找的元素值:";
            cin >> b;
            if (a = locateelem(x, b))
                cout << "查找成功!\n元素编号为:" << a << endl;
            else
                cout << "查找失败!" << endl;
            break;
        case 'F':
            cout << "请输入要插入的位置编号:";
            cin >> a;
            cout << "请输入要插入的元素值:";
            cin >> b;
            if (listinsert(x, --a, b))
                cout << "插入成功!" << endl;
            else
                cout << "插入失败!" << endl;
            break;
        case 'G':
            cout << "请输入要删除的元素编号:";
            cin >> a;
            if (listdelete(x, a))
                cout << "删除成功!" << endl;
            else
                cout << "删除失败!" << endl;
            break;
        case 'H':
            cout << "最大子列和为:" << MaxSubseqSum(x) << endl;
            break;
        case 'I':
            listclear(x);
            cout << "清空成功!" << endl;
            break;
        case 'J':
            return 0;
        default:
            cout << "选择错误!\n请重新选择!" << endl;
        }
        system("pause");
        system("cls");
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76

如测试线性表为：{6,8,-9,-7,4,0,8,-4,-5,-5}

输入H并回车即得：

“最大子列和为:14”

约瑟夫环问题

据说著名犹太历史学家Josephus有过以下的故事：在罗马人占领乔塔帕特后，39个犹太人与Josephus及他的朋友躲到一个洞中，39个犹太人决定宁愿死也不要被敌人抓到，于是决定了一个自杀方式，41个人排成一个圆圈，由第1个人开始报数，每报数到第3人该人就必须自杀，然后再由下一个重新报数，直到所有人都自杀身亡为止。然而Josephus 和他的朋友并不想遵从。首先从一个人开始，越过k-2个人（因为第一个人已经被越过），并杀掉第k个人。接着，再越过k-1个人，并杀掉第k个人。这个过程沿着圆圈一直进行，直到最终只剩下一个人留下，这个人就可以继续活着。则问题为，给定总人数以及报数k，一开始要站在什么地方才能避免被处决？

求解算法

顺序表模拟法

利用顺序表模拟逐个报数的过程。建立顺序表，第i个位置代表第i+1个人。程序如下：

#include "list.h"
unsigned josephus1(unsigned n, unsigned r)
{
    if (!n)
        return 0;
    if (n == 1)
        return 1;
    mylist<bool> a(false, n);
    unsigned i(((r - 1) % n)), k(r), m(n - 1);
    a[i] = true;
    while (--m)
    {
        do
            if (a[++i %= n])
                ++k;
        while (--k);
        k = r;
        a[i] = true;
    }
    return locateelem(a, false);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

链表模拟法

利用循环链表模拟逐个报数的过程。程序如下：

struct node
{
    int no;
    struct node *next;
};
unsigned josephus2(unsigned n, unsigned r)
{
    unsigned i;
    struct node *list, *p, *q;
    (p = new node)->no = 1;
    list = q = p;
    for (i = 2; i <= n; ++i) // 创建链表
    {
        (p = new node)->no = i;
        q->next = p, q = p; // else list->next=p,list=p;
    }
    q = p = q->next = list; // 首尾相连
    while (p->next != p)    // 进行排减
    {
        for (i = 1; i < r; ++i)
            q = p, p = p->next; // 跳过m-1
        q->next = p->next;      // 排除m
        delete p;
        p = q->next; // 重新将链表相连
    }
    return p->no;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

递推法

将n个人编号： $0,\,1,\cdots,\,n$ 。设报到 $r$ 的人退出，若一共有 $n$ 个人，设 $a_n^{(r)}$ 表示此时剩下的人的编号，则每淘汰掉一个人，下一个人成为头，相当于把数组向前移动 $r$ 位。若已知 $n - 1$ 个人时，即胜利者的下标位置为 $a_{n-1}^{(r)}$ ，则 $n$ 个人的时候，就是往后移动 $r$ 位。因为有可能数组越界，超过的部分会被接到头上，所以还要模 $n$ 。故可得递推公式

$a_n^{(r)}=$

{\begin{cases} 0 & , n = 1 \\ (a_{n - 1}^{(r)} + r) mod n & , n > 1 \end{cases}

$\begin{cases}0&,n=1\\(a_{n-1}^{(r)}+r)\bmod n&,n>1\end{cases}$

a_{n}^{(r)} = {0 (a_{n - 1}^{(r)} + r) mod n, n = 1, n > 1

但由于编号是从0开始的，故在最后需要再加一。程序如下：

unsigned sub_josephus(unsigned n, unsigned r)
{
    if (n == 1)
        return 0;
    return (sub_josephus(n - 1, r) + r) % n;
}
unsigned josephus(unsigned n, unsigned r)
{
    return sub_josephus(n, r) + 1;
}
1
2
3
4
5
6
7
8
9
10

测试程序

int main()
{
    unsigned n, r;
    cin >> n >> r;
    cout << josephus2(n, r);
    system("pause");
    return 0;
}
1
2
3
4
5
6
7
8

如：输入17 7，输出2。

无法判断该位置是否合法，即是否在申请的数组空间内。若使用不当，可能造成野指针问题。可能的解决方案是：另外建立一个静态数据成员error，若非法，则返回error的引用。但是一个弊端是无法为error变量给定一个合适的值来表示非正常的情况，其原因是这是抽象类，无法确定一个统一的错误标志。若为具体的类型，则矛盾就可以迎刃而解。(如double类就可以将error赋值为NaN) ↩︎

本文内容由网友自发贡献，转载请注明出处：【wpsshop博客】

数据结构-线性表及其应用(C++)

文章目录

顺序表

构造与析构

判断线性表是否为空表

求线性表的长度

输出线性表

下标访问的实现

按元素值查找

插入数据元素

删除数据元素

清空线性表

链表

准备工作

构造与析构

判断链表是否为空

求链表的长度

输出链表

下标访问的实现

查找元素

插入元素

删除元素

线性表的应用

最大子列问题

求解算法

暴力求解

在线处理

测试程序

约瑟夫环问题

求解算法

顺序表模拟法

链表模拟法

递推法

测试程序