第02章数据结构课件

PEF文件使用"pdfFactoryPro”试用版本创建WAWfincprint.comcn

第2章线性表及其顺序存储

PEF文件使用"pdfFactoryPro”试用版本创建WAWfincprint.comcn

第2章线性表及其顺序存储

线性表是一种常用的数据结构，本章介绍线性表

及其顺序存储，并对栈和队列及它们的顺序实现给出

了详细的设计描述。

PEF文件使用"pdfFactoryPro”试用版本创建WAWfincprint.comcn

第2章线性表及其顺序存储

线性表是一种常用的数据结构，本章介绍线性表

及其顺序存储，并对栈和队列及它们的顺序实现给出

了详细的设计描述。

2.1线性表

PEF文件使用"pdfFactoryPro”试用版本创建WAWfincprint.comcn

第2章线性表及其顺序存储

线性表是一种常用的数据结构，本章介绍线性表

及其顺序存储，并对栈和队列及它们的顺序实现给出

了详细的设计描述。

2.1线爨

线性表是一个线性结构，它是一个含有n》0个

结点的有限序列，对于其中的结点，有且仅有一个

开始结点没有前驱但有一个后继结点，有且仅有一

个终端结点没有后继但有一个前驱结点，其它的结

点都有且仅有一个前驱和一个后继结点。一般地，

一个莪性表可以表示成一个线性序列：…卜已

其中均是开始结点，心是终端结点。

PEF文件使用"pdfFactoryPro”试用版本创建WAWfincprint.comcn

2.21页序表

221顺序表

PEF文件使用"pdfFactoryPro"试用版本创建fincprint.comcn

2.21页序表

221顺序表

线性表采用顺序存储的方式存储就称之为顺序表。

顺序表是将表中的结点依次存放在计算机内存中一组

地址连续的年储单元中。

PEF文件使用"pdfFactoryPro”试用版本创建WAWfincprint.comcn

2.21页序表

2.2.力顿序表

线性表采用顺序存储的方式存储就称之为顺序表。

顺序表是将表中的结点依次存放在计算机内存中一组

地址连续的年储单元中。

如顺序表的每个结点占用len个内存单元，用

location(kJ表示顺序表中第i个结点(所占内存空间的

第1个单元的地址。则有如下的关系

location(ki+1)=location(k)+len

location(kJ=location(k1)+(i-l)len

PEF文件使用"pdfFactoryPro”试用版本创建WAWfincprint.comcn

PEF文件使用"pdfFactoryPro”试用版本创建WAWfincprint.comcn

顺序表的存储结构如下图所示:

存储结构要体现数据的逻辑结构，顺序表的存储

结构中，内存中物理地址相邻的结点一定具有顺序表

中的逻辑关系。

PEF文件使用"pdfFactoryPro”试用版本创建WAWfincprint.comcn

顺序表类型的描述如下：

ADTsequence_list{

数据集合K:K={k]9k2,...,kn},n>0,K中的元素是datatype类型

数据关系R:R={r},r={<ki,ki+1>|i=l,2,...,n-l}

操作集合：

(1)voidinit_sequence_list(sequence_list*slt)顺序表的初始化---置空表

(2)voidinsert_sequence_list(sequence_list*slt,datatypex)后部插入值为x结点

(3)voidprint_sequence_list(sequence_listsit)打印顺序表的各结点值

(4)intis_empty_sequence_list(sequence_listsit)判断顺序表是否为空

(5)intfind_num_sequence_list(sequence_listsit,datatypex)查找值为x结点位置

(6)intget_data_pos(sequence_listsit,inti)取得顺序表中第i个结点的值

(7)voidinsert_pos_sequence_list(sequence_list*slt,intposition,datatypex)

(8)voiddelete_pos_sequence_list(sequence_list*slt,intposition)

}ADTsequencelist;

PEF文件使用"pdfFactoryPro”试用版本创建WAWfincprint.comcn

222顺序表的实现

用C语言中的数组存储顺序表。C语言中数组的下标

是从0开始的，即数组中下标为0的元素对应的是顺序

表中的第1个结点，数组中下标为i的元素对应的是顺序

表中的第i+1个结点。为了方便，将顺序表中各结点的

序号改为和对应数组元素的下标序号一致，即将顺序

表中各结点的序号从0开始编号。这样，一个长度为n

的顺序表可以表示为

{k。,k],k?,…,院_]}

PEF文件使用"pdfFactoryPro”试用版本创建WAWfincprint.comcn

顺序表的存储结构的C语言描述如下:

«1>>2><1>

^>»*T**T**T**T*^>»*TW

/*顺序表的头文件，文件名sequlist.h*/

<l4»>|><1<»st*

/^TW^TW*T^*T^^TW

#defineMAXSIZE100

typedefintdatatype;

typedefstruct{

datatypea[MAXSIZE];

intsize;

}sequence_list;

PEF文件使用"pdfFactoryPro”试用版本创建WAWfincprint.comcn

顺序表的几个基本操作的具体实现:

PEF文件使用"pdfFactoryPro”试用版本创建WAWfincprint.comcn

顺序表的几个基本操作的具体实现:

K!>»1><1>K!>»x»

*Z^

顺序表的初始化--置空表

/*文件名seqlinit.c,函数名init_sequence_list()

K|^^}><>!>»1>^|>^j>K|^<J>K!>^f>^|>^}>^}>^1>

*T^*T*

PEF文件使用"pdfFactoryPro”试用版本创建WAWfincprint.comcn

顺序表的几个基本操作的具体实现:

K!>»1><1>K!>»x»

*Z^

顺序表的初始化--置空表

/*文件名seqlinit.c,函数名init_sequence_list()*/

/v|><A»»1>»X>

/*T**T*<Tw*T^

voidinit_sequence_list(sequence_list*slt)

slt->size=0;

)

算法2.1顺序表的初始化一置空表

PEF文件使用"pdfFactoryPro”试用版本创建WAWfincprint.comcn

^j>^t>^f>^9>^f>^f>K!>«1>^j>^9^

rrw^TM*T*<TM*T^rrw<|^*r^

/*在顺序表后部进行插入操作*/

/*文件名seqlinse.c,函数名insert_sequence」ist()*/

*1^«1>«1><1^<1^<1^«1>«»1^<}>^|>

<T>>TW*TW>TW*TW*TW<TW^T><TM>T*<T^rT><T>*TW<TW<T^*TW>TW*7^*TW*T>

voidinsert_sequence_list(sequence_list*slt,datatypex)

(

if(slt->size==MAXSIZE)

{printf("顺序表是满的!");exit(1);}

slt->size=slt->size+1;

slt->a[slt->size]=x;

)

算法2.2在顺序表后部进行插入操作

PEF文件使用"pdfFactoryPro”试用版本创建WAWfincprint.comcn

PEF文件使用"pdfFactoryPro”试用版本创建WAWfincprint.comcn

/^9>^1^^9^^f>^1>^9>^1^^f>«1^/

/>1^*1**1**J^<1^>1^^1**1**1^*1**TW*T**T**T*>T^*|>^W*T*/

*打印顺序表的各结点值

/*文件名seqlprin.c,函数名print_sequence」ist()*/

//<i><i>^v>xt>/

PEF文件使用"pdfFactoryPro”试用版本创建WAWfincprint.comcn

/^9>^1^^9^^f>^1>^9>^1^^f>«1^/

/>1^*1**1**J^<1^>1^^1**1**1^*1**TW*T**T**T*>T^*|>^W*T*/

*打印顺序表的各结点值

/*文件名seqlprin.c,函数名print_sequence」ist()*/

/^t>»t>^t><i><i>^v>^t>^t>^t>xt>»f>^t>^t>^t>^t>^t>^t>

//

voidprint_sequence_list(sequence_listsit)

(

inti;

if(!slt.size)printf("\n顺序表是空的!”);

else

for(i=0;i<slt.size;i++)printf("%5d",slt.a[i]);

算法2.3打印顺序表的各结点值

PEF文件使用"pdfFactoryPro”试用版本创建WAWfincprint.comcn

intis_empty_sequence_list(sequence_listsit)

return(slt.size==O?0:1);

)

算法2.4判断顺序表是否为空

PEF文件使用"pdfFactoryPro”试用版本创建WAWfincprint.comcn

^f>^1>«1^«1^^1>«1^^9>^J>^9>/

*TW*T**T^*TW*T**T**T**T**T*^T**T*^TM*TW*TW*T**T^>T^/

/*判断顺序表是否为空*/

/*文件名seqlempt.c,函数名is_empty_sequence_list()*/

/Sl^Sl^»1>^f>^|><f><A>//

intis_empty_sequence_list(sequence_listsit)

return(slt.size==O?0:1);

)

算法2.4判断顺序表是否为空

PEF文件使用"pdfFactoryPro”试用版本创建WAWfincprint.comcn

^f>^f>^{>KJ>*9^^f>^1>>]^^f>

^W*T**T*^W*1**T**T**TW*TW

查找顺序表中值为X的结点位置*/

/*文件名seqlfind.c，函数名find_num_sequence_list()*/

/^f>K!>«kl><I>»I>^f><f^^f>K!>^|>»j>»f><1>^f>/

/*T^<T^/

PEF文件使用"pdfFactoryPro”试用版本创建WAWfincprint.comcn

^f>^f>^{>KJ>*9^^f>^1>>]^^f>

^W*T**T*^W*1**T**T**TW*TW

/*查找顺序表中值为X的结点位置*/

/*文件名seqlfind.c,函数名find_num_sequence_list()*/

»f^^f>^|>«A»K|><I>^f>^9><f^<A»<X^*1>^I>^f>^f>»j>»f>/

/XT**T^*TM<T^/

intfind_num_sequence_list(sequence_listsit,datatypex)

(

inti=0;

while(slt.a[i]!=x&&i<slt.size)i++;

return(i<slt.size?i:-1);

}

算法2.5查找顺序表中值为x的结点位置

PEF文件使用"pdfFactoryPro”试用版本创建WAWfincprint.comcn

^1^^|>^9^^9>^1>^f>^1>>1>^f>^1>^{>^1>

*TW*1**T*>1**1**1*>1^*1^*1**TW*1**TW*T**TW<J*<T**T*

取得顺序表中第i个结点的值*

/*文件名seqlget.c,函数名get_data__pos_sequence_list()*/

//^1><1>»X»^*fT>*»X»^|>^f><1^^f>/

PEF文件使用"pdfFactoryPro”试用版本创建WAWfincprint.comcn

^9^^t>^9>>f^*1>^9>^9>^1>>f>^f>/

*TW*T*<T**T>*TW*T**TW*T**TW*T**T*^1**T^*T*/

/*取得顺序表中第i个结点的值*/

/*文件名seqlget.c,函数名get_data_pos_sequence_list()*/

<1><X»^f>»X»^f>/

<T>#T^*T^<T^/

intget_data_pos(sequence_listsltjnti)

(

if(i<O||i>=slt.size)

{printf(”\n指定位置的结点不存在!)eWt(1);}

else

returnslt.a[i];

)

算法2.6取得顺序表中第i个结点的值

PEF文件使用"pdfFactoryPro”试用版本创建WAWfincprint.comcn

顺序表的插入运算是将一个值为X的结点插入到顺序

表的第i个位置O4i《n,即将x插入到3和I之间，如果

i=n,则表示插入到表的最后，一般地可表示为：

才由刖：{k。，,kj”kj,…，j}

插入后：{k0,k1?kg,x,kpk『i}

PEF文件使用"pdfFactoryPro”试用版本创建WAWfincprint.comcn

顺序表的插入运算是将一个值为X的结点插入到顺序

表的第i个位置O4i《n,即将x插入到3和I之间，如果

i=n,则表示插入到表的最后，一般地可表示为：

才由刖：{k。，,kj”kj,…，j}

插入后：{k0,k1?kg,x,kpk『i}

插入过程的图示见下图：

PEF文件使用"pdfFactoryPro”试用版本创建WAWfincprint.comcn

顺序表的插入运算是将一个值为X的结点插入到顺序

表的第i个位置O4i《n,即将x插入到3和I之间，如果

i=n,则表示插入到表的最后，一般地可表示为：

才由刖：{k。，,kj”kj,…，j}

插入后：{k0,k1?kg,x,kpk『i}

插入过程的图示见下图：

PEF文件使用"pdfFactoryPro”试用版本创建WAWfincprint.comcn

^f>^J>^1>^f>^9>^1>«1^>f>^t>

*TW*T**T**1^*T^*TW*T**T**T**T^*T**T**T^*TW*T*<|**T**T*

/*在顺序表的position位置插入值为x的结点*/

/*文件名seqlinse.c,函数名insert_pos_sequence_list()*/

/<1^^jL>»1>»X»»1>/

/*T^#TM/

PEF文件使用"pdfFactoryPro”试用版本创建WAWfincprint.comcn

voidinsert_pos_sequence_list(sequence_list*slt,int

position,datatypex)

{inti;

if(slt->size==MAXSIZE)

{printf(”\n顺序表是满的!没法插入!”);exit⑴;}

if(position<0||position>slt->size)

{printf("\n指定的插入位置不存在!)exit。);}

for(i=slt->size;i>position;i-)slt->a[i]=slt->a[i-1];

slt->a[position]=x;

slt->size++;

)

算法2.7在顺序表的pos由on位置插入值为x的结点

PEF文件使用"pdfFactoryPro”试用版本创建WAWfincprint.comcn

算法2.7中，所花费的时间主要是元素后移操作，对

于在第i个位置上插入一个新的元素，需要移动（n-i）

个元素，设在第i个位置上插入一个元素的概率为R,且

在任意一个位置上插入元素的概率相手，即

Po=Pi=P2=...=Pn=l/n+l,则在一个长度为n的顺序表中插

入一个元素所需的平均移动次数为：

PEF文件使用"pdfFactoryPro”试用版本创建WAWfincprint.comcn

算法2.7中，所花费的时间主要是元素后移操作，对

于在第i个位置上插入一个新的元素，需要移动（n-i）

个元素，设在第i个位置上插入一个元素的概率为R,且

在任意一个位置上插入元素的概率相手，即

Po=Pi=P2=...=Pn=l/n+l,则在一个长度为n的顺序表中插

入一个元素所需的平均移动次数为：

t小这，）=T义中档

toto^+1〃+122

PEF文件使用"pdfFactoryPro”试用版本创建WAWfincprint.comcn

算法2.7中，所花费的时间主要是元素后移操作，对

于在第i个位置上插入一个新的元素，需要移动(n-i)

个元素，设在第i个位置上插入一个元素的概率为R,且

在任意一个位置上插入元素的概率相手，即

Po=Pi=P2=...=Pn=l/n+l,则在一个长度为n的顺序表中插

入一个元素所需的平均移动次数为：

t小这，）=T义中档

toto^+1〃+122

即在长度为n的顺序表中插入一个元素平均需要

移动表中的一半元素。该算法的时间复杂度为0(n)。

PEF文件使用"pdfFactoryPro”试用版本创建WAWfincprint.comcn

顺序表的删除操作是指删除顺序表中的第i个结点,

0<i<n-l5一般地可表示为：

删除前：｛ko，k“

删除后：｛k0,"…，kg,K+1,…，kn_J

PEF文件使用"pdfFactoryPro”试用版本创建WAWfincprint.comcn

顺序表的删除操作是指删除顺序表中的第i个结点,

0<i<n-l5一般地可表示为：

删除前：｛ko，k“

删除后：｛k0,"…，kg,kj+1,kn_J

删除过程的图示见下图：

PEF文件使用"pdfFactoryPro”试用版本创建WAWfincprint.comcn

顺序表的删除操作是指删除顺序表中的第i个结点,

0<i<n-l5一般地可表示为：

删除前：｛ko，k“

删除后：｛k0,"…，kg,kj+1,kn_J

删除过程的图示见下图：

PEF文件使用"pdfFactoryPro”试用版本创建WAWfincprint.comcn

删除操作的具体实现见算法2.8

PEF文件使用"pdfFactoryPro”试用版本创建WAWfincprint.comcn

删除操作的具体实现见算法2.8

/<1^^9>^9^^1>^}>/

/*1**1**TW*1*<1^^1**1**1**1**1^*1**1**T><Tw/

/*删除顺序表中第position位置的结点*/

/*文件名seqldele.c,函数名delete_pos_sequence_list()*/

/^|>^L»»1><1>KI>»X><>1>/

/^TW<TM/

PEF文件使用"pdfFactoryPro”试用版本创建WAWfincprint.comcn

删除操作的具体实现见算法2.8

voiddelete_pos_sequence_list(sequence_list*slt,intposition)

(

inti;

if(slt->size==O)

{printf(”\n顺序表是空的!");exit⑴;}

if(position<0||position>=slt->size)

{printf(”\n指定的删除位置不存在!");exit(1);}

for(i=position;i<slt->size-1;i-)slt->a[i]=slt->a[i+1];

slt->size-;

)

算法2.8删除顺序表中第pos田on位置的结点

PEF文件使用"pdfFactoryPro”试用版本创建WAWfincprint.comcn

要删除顺序表中的第i个结点，则需要称动（n-i-1）

个元素，设删除表中第i个结点的概率为q〃且在表中每

一个位置删除的概率相等，即：

q（）=qi=・・尸qxi/n

则在一个长度为n的顺序表中删除一个结点的平均

移动次数为：

PEF文件使用"pdfFactoryPro”试用版本创建WAWfincprint.comcn

要删除顺序表中的第i个结点，则需要称动（n-i-1）

个元素，设删除表中第i个结点的概率为q〃且在表中每

一个位置删除的概率相等，即：

q（）=qi=・・尸qxi/n

则在一个长度为n的顺序表中删除一个结点的平均

移动次数为：

PEF文件使用"pdfFactoryPro”试用版本创建WAWfincprint.comcn

要删除顺序表中的第i个结点，则需要称动（n-i-1）

个元素，设删除表中第i个结点的概率为q〃且在表中每

一个位置删除的概率相等，即：

q（）=qi=・・尸qxi/n

则在一个长度为n的顺序表中删除一个结点的平均

移动次数为：

=之一("-I)=—x=---

z=o2=0nn22

这表明，在一个长为n的顺序表中删除一个元素平

均需要移动表中大约一半的元素。该算法的时间复杂

度为O（n）o

PEF文件使用"pdfFactoryPro”试用版本创建WAWfincprint.comcn

2.3栈

PEF文件使用"pdfFactoryPro”试用版本创建WAWfincprint.comcn

2.3栈

231栈

PIT文件使用"pdfFactoryPro"试用版本创建fincprint.comcn

2.3栈

231栈

栈是一种特殊的线性表，对于这种线性表规定它

的插入运算和删除运算均在线性表的同一端进行，进

行插入和删除的那一端称为栈顶，另一端称为栈底。

栈的插入操作和删除操作也分别简称进栈和出栈。

PEF文件使用"pdfFactoryPro”试用版本创建WAWfincprint.comcn

2.3栈

231栈

栈是一种特殊的线性表，对于这种线性表规定它

的插入运算和删除运算均在线性表的同一端进行，进

行插入和删除的那一端称为栈顶，另一端称为栈底。

栈的插入操作和删除操作也分别简称进栈和出栈。

如果栈中有n个结点

{k0,，k2,.・.，kn-i｝，

k0为栈底，kn.1是栈顶,

则栈中结点的进栈顺

序为卜0,1<2，…，kn」,

而出栈的顺序为kn【

kn.2,kvk0o如囱

所示。

PEF文件使用"pdfFactoryPro”试用版本创建WAWfincprint.comcn

2.3栈

231栈

栈是一种特殊的线性表，对于这种线性表规定它

的插入运算和删除运算均在线性表的同一端进行，进

行插入和删除的那一端称为栈顶，另一端称为栈底。

栈的插入操作和删除操作也分别简称进栈和出栈。

如果栈中有n个结点

{k0,，k2,.・.，kn-i｝，

k0为栈底,是栈顶,

则栈中结点的进栈顺

序为…，kn」，

而出栈的顺序为幻_1,；

kn.2,kvk0o如囱

而示。!

PEF文件使用"pdfFactoryPro”试用版本创建WAWfincprint.comcn

2.3栈

231栈

栈是一种特殊的线性表，对于这种线性表规定它

的插入运算和删除运算均在线性表的同一端进行，进

行插入和删除的那一端称为栈顶，另一端称为栈底。

栈的插入操作和删除操作也分别简称进栈和出栈。

如果栈中有n个结点

{k0,，k2,.・.，kn-i｝，

k0为栈底,是栈顶,

则栈中结点的进栈顺

序为…，kn」，

而出栈的顺序为幻_1,；

kn.2,kvk0o如囱

而示。!

PEF文件使用"pdfFactoryPro”试用版本创建WAWfincprint.comcn

2.3栈

231栈

栈是一种特殊的线性表，对于这种线性表规定它

的插入运算和删除运算均在线性表的同一端进行，进

行插入和删除的那一端称为栈顶，另一端称为栈底。

栈的插入操作和删除操作也分别简称进栈和出栈。

如果栈中有个结点

n栈具有后

{k0,，k2,.・.，kn-i｝，进先出或

为栈底，是栈顶,

k0kn.1先进后出

则栈中结点的进栈顺(FILO,

序为卜07I，卜2，…，kn」?FirstIn

而出栈的顺序为勺ILastOut)

k.,kk如囱

n2v0o：的性质

1而示。!II____________________________.

PEF文件使用"pdfFactoryPro”试用版本创建WAWfincprint.comcn

栈类型的描述如下：

ADTsequence_stack{

数据集合K:K={kpk2,...,kn},n>0,K中的元素是datatype类型

数据关系R:R={r}

r={<ki,ki+1>|

操作集合：

(1)voidinit_sequence_stack(sequence_stack*st)(可页序存储)

初始化

(2)intis_empty_stack(sequence_stackst)判断栈(顺序存储)

是否为空———

(3)voidprint_sequence_stack(sequence_stackst)打印栈(顺

序存储)的意点、值——

PEF文件使用"pdfFactoryPro”试用版本创建WAWfincprint.comcn

(4)datatypeget_top(sequence_stackst)取得栈顶(顺序存

猫)结点血

(5)voidpush(sequence_stack*st,datatypex)栈(顺序存储)

的插入操作

(6)voidpop(sequence_stack*st)栈(顺序存储)的删除操

作

}ADTsequence_stack

PEF文件使用"pdfFactoryPro”试用版本创建WAWfincprint.comcn

2.3.2顺序栈及其实现

PEF文件使用"pdfFactoryPro”试用版本创建WAWfincprint.comcn

2.3.2顺序栈及其实现

栈的实现方式一般有两种：顺序存储和链式存储。

本小节将给出栈的顺序存储实现。

PEF文件使用"pdfFactoryPro”试用版本创建WAWfincprint.comcn

2.3.2顺序栈及其实现

栈的实现方式一般有两种：顺序存储和链式存储。

本小节将给出栈的顺序存储实现。

栈的顺序存储方式就是在顺序表的基础上对插入

和删除操作限制它们在顺序表的同一端进行，所以同

顺序表一样也可用一维数组表示。

一般地，可以设定一个足够大的一维数组存储栈,

数组中下标为0的元素就是栈底，对于栈顶，可以设一

个指针top指示它。

为了方便，设定top所指的位置是下一个将要插入

的结点的存储位置,这样，当top=0时就表示是一个空

的栈。一个栈的几种状态以及在这些状态下栈顶指针

top和栈中结点的关系如下图所示。

PEF文件使用"pdfFactoryPro”试用版本创建WAWfincprint.comcn

数组下标数组下标数组下标

topf

MAXSIZE-1MAXSIZE.1kMAXSIZE-1

!!!!

2top—2kj2

1ki1ki1

topf0ko0ko0

(a)空栈⑻有两个结点的栈(c)栈已满

PEF文件使用"pdfFactoryPro”试用版本创建WAWfincprint.comcn

栈的顺序存储结构的C语言描述如下: