1. Toy模板网首页
  2. > Toy博客

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

10月前 作者：zsc_118 分类：Toy博客 阅读(39) 违法举报

这篇具有很好参考价值的文章主要介绍了数据结构-线性表及其应用(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;
    }
};

判断线性表是否为空表

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

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

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

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

求线性表的长度

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

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

输出线性表

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

#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;
}

下标访问的实现

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

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。程序如下：

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

按元素值查找

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

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;
}

插入数据元素

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

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;
}

删除数据元素

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

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;
}

清空线性表

类似于析构：

template <typename T>
inline void listclear(mylist<T> &x)
{
    if (x.b)
    {
        delete[] x.b;
        x.b = x.e = nullptr;
    }
}

链表

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

准备工作

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

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

构造与析构

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;
        }
    }
};

判断链表是否为空

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

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

求链表的长度

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

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;
}

输出链表

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

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;
}

下标访问的实现

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

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;
}

查找元素

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

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;
}

插入元素

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

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;
}

删除元素

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

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;
}

线性表的应用

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

最大子列问题

给定 n n n个整数组成的序列 { N k } k = 1 n \{N_k\}_{k=1}^n {Nk​}k=1n​。“连续子列”被定义为 { N k } k = i j \{N_k\}_{k=i}^j {Nk​}k=ij​，其中 1 ⩽ i ⩽ j ⩽ n 1\leqslant i\leqslant j\leqslant n 1⩽i⩽j⩽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;
}

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

在线处理

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

S k = { ∑ i = 1 k N i , 1 ⩽ k ⩽ n 0 , k = 0 S_k=\begin{cases} \sum\limits_{i=1}^kN_i,&1\leqslant k\leqslant n\\0,&k=0 \end{cases} Sk​=⎩ ⎨ ⎧​i=1∑k​Ni​,0,​1⩽k⩽nk=0​

则问题转化为求 max ⁡ i ⩾ j S i − S j \max\limits_{i\geqslant j}S_i-S_j i⩾jmax​Si​−Sj​。

#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;
}

时间复杂度： O ( n ) O(n) 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");
    }
}

如测试线性表为：{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);
}
链表模拟法

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

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;
}
递推法

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

a n ( r ) = { 0 , n = 1 ( a n − 1 ( r ) + r )   m o d   n , n > 1 a_n^{(r)}=\begin{cases}0&,n=1\\(a_{n-1}^{(r)}+r)\bmod n&,n>1\end{cases} an(r)​={0(an−1(r)​+r)modn​,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;
}

测试程序

int main()
{
    unsigned n, r;
    cin >> n >> r;
    cout << josephus2(n, r);
    system("pause");
    return 0;
}

如：输入17 7，输出2。

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

到了这里，关于数据结构-线性表及其应用(C++)的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处： 如若内容造成侵权/违法违规/事实不符，请点击违法举报进行投诉反馈，一经查实，立即删除！

分享到：
领支付宝红包 赞助服务器费用

相关文章

  • 数据结构—哈夫曼树及其应用

    数据结构—哈夫曼树及其应用

    5.6哈夫曼树及其应用 5.6.1哈夫曼树的基本概念 路径 ：从树中一个结点到另一个结点之间的 分支 构成这两个结点间的路径。 结点的路径长度 ：两结点间路径上的 分支数 。 树的路径长度 ：从 树根 到每一个结点的 路径长度之和 。记作 TL 结点数目相同的二叉树中，完全二叉

    2024年02月14日
    浏览(38)
  • 【数据结构】：顺序表及其通讯录应用

    【数据结构】：顺序表及其通讯录应用

    1.1为什么会存在数据结构？ 我们常常接触到诸如生活中的姓名、身份证、网页内的图片、视频等各种各样的信息，这些信息就是我们常说的数据。在使用这些数据时，我们发现随着数据的增加，当我们要单独寻找某一个数据时就会非常困难，就像图书馆内书籍如果没有按一定

    2024年04月26日
    浏览(43)
  • 第14章_集合与数据结构拓展练习(前序、中序、后序遍历,线性结构,单向链表构建,单向链表及其反转,字符串压缩)

    第14章_集合与数据结构拓展练习(前序、中序、后序遍历,线性结构,单向链表构建,单向链表及其反转,字符串压缩)

    1、前序、中序、后序遍历 分析： 完全二叉树： 叶结点只能出现在最底层的两层，且最底层叶结点均处于次底层叶结点的左侧 2、线性结构 3、其它 4、单向链表构建 （1）定义一个单向链表SingleLinked类 包含私有的静态内部类Node 包含Object类型的data属性和Node类型的next属性 包含

    2024年01月23日
    浏览(49)
  • 数据结构第三次实验-图及其应用

    数据结构第三次实验-图及其应用

    一、实验目的 掌握图的存储、构建、搜索等操作和应用，能用最短路径及其搜索等算法编制较 综合性的程序，求解最优路线问题，进行程序设计、数据结构和算法设计等方面的综合训练。 二、实验内容及要求 1、任务描述 实验内容： 用户驾车出行由于出行目的的不同对道

    2024年02月06日
    浏览(42)
  • 深入理解数据结构：队列的实现及其应用场景

    深入理解数据结构：队列的实现及其应用场景

    队列（Queue）是一种具有先进先出（FIFO）特性的数据结构。在队列中，数据的插入和删除操作分别在队列的两端进行。插入操作在队列的尾部进行，而删除操作则在队列的头部进行。这种特性使得队列在很多实际应用中非常有用，比如任务调度、缓冲区管理等。 线性表是一种

    2024年04月28日
    浏览(53)
  • 【数据结构】线性表（六）堆栈：顺序栈及其基本操作（初始化、判空、判满、入栈、出栈、存取栈顶元素、清空栈）

    【数据结构】线性表（六）堆栈：顺序栈及其基本操作（初始化、判空、判满、入栈、出栈、存取栈顶元素、清空栈）

       堆栈Stack 和 队列Queue 是两种非常重要的数据结构，两者都是特殊的线性表： 对于堆栈，所有的插入和删除（以至几乎所有的存取）都是在表的同一端进行 对于队列，所有的插入都是在表的一端进行，所有的删除（以至几乎所有的存取）都是在表的另一端进行。    堆

    2024年02月07日
    浏览(45)

  • 头歌数据结构实训参考---二叉树及其应用

    第1关 实现二叉树的创建 第2关 计算二叉树的深度和节点个数 第3关 递归实现二叉树左右子树交换 第4关 非递归实现二叉树左右子树交换 第5关 层次遍历二叉树

    2024年02月05日
    浏览(43)
  • 【023】C/C++数据结构之链表及其实战应用

    【023】C/C++数据结构之链表及其实战应用

    💡 作者简介：专注于C/C++高性能程序设计和开发，理论与代码实践结合，让世界没有难学的技术。包括C/C++、Linux、MySQL、Redis、TCP/IP、协程、网络编程等。 👉 🎖️ CSDN实力新星，社区专家博主 👉 🔔 专栏介绍：从零到c++精通的学习之路。内容包括C++基础编程、中级编程、

    2024年02月08日
    浏览(56)
  • 数据结构中： 一元多项式的运算（相加，相减，相乘）------用C语言 / C++来实现。 数据结构线性表的操作和应用（顺序存储）

    数据结构中： 一元多项式的运算（相加，相减，相乘）------用C语言 / C++来实现。 数据结构线性表的操作和应用（顺序存储）

    线性表的操作和应用（顺序存储）。用顺序存储实现一元多项式，并进行加、减、乘运算。 （1）一元多项式结构体创建  （2）初始化 （3）一元多项式赋值             （4）打印一元多项式 （5）加法运算                        （6）减法运算 （7）乘法运算    全部代

    2024年02月01日
    浏览(63)
  • 青岛大学_王卓老师【数据结构与算法】Week04_08_线性表的应用1_学习笔记

    青岛大学_王卓老师【数据结构与算法】Week04_08_线性表的应用1_学习笔记

    本文是个人学习笔记，素材来自青岛大学王卓老师的教学视频。 一方面用于学习记录与分享，另一方面是想让更多的人看到这么好的《数据结构与算法》的学习视频。 如有侵权，请留言作删文处理。 课程视频链接： 数据结构与算法基础–第04周08–2.7线性表的应用1–线性表

    2024年02月12日
    浏览(37)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包，优惠每天领

二维码1

领取红包

二维码2

领红包