? 线性表
? 顺序表
? 链表
? 顺序表与链表的比较
线性表 (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;
}
静态链表结构
静态链表定义
const int MaxSize = 100; //静态链表大小
typedef int ListData;
typedef struct node { //静态链表结点
ListData data;
int link;
} SNode;
typedef struct { //静态链表
SNode Nodes[MaxSize];
int newptr; //当前可分配空间首地址
} SLinkList;
将链表空间初始化
void InitList ( SLinkList SL ) {
SL.Nodes[0].link = -1;
SL.newptr = 1; //当前可分配空间 从 1 开始
//建立带表头结点的空链表
for ( int i = 1; i < MaxSize-1; i++ )
SL.Nodes[i].link = i+1;
//构成空闲链接表
SL.Nodes[MaxSize-1].link = -1;
//链表收尾
}
在静态链表中查找具有给定值的结点
int Find ( SLinkList SL,ListData x ) {
int p = SL.Nodes[0].link;
//指针 p 指向链表第一个结点
while ( p != -1 )
if ( SL.Nodes[p].data != x)
p = SL.Nodes[p].link;
else break;
//逐个结点检测查找具有给定值的结点
return p;
}
在静态链表的表尾追加一个新结点
int Append ( SLinkList SL,ListData x ) {
if ( SL.newptr == -1 ) return 0; //追加失败
int q = SL.newptr; //分配结点
SL.newptr = SL.Nodes[SL.newptr].link;
SL.Nodes[q].data = x;
SL.Nodes[q].link = NULL;
int p = 0; //查找表尾
while ( SL.Nodes[p].link != -1 )
p = SL.Nodes[p].link;
SL.Nodes[p].link = q; //追加
return 1;
}
在静态链表中查找 第 i 个 结点
int Locate ( SLinkList SL,int i ) {
if ( i < 0 ) return -1; //参数不合理
int j = 0,p = SL.Nodes[0].link;
while ( p != -1 && j < i ) {
//循链查找第 i 号结点
p = SL.Nodes[p].link;
j++;
}
if ( i == 0 ) return 0;
return p;
}
在静态链表 第 i 个 结点处插入一个新结点
int Insert ( SLinkList SL,int i,ListData x ) {
int p = Locate ( SL,i-1 );
if ( p == -1 ) return 0; //找不到结点
int q = SL.newptr; //分配结点
SL.newptr = SL.Nodes[SL.newptr].link;
SL.Nodes[q].data = x;
SL.Nodes[q].link = SL.Nodes[p].link;
SL.Nodes[p].link = q; //插入
return 1;
}
在静态链表中释放 第 i 个 结点
int Remove ( SLinkList SL,int i ) {
int p = Locate ( SL,i-1 );
if ( p == -1 ) return 0; //找不到结点
int q = SL.Nodes[p].link; //第 i 号结点
SL.Nodes[p].link = SL.Nodes[q].link;
SL.Nodes[q].link = SL.newptr; //释放
SL.newptr = q;
return 1;
}
循环链表 (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;
}
静态链表结构
静态链表定义
const int MaxSize = 100; //静态链表大小
typedef int ListData;
typedef struct node { //静态链表结点
ListData data;
int link;
} SNode;
typedef struct { //静态链表
SNode Nodes[MaxSize];
int newptr; //当前可分配空间首地址
} SLinkList;
将链表空间初始化
void InitList ( SLinkList SL ) {
SL.Nodes[0].link = -1;
SL.newptr = 1; //当前可分配空间 从 1 开始
//建立带表头结点的空链表
for ( int i = 1; i < MaxSize-1; i++ )
SL.Nodes[i].link = i+1;
//构成空闲链接表
SL.Nodes[MaxSize-1].link = -1;
//链表收尾
}
在静态链表中查找具有给定值的结点
int Find ( SLinkList SL,ListData x ) {
int p = SL.Nodes[0].link;
//指针 p 指向链表第一个结点
while ( p != -1 )
if ( SL.Nodes[p].data != x)
p = SL.Nodes[p].link;
else break;
//逐个结点检测查找具有给定值的结点
return p;
}
在静态链表的表尾追加一个新结点
int Append ( SLinkList SL,ListData x ) {
if ( SL.newptr == -1 ) return 0; //追加失败
int q = SL.newptr; //分配结点
SL.newptr = SL.Nodes[SL.newptr].link;
SL.Nodes[q].data = x;
SL.Nodes[q].link = NULL;
int p = 0; //查找表尾
while ( SL.Nodes[p].link != -1 )
p = SL.Nodes[p].link;
SL.Nodes[p].link = q; //追加
return 1;
}
在静态链表中查找 第 i 个 结点
int Locate ( SLinkList SL,int i ) {
if ( i < 0 ) return -1; //参数不合理
int j = 0,p = SL.Nodes[0].link;
while ( p != -1 && j < i ) {
//循链查找第 i 号结点
p = SL.Nodes[p].link;
j++;
}
if ( i == 0 ) return 0;
return p;
}
在静态链表 第 i 个 结点处插入一个新结点
int Insert ( SLinkList SL,int i,ListData x ) {
int p = Locate ( SL,i-1 );
if ( p == -1 ) return 0; //找不到结点
int q = SL.newptr; //分配结点
SL.newptr = SL.Nodes[SL.newptr].link;
SL.Nodes[q].data = x;
SL.Nodes[q].link = SL.Nodes[p].link;
SL.Nodes[p].link = q; //插入
return 1;
}
在静态链表中释放 第 i 个 结点
int Remove ( SLinkList SL,int i ) {
int p = Locate ( SL,i-1 );
if ( p == -1 ) return 0; //找不到结点
int q = SL.Nodes[p].link; //第 i 号结点
SL.Nodes[p].link = SL.Nodes[q].link;
SL.Nodes[q].link = SL.newptr; //释放
SL.newptr = q;
return 1;
}
循环链表 (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
顺序表与链表的比较
基于时间的比较
? 存取方式
? 顺序表可以 随机存取,也可以 顺序存取
? 链表是 顺序存取 的
? 插入 /删除时移动元素个数
? 顺序表平均需要移动近一半元素
? 链表不需要移动元素，只需要修改指针
? 若插入 /删除仅发生在表的两端，宜采
用带尾指针的循环链表
