数据结构--线性表_直接前驱和直接后继描述了结点之间的

简述：

线性表是 n (≥0) 个数据元素的有限序列
记作L =（a1, a2, …, an），ai 是表中数据元素（也叫表项），n 是线性表的长度，L是表名。n=0是空表, 第1个表项叫表头（head)，最后1个表项叫表尾(tail)。

原则上讲，线性表中元素的数据类型可以不相同。由于采用的存储结构不同，会对元素的数据类型有限制。为简单起见，假定各元素类型相同。

线性表特点
1.除第一个元素外，其他每一个元素有一个且仅有一个直接前驱。

2.除最后一个元素外，其他每一个元素有一个且仅有一个直接后继。

3.直接前驱和直接后继描述了结点之间的逻辑关系，即邻接关系，表示为<ai , ai+1> 。

一、顺序表

将线性表中元素相继存放在一个连续的存储空间中。可利用一维数组实现。
顺序表特点：
逻辑顺序与物理存储顺序一致，可随机访问。

具体实现：

#include<iostream>
using namespace std;
const int kDefaultSize = 100;
//线性表中存放不同的数据类型，可以用union实现
//union T
//{
//	int val;
//	char ch;
//	float dir;
//	T* link;
//};
template <class T>
class SeqList {
public:
	SeqList(int size=kDefaultSize);
	~Seqlist();
	SeqList(SeqList<T>& L);//拷贝构造
	SeqList<T>& operator=(SeqList<T>& L);//重载运算符=
 
	bool GetData(int i, T& x) const;
	void SetData(int i, T& x);
 
	bool IsEmpty()const;
	bool IsFull()const;
	int Size() const;//表中最大容纳的元素的个数
	int Length() const;//表长度
	void Sort();
	int Locate(int i) const;//定位第i个元素，返回表项序号
	bool Insert(int i, const T& x);//在第i个元素位置插入数据x
	bool Remove(int i, T& x);//删除第i个元素，通过x返回该元素的值
	int Search(const T& x) const;
 
 
//顺序表的静态存储
// 	   T data[kDefaultSize];
// 	   int n;//表示当前元素个数
//顺序表的动态存储
private:
	T* data;
	int n;
	int MAXSIZE;//表示最大能够容纳的元素个数
	void resize(int newSize);//改变数组空间的大小
 
};
template <class T>
SeqList<T>::SeqList(int size)
{
	if (size > 0)
	{
		maxSize = size;
		n = 0;
		data = new T[maxSize];
		if (data = nullptr)
		{
			cerr << "存储分配错误！" << endl;
			exit(1);
		}
	}
}
 
template <class T>
bool SeqList<T>::IsEmpty()const
{
	return n == 0 ? true : false;
}
 
template <class T>
bool SeqList<T>::IsFull()const
{
	return n == MAXSIZE ? true : false;
}
 
template <class T>
int SeqList<T>::Size()const
{
	return MAXSIZE;
}
 
template <class T>
int SeqList<T>::Length()const
{
	return n;
}
 
template <class T>
int SeqList<T>::Locate(int i)const
{
	if (i >= 1 && i <= n)
	{
		return i;
	}
	else
	{
		return 0;
	}
}
 
template <class T>
bool SeqList<T>::GetData(int i,T&x)const
{
	if (i >= 1 && i <= n)
	{
		x = data[i - 1];
		return true;
	}
	return false;
}
 
template <class T>
void SeqList<T>::SetData(int i, T& x)
{
	if (i >= 1 && i <= n)
	{
		data[i - 1] = x;
	}
}
 
template <class T>
int SeqList<T>::Search(const T& x)const
{
	for (int i = 0; i < n; i++)
	{
		if(data[i]==x)
			return (i+1)
	}
	return 0;
}
 
template <class T>
bool SeqList<T>::Insert(int i,const T& x)
{
	if (n == MAXSIZE) return false;
	if (i<1 || i>n + 1) return false;
	if (i < n)
	{
		for (int j = n; j>=i; j--)
		{
			data[j] = data[j - 1];
		}
	}
	data[i - 1] = x;
	n++;
	return true;
}
 
template <class T>
bool SeqList<T>::Remove(int i, T& x)
{
	if (n==0) return false;
	if (i<1 || i>n) return false;
	x= data[i - 1];
	if (i < n)
	{
		for (int j = i; j<n; j++)
		{
			data[j-1] = data[j];
		}
	}
	n--;
	return true;
}
 
template <class T>
SeqList<T>::SeqList(SeqList<T>& L) {
	maxSize = L.Size();
	n = L.Length();
	data = new T[maxSize];
	if (data == nullptr) {
		cerr << “存储分配错误” << endl;  exit(1);
	}
	T value;
	for (int i = 1; i <= n; i++) {
		L.GetData(i, value);
		data[i - 1] = value;
	}
}
 
template <class T>
SeqList<T>&  SeqList<T>::  operator=(SeqList<T>& L) 
{
	if (this == &L) // 自复制，返回自身
		return *this;
	delete[] data;
	maxSize = L.Size();
	n = L.Length();
	data = new T[maxSize]; // 动态空间分配
 
	if (data == nullptr) {
		cerr << “存储分配错误” << endl;
		exit(1);
	}
	T value;
	for (int i = 1; i <= n; i++) {
		L.GetData(i, value); // 获取L中第i个元素的值
		data[i - 1] = value; // 将该值赋给data数组的第i个元素
	}
	return *this;
}

二、单链表

单链表是包含0个或多个元素的线性结构，其中每个元素（也称为结点node）包含两个域：数据域和链域。
数据域data：存储线性表的一个元素信息，其数据类型由应用问题决定。
链域：存储一个指针，指向下一个结点的存储地址。表示元素ai与ai+1之间的逻辑关系，即直接后继的存储地址。

first指针为空指针nullptr时，表示该链表当前有0个元素。
表尾没有直接后继，其链域设置为空。

特点：

结点之间可以连续，可以不连续存储。
结点的逻辑顺序与物理顺序可以不一致。
表的长度可以很方便的进行扩充。

具体实现过程如下：

#include<iostream>
using namespace std;
//不带头结点的链表
template<class T> struct ListNode
{
	T data;
	ListNode<T>* next;
	LinkNode<const T& item, LinkNode<T>* ptr = NULL>;
	LinkNode(LinkNode<T>* ptr = NULL);
 
};
 
template <class T>
class List
{
public:
	List();
	List(const List<T>& L);//拷贝构造函数
	List<T>& operator=(const List<T>& L);
	~List();
	void InputFront(const T& elem); // 在表头插入元素
	void InputRear(const T& elem); // 在表尾插入元素
	bool Insert(int i, const T& x); // 在第i个位置插入元素
	bool Remove(int i, T& x); // 删除第i个位置的元素
	ListNode<T>* Search(const T& x); // 查找元素x
	ListNode<T>* Locate(int i); // 返回第i个结点的位置
	bool GetData(int i, T& x) const;// 获取第i个位置的元素
	void SetData(int i, const T& x); // 设置第i个位置的元素
	void MakeEmpty(); // 清空表
	void CopyList(const List<T>& L); // 拷贝表
	int Length() const; // 获取表长度
	bool IsEmpty() const; // 判断表是否为空
	bool IsFull() const; // 判断表是否为满
	void Sort(); // 对表进行排序
	friend ostream& operator<<(
		ostream& out, const List<T>& L); //重载输出运算符
	friend istream& operator>>(
		istream& in, List<T>& L); //重载输入运算符
	void travel_list();//遍历链表
private:
	ListNode<T>* first;
};
 
template <class T>
void List<T>::travel_list()
{
	for (ListNode<T>* iter = first; iter != nullptr; iter = iter->next)
	{
		cout << iter->data << " ";
	}
	/*另一种遍历方法：
	LinkNode<T>* iter = first;
	while (iter != NULL) {
		cout << iter->data << " ";
		iter = iter->next;
	}*/
}
template <class T>
int List<T>::Length() const {
	int len = 0;
	ListNode<T>* iter = first;
	while (iter != nullptr) {
		len++;
		iter = iter->next;
	}
	return len;
}
 
template <class T>
ListNode<T>* List<T>:: Search (const T&x){
	ListNode<T>* iter = first;
	while (iter != nullptr) {
		if (iter->data ==x )
		{
			return iter;
		}
		iter = iter->next;
	}
	return iter;
	/*另外一种查找方式
	LinkNode<T>* Search(const T & x) {
		LinkNode<T>* iter = first;
		while (iter != nullptr && iter->data != x) {
			iter = iter->next;
		}
		return iter;
	}*/
}
 
template<class T>
ListNode<T>* List<T>::Locate(int i)
{
	if (i<0 || i>length())
	{
		return nullptr;
	}
	ListNode<T>* iter = first;
	int j = 1; // 记录当前结点的位置
	while (iter != nullptr && j < i) { // 当前结点非空且位置小于i
		iter = iter->next;
		j++;
	}
	return iter; // 返回第i个结点的位置
}
template<class T>
void  List<T>::SetData(int i,const T&x)
{
	ListNode<T>* p = Locate(i);
	if (p != nullptr)
	{
		p->data = x;
	}
}
 
template <class T> // 获取第i个位置的元素
bool List<T>::GetData(int i, T& x) const {
	ListNode<T>* p = Locate(i);
	if (p != nullptr) {
		x = p->data;
		return true;
	}
	return false;
}
 
template <class T>
void List<T>::InputFront(const T& elem)
{
	ListNode<T>* newNode = new ListNode<T>(elem);
	if (newNode == nullptr)
		return;
	newNode->next = first;
	first = newNode;
}
 
template <class T>
void List<T>::InputRear(const T& elem)
{
	ListNode<T>* newNode = new ListNode<T>(elem);
	if (newNode == nullptr)
		return;
	if (first == nullptr)
	{
		first = newNode;
	}
	else
	{
		ListNode<T>* rear = first;
		while (rear->next != nullptr)
		{
			rear = rear->next;
		}
		rear->next = newNode;
	}
}
 
template<class T>
bool List<T>::Insert(int i, const T& x)//让第i个结点的值，变成插入的x
{
	if (i<1 || i>n)
	return false;
	else {
		if (first->next=NULL)//表头节点没有直接前驱
		{
			InputFront(x);
			return true;
		}
		else {
			pre = first;
			for (int j = 1; j < i - 1; j++)
			{
				if (pre = nullptr) break;
				pre = pre->next;
			}
			/*定位当前位置的前驱结点pre
				listNodeM<T>* pre = locate(i - 1);*/
			if (pre = nullptr)
			{
				ceer << "无效的插入位置" << endl;
				return false;
			}
			else
			{
				newNode = new ListNode<T>(x);
				newNode->next = pre->next;
				pre->next;
				return true;
			}
		}
	}
}
 
template<class T>
bool List<T>::Remove(int i, T& x)
{
	ListNode<T>* del;
	ListNode<T>* pre = Locate(i - 1); // 定位当前位置的前驱节点pre
	if (pre == nullptr || pre->next == nullptr) // 空表或者表链太短
		return false;
	del = pre->next; // 当前位置
	pre->next = del->next;
	x = del->data; //保存删除结点的数据
	delete del;
	return true;
}
 
template<class T>
void List<T>::MakeEmpty()
{
	ListNode<T>* pnd = NULL;
	while (first != NULL)
	{
		pnd = first;
		first = first->next;
		delete pnd;
	}
}
 
template<class T>
List<T>::~List()
{
	MakeEmpty();
}
 
template<class T>
void List<T>::CopyList(const List<T>& L)
{
	if (L.first == NULL)
		return;
	ListNode<T>* newNode = new ListNode<T>(L.first->data);
	first = newNode;
	iter = L.first->next;
	rear = newNode;
	while (iter)
	{
		newNode= new LinkNode<T>(iter->data);
		rear->next = newNode;
		iter = iter->next;
		rear = rear->next;
	}
}
 
template<class T>
List<T>::List(const List<T>& L)
{
	first = nullptr;
	CopyList(L);
}
 
template<class T>
List<T>& List<T>::operator=(const List<T>& L)
{
	//首先判断是否是自复制，如果不是，调用CopyList函数完成链表的复制。
	if (this == &L)
		return *this;
	MakeEmpty();
	CopyList(L);
	return *this;
}

三、循环链表

循环链表（circular list）是另一种形式的表示线性表的链表，它的结点结构与单链表相同，与单链表不同的是链表中表尾结点的next域中不是NULL，而是存放了一个指向链表开始结点的指针。

链表表尾的特点不再是其next域指向NULL，而是其next区域指向表头结点。

在表头位置插入或删除结点，不仅需要修改first指针指向，也需要修改表尾结点next域的指向。

实现过程及举例

#include<iostream>
using namespace std;
template<class T>
struct CircLinkNode
{
    T data;
    CircLinkNode* next;
    CircLinkNode(const T& item, CircLinkNode<T>* ptr = NULL)
    {
        data = item;
        next = ptr;
    }
    CircLinkNode(CircLinkNode<T>* ptr = NULL)
    {
        next = ptr;
    }
};
 
template <class T>      //链表类定义
class CircList {
private:
    CircLinkNode<T>* first, * last;  //头指针, 尾指针
public:
    CircList(const T& x);		         //构造函数
    CircList(const CircList<T>& L);        //复制构造函数
    CircList<T> operator=(const CircList<T>& L);  // 赋值运算符函数
    ~CircList();    //析构函数
 
    bool Insert(int i, const T& x);	                    //插入
    bool Remove(int i, T& x);	   //删除
    CircLinkNode<T>* Search(const T& x);	//搜索
    CircLinkNode<T>* Locate(int i);	//定位
    T* getData(int i);	                               //提取
    void setData(int i, T x);		//修改
    int Length() const;		         //计算链表长度
    bool IsEmpty();//判表空否
    CircLinkNode<T>* getHead() const; //返回表头结点地址
    void setHead(CircLinkNode<T>* p); //设置表头结点地址
};
 
//功能举例实现：
template <class T>
CircLinkNode<T>*  CircList<T>::Search(const T& x)
{
    //在链表中从头搜索其数据值为 x 的结点
    current = first->next;
    while (current != first && current->data != x)
        current = current->next;
    return current;
}
 

四、双向循环链表

双向链表是指在前驱和后继方向都能游历（遍历）的线性链表。

双向链表通常采用带表头结点的循环链表形式。

具体实现：

#include<iostream>
using namespace std;
 
template <class T>
struct DblNode {
    T data;
    DblNode<T>* rLink, * lLink;
    DblNode(DblNode<T>* l = NULL, DblNode<T>* r = NULL) {
        lLink = l;
        rLink = r;
    }
    DblNode(T value, DblNode<T>* l = NULL, DblNode<T>* r = NULL) {
        data = value;
        lLink = l;
        rLink = r;
    }
};
 
template <class T>
class DblList {
private:
    DblNode<T>* first;
public:
    DblList();
    DblList(const DblList<T>& L);
    DblList<T>& operator=(const DblList<T>& L);
    ~DblList();
 
    void MakeEmpty();  //清空
    void CopyList();      //复制链表
    DblNode<T>* GetFirst()const;  //返回头结点
    DblNode<T>* Locate(int i, int d = 1); //判断第i个结点是否在链表中
    bool Insert(int i, const T& x, int d = 1);//在第i个位置插入结点
    bool Remove(int i, T& x, int d);//在第i个位置删除节点
    DblNode<T>* Search(const T& x, int d = 1);// 搜索x
    void SetData(int i, const T& x);// 设置第i个位置上的结点
    bool GetData(int, T& x); //返回第i位置上的结点
    bool IsEmpty(); //判空
    bool IsFull();  //判满
    friend istream& operator >> (istream& in, DblList<T>& dbl);
    friend ostream& operator << (ostream& out, DblList <T>& dbl);
};
 

五、静态链表

为数组中每一个元素附加一个链接指针，就形成静态链表结构。

处理时可以不改变各元素的物理位置，只要重新链接就能改变这些元素的逻辑顺序。

它是利用数组定义的，在整个运算过程中存储空间的大小不会变化。

静态链表每个结点由两个数据成员构成：data域存储数据，next域存放链接指针。
所有结点形成一个结点数组。

下标0是表头结点，next是链域，下个结点的地址。

循环链表的表尾的链域next = 0，回到表头结点。

如果不是循环链表，表尾结点指针next = -1。

next指针是数组下标，因此是整数。

欢迎批评指正！