单向链表(c/c++)

链表是一种常见的数据结构，其中运用到了结构体指针，链表可以实现动态存储分配，换而言之，链表是一个功能强大的数组，可以在某个节点定义多种数据类型，可以实现任意的添加，删除，插入节点等。（废话结束

前置知识：

地址,结构体,malloc函数与循环选择结构。

---

那我们先来学习一下malloc函数：

/*
格式为
(数据类型*)malloc(申请内存大小)
malloc函数可以通过传入要申请的内存大小在总堆里申请内存
之后会回归一个地址，在其前面的(数据类型*)是将这个地址定义
为要求数据类型。
*/int* ptr=(int*)malloc(sizeof(int));
/*
sizeof是一个传入数据类型，返回其所占内存的函数
那么sizeof(int),就是一个int类型的数所占的内存
之后将申请到的内存转换为int类型存储
*/int* ptd=(int*)malloc(5*sizeof(int));
//申请的内存大小为5*sizeof(int)也就是五个int类型的数字

之后我们来看通过结构体定义的链表节点

typedef struct Node{int data;//存储数据Node* next;//存储下个结点地址
}Node;//将结点名定义为Nodetypedef Node* List;//相当于Node List[]
//一个结点数组就是一个链表

将多个结点通过next相连就变成了一个链表。

---

链表操作

        链表操作一般分为六部分：建立链表，插入结点，删除结点，查找结点，更新结点，遍历链表。我们将这六步写为六个函数依次实现。

建立链表：

        创建一个空链表，初始化头节点，并将头节点的指针置为NULL(在这里提一下，链表是没有规定长度的，我们一般在遍历到结点->next==NULL时认为链表结束)

void BuildList(List& L){node=(Node*)malloc(sizeof(Node));//申请一个结点内存//申请内存if(!node){//node==NULL时cout<<"申请失败\n";return;}node->next=NULL;
}

调用函数后，链表结构如下：（一个结点，data为空，看作头节点）

插入结点：

        插入结点分为两种方式：头插法和尾插法，我们通过动图来演示一下

        尾插法:

        头插法：

可以比较清楚的看出两者的差异，尾插法是将新建结点插入到链表末尾，头插法是将新建结点插入到链表头节点后面。下面分别是两种方法的代码实现：

void Postinsert(List& L){//尾插法Node* node=(Node*)malloc(sizeof(Node));//申请一个结点内存L->next=node;//尾结点更新为node node->next=NULL;//尾结点下一位为NULL 
}
void Preinsert(List& L){//头插法Node node=(Node*)malloc(sizeof(Node));//申请一个结点内存node->next=L->next;//node结点下一位应为原来头节点下一位 L->next=node;//将node放入头节点的next位 
}

删除结点：

        找到要删除的节点，并将其删除，之后将删除节点的两侧相连。

        动图演示如下：

代码实现如下：

void DeleteNode(List& L,int t){//删除第t个结点Node* node=L->next;//定义结点指针Node* pre=L;//定义结点前一位指针while(--t){//while循环遍历第t个结点if(node==NULL){//当结点不存在时cout<<"此结点不存在\n";break;}pre=node;node=node->next;//更新pre，node指针}free(node);//释放内存   
}

查找结点：

        查找到 data为t 结点位于链表的第几位，并return位置

        动图演示如下：

        

代码实现如下：

int SearchNode(List& L,int T){//查找data为T的结点int cnt=1;//记录位数Node* node=L->next;while(node!=NULL){if(node->data==T)return cnt;//找到时return位数node=node->next;cnt++;//更新node指针与位数}cout<<"未找到结点\n";return -1;
}

更新结点：

        找到要更新的节点位置，并将其data更新。

        动图演示如下：

        

void UpdateNode(List& L,int a,int b){//将第a个结点data更新为bNode* node=L->next;//定义结点指针int cnt=1;//cnt用于计数while(node!=NULL){//while循环遍历找到第a个结点if(cnt==a){//找到结点时node->data=b;//updatebreak;       //停止循环}cnt++;node=node->next;//更新cnt和结点指针}if(node==NULL)//结点不存在时cout<<"该结点不存在\n";
}

遍历链表：

        遍历整个链表，输出每个结点的值

        动图演示如下：

代码实现如下：

void ErgodicList(List& L){//遍历输出Node* node=L->next;cout<<"链表遍历结果如下：\n";while(node!=NULL){cout<<node->next<<" ";node=node->next;}cout<<"\n";
}

结束

---