数据结构实用教程讲课教案

这次由本人主讲的数据结构（本科）IP课程共分为10讲，每讲大致为50分钟。

第一讲数据结构概述

第二讲集合与线性表

第三讲栈和队列

第四讲二叉树

第五讲二叉搜索树和堆

第六讲平衡二叉树

第七讲图的概念和存储结构

第八讲二分查找和散列查找

第九讲选择排序

第十讲快速排序和归并排序

第一讲数据结构概述

一、数据结构的分类

二、数据结构的定义

三、数据结构的图形表示

四、数据结构的二元组表示

五、数据结构的应用实例

六、算法的时间复杂度

一、数据结构的分类

数据结构又分为数据的逻辑结构和数据的存储结构这两个方面，我们时常把数据的逻辑

结构简称为数据结构，而在讨论数据的存储结构时则必须指明是数据的存储结构。

数据结构的分类：这里是指数据的逻辑结构的分类。总体来说数据的逻辑结构被分为集

合结构、线性结构、树结构和图结构等四种基本类型。对于一些复杂的数据结构可以由这四

种基本的数据结构，根据实际需要进行组合或嵌套所构成。

数据的存储结构分类：被分为顺序、链接、索引和散列四种，由它们的组合和嵌套可以

构成更复杂的存储结构。

广义的数据结构的概念还包含对数据进行的各种运算，通常有插入、删除、查找、更新、

排序、遍历等运算.

二、数据结构的定义

1、集合结构

集合结构是指数据中各元素之间没有任何次序。如一个容器中的所有乒乓球，一个俱乐

部里的所有成员，可以认为它们之间没有任何次序，它们均为集合结构。

2、线性结构

线性结构是指数据中各元素之间具有1对1的先后次序关系。如在一个列车时刻表中，

各车次记录之间是按照发车时间的先后次序排列的；在一个人事职工表中，各职工记录之间

是按照职工编号的先后次序排列的。所以，它们的表结构都是线性结构。

3、树结构

树结构是指数据中各元素之间具有1对多的先后次序关系，并且只有一个元素称为树根

结点，其余均为树枝结点和树叶结点。如在一个企业的组织机构中，总经理只有一个，相当

于是树根；它下属多个部门，每个部门又各有一个部门经理，相当于是树枝；每个部门又有

多名员工，属于部门经理领导，相当于是树叶。所以，企业的组织结构是一个树结构。

4、图结构

图结构是指数据中各元素之间具有多对多的关系。这是数据结构中最复杂的结构。如在

一个城市交通图中，所有道路连接成一个复杂的图结构，交叉路口就是图中的顶点，每条道

路就是图中的边，从一个交叉路口可以到达与其连接的其他交叉路口。

三、数据结构的图形表示

各种数据结构类型的图形表示如下:

(b)线性结构

(d)图结构

从图形表示中可以清醒地看出：

集合结构中的元素是各自独立的，元素之间没有联系.

线性结构中的元素是一个接一个串联起来的，它有一个头元素A和一个尾元素G,其余

为中间元素；每个中间元素既有前驱元素，又有后继元素，如B的前驱元素为A,后继元素

为C;C的前驱元素为B,后继元素为D,…，头元素A没有前驱元素，只有后继元素B;尾

元素G只有前驱元素F,没有后继元素。

树结构的图形表示象倒着画的一棵树，树中有一个树根元素A,它有3个后继元素，又

称为A的孩子结点B、C和D,C结点有两个孩子E和F,D结点有一个孩子G,由于B、E、F、

G没有孩子，所以称它们为叶子结点，而A、C、D被称为树枝结点或分支结点，同时A又是

唯一的一个树根结点。

在树结构中，树根结点只有后继结点，而没有前驱结点；如A为树根结点，它没有前驱

结点，或者说其前驱结点为空，它有后继结点为B、C和D;除树根结点外，每个结点都有

唯一一个前驱结点，又称为是父结点或双亲结点；如C的前驱结点为A,G的前驱结点为D,

每个结点的前驱结点即双亲结点，从图形中都能够很容易得到。

在图结构中，每个结点或称顶点都可以有任意多个前驱结点和任意多个后继结点.如(d)

图所示的图中，顶点A没有前驱结点，或者说它有0个前驱结点，A有3个后继结点B、C

和G;G有2个前驱结点A和D,有一个后继结点F;E有一个前驱结点C和0个后继结点，

或者说，E没有后继，对于图形中的其他结点都能够很容易得到其前驱和后继结点。

从数据结构的图形表示中还可以清楚地看出：树结构是图结构的特例，若在图结构中，

每个结点的前驱不能有任意多个，而只能有一个，并且只能有一个结点没有前驱，则就成为

了树结构；线性结构是树结构的特例，若在树结构中，每个结点不能有任意多个后继，而只

能有一个后继，则就成为了线性结构。为了区别于线性结构，时常把树结构和图结构称为非

线性结构。

四、数据结构的二元组表示

数据结构的二元组表示采用B=(K,R)的形式，其中第一元K给出数据结构中所有元素

的集合，第二元R给出数据结构中所有元素具有的二元关系的集合，通常对每个二元关系分

别进行讨论，所以直接用R表示这一种二元关系，该二元关系是有序对的集合，又称是序偶

的集合，每个有序对(即序偶)是用一对尖括号括起来的、具有前驱和后继关系的两个元素.

对于前面图形中给出的四种数据结构，下面分别讨论它们的二元组表示。

集合结构中的元素集合K和二元关系R分别为：

K={A,B,C,D,E,F,G)

R={)

因为集合中的元素为孤立顶点，它们之间没有前驱和后继的关系，所以对应的二元关系

为空。

线性结构中的元素集合K和二元关系R分别为：

K={A,B,C,D,E,F,G}

R={<A,B>,<B,C>,<C,D>,<D,E>,<E,F>,<F,G>}

因为A和B构成一对前驱和后继关系，对应图形中的一条有向边，它的起点为A,终点

为B,它就构成了R中的一个有序对，同理，B和C、C和D等都是R中的有序对。由于该线

性结构包含有7个元素，所以二元关系R中共含有6个有序对。

树结构中的元素集合K和二元关系R分别为：

K={A,B,C,D,E,F,G}

R={<A,B>,<A,C>,<A,D>,<C,E>,<C,F>,<D,G>}

因为A和B构成一对前驱和后继关系，所以它是R中的一个有序对，同理，A和C、A

和D等都是R中的有序对。由于该树结构包含有7个元素，所以二元关系R中共含有6个有

序对，即每个元素对应唯一一个有序对，并且是有序对中的后继元素，而树根结点没有对应

的、作为后继元素的有序对。所以当一棵树具有n个结点时，它必然具有n-1个有序对，对

应图形中为n-1条有向边。

图结构中的元素集合K和二元关系R分别为：

K={A,B,C,D,E,F,G}

R={<A,B>,<A,C>,<A,G>,<D,G>,<D,F>,<C,E>,<C,F>,<G,F>)

在线性结构和树结构中，若元素个数为n,则有序对个数必然为n-1;而在图结构中不

存在这种对应的关系，也就是说，其有序对的个数又称有向边数可能大于、等于或小于n-1。

在这个图结构的例子中，元素个数为7个，边数为8个。

五、数据结构应用实例

下面为某个公司的职工简表

职工号姓名性别出生日期职务部门

01万明华男1962-03-20经理

02赵宁男1968-06-14主管销售部

03张利女1964-12-07主管财务部

04赵书芳女1972-08-05主任办公室

05刘永年男1959-08-15科员销售部

06王明理女1975-04-01科员销售部

07王敏女1972-06-28科员财务部

08张才男1967-03-17科员财务部

09马立仁男1975-10-12科员财务部

10邢怀常男1976-07-05科员办公室

该表中包含有10条职工记录，每条记录都由六个数据项所组成，由于每条记录的职工

号各不相同，所以可把每条记录的职工号作为该记录的关键字，并在下面的讨论中，用记录

的关键字来代表整个记录。

对于上面所述的一张表，假定不考虑该表中记录之间的任何次序，则该表中的数据就是

一个集合结构，对应的记录集合以及二元关系为：

K={01,02,03,04,05,06,07,08,09,10}

R={)

若考虑到该表中的职工记录是按照职工号从小到大有序排列的这个特点，则这个职工表

又是一个线性结构，其中表头元素为01号职工，接着为02号职工，依次类推，表尾元素为

10号职工。该线性结构包含的记录集合和二元关系为：

K={01,02,03,04,05,06,07,08,09,10}

R={<01,02>,<02,03>,<03,04>,<04,05>,<05,06>,<06,07>,

<07,08>,<08,09>,<09,10>}

有时需要按职工的出生日期进行数据结构的定义和处理，则可以把表中的所有职工看作

是按照出生日期，从小到大有序的，由此对应的数据结构也是一种线性结构，其中05号职

工的出生日期最早，即年龄最大，为表头元素，01号职工年龄次之，为这种线性结构中的

第二个元素，依次类推，10号职工的出生日期最晚，为表尾元素。该线性结构包含的记录

集合和二元关系为：

K={01,02,03,04,05,06,07,08,09,10}

R={<05,01>,<01,03>,<03,08>,<08,02>,<02,07>,<07,04>,

<04,06>,<06,09>,<09,10>)

对应的图形表示为：

:碱一@10308—⑫1同―

从图形表示中能够清楚地看出每个职工出生日期的先后排列次序。

在上面职工表中，还存在职工人员之间领导与被领导的关系，其中01号职工为经理,

直接领导02、03和04号职工，他们分别是相应部门的主管，02号职工直接领导05和06

号职工，03号职工直接领导07、08和09号职工，04号职工直接领导10号职工。由此可知，

该职工表是一种树结构，包含的职工集合和二元关系分别为：

K={01,02,03,04,05,06,07,08,09,10)

R={<01,02>,<01,03>,<01,04>,<02,05>,<02,06>,<03,07>,

<03,08>,<03,09>,<04,10>}

对应的图形表示为：

若要反映职工之间的好友关系，假定01和02号职工是好友，01和04号是好友，02

和03、02和06、02和07、03和07、04和06、05和07之间是好友，则反映这种好友关系

的数据结构是图结构，二元组中的元素集合和有序对集合分别为：

K={01,02,03,04,05,06,07,08,09,10}

R={<01,02>,<02,01>,<01,04>,<04,01>,<02,03>,<03,02>,<02,06>,<06,02>,

<02,07>,<07,02>,<03,07>,<07,03>,<04,06>,<06,04>,<05,07>,<07,05>}

对应的图形表示如下面左图所示，其中08、09和10号职工无好友，在图形中为孤立顶

点，省略未画；图形中每对顶点之间的两条相反的有向边，表示这两个顶点职工是一对好朋

友，为了简化起见，两条相反的有向边可以用一条无向边来代替，隐含着该无向边是双向的，

即连接的两个顶点互为前驱和后继，则对应的无向图表示如下面右图所示。

从上面左图可以看出，R是K上的对称关系，即若存在<x,y>这个序偶，则必然存在<y,x>

这个序偶与之对应。为了简化起见，我们在二元组表示中把<x,y>和<y,x>这两个对称序偶用

一个无序对(x,y)或(y,x)来代替，这样R关系可改写为：

R={(01,02),(01,04),(02,03),(02,06),(02,07),(03,07),(04,06),(05,07))

可见R成为了一个无序对的集合，其中的每个元素为用圆括号括起来的一个无序对，对

应图形中的一条无向边，由无向边构成的图形称为无向图，反之为有向图。

六、算法的时间复杂度

算法的时间复杂度是一个算法运行时间的相对量度。一个算法的运行时间是指在计算机

上从开始到结束运行所花费的时间长短，它大致等于计算机执行一种简单操作(如赋值、比

较、计算、转向、返回、输入、输出等)所需的时间与算法中进行简单操作次数的乘积.因

为执行一种简单操作所需的时间随机器而异，它是由机器本身硬软件环境决定的，与算法无

关，所以我们只讨论影响运行时间的另一个因素一一算法中进行简单操作次数的多少。

不管一个算法是简单还是复杂，最终都是被编译后分解成简单操作再通过CPU来具体执

行的。因此，每个算法都对应着一定的简单操作的次数。显然，在一个算法中，进行简单操

作的次数越少，其运行时间也就相对地越短；次数越多，其运行时间也就相对地越长。所以，

通常把算法中包含简单操作次数的多少叫做该算法的时间复杂度，或者叫做时间复杂性，用

它来衡量一个算法的运行时间性能或称计算性能。

若解决一个问题的规模为n,即表示待处理的数据中包含有n个元素，则算法的时间复

杂度通常是n的一个函数，假定记为f(n)。

算法的时间复杂度通常采用数量级的形式表示，所以求一个算法的时间复杂度只要分析

清楚算法中主要的循环体内简单操作的执行次数，或递归函数的调用次数即可。例如，对于

一个含有n土C次循环的算法，其中n表示待处理问题的规模，C是一个常量，n»C,则该

算法的时间复杂度为0(n);对于一个含有双重循环的算法，循环次数的主体呈现在/数量

级上，所以则该算法的时间复杂度为0(/)。

算法的时间复杂度通常具有0(1)、0(Vn)、0(n).0(log2n),0(n*log2n),0(/)、035、

0(2")和0(n!)等形式。其中0(1)表示算法的时间复杂度为常量，它不随数据量n的改变而

改变，如访问一个数据表中第一个元素时，无论该表的大小如何，其时间复杂度均为0(1)。

0(新)表示算法的时间复杂度与数据量大小n的平方根成正比,如计算满足不等式£k<n

k=l

中的最大i值时，其算法的时间复杂度就是0(〃)。具有0(n)数量级的算法被称为具有线

性数量级的算法，其运行时间与n成正比，如对一个表进行顺序查找时，其时间复杂度就是

0(n)。有一些算法的时间复杂度为0(logm),即与n的对数成正比，如在有序表上进行二分

查找的算法就是如此。对数组进行简单插入或选择排序的算法的时间复杂度为0(/),当n

加倍时，其运行时间将增长4倍。

一个算法的时间复杂度还可以具体分为最好、最差和平均三种情况来讨论。下面结合从

一维数组a[n]中顺序查找其值等于给定值item的元素的算法进行说明。

intSequenceSearch(inta[],intn,intitem)

〃若查找成功则返回元素的下标，否则返回-1。

(

for(inti=0;i<n;i++)

if(a[i]==item)returni;

return-1;

)

此算法的时间复杂度主要取决于for循环体被反复执行的次数。最好情况是第一个元素

a[0]的值就等于item,此时只需要进行元素的一次比较就查找成功，相应的时间复杂度为

0(1);最差情况是最后一个元素a[nT]的值等于item,此时需要进行同全部n个元素的比

较才能查找成功，相应的时间复杂度为0(n);平均情况是：每一个元素都有相同的概率(即

均为,)等于给定值item,则查找成功需要同元素进行比较的平均次数为

n

n

:Zi=；5+D，相应的时间复杂度为0(n),它同最坏情况具有相同的数量级，因为它

z=l

们之间的比较次数只在n的系数项和常数项上有差别，而在n的指数上没有差别。

当在数组a上顺序比较所有n个元素后仍找不到等于给定值item的元素，则表明查找

失败，这种情况所对应的时间复杂度也为0(n)o

对于许多算法来说，平均和最差这两种情况下的时间复杂度的数量级形式往往是相同

的，它们主要是差别在最高次赛的系数上。另外有一些算法，其最好、最差和平均情况下的

时间复杂度或相应的数量级都是相同的，如求出n个元素平均值的算法就是如此，其时间复

杂度的最好、最差和平均情况均为0(n).

上面从数据结构的分类、数据结构的定义、数据结构的二元组表示、数据结构的图形表

示、数据结构的应用举例等多个方面，对数据结构的含义进行了详细地阐述，以便使同学们

能够更好地利用数据结构组织数据和处理问题。

这一讲也同时简要地介绍了算法的时间复杂度，与时间复杂度相类似的还有算法的空间

复杂度，它是算法在运行过程中临时占用内存空间大小的相对量度，它也有常量级0(1)、

平方根级0(五)、线性级0(n)、平方级0(/)、对数级O(logji)等不同级别。

例如，对于下面的算法：

intf(intn){

if(n<0)return-1;

elseif(n==0)rerun0;

elseretunn+f(n-1);

)

这是一个递归算法，其功能是计算出1+2+…+n的累加和，该算法要被递归调用n+1次，

其参数值依次为n、n-l、…、1、0,每次调用都是执行一条条件语句，而且都要把n值保

存起来，所以该算法的时间复杂度和空间复杂度均为03)。

这一讲到此结束，同学们再见!

同学们好:

第二讲集合与线性表

一、集合的定义

二、集合的抽象数据类型

三、集合的顺序存储结构和操作实现

四、集合的链接存储结构和操作实现

五、集合运算的时间复杂度分析

六、线性表的存储和运算简介

一、集合的定义

集合是集合结构的简称，它是具有相同属性的数据元素按任何次序排列而成的。该集合

中数据元素的个数称为集合的长度，通常用n表示，n>0。当n=0时则为空集。若集合为空，

则表示为{},若非空则表示为：

(31,a.2,,,,,ai,Hi+i,•,,,aj

其中每个元素的下标为对该元素的编号，它是为了区别而任意标注的，不代表任何次序。

因为集合中的元素可以按任何次序排列，假定就按元素前后位置编号的次序排列，那么a1

就是集合中的第一个元素,a?就是集合中的第二个元素,ai就是第i个元素,a。就是第口个(即

最后一个)元素。

集合中不含有任何关系，或者说含有的关系为空。

集合中的元素类型可以为任何一种类型，假定用标识符ElemType表示。若实际的元素

类型为某一具体类型，如整型int,则可以通过如下语句把ElemType类型等价定义为int

类型。

TypedefintElemType;

二、集合的抽象数据类型

集合的抽象数据类型包括数据和操作两个部分.数据部分为一个集合，假定用标识符S

表示。操作部分包含对集合进行的各种常用运算，如初始化一个集合，向集合中插入一个元

素，从集合中删除一个元素，从集合中查找一个元素等。

集合结构的抽象数据类型可定义如下：

ADTSETis//其中SET表示集合的抽象数据类型名

Data:〃表明为数据部分

一个集合S

Operation://表明为操作部分

voidInitSet(&S)//初始化集合为空

boolInsertSet(&S,item);//向集合中插入一个元素

boolDeleteSet(&S,item);//从集合中删除一个元素

boolFindSet(&S,&item);〃从集合中查找一个元素

....."还有其他对集合的运算

endSET

初始化集合、向集合中插入元素和从集合中删除元素等，都需要改变集合的状态，所以

函数中的集合参数S必须定义为引用参数，这样才能够把运算后的结果反映到实参变量上，

当从集合中查找元素时，它不会改变集合的状态，所以其集合参数可以使用引用参数，也可

以使用值参数，若使用值参数，将会花费时间用来实现实参向值参变量的内容复制上，所以

对集合的查找也最好采用引用参数为宜。另外，为了保护引用参数的值在查找过程中不被改

变，可以使用常量引用，即在引用参数前加上const保留字。

三、集合的顺序存储结构和操作实现

集合的顺序存储结构就是把集合中的所有元素，按照一定的次序顺序存储到内存中一块

连续的存储空间中。我们知道，一个数组空间是内存的一块连续的存储空间，该空间中的存

储位置是按照数组下标的次序顺序排列的，所以只要按照集合元素的编号次序把每个元素存

储到数组中相应下标的存储位置，就实现了集合的顺序存储结构。

假定用标识符set指向动态分配的数组空间，用标识符len表示集合当前长度的变量，

用标识符MaxSize表示数组空间的大小，即数组中下标位置的个数，则集合的顺序存储结构

类型，定义如下：

structSetSq{〃这里假定用标识符SetSq表示这种结构类型

ElemType*set;〃set用来指向动态分配的数组空间

intlen;〃存集合当前长度，即当前集合中所含元素的个数

intMaxSize;//存set数组长度，亦即所能存储集合的最大长度

)；

集合的顺序存储结构的示意图如下所示：

len

set012n-1nIn+1IMaxSize-1

a】a2汽3an

在这里，加元素被存储到数组中下标为。的数组单元中，a2元素被存储到下标为1的单

元中，依次类推，最后一个元素an被存储到下标为n-1的单元中，存储集合长度len变量

的值等于n,存储数组长度MaxSize变量的值等于数组空间的最大下标值加1。

下面给出对顺序存储的集合S进行初始化以及插入、删除和查找元素的算法。

1.初始化集合

初始化集合需要为集合动态分配数组存储空间，并使set指向这个数组空间，该空间的

大小由参数ms决定，当然ms的值要大于等于1。

voidInitSet(SetSq&S,intms)

(

if(ms<=0){cout«"ms值非法!n«endl;exit(1);}

S.MaxSize=ms;〃置数组空间大小为ms

S.set=ne\vElemType[ms];//动态分配数组存储空间

S.len=0;〃初始置集合为空，即置当前集合长度为0

2.向集合中插入一个元素

此算法包含如下五个步骤：

(1)检查存储集合的数组空间是否被用完，若是则停止运行；

(2)顺序查找集合中是否存在值为待插值item的元素，若存在则不能插入，返回假，

因为集合中不允许存在重复的元素；

(3)把>item值插入到最后一个集合元素的后面空位置上；

(4)集合长度增1;

(5)返回真表示插入成功。

对应的算法描述如下：

boolInsertSet(SetSq&S,ElemTypeitem)

(

if(S.len==S.MaxSize){cout<<"集合空间满！"<<endl;exit(1);}

for(inti=0;i<S.len;i++)

if(S.set[i]==item){cout<<"元素已存在！"<<endl;returnfalse;}

S.set[S.len]=item;

S.len++;

returntrue;

)

3.从集合中删除一个元素

此算法首先从集合中顺序查找值等于待删值item的元素，若存在则删除它，删除过程

是把最后一个元素直接移动到该元素空出的位置，接着使集合长度减1,返回真表示删除成

功；若不存在，则无法删除，返回假表示删除失败。

boolDeleteSet(SetSqfcS,ElemTypeitem)

(

for(inti=0;i<S.len;i++)

if(S.set[i]==item)break;

if(i<S.len){

S.set[i]=S.set[S.len-1];

S.len一;

returntrue;//删除成功返回真

)

else

returnfalse;〃删除失败返回假

4.从集合中查找一个元素

此算法首先从集合中顺序查找值等于待查值item的元素，若存在则把该元素值赋给

item引用参数带回，并返回真表示查找成功；若不存在，则返回假表示查找失败。

通常传递给item的待查值是一个元素的关键字，不是完整的记录，如对于学生记录，

待查值是学号，对于产品记录，待查值是产品号；若查询到对应值的元素，则需要把该元素

的完整值赋给item带回，以便彳吏用。如可以通过item得到某个学生的成绩，某个产品的价

格等。

boolFindSet(SetSq&S,ElemType&item)

for(inti=0;i<S.len;i++)

if(S.set[i]==item)break;

if(i<S.len){

item=S.set[i];

returntrue;

)

else

returnfalse;

四、集合的链接存储结构和操作实现

我们知道，集合的顺序存储结构是通过数组实现的，而集合的链接存储结构则不同，它

是通过存储结点之间的依次链接来实现的，从而形成一个链接表。

链接表中的每个结点包含有一个值域data和一个指针域next,值域用来存储集合中相

应的元素，指针域用来指向下一个存储结点。

当链接表中的每个结点只包含有一个指针域时，则称这种链接表为单链表。在一个单链

表中，第一个结点称为表头结点，用来存储集合中的第一个元素，指向第一个结点的指针被

称为表头指针，最后一个结点被称为表尾结点，表尾结点的指针域的值为空，表明它不会指

向任何结点。

在一个单链表中，除表头结点外，每个结点都由其前一个结点的指针域所指向，第一个

结点只能由另设的表头指针所指向。当访问一个单链表时，只能从表头指针出发，首先访问

第一个结点即表头结点，由第一个结点的指针域得到第二个结点的地址，接着访问第二个结

点，再由第二个结点的指针域得到第三个结点的地址，接着访问第三个结点，以此类推，直

到访问完最后一个结点（即指针域为空）的结点为止。

存储集合的单链表中的存储结点定义如下：

structsNode{

ElemTypedata;

sNode*next;

）；

集合的链接存储结构示意图如下图所示。

headata2a：a：”...a„A

其中head为表头指针，它指向存储储元素的第一个结点，该结点的指针域指向存储a?

元素的第二个结点，依次类推，最后存储右元素的结点的指针域为空，链接表到此结束。

下面给出对链接存储的集合S进行初始化以及插入、删除和查找元素的算法，其中集合

S对应的单链表的表头指针为head。

1.初始化集合

voidInitSet（sNode*&head）//置集合为空

head=NULL;〃把表头指针置为空

2.向集合中插入一个元素

(1)顺序查找集合单链表中是否存在值为待插入值item的元素，若存在则不能插入，

因为集合中不允许存在重复的元素，返回假，表示插入失败；

(2)利用item值建立一个新结点tp;

(3)把这个新结点tp插入到单链表的表头，即把原表头指针head赋给tp结点的指针

域，把ip赋给head成为新的表头指针的值；

(4)返回真表示插入成功。

boolInsertSet(sNode*&head,ElemTypeitem)

(

〃从单链表中顺序查找是否存在值为item的结点

sNode*p=head;

while(p!=NULL){

if(p->data==item)break;

elsep=p->next;

)

if(p!=NULL)returnfalse;//插入失败返回假

〃建立值为item的新结点

sNode*tp=newsNode;

tp->data=item;

//新结点tp插入到单链表的表头

tp->next=head;

head=tp;

〃返回真表示插入成功

returntrue;

)

3.从集合中删除一个元素

(1)顺序查找集合单链表中是否存在值为待删除值为item的元素，若不存在则返回假,

表示删除失败；

(2)从单链表中删除结点，即把被删除结点的指针域的值赋给其前驱结点的指针域，若

删除的是单链表中的表头结点，则把该结点的指针域的值赋给表头指针即可；

(3)返回真表示删除成功。

boolDeleteSet(sNode*&head,ElemTypeitem)

(

〃从单链表中顺序查找是否存在值为item的结点

sNode*p=head,*q=NULL;//q指向p的前驱结点，开始时p指表头，q为空

while(p!=NULL){

if(p->data==item)break;

else{q=p;p=p->next;}

)

if(p==NULL)returnfalse;〃删除失败，返回假

〃从单链表中删除已找到的p结点，它的前驱结点为q结点

if(q==NULL)head=p->next;〃删除表头结点，从单链表中摘除

elseq->next=p->next;//删除非表头结点

〃回收p结点后返回真

deletep;

returntrue;

)

4.从集合中查找一个元素

boolFindSet(sNode*head,ElemType&item)

(

〃从单链表中顺序查找是否存在值为item的结点

sNode*p=head;

while(p!=NULL){

if(p->data==item)break;

elsep=p->next;

)

〃若存在由item带回已查找到的元素并返回真，否则返回假

if(p!=NULL){item=p->data;returntrue;}

elsereturnfalse;

五、集合运算的时间复杂度分析

插入运算：若已知插入的元素是集合中没有的，则可以省略从集合中查找该元素的步骤，

把该元素直接写入到集合顺序表的表尾后的位置，使之成为新的表尾，或者把该元素直接链

接到集合单链表的表头，成为新的表头结点，这种情况的时间复杂度为0(1);若在插入时

不省略查找步骤，则向集合插入元素的时间复杂度为03)。

删除运算：需要从集合中先顺序查找出待删除的元素，然后再从集合中删除该元素，所

以其时间复杂度为0(n)。

查找运算：需要顺序查找出给定元素，所以其时间复杂度为0(n)。

六、线性表的存储和运算简介

线性表是线性结构的一种表现形式。

线性表的定义、抽象数据类型、存储结构和运算等都同集合类似。

线性表就是一种线性结构，即是具有相同属性的一个有限序列，序列中的元素是一个接

一个有序的，序列中元素的个数就是该线性表的长度，若用n表示，则n大于等于0,当n

等于0时其线性表为空。线性表中的所有元素通常用一对圆括号括起来，元素之间的位置排

列次序就是它们的先后逻辑顺序。线性表中的元素个数也随着插入和删除元素的变化而变

化。当向线性表中插入一个元素时，其长度就增加1,相反，当从线性表中删除一个元素后，

其长度就减少1。

线性表的抽象数据类型也同样包括数据和操作两个部分，数据部分是一个用顺序或链接

存储的线性表，操作部分包括线性表的初始化，插入、删除、查找元素等操作。

线性表的存储结构也通常采用顺序和链接两种方式，顺序存储方式也是依靠数组实现

的，链接存储方式也是依靠存储结点链接实现的。这都和集合的存储结构类似。

线性表的插入运算与集合结构有所不同。向集合中插入一个元素是插入到顺序存储的集

合的表尾，或者链接存储的集合的表头，它不涉及到其他任何元素或结点的改变；而向线性

表中插入一个元素时，是按照逻辑次序进行插入，若要插入到顺序存储的线性表的第i个元

素之后，则第i+1至第n个的所有位置上的元素都要后移一个位置，腾出第i+1个位置，以

便存储待插入的元素；若要插入到链接存储线性表的第i个元素之后，则要把新插入元素结

点链接到对应的第i个元素结点之后，第i+1个元素结点之前，为此需把第i个结点的指针

域的值赋给新插入结点的指针域，使其指向后继的第i+1个结点，接着把新插入结点的地址

赋给第i个结点的指针域，使其指向新插入的结点。

下面来看一下向线性表插入元素的例子。

假定一个包含6个元素的线性表为(23,15,48,34,79,60)

假定被顺序存储在一维数组A[]的前6个下标位置，如下所示：

下标012345678g

231548347960

假定需要在下标为3的位置插入一个元素56,则首先需要把位置3至表尾位置5的所

有元素依次后移一个位置，注意，应该按下标从大到小的次序，后移对应的元素，使下标为

3的位置空出来，如下所示：

下标012345678g

231548347960

接着把新元素56写入到已经空出的下标为3的位置，如下所示：

下标012345678g

23154856347960

再修改线性表中保存的当前长度的值，使之增加1,即由6变为，这样，对顺序存储

的线性表的插入过程就结束了。

若用链接的方式存储上述所给的线性表，则如下所示：

head23M15用48"34

若要在值为48的结点之后插入一个值为56的新结点，则得到的链接存储结构如下:

head―►23►15—►48—►56f34—*79—*60A

此时，48结点的后继结点不是34结点，而是56结点，即首先需要把原48结点的next

域的值赋给新结点56的指针域使之指向34结点，接着把新结点56的地址赋给48结点的指

针域，使之指向新插入的56结点，这样就完成了在链接存储的线性表上插入元素的运算。

若在顺序存储的线性表上删除一个元素，则需要把该元素位置之后的所有元素依次前移

一个位置，然后再使线性表的长度减1即可。

例如，一个线性表的顺序存储结构为：

下标012345678g

231548347960

若要删除下标为1位置上的元素15,则使其后的每个元素前移，如下所示：

下标012345678g

2348347960

然后，使线性表的长度由6减1后变为5,则删除操作就此完成。

若要在链接存储的线性表上删除一个结点，则同在链接存储的集合上的删除完全相同，

就是把被删除结点的指针域的值赋给其前驱结点的指针域即可。

例如，一个线性表的链接存储结构如下：

head-23用话一川48修34用79用60加

若要从中删除值为34的结点，则把结点34的指针域的值赋给其前驱结点48的指针域即

可，得到的结果如下：

head-23修西闺48川79f60|/\|

特殊地，若删除的是表头结点，即head指针所指向的值为23的结点，则需要把需要把

23结点的指针域的值赋给表头指针变量head,使head指向了值为15的结点，即原单链表

中的第二个结点，运算结果如下：

head—►15—►)48—►34'79—60H

这一讲就讲到这里，同学们再见!

同学们好:

第三讲栈和队列

第一部分栈

一、栈的定义

二、栈的抽象数据类型

三、栈的顺序存储结构和操作实现

四、栈的链接存储结构和操作实现

五、栈的简单应用举例

一、栈的定义

栈（Stack）是一种运算受限的线性表，其限制是仅允许在表的一端进行插入和删除运

算。人们把对栈进行运算的一端称为栈顶，栈顶的第一个元素被称为栈顶元素，相对地，把

另一端称为栈底，向一个栈插入新元素又称为进栈或入栈，它是把该元素放到栈顶元素的上

面，使之成为新的栈顶元素；从一个栈删除元素又称为出栈或退栈，它是才“戋顶元素删除掉，

使其下面的相邻元素成为新的栈顶元素。

在日常生活中，有许多类似栈的例子，如刷洗盘子时，依次把每个洗净的盘子放到洗好

的一摞盘子的上面，此操作相当于进栈；取用盘子时，从一摞盘子上一个接一个地向下拿，

相当于出栈。又如向枪支弹夹里装子弹时，子弹被一个接一个地压入，则称为进栈；射击时

子弹总是从顶部一个接一个地被射出，此称为子弹出栈。

由于栈的插入和删除运算仅在栈顶一端进行，后进栈的元素必定先出栈，所以又把栈称

为后进先出表（LastInFirstOut,简称LIFO）。

假定一个栈S为（a,b,c）,其中表尾的一端为栈顶，字符c为栈顶元素。若向S压入一

个元素d,则S变为（a,b,c,d）,此时字符d为栈顶元素；若接着从栈S中依次删除两个元

素，则首先删除的是元素d,接着删除的是元素c,栈S变为（a,b）,栈顶元素为b.

二、栈的抽象数据类型

栈的抽象数据类型中的数据部分为具有ElemType元素类型的一个栈，它可以采用任一

种存储结构实现；操作部分应包括元素进栈、元素出栈、读取栈顶元素、检查栈是否为空等。

下面给出栈的抽象数据类型的具体定义.

ADTSTACKis"STACK是栈的抽象数据类型名

一个栈S,存储栈中的所有元素

Operation:

voidInitStack(&S);〃初始化栈S,即把它置为空

voidPush(&S,item)//元素进栈，即把元素ilem插入到栈顶

ElemTypePop(&S)//删除栈顶元素并返回之

ElemTypePeek(&S)//返回栈顶元素的值，但不改变栈的状态

boolEmptyStack(&S);//判断S是否为空

voidClearStack(&S);〃清除栈中所有元素，使之成为空栈

endSTACK

对于判断栈是否为空和返回栈顶元素这两种操作，由于它们不改变栈的状态，所以可在

引用参数前使用常量定义符const,使得函数操作不能有意或无意地改变栈的状态。

假定栈a的元素类型为int,下面给出调用上述栈操作的一些例子。

(1)InitStack(a);〃表示把栈a置空

(2)Push(a,18);〃表示元素18进栈

(3)intx=46;Push(a,x);〃表示x的值46进栈

(4)Push(a,x/3);〃表示x除以3的整数值15进栈

(5)x=Pop(a);〃表示栈顶元素15退栈并赋给x

(6)cout<<Peek(a);〃表示读取当前栈顶元素46并输出

⑺Pop(a);〃栈顶元素46出栈，返回值46自动丢失

(8)EmptyStack(a);〃因此时栈a非空，所以返回的值false

(9)cout«Pop(a)«endl;〃栈顶元素18退栈并输出，此时栈已空

(10)x=EmptyStack(a);〃因栈为空，返回true,接着把对应的整数值1赋给x

三、栈的顺序存储结构和操作实现

栈的顺序存储结构同集合的顺序存储结构类似，定义的结构类型如下：

structStack{//Stack为结构类型名

ElemType*stack;〃指向动态分配的数组存储空间的首地址的指针

inttop;〃栈顶指针，存储栈顶元素所在的下标位置

intMaxSize;//保存stack所指向的栈空间的大小

）；

在顺序存储的栈中，top的值为T表示栈空，每次向栈中压入一个元素时，首先使top

增1,用以指示新的栈顶位置，然后再把元素赋值到这个空位置上，每次从栈中弹出一个元

素时，首先取出栈顶元素，然后使top减1,指示出前一个元素成为新的栈顶元素。由此可

知，对顺序栈的插入和删除运算相当于是在顺序表的表尾进行的，其时间复杂度为0（1）。

在一个顺序栈中，若top已经指向了MaxSize-1的位置，则表示栈满，若再向其插入新

元素时就需要进行栈满处理，如分配更大的存储空间满足插入要求，或输出栈满信息告之用

户等；相反，若top的值已经等于T,则表示栈空，通常利用栈空作为循环结束的条件，表

明栈中的数据已经处理完毕。

设一个栈S为（a,b,c,d,e）,对应的顺序存储结构如下图（a）所示。若向S中插入一个元

素3则对应如下图（b）所示。若接着执行两次出栈操作后，贝U栈S对应如下图（c）所示。若

依次使栈S中的所有元素出栈，则s变为空，如下图（d）所示。

MaxSize-1MaxSize-1MaxSize-1MaxSize-1

............

•••…•••

5f◄—top

4e<—top4e44

3d3d3d4—top3

2c2c2c2

1b1b1b1

0a0a0a0

(a)top=4(b)top=5(c)top=3(d)top二T

下面给出栈在顺序存储结构下的操作实现。

1.初始化栈S为空

初始化顺序栈需要为其动态分配数组存储空间，并使stack指向这个数组空间，该空间

的大小由参数ms决定，当然ms的值要大于等于L

voidInitStack(Stack&S,intms)

(

if(ms<=0){cout«nms值非法!"«endl;exit(1);}

〃初始设置栈空间大小为ms的值

S.MaxSize=ms;

//动态存储空间分配

S.stack=newElemType[S.MaxSize];

//初始置栈为空

S.top=-l;

)

2.元素item进栈，即插入到栈顶

voidPush(Stack&S,ElemType