Hello大家好！很高兴我们又见面啦！给生活添点passion，开始今天的编程之路！
我的博客：<但凡.
我的专栏：《数据结构与算法之美》、《编程之路》、《题海拾贝》
欢迎点赞，关注！
目录
1、使用C++实现单链表
1.1节点的声明
1.2节点的初始化
1.3头插和尾插
1.3.1头插
1.3.2尾插
1.4头删和尾删
1.4.1头删
1.4.2尾删
1.5打印链表
1.6测试
2、面向对象的方式实现单链表
2.1面向对象和面向过程
2.2面向对象的方式实现单链表
3、静态链表实现
3.1动态实现链表和静态实现链表
3.2链表静态实现
3.2.1理解
3.2.2创建
3.2.3头插
3.2.3遍历打印链表
3.2.4测试
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 1WeiCha(phead, 2);//0 1 2WeiCha(phead, 3);//0 1 2 3WeiCha(phead, 4);//0 1 2 3 4TouShan(phead);//1 2 3 4WeiShan(phead);//1 2 3Printlist(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 1list.WeiCha(2);//0 1 2list.WeiCha(3);//0 1 2 3list.WeiCha(4);//0 1 2 3 4list.TouShan();//1 2 3 4list.WeiShan();//1 2 3list.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;
}
输出结果：
这里我们只实现了头插和遍历两个操作，这也是我们用的最多的两个操作。
好了，今天的内容就分享到这，我们下期再见！