链表（数据结构）

一、链表的定义

1、定义

（1）n个结点离散分配
（2）彼此通过指针相连
（3）每个结点只有1个前驱结点，每个结点只有1个后续结点。首结点没有前驱结点，尾结点没有后续结点。

2、一些概念

• 结点：类似数组的元素，单个的逻辑上具有独立意义的个体。
  每个结点的结构都相同。

• 有效结点：存放有效数据的结点

• 首结点：第一个有效结点

• 尾结点：最后一个有效结点

• 头结点：不存放任何有效数据；它指向首结点；它的数据类型与其它结点的数据类型相同。
  加头结点的目的：对链表进行操作时，在前面添加没有实际含义的头结点，可以方便我们对链表进行操作。

• 头指针：指向头结点的指针变量

• 尾指针：指向尾结点的指针变量

3、确定一个链表需要几个参数？

1个参数：头指针。

因为通过头指针，可以推算出链表的其它所有信息。

因此，如果通过一个函数来对链表进行处理，我们至少需要接收链表的头指针信息。

4、每个结点的数据类型该如何表示？（如何模拟/表示一个结点）

每个结点可以分为2部分：数据域和指针域。
数据域中的数据可以非常复杂；指针域中的指针指向另外一个和它数据类型相同的结点。

（1）

typedef struct Node
{
    int data;  // 数据域
    struct Node *pNext;  //指针域
} NODE, *PNODE;

（2）

PNODE p = (PNODE)malloc(sizeof(NODE));
// 将动态分配的新结点的地址赋给p

（3）

free p;    // 删除p指向结点所占的内存
// 不是删除p本身所占内存

（4）

p -> pNext;    // p所指向结构体变量中的pNext成员本身

二、链表的分类

• 单链表
  每个结点只有一个指针域，且该指针域只能指向后面的结点。

• 双链表
  每个结点有2个指针域。左边的指针域指向前面的结点，右边的指针域指向后面的结点。

• 循环链表
  能通过任何一个结点找到其他所有的结点。
  尾结点的指针域指向了头结点。

• 非循环链表

三、单链表的操作

• 创建链表

• 遍历链表

• 查找

• 清空

• 销毁

• 判断是否为空

• 求长度

• 排序

• 删除结点：删除p所指向的结点后面的结点

  // 错误：
  p->pNext = p->pNext->pNext; // 删除结点的内存就会被泄漏

  // 错误：
  free(p->pNext); // 直接free掉这个结点，则它指向的结点也都找不到了。

• 插入结点：把q所指向的结点插到p所指向的结点后面

  // 错误：
  p->pNext = q;
  q->pNext = p->pNext;

  // 方法1：先临时定义一个指向p后面结点的指针r
  r = p->pNext; // r指向p后面的那个结点
  p->pNext = q;
  q->pNext = r;

  // 方法2：
  q->pNext = p->pNext;
  p->pNext = q;