值域链域链表-基本概念
.链表是线性表的⼀种存储形式。
链表的结点结构：
值域（数据域）：存储表元素值；
链域（指针域）：存储后继结点的存储地址（指单向链表）。
⾸指针（表头指针）：指向链表的第⼀个结点的指针变量，其值为⾸结点的存储地址。// 如下图 head 部分
表尾结点（最后⼀个结点）的链域值为空（NULL）。// 如下图的最后⼀个结点，也就是 “刘” 结点。空，⽤ ^ 表⽰。
编码时，“空” ⽤符号常量 NULL 表⽰，NULL 的值为数字 0
。
⼀个链表就是表头指针和⼀串相继链接的结点
的总称。
⽤ C语⾔的结构类型定义单向链表的结点结构：
1// 利⽤ typedef 功能重定义了结点类型名 snode 和指针类型名 ptr
2
3 typedef struct linkednode{ //结点类型
4
5  int data；//值域
6
7  struct linkednode *next；//链域
8
9 }　snode，*ptr；//结点类型名 snode 和指针类型名 ptr
10
11 ptr head，p，q；// 定义指针类型变量
// 类型 struct linkednode* 与类型 ptr 等价，都是指向 snode 的指针类型。
头指针指着头结点；
struct head是定义头指针
关于 typedef ：⽤来为复杂的声明定义简单的别名，它与宏定义有些差异。它本⾝是⼀种存储类的关键字，与auto、extern、mutable、static、register等关键字不能出现在同⼀个表达式中。
使⽤ typedef 为现有类型创建别名：
使⽤ typedef 掩饰复合类型，如指针和数组：
关于 C语⾔结构体变量，也就是上述代码部分第9⾏那⾥：
为了定义结构，必须使⽤ struct 语句。struct 语句定义了⼀个包含多个成员的新的数据类型，struct 语句格式如下：
tag 是结构体标签；member-list 是标准的变量定义，⽐如 int i；或者 float f，或者其他有效变量定义。
variable-list 结构变量，定义在结构的末尾，最后⼀个分号之前，可以指定⼀个或多个结构变量。例：
这时我们可以直接使⽤ book，就相当于使⽤ Books 这个结构体，⽽⽆需再 struct Books book；
-----------------------分-----------------------割-----------------------线-----------------------
结点的产⽣和回收：
因为链表的结点是在程序运⾏期间动态产⽣和撤销的，
①当⽤户程序需要使⽤新结点时，调⽤ malloc 函数向系统申请结点；
malloc 产⽣结点（动态结点）
②当某结点废弃不⽤时，可调⽤ free 函数将其释放，交给系统回收资源。
free 回收结点
③ malloc 和 free 均是系统库⽂件 malloc.h 中的标准函数，所以程序前部要有编译预处理命令
#include <malloc.h>
④ malloc（）函数的典型⽤法：p = （ptr）malloc（sizeof（snode））；
这⾥的 “ptr” 和 “snode” 是上边 “⽤ C语⾔的结构类型定义单向链表的结点结构” ⾥的。
⽽ p = （ptr）malloc（sizeof（snode））；的含义：
申请产⽣⼀个⼤⼩为 sizeof（snode）的动态变量空间，也称⼀个动态结点；
数组和链表将结点的地址值转换成 ptr 类型，赋值给指针变量 p；
这样可以利⽤指针 p 访问动态结点，若分配失败，返回 NULL
⑤也可以利⽤ C++ 语⾔中的 new 命令实现动态存储分配⼯作：p = new snode；
⑥在 p 获得动态结点的地址之后，就可以引⽤它的值域 p->data 和 p->next
p->data 和 p->next 也是变量，其中 p->next 是⼀个指针变量，可以指向其它结点。
p->data：结点的值域，等价于 (*p).data；
p->next：结点的链域，等价于 (*p).next；
⑦ “废结点” 的回收：
调⽤函数 free（p）例如：free（p）；
该语句含义为：释放指针 p 所指向的动态结点所占⽤的存储单元，系统将原先分配给结点 p-> 的存储单元回收到动态存储区，以便 “今后” 重新分配给 “下⼀个” 申请者。
注意！！执⾏语句 “free（p）” 之后，结点 p 被释放，结点 p 不复存在，对结点 p-> 的操作也将变得⽆意义。
但是！！变量 p 并没有消失，还可以⽤来指向其它结点，当 p 指向其它结点后，⼜可以对新的这个 p-> 指向的结点进⾏操作，但已经不是原来的结点。
也可以使⽤ C++ 的 delete 命令回收结点，delete p；
-----------------------分-----------------------割-----------------------线-----------------------
结点的链接操作：是让前趋节点的链域指向后继结点。
若指针变量 p 和 q ，分别指向结点 p 和 q，⽤语句 q->next = p ，可以将结点 p 链接到结点 q 的后⾯
p 是⼀个指针变量，q->next 也是⼀个指针变量，
同类型指针变量之间执⾏赋值操作，
是将结点 p 的地址值赋给了链域 q->next，
由于赋值号左侧是链域，于是完成了结点的链接操作。
注意：唯有对链域的赋值操作才是结点的链接操作，其余形式的同类型指针之间的赋值操作，仅仅是改变指针的指向关系，丝毫不会改变结点的链接关系。

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。