链表
链表
今天教大家up好久才琢磨明白的链表~
链表：
定义一个含有 int类型 和 指向node类型的指针 的数据类型（结构体，下文有讲解），其中每个指针都指向下一个数据储存的内存地址即可
对于数组，想要在一列数中插入一个或多个数，就需要使数据依次向后移到下一个下标的空间里，造成程序的运行时间也很大，用链表这种结构就可以很简单的插入和删除数据了
首先，大家需要了解什么是指针
在c++中指针的应用非常广泛
以下是指针教程：
首先创建一个int a，再创建一个int型指针变量*p
格式如下：
int a；
int *p；//指向什么类型就定义什么类型
此时再加入以下语句
p=a；//指针变量p中存的是int a在内存中的地址，为取址符，顾名思义就是获取地址的操作
coutp;
程序则输出一串16进制数，内容为p的值(也就是a的地址）
*p=1//则是用指针间接操作int a，此语句给a赋值为1，*p 代表p地址中存的数据
以上就是指针的基本操作，大家可以自己试试改改数据和语句，摸索摸索
其次要了解结构体
结构体就是将多种类型的数据放在一起，作为一个新类型的数据使用
如
struct node//建立一个”node”类型的数据
{
int data;
int data2;
};//结尾一定要加分号
访问和操作数据呢，用.符来操作，如下
node a；//创建一个node型的数据命名为a
根据上面的定义可以知道node型包含int data和data2
node.data=1;
coutnode.data;
cinnode.data;
coutnode.data;
既可以实现对数据的操作
如果创建的是指向node类型的指针呢
node *p;
那么访问数据就要用-符号来表示了，即：
cinnode-data;
coutnode-data;
输入一个值
输出的就是刚刚输入的值了
下面介绍一个实现链表所需的一个函数malloc()
malloc需要头文件#includecstdlib
格式：(i数据类型*)malloc(存储数据所需的内存字节数);//可以用sizeof(数据类型);来获取数据类型所需要的字节
(int*)malloc(sizeof(int));
功能是动态获取内存中的一块区域的地址，大小可以储存一个int变量
int *p；
p=(int*)malloc(sizeof(int));
cin*p;
coutp *pendl;
运行后可见输出的是分配的地址以及此地址中存的数据
那这个函数的意义是什么呢？不急，这个运用非常巧妙，继续往下看
先把程序贴出来，不要被篇幅所吓倒，实际原理很简单的~
#include iostream
#include cstdlib
using namespace std;
struct node
{
int data;
struct node *next;
};
int main()
{
node *head,*p,*q,*t;
int a,n;
cinn;
head=NULL;
for(int i=0;in;i++)//以下为创建链表
{
cina;
p=(node*)malloc(sizeof(node));
p-data=a;
p-next=NULL;
if(head==NULL)
{
head=p;
}
else
{
q-next=p;
}
q=p;
}
cina;//以下为插入数据
t=head;
while(t!=NULL)
{
if(t-next==NULL || t-next-dataa)//下一个节点的值大于a或无下一个节点
{
p=(node*)malloc(sizeof(node));
p-data=a;
p-next=t-next;
t-next=p;
break;
}
t=t-next;
}
t=head;//以下为输出
while(t!=NULL)
{
printf(%d ,t-data);
t=t-next;
}
return 0;
}
自己悟明白了没有？
创建链表的过程其实是根据动态分配的地址存入数据，虽然*p，*q，*t，*head都在改变
但每次操作后本节点数据和下一个节点的地址都储存在了内存中，所以只要使head指向第一个节点，就可以用t=t-next;来依次获取下一个节点的地址并操作数据了
以下是我本人研究时在草纸上的模拟~
链表结构以及创建操作示意图
循环次数少时程序运行顺序示意图
算法是建立在语法的基础上的，最主要还是要自己去理解去悟，若有疑问可以在评论中向我提问~
关于链表的c++专栏就到此结束啦~
b站up主提醒您，道路千万条，三连第一条，看完不三连，up两行泪
以上就是（链表）全部内容，收藏起来下次访问不迷路！