v76.链表
1.可变数组的缺陷
因为每当有需求的时候，都要去重新申请一个额外的空间然后copy，这样的缺陷：1copy需要时间；2可能会无法再次申请空间。
2.链表（linked list）
每个单元称作做一个结点（node），每个结点包含一个值和一个指针，其中的指针会指向下一个结点。其中head时开始指向链表的东西。
先来个代码展示
单链表单向导航；双链表双向导航；循环列表 最后的结点指向第一个结点。
单链表：
结点不需要按照顺序储存内存中。每个节点包含两个部分，一个用来储存实际数据，另一个储存下一个节点的地址（也就是指针）。这样就可以实现从第一个节点访问第二个节点，第二个节点访问第三个节点，只能是单向的，以此类推…那么如何访问第一个节点呢？需要一个head指针，里面存放第一个节点的地址，可以访问第一个节点。虽然链表在内存中是分散的，但是由于链表的链接部分，他们相互连接在一起。链表是列表的链接表示形式，但不是顺序的。
假设需要储存四个数字，那么可以使用数组或者链表。
使用数组的方式，他们在内存中储存的位置是连续的。可以认为数组是列表的顺序表示。
自引用结构（structure），即里面包含 指向一个相同结构类型的指针 的结构体。
- 一个结点包含两种不同的类型，data部分和link部分，那么使用结构就可以将这两种类型连接在一起：
struct node{
int data;
struct node* link;
};
第一个成员变量是data部分，数据类型不重要，int\float\char…均可；
第二个成员变量是指针类型，struct node表示的是它指向的数据类型。因为每个结点本就属于struct node类型，指针要指向下一个节点，实际上就是：要指向一个struct node类型的变量。所以设置为struct node* link;link就表示指向下一个结构体结点的指针。结点只不过是一个自引用结构…
需要注意的是，单链表只能有一个指针，数据可以有多个：
----至于什么时候用*head 什么时候用head的思考：
在一开始初始化指针head的时候，使用struct node* head，表示声明了一个struct node* 类型的变量：即一种指向struct node结构类型的指针。至此这个指针类型的变量名字就叫head，你为它分配内存甚至说你去改变它的值都是要用head = ...。使用*head表示取指针所指的东西！*head = ...。当然要表示函数参数表中的形式参数是要求传入指针，需要用*head表示。
—关于malloc函数：
分配内存所需的内存空间，并且返回一个指针 ，指向已分配内存的变量地址
#include <stdio.h>//c语言标准输入输出
#include <stdlib.h>//引用malloc函数为结构体节点创建内存
struct node {
int data;
struct node* link;
};
int main()
{
struct node* head = NULL;//head是指向 第一个 结构体节点的指针，通过这个指针，既可以访问data部分也可访问link部分
//能不能把head看做一个结构体类型的呢？
head = (struct node*)malloc(sizeof(struct node));//虽然有等号，但这不是赋值？malloc分配内存，帮助我们创建一个节点。这个操作后，节点的地址被返回到头指针head中
//通过头指针head访问第一个节点，并尝试初始化
head->data = 45;
head->link = NULL;//这里也是一样，虽然link是指针类型，但是普通访问指针变量的时候只写名字link即可
//打印第一个节点的data
printf("%d",head->data);//使用头指针来访问第一个节点，因为访问这个结点只有一个路线：通过头指针
return 0 ;
}
在每次为结点创建内存，那就必须得有一个指针来储存该节点的地址。因为如果没有这样的指针，那就无法访问结点。
链表基本上必须由三个节点组成
下面通过程序实现下面的一个链表：
head头指针储存第一个节点的地址，第一个节点的link部分储存第二个节点的地址…最后的节点link部分指向零地址，也就是NULL。
#include <stdio.h>
#include <stdlib.h>
struct node{
int data;
struct node* link;//见到这种反应一定要想到是指向结构类型的指针！！
};
int main()
{
struct node* head;
head = (struct node*)malloc(sizeof(struct node));//malloc函数返回的地址就是1000，节点一的地址
//有了地址之后就可以访问数据
head->data = 45;
head->link = NULL;
}
现在的问题：
可以再用一个头指针指向节点：
-----继续建立第二个节点：
struct node* current = malloc(sizeof(struct node));//创建一个新的头指针，并且指向了一个新的节点
current->data = 98;
current->link = NULL;
head->link = current;//更新head->link指向的零地址，地址给到第一个节点，将第一个节点的链接部分的指针指向第二个节点
return 0 ;
----继续建立第三个节点。可以像之前一样初始化一个指针current2、访问、交地址。
struct node* current2 = malloc(sizeof(struct node));//建立第三个字节
current2->data = 3;
current2->link = NULL;
current->link/*第二个结点的link*/ = current2;//更新current->link指向的零地址，
//地址给到第二个节点的link，使第二个节点的link像current2一样指向第三个节点。
原文地址：https://blog.csdn.net/2302_79232710/article/details/136781292
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！