? 线性表
顺序表
链表
顺序表与链表的比较线性表 (Linear List)
线性表的定义和特点
定义 n（? 0） 个数据元素的有限序列，记作
（ a1,a2,…,an）
ai 是表中数据元素,n 是表长度。
遍历 逐项访问：
从前向后 从后向前线性表的特点
除第一个元素外，其他每一个元素有一个且仅有一个 直接前驱 。
除最后一个元素外，其他每一个元素有一个且仅有一个 直接后继 。
a1 a2 a3 a4 a5 a6
顺序表 (Sequential List)
顺序表的定义和特点
定义 将线性表中的元素相继存放在一个连续的存储空间中。
可利用 一维数组 描述 存储结构
特点 线性表的顺序存储方式
遍历 顺序 访问,可以随机存取
25 34 57 16 48 09
0 1 2 3 4 5
data
顺序表的连续存储方式
35 27 49 18 60 54 77 83 41 02
0 1 2 3 4 5 6 7 8 9
l l l l l l l l l l
LOC(i) = LOC(i-1)+l = a+i*l
LOC(i) = LOC(i-1)+l = a+i*l,i > 0a,i = 0
a+i*l
a
顺序表 (SeqList)的定义
#define ListSize 100 //最大允许长度
typedef int ListData;
typedef struct {
ListData * data; //存储数组
int length; //当前元素个数
} SeqList;
顺序表基本运算的实现
构造一个空的顺序表
void InitList ( SeqList & L ) {
L.data = ( ListData * ) malloc
( ListSize * sizeof ( ListData ) );
if ( L.data == NULL ) {
printf (,存储分配失败 !\n”);
exit (1);
}
L.length = 0;
}
求表的长度
int Length ( SeqList & L ) {
return L.length;
}
提取 函数：在表中提取第 i 个元素的值
ListData GetData ( SeqList &L,int i ) {
if ( i >= 0 && i < L.length )
return L.data[i];
else printf (,参数 i 不合理 ！ \n” );
}
//在出错情况，函数返回值不能用 ！
按值查找,在顺序表中从头查找结点值等于给定值 x 的结点
int Find ( SeqList &L,ListData x ) {
int i = 0;
while ( i < L.length && L.data[i] != x )
i++;
if ( i < L.length ) return i;
else return -1;
}
顺序查找图示
25 34 57 16 48 09
0 1 2 3 4 5
data
查找 16 i
25 34 57 16 48 09
i
25 34 57 16 48 09
i
25 34 57 16 48 09
i 查找成功
25 34 57 16 48
0 1 2 3 4
data
查找 50 i
25 34 57 16 48
i
25 34 57 16 48
i
25 34 57 16 48
i
25 34 57 16 48
i 查找失败查找成功的平均比较次数若查找概率相等，则查找不成功 数据比较 n 次
i
n
i
i cp
1
0
=A C N
2
1
2
)(11
)2(1
1
1)(
1
=
1
0
nnn
n
n
n
i
n
n
i
A C N?
22
1)(
1)(
1
0)1(
1
1
)(
1
1
=
0
nnn
n
n
n
in
n
n
i
A M N
表项的插入
25 34 57 16 48 09 63
0 1 2 3 4 5 6 7
data
50插入 x
25 34 57 50 16 48 09 63
0 1 2 3 4 5 6 7
data 50
i
表项的插入
int Insert ( SeqList &L,ListData x,int i ) {
//在表中第 i 个位置插入新元素 x
if (i < 0 || i > L.length || L.length == ListSize)
return 0; //插入不成功
else {
for ( int j = L.length; j > i; j-- )
L.data[j] = L.data[j -1];
L.data[i] = x; L.length++;
return 1; //插入成功
}
}
表项的删除
1
0 2
1
2
1)(11)(1= n
i
nnn
n
in
n
A M N
25 34 57 50 16 48 09 63
0 1 2 3 4 5 6 7
data 16
删除 x
25 34 57 50 48 09 63
0 1 2 3 4 5 6 7
data
表项的删除
int Delete ( SeqList &L,ListData x ) {
//在表中删除已有元素 x
int i = Find (L,x); //在表中查找 x
if ( i >= 0 ) {
L.length -- ;
for ( int j = i; j < L.length; j++ )
L.data[j] = L.data[j+1];
return 1; //成功删除
}
return 0; //表中没有 x
}
顺序表的应用,集合的“并”运算
void Union ( SeqList &A,SeqList &B ) {
int n = Length ( A );
int m = Length ( B );
for ( int i = 0; i < m; i++ ) {
int x = GetData ( B,i ); //在 B中取一元素
int k = Find (A,x); //在 A中查找它
if ( k == -1 ) //若未找到插入它
{ Insert ( A,x,n ); n++; }
}
}
void Intersection ( SeqList &A,SeqList &B ) {
int n = Length ( A );
int m = Length ( B ); int i = 0;
while ( i < n ) {
int x = GetData ( A,i ); //在 A中取一元素
int k = Find ( B,x ); //在 B中查找它
if ( k == -1 ) { Delete ( A,i ); n--; }
else i++; //未找到在 A中删除它
}
}
顺序表的应用,集合的“交”运算链表（ Linked List）
链接表是线性表的链接存储表示
单链表
静态链表
循环链表
双向链表单链表 (Singly Linked List)
特点
每个元素 (表项 )由结点 (Node)构成。
线性结构
结点可以连续，可以不连续存储
结点的逻辑顺序与物理顺序可以不一致
表可扩充
data link
a0 a1 a2 a3 a4?first
单链表的存储映像
free (a) 可利用存储空间
a0 a2 a1 a3?
freefirst
(b) 经过一段运行后的单链表结构单链表的定义
typedef char ListData;
typedef struct node { //链表结点
ListData data; //结点数据域
struct node * link; //结点链域
} ListNode;
typedef ListNode * LinkList; //链表 头指针
LinkList first; //链表 头指针单链表中的插入与删除
插入
第一种情况：在第一个结点前插入
newnode->link = first ;
first = newnode;
（插入前） （插入后）
first
newnode newnode
first
(插入前 ) (插入后 )
第二种情况：在链表中间插入
newnode->link = p->link;
p->link = newnode；
newnode
p
newnode
p
第三种情况：在链表末尾插入
newnode->link = p->link;
p->link = newnode；
(插入前 ) (插入后 )
newnode newnode
p p
int Insert ( LinkList& first,int x,int i ) {
//在链表第 i 个结点处插入新元素 x
ListNode * p = first; int k = 0;
while ( p != NULL && k < i -1 )
{ p = p->link; k++; } //找第 i-1个结点
if ( p == NULL && first != NULL ) {
printf (,无效的插入位置 !\n” );
return 0;
}
ListNode * newnode = //创建新结点
(ListNode *) malloc ( sizeof (ListNode) );
newnode->data = x;
if ( first == NULL || i == 1 ) { //插在表前
newnode->link = first;
first = newnode;
}
else { //插在表中或末尾
newnode->link = p->link;
p->link = newnode;
}
return 1;
}
删除
第一种情况,删除表中第一个元素
第二种情况,删除表中或表尾元素在单链表中删除含 ai的结点
ai-1
ai-1
ai
ai
ai+1
ai+1
p q
删除前删除后
int Delete ( LinkList& first,int i ) {
//在链表中删除第 i 个结点
ListNode *p,*q;
if ( i == 1 ) //删除表中第 1 个结点
{ q = first; first = first->link; }
else {
p = first; int k = 0; //找第 i-1个结点
while ( p != NULL && k < i-1 )
{ p = p->link; k++; }
if ( p == NULL || p->link == NULL ) {
printf (,无效的删除位置 !\n” );
return 0;
}
else { //删除表中或表尾元素
q = p->link; //重新链接
p->link = q->link;
}
}
free ( q ); //删除 q
return 1;
}
带表头结点的单链表
表头结点位于表的最前端，本身不带数据,仅标志表头 。
设置表头结点的目的是
统一空表与非空表的操作
简化链表操作的实现 。
非空表 空表
0ana1first first 0
在带表头结点的单链表第一个结点前插入新结点
newnode->link = p->link; p->link = newnode;
first
newnode
first
newnode
插入
first
newnode
0 first
newnode 0
插入
p p
p p
q = p->link;
p->link = q->link;
delete q;
从带表头结点的单链表中删除第一个结点
first
first
(非空表）
first
0first
(空表）
0
p q
p q
前插法建立单链表
从一个空表开始，重复读入数据：
生成新结点
将读入数据存放到新结点的数据域中
将该新结点插入到链表的前端
直到读入结束符为止。
first
newnode
first
newnode
0
0
LinkList createListF ( void ) {
char ch; ListNode *s;
LinkList head = //建立表头结点
(LinkList) malloc (sizeof (ListNode));
head->link = NULL;
while ( (ch = getchar( ) ) !=?\n? ) {
s = (listNode *) malloc (sizeof(ListNode));
s->data = ch; //建立新结点
s->link = head->link; //插入到表前端
head->link = s;
}
return head;
}
后插法建立单链表
每次将新结点加在链表的表尾；
设置一个尾指针 r，总是指向表中最后一个结点，新结点插在它的后面；
尾指针 r 初始时置为指向表头结点地址。
0
0newnode
first
newnode
0
0
r
r
r
r
LinkList createListR ( void ) {
char ch;
LinkList head = //建立表头结点
(LinkList) malloc (sizeof (ListNode));
ListNode *s,*r = head; // r指向表尾
while ( (ch = getchar( ) ) !=?\n? ) {
s = (listNode *) malloc (sizeof(ListNode));
s->data = ch; //建立新结点
r ->link = s; r = s; //插入到表末端
}
r ->link = NULL; //表收尾
return head;
}
first
q
first
first
q
q
first
a0 a1
a1
a2
a2
a2
单链表清空单链表清空
void makeEmpty ( LinkList first ) {
//删去链表中除表头结点外的所有其他结点
ListNode *q;
while ( first->link != NULL ) {
q = first->link; first->link = q->link;
//将表头结点后第一个结点从链中摘下
free( q ); //释放它
}
}
first
p
a0 a1 a2
c = 0
first
p
a0 a1 a2
c = 1
first
p
a0 a1 a2
c = 2
first
p
a0 a1 a2
c = 3
计算单链表长度
int Length ( LinkList first ) {
ListNode *p = first->link;
//检测指针 p 指示第一个结点
int count = 0;
while ( p != NULL ) { //逐个结点检测
p = p->link; count++;
}
return count;
}
计算单链表长度
ListNode * Find ( LinkList first,ListData value ) {
//在链表中从头搜索其数据值为 value的结点
ListNode * p = first->link;
//检测指针 p 指示第一个结点
while ( p != NULL && p->data != value )
p = p->link;
return p;
}
在单链表中按值查找
ListNode * Locate ( LinkList first,int i ) {
//返回表中第 i 个元素的地址
if ( i < 0 ) return NULL; // i 值不合理
ListNode * p = first; int k = 0; //置于表头
while ( p != NULL && k < i )
{ p = p->link; k++; } //找第 i 个结点
if ( k == i ) return p;
else return NULL;
//返回第 i 个结点地址或 NULL
}
在单链表中按序号查找（定位）
在单链表中插入新结点
newnode->link = p->link; p->link = newnode;
first
newnode
first
newnode
插入
newnode newnode
插入
p p
p p
int Insert (LinkList first,ListData x,int i ) {
//将新元素 x 插入在链表中第 i 号结点位置
ListNode * p = Locate ( first,i-1 );
if ( p == NULL ) return 0; //不插入
ListNode * newnode = //创建新结点
(ListNode *) malloc (sizeof (ListNode) );
newnode->data = x;
newnode->link = p->link; //链入
p->link = newnode;
return 1; //插入成功，函数返回 1
}
在单链表中插入新元素在单链表中删除一个结点
q = p->link;
p->link = q->link;
delete q;
first
0first
p
p
p
q
q
q
int delete ( LinkList first,int i ) {
//将链表第 i 号元素删去
ListNode * p = Locate ( first,i-1 );
//寻找被删结点的前驱结点
if ( p == NULL || p->link == NULL)
return 0; //不删除
ListNode * q = p->link; //被删结点地址
p->link = q->link; //摘下被删结点
free ( q ); //释放
return l;
}
在单链表中删除一个结点
【 例 】 单链表 求和函数
typedef int ListData;
int sum ( LinkList ls ) {
ListNode * p = ls->link;
int retvalue = 0;
while ( p != NULL ) {
retvalue += p->data; //累加
p = p->link;
}
return retvalue;
}
循环链表 (Circular List)
循环链表是单链表的变形。
循环链表最后一个结点的 link 指针不 为
NULL，而是指向了表的前端。
为简化操作，在循环链表中往往加入表头结点。
循环链表的特点是,只要知道表中某一结点的地址，就可搜寻到所有其他结点的地址。
循环链表的示例
带表头结点的循环链表
a0 a1 a2 an-1first
an-1first a1a
0
first
(空表 )
(非空表 )
查找成功查找不成功循环链表的查找
first
first
31
31
48
48
15
15
57
57
查找 15
查找 25
p p p
p p p pp
循环链表的定义
typedef char ListData;
typedef struct cnode { //链表结点
ListData data; //结点数据域
struct cnode * link; //结点链域
} CircListNode;
typedef CircListNode * CircLinkList;
//循环 链表 头指针
CircLinkList first; //循环 链表 头指针循环链表的查找算法
CircListNode * Find ( CircLinkList first,
ListData value ) {
//在链表中从头搜索其数据值为 value的结点
CircListNode * p = first->link;
//检测指针 p 指示第一个结点
while ( p != first && p->data != value )
p = p->link;
return p;
}
带尾指针的循环链表
rear
31 48 15 5722
如果插入与删除仅在链表的两端发生，
可采用带表尾指针的循环链表结构。
在表尾插入，时间复杂性 O(1)
在表尾删除，时间复杂性 O(n)
在表头插入，相当于在表尾插入在表头删除，时间复杂性 O(1)
将循环链表链入单链表链头
rear15 20 25 3010
first 60 65 7055
rear15 20 25 3010
p 60 65 7055
first
双向链表 (Doubly Linked List)
双向链表是指在前驱和后继方向都能游历 (遍历 )的线性链表。
双向链表每个结点结构：
双向链表通常采用带表头结点的循环链表形式。
前驱方向后继方向
prior data next
结点指向
p == p->prior->next == p->next->prior
非空表 空表
p->prior p->nextp
priornext
first first
双向循环链表的定义
typedef int ListData;
typedef struct dnode {
ListNode data; //数据
struct dnode * prior,* next; //指针
} DblNode;
typedef DblNode * DblList; //双向链表建立空的双向循环链表
void CreateDblList ( DblList & first ) {
first = ( DblNode * ) malloc
( sizeof ( DblNode ) );
if ( first == NULL )
{ print (,存储分配错 !\n” ); exit (1); }
first->prior = first->next = first;
//表头结点的链指针指向自己
}
计算双向循环链表的长度
int Length ( DblList first ) {
//计算带表头结点的双向循环链表的长度
DblNode * p = first->next;
int count = 0;
while ( p != first )
{ p = p->next; count++; }
return count;
}
查找成功查找不成功双向循环链表的查找
first
first
31
31
48
48
15
15
57
57
查找 15
查找 25
ListNode * Find ( DblList first,ListData x ) {
//在双向循环链表中搜索含 x 的结点,若找到,
//则返回该结点的地址,否则返回表头地址。
DblNode * p = first->next;
while ( p != first && p->data != x )
p = p->next;
return p;
}
//也可以在 prior (前驱 ) 方向查找,程序类似。
DblNode * Locate ( DblList first,int i ) {
if ( i < 0 ) return first;
DblNode * p = first->next; int j = 1;
while ( p != first && j < i )
{ p = p->next; j++; }
return p;
}
//也可以在 prior (前驱 ) 方向查找,程序类似。
定位：查找第 i 个结点在链中的位置双向循环链表的插入 (非空表 )
first
first
31 48 15
在结点 *p 后插入 25 p
p
31 48 25 15
q->prior = p;
q->next = p->next;
p->next = q;
q->next->prior = q;
q
双向循环链表的插入 (空表 )
first
在结点 *p 后插入 25
p q
25
q->prior = p;
q->next = p->next; ( = first )
p->next = q;
q->next->prior = q; ( first->prior = q )
first
p
int Insert ( DblList first,int i,ListData x ) {
DblNode * p = Locate ( first,i-1 );
//指针定位于插入位置
if ( p == first && i != 1) return 0;
DblNode * q = ( DblNode * ) malloc
( sizeof ( DblNode ) ); //分配结点
q->data = x;
q->prior = p; p->next->prior = q;
//在前驱方向链入新结点
q->next = p->next; p->next = q;
//在后继方向链入新结点
return 1;
}
删除 48
双向循环链表的删除
first
first
非空表31 48 15
p
31 15
p->next->prior = p->prior;
p->prior->next = p->next;
删除 31
双向循环链表的删除
first first31
p
p->next->prior = p->prior;
p->prior->next = p->next;
int Remove ( DblList first,int i ) {
DblNode * p = Locate ( first,i );
//指针定位于删除结点位置
if ( p == first ) return 0;
p->next->prior = p->prior;
p->prior->next = p->next;
//将被删结点 *p 从链上摘下
free ( p ); //删去
return 1;
}
顺序表与链表的比较基于空间的比较
存储分配的方式
顺序表的存储空间是 静态分配 的
链表的存储空间是 动态分配 的
存储密度 = 结点数据本身所占的存储量
/结点结构所占的存储总量
顺序表的存储密度 = 1
链表的存储密度 < 1
顺序表与链表的比较基于时间的比较
存取方式
顺序表可以 随机存取,也可以 顺序存取
链表是 顺序存取 的
插入 /删除时移动元素个数
顺序表平均需要移动近一半元素
链表不需要移动元素，只需要修改指针
若插入 /删除仅发生在表的两端，宜采用带尾指针的循环链表
顺序表
链表
顺序表与链表的比较线性表 (Linear List)
线性表的定义和特点
定义 n（? 0） 个数据元素的有限序列，记作
（ a1,a2,…,an）
ai 是表中数据元素,n 是表长度。
遍历 逐项访问：
从前向后 从后向前线性表的特点
除第一个元素外，其他每一个元素有一个且仅有一个 直接前驱 。
除最后一个元素外，其他每一个元素有一个且仅有一个 直接后继 。
a1 a2 a3 a4 a5 a6
顺序表 (Sequential List)
顺序表的定义和特点
定义 将线性表中的元素相继存放在一个连续的存储空间中。
可利用 一维数组 描述 存储结构
特点 线性表的顺序存储方式
遍历 顺序 访问,可以随机存取
25 34 57 16 48 09
0 1 2 3 4 5
data
顺序表的连续存储方式
35 27 49 18 60 54 77 83 41 02
0 1 2 3 4 5 6 7 8 9
l l l l l l l l l l
LOC(i) = LOC(i-1)+l = a+i*l
LOC(i) = LOC(i-1)+l = a+i*l,i > 0a,i = 0
a+i*l
a
顺序表 (SeqList)的定义
#define ListSize 100 //最大允许长度
typedef int ListData;
typedef struct {
ListData * data; //存储数组
int length; //当前元素个数
} SeqList;
顺序表基本运算的实现
构造一个空的顺序表
void InitList ( SeqList & L ) {
L.data = ( ListData * ) malloc
( ListSize * sizeof ( ListData ) );
if ( L.data == NULL ) {
printf (,存储分配失败 !\n”);
exit (1);
}
L.length = 0;
}
求表的长度
int Length ( SeqList & L ) {
return L.length;
}
提取 函数：在表中提取第 i 个元素的值
ListData GetData ( SeqList &L,int i ) {
if ( i >= 0 && i < L.length )
return L.data[i];
else printf (,参数 i 不合理 ！ \n” );
}
//在出错情况，函数返回值不能用 ！
按值查找,在顺序表中从头查找结点值等于给定值 x 的结点
int Find ( SeqList &L,ListData x ) {
int i = 0;
while ( i < L.length && L.data[i] != x )
i++;
if ( i < L.length ) return i;
else return -1;
}
顺序查找图示
25 34 57 16 48 09
0 1 2 3 4 5
data
查找 16 i
25 34 57 16 48 09
i
25 34 57 16 48 09
i
25 34 57 16 48 09
i 查找成功
25 34 57 16 48
0 1 2 3 4
data
查找 50 i
25 34 57 16 48
i
25 34 57 16 48
i
25 34 57 16 48
i
25 34 57 16 48
i 查找失败查找成功的平均比较次数若查找概率相等，则查找不成功 数据比较 n 次
i
n
i
i cp
1
0
=A C N
2
1
2
)(11
)2(1
1
1)(
1
=
1
0
nnn
n
n
n
i
n
n
i
A C N?
22
1)(
1)(
1
0)1(
1
1
)(
1
1
=
0
nnn
n
n
n
in
n
n
i
A M N
表项的插入
25 34 57 16 48 09 63
0 1 2 3 4 5 6 7
data
50插入 x
25 34 57 50 16 48 09 63
0 1 2 3 4 5 6 7
data 50
i
表项的插入
int Insert ( SeqList &L,ListData x,int i ) {
//在表中第 i 个位置插入新元素 x
if (i < 0 || i > L.length || L.length == ListSize)
return 0; //插入不成功
else {
for ( int j = L.length; j > i; j-- )
L.data[j] = L.data[j -1];
L.data[i] = x; L.length++;
return 1; //插入成功
}
}
表项的删除
1
0 2
1
2
1)(11)(1= n
i
nnn
n
in
n
A M N
25 34 57 50 16 48 09 63
0 1 2 3 4 5 6 7
data 16
删除 x
25 34 57 50 48 09 63
0 1 2 3 4 5 6 7
data
表项的删除
int Delete ( SeqList &L,ListData x ) {
//在表中删除已有元素 x
int i = Find (L,x); //在表中查找 x
if ( i >= 0 ) {
L.length -- ;
for ( int j = i; j < L.length; j++ )
L.data[j] = L.data[j+1];
return 1; //成功删除
}
return 0; //表中没有 x
}
顺序表的应用,集合的“并”运算
void Union ( SeqList &A,SeqList &B ) {
int n = Length ( A );
int m = Length ( B );
for ( int i = 0; i < m; i++ ) {
int x = GetData ( B,i ); //在 B中取一元素
int k = Find (A,x); //在 A中查找它
if ( k == -1 ) //若未找到插入它
{ Insert ( A,x,n ); n++; }
}
}
void Intersection ( SeqList &A,SeqList &B ) {
int n = Length ( A );
int m = Length ( B ); int i = 0;
while ( i < n ) {
int x = GetData ( A,i ); //在 A中取一元素
int k = Find ( B,x ); //在 B中查找它
if ( k == -1 ) { Delete ( A,i ); n--; }
else i++; //未找到在 A中删除它
}
}
顺序表的应用,集合的“交”运算链表（ Linked List）
链接表是线性表的链接存储表示
单链表
静态链表
循环链表
双向链表单链表 (Singly Linked List)
特点
每个元素 (表项 )由结点 (Node)构成。
线性结构
结点可以连续，可以不连续存储
结点的逻辑顺序与物理顺序可以不一致
表可扩充
data link
a0 a1 a2 a3 a4?first
单链表的存储映像
free (a) 可利用存储空间
a0 a2 a1 a3?
freefirst
(b) 经过一段运行后的单链表结构单链表的定义
typedef char ListData;
typedef struct node { //链表结点
ListData data; //结点数据域
struct node * link; //结点链域
} ListNode;
typedef ListNode * LinkList; //链表 头指针
LinkList first; //链表 头指针单链表中的插入与删除
插入
第一种情况：在第一个结点前插入
newnode->link = first ;
first = newnode;
（插入前） （插入后）
first
newnode newnode
first
(插入前 ) (插入后 )
第二种情况：在链表中间插入
newnode->link = p->link;
p->link = newnode；
newnode
p
newnode
p
第三种情况：在链表末尾插入
newnode->link = p->link;
p->link = newnode；
(插入前 ) (插入后 )
newnode newnode
p p
int Insert ( LinkList& first,int x,int i ) {
//在链表第 i 个结点处插入新元素 x
ListNode * p = first; int k = 0;
while ( p != NULL && k < i -1 )
{ p = p->link; k++; } //找第 i-1个结点
if ( p == NULL && first != NULL ) {
printf (,无效的插入位置 !\n” );
return 0;
}
ListNode * newnode = //创建新结点
(ListNode *) malloc ( sizeof (ListNode) );
newnode->data = x;
if ( first == NULL || i == 1 ) { //插在表前
newnode->link = first;
first = newnode;
}
else { //插在表中或末尾
newnode->link = p->link;
p->link = newnode;
}
return 1;
}
删除
第一种情况,删除表中第一个元素
第二种情况,删除表中或表尾元素在单链表中删除含 ai的结点
ai-1
ai-1
ai
ai
ai+1
ai+1
p q
删除前删除后
int Delete ( LinkList& first,int i ) {
//在链表中删除第 i 个结点
ListNode *p,*q;
if ( i == 1 ) //删除表中第 1 个结点
{ q = first; first = first->link; }
else {
p = first; int k = 0; //找第 i-1个结点
while ( p != NULL && k < i-1 )
{ p = p->link; k++; }
if ( p == NULL || p->link == NULL ) {
printf (,无效的删除位置 !\n” );
return 0;
}
else { //删除表中或表尾元素
q = p->link; //重新链接
p->link = q->link;
}
}
free ( q ); //删除 q
return 1;
}
带表头结点的单链表
表头结点位于表的最前端，本身不带数据,仅标志表头 。
设置表头结点的目的是
统一空表与非空表的操作
简化链表操作的实现 。
非空表 空表
0ana1first first 0
在带表头结点的单链表第一个结点前插入新结点
newnode->link = p->link; p->link = newnode;
first
newnode
first
newnode
插入
first
newnode
0 first
newnode 0
插入
p p
p p
q = p->link;
p->link = q->link;
delete q;
从带表头结点的单链表中删除第一个结点
first
first
(非空表）
first
0first
(空表）
0
p q
p q
前插法建立单链表
从一个空表开始，重复读入数据：
生成新结点
将读入数据存放到新结点的数据域中
将该新结点插入到链表的前端
直到读入结束符为止。
first
newnode
first
newnode
0
0
LinkList createListF ( void ) {
char ch; ListNode *s;
LinkList head = //建立表头结点
(LinkList) malloc (sizeof (ListNode));
head->link = NULL;
while ( (ch = getchar( ) ) !=?\n? ) {
s = (listNode *) malloc (sizeof(ListNode));
s->data = ch; //建立新结点
s->link = head->link; //插入到表前端
head->link = s;
}
return head;
}
后插法建立单链表
每次将新结点加在链表的表尾；
设置一个尾指针 r，总是指向表中最后一个结点，新结点插在它的后面；
尾指针 r 初始时置为指向表头结点地址。
0
0newnode
first
newnode
0
0
r
r
r
r
LinkList createListR ( void ) {
char ch;
LinkList head = //建立表头结点
(LinkList) malloc (sizeof (ListNode));
ListNode *s,*r = head; // r指向表尾
while ( (ch = getchar( ) ) !=?\n? ) {
s = (listNode *) malloc (sizeof(ListNode));
s->data = ch; //建立新结点
r ->link = s; r = s; //插入到表末端
}
r ->link = NULL; //表收尾
return head;
}
first
q
first
first
q
q
first
a0 a1
a1
a2
a2
a2
单链表清空单链表清空
void makeEmpty ( LinkList first ) {
//删去链表中除表头结点外的所有其他结点
ListNode *q;
while ( first->link != NULL ) {
q = first->link; first->link = q->link;
//将表头结点后第一个结点从链中摘下
free( q ); //释放它
}
}
first
p
a0 a1 a2
c = 0
first
p
a0 a1 a2
c = 1
first
p
a0 a1 a2
c = 2
first
p
a0 a1 a2
c = 3
计算单链表长度
int Length ( LinkList first ) {
ListNode *p = first->link;
//检测指针 p 指示第一个结点
int count = 0;
while ( p != NULL ) { //逐个结点检测
p = p->link; count++;
}
return count;
}
计算单链表长度
ListNode * Find ( LinkList first,ListData value ) {
//在链表中从头搜索其数据值为 value的结点
ListNode * p = first->link;
//检测指针 p 指示第一个结点
while ( p != NULL && p->data != value )
p = p->link;
return p;
}
在单链表中按值查找
ListNode * Locate ( LinkList first,int i ) {
//返回表中第 i 个元素的地址
if ( i < 0 ) return NULL; // i 值不合理
ListNode * p = first; int k = 0; //置于表头
while ( p != NULL && k < i )
{ p = p->link; k++; } //找第 i 个结点
if ( k == i ) return p;
else return NULL;
//返回第 i 个结点地址或 NULL
}
在单链表中按序号查找（定位）
在单链表中插入新结点
newnode->link = p->link; p->link = newnode;
first
newnode
first
newnode
插入
newnode newnode
插入
p p
p p
int Insert (LinkList first,ListData x,int i ) {
//将新元素 x 插入在链表中第 i 号结点位置
ListNode * p = Locate ( first,i-1 );
if ( p == NULL ) return 0; //不插入
ListNode * newnode = //创建新结点
(ListNode *) malloc (sizeof (ListNode) );
newnode->data = x;
newnode->link = p->link; //链入
p->link = newnode;
return 1; //插入成功，函数返回 1
}
在单链表中插入新元素在单链表中删除一个结点
q = p->link;
p->link = q->link;
delete q;
first
0first
p
p
p
q
q
q
int delete ( LinkList first,int i ) {
//将链表第 i 号元素删去
ListNode * p = Locate ( first,i-1 );
//寻找被删结点的前驱结点
if ( p == NULL || p->link == NULL)
return 0; //不删除
ListNode * q = p->link; //被删结点地址
p->link = q->link; //摘下被删结点
free ( q ); //释放
return l;
}
在单链表中删除一个结点
【 例 】 单链表 求和函数
typedef int ListData;
int sum ( LinkList ls ) {
ListNode * p = ls->link;
int retvalue = 0;
while ( p != NULL ) {
retvalue += p->data; //累加
p = p->link;
}
return retvalue;
}
循环链表 (Circular List)
循环链表是单链表的变形。
循环链表最后一个结点的 link 指针不 为
NULL，而是指向了表的前端。
为简化操作，在循环链表中往往加入表头结点。
循环链表的特点是,只要知道表中某一结点的地址，就可搜寻到所有其他结点的地址。
循环链表的示例
带表头结点的循环链表
a0 a1 a2 an-1first
an-1first a1a
0
first
(空表 )
(非空表 )
查找成功查找不成功循环链表的查找
first
first
31
31
48
48
15
15
57
57
查找 15
查找 25
p p p
p p p pp
循环链表的定义
typedef char ListData;
typedef struct cnode { //链表结点
ListData data; //结点数据域
struct cnode * link; //结点链域
} CircListNode;
typedef CircListNode * CircLinkList;
//循环 链表 头指针
CircLinkList first; //循环 链表 头指针循环链表的查找算法
CircListNode * Find ( CircLinkList first,
ListData value ) {
//在链表中从头搜索其数据值为 value的结点
CircListNode * p = first->link;
//检测指针 p 指示第一个结点
while ( p != first && p->data != value )
p = p->link;
return p;
}
带尾指针的循环链表
rear
31 48 15 5722
如果插入与删除仅在链表的两端发生，
可采用带表尾指针的循环链表结构。
在表尾插入，时间复杂性 O(1)
在表尾删除，时间复杂性 O(n)
在表头插入，相当于在表尾插入在表头删除，时间复杂性 O(1)
将循环链表链入单链表链头
rear15 20 25 3010
first 60 65 7055
rear15 20 25 3010
p 60 65 7055
first
双向链表 (Doubly Linked List)
双向链表是指在前驱和后继方向都能游历 (遍历 )的线性链表。
双向链表每个结点结构：
双向链表通常采用带表头结点的循环链表形式。
前驱方向后继方向
prior data next
结点指向
p == p->prior->next == p->next->prior
非空表 空表
p->prior p->nextp
priornext
first first
双向循环链表的定义
typedef int ListData;
typedef struct dnode {
ListNode data; //数据
struct dnode * prior,* next; //指针
} DblNode;
typedef DblNode * DblList; //双向链表建立空的双向循环链表
void CreateDblList ( DblList & first ) {
first = ( DblNode * ) malloc
( sizeof ( DblNode ) );
if ( first == NULL )
{ print (,存储分配错 !\n” ); exit (1); }
first->prior = first->next = first;
//表头结点的链指针指向自己
}
计算双向循环链表的长度
int Length ( DblList first ) {
//计算带表头结点的双向循环链表的长度
DblNode * p = first->next;
int count = 0;
while ( p != first )
{ p = p->next; count++; }
return count;
}
查找成功查找不成功双向循环链表的查找
first
first
31
31
48
48
15
15
57
57
查找 15
查找 25
ListNode * Find ( DblList first,ListData x ) {
//在双向循环链表中搜索含 x 的结点,若找到,
//则返回该结点的地址,否则返回表头地址。
DblNode * p = first->next;
while ( p != first && p->data != x )
p = p->next;
return p;
}
//也可以在 prior (前驱 ) 方向查找,程序类似。
DblNode * Locate ( DblList first,int i ) {
if ( i < 0 ) return first;
DblNode * p = first->next; int j = 1;
while ( p != first && j < i )
{ p = p->next; j++; }
return p;
}
//也可以在 prior (前驱 ) 方向查找,程序类似。
定位：查找第 i 个结点在链中的位置双向循环链表的插入 (非空表 )
first
first
31 48 15
在结点 *p 后插入 25 p
p
31 48 25 15
q->prior = p;
q->next = p->next;
p->next = q;
q->next->prior = q;
q
双向循环链表的插入 (空表 )
first
在结点 *p 后插入 25
p q
25
q->prior = p;
q->next = p->next; ( = first )
p->next = q;
q->next->prior = q; ( first->prior = q )
first
p
int Insert ( DblList first,int i,ListData x ) {
DblNode * p = Locate ( first,i-1 );
//指针定位于插入位置
if ( p == first && i != 1) return 0;
DblNode * q = ( DblNode * ) malloc
( sizeof ( DblNode ) ); //分配结点
q->data = x;
q->prior = p; p->next->prior = q;
//在前驱方向链入新结点
q->next = p->next; p->next = q;
//在后继方向链入新结点
return 1;
}
删除 48
双向循环链表的删除
first
first
非空表31 48 15
p
31 15
p->next->prior = p->prior;
p->prior->next = p->next;
删除 31
双向循环链表的删除
first first31
p
p->next->prior = p->prior;
p->prior->next = p->next;
int Remove ( DblList first,int i ) {
DblNode * p = Locate ( first,i );
//指针定位于删除结点位置
if ( p == first ) return 0;
p->next->prior = p->prior;
p->prior->next = p->next;
//将被删结点 *p 从链上摘下
free ( p ); //删去
return 1;
}
顺序表与链表的比较基于空间的比较
存储分配的方式
顺序表的存储空间是 静态分配 的
链表的存储空间是 动态分配 的
存储密度 = 结点数据本身所占的存储量
/结点结构所占的存储总量
顺序表的存储密度 = 1
链表的存储密度 < 1
顺序表与链表的比较基于时间的比较
存取方式
顺序表可以 随机存取,也可以 顺序存取
链表是 顺序存取 的
插入 /删除时移动元素个数
顺序表平均需要移动近一半元素
链表不需要移动元素，只需要修改指针
若插入 /删除仅发生在表的两端，宜采用带尾指针的循环链表
