线性表是最基本、最简单、也是最常用的一种数据结构。它是由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∑kNi,0,1⩽k⩽nk=0
则问题转化为求 max i ⩾ j S i − S j \max\limits_{i\geqslant j}S_i-S_j i⩾jmaxSi−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。文章来源:https://www.toymoban.com/news/detail-783560.html
-
无法判断该位置是否合法,即是否在申请的数组空间内。若使用不当,可能造成野指针问题。可能的解决方案是:另外建立一个静态数据成员
error
,若非法,则返回error
的引用。但是一个弊端是无法为error
变量给定一个合适的值来表示非正常的情况,其原因是这是抽象类,无法确定一个统一的错误标志。若为具体的类型,则矛盾就可以迎刃而解。(如double
类就可以将error
赋值为NaN
) ↩︎文章来源地址https://www.toymoban.com/news/detail-783560.html
到了这里,关于数据结构-线性表及其应用(C++)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!