头指针 first 150
地址 110 120 130 140 150 160 170 180
data 域 a2
a4 a6 a1
a5 a3
图 2 -5 单链表示意图
a1
a2
a3
a4
图２-6 单链表的逻辑表示
link 域 180
170 NULL
110
140 130
a5
a6 ^
单链表可用Ｃ++描述为:
void TraverseList(&L) //遍历线性表L int Find(&L,ElemType x) //在线性表L中查找值为X的 元素
int Update(&L,ElemType x) //在线性表L中查找值为X的 元素,并用X的值更新该元素
.…..
END Linearlist
2.2 顺序表
线性表的顺序存储结构,也称为顺序表。其存储方式为： 在内存中开辟一片连续存储空间，但该连续存储空间 的大小要大于或等于顺序表的长度，然后让线性表中 第一个元素存放在连续存储空间第一个位置，第二个 元素紧跟着第一个之后，其余依此类推。
顺序表可用Ｃ++描述为: （参见教材P30)
class SeqList { Type *data; int MaxSize; //线性表最大长度 int size; //当前线性表长度
故时间复杂度为O(n)。
同理，可推出删除运算的平均移动次数为 n1 ， 2
故时间复杂度为O(n)。
第3章 链表
线性表的链式存贮结构，也称为链表。其 存贮方式是：在内存中利用存贮单元(可以 不连续)来存放元素值及它在内存的地址， 各个元素的存放顺序及位置都可以以任意 顺序进行，原来相邻的元素存放到计算机 内存后不一定相邻，从一个元素找下一个 元素必须通过地址(指针)才能实现。故不能 像顺序表一样可随机访问，而只能按顺序 访问。常用的链表有单链表、循环链表和 双向链表。
删除
ai-1
ai
ai+1
p
p->rLink = p->rLink->rLink; p->rLink->lLink = p;
循环链表
最后一个结点的指针域的指 针又指回第一个结点
a1 a2 … an
判别链表中最后一个结点的条件不 再是“后继是否为空”，而是“后 继 (int j=L.size-1; j<=i; j--)
{ L.data[j+1]=L.data[j]; }
i位置
最后的位置 L.size-1
a1 a2 … ai-1 ai … an
a1 a2 … ai-1 e ai … an
表的长度增1
有关删除运算
删除表头元素操作 删除给定值元素操作 删除i位置元素操作
class ListNode
{ Type data; //元素类型
ListNode * link; //指针类型,存放下一个元素地址
}
first
a1
a2
……
an ^
(a) 不带头结点的单链表
first 头
a1
a2
……
an ^
(b) 带头结点的单链表 图 2-7 不带头结点和带头结点的单链表
插入、删除、建立等操作在单链表中的实现： 有序对 <ai-1, ai>改变为 <ai-1, e> 和<e, ai>
线性表的抽象数据类型描述
ADT Linearlist is Data: 一个线性表L定义为L=(a1,a2,…,an)，当L=（ ）时定义 为一个空表 operation: void InitList(&L) //将线性表L置成空表 int ListSize(&L) //求给定线性表L的长度 Elemtype GetElem(&L,int i) //取线性表L第i个位置上 的元素
３.１ 单链表结构
在定义的链表中，若只含有一个指针域来存放下一个 元素地址，称这样的链表为单链表或线性链表。 线性链表中的结点结构可描述为:
Data link
其中data 域用来存放结点本身信息，类型由具体问题而定， (本书中设定为Type类型，表示某一种具体的已知类型)， link域用来存放下一个元素地址。
双向链表可用C++描述如下：(参见教材P62） class DblList { Type data; //结点的数据域,类型设定为Type DblNode *lLink, *rLink; //定义指向直接后继和直 接前驱的指针
}
p
双向链表
ai-1
ai
插入
e
s s->rLink = p->rLink; p->rLink = s; s->rLink->lLink = s; s->lLink = p;
…… };
//若干操作函数
顺序表操作的实现
有关线性表遍历及查找: 从表头元素起依次访问每一个元素，遍历时 每个元素只被访问一次,查找时每访问一个 元素都与给定值比较
a1 a2 … ai-1 ai … an …
表头元素
L.data[0]
表尾元素
L.data[L.size-1]
有关插入的操作
• 表头或表尾插入一个元素 • 合适的位置插入一个元素 • 插在i位置操作
ai-1
ai
e
s = new ListNode;
s->data = e;
//生成新结点
s->link = p->link;
p->link = s;
//插入
p
aii--11
s
ai e
q = p->link; p->link = q->link; e = q->data; delete q;
p
q
ai-1
第2章 线性表
线性表的定义
线性表（linear list）是n（n≥0）个数据元素a1，a2，…an组 成的有限序列。其中n 称为数据元素的个数或线性表的长 度，当n=0时称为空表，n>0时称为非空表。通常将非空的 线性表记为（a1，a2，…,an），其中的数据元素ai（1≤i≤n） 是一个抽象的符号，其具体含义在不同情况下是不同的， 即它的数据类型可以根据具体情况而定，本书中，我们将 它的类型设定为ElemType，表示某一种具体的已知数据类 型。
插入算法花费的时间，主要在于循环中元素的后移 （其它语句花费的时间可以省去），即从插入位置到 最后位置的所有元素都要后移一位，使空出的位置插 入元素值e。但是，插入的位置是不固定的，当插入位 置i=0时，全部元素都得移动，需n次移动，当i=n时， 不需移动元素，故在i位置插入时移动次数为n-i，假设 在每个位置插入的概率相等为1/(n+1)，则平均移动元 素的次数为 n/2（参见教材P33） 。
线性表的特征 从线性表的定义可以看出线性表的特征： （1 ） 有且仅有一个开始结点(表头结点)a1，它没 有直接前驱，只有一个直接后继; （2） 有且仅有一个终端结点(表尾结点)an，它没有 直接后继，只有一个直接前驱; （3） 其它结点都有一个直接前驱和直接后继； （ 4）元素之间为一对一的线性关系。
ai
ai+1
双向链表结构
在单链表中，从某个结点出发可以直接找到它的直接后 继，时间复杂度为O(1) ，但无法直接找到它的直接前驱； 在单循环链表中，从某个结点出发可以直接找到它的直 接后继，时间复杂仍为O(1)，直接找到它的直接前驱， 时间复杂为O(n)。有时，希望能快速找到一个结点的直 接前驱，这时，可以在单链表中的结点中增加一个指针 域指向它的直接前驱，这样的链表，就称为双向链表(一 个结点中含有两个指针)。如果每条链构成一个循环链表， 则会得双向循环链表。
