文档介绍：: .
×
Eqninidelete =−=−=∑∑i () ()
ii==11n 2
其中，qi 表示删除元素 ai 的概率。
2）线性表的链式存储
线性表的链式存储是用节点来存储数据元素，元素的节点地址可以连续，也可以不连续，
因此，存储数据元素的同时必须存储元素之间的逻辑关系。另外，节点空间只有在需要的时候
才申请，无须事先分配。基本的节点结构如下所示：
数据域 指针域
节点中的数据域用于存储数据元素的值，指针域则存储当前元素的直接前驱或直接后继元
素的位置信息，指针域中所存储的信息称为指针（或链）。
n 个节点通过指针连成一个链表，若节点中只有一个指针域，则称为线性链表（或单链表），
如图 3-2 所示。第 3 章 数据结构与算法 115
（a）不含头节点的单链表
（b）含头节点的单链表
图 3-2 线性表元素的单链表存储
在链式存储结构中，只需要一个指针（称为头指针，如图 3-2 中的 Head）指向第一个节点，
就可以按照链接关系顺序地访问表中的任意一个元素。为了简化对链表状态的判定和处理，特
别引入一个不存储数据元素的节点，称为头节点，将其作为链表的第一个节点并令头指针指向
该节点。
在链式存储结构下进行插入和删除，其实质都是对相关指针的修改。
设单链表节点类型的定义为：
typedef struct node{
int data; /*数据域*/
struct node *next; /*指针域*/
}NODE, *LinkList;
在单链表 p 所指节点（图 3-3 中元素 a 所在节点）后插入新元素节点（s 所指节点，图
3-3（a）中元素 c 所在节点）时，操作如下。
① s->next = p->next; /*s 所指节点的指针域改为指向 p 所指节点的后继节点*/
② p->next = s; /*p所指节点的指针域改为指向 s 所指节点*/
（a）单链表中插入节点 （b）单链表中删除节点
图 3-3 在单链表中插入和删除节点时的指针变化示意图
在单链表中删除 p 所指节点的后继节点时，操作如下。
① q = p->next; /*备份被删除节点的指针*/
② p->next = p->next->next; /*修改节点间的链接关系，从链表中摘除要删除的节点*/
③ free(q); /*释放被删除节点的空间*/116 数据库系统工程师教程（第