第二章 线性表
线性表
顺序表
链表
顺序表与链表的比较线性表定义,n（?0） 个数据元素的有限序列，记作
（ a1,… ai-1,ai,ai+1,…,an）
其中,ai是表中数据元素,n 是表长度。
特点,
同一线性表中元素具有相同特性。
相邻数据元素之间存在序偶关系。
除第一个元素外，其他每一个元素有一个且仅有一个直接前驱。
除最后一个元素外，其他每一个元素有一个且仅有一个直接后继。
顺序表定义,将线性表中的元素相继存放在一个连续的存储空间中。
存储结构,数组。
特点,线性表的顺序存储方式。
存取方式,顺序存取顺序存储结构示意图
45 89 90 67 40 78
0 1 2 3 4 5
顺序表的存储方式：
LOC(a i+1) = LOC( a i )+(i-1)*l
LOC(a i) = LOC(a1)+(i-1)*l
a1 a2 … a i … … … an
1 2 … i … … … n
a a+l … a+(i -1)*l … … … a+(n -1)*l idle
顺序表（ SeqList） 的类型定义
#define ListSize 100 //最大允许长度
typedef int ListData;
typedef struct {
ListData * data; //存储空间基址
int length; //当前元素个数
}
顺序表基本运算
初始化
void InitList ( SeqList & L ) {
L.data = ( ListData * ) malloc
( ListSize * sizeof ( ListData ) );
if ( L.data == NULL ) {
printf (,存储分配失败 !\n” );
exit (1);
}
L.length = 0;
}
按值查找,找 x在表中的位置，若查找成功，
返回表项的位置，否则返回 -1
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;
}
按值查找,判断 x是否在表中
int IsIn ( SeqList &L,ListData x )
{ int i = 0,found=0;
while ( i < L.length &&!found )
if(L.data[i] != x ) i++;
else found=1;
return found;
}
求表的长度
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 Next ( SeqList &L,ListData x ) {
int i = Find(x);
if ( i >0 && i < L.length ) return i+1;
else return -1;
}
寻找 x的前驱
int Next ( SeqList &L,ListData x ) {
int i = Find(x);
if ( i >0 && i < L.length ) return i-1;
else return -1;
}
插入
22
1)(
1)(
1
0)1(
0 1
1
)(
1
1
=
nnn
n
n
n
i n
in
n
A M N
25 34 57 16 48 09 63
0 1 2 3 4 5 6 7
50插入 x
25 34 57 50 16 48 09 63
0 1 2 3 4 5 6 7
50
i
顺序表插入时，平均数据移动次数 AMN在各表项插入概率相等时
顺序表的插入
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 6316
删除 x
25 34 57 50 48 09 63
0 1 2 3 4 5 6 7
顺序表删除平均数据移动次数 AMN在各表项删除概率相等时
顺序表的删除
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)
定义,用一组 地址任意 的存储单元存放线性表中的数据元素。
数据域 指针域
ZHANG 13
WANG 1
LI null
ZHAO 37
WU 7
ZHOU 19
SUN 25
存储地址
1
7
13
19
25
31
37
31
头指针每个元素由结点 (Node)构成,它包括两个域,数据域 Data和指针域 Link
data link
存储结构,链式存储结构特点,存储单元可以不连续。
存取方式,顺序存取。
Node
单链表结构
单链表的类型定义
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；
p
(插入前 ) (插入后 )
newnode newnode
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;//新结点成为第一个结点
if(first==NULL)last=newnode;//若是空表，表尾指针指向新结点
first = newnode;
}
else {//插在表中间或末尾
newnode->link = p->link;
if(p->link ==NULL)last=newnode;
p->link = newnode;
}
return 1;
}
删除在单链表中删除 ai结点
q = p->link;
p->link = q->link;
删除前删除后?ai-1 ai ai+1
p q
p
ai-1 ai+1ai
int Delete ( LinkList& first,int i ) {
//在链表中删除第 i 个结点
ListNode *p,*q;
if ( i == 0 ) //删除表中第 1 个结点
{ q = first; first = first->link; }
else {
p = first; int k = 0;
while ( p != NULL && k < i-1 )
{ p = p->link; k++; } //找第 i-1个结点
if ( p == NULL || p->link == NULL ) {//找不到第
i-1个结点
printf (,无效的删除位置 !\n” );
return 0;
}
else {//删除中间结点或尾结点元素
q = p->link;
p->link = q->link;
}
if (q==last) last=p;//删除表尾结点
k= q->data; free ( q ); return k; //取出被删结点数据并释放 q
}
}
带 表头结点 的单链表
表头结点 位于表的最前端，本身不带数据，仅标志表头。
设置表头结点的目的,
简化链表操作的实现。
非空表 空表
^ana1first first ^
插入
q->link = p->link;
p->link = q;
first
q
first
q
first
q
^ first
q ^
p p
p p
插入前 插入后
q q
插入p p
int Insert (LinkList first,ListData x,int i ) {
//将新元素 x 插入在链表中第 i 号结点位置
ListNode * p = Locate ( first,i-1 );
if ( p == NULL ) return 0; //参数 i值不合理返回 0
ListNode * newnode = //创建新结点
(ListNode *) malloc (sizeof (ListNode) );
newnode->data = x;
newnode->link = p->link; //链入
p->link = newnode;
return 1;
}
删除 q = p->link;
p->link = q->link;
delete q;
删除前
first
(非空表） (空表）
first
^
first
p q
^
p q
first
删除后
int delete ( LinkList first,int i ) {
//将链表第 i 号元素删去
ListNode * p,* q
p = Locate ( first,i-1 ); //寻找第 i-1个 结点
if ( p == NULL || p->link == NULL)
return 0;//i值不合理或空表
q = p->link;
p->link = q->link; //删除结点
free ( q ); //释放
return 1;
}
前插法建立单链表
从一个空表开始，重复读入数据：
生成新结点
将读入数据存放到新结点的数据域中
将该新结点插入到链表的前端
直到读入结束符为止。
first
q
first
q
^
^
LinkList createListF ( void ) {
char ch; ListNode *q;
LinkList head = //建立表头结点
(LinkList) malloc (sizeof (ListNode));
head->link = NULL;
while ( (ch = getchar( ) ) !=?\n? ) {
q = (listNode *) malloc (sizeof(ListNode));
q->data = ch; //建立新结点
q->link = head->link; //插入到表前端
head->link = q;
}
return head;
}
后插法建立单链表
每次将新结点加在链表的表尾；
尾指针 r,总是指向表中最后一个结点，新结点插在它的后面；
^
q
first ^
r
^first ^
r
LinkList createListR ( void ) {
char ch;
LinkList head = //建立表头结点
(LinkList) malloc (sizeof (ListNode));
ListNode *q,*r = NULL;
while ( (ch = getchar( ) ) !=?\n? ) {
q = (listNode *) malloc (sizeof(ListNode));
q->data = ch; //建立新结点
r ->link = q; r =q; //插入到表末端
}
r ->link = NULL;
return head;
}
单链表清空
void makeEmpty ( LinkList first ) {
//删去链表中除表头结点外的所有其它结点
ListNode *q;
while ( first->link != NULL ) {//当链不空时，循环逐个删去所有结点
q = first->link; first->link = q->link;
free( q ); //释放
}
last=first;
}
计算单链表长度
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;
ListNode * p = first; int k = 0;
while ( p != NULL && k < i )
{ p = p->link; k++; } //找第 i 个结点
if ( k == i ) return p; //返回第 i 个结点地址
else return NULL;
}
1
ZHANG 2
WANG 6
LI 5
ZHAO 5
WU -1
CHEN 3
1
ZHANG 2
WANG 3
LI 4
ZHAO 5
WU -1
0
1
2
3
4
5
6
0
1
2
3
4
5
6
修改前 （插入 chen,删除 zhao)修改后用一维数组描述线性链表静态链表
定义
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;
}
在静态链表中查找第 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，而是指向头结点。只要已知表中某一结点的地址，
就可搜寻所有结点的地址 。
存储结构,链式存储结构带表头结点的循环链表
an-1first a1a0
first
(空表 )
(非空表 )
循环链表的插入约瑟夫问题
用循环链表求解约瑟夫问题
n 个人围成一个圆圈，首先第 2个人从 1开始一个人一个人顺时针报数,报到第 m个人，令其出列。然后再从下一个人开始，从 1顺时针报数，
报到第 m个人，再令其出列,…,如此下去,
直到圆圈中只剩一个人为止。此人即为优胜者。
例如 n = 3 m = 8
约瑟夫问题的解法
#include <iostream.h>
#include,CircList.h”
void Josephus ( int n,int m ) {
for ( int i=0; i<n-1; i++ ) { //执行 n-1次
for ( int j=0; j<m-1; j++ ) Next ( );
cout <<,Delete person,<<
getData ( ) << endl; //数 m-1个人
Remove ( ); //删去
}
}
void main ( ) {
CircList<int> clist;
int n,m;
cout <<,Enter the Number of Contestants?”;
cin >> n >> m;
for ( int i=1; i<=n; i++ ) clist.insert (i); //形成约瑟夫环
clist.Josephus (n,m); //解决约瑟夫问题
}
多项式及其相加
在多项式的链表表示中每个结点增加了一个数据成员 link，作为链接指针。
优点是：
– 多项式的项数可以动态地增长，不存在存储溢出问题。
– 插入、删除方便，不移动元素。
多项式链表的相加
AH = 1 - 10x6 + 2x8 +7x14
BH = - x4 + 10x6 - 3x10 + 8x14 +4x18
Polynomial operator + ( const Polynomial
& ah,const Polynomial & bh ) {
Term *pa,*pb,*pc,*p;
ListIterator<Element> Aiter ( ah.poly );
ListIterator<Element> Biter ( bh.poly );
//建立两个多项式对象 Aiter,Biter
pa = pc = Aiter.First ( ); // pa 检测指针
pb = Biter.First ( ); // pb 检测指针
pa = Aiter.Next ( ); pb = Biter.Next( );
// pa,pb 越过表头结点
delete pb;
while ( Aiter.NotNull ( ) && Biter.NotNull ( ) )
switch ( compare ( pa→exp,pb→exp ) ) {
case '=',
pa→coef = pa→coef + pb→coef;
p = pb; pb = Biter.Next ( ); delete p;
if ( !pa→coef ) {
p = pa; pa = Aiter.Next ( );
delete p;
}
else {
pc→link = pa; pc = pa;
pa = Aiter.Next ( );
}
break;
case '<',
pc→next = pb; pc = pb;
pb = Biter.Next ( ); break;
case '>',
pc→next = pa; pc = pa;
pa = Aiter.Next ( );
}
if ( Aiter.NotNull ( ) ) pc→next = pa;
else pc→next = pb;
}
双向链表 (Doubly Linked List)
双向链表结点结构,
prior data next
指向直接前驱 指向直接 后继非空表 空表
firstfirst
双向循环链表的定义
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;
}
双向循环链表的插入 (非空表 )
q->prior = p;
q->next = p->next;
p->next = q;
q->next->prior = q;
在结点 *p 后插入 25
first
first
31 48 15
p
p
31 48 25 15
q
双向循环链表的插入 (空表 )
q->prior = p;
q->next = p->next;
p->next = q;
q->next->prior = q;
p q
first 25first
p
在结点 *p 后插入 25
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;
}
双向循环链表的删除
p->next->prior = p->prior;
p->prior->next = p->next;
(非空表 )
删除 48
first
first
31 48 15
p
31 15
双向循环链表的删除
p->next->prior = p->prior;
p->prior->next = p->next;
first31
p删除 31
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
顺序表与链表的比较基于时间的比较
存取方式
顺序表可以随机存取，也可以顺序存取
链表是顺序存取的
插入 /删除时移动元素个数
顺序表平均需要移动近一半元素
链表不需要移动元素，只需要修改指针结 束
线性表
顺序表
链表
顺序表与链表的比较线性表定义,n（?0） 个数据元素的有限序列，记作
（ a1,… ai-1,ai,ai+1,…,an）
其中,ai是表中数据元素,n 是表长度。
特点,
同一线性表中元素具有相同特性。
相邻数据元素之间存在序偶关系。
除第一个元素外，其他每一个元素有一个且仅有一个直接前驱。
除最后一个元素外，其他每一个元素有一个且仅有一个直接后继。
顺序表定义,将线性表中的元素相继存放在一个连续的存储空间中。
存储结构,数组。
特点,线性表的顺序存储方式。
存取方式,顺序存取顺序存储结构示意图
45 89 90 67 40 78
0 1 2 3 4 5
顺序表的存储方式：
LOC(a i+1) = LOC( a i )+(i-1)*l
LOC(a i) = LOC(a1)+(i-1)*l
a1 a2 … a i … … … an
1 2 … i … … … n
a a+l … a+(i -1)*l … … … a+(n -1)*l idle
顺序表（ SeqList） 的类型定义
#define ListSize 100 //最大允许长度
typedef int ListData;
typedef struct {
ListData * data; //存储空间基址
int length; //当前元素个数
}
顺序表基本运算
初始化
void InitList ( SeqList & L ) {
L.data = ( ListData * ) malloc
( ListSize * sizeof ( ListData ) );
if ( L.data == NULL ) {
printf (,存储分配失败 !\n” );
exit (1);
}
L.length = 0;
}
按值查找,找 x在表中的位置，若查找成功，
返回表项的位置，否则返回 -1
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;
}
按值查找,判断 x是否在表中
int IsIn ( SeqList &L,ListData x )
{ int i = 0,found=0;
while ( i < L.length &&!found )
if(L.data[i] != x ) i++;
else found=1;
return found;
}
求表的长度
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 Next ( SeqList &L,ListData x ) {
int i = Find(x);
if ( i >0 && i < L.length ) return i+1;
else return -1;
}
寻找 x的前驱
int Next ( SeqList &L,ListData x ) {
int i = Find(x);
if ( i >0 && i < L.length ) return i-1;
else return -1;
}
插入
22
1)(
1)(
1
0)1(
0 1
1
)(
1
1
=
nnn
n
n
n
i n
in
n
A M N
25 34 57 16 48 09 63
0 1 2 3 4 5 6 7
50插入 x
25 34 57 50 16 48 09 63
0 1 2 3 4 5 6 7
50
i
顺序表插入时，平均数据移动次数 AMN在各表项插入概率相等时
顺序表的插入
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 6316
删除 x
25 34 57 50 48 09 63
0 1 2 3 4 5 6 7
顺序表删除平均数据移动次数 AMN在各表项删除概率相等时
顺序表的删除
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)
定义,用一组 地址任意 的存储单元存放线性表中的数据元素。
数据域 指针域
ZHANG 13
WANG 1
LI null
ZHAO 37
WU 7
ZHOU 19
SUN 25
存储地址
1
7
13
19
25
31
37
31
头指针每个元素由结点 (Node)构成,它包括两个域,数据域 Data和指针域 Link
data link
存储结构,链式存储结构特点,存储单元可以不连续。
存取方式,顺序存取。
Node
单链表结构
单链表的类型定义
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；
p
(插入前 ) (插入后 )
newnode newnode
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;//新结点成为第一个结点
if(first==NULL)last=newnode;//若是空表，表尾指针指向新结点
first = newnode;
}
else {//插在表中间或末尾
newnode->link = p->link;
if(p->link ==NULL)last=newnode;
p->link = newnode;
}
return 1;
}
删除在单链表中删除 ai结点
q = p->link;
p->link = q->link;
删除前删除后?ai-1 ai ai+1
p q
p
ai-1 ai+1ai
int Delete ( LinkList& first,int i ) {
//在链表中删除第 i 个结点
ListNode *p,*q;
if ( i == 0 ) //删除表中第 1 个结点
{ q = first; first = first->link; }
else {
p = first; int k = 0;
while ( p != NULL && k < i-1 )
{ p = p->link; k++; } //找第 i-1个结点
if ( p == NULL || p->link == NULL ) {//找不到第
i-1个结点
printf (,无效的删除位置 !\n” );
return 0;
}
else {//删除中间结点或尾结点元素
q = p->link;
p->link = q->link;
}
if (q==last) last=p;//删除表尾结点
k= q->data; free ( q ); return k; //取出被删结点数据并释放 q
}
}
带 表头结点 的单链表
表头结点 位于表的最前端，本身不带数据，仅标志表头。
设置表头结点的目的,
简化链表操作的实现。
非空表 空表
^ana1first first ^
插入
q->link = p->link;
p->link = q;
first
q
first
q
first
q
^ first
q ^
p p
p p
插入前 插入后
q q
插入p p
int Insert (LinkList first,ListData x,int i ) {
//将新元素 x 插入在链表中第 i 号结点位置
ListNode * p = Locate ( first,i-1 );
if ( p == NULL ) return 0; //参数 i值不合理返回 0
ListNode * newnode = //创建新结点
(ListNode *) malloc (sizeof (ListNode) );
newnode->data = x;
newnode->link = p->link; //链入
p->link = newnode;
return 1;
}
删除 q = p->link;
p->link = q->link;
delete q;
删除前
first
(非空表） (空表）
first
^
first
p q
^
p q
first
删除后
int delete ( LinkList first,int i ) {
//将链表第 i 号元素删去
ListNode * p,* q
p = Locate ( first,i-1 ); //寻找第 i-1个 结点
if ( p == NULL || p->link == NULL)
return 0;//i值不合理或空表
q = p->link;
p->link = q->link; //删除结点
free ( q ); //释放
return 1;
}
前插法建立单链表
从一个空表开始，重复读入数据：
生成新结点
将读入数据存放到新结点的数据域中
将该新结点插入到链表的前端
直到读入结束符为止。
first
q
first
q
^
^
LinkList createListF ( void ) {
char ch; ListNode *q;
LinkList head = //建立表头结点
(LinkList) malloc (sizeof (ListNode));
head->link = NULL;
while ( (ch = getchar( ) ) !=?\n? ) {
q = (listNode *) malloc (sizeof(ListNode));
q->data = ch; //建立新结点
q->link = head->link; //插入到表前端
head->link = q;
}
return head;
}
后插法建立单链表
每次将新结点加在链表的表尾；
尾指针 r,总是指向表中最后一个结点，新结点插在它的后面；
^
q
first ^
r
^first ^
r
LinkList createListR ( void ) {
char ch;
LinkList head = //建立表头结点
(LinkList) malloc (sizeof (ListNode));
ListNode *q,*r = NULL;
while ( (ch = getchar( ) ) !=?\n? ) {
q = (listNode *) malloc (sizeof(ListNode));
q->data = ch; //建立新结点
r ->link = q; r =q; //插入到表末端
}
r ->link = NULL;
return head;
}
单链表清空
void makeEmpty ( LinkList first ) {
//删去链表中除表头结点外的所有其它结点
ListNode *q;
while ( first->link != NULL ) {//当链不空时，循环逐个删去所有结点
q = first->link; first->link = q->link;
free( q ); //释放
}
last=first;
}
计算单链表长度
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;
ListNode * p = first; int k = 0;
while ( p != NULL && k < i )
{ p = p->link; k++; } //找第 i 个结点
if ( k == i ) return p; //返回第 i 个结点地址
else return NULL;
}
1
ZHANG 2
WANG 6
LI 5
ZHAO 5
WU -1
CHEN 3
1
ZHANG 2
WANG 3
LI 4
ZHAO 5
WU -1
0
1
2
3
4
5
6
0
1
2
3
4
5
6
修改前 （插入 chen,删除 zhao)修改后用一维数组描述线性链表静态链表
定义
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;
}
在静态链表中查找第 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，而是指向头结点。只要已知表中某一结点的地址，
就可搜寻所有结点的地址 。
存储结构,链式存储结构带表头结点的循环链表
an-1first a1a0
first
(空表 )
(非空表 )
循环链表的插入约瑟夫问题
用循环链表求解约瑟夫问题
n 个人围成一个圆圈，首先第 2个人从 1开始一个人一个人顺时针报数,报到第 m个人，令其出列。然后再从下一个人开始，从 1顺时针报数，
报到第 m个人，再令其出列,…,如此下去,
直到圆圈中只剩一个人为止。此人即为优胜者。
例如 n = 3 m = 8
约瑟夫问题的解法
#include <iostream.h>
#include,CircList.h”
void Josephus ( int n,int m ) {
for ( int i=0; i<n-1; i++ ) { //执行 n-1次
for ( int j=0; j<m-1; j++ ) Next ( );
cout <<,Delete person,<<
getData ( ) << endl; //数 m-1个人
Remove ( ); //删去
}
}
void main ( ) {
CircList<int> clist;
int n,m;
cout <<,Enter the Number of Contestants?”;
cin >> n >> m;
for ( int i=1; i<=n; i++ ) clist.insert (i); //形成约瑟夫环
clist.Josephus (n,m); //解决约瑟夫问题
}
多项式及其相加
在多项式的链表表示中每个结点增加了一个数据成员 link，作为链接指针。
优点是：
– 多项式的项数可以动态地增长，不存在存储溢出问题。
– 插入、删除方便，不移动元素。
多项式链表的相加
AH = 1 - 10x6 + 2x8 +7x14
BH = - x4 + 10x6 - 3x10 + 8x14 +4x18
Polynomial operator + ( const Polynomial
& ah,const Polynomial & bh ) {
Term *pa,*pb,*pc,*p;
ListIterator<Element> Aiter ( ah.poly );
ListIterator<Element> Biter ( bh.poly );
//建立两个多项式对象 Aiter,Biter
pa = pc = Aiter.First ( ); // pa 检测指针
pb = Biter.First ( ); // pb 检测指针
pa = Aiter.Next ( ); pb = Biter.Next( );
// pa,pb 越过表头结点
delete pb;
while ( Aiter.NotNull ( ) && Biter.NotNull ( ) )
switch ( compare ( pa→exp,pb→exp ) ) {
case '=',
pa→coef = pa→coef + pb→coef;
p = pb; pb = Biter.Next ( ); delete p;
if ( !pa→coef ) {
p = pa; pa = Aiter.Next ( );
delete p;
}
else {
pc→link = pa; pc = pa;
pa = Aiter.Next ( );
}
break;
case '<',
pc→next = pb; pc = pb;
pb = Biter.Next ( ); break;
case '>',
pc→next = pa; pc = pa;
pa = Aiter.Next ( );
}
if ( Aiter.NotNull ( ) ) pc→next = pa;
else pc→next = pb;
}
双向链表 (Doubly Linked List)
双向链表结点结构,
prior data next
指向直接前驱 指向直接 后继非空表 空表
firstfirst
双向循环链表的定义
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;
}
双向循环链表的插入 (非空表 )
q->prior = p;
q->next = p->next;
p->next = q;
q->next->prior = q;
在结点 *p 后插入 25
first
first
31 48 15
p
p
31 48 25 15
q
双向循环链表的插入 (空表 )
q->prior = p;
q->next = p->next;
p->next = q;
q->next->prior = q;
p q
first 25first
p
在结点 *p 后插入 25
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;
}
双向循环链表的删除
p->next->prior = p->prior;
p->prior->next = p->next;
(非空表 )
删除 48
first
first
31 48 15
p
31 15
双向循环链表的删除
p->next->prior = p->prior;
p->prior->next = p->next;
first31
p删除 31
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
顺序表与链表的比较基于时间的比较
存取方式
顺序表可以随机存取，也可以顺序存取
链表是顺序存取的
插入 /删除时移动元素个数
顺序表平均需要移动近一半元素
链表不需要移动元素，只需要修改指针结 束
