1、指针链表
先看一道题目
【问题描述】
输入n个数据，建立带有头结点的单链表，并将建立好的单链表中的数据从头至尾遍历输出（要求输出数据的顺序与输入数据的顺序一致）。
【输入形式】
输入两行
第一行为整数n（范围1-10）
第二行为n个整型数据，数据与数据之间用空格分开。
【输出形式】
输出数据的顺序与输入数据的顺序一致，数据与数据之间仅用一个空格隔开。
【样例输入】
3
34 56 23
【样例输出】
34 56 23
这个时候我们就可以用指针链表来解决这个问题
先上完整代码，再一一解释
#include<iostream>
#include<cstdlib>
using namespace std;
struct node//定义一个结构体struct来储存这个节点
{
int data;//整型data，存储具体的数值
struct node *next;//一个指针，用来储存下一个节点的地址
};
int main()
{
struct node * head, * p,* q, * t;
int i, n, a;
cin >> n;
head = NULL;//头指针初始为空
for ( i = 1; i <= n; i++)
{
cin >> a;
p = (struct node*)malloc(sizeof(struct node));//动态申请一个空间，用来存放一个节点，并用临时指针p指向这个节点
p->data = a;//将数据存储到当前节点的data域中
p->next = NULL;//设置当前节点的后继指针指向空，也就是当前节点的下一个节点为空
if (head == NULL)head = p;//如果这是第一个创建的节点，则将头指针指向这个节点
else q->next = p;//如果不是第一个创建的节点，则将上一个节点的后继指针指向当前节点
q = p;//指针q也指向当前节点
}
//输出链表中的所有数
t = head;
while (t != NULL)
{
cout << t->data<<" ";
t = t->next;//继续下一个节点
}
return 0;
}?
2、指针链表节点的增加?
核心：用一个临时指针t从链表的头部开始遍历，等到t的下一个节点的值比某个值大的时候，将那个值插到中间，如图
上完整代码和注释
#include<iostream>
#include<cstdlib>
using namespace std;
struct node//定义一个结构体struct来储存这个节点
{
int data;//整型data，存储具体的数值
struct node *next;//一个指针，用来储存下一个节点的地址
};
int main()
{
struct node * head, * p,* q, * t;
int i, n, a;
cin >> n;
head = NULL;//头指针初始为空
for ( i = 1; i <= n; i++)
{
cin >> a;
p = (struct node*)malloc(sizeof(struct node));//动态申请一个空间，用来存放一个节点，并用临时指针p指向这个节点
p->data = a;//将数据存储到当前节点的data域中
p->next = NULL;//设置当前节点的后继指针指向空，也就是当前节点的下一个节点为空
if (head == NULL)head = p;//如果这是第一个创建的节点，则将头指针指向这个节点
else q->next = p;//如果不是第一个创建的节点，则将上一个节点的后继指针指向当前节点
q = p;//指针q也指向当前节点
}
cin>>a;
t = head;//从链表头部开始遍历
while(t!=NULL) //当没有到达链表尾部的时候循环
{
if(t->next->data>a)//如果当前节点的下一个节点的值大于待插数，将数插到中间
{
p = (struct node*)malloc(sizeof(struct node));//动态申请一个空间，用来存放一个节点，并用临时指针p指向这个节点
p->data = a;//将数据存储到当前节点的data域中
p->next=t->next;//新增节点的后继指针指向当前节点的后继指针所指向的节点
t->next=p;//当前节点的后继指针指向新增节点
break;
}
t=t->next;
}
//输出链表中的所有数
t = head;
while (t != NULL)
{
cout << t->data<<" ";
t = t->next;//继续下一个节点
}
return 0;
}?运行结果
3、指针链表节点的删除?
再上一道题目
【问题描述】
输入n个数据，建立带有头结点的单链表，并将建立好的单链表中的数据从头至尾遍历输出，再输入一个数据，如果在该单链表中有该数据则删除该数据（假设数据不重复），再输出链表中的内容。
【输入形式】
输入有三行
第一行为整数n;
第二行为n个整数，整数与整数之间用一个空格隔开。
第三行为一个整数。
【输出形式】
分两行输出，第一行为与输入顺序相同的原数据，数据与数据之间用空格隔开。
第二行为删除上述第三行输入的数据之后链表中剩下的内容。
【样例输入】
5
1 2 3 4 5
3
【样例输出】
1 2 3 4 5
1 2 4 5
对于这道题，我们需要找到要删除的节点，并将此节点的上一节点的后继指针指向此节点的后继指针
上图
上完整代码和注释
#include<iostream>
#include<cstdlib>
using namespace std;
struct node//定义一个结构体struct来储存这个节点
{
int data;//整型data，存储具体的数值
struct node *next;//一个指针，用来储存下一个节点的地址
};
int main()
{
struct node * head, * p,* q, * t;
int i, n, a;
cin >> n;
head = NULL;//头指针初始为空
for ( i = 1; i <= n; i++)
{
cin >> a;
p = (struct node*)malloc(sizeof(struct node));//动态申请一个空间，用来存放一个节点，并用临时指针p指向这个节点
p->data = a;//将数据存储到当前节点的data域中
p->next = NULL;//设置当前节点的后继指针指向空，也就是当前节点的下一个节点为空
if (head == NULL)head = p;//如果这是第一个创建的节点，则将头指针指向这个节点
else q->next = p;//如果不是第一个创建的节点，则将上一个节点的后继指针指向当前节点
q = p;//指针q也指向当前节点
}
cin>>a;//输入要删除的节点
//根据题目，先输出一遍链表中的所有数
t = head;
while (t != NULL)
{
cout << t->data<<" ";
t = t->next;//继续下一个节点
}
cout<<endl;//换行
t = head;//从头开始遍历
while (t != NULL)
{
if (t->next->data == a)//如果当前节点的下一个节点的值等于要删除的数
{
t->next = t->next->next;//将当前节点的后继指针连到下下个节点
break;
}
t = t->next;
}
//删除后再输出链表中的所有数
t = head;
while (t != NULL)
{
cout << t->data<<" ";
t = t->next;//继续下一个节点
}
return 0;
}运行结果
?
?本文思路出自入门算法书《啊哈算法》，并做了一定延伸，各位大佬看到轻喷
计算机小白一枚~