C++通过类实现单链表（保姆级教程，附源码，可实现多种操作）_while(head->next!=null)

源码提取链接：百度网盘 请输入提取码百度网盘为您提供文件的网络备份、同步和分享服务。空间大、速度快、安全稳固，支持教育网加速，支持手机端。注册使用百度网盘即可享受免费存储空间https://pan.baidu.com/s/1_Yl1tg7TXJERmk7qaOc29g
提取码：s7h1

目录

0.需要引入的库函数

1.认识和构造链表

1.1什么是链表

1.1.1节点

1.1.2链表的连接方式

1.1.3链表的灵魂——head指针

1.1.4链表的构造——带头结点&不带头结点

1.1.5编写析构函数（必写）

1.2空链表及链表的判空条件

2.基础功能实现

2.1返回头指针

2.2返回with_head值（用以外部判断带不带头结点）

2.3返回尾指针

2.4清空链表

2.5链表的长度获取

2.6输入数据构造链表

2.7输出链表

3.更多有意思的方法实现

3.1按位查找结点（返回第i个结点的结点指针）

3.2按值查找（返回其所在结点是第几个）

3.3保存第k个结点的信息（需要提供一个datas结构体来存储）

3.4按位删除结点

3.5按值删除

3.6翻转链表

4.插值

4.1按位插入

4.2单调性判别

4.3按值插入

4.4改进按位插入

5.一些测试函数（自己调试的时候写的）

5.1方法函数测试

5.2带头结点链表测试

5.3不带头结点链表测试

6.LinkList类整合

---

0.需要引入的库函数

#include <iostream>
#include <string>

1.认识和构造链表

1.1什么是链表

老规矩，先康康百度百科对它的定义

1.1.1节点

 可见链表的最小组成单元便是节点，如下图所示，节点则一般由两部分构成——1.数据2.next指针（用于指向下一节点）。

那便先定义一个最小组成单元节点吧！因为囊括了两个部分，所以我们采用结构体来储存这俩数据。那么问题来了，数据data是什么数据类型，指针类型又是什么呢？

data的类型好办，想存一个整形那就来个int data;想存个字符那就char data;但是如果我比较贪，我既想保存一个数字又想保存一串字符呢？那就采用一个结构体来保存数据吧！该部分代码如下：

typedef struct datas
{
	int num;
	string intro;
	datas()
	{
		num = 0;
		intro = "无";
	};
	datas(int n, string s)
	{
		num = n;
		intro = s;
	};
}datas;

这样我们就定义好了一个结构体datas，它囊括两个信息——1.一个整型数据num2.一个字符串intro

并且定义了两种构造方式——无参构造时让数字为0信息为“无”，有参构造时第一个参数传给整形数据，第二个传给字符串数据。

接下来想一想next指针的类型应该是啥，前面说了next指针是用来指向下一节点的地址的，那么假设节点的类型是NodeType，那么next的类型即为NodeType*。而前面又说了节点我们应该构造成一个结构体，欸嘿这一来就成了。

我们得到了节点结构体node。 

typedef struct node
{
	datas* information;
	node* next;
}node;

 （其中information是指向datas结构体的一个指针。）

再来完善一手这个结构体，既然定义了一个结构体那我们不妨给它也写上构造函数好了。先考虑一下无参构造，无参构造时只需要构造一个能放入数据的孤立节点就好。

什么是孤立节点呢？这是我随口胡诌的词哈哈哈，就是说这一个节点的data部分是可以存入数据滴，但是它的next指针指向NULL，意思就是它和其他任何节点没有关联，就像一个孤儿，所以我叫它孤儿孤立节点。

这么一来无参构造的方式就很明确了，给information分配一个内存以确保可以存入数据，再将next指向NULL，如此一来便大功告成!

node() //无参构造结点
{
	information = new datas;
	next = NULL;
};

再来带参构造一个节点，我们关心的只有俩参数，一个是数据指针information（代表这个节点包含何种信息），一个是next指针（指明这个节点将要带领我们去向何方），但往往我们带参只是想建立一个有初始数据的孤立节点，比如下面要说的无头节点链表中的构造方式。 

总的来说带参构造节点时information取何值必须与用户交互，而next可以给以默认值 NULL来构造成带值的孤立节点。于是我们得到了如下的带参构造函数：

node(datas& item, node* ptr = NULL) //带参构造结点（无头结点）
{
	information = &item;
	next = ptr;
};

这时候发挥一下裁缝天赋，将上面的node结构体和两种构造方式一缝合，欸嘿，就得到了完整的节点结构体：

//节点类结构体
typedef struct node
{
 
	datas* information;
	node* next;
	node() //无参构造节点
	{
		information = new datas;
		next = NULL;
	};
	node(datas& item, node* ptr = NULL) //带参构造节点（无头节点）
	{
		information = &item;
		next = ptr;
	};
 
}node;

1.1.2链表的连接方式

知道和构造好了最小组成单元之后再需要figure out的就是组成方式，即链表是通过怎样的方式将一个个最小组成单元——节点连接在一起的。（突然放洋屁哈哈哈）

链表的连接方式很简单，即将每一个节点的next指针指向下一个节点的地址。假设我们有两个孤立节点指针node1, node2（注意这里node1,node2都是节点指针node*，指向两个孤立节点），这时我们将他们连接起来：node1->next = node2;这样就得到了一个长度为2的链表，好耶！

那这时候我们就可以通过node1来访问node2的值，即：node->next->information所指向的datas结构体就是节点2中的信息，同理如果有n个孤立节点依次连接起来，我们就可以通过第一个节点的指针挨个遍历所有节点的信息啦！

1.1.3链表的灵魂——head指针

链表有了节点和连接方式之后，就还差临门一脚了。仿佛此时一个链表类LinkList已经呼之欲出了，但是总觉少了些什么罢，却又是什么呢，我竟答不上来......

究竟少了个啥呢？想想说连接方式里最后说的我们可以通过第一个节点的指针挨个遍历所有节点信息，这个指针就像是所有连接在一起的节点的老大哥一样，所以我们形象的称呼他为老大哥head

显然由于head指向的是链表的第一个节点，所以它的类型是node*，这样我们就得到了LinkList类的雏形：

class LinkList
{
 
private:
    node* head;
 
};

接下来完成以下链表的构造就算是得到了一个初具其形的链表类！

1.1.4链表的构造——带头结点&不带头结点

链表的构造形式有两种：1.带头结点的链表2.不带头结点的链表

它们的区别在于你所感兴趣的信息是从*head结点开始还是(*head->next)结点开始存储。扯白了说就是含有有用信息的结点是从第一个开始捏还是第二个开始捏。

当所感兴趣的信息从(*head->next)结点（也就是第二个结点）开始时第一个结点就只沦为一个指路的工具人，哦不，工具点，此时这个head只用来指路，它带不带信息，带什么信息都雨我无瓜。这便是带头结点的单链表。

当所感兴趣的信息从(*head)结点（也就是第一个结点）开始时，第一个结点便不单单是指路的工具，它所携带的数据*(head->information)同样是俺们感兴趣的玩意。这便是不带头结点的单链表。

此时，最大的区别就体现在二者的长度计算上了，来，康些好康的方便理解：

由于两者在读取信息和计算长度上都有差异，所以添加一个私有成员bool with_head，以此判别是否带头结点！ 

那我们由此可以得出带头结点的构造是非参构造，因为此时head指向的结点的数据信息无关紧要不需要进行人为输入，直接申请一个新结点的空间即可。即:head = new node;

//不带参构造——带头结点的单链表
LinkList()
{
    head = new node;    
    with_head = true;
};

而当我们想要构造不带头结点的单链表时，我们就需要人为地输入一个带有所需信息的结点来初始化head，这便是带参构造（按道理以data作为初始化信息看上去更合理，但是我是懒鬼，所以我的源码里用的是以一个结点指针作为初始化参数的，欸嘿）

版本1——以node*为输入参数

//带参数构造——不带头结点的单链表
LinkList(node* x)
{
    head = x;
    with_head = false;
};

版本2——以datas*为输入参数

//带参数构造——不带头结点的单链表
LinkList(datas* x)
{
    head = new node; //建立一个孤立节点
    head->information = x; //将第一个节点的信息装进去
    with_head = false;
};

至此，我们的LinkList类已经初具其形啦！让我们来康康：

class LinkList
{
public:
	//无参构造，带头结点的链表
	LinkList()
	{
		head = new node;//给头结点分配内存
		with_head = true;
	};
 
	//带参构造，无头结点的链表
	LinkList(node* x)
	{
 
		head = x;
		with_head = false;//不带头结点
 
	};
 
private:
	node* head;//头节点指针
	bool with_head;
};

1.1.5编写析构函数（必写）

这是很重要很重要的一步！！！你可能会纳闷在前面构造线性表类SeqList都没提什么析构函数，怎么这里却突然冒出来一个析构函数呢？

因为在编写链表时我们会用到大量的指针，包括在实现一些功能时常常会定义一个孤立节点并给它分配空间拿来使用，如果没有析构函数，这些给出去的内存空间就像嫁出去的媳妇、泼出去的水，不及时清理这些指针就会导致内存泄露！！！

所以我们在析构函数中就一个目的，清除链表中占用的空间，也就是清空链表！由此可见清空链表是一个很重要的功能，我们必须要实现这一功能，假如我们已经通过函数void makeEmpty()实现了这一功能（具体实现见下文），那么析构函数就很好办了：

//析构函数（用于释放内存，防止内存泄露）
~LinkList()
{
	makeEmpty();
}

1.2空链表及链表的判空条件

怎样是一个空的链表呢？由于链表的必备元素就一结点指针head，那我们只能由head下手并从此判断，这时细心的你应该注意到了在上文中说过带头结点和不带头结点的单链表在计数上是有差异的，那么自然对于二者的判空也有差异。

什么是空链表呢，咱就是说在这个链表里没有一个结点包含咱想要的信息，这样的链表就叫空链表。

先考虑一手带头结点的链表何时为空：由于带头结点的信息存储是从头结点的下一个结点开始的，那么当头结点的下一个结点不存在时，就称此时的带头结点的链表为空。即：head->next==NULL时为空！

再考虑一手不带头结点的链表何时为空：由于不带头结点的信息存储是从head所指向的结点开始的，那么当head所指向的结点不存在时，就称此时的带头结点的链表为空。即：head==NULL时为空！

也即判空条件可用一个三目运算符表示：(with_head)?head->next==NULL:head==NULL;

于是我们得到了判空函数isEmpty()

bool isEmpty()
{
	return (with_head) ? head->next == NULL : head == NULL;
}

2.基础功能实现

2.1返回头指针

node* get_head()
{
    return head;
}

2.2返回with_head值（用以外部判断带不带头结点）

bool withHead()
{
    return with_head;
}

2.3返回尾指针

这个实现很容易，但是很实用。尾指针也就是单链表末尾的指针，那不管单链表带不带头结点，它的尾结点均满足一个条件——其所指的下一个结点不存在，也就是node->next==NULL，而这一个结点指针node就是我们要找的尾指针。

再考虑一个特殊情况——当链表尾空，它没有任何连接的结点，那尾结点都不存在何谈尾指针，所以空表时直接返回NULL。

不空的时候我们怎么来找到尾结点呢，我们定义一个结点指针p让它等于head，随后利用while循环只要p不是尾指针（也就是p->next不是NULL），那么p就一直下移，即：p = p->next。

这么一来我们就得到了尾指针的返回函数:

node* last()
{
 
    if (isEmpty())
    {
        return NULL;
    }
 
    node* p = head;
    while ( p->next != NULL )
    {
        p = p->next;
    }
    return p;
 
}

2.4清空链表

想要清空一个链表那么就让它变成空表就好了，先考虑带头结点的情况，此时只需最后使得head->next= NULL并且所有数据节点占用的空间得到释放。

这里注意要让所有数据结点占用的空间得到释放，而遍历链表是从头开始一个一个遍历的，那么想要释放数据结点的空间也就只好一个一个释放过去。

这里我们将清空链表分为4步：

1.建立一个新结点指针p

2.如果head->next != NULL，则将head->next指向下下个

(第二步的实现方法为先用p指向待删结点，也就是p = head->next;然后再将第一个结点与待删节点的下一个结点进行连接，即：head->next = p->next;)

3.释放p的空间

4.重复2、3步直到head->next == NULL（也即此时该带头结点的链表为空）

具体如下图所示：

好了到这里我们就获得了一个清空带头结点的清空函数：

void makeEmpty()
{
 
    node* p;
    while (head->next != NULL)
    {
        p = head->next;
        head->next = p->next;
        delete p;
    }
 
}

那么如果不带头结点怎么办呢，通过上图可以发现删除完之后head所指向的头结点是被保留了的，也就是说当链表不带头结点，我们还要手动删除掉head指向的结点（也就是第一个节点）

即if (!with_head)        head = NULL;

于是，我们得到了完整的makeEmpty()函数：

void makeEmpty()
{
 
    node* p;
    while (head->next != NULL)
    {
        p = head->next;
        head->next = p->next;
        delete p;
    }
 
 
    if (!with_head)
        head = NULL;
}

哈哈哈，写着写着突然清空时发现忽略了一种异常情况——所需清空的已经是空表了，此时应当抛错或者直接return，我比较喜欢抛错。

void makeEmpty()
{
 
    if (isEmpty())
    {
        cout << "空的不能再空啦！" << endl;
        throw 1;
        return;
    }
 
    node* p;
    while (head->next != NULL)
    {
        p = head->next;
        head->next = p->next;
        delete p;
    }
 
 
    if (!with_head)
        head = NULL;
}

2.5链表的长度获取

获取长度的原理十分简单，就是从第一个数据结点开始一直往后遍历，同时记录次数，最后返回次数即可。当然，空表的长度为0，这个情况单独拎出来考虑即可。

关键在第一个数据结点的指针是head还是head->next呢？这时候用三目运算符就好啦，如果是带头结点的那么信息存储结点显然是从head->next开始的，于是得到:

node*p = (with_head) ? head->next : head;

p就是我们遍历的起始指针啦，结束标志自然是当p为尾结点的时候，也就是说初始操作次数初始化为1，因为如果p就是尾结点，那么显然链表长度为1且此时进不了循环。

于是我们得到了长度获取函数length()

int length()
{
    if (isEmpty())
        return 0;
    
    node*p = (with_head) ? head->next : head;
    int count = 1;
    while ( p->next != NULL )
    {
        p = p->next;
        count++;
    }
    return count;
}

2.6输入数据构造链表

这里的构成方法分为两种，一种是前插法，另一种是尾插法。

前插法是指每一个输入数据形成的新节点总是插入在head所指的结点之后。

尾插法是指每一个输入数据形成的新节点总是插在尾结点之后。（这就是为啥要写个last()函数）

那么先来思考一下输入的问题，由于我预先不知道用户需要输入多少个数据，所以我们采用while输入，那么这时候就需要一个结束标志，我们定义一个datas endTag = { 0, "结束" }，也就是当用户输入的数字信息为0并且文字信息为"结束"时我们才结束输入的过程。

注意考虑一个特殊情况，如果用户手贱点开输入，为了退出而直接输入结束标志，此时直接return出去就好了。

void input(datas endTag={ 0, "结束" }, bool front=true)
{
 
	datas new_data; //用来存储输入的数据
    
    cout << "请输入第一个数据：";
	cin >> new_data.num;
	cin >> new_data.intro;
 
	//直接输入结束符直接开溜
	if ((new_data.num == endTag.num) && (new_data.intro == endTag.intro))
	{
		return;
	}
 
	//不满足结束标志则持续输入
	while ((new_data.num != endTag.num) || (new_data.intro != endTag.intro))
	{
		cout << "请输入数据：";
		cin >> new_data.num;
		cin >> new_data.intro;
	}
 
 
}

接着考虑插入问题：由于输入的是datas数据，我们还要将之打包成一个新的结点

构造新节点&保存数据:

node* p = new node; //为新插入的结点申请内存
p->information->num = new_data.num;
p->information->intro = new_data.intro;

前插法： 

将新节点插入头结点后，此时为了保留原本的表链，需要先将新节点的next指向head->next，再将head->next指向新节点。即：

p->next = head->next;
head->next = p;

后插法：

后插法最简单，直接将尾指针的next指向新节点即可：last()->next = p;

这里巧妙在p是无参构造的node，它的next原本就是NULL，恰好与尾结点的定义不谋而合

last()->next = p;

于是咱们就得到了完整的输入函数input()

void input(datas endTag={ 0, "结束" }, bool front=true)
{
 
	//为新元素申请结点
	node* p;
 
	datas* new_data = new datas;
 
	if (front)//前插法构造链表
	{
		cout << "请输入第一个数据：";
		cin >> new_data->num;
		cin >> new_data->intro;
 
		//直接输入结束符，立刻开溜
		if ((new_data->num == endTag.num) && (new_data->intro == endTag.intro))
		{
			return;
		}
 
		//不满足结束标志则持续输入
		while ((new_data->num != endTag.num) || (new_data->intro != endTag.intro))
		{
			p = new node;//为新结点申请空间
			p->information->num = new_data->num;
			p->information->intro = new_data->intro;
			if (head->next != NULL)
			{
				p->next = head->next;
			}
			head->next = p;
			cout << "请输入数据：";
			cin >> new_data->num;
			cin >> new_data->intro;
		}
	
	}
 
	else//尾插法构造链表
	{
 
		cout << "请输入第一个数据：";
		cin >> new_data->num;
		cin >> new_data->intro;
 
		if ((new_data->num == endTag.num) && (new_data->intro == endTag.intro))
		{
			return;
		}
 
 
		//不满足结束标志则持续输入
		while ((new_data->num != endTag.num) || (new_data->intro != endTag.intro))
		{
			p = new node;//为新结点申请空间
			p->information->num = new_data->num;
			p->information->intro = new_data->intro;
			last()->next = p;
			cout << "请输入数据：";
			cin >> new_data->num;
			cin >> new_data->intro;
		}
 
	}
 
}

2.7输出链表

输出一个链表很容易，只要从第一个存有所需信息的结点开始一直遍历并输出下去即可。

但是要注意一个异常，如果为空链表，你可以选择抛错说“空链表无法输出”，也可以输出个“空空如也”啥的，看你自己乐意哪种，我个人倾向于抛错。

只需要注意一点就是开始遍历的结点p应该等于(with_head) ? head->next : head，因为带不带头结点关乎第一个存储信息的结点的位置！

还有一件事！注意这里不是遍历到尾结点就可以跑路的！！！

因为尾结点是含有信息的，所以也要输出，所以结束输出的条件为p == NULL

void output()
{
 
	if (isEmpty())
	{
		cout << "空链表无法输出!" << endl;
		throw 1;
        return;
	}
 
    node* p = (with_head) ? head->next : head;
 
	//带头结点的链表信息输出
	if (with_head)
	{
		p->information = head->next->information;
		int count = 1;
		while (p != NULL)
		{
 
			cout << "第" << count << "个结点数据信息如下:" << endl;
			cout << "数字为：" << p->information->num << endl;
			cout << "信息为：" << p->information->intro << endl;
 
			count++;
			p = p->next;
 
		}
	}
	//不带头结点的链表信息输出
	else
	{
		//将初始数据输出
		cout << "第1" << "个结点数据信息如下:" << endl;
		cout << "数字为：" << head->information->num << endl;
		cout << "信息为：" << head->information->intro << endl;
		p->information = head->next->information;
		int count = 1;
		while (p != NULL)
		{
 
			cout << "第" << count+1 << "个结点数据信息如下:" << endl;
			cout << "数字为：" << p->information->num << endl;
			cout << "信息为：" << p->information->intro << endl;
 
			count++;
			p = p->next;
 
		}
	}
 
}

3.更多有意思的方法实现

3.1按位查找结点（返回第i个结点的结点指针）

上面实现了一些基操，那么下面再来实现一些有趣的方法，按位查找首当其冲嗷！这个操作很简单，通过上面的方法实现，相信你已经熟练掌握了如何遍历一个链表，那只要在遍历的时候一遍遍历一遍数数，数到i的时候就直接return p;

在开写之前还是先考虑一手异常情况，当i<=0的时候是死都找不到的，直接回NULL（i=0的时候带头结点的可以找到头结点但这没意义所以一并当作异常处理掉！）

于是我们得到了如下代码：

//检查无误！
node* locate(int i)
{
	
	//i<=0回空指针
	if (i <= 0)
	{
		return NULL;
	}
 
	node* current = head;//当前所在结点指针
	int k = (with_head) ? 0 : 1;//计数
	while (current != NULL && k < i)
	{
		current = current->next;
		k++;
	}
	return current;
 
}

3.2按值查找（返回其所在结点是第几个）

按位和按值总是被一起提及，那我们也不能棒打鸳鸯，既然写了按位查找，就再写一个按值查找吧！

首先考虑一手异常情况

1.空表，没东西给你找

2.要找的数据压根找不到，返回-1（效仿py哈哈哈）

然后寻找所用的结点指针p初始化时要考虑带不带头结点（用那个三目运算符，老生常谈了属于是）

所以逻辑顺序是

处理异常->找找找（找到了立刻return然后开溜）->找不到（回-1）

int find(datas& x)
{
 
	node* p = (with_head) ? head->next : head;
	int i = 1;
 
	if (isEmpty())
	{
		cout << "无数据可供查找！" << endl;
		throw 2;
	}
 
	while ((p->information->num != x.num) || (p->information->intro != x.intro))
	{
		if (p->next == NULL)
			break;
		p = p->next;
		i++;
	}
	if ((p->information->num == x.num) && (p->information->intro == x.intro))
	{
		return i;
	}
	
	//找不到
	return -1;
 
}

3.3保存第k个结点的信息（需要提供一个datas结构体来存储）

首先看到第k个，马上想到异常——空表和当k溢出范围，即当k不属于区间[1,length]

那如果k合法且表不空呢？该如何存储数据呢？

很简单嘛，用3.1实现的locate方法，locate(i)返回的是第i个结点的地址信息那我们通过对它所指向的结构体指针infromation取个址就得到了所需数据datas啦！

于是得到下面的代码：

void save_data(int k, datas& saved)
{
 
	if (isEmpty())
	{
		cout << "鬼！这里没东西可存！" << endl;
		throw 1;
        return;
	}
 
	else if (k < 0 || k > length())
	{
		cout << "所给下标溢出范围" << endl;
		throw 2;
        return;
	}
 
	else
	{
        saved = *(locate(k)->information);
	}
 
}

3.4按位删除结点

接下来实现一手按位删除元素的操作，还记得之前写清空链表时的操作嘛？要删掉一个结点很简单，找到它上一个结点并将他先连接到下下个结点，再杀掉当前的待删结点。

而待删结点前一个结点怎么获得呢？欸嘿，直接locate(k-1)

异常处理和按位寻找一样，所以直接上代码：

datas remove(int k)
{
    //异常处理
    if(k<1 || k>length())
    {
        cout << "下标不合法！" << endl;
        throw 1;
    }
    if (isEmpty())
	{
		cout << "所要移去的结点为空结点" << endl;
		throw 1;
	}
	node* p = locate(k - 1);
	node* del = p->next; //被删除的结点的指针
	p->next = del->next;
	datas* save = new datas;
	save->num = del->information->num;
	save->intro = del->information->intro;
	delete del;
 
	return *save;
}

3.5按值删除

按值删除只需要先处理异常，然后通过前面实现的find方法获取待删下标，再按位删除就好啦！

代码如下：

datas remove_num(int num)
{
    if(isEmpty())
    {
        cout << "空表无法进行remove操作" << endl;
        throw 1;
    }
    int index = find(num);
    
    if (index == -1)
    {
        return;
    }
    
    return remove(index);
} 

3.6翻转链表

想要翻转一个链表可以怎么做捏？我想到的方法是：

1.先把尾结点挪到第一个数据结点前，并记录这个被挪动的结点指针end

2.不断将尾结点挪动到end所指的结点上，并刷新end

3.重复第二步直到第一个数据点的next指向NULL

具体如下图：

 上图考虑的是带头结点的情况，此时不难发现只要将head->next指向end就完成了翻转

那么如果不带头结点呢？那只要把head指向end就好了，因为end指向的是翻转后的第一个数据结点。

于是我们得到了如下代码：

//翻转链表
void reverse()
{
 
	if (isEmpty())
	{
 
		cout << "空表无法反转！" << endl;
		throw 1;
		return;
 
	}
 
	node* start = (withHead()) ? head->next : head;
	node* end = last();
	node* pre = start;
	//翻转
	while (start->next != NULL)
	{
		//暂时储存下一节点的next信息
		node* temp = start->next->next;
		//下一节点的next接到前一结点
		start->next->next = pre;
		//储存前一结点信息以便下一次拼接
		pre = start->next;
		//当前结点的next后跳一位
		start->next = temp;
 
	}
 
	//重新赋值head
	if (withHead())
	{
		//有头指针时，反转后将头结点指向end
		head->next = end;
	}
	else
	{
		//无头指针时，翻转后只需要把end赋给head
		head = end;
	}
 
}

4.插值

因为插值是我作业的重点任务，所以单独拎出来说说，而且链表的插值还要判别下单调性啥的，还蛮有意思。

4.1按位插入

到了这个地步，按位插入拆分成按位和插入的话只需要解决后者了，因为找到该插入的结点可以直接locate一手，欸嘿！

那我们只要明确一下插入的逻辑，想将datas的数据插入第k个结点，那也就是相当于原来的第k-1个结点要与新结点连接并且新节点的next指向原第k个结点。

封装成新节点十分简单：

node* p = new node;
*(p->information) = ins_data;//ins_data为输入的要插入的数据

如果新节点指针为p，那么上述逻辑写成代码就是：

node* current = locate(k-1);
p->next = current->next;
current->next = p;

 于是我们得到了按位插入方法：

void insert(datas ins_data, int k)
{
	node* current = locate(k - 1);
	node* p = new node;//插入结点
	//将插入数据放入插入节点
	p->information->intro = ins_data.intro;
	p->information->num = ins_data.num;
 
	//插入结点
	p->next = current->next;
	current->next = p;
}

4.2单调性判别

看着这个标题直接梦回大一学高数那会哈哈！在线性表那我有说过按值插入的前提是序列有序，那么在进行按值插入前我们就得先完成一个用来甄别链表是否具有有序性的方法。

首先确定函数类型，由于单调性有三种情况——1.无单调性2.递增3.递减

所以简单的bool型已经无法满足我们的需求，所以我选择采用整形，返回值为0代表无单调性，1代表递增，2代表递减。

首先考虑特殊情况——1.空表（无单调性）2.长度为1的链表（这个情况的处理我直接当成递增了）

于是得到以下代码：

if (isEmpty())
{
	cout << "空表无单调性！" << endl;
	return 0;
}
 
if (length() == 1)
{
	return 1;
}

接着来做初始化，有两个东西得初始化，第一个自然是老生常谈的结点指针p，因为判断单调性从有数据的结点开始就好了所以node* p = (with_head) ? head->next : head;

第二个则是判断一开始的单调性（通过判断第一个和第二个的大小来获得初始单调性）

int sign = (p->information->num < p->next->information->num) ? 1 : 2;//1增2减

接着便是遍历链表，看之后的大小关系是否会打脸sign初始值，即如果第一个节点的num比第二个的大，那初始单调性是递增，如果后来出现一个结点的num值反倒小于后一个结点的num则属于是打脸了，一打脸就代表该链表没得单调性，直接return 0;

//判断是否具有单调性
switch (sign)
{
case 1://递增
	while (p->next != NULL)
	{
		if (p->information->num > p->next->information->num)
		{
			return 0;
		}
		p = p->next;
	}
	return 1;
	break;
case 2://递减
	while (p->next != NULL)
	{
		if (p->information->num < p->next->information->num)
		{
			return 0;
		}
		p = p->next;
	}
	return 2;
	break;
default:
	return 0;
	break;
}

至此我们便获得了一个用于判断单调性的函数：

int single()
{
 
	if (isEmpty())
	{
		cout << "空表无单调性！" << endl;
		return 0;
	}
 
	node* p = (withHead()) ? head->next : head;
	if (length() == 1)
	{
		return 1;
	}
	int sign = (p->information->num < p->next->information->num) ? 1 : 2;//1增2减
	
	//判断是否具有单调性
	switch (sign)
	{
	case 1://递增
		while (p->next != NULL)
		{
			if (p->information->num > p->next->information->num)
			{
				return 0;
			}
			p = p->next;
		}
		return 1;
		break;
	case 2://递减
		while (p->next != NULL)
		{
			if (p->information->num < p->next->information->num)
			{
				return 0;
			}
			p = p->next;
		}
		return 2;
		break;
	default:
		return 0;
		break;
	}
}

4.3按值插入

有了上述两个方法就很好办啦！逻辑也很简单：

先判断该链表有没有单调性，没有的话没法按值插入

有单调性则先比较两头，比较一头一尾，因为按位插入基于locate方法，所以没法将待插结点变成头或尾。

所以对先将一头一尾与待插数据进行大小比较，插头插尾拎出来考虑。

该插入的地方既不在头也不在尾则遍历链表寻找合适的index，这里注意如果待插结点在第i个结点和第i+1个结点符合递变规律，那么应该让它成为新的第i+1个结点，即insert(ins_data, index+1)

于是我们得到了按值插入函数:

void insert(datas ins_data)
{
	//初始化为第一个有信息结点用来判断特殊情况
	node* p = (withHead()) ? head->next : head;
	int index = 1;//当前处于第一个结点
	switch (single())
	{
	case 0://无序时抛错
		cout << "该链表数字排列无序，无法按值插入！" << endl;
		throw 1;
		return;
		break;
	case 1://递增排列
		//比第一个还小就插在第一个
		if (ins_data.num <= p->information->num)
		{
			insert(ins_data, 1);
		}
		//比最后一个还大就插在尾
		else if (ins_data.num >= last()->information->num)
		{
			node* ins_node = new node;
			//插入值赋给插入节点
			*(ins_node->information) = ins_data;
			last()->next = ins_node;//插入尾结点后
		}
		//不然就寻找合适的位置下标index
		else
		{
			while (1)
			{
				if (ins_data.num >= p->information->num && //比这一个大
					ins_data.num <= p->next->information->num)//比下一个小
				{
					insert(ins_data, index + 1);
					break;
				}//循环边界，当ins_data.num在第index和第index+1数据之间则插成第index+1个
				p = p->next;
				index++;
			}
		}
		break;
	case 2://递减排列
		//比第一个还大就插在第一个
		if (ins_data.num >= p->information->num)
		{
			insert(ins_data, 1);
		}
		//比最后一个还小就插在尾
		else if (ins_data.num <= last()->information->num)
		{
			node* ins_node = new node;
			//插入值赋给插入节点
			*(ins_node->information) = ins_data;
			last()->next = ins_node;//插入尾结点后
		}
		//不然就寻找合适的位置下标index
		else
		{
			while (1)
			{
				if (ins_data.num <= p->information->num && //比这一个小
					ins_data.num >= p->next->information->num)//比下一个大
				{
					insert(ins_data, index + 1);
					break;
				}//循环边界，当ins_data.num在第index和第index+1数据之间则插成第index+1个
				p = p->next;
				index++;
			}
		}
		break;
		break;
	default:
		break;
	}
 
}

4.4改进按位插入

通过4.3发现之前的按位插入漏掉了一头一尾两种情况

如果要插入最头上还应分成是否带有头结点来考虑，即：

if (k == 1)//要插成第一个
{
	if (with_head)
	{
		p->next = head->next;
		head->next = p;
	}
 
	else
	{
		p->next = head;
		head = p;
	}
}

插成尾就比较简单，直接:

last()->next = p;

即可，所以改进后的按位插入函数为：

void insert(datas ins_data, int k)
{
	node* p = new node;//插入结点
	//将插入数据放入插入节点
	p->information->intro = ins_data.intro;
	p->information->num = ins_data.num;
 
	if (k == 1)//要插成第一个
	{
		if (with_head)
		{
			p->next = head->next;
			head->next = p;
		}
 
		else
		{
			p->next = head;
			head = p;
		}
	}
 
	else if (k == length() + 1)//代表成为新尾结点
	{
		last()->next = p;
	}
 
	node* current = locate(k - 1);
 
	//插入结点
	p->next = current->next;
	current->next = p;
}

5.一些测试函数（自己调试的时候写的）

5.1方法函数测试

void Func_test()
{
	LinkList L1;
	L1.input();
	L1.output();
	cout << L1.isEmpty() << endl;
	cout << L1.length() << endl;
	datas d = { 2, "b" };
	cout << L1.find(d) << endl;
	if (L1.locate(L1.find(d))->information->num == 2)
	{
		cout << "locate函数检查无误！" << endl;
	}
	else
	{
		cout << "locate函数有误！" << endl;
	}
	cout << "尾部数字为：" << L1.last()->information->num << endl;
 
	//检查单调性
	if (L1.single() == 0)
	{
		cout << "无单调性" << endl;
	}
	else
	{
		string dd_str = (L1.single() == 1) ? "递增" : "递减";
		cout << dd_str << endl;
	}
 
	//检查按值插入
	datas insert_data = { 2, "被按值插入的数字" };
	L1.insert(insert_data, L1.withHead());
	L1.output();
 
	//检查按位插入
	insert_data = { 0, "被按位插入的数字" };
	L1.insert(insert_data, 1);
	L1.output();
 
	//检查remove
	datas rem, temp;//用来储存被删除的结点信息
	int length = L1.length();
	temp = *(L1.locate(1)->information);
	rem = L1.remove(1);
	int length_ = L1.length();
	if (length_ == length - 1 && rem.num == temp.num && rem.intro == temp.intro)
	{
		cout << "remove函数检查无误！" << endl;
	}
	else
	{
		cout << "remove函数出问题咯！" << endl;
	}
 
	//翻转
	L1.reverse();
	L1.output();
 
	//检查makeEmpty
	L1.makeEmpty();
	string mE_ass_err = (L1.length() == 0) ? "makeEmpty函数正确无误！" : 
		"makeEmpty函数有问题";
	cout << mE_ass_err << endl;
 
}

5.2带头结点链表测试

void head_display()
{
	LinkList L1;
	L1.input();
	L1.output();
	cout << L1.isEmpty() << endl;
	cout << L1.length() << endl;
	datas d = { 2, "b" };
	cout << L1.find(d) << endl;
	if (L1.locate(L1.find(d))->information->num == 2)
	{
		cout << "locate函数检查无误！" << endl;
	}
	else
	{
		cout << "locate函数有误！" << endl;
	}
	cout << "尾部数字为：" << L1.last()->information->num << endl;
 
	//检查单调性
	if (L1.single() == 0)
	{
		cout << "无单调性" << endl;
	}
	else
	{
		string dd_str = (L1.single() == 1) ? "递增" : "递减";
		cout << dd_str << endl;
	}
 
	//检查按值插入
	datas insert_data = { 30, "被插入的数字" };
	L1.insert(insert_data);
	L1.output();
 
	//检查按位插入
	insert_data = { 2, "被插入的数字" };
	L1.insert(insert_data, 1);
	L1.output();
 
	//检查save_data
	datas save_data;
	L1.save_data(3, save_data);
	cout << "--------被保存的是第三个结点，信息如下----------" << endl;
	cout << "num：" << save_data.num << endl;
	cout << "intro：" << save_data.intro << endl;
 
	datas remove_data = L1.remove(2);
	L1.output();
	cout << "------被删除的结点信息如下--------" << endl;
	cout << "num：" << remove_data.num << endl;
	cout << "intro：" << remove_data.intro << endl;
 
	//翻转演示
	L1.reverse();
	cout << "------翻转后的链表信息如下--------" << endl;
	L1.output();
 
	//清空检查
	L1.makeEmpty();
	cout << "清空后链表长度为：" << L1.length() << endl;
 
}

5.3不带头结点链表测试

void nohead_display()
{
	datas* init_data = new datas;
	*init_data = { 0, "初始结点" };
	node* init_node = new node;
	init_node->information = init_data;
 
	//构造无头结点的链表
	LinkList L1(init_node);
	L1.input();
	L1.output();
	cout << "第2个结点数字为" << L1.locate(2)->information->num << endl;
 
	cout << "------长度如下------" << endl;
	cout << L1.length() << endl;
 
	//按位插值检验
	datas ins_data = { 10, "被插入的结点" };
	L1.insert(ins_data, 2);
	L1.output();
 
	//按位删除检查
	datas remove_data = L1.remove(2);
	L1.output();
	cout << "------被删除的结点信息如下--------" << endl;
	cout << "num：" << remove_data.num << endl;
	cout << "intro：" << remove_data.intro << endl;
 
	//单调性检查
	if (L1.single() == 0)
	{
		cout << "无单调性" << endl;
	}
	else
	{
		string ddx = (L1.single() == 1) ? "递增" : "递减";
		cout << ddx << endl;
	}
 
	//按值插入检查
	ins_data = { 15, "被插入的结点" };
	L1.insert(ins_data, L1.withHead());
	L1.output();
 
	//翻转演示
	L1.reverse();
	cout << "------翻转后的链表信息如下--------" << endl;
	L1.output();
 
}

6.LinkList类整合

class LinkList
{
public:
	//无参构造，带头结点的链表
	LinkList()
	{
		head = new node;//给头结点分配内存
		with_head = true;
	};
 
	//带参构造，无头结点的链表
	LinkList(node* x)
	{
 
		head = x;
		with_head = false;//不带头结点
 
	};
 
    //析构函数（用于释放内存，防止内存泄露）
    ~LinkList()
    {
	    makeEmpty();
    }
 
    bool isEmpty()
    {
	    return (with_head) ? head->next == NULL : head == NULL;
    }
 
    node* get_head()
    {
        return head;
    }
    
    bool withHead()
    {
        return with_head;
    }
 
    node* last()
    {
 
        if (isEmpty())
        {
            return NULL;
        }
 
        node* p = head;
        while ( p->next != NULL )
        {
            p = p->next;
        }
        return p;
 
    }
    
    void makeEmpty()
    {
 
        if (isEmpty())
        {
            cout << "空的不能再空啦！" << endl;
            throw 1;
            return;
        }
 
        node* p;
        while (head->next != NULL)
        {
            p = head->next;
            head->next = p->next;
            delete p;
        }
 
 
        if (!with_head)
            head = NULL;
    }
 
    int length()
    {
        if (isEmpty())
            return 0;
    
        node*p = (with_head) ? head->next : head;
        int count = 1;
        while ( p->next != NULL )
        {
            p = p->next;
            count++;
        }
        return count;
    }    
 
    void input(datas endTag={ 0, "结束" }, bool front=true)
    {
 
	    //为新元素申请结点
	    node* p;
 
	    datas* new_data = new datas;
 
	    if (front)//前插法构造链表
    	{
	    	cout << "请输入第一个数据：";
	    	cin >> new_data->num;
	    	cin >> new_data->intro;
 
		    //直接输入结束符，立刻开溜
		    if ((new_data->num == endTag.num) && (new_data->intro == endTag.intro))
		    {
		    	return;
		    }
 
		    //不满足结束标志则持续输入
		    while ((new_data->num != endTag.num) || (new_data->intro != endTag.intro))
		    {
		    	p = new node;//为新结点申请空间
		    	p->information->num = new_data->num;
		    	p->information->intro = new_data->intro;
		    	if (head->next != NULL)
		    	{
		    		p->next = head->next;
		    	}
		    	head->next = p;
		    	cout << "请输入数据：";
		    	cin >> new_data->num;
		    	cin >> new_data->intro;
		    }
	
	    }
 
	    else//尾插法构造链表
	    {
 
		    cout << "请输入第一个数据：";
		    cin >> new_data->num;
		    cin >> new_data->intro;
 
		    if ((new_data->num == endTag.num) && (new_data->intro == endTag.intro))
		    {
		    	return;
		    }
 
 
		    //不满足结束标志则持续输入
		    while ((new_data->num != endTag.num) || (new_data->intro != endTag.intro))
		    {
			    p = new node;//为新结点申请空间
			    p->information->num = new_data->num;
			    p->information->intro = new_data->intro;
			    last()->next = p;
			    cout << "请输入数据：";
		       	cin >> new_data->num;
		    	cin >> new_data->intro;
		    }
 
	    }
 
    }
 
    void output()
    {
 
	    if (isEmpty())
	    {
	    	cout << "空链表无法输出!" << endl;
	    	throw 1;
            return;
	    }
 
        node* p = (with_head) ? head->next : head;
 
	    //带头结点的链表信息输出
	    if (with_head)
	    {
		    p->information = head->next->information;
		    int count = 1;
		    while (p != NULL)
		    {
 
			    cout << "第" << count << "个结点数据信息如下:" << endl;
			    cout << "数字为：" << p->information->num << endl;
			    cout << "信息为：" << p->information->intro << endl;
 
		    	count++;
		    	p = p->next;
    
	        }
    	}
	    //不带头结点的链表信息输出
	    else
    	{
		    //将初始数据输出
		    cout << "第1" << "个结点数据信息如下:" << endl;
		    cout << "数字为：" << head->information->num << endl;
		    cout << "信息为：" << head->information->intro << endl;
		    p->information = head->next->information;
		    int count = 1;
		    while (p != NULL)
		    {
 
			    cout << "第" << count+1 << "个结点数据信息如下:" << endl;
			    cout << "数字为：" << p->information->num << endl;
			    cout << "信息为：" << p->information->intro << endl;
 
		    	count++;
		    	p = p->next;
 
		    }
	    }
 
    }
 
    //检查无误！
    node* locate(int i)
    {
	
	    //i<=0回空指针
	    if (i <= 0)
	    {
	    	return NULL;
	    }
 
	    node* current = head;//当前所在结点指针
	    int k = (with_head) ? 0 : 1;//计数
	    while (current != NULL && k < i)
	    {
	    	current = current->next;
	    	k++;
	    }
	    return current;
 
    }
 
    int find(datas& x)
    {
 
	    node* p = (with_head) ? head->next : head;
	    int i = 1;
 
	    if (isEmpty())
	    {
	    	cout << "无数据可供查找！" << endl;
	    	throw 2;
	    }
 
	    while ((p->information->num != x.num) || (p->information->intro != x.intro))
	    {
		    if (p->next == NULL)
		    	break;
		    p = p->next;
	    	i++;
	    }
	    if ((p->information->num == x.num) && (p->information->intro == x.intro))
	    {
	        return i;
	    }
	
	    //找不到
	    return -1;
 
    }
 
    void save_data(int k, datas& saved)
    {
 
	    if (isEmpty())
	    {
	    	cout << "鬼！这里没东西可存！" << endl;
	    	throw 1;
            return;
	    }
    
	    else if (k < 0 || k > length())
	    {
		    cout << "所给下标溢出范围" << endl;
	    	throw 2;
            return;
	    }
    
	    else
	    {
            saved = *(locate(k)->information);
	    }
 
    }
 
    datas remove(int k)
    {
        //异常处理
        if(k<1 || k>length())
        {
            cout << "下标不合法！" << endl;
            throw 1;
        }
        if (isEmpty())
	    {
	    	cout << "所要移去的结点为空结点" << endl;
	    	throw 1;
	    }
	    node* p = locate(k - 1);
	    node* del = p->next; //被删除的结点的指针
	    p->next = del->next;
	    datas* save = new datas;
	    save->num = del->information->num;
	    save->intro = del->information->intro;
	    delete del;
 
    	return *save;
    }
 
    datas remove_num(int num)
    {
        if(isEmpty())
        {
            cout << "空表无法进行remove操作" << endl;
            throw 1;
        }
        int index = find(num);
    
        if (index == -1)
        {
            return;
        }
    
        return remove(index);
    } 
 
    //翻转链表
    void reverse()
    {
 
	    if (isEmpty())
	    {
 
	    	cout << "空表无法反转！" << endl;
	    	throw 1;
	    	return;
 
	    }
 
	    node* start = (withHead()) ? head->next : head;
	    node* end = last();
	    node* pre = start;
	    //翻转
	    while (start->next != NULL)
	    {
		    //暂时储存下一节点的next信息
		    node* temp = start->next->next;
		    //下一节点的next接到前一结点
	    	start->next->next = pre;
	    	//储存前一结点信息以便下一次拼接
	    	pre = start->next;
		    //当前结点的next后跳一位
	    	start->next = temp;
 
	    }
 
	    //重新赋值head
	    if (withHead())
	    {
	    	//有头指针时，反转后将头结点指向end
	    	head->next = end;
	    }
	    else
	    {
	    	//无头指针时，翻转后只需要把end赋给head
	    	head = end;
	    }
 
    }
 
    int single()
    {
 
	    if (isEmpty())
	    {
	    	cout << "空表无单调性！" << endl;
	    	return 0;
	    }
 
	    node* p = (withHead()) ? head->next : head;
	    if (length() == 1)
	    {
		    return 1;
	    }
	    int sign = (p->information->num < p->next->information->num) ? 1 : 2;//1增2减
	
	    //判断是否具有单调性
	    switch (sign)
	    {
	    case 1://递增
		    while (p->next != NULL)
	    	{
		    	if (p->information->num > p->next->information->num)
		    	{
		    		return 0;
		    	}
		    	p = p->next;
	    	}
	    	return 1;
	    	break;
	    case 2://递减
		    while (p->next != NULL)
		    {
		    	if (p->information->num < p->next->information->num)
			    {
			    	return 0;
		    	}
		    	p = p->next;
	    	}
	    	return 2;
	    	break;
	    default:
	    	return 0;
	    	break;
	    }
    }
 
    void insert(datas ins_data, int k)
    {
	    node* p = new node;//插入结点
	    //将插入数据放入插入节点
    	p->information->intro = ins_data.intro;
	    p->information->num = ins_data.num;
 
	    if (k == 1)//要插成第一个
    	{
		    if (with_head)
		    {
	    		p->next = head->next;
	    		head->next = p;
	    	}
 
	    	else
	    	{
	    		p->next = head;
	    		head = p;
	    	}
	    }
 
	    else if (k == length() + 1)//代表成为新尾结点
	    {
	    	last()->next = p;
	    }
    
	    node* current = locate(k - 1);
 
	    //插入结点
	    p->next = current->next;
	    current->next = p;
    }
 
    void insert(datas ins_data)
    {
	    //初始化为第一个有信息结点用来判断特殊情况
	    node* p = (withHead()) ? head->next : head;
	    int index = 1;//当前处于第一个结点
	    switch (single())
    	{
	    case 0://无序时抛错
	    	cout << "该链表数字排列无序，无法按值插入！" << endl;
	    	throw 1;
		    return;
		    break;
	    case 1://递增排列
	    	//比第一个还小就插在第一个
	    	if (ins_data.num <= p->information->num)
	    	{
		    	insert(ins_data, 1);
	    	}
		    //比最后一个还大就插在尾
		    else if (ins_data.num >= last()->information->num)
		    {
		    	node* ins_node = new node;
		    	//插入值赋给插入节点
		    	*(ins_node->information) = ins_data;
		    	last()->next = ins_node;//插入尾结点后
		    }
		    //不然就寻找合适的位置下标index
		    else
		    {
		    	while (1)
		    	{
			    	if (ins_data.num >= p->information->num && //比这一个大
				    	ins_data.num <= p->next->information->num)//比下一个小
			    	{
				    	insert(ins_data, index + 1);
				    	break;
				    }//循环边界，当ins_data.num在第index和第index+1数据之间则插成第index+1个
			    	p = p->next;
			    	index++;
		    	}
	    	}
		    break;
	    case 2://递减排列
		    //比第一个还大就插在第一个
	    	if (ins_data.num >= p->information->num)
	    	{
	    		insert(ins_data, 1);
		    }
		    //比最后一个还小就插在尾
		    else if (ins_data.num <= last()->information->num)
		    {
		    	node* ins_node = new node;
		    	//插入值赋给插入节点
		    	*(ins_node->information) = ins_data;
		    	last()->next = ins_node;//插入尾结点后
		    }
		    //不然就寻找合适的位置下标index
		    else
		    {
			    while (1)
			    {
				    if (ins_data.num <= p->information->num && //比这一个小
				    	ins_data.num >= p->next->information->num)//比下一个大
				    {
				    	insert(ins_data, index + 1);
				    	break;
				    }//循环边界，当ins_data.num在第index和第index+1数据之间则插成第index+1个
			    	p = p->next;
			    	index++;
			    }
	    	}
	    	break;
	    default:
	    	break;
    	}
 
    }
 
private:
	node* head;//头节点指针
	bool with_head;
};