数据结构-线性表及其应用(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;
}

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

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 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$。“最大子列和”则被定义为所有连续子列元素的和中最大者。现要求计算给定整数序列的最大子列和。

求解算法

暴力求解

遍历所有子列：

#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)$

在线处理

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

$$S_k=?\begin{array}{ll}\sum _{i=1}^k{N}_i,& 1?k?n\\ 0,& k=0\end{array}$$

则问题转化为求$\underset{i?j}{\max }{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;
}

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

$$a_n^{(r)}=\{\begin{array}{ll}0& ,n=1\\ (a_{n?1}^{(r)}+r)\mathrm{mod}n& ,n>1\end{array}$$

但由于编号是从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) ??