2.2 线性表的链式存储

L
p
a1
a2
a3
an ^
空表条件：L= =NULL 表尾条件：p->next= =NULL
头结点 首元结点
p
L L
a1
a2
an ^
^
表尾条件：p->next= =NULL 空表条件：L->next= =NULL
单链表几个基本操作的具体实现： L 1.建立空的单链表
Status InitList_L(LinkList &L) { //创建一个带头结点的空的单链表 L = ( LinkList)malloc( sizeof(LNode ) );
右图可以简洁地用下面图形表示：
例：数据的逻辑结构B=（K，R） 其中 K={k1,k2,k3,k4,k5} 元素+指针=结点 以”结点的序列”表示线性表——链表 R={r} r={< k1,k2>,<k2,k3>,<k3,k4>,<k4,k5>} 头指针：指示单链表第一个结点的存 储位置的指针，整个链表的存取必须 是一个线性结构，它的链式存储如图 从头指针开始。常用head表示。 所示 空指针：终端结点无后继，故终端结 点的指针域为空，即NULL（图示中 也可用^表示) 参见P28图2.6
//在带头结点的单链表L中删除第i个元素，并由e返回其值
p=L; j=0; while(p->next && j<i-1) { p=p->next; ++j; //寻找第i个结点并令p指向其前趋 } if(!(p->next)||j>i-1) return ERROR; //删除位置不合理 q=p->next; p->next=q->next;//删除结点,或p->next=p->next->next； 链式存储的插入和删除 e=q->data; 操作比顺序存储方便，无须 free(q); //释放结点.指针q不能省,为什么? 移动结点，仅需修改指针， return OK; 但不能随机访问某个结点！ }//ListDelete_L 教材算法 2.10
算法的执行时间与key的取值有关，平均时间复杂度O(n)。
3.插入操作
将值为x的新结点插入到表的第i个结点位 置上，即插入到ai-1与ai之间，操作步骤： 1)找到ai-1的存储位置p； 2)生成一个数据域为x的新结点*s； 3)新结点的指针域指向结点ai； 4)令结点*p的指针域指向新结点。 (注意3和4步的次序) 插入过程如下图：
知识回顾
线性表的链式存储 单链表(线性链表)及C语言实现 头结点 单链表的建立、输出、查找、插入、删除 单链表与顺序表的比较
习题集P13
例题2.4对以下单链表分别执行下列各程序段， 2.4 并画出结果示意图.
L
2
5 P
7
3 R
8 ^ S
(1) L=P->next; 2 5 P 7 L 3 R 8 S ^
不带表头结点的单链表的删除：（分情况考虑）
为什么要定义头结点？ 带头结点的表，操作的实现比较方便。 没有头结点时，在最前面插入删除需要 修改表头指针,在其他位置插入删除时修改 前驱结点的next域，两种操作需要分别处 理。 有头结点时，表中每个“有效”结点都链 接在另一个结点的next域，操作可以统一处 理。
2.查找运算
1)按位序查找——GetElem_L(L, i, &e) 查找思想: 指针p从链表的头结点开始顺着链扫描。当p 扫描下一个结点时,计数器j相应加1；当j=i时, 指针p所指的结点就是要找的第i个结点；而当p 指针指为NULL或j>i时,表示找不到第i个结点。 思考：为什么有可能出现j>i？
在存储每个结点值的同时，只存储指示其后继结 在存储 ，只 点的地址（或位置）信息——称为指针(pointer)或 链(link) 。将每个结点只有一个链域的链表称为 线性链表或单链表（Single Linked)。每个结点的 存储形式是：
data
next
其中：data是数据域，用来存放结点的值。 next是指针域（链域），用来存放结点的 直接后继的地址（位置）。
} if (!p||j>i) return ERROR; // i大于表长或i小于1 e=p->data; //取第i个元素 return OK; }//GetElem_L教材算法 2.8
算法分析：while循环体中的语句频度与被查元素在 表中位置有关，若1≤i≤n，则频度为i-1，否则频度为 n。在等概率假设下平均时间复杂度为O(n)。
5.动态建立单链表(P30) 头插法建立含n个结点的带头结点的单链表L
头结点
L
an ^
p
an-1
p->next=L->next； L->next=p；
void CreateList_L(LinkList &L,int n){
//逆序输入n个元素的值,建立带表头节点的单链表L
L=(LinkList)malloc(sizeof(LNode)); L->next=NULL; //先建立带表头结点的单链表L for(i=n;i>0;--i) { p=(LinkList) malloc(sizeof(LNode)); scanf(&p->data); //生成新结点并输入元素值 p->next=L->next; L->next=p; //插入到表头 } }//CreateList_L教材算法2.11 O(n)
– 删除操作： – （删除第i个元素，并用e返回其值，同样 必须要先找到第i-1个元素）
p q
a1
a2
a3
q=p->next; p->next=q->next; 或者： p->next= p->next ->next；
Status ListDelete_L(LinkList &L,int i,ElemType &e){
链式存储：用一组地址任意的存储单 元存储线性表的数据元素。即：其中结点 元存储线性表的数据元素。即： 的逻辑次序和物理次序不一定相同。 除存放结点的数据，还需附设指针， 用指针体现结点之间的逻辑关系。用这种 用指针体现结点之间的 方式实现的表称为链表。常常要利用语言 的动态存储分配功能。
2.3.1 单链表（线性链表）——最简单的链表
单链表的C语言实现：
typedef char ElemType; //设结点数据域类型为字符 typedef struct LNode{ ElemType data;
//结点的数据域
struct LNode *next; //结点的指针域 }LNode, *LinkList; LNode *p; LinkList head;
^
//由系统生成一个LNode类型的结点，并将其起始位 //置赋给指针变量L if ( L != NULL ) L->next = NULL; return OK; }//InitList_L 算法2.3.1 1.malloc(size)函数； 2.free(L)函数：系统回收一个 LNode型的结点，回收后的空间 可以备作再次生成结点时用。
head
bat cat eat … mat ^
在链表中，任何两个元素的存储位置之间没 有固定的联系。即使知道被访问结点的序号i，也 不能象顺序表中那样直接访问，而只能从链表的 头指针出发，顺链域next逐个结点往下搜索，直 到搜索到第i个结点为止。因此，链表是非随机存 取结构。链表的查找只能从头指针开始顺序查 找。 （“顺藤摸瓜”） 若p->data=ai，则p->next->data=ai+1 ，类 推。
井冈山大学计算机科学系 孙凌宇 sunlingyu@
2.3 线性表的链式表示和实现
数据结构的存储方式必须体 现它的逻辑关系 。
除顺序存储外，线性表还常用链式 方式存储。本节将介绍一般线性表的几 种链式存储实现方式：单链表、循环链 表和双向链表。
2.3 线性表的链式表示和实现
不带表头结点的单链表的插入：（分情况考虑）
4、删除操作
删除运算是将链表的第i个结点删去。因为 在单链表中，结点ai的存储地址在其直接前趋 结点ai-1的指针域next中，所以 1)找到ai-1的存储位置p； 2)令p–>next指向ai的直接后继结点，即把ai从 链上摘下； 3)释放结点ai的空间，将其归还给“存储池”。 删除过程如下图所示： 删除过程如下图所示
– 插入操作：（插在第i个元素之前必须要先 找到第i-1个元素）
p
ai-1
ai ^ e
s
s->next=p->next； p->next=s；
Status ListInsert_L(LinkList &L,int i,ElemType e) {
//在带表头结点的单链表L中第i个位置前插入元素e
p=L; j=0; //假设头结点位置为0 while (p&&j<i-1) //寻找第i-1个结点 { p=p->next; ++j;} if (!p||j>i-1) return ERROR; //i大于表长加1或i小于1 s=(LNode*)malloc(sizeof(LNode)); s->data=e; //生成新结点 s->next=p->next; p->next=s; //插入L中 return OK; }//ListInsert_L 教材算法 2.9
2
5 P
7
3 R
5 ^ S
L
2
5 P
7
3 R
8 ^ S