链表
1.节点是什么
链表是物理存储单元上非连续的、非顺序的存储结构,数据元素的逻辑顺序是通过链表的指针地址实现,有一系列结点
组成,结点可动态的生成。(简化来说就是存储地址不连续,但我们可以用一些逻辑思维把它们连接起来)
针对于这个结构,我们该如何表示它呢,其实啊我们在大一学过结构体,我们可以利用一下它
struct node{
int date;
struct node* next;
};
//上面的date就是数据域,用来存取我们想要存取的类型,对于数据域我们可以去存取任意类型
//例如
string date //字符串类型
long long int date//长整数类型
char date //字符型
//下面的next就是指向和自己同一个类型的指针
//例如
int* next;//定义一个指向int类型变量的指针
char* next//定义一个指向char 类型的指针
我么这样定义结构体变量 struct node a;
那我们类比一下 struct node* next 就是定义一个指向自己类型的指针
知道了什么是节点 那什么是链表的 (不要急,听我慢慢道来)
2.链表是什么
链表就是把这些节点连接起来,那怎怎么连接才能保证逻辑上有序呢
我们可以利用每个节点里面有一个指针,每一个节点都指向下一个节点,顺腾摸瓜,那不就连起来了吗
**具体结构是这样的******************
头结点==》首元结点(节点1)==》节点2==》节点3==》NULL;
有同学会问 头指针在哪里,其实啊头指针就是一个指针变量,它存储着头结点的地址
就像这样
3.如何操作链表
3.1创建单链表
//前插法
void createlist(node* L ,int n)//将链表头传进来,以及所建立的链表的长度
{
L=new node();//创建一个节点
L->next=NULL;
for(int i=1;i<=n;i++)
{
node* p=new node();//新建节点
cin>>(p->date);//输入节点的数据域
p->next=L-next;
L-next=p;
}
}
//后插法
void createlist(node* L,int n)
{
L=new node();
L->next=NULL;
r=L;
for(int i=1;i<=n;i++)
{
node* p=new node();
cin>>p->date;
p->next=NULL;
r->next=p;
r=p;
}
}
这写法和书上不完全一样,那是因为书上只是写了一个模板,也就是伪代码。对于每一个功能建议把它封装起来也就是写到一个函数中;
接下来我会为大家详细图解上述两种算法
链表变种
1.循环链表
2.循环链表的拼接
棒