第 2章 线性表
数据结构（ C++描述）
目录
2.1 线性表的定义及其运算
2.2线性表的顺序存储结构
２,３ 线性 表的链式存贮结构
结束放演
2.1 线性表的定义及其运算
2.1.1线性表的定义
1,线性表的定义
线性表 （ linear list） 是 n（ n≥0） 个数据元素 a1,a2,… an组
成的有限序列 。 其中 n 称为数据元素的个数或线性表的长
度, 当 n=0时称为空表, n>0时称为非空表 。 通常将非空的
线性表记为 （ a1,a2,…,an）, 其中的数据元素 ai（ 1≤i≤n）
是一个抽象的符号, 其具体含义在不同情况下是不同的,
即它的数据类型可以根据具体情况而定, 本书中, 我们将
它的类型设定为 elemtype,表示某一种具体的已知数据类
型 。
2,线性表的特征
从线性表的定义可以看出线性表的特征：
（ 1 ） 有且仅有一个开始结点 (表头结点 )a1,它没
有直接前驱, 只有一个直接后继 ;
（ 2） 有且仅有一个终端结点 (表尾结点 )an,它没有
直接后继, 只有一个直接前驱 ;
（ 3） 其它结点都有一个直接前驱和直接后继；
（ 4） 元素之间为一对一的线性关系 。
线性表是一种典型的线性结构, 用二元组表示为：
linear_list=(A,R)
其中
A={ai ∣ 1≤i≤n,n≥0,ai∈ elemtype}
R={r}
r={<ai,ai+1> ∣ 1≤i≤n-1}
对应的逻辑结构图如图 2-1所示。
a 1 a 2 …… a n
图 2 - 1 线性表逻辑结构示意图
2.1.2 线性表的运算
常见线性表的运算有：
1,置空表 SETNULL（ &L） 将线性表 L置成空表
2,求长度 LENGTH（ L） 求给定线性表 L的长度
3,取元素 GET（ L,i） 若 1≤i≤length(L),则取第 i个位
置上的元素, 否则取得的元素为 NULL。
4,求直接前趋 PRI0R（ L,X） 求线性表 L中元素值为 X
的直接前趋, 若 X为第一个元素, 前驱为 NULL。
5,求直接后继 NEXT（ L,X） 求线性表 L中元素值
为 X直接后继, 若 X为最后一个元素, 后继为 NULL。
6,定位函数 LOCATE（ L,X） 在线性表 L中查找
值为 X的元素位置, 若有多个值为 X,则以第一个为
准, 若没有, 位置为 0。
7,插入 INSERT（ &L,X,i） 在线性表 L中第 i个
位置上插入值为 X的元素 。
8,删除 DELETE（ &L,i） 删除线性表 L中第 i个
位置上的元素 。
2.1.3线性表的抽象数据类型描述
上述这些操作可用抽象数据类型描述为：
ADT Linearlist is
Data:
一个线性表 L定义为 L=(a1,a2,…,an),当 L=（ ） 时定义
为一个空表
operation:
void setnull(&L) //将线性表 L置成空表
int Length(L) //求给定线性表 L的长度
elemtype Get(L,i) //取线性表 L第 i个位置上的元素
elemtype Prior(L,x) //求线性表 L中元素值为 X的直接前
趋
elemtype Next(L,x) //求线性表 L中元素值为 X的直接
后继
int Locate(L,x) //在线性表 L中查找值为 X的元素位
置
void Insert(&L,x,i) //在线性表 L中第 i个位置上插入
值为 X的元素
void Delete(&L,i) //删除线性表 L中第 i个位置上的元
素
END Linearlist
例 2-1 假设线性表 L=(23,56,89,76,18),i=3,x=56,y=88,则
对 L的一组操作及结果如下：
Length(L); //所得结果为 5
Get(L,i) //所得结果为 89
Prior(L,x) //所得结果为 23
Next(L,x) //所得结果为 89
Locate(L,x) //所得结果为 2
Insert(&L,y,i) //所得结果为 (23,56,88,89,76,18)
Delete(&L,i+1) //所得结果为 (23,56,88,76,18)
2.2线性表的顺序存储结构
2.2.1 顺序表结构
线性表的顺序存储结构,也称为顺序表 。 其存储方式为：
在内存中开辟一片连续存储空间, 但该连续存储空间
的大小要大于或等于顺序表的长度, 然后让线性表中
第一个元素存放在连续存储空间第一个位置, 第二个
元素紧跟着第一个之后, 其余依此类推 。
假设线性表中元素为 （ a1,a2,…,,an）, 设第一个元
素 a1的内存地址为 LOC(a1)（ 在图 2-2中表示为 b）, 而
每个元素在计算机内占 d个存贮单元,则第 i个元素 ai的
地址为 LOC(ai)=LOC(a1)+(i-1)× d (其中 1≤i≤n)
于是可用 C++语言描述为,
const int maxsize=maxlen； //maxlen表示线性表允
许的最大长度
struct sequenlist
{
elemtype a[maxsize]; //表示线性表 （ a1,a2,…,,an）
int len; //len表示线性表的实际长度
}；
存储地址 内存排列 位置序号
?
a
1
a
2
…
a
i
…
a
n
…
0
1
2
…
i
…
n
…
m ax le n - 1
b
b+d
…
b+ (i - 1) × d
…
b+(n - 1) × d
图 2 - 2 顺序存储结构示意图
2.2.2 顺序表运算
1,求顺序表的长度 length(L)
int length(sequenlist L)
{
return L.len;
}
该算法的语句频度为 1,时间复杂度为 0(1)。
2．插入运算 Insert( &L,x,i)
void Insert(sequenlist &L,elemtype x,int i)
{ int j;
if(L.len>=maxsize-1)
cout<<”overflow”<<endl;
else if ((i<1)||(i>L.len+1)
cout<<”position is not correct!”<<endl;
else { for(j=L.len;j>=i;j--)
L.a[j+1]=L.a[j]; //元素后移
L.a[i]=x; //插入元素
L.len++; //表长度增加 1
}}
0
1
2
3
…
i - 1
i
i+1
…
n
…
m a x si z e - 1
a
1
a
2
a
3
…
a
i - 1
x
a
i
…
a
n - 1
a
n
0
1
2
3
…
i - 1
i
i+1
…
n
…
m a x si z e - 1
a
1
a
2
a
3
…
a
i - 1
a
i
a
i +1
…
a
n
…
序号 内容 序 号 内容
插入前 插入后
图 2 - 3 顺序表中插入元素前后状态
３, 删除运算 Delete(&L,i)
void Delete(sequenlist &L,int i)
{ int j;
if((i<1)||(i>L.len))
cout<<” position is not correct!”<<endl;
else {
for(j=i+1;j<=L.len;j++)
L.a[j-1]=L.a[j]; //元素前移
L.len--; //表长度减 1
} }
0
1
2
3
…
i - 1
i
i+1
…
n - 1
…
m a x si z e - 1
a
1
a
2
a
3
…
a
i - 1
a
i +1
a
i +2
…
a
n
…
0
1
2
3
…
i - 1
i
i+1
…
n
…
m a x si z e - 1
a
1
a
2
a
3
…
a
i - 1
a
i
a
i +1
…
a
n
…
序号 内容 序号 内容
删除前 删除后
图 2 - 4 顺序表中删除元素前后状态
插入算法花费的时间, 主要在于循环中元素的后移
（ 其它语句花费的时间可以省去 ）, 即从插入位置到
最后位置的所有元素都要后移一位, 使空出的位置插
入元素值 x。 但是, 插入的位置是不固定的, 当插入位
置 i=１时, 全部元素都得移动, 需 n次移动, 当 i=n+１
时, 不需移动元素, 故在 i位置插入时移动次数为 n-i+1，
假设在每个位置插入的概率相等为, 则平均移动元
素的次数为
=
故时间复杂度为 O(n)。
同理，可推出删除运算的平均移动次数为,
故时间复杂度为 O(n)。
11?n
??? ? ??11 11 )]1([ni n in
2
n
21?n
4,置空表 setnull(&L)
void setnull(sequenlist &L)
{
L.len=0;
}
该算法的时间复杂度为 O(1)。
5,定位算法 Locate(L,x)
int Locate(sequenlist L,elemtype x)
{ int j=1;
while(j<=L.len)&&(L.a[j]!=x)
j++;
if(j<=L.len) return j;
else return 0;
}
该算法的时间复杂度为 O(n)。
6,取元素 Get(L,i)
elemtype Get(sequenlist L,int i)
{
if(i<1)||(i>L.len) return NULL;
else return L.a[i];
}
该算法的时间复杂度为 O(1)。
2.2.3 顺序表存储空间的动态分配
若将前面线性表的顺序存储结构类型中的数组形式改为
指针形式, 则得到动态分配形式如下：
struct sequenlist
{
elemtype *a;
int len;
};
在此时, 只有线性表置空表算法需要修改, 其它算法都
与静态分配相同 。 这时的置空表算法应改为：
void setnull(sequenlist &L)
{
L.a=new elemtype[maxsize]; //动态申请存储单元
if(L.a==NULL) //申请不成功
exit(1);
L.len=0;
}
２,３ 线性表的链式存贮结构
线性表的链式存贮结构, 也称为链表 。 其存贮方式是：
在内存中利用存贮单元 (可以不连续 )来存放元素值及它在
内存的地址, 各个元素的存放顺序及位置都可以以任意
顺序进行, 原来相邻的元素存放到计算机内存后不一定
相邻, 从一个元素找下一个元素必须通过地址 (指针 )才能
实现 。 故不能像顺序表一样可随机访问, 而只能按顺序
访问 。 常用的链表有单链表, 循环链表和双向链表, 多
重链表等 。
２,３,１ 单链表结构
在定义的链表中, 若只含有一个指针域来存放下一个
元素地址, 称这样的链表为单链表或线性链表 。
线性链表中的结点结构可描述为,
D a ta n e x t
n e x t
其中 data 域用来存放结点本身信息, 类型由具体问题
而定, 本书中, 我们也将其设定为 elemtype类型, 表
示某一种具体的已知类型, next域用来存放下一个元
素地址 。
a
2
1 8 0
a
4
1 7 0
a
6
N U L L
a
1
1 1 0
a
5
1 4 0
a
3
1 3 0
150
地址 data 域 next 域
1 10
120
130
140
150
160
170
180
head
头指针
图 2 - 5 单链表示意图
a 1 a 2 a 3 a 4 a 5 a 6 ^
图２ - 6 单链表的逻辑表示
单链表可用Ｃ ++描述为,
struct link
{ elemtype data; //元素类型
link *next; //指针类型,存放下一个元素地址
}
( a ) 不带头结点的单链表
a 1 h e a d a 2 …… a n ^
( b ) 带头结点的单链表
h e a d …… a n ^ 头 a 1
a
2
图 2 - 7 不带头结点和带头结点的单链表
2,3,2单链表运算
１, 头插法建立单链表 (从左边插入结点 )
link *hcreat( )
{ link *s,*p; int i;
cin>>i; //输入结点数值, 为 0时算法结束
p=NULL;
while(i)
{ s=new link; s->data=i;
s->next=p; p=s;
cin>>i; }
return p;
}
2,尾插法建立单链表 (从右边插入结点 )
link *rcreat( )
{ link *s,*r,*p; int i;
p=r=new link; p->next=NULL;
cin>>i;
while(i)
{ s=new link; s->data=i;
r->next=s; r=s;
cin>>i; }
r->next=NULL; return p; }
3,单链表上的查找运算
(1) 按值查找 Locate(head,x)
在单链表 head中, 查找值为 x的结点, 若找到, 返回它的
地址, 否则返回 NULL。
(2) 按序号查找 get(head,i)
在单链表 head中查找第 i个位置上的元素, 若找到,
则返回它的地址, 否则返回 NULL。
Link *Locate(link *head,elemtype x)
{ link *p;
p=head->next;
while((p!=NULL)&&(p->data!=x))
p=p->next;
return p;
}
算法的时间复杂度都为Ｏ (n)。
Link *get(link *head,int i)
{ int j; link *p;
j=1; p=head->next;
while((j<i)&&(p!=NULL)
{ j++;
p=p->next; }
return p;
}
算法的时间复杂度都为Ｏ (n)。
4,单链表上的插入运算
若将 x插入 a和 b 之间，插入结点的指针变化如图２ -8
所示。
① ②
s
a b
x
p
?
图 2 - 8 插入结点时的指针修改
void insert(link *head,elemtype x,elemtype y)
//在头指针 head所指单链表中,在值为 y的结点之后插入
值为 x的结点
{ link *p,*s;
s=new link; s->data=x;
if(head->next==NULL) //链表为空
{ head->next=s; s->next=NULL; }
p=Locate(head,y) //调用查找算法
if(p==NULL) cout<<”插入位置非法, ;
else { s->next=p->next;
p->next=s; } }
５, 单链表上的删除运算
若将 x删除，删除结点的指针变化如图 2-9所示。
p q
? a 1 x a 2
图 2 - 9 删除结点的指针修改
void delete(link *head,elemtype x)
//在 head为头指针的单链表中,删除值为 x的结点
{ link *p,*q;
q=head; p=head->next;
while(p!=NULL)&&(p->data!=x)
{ q=p; p=p->next; }
if(p==NULL) cout<<“要删除的结点不存在, ；
else { q->next=p->next; delete(p);
} }
６,输出单链表
若需将单链表按逻辑顺序输出 (见图２ -10)，则必须从头
到尾访问单链表中每一个结点，
a n ^ …… 头 a 1 head a 2
( a ) 单链表示意图
a
1 a 2 a
n
……
( b ) 单链表输出结果示意图
图 2 - 10 单链表按逻辑结构输出示意图
void print(link *head)
{ link *p;
p=head->next;
while(p->next!=NULL)
{ cout<<p->data<<”->”; //输出表中非最后一个元
素
p=p->next; }
cout<<p->data; //输出表中最后一个元素
cout<<endl;
}
２,３,３ 循环链表结构
单链表上的访问是一种顺序访问，从其中某一个结点出
发，可以找到它的直接后继，但无法找到它的直接前驱。
因此，我们可以考虑建立这样的链表，具有单链表的特
征，但又不需要增加额外的存贮空间，仅对表的链接方
式稍作改变，使得对表的处理更加方便灵活。从单链表
可知，最后一个结点的指针域为 NULL表示单链表已经
结束。如果将单链表最后一个结点的指针域改为存放链
表中头结点 (或第一个结点 )的地址，就使得整个链表构
成一个环，又没有增加额外的存贮空间，称这们的链表
为单循环链表，在不引起混淆时称为循环表 (后面还要
提到双向循环表 )
循环链表上的运算与单链表上运算基本一致, 区别只
在于最后一个结点的判断 (即循环的条件不同 ),但利
用循环链表实现某些运算较单链表方便 (从某个结点
出发能求出它的直接前驱, 而单链表是不行的, 只能
从头出发 )。
头 a 1 a 2
…… a
n
head
(b) 非空循环表
图 2 - 11 带头结的单循环链表示意图
(a ) 空循环表
头
head
2.3.4 双向链表结构
1,双向链表基本概念
在单链表中, 从某个结点出发可以直接找到它的直接后
继, 时间复杂度为 O(1), 但无法直接找到它的直接前驱；
在单循环链表中, 从某个结点出发可以直接找到它的直
接后继, 时间复杂仍为 O(1),直接找到它的直接前驱,
时间复杂为 O(n)。 有时, 希望能快速找到一个结点的直
接前驱, 这时, 可以在单链表中的结点中增加一个指针
域指向它的直接前驱, 这样的链表, 就称为双向链表 (一
个结点中含有两个指针 )。 如果每条链构成一个循环链表,
则会得双向循环链表 。
双向链表可用 C++描述如下：
struct dulink
{
elemtype data; //结点的数据域,类型设定为
elemtype
dulink *next,*prior; //定义指向直接后继和直接前驱
的指针
}
^
头
a 1
a 2
a n
^
尾
……
……
h e a d
r e a r
( a ) 双向链表示意图
头
a 1
a 2
a n
尾
……
……
h e a d
r e a r
( b ) 双向循环链表示意图
图 2 - 1 5 双向链表及循环链表示意图
2,双向链表插入运算 duinsert (head,x,y)
在 head为头指针的双向链表中，在值为 Y的结点之后
插入值为 X的结点，插入结点的指针变化见图 2-16(若
改为在值为 Y的结点之前插入值为 X的结点，可以作
类似分析 )。
图 2 - 1 6 S 插入 P 之后指针变化示意图
④
X
Y
②
①
③
?
?
s
p
插入算法描述为：
void duinsert(dulink *head,elemtype x,elemtype y)
{ dulink *p,*s;
s=new dulink; //申请待插入的结点
s->data=x; p=head;
while(p!=NULL)&&(p->data!=y) //用循环查找值为
y的结点
p=p->next;
if (p!=NULL) //已找到插入位置
{ s->next=p->next; p->next->prior=s;
s->prior=p; p->next=s; }
else cout<<”插入位置不存在, ; }
3 。 双向链表的删除运算 dudelete(head,x)
在以 head为头的双向链表中删除值为 x的结点，删
除算法的指针变化见图 2-17。
?
?
p
a
x
b
②
①
图 2 - 1 7 删除 P 指针所指结 点示意图
删除算法描述为,
void dudelete(dulink *head,int x)
{ dulink *p; p=head;
while(p!=NULL)&&(p->data!=x) //用循环查找值为
x的结点
p=p->next;
if(p!=NULL) //已找到该结点
{ p->prior->next=p->next;
p->next->prior=p->prior;
delete p; } //删除后的结点空间回收
else cout<<”没找到, 不能删除, ; }
数据结构（ C++描述）
目录
2.1 线性表的定义及其运算
2.2线性表的顺序存储结构
２,３ 线性 表的链式存贮结构
结束放演
2.1 线性表的定义及其运算
2.1.1线性表的定义
1,线性表的定义
线性表 （ linear list） 是 n（ n≥0） 个数据元素 a1,a2,… an组
成的有限序列 。 其中 n 称为数据元素的个数或线性表的长
度, 当 n=0时称为空表, n>0时称为非空表 。 通常将非空的
线性表记为 （ a1,a2,…,an）, 其中的数据元素 ai（ 1≤i≤n）
是一个抽象的符号, 其具体含义在不同情况下是不同的,
即它的数据类型可以根据具体情况而定, 本书中, 我们将
它的类型设定为 elemtype,表示某一种具体的已知数据类
型 。
2,线性表的特征
从线性表的定义可以看出线性表的特征：
（ 1 ） 有且仅有一个开始结点 (表头结点 )a1,它没
有直接前驱, 只有一个直接后继 ;
（ 2） 有且仅有一个终端结点 (表尾结点 )an,它没有
直接后继, 只有一个直接前驱 ;
（ 3） 其它结点都有一个直接前驱和直接后继；
（ 4） 元素之间为一对一的线性关系 。
线性表是一种典型的线性结构, 用二元组表示为：
linear_list=(A,R)
其中
A={ai ∣ 1≤i≤n,n≥0,ai∈ elemtype}
R={r}
r={<ai,ai+1> ∣ 1≤i≤n-1}
对应的逻辑结构图如图 2-1所示。
a 1 a 2 …… a n
图 2 - 1 线性表逻辑结构示意图
2.1.2 线性表的运算
常见线性表的运算有：
1,置空表 SETNULL（ &L） 将线性表 L置成空表
2,求长度 LENGTH（ L） 求给定线性表 L的长度
3,取元素 GET（ L,i） 若 1≤i≤length(L),则取第 i个位
置上的元素, 否则取得的元素为 NULL。
4,求直接前趋 PRI0R（ L,X） 求线性表 L中元素值为 X
的直接前趋, 若 X为第一个元素, 前驱为 NULL。
5,求直接后继 NEXT（ L,X） 求线性表 L中元素值
为 X直接后继, 若 X为最后一个元素, 后继为 NULL。
6,定位函数 LOCATE（ L,X） 在线性表 L中查找
值为 X的元素位置, 若有多个值为 X,则以第一个为
准, 若没有, 位置为 0。
7,插入 INSERT（ &L,X,i） 在线性表 L中第 i个
位置上插入值为 X的元素 。
8,删除 DELETE（ &L,i） 删除线性表 L中第 i个
位置上的元素 。
2.1.3线性表的抽象数据类型描述
上述这些操作可用抽象数据类型描述为：
ADT Linearlist is
Data:
一个线性表 L定义为 L=(a1,a2,…,an),当 L=（ ） 时定义
为一个空表
operation:
void setnull(&L) //将线性表 L置成空表
int Length(L) //求给定线性表 L的长度
elemtype Get(L,i) //取线性表 L第 i个位置上的元素
elemtype Prior(L,x) //求线性表 L中元素值为 X的直接前
趋
elemtype Next(L,x) //求线性表 L中元素值为 X的直接
后继
int Locate(L,x) //在线性表 L中查找值为 X的元素位
置
void Insert(&L,x,i) //在线性表 L中第 i个位置上插入
值为 X的元素
void Delete(&L,i) //删除线性表 L中第 i个位置上的元
素
END Linearlist
例 2-1 假设线性表 L=(23,56,89,76,18),i=3,x=56,y=88,则
对 L的一组操作及结果如下：
Length(L); //所得结果为 5
Get(L,i) //所得结果为 89
Prior(L,x) //所得结果为 23
Next(L,x) //所得结果为 89
Locate(L,x) //所得结果为 2
Insert(&L,y,i) //所得结果为 (23,56,88,89,76,18)
Delete(&L,i+1) //所得结果为 (23,56,88,76,18)
2.2线性表的顺序存储结构
2.2.1 顺序表结构
线性表的顺序存储结构,也称为顺序表 。 其存储方式为：
在内存中开辟一片连续存储空间, 但该连续存储空间
的大小要大于或等于顺序表的长度, 然后让线性表中
第一个元素存放在连续存储空间第一个位置, 第二个
元素紧跟着第一个之后, 其余依此类推 。
假设线性表中元素为 （ a1,a2,…,,an）, 设第一个元
素 a1的内存地址为 LOC(a1)（ 在图 2-2中表示为 b）, 而
每个元素在计算机内占 d个存贮单元,则第 i个元素 ai的
地址为 LOC(ai)=LOC(a1)+(i-1)× d (其中 1≤i≤n)
于是可用 C++语言描述为,
const int maxsize=maxlen； //maxlen表示线性表允
许的最大长度
struct sequenlist
{
elemtype a[maxsize]; //表示线性表 （ a1,a2,…,,an）
int len; //len表示线性表的实际长度
}；
存储地址 内存排列 位置序号
?
a
1
a
2
…
a
i
…
a
n
…
0
1
2
…
i
…
n
…
m ax le n - 1
b
b+d
…
b+ (i - 1) × d
…
b+(n - 1) × d
图 2 - 2 顺序存储结构示意图
2.2.2 顺序表运算
1,求顺序表的长度 length(L)
int length(sequenlist L)
{
return L.len;
}
该算法的语句频度为 1,时间复杂度为 0(1)。
2．插入运算 Insert( &L,x,i)
void Insert(sequenlist &L,elemtype x,int i)
{ int j;
if(L.len>=maxsize-1)
cout<<”overflow”<<endl;
else if ((i<1)||(i>L.len+1)
cout<<”position is not correct!”<<endl;
else { for(j=L.len;j>=i;j--)
L.a[j+1]=L.a[j]; //元素后移
L.a[i]=x; //插入元素
L.len++; //表长度增加 1
}}
0
1
2
3
…
i - 1
i
i+1
…
n
…
m a x si z e - 1
a
1
a
2
a
3
…
a
i - 1
x
a
i
…
a
n - 1
a
n
0
1
2
3
…
i - 1
i
i+1
…
n
…
m a x si z e - 1
a
1
a
2
a
3
…
a
i - 1
a
i
a
i +1
…
a
n
…
序号 内容 序 号 内容
插入前 插入后
图 2 - 3 顺序表中插入元素前后状态
３, 删除运算 Delete(&L,i)
void Delete(sequenlist &L,int i)
{ int j;
if((i<1)||(i>L.len))
cout<<” position is not correct!”<<endl;
else {
for(j=i+1;j<=L.len;j++)
L.a[j-1]=L.a[j]; //元素前移
L.len--; //表长度减 1
} }
0
1
2
3
…
i - 1
i
i+1
…
n - 1
…
m a x si z e - 1
a
1
a
2
a
3
…
a
i - 1
a
i +1
a
i +2
…
a
n
…
0
1
2
3
…
i - 1
i
i+1
…
n
…
m a x si z e - 1
a
1
a
2
a
3
…
a
i - 1
a
i
a
i +1
…
a
n
…
序号 内容 序号 内容
删除前 删除后
图 2 - 4 顺序表中删除元素前后状态
插入算法花费的时间, 主要在于循环中元素的后移
（ 其它语句花费的时间可以省去 ）, 即从插入位置到
最后位置的所有元素都要后移一位, 使空出的位置插
入元素值 x。 但是, 插入的位置是不固定的, 当插入位
置 i=１时, 全部元素都得移动, 需 n次移动, 当 i=n+１
时, 不需移动元素, 故在 i位置插入时移动次数为 n-i+1，
假设在每个位置插入的概率相等为, 则平均移动元
素的次数为
=
故时间复杂度为 O(n)。
同理，可推出删除运算的平均移动次数为,
故时间复杂度为 O(n)。
11?n
??? ? ??11 11 )]1([ni n in
2
n
21?n
4,置空表 setnull(&L)
void setnull(sequenlist &L)
{
L.len=0;
}
该算法的时间复杂度为 O(1)。
5,定位算法 Locate(L,x)
int Locate(sequenlist L,elemtype x)
{ int j=1;
while(j<=L.len)&&(L.a[j]!=x)
j++;
if(j<=L.len) return j;
else return 0;
}
该算法的时间复杂度为 O(n)。
6,取元素 Get(L,i)
elemtype Get(sequenlist L,int i)
{
if(i<1)||(i>L.len) return NULL;
else return L.a[i];
}
该算法的时间复杂度为 O(1)。
2.2.3 顺序表存储空间的动态分配
若将前面线性表的顺序存储结构类型中的数组形式改为
指针形式, 则得到动态分配形式如下：
struct sequenlist
{
elemtype *a;
int len;
};
在此时, 只有线性表置空表算法需要修改, 其它算法都
与静态分配相同 。 这时的置空表算法应改为：
void setnull(sequenlist &L)
{
L.a=new elemtype[maxsize]; //动态申请存储单元
if(L.a==NULL) //申请不成功
exit(1);
L.len=0;
}
２,３ 线性表的链式存贮结构
线性表的链式存贮结构, 也称为链表 。 其存贮方式是：
在内存中利用存贮单元 (可以不连续 )来存放元素值及它在
内存的地址, 各个元素的存放顺序及位置都可以以任意
顺序进行, 原来相邻的元素存放到计算机内存后不一定
相邻, 从一个元素找下一个元素必须通过地址 (指针 )才能
实现 。 故不能像顺序表一样可随机访问, 而只能按顺序
访问 。 常用的链表有单链表, 循环链表和双向链表, 多
重链表等 。
２,３,１ 单链表结构
在定义的链表中, 若只含有一个指针域来存放下一个
元素地址, 称这样的链表为单链表或线性链表 。
线性链表中的结点结构可描述为,
D a ta n e x t
n e x t
其中 data 域用来存放结点本身信息, 类型由具体问题
而定, 本书中, 我们也将其设定为 elemtype类型, 表
示某一种具体的已知类型, next域用来存放下一个元
素地址 。
a
2
1 8 0
a
4
1 7 0
a
6
N U L L
a
1
1 1 0
a
5
1 4 0
a
3
1 3 0
150
地址 data 域 next 域
1 10
120
130
140
150
160
170
180
head
头指针
图 2 - 5 单链表示意图
a 1 a 2 a 3 a 4 a 5 a 6 ^
图２ - 6 单链表的逻辑表示
单链表可用Ｃ ++描述为,
struct link
{ elemtype data; //元素类型
link *next; //指针类型,存放下一个元素地址
}
( a ) 不带头结点的单链表
a 1 h e a d a 2 …… a n ^
( b ) 带头结点的单链表
h e a d …… a n ^ 头 a 1
a
2
图 2 - 7 不带头结点和带头结点的单链表
2,3,2单链表运算
１, 头插法建立单链表 (从左边插入结点 )
link *hcreat( )
{ link *s,*p; int i;
cin>>i; //输入结点数值, 为 0时算法结束
p=NULL;
while(i)
{ s=new link; s->data=i;
s->next=p; p=s;
cin>>i; }
return p;
}
2,尾插法建立单链表 (从右边插入结点 )
link *rcreat( )
{ link *s,*r,*p; int i;
p=r=new link; p->next=NULL;
cin>>i;
while(i)
{ s=new link; s->data=i;
r->next=s; r=s;
cin>>i; }
r->next=NULL; return p; }
3,单链表上的查找运算
(1) 按值查找 Locate(head,x)
在单链表 head中, 查找值为 x的结点, 若找到, 返回它的
地址, 否则返回 NULL。
(2) 按序号查找 get(head,i)
在单链表 head中查找第 i个位置上的元素, 若找到,
则返回它的地址, 否则返回 NULL。
Link *Locate(link *head,elemtype x)
{ link *p;
p=head->next;
while((p!=NULL)&&(p->data!=x))
p=p->next;
return p;
}
算法的时间复杂度都为Ｏ (n)。
Link *get(link *head,int i)
{ int j; link *p;
j=1; p=head->next;
while((j<i)&&(p!=NULL)
{ j++;
p=p->next; }
return p;
}
算法的时间复杂度都为Ｏ (n)。
4,单链表上的插入运算
若将 x插入 a和 b 之间，插入结点的指针变化如图２ -8
所示。
① ②
s
a b
x
p
?
图 2 - 8 插入结点时的指针修改
void insert(link *head,elemtype x,elemtype y)
//在头指针 head所指单链表中,在值为 y的结点之后插入
值为 x的结点
{ link *p,*s;
s=new link; s->data=x;
if(head->next==NULL) //链表为空
{ head->next=s; s->next=NULL; }
p=Locate(head,y) //调用查找算法
if(p==NULL) cout<<”插入位置非法, ;
else { s->next=p->next;
p->next=s; } }
５, 单链表上的删除运算
若将 x删除，删除结点的指针变化如图 2-9所示。
p q
? a 1 x a 2
图 2 - 9 删除结点的指针修改
void delete(link *head,elemtype x)
//在 head为头指针的单链表中,删除值为 x的结点
{ link *p,*q;
q=head; p=head->next;
while(p!=NULL)&&(p->data!=x)
{ q=p; p=p->next; }
if(p==NULL) cout<<“要删除的结点不存在, ；
else { q->next=p->next; delete(p);
} }
６,输出单链表
若需将单链表按逻辑顺序输出 (见图２ -10)，则必须从头
到尾访问单链表中每一个结点，
a n ^ …… 头 a 1 head a 2
( a ) 单链表示意图
a
1 a 2 a
n
……
( b ) 单链表输出结果示意图
图 2 - 10 单链表按逻辑结构输出示意图
void print(link *head)
{ link *p;
p=head->next;
while(p->next!=NULL)
{ cout<<p->data<<”->”; //输出表中非最后一个元
素
p=p->next; }
cout<<p->data; //输出表中最后一个元素
cout<<endl;
}
２,３,３ 循环链表结构
单链表上的访问是一种顺序访问，从其中某一个结点出
发，可以找到它的直接后继，但无法找到它的直接前驱。
因此，我们可以考虑建立这样的链表，具有单链表的特
征，但又不需要增加额外的存贮空间，仅对表的链接方
式稍作改变，使得对表的处理更加方便灵活。从单链表
可知，最后一个结点的指针域为 NULL表示单链表已经
结束。如果将单链表最后一个结点的指针域改为存放链
表中头结点 (或第一个结点 )的地址，就使得整个链表构
成一个环，又没有增加额外的存贮空间，称这们的链表
为单循环链表，在不引起混淆时称为循环表 (后面还要
提到双向循环表 )
循环链表上的运算与单链表上运算基本一致, 区别只
在于最后一个结点的判断 (即循环的条件不同 ),但利
用循环链表实现某些运算较单链表方便 (从某个结点
出发能求出它的直接前驱, 而单链表是不行的, 只能
从头出发 )。
头 a 1 a 2
…… a
n
head
(b) 非空循环表
图 2 - 11 带头结的单循环链表示意图
(a ) 空循环表
头
head
2.3.4 双向链表结构
1,双向链表基本概念
在单链表中, 从某个结点出发可以直接找到它的直接后
继, 时间复杂度为 O(1), 但无法直接找到它的直接前驱；
在单循环链表中, 从某个结点出发可以直接找到它的直
接后继, 时间复杂仍为 O(1),直接找到它的直接前驱,
时间复杂为 O(n)。 有时, 希望能快速找到一个结点的直
接前驱, 这时, 可以在单链表中的结点中增加一个指针
域指向它的直接前驱, 这样的链表, 就称为双向链表 (一
个结点中含有两个指针 )。 如果每条链构成一个循环链表,
则会得双向循环链表 。
双向链表可用 C++描述如下：
struct dulink
{
elemtype data; //结点的数据域,类型设定为
elemtype
dulink *next,*prior; //定义指向直接后继和直接前驱
的指针
}
^
头
a 1
a 2
a n
^
尾
……
……
h e a d
r e a r
( a ) 双向链表示意图
头
a 1
a 2
a n
尾
……
……
h e a d
r e a r
( b ) 双向循环链表示意图
图 2 - 1 5 双向链表及循环链表示意图
2,双向链表插入运算 duinsert (head,x,y)
在 head为头指针的双向链表中，在值为 Y的结点之后
插入值为 X的结点，插入结点的指针变化见图 2-16(若
改为在值为 Y的结点之前插入值为 X的结点，可以作
类似分析 )。
图 2 - 1 6 S 插入 P 之后指针变化示意图
④
X
Y
②
①
③
?
?
s
p
插入算法描述为：
void duinsert(dulink *head,elemtype x,elemtype y)
{ dulink *p,*s;
s=new dulink; //申请待插入的结点
s->data=x; p=head;
while(p!=NULL)&&(p->data!=y) //用循环查找值为
y的结点
p=p->next;
if (p!=NULL) //已找到插入位置
{ s->next=p->next; p->next->prior=s;
s->prior=p; p->next=s; }
else cout<<”插入位置不存在, ; }
3 。 双向链表的删除运算 dudelete(head,x)
在以 head为头的双向链表中删除值为 x的结点，删
除算法的指针变化见图 2-17。
?
?
p
a
x
b
②
①
图 2 - 1 7 删除 P 指针所指结 点示意图
删除算法描述为,
void dudelete(dulink *head,int x)
{ dulink *p; p=head;
while(p!=NULL)&&(p->data!=x) //用循环查找值为
x的结点
p=p->next;
if(p!=NULL) //已找到该结点
{ p->prior->next=p->next;
p->next->prior=p->prior;
delete p; } //删除后的结点空间回收
else cout<<”没找到, 不能删除, ; }
