目录
一、概念
1、链式存储结构
结点在存储器中的位置是任意的，即逻辑上相邻的数据元素在物理上不一定相邻；
2、线性表的链式表示又称为非顺序映像或链式映像。
3、链表中元素的逻辑次序和物理次序不一定相同。
4、结点：由数据域和指针域两部分组成
数据域：存储元素数值数据；
指针域：存储直接后继结点的存储位置。
5、单链表：只有一个指针域的链表；
双链表：结点有两个指针域的链表；
循环链表：首尾相接的链表。
6、头指针：是指向链表中第一个结点的指针；
开始结点（首元结点）：是指链表中存储第一个数据元素a1的结点；
头节点：是在链表的开始结点之前附设的一个结点。
7、带头结点的单链表：头指针head指向头节点，头节点的值域不含任何信息。头指针head始终不等于NULL。head->next等于NULL时，链表为空。
不带头节点的单链表：头指针head直接指向开始结点。
二、链表（链式存储结构）的特点
- 结点在存储器中的位置是任意的，即逻辑上相邻的数据元素在物理上不一定相邻。
- 访问时只能通过头指针进入链表，并通过每个结点的指针域依次向后顺序扫描其余结点，所以寻找第一个结点和最后一个结点所花费的时间不一样。
- 理解顺序表和链表的存取方式，注意不是存储方式：顺序表——>随机存取；链表——>顺序存取。
三、单链表的定义与表示
typedef struct LNode{ //声明结点的类型和指向结点的指针类型
ElemType data; //结点的数据域
struct LNode *next; //结点的指针域
}LNode,*LinkList; //LinList为指向结构体LNode的指针类型
- 单链表是有头指针唯一确定，因此单链表可以用头指针的名字命名。
- 定义链表L：LinkList L;
- 定义结点指针：LNode *p;(或者是：LinkList p;)
四、单链表基本操作的实现
1、单链表的初始化（带头结点的单链表）
单链表的初始化：即构造一个空表
算法步骤：（1）生成新结点作头节点，用头指针L指向头结点。（2）将头结点的指针域置空。
算法描述：
void InitList(LinkList &L) { //L为引用型参数
L=(LinkList)malloc(sizeof(LNode)); //创建头结点L
L->next=NULL; //头结点next置为空表示空的单链表
}malloc(m)函数，开辟m字节长度的地址空间，并返回这段空间的首地址；
sizeof(x)运算，计算x的长度；
注意：需要加载头文件：<stdlib.h>
2、判断链表是否为空
空表：链表中无元素，称为空链表（头指针和头结点任然在）。
int listEmpty(LinkList L){ //若L为空表，则返回0，否则返回1
if(L->next==NULL){
return 0;
}else{
return 1;
}
}3、单链表的销毁
算法思路：从头指针开始，依次释放所有结点。
void destroyList(LinkList &L){
LinList p;
p=(LinkList)malloc(sizeof(LNode));
while(L!=NULL){
p=L;
L=L->next;
free(p);
}free(p)函数，释放指针p所指变量的存储空间，即彻底删除一个变量。
4、清空单链表
链表任然存在，但链表中无元素，成为空链表（头指针和头结点任然存在）
算法思路：依次释放所有结点，并将头结点指针域设置为空。
void clearList(LinkList &L){
LinkList p,q;
p=L->next; //p表示首元结点
while(p!=NULL){
q=p->next;
free(p);
p=q;
}
L->next=NULL;
}5、单链表的表长
算法思路：从开始结点（首元结点）开始，依次技术所有结点。
int listLength(LinkList L){
LinkList p;
p=L->next; //p指向开始结点
int len=0; //表长
while(p!=NULL){
len++;
p=p->next;
}
return len;
}重要操作：
p=L; //p指向头结点
q=L->next; //q指向开始结点（首元结点）
p=p->next; //p指向下一结点