大家好，又见面了，我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新Idea2022.1教程亲测有效,一键激活。
Jetbrains全家桶1年46，售后保障稳定
第一次写博客，如果写得不好请谅解，欢迎大佬们一起交流讨论。
在我初学链表的时候，会觉得书上讲解十分抽象，理解到头炸，在通过做题的方式后，对链表又产生了新的认识和看法，使用链表的方式更加灵活了，通过这篇文章与大家分享一下单向链表的一些知识。
本文章主要讲单向链表：创建，输出，排序，插入，- 删除，清空
链表是一种重要的数据结构，它是动态地进行储存分配的一种结构，并且链表必须用指针变量才能实现（重点!）。
1. 创建
首先，建立动态链表，就是在程序运行中根据需求向系统申请储存空间，类似int *m = new int[n]的方式构造动态数组，概念是一种从无到有地建立新节点，并将各节点连接形成链表。
这篇文章以成员为id和成绩作为例子，通过C++实现。
环境：Code::Blocks_16.1 && VS2017
题目：
第1~n行每行都是两个整数，第一个是 id（唯一的），第二个是 score；第n+1行只有一个数字，0（n可能是0）。
这里的id输入是未排好序的整数
节点的声明：
struct Node {
int id;
int score;
struct Node *next; // 此处*next表示尾巴
}*list_head; // 设list_head，为全局变量的指针
接下来要讲如何实现建立动态链表，先放代码再继续讲解。
void scan() //创建链表
{
int id;
Node *list_temp; // 过渡指针，负责将各节点连接
list_head = NULL; // 作为头部，还没有输入，此时为 NULL
list_temp = list_head; // 将过渡指针指向头部，即从第一个节点开始
cout << “请输入id和score:” << endl;
while(cin >> id, id) // 判断输入id是否非0
{
Node *list_body = new Node();
// 申请空间，这里的括号可以删除，但为了增加程序的可读性，建议保留
list_body->id = id;
cin >> list_body->score;
list_body->next = NULL;
/* 以上是成员赋值，因为是单向链表的使用，所以next必须为NULL*/
if(list_head == NULL)
// 如果新节点是第一个节点，则将这个节点连接到头部list_head，即指针 list_head 为链表的头地址
list_head = list_body;
else // 此时不是第一个节点，使用过渡指针list_temp将节点与新节点连接
list_temp->next = list_body;
list_temp = list_body; // 过渡指针移动至新节点
}
}
假如把链表比作串烤串，那么一开始的链表就是一根竹签（list_head = NULL）
之后每串入一块肉(body)，就是new了一个新节点，并且这串肉首尾相连，竹签从肉出去的地方就是它的尾部（next），当没有下一个肉串入时，next = NULL
（list_body_1->next = list_body_2; list_body_2->next = list_body_3; …; list_body_n-1->next = list_body_n; 注意！list_body_n->next = NULL）
看上去将“肉”串在一起用编程实现很困难，其实只要通过指针list_temp就可以实现将各块“肉”首尾相连，这里我将指针list_temp称为过渡指针。
指针list_temp是通过，将新节点的地址复制给next来实现节点连接，这块的知识我自己学都觉得很抽象，得通过图文结合来理解，建立起框架。
指针list_temp是不停变换的，每次连接好节点后，便会移动至新节点的位置，不改变其他变量，确保不会指针漂移。
n个相连的body（节点）形成单向链表，list_head是第一个body的地址，每个body的next指向的是下一个body的地址，除了最后一个body指向的是NULL（因为后面已经没有body），其实就是串烤肉这么简单。
2. 输出
链表的输出，这部分比较简单。
代码部分：
/* 通过过渡指针 list_temp 从 head 位置到链表结尾，移动至每个节点来实现输出成员 */
void print_list()
{
Node *list_temp = list_head;
cout << "*** LISTING ***" << endl;
while(list_temp != NULL) // 判断当前位置是否存在节点
{
cout << "id:" << list_temp->id << '\t' << "score:" << list_temp->score << endl;
list_temp = list_temp->next;
}
cout << "*** END OF FILE ***" << endl;
}
这里可以理解为吃烤串，不过正常的吃烤串是从竹签尖的那端开始吃，而这里的“吃烤串”是从竹签底端的肉(list_temphead)开始往上吃（即往list_temp的箭头方向移动）
3. 排序
对于刚入门的菜鸟，先了解使用冒泡法排序链表，感兴趣的还可以去了解快排和归并排序。
void cmp_list() //升序冒泡排序
{
Node *list_temp = NULL; //控制外循环，指向需要排序的第一个节点
Node *list_end = NULL; //控制内循环，指向需要排序的最后一个节点
list_temp = list_head; //指向表头
while(list_temp != list_end)
{
while(list_temp->next != list_end)
{
/*这里的数据交换根据实际情况，但原理相同*/
if(list_temp->id > list_temp->next ->id ) //当前节点的id与下一个节点的id比较
{
//用整数cache_id和cache_score分别记录当前的位置的id和score
int cache_id = list_temp->id;
int cache_score = list_temp->score;
//下面的代码是交换两个链表的数据
list_temp->id = list_temp->next->id;
list_temp->score = list_temp->next->score;
list_temp->next->id = cache_id;
list_temp->next->score = cache_score;
}
list_temp = list_temp->next ;
}
list_end = list_temp; //将当前排序的最后一个节点向前挪动一个位置
list_temp = list_head; //重新指向表头
}
}
只要能理解数组的冒泡法，相信也能理解链表的冒泡排序，因为原理是相同的。这段代码我已经优化了一些，把链表无节点和链表只有一个节点的情况也考虑到了。
4. 插入
往链表中插入数据，先贴代码：
void add_point()
{
cout << "请输入新数据:" << endl;
Node *list_temp = list_head;
Node *new_body = new Node();
/*成员赋值*/
cin >> new_body->id >> new_body->score;
new_body->next = NULL;
/*if里的思想是:如果当前是空链表或新数据比第一个数小,则这样写 else里的思想是:当前链表已经升序排序过,所以满足插入的条件是出现数据比现在的值大或全部id都小于新id */
if(list_temp == NULL || new_body->id < list_temp->id)
{
new_body->next = list_temp;
list_head = new_body;
}
else
{
while(list_temp->next != NULL && list_temp->id < new_body->id )
{
if(list_temp->next->id > new_body->id)
break;
list_temp = list_temp->next;
}
new_body->next = list_temp->next;
list_temp->next = new_body;
}
}
链表排序后的插入我认为不好写，这段代码是我经过不断优化的最终写法，也有更简单的方法，那就是在链表尾部添加新数据，接着再次调用排序（例如冒泡法）。
链表插入的简单思想就是插入作为第一个节点，还是不是作为第一个节点插入。事实上，用双向链表来做插入更方便。
5. 删除
链表节点的删除就几种情况，首和尾和非首尾，像我用的这个链表只要考虑首和非首就可以。
void delete_point()
{
int id;
cout << "请输入要删除的id:" << endl;
cin >> id;
Node *list_temp = list_head, *cache = NULL;
if(list_head != NULL)
{
if(id == list_temp->id) //删除第一个节点
{
cache = list_temp->next;
delete (list_temp);
list_temp = NULL;
list_head = cache;
}
else //删除其他节点
{
while(list_temp->next != NULL && id != list_temp->id)
{
cache = list_temp;
list_temp = list_temp->next;
}
if(id == list_temp->id)
{
cache->next = list_temp->next;
delete (list_temp);
list_temp = NULL;
}
}
}
}
链表的节点删除是通过搜索来删除数据，主要是要考虑 当前符合的数据是链表的第一个节点还是其他节点，如果是第一个节点的话，那么就必须得修改list_head的位置。
6. 清空
void delete_all()
{
if(list_head != NULL)
{
Node *list_temp = NULL, *cache = NULL;
list_temp = list_head;
while(list_temp != NULL)
{
cache= list_temp->next;
delete(list_temp);
list_temp = NULL;
list_temp = cache;
}
}
cout << "链表已清空:" << endl;
}
链表的清空非常简单，并且链表的清空是必须的！！每次删除节点，一定要防止内存泄漏，虽然可能有内存回收机制，但是建议令该节点等于NULL，可以防止出现小问题。
7. 完整代码
#include <iostream>
using namespace std;
struct Node
{
int id;
int score;
struct Node *next; //此处*next表示尾巴
}*list_head;//设list_head，为全局变量的指针
void scan_list(); //链表的输入
void print_list(); //链表的输出
void cmp_list(); //链表的排序
void add_point(); //链表节点的添加
void delete_point(); //链表节点的删除
void delete_all(); //链表的清空
int main()
{
scan_list();
cout << "链表的创建:" << endl;
print_list();
cmp_list();
cout << "链表的排序:" << endl;
print_list();
add_point();
cout << "链表的添加:" << endl;
print_list();
delete_point();
cout << "链表的删除:" << endl;
print_list();
delete_all();
return 0;
}
void scan_list()
{
int id;
Node *list_temp = NULL; //过渡指针，负责将各节点连接
list_head = NULL; //作为头部，还没有输入，此时为NULL
list_temp = list_head; //将过渡指针指向头部，即从第一个节点开始
cout << "请输入id和score:" << endl;
while(cin >> id,id) //判断输入id是否非0
{
Node *list_body = new Node(); //申请空间，这里的括号可以删除，但为了增加程序的可读性，建议保留
list_body->id = id;
cin >> list_body->score;
list_body->next = NULL;
/*以上是成员赋值，因为是单向链表的使用，所以next必须为NULL*/
if(list_head == NULL) //如果新节点是第一个节点，则将这个节点连接到头部list_head，即指针list_head为链表的头地址
list_head = list_body;
else //此时不是第一个节点，使用过渡指针list_temp将节点与新节点连接
list_temp->next = list_body;
list_temp = list_body; //过渡指针移动至新节点
}
}
void print_list()
{
Node *list_temp = list_head;
cout << "*** LISTING ***" << endl;
while(list_temp != NULL) //判断当前位置是否存在节点
{
cout << "id:" << list_temp->id << '\t' << "score:" << list_temp->score << endl;
list_temp = list_temp->next;
}
cout << "*** END OF FILE ***" << endl;
}
void cmp_list() //升序冒泡排序
{
Node *list_temp = NULL; //控制外循环，指向需要排序的第一个节点
Node *list_end = NULL; //控制内循环，指向需要排序的最后一个节点
list_temp = list_head; //指向表头
while(list_temp != list_end)
{
while(list_temp->next != list_end)
{
/*这里的数据交换根据实际情况，但原理相同*/
if(list_temp->id > list_temp->next ->id ) //当前节点的id与下一个节点的id比较
{
//用整数cache_id和cache_score分别记录当前的位置的id和score
int cache_id = list_temp->id;
int cache_score = list_temp->score;
//下面的代码是交换两个链表的数据
list_temp->id = list_temp->next->id;
list_temp->score = list_temp->next->score;
list_temp->next->id = cache_id;
list_temp->next->score = cache_score;
}
list_temp = list_temp->next ;
}
list_end = list_temp; //将当前排序的最后一个节点向前挪动一个位置
list_temp = list_head; //重新指向表头
}
}
void add_point()
{
cout << "请输入新数据:" << endl;
Node *list_temp = list_head;
Node *new_body = new Node();
/*成员赋值*/
cin >> new_body->id >> new_body->score;
new_body->next = NULL;
/*if里的思想是:如果当前是空链表或新数据比第一个数小,则这样写 else里的思想是:当前链表已经升序排序过,所以满足插入的条件是出现数据比现在的值大或全部id都小于新id */
if(list_temp == NULL || new_body->id < list_temp->id)
{
new_body->next = list_temp;
list_head = new_body;
}
else
{
while(list_temp->next != NULL && list_temp->id < new_body->id )
{
if(list_temp->next->id > new_body->id)
break;
list_temp = list_temp->next;
}
new_body->next = list_temp->next;
list_temp->next = new_body;
}
}
void delete_point()
{
int id;
cout << "请输入要删除的id:" << endl;
cin >> id;
Node *list_temp = list_head, *cache = NULL;
if(list_head != NULL)
{
if(id == list_temp->id) //删除第一个节点
{
cache = list_temp->next;
delete (list_temp);
list_temp = NULL;
list_head = cache;
}
else //删除其他节点
{
while(list_temp->next != NULL && id != list_temp->id)
{
cache = list_temp;
list_temp = list_temp->next;
}
if(id == list_temp->id)
{
cache->next = list_temp->next;
delete (list_temp);
list_temp = NULL;
}
}
}
}
void delete_all()
{
if(list_head != NULL)
{
Node *list_temp = NULL, *cache = NULL;
list_temp = list_head;
while(list_temp != NULL)
{
cache= list_temp->next;
delete(list_temp);
list_temp = NULL;
list_temp = cache;
}
}
cout << "链表已清空:" << endl;
}
我希望我的这篇博客对链表初学者可以为提供思路，注意，链表是C++/C里很重要的一个部分，还请大家看我的代码不仅仅是复制黏贴那么简单。我的代码或许还存在一些bug或可以完善的地方，欢迎大佬们指点与讨论。
发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/219130.html原文链接：https://javaforall.net
