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

这篇具有很好参考价值的文章主要介绍了数据结构-线性表及其应用(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 1ijn。“最大子列和”则被定义为所有连续子列元素的和中最大者。现要求计算给定整数序列的最大子列和。

求解算法

暴力求解

遍历所有子列:

#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=1kNi,0,1knk=0

则问题转化为求 max ⁡ i ⩾ j S i − S j \max\limits_{i\geqslant j}S_i-S_j ijmaxSiSj

#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 n1个人时,即胜利者的下标位置为 a n − 1 ( r ) a_{n-1}^{(r)} an1(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(an1(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日
    浏览(37)
  • 【数据结构】:顺序表及其通讯录应用

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

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

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

    2024年01月23日
    浏览(48)
  • 深入理解数据结构:队列的实现及其应用场景

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

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

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

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

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

    2024年02月07日
    浏览(44)
  • 头歌数据结构实训参考---二叉树及其应用

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

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

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

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

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

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

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

    2024年02月12日
    浏览(37)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包