Hello大家好！很高兴我们又见面啦！给生活添点passion，开始今天的编程之路！
我的博客：<但凡.
我的专栏：《数据结构与算法之美》、《编程之路》、《题海拾贝》
欢迎点赞，关注！
目录
1、使用C++实现单链表
虽然我还没说过C++，但是使用C++实现单链表的大体操作和步骤与C语言几乎没有区别，所以我们用C++实现一下单链表，为的是做我们的面向对象方式实现单链表。当然了，后面我可能会出一篇c到c++衔接的博客，大家也可以看完那个之后再回来看这个哈~
当然了，在实现单链表时有的c++的新增函数我会做出说明的，大家了解就行。
1.1节点的声明
typedef struct Node
{
int a;
Node* next;
}Node;1.2节点的初始化
咱们还是先来经典的初始化节点：
Node* BuyNode(int n)//初始化节点
{
Node* NewNode = new Node;
if (NewNode == NULL)
{
cout << "节点内存申请失败!" << endl;
return NULL;
}
NewNode->a = n;
NewNode->next = NULL;
return NewNode;
}其中，我们的cout<<是输出打印，我可以理解为printf(但是还是有区别的)，endl是换行（end line）。
new可以看成是C++版的malloc，new Node就是开辟一个Node类型的空间。
1.3头插和尾插
1.3.1头插
void TouCha(Node* & ph, int x)
{
Node* NewNode = BuyNode(x);
NewNode->next = ph;
ph = NewNode;
}我们这里使用&引用来取别名，当然了使用C语言里面的二级指针也是可以实现的，但是需要注意的是，如上代码我们传入的参数应该是Node*类型的，而二级指针我们应该传入&Node。（我也懒得整英文名了，还是直接拼音取名吧看着还舒服点，但是我们以后尽量还是英文取名，遵循取名习惯规则）。
1.3.2尾插
void WeiCha(Node*& ph, int x)
{
Node* NewNode = BuyNode(x);
Node* pcur = ph;
if (ph == NULL)//链表为空的情况
{
ph = NewNode;
}
else
{
while (pcur->next)//让pcur找到链表最后一个节点
{
pcur = pcur->next;
}
pcur->next = NewNode;
}
}1.4头删和尾删
1.4.1头删
void TouShan(Node*& ph)
{
if (ph == NULL)
{
cout << "无可删除元素" << endl;
}
Node* pcur = ph;
ph = ph->next;
delete pcur;
pcur = NULL;
}1.4.2尾删
void WeiShan(Node*& ph)
{
if (ph == NULL)
{
cout << "无可删除元素" << endl;
}
else if (ph->next == NULL)//表中就一个元素
{
TouShan(ph);//这时候头删尾删都一样，调用头删
}
else
{
Node* pcur = ph;
Node* pb = ph;//记录pcur的前一个节点
while (pcur->next)//让pcur找到最后一个节点
{
pb = pcur;
pcur = pcur->next;
}
delete pcur;
pcur = NULL;
pb->next = NULL;
}
}在删除操作中，C++提供了一个新的删除函数delete，他的用法和作用和free相似，当然我们这里用free也可以，但是new和delete是配对的，所以我们在这用的delete。
1.5打印链表
void Printlist(Node* ph)
{
while (ph->next)
{
cout << ph->a << "-->";
ph = ph->next;
}
cout << ph->a << endl;
}1.6测试
在这我们还是和上两篇一样，把函数封装成头文件，然后在主程序的源文件中包含这个头文件。
测试程序：
#include"FileName.h"
int main()
{
//初始化链表
Node* phead=BuyNode(1);//1
//节点的插入
TouCha(&phead,0);//0 1
WeiCha(phead, 2);//0 1 2
WeiCha(phead, 3);//0 1 2 3
WeiCha(phead, 4);//0 1 2 3 4
TouShan(phead);//1 2 3 4
WeiShan(phead);//1 2 3
Printlist(phead);
return 0;
}输出结果：
2、面向对象的方式实现单链表
2.1面向对象和面向过程
- 面向过程强调的是功能行为，以函数为最小单位，考虑怎么做。
- 面向对象，将功能封装进对象，强调具备了功能的对象，以类/对象为最小单位，考虑谁来做。
我们以上的单链表是以面向过程的方式实现的，而其实际上我们写的单链表大多是以面向对象的形式来实现的，现在我们对以上代码进行改造，使其以面向对象的形式展现出来。
2.2面向对象的方式实现单链表
在C++中，我们的结构体进行了升级，现在它可以包含成员函数，也就是说结构体的成员现在也可以是函数了。
此外，C++的结构体会有⼀些默认的成员函数，比如：构造函数、析构函数等。这些函数都是自动被调用，不需要手动调用。
现在我们先给大家把代码写出来，然后再进行讲解：
#define _CRT_SECURE_NO_WARNINGS 1
#pragma once
#include<iostream>
using namespace std;
typedef struct Node
{
int a;
Node* next;
}Node;
struct list
{
//初始化链表
Node* phead;
list()//构造函数
{
phead = BuyNode(1);
}
~list()
{
while (phead)
{
TouShan();
}
}
Node* BuyNode(int n)//初始化节点
{
Node* NewNode = new Node;
if (NewNode == NULL)
{
cout << "节点内存申请失败!" << endl;
return NULL;
}
NewNode->a = n;
NewNode->next = NULL;
return NewNode;
}
void TouCha(int x)
{
Node* NewNode = BuyNode(x);
NewNode->next = phead;
phead = NewNode;
}
void WeiCha(int x)
{
Node* NewNode = BuyNode(x);
Node* pcur = phead;
if (phead == NULL)//链表为空的情况
{
phead = NewNode;
}
else
{
while (pcur->next)//让pcur找到链表最后一个节点
{
pcur = pcur->next;
}
pcur->next = NewNode;
}
}
void WeiShan()
{
if (phead == NULL)
{
cout << "无可删除元素" << endl;
}
else if (phead->next == NULL)//表中就一个元素
{
TouShan();//这时候头删尾删都一样，调用头删
}
else
{
Node* pcur = phead;
Node* pb = phead;//记录pcur的前一个节点
while (pcur->next)//让pcur找到最后一个节点
{
pb = pcur;
pcur = pcur->next;
}
delete pcur;
pcur = NULL;
pb->next = NULL;
}
}
void TouShan()
{
if (phead == NULL)
{
cout << "无可删除元素" << endl;
}
else
{
Node* pcur = phead;
phead = phead->next;
delete pcur;
pcur = NULL;
}
}
void Printlist()
{
while (phead->next)
{
cout << phead->a << "-->";
phead = phead->next;
}
cout << phead->a << endl;
}
};
int main()
{
struct list list;
//节点的插入
list.TouCha(0);//0 1
list.WeiCha(2);//0 1 2
list.WeiCha(3);//0 1 2 3
list.WeiCha(4);//0 1 2 3 4
list.TouShan();//1 2 3 4
list.WeiShan();//1 2 3
list.Printlist();
return 0;
}
为了方便展示，我们把这些代码都放到一起了。
我们来说一下都做了哪些改动：
1、我们把前面写的所有代码都放到了struct list这个结构体的声明里面，让他们作为结构体的成员。
2、我们把所有函数的参数Node* ph都去掉了，并且把所有函数大括号里的ph都改成了phead。这样做是因为我们在list这个结构体里声明或者说创建了phead，那么我们直接对它进行更改就行，不用再传参了。
3、我们新建一个该结构体类型的变量取名为list，但需要注意的是，这样做的话我们在结构体中调用函数时不用带list.，但是在主函数中调用函数需要带list.。
4、我们创建了一个构造函数和一个析构函数。这两个函数会自动调用。我们在使用结构体中的函数之前自动调用构造函数，初始化phead，在完成使用完结构体中的函数后调用析构函数，删除这个链表中的每一个节点（这也是为什么我没写销毁链表这个函数的原因）。
输出结果：
3、静态链表实现
3.1动态实现链表和静态实现链表
我们上面写的代码就是动态实现链表，因为我们运用了new和delete，以及上两篇我们使用的malloc和free。这种实现方法的优点是空间可以由我们自由操作，不浪费空间，但缺点是耗时，而且不好写。
所以在算法竞赛中，我们更常用的是静态实现链表。我们直接开辟一个足够大的空间，就不用频繁的malloc和free占用时间了。
其实链表有很多种，如下图，组合起来一共可以有八种！但是他们的原理都是一样的。我们在这实现一个有头的，循环的链表。
3.2链表静态实现
3.2.1理解
这是链表的理解图，其中红色框框里存放的是节点的数据（我i们这里让节点等于下标），黑色框框里存放的是下一个节点的下标。需要注意的是，第七个节点存放我们第一个节点的下标，达到循环的效果。
3.2.2创建
//创建
int e[N], ne[N], h, id;
//e[N]存放元素，ne[N]存放下一个节点下标3.2.3头插
void TouCha(int x)//注意我们哨兵位是不动的
{
id++;
e[id] = x;
ne[id] = ne[h];
ne[h] = id;
}我们的id存放的是有效的数据个数，比方说我现在存放了2个数据，id就是2，同时最后一个数据的下标是2。
头插我们可以理解为我们先给有效数据id加加，然后再在这个有效数据的位置放上我们想要存放的数据，然后让下标为id的这个位置存放哨兵节点h指向的节点的坐标，再让哨兵位置存放的下标变成id。
3.2.3遍历打印链表
void print()
{
for (int i = ne[h];i;i = ne[i])
{
cout << e[i] << endl;
}
}当i等于0时停止打印。
3.2.4测试
#define _CRT_SECURE_NO_WARNINGS 1
#include<iostream>
using namespace std;
const int N = 1e5 + 10;//10的五次方加10
//创建
int e[N], ne[N], h, id;
//e[N]存放元素，ne[N]存放下一个节点下标
void TouCha(int x)//注意我们哨兵位是不动的
{
id++;
e[id] = x;
ne[id] = ne[h];
ne[h] = id;
}
void print()
{
for (int i = ne[h];i;i = ne[i])
{
cout << e[i] << endl;
}
}
int main()
{
TouCha(1);
TouCha(2);
TouCha(3);
print();
return 0;
}
输出结果：
这里我们只实现了头插和遍历两个操作，这也是我们用的最多的两个操作。
好了，今天的内容就分享到这，我们下期再见！
标签：Node,单链,进阶,之美,next,链表,pcur,phead,NewNode From： https://blog.csdn.net/2401_87995839/article/details/144353238