数据结构课件.docx

数据结构课件.docx

《数据结构课件.docx》由会员分享，可在线阅读，更多相关《数据结构课件.docx（78页珍藏版）》请在冰点文库上搜索。

数据结构课件

第一讲数据结构概述

一、数据结构的分类

二、数据结构的定义

三、数据结构的图形表示

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

五、数据结构的应用实例

六、算法的时间复杂度

一、数据结构的分类

数据结构又分为数据的逻辑结构和数据的存储结构这两个方面，我们时常把数据的逻辑结构简称为数据结构，而在讨论数据的存储结构时则必须指明是数据的存储结构。

数据结构的分类：

这里是指数据的逻辑结构的分类。

总体来说数据的逻辑结构被分为集合结构、线性结构、树结构和图结构等四种基本类型。

对于一些复杂的数据结构可以由这四种基本的数据结构，根据实际需要进行组合或嵌套所构成。

数据的存储结构分类：

被分为顺序、链接、索引和散列四种，由它们的组合和嵌套可以构成更复杂的存储结构。

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

二、数据结构的定义

1、集合结构

集合结构是指数据中各元素之间没有任何次序。

如一个容器中的所有乒乓球，一个俱乐部里的所有成员，可以认为它们之间没有任何次序，它们均为集合结构。

2、线性结构

线性结构是指数据中各元素之间具有1对1的先后次序关系。

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

所以，它们的表结构都是线性结构。

3、树结构

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

如在一个企业的组织机构中，总经理只有一个，相当于是树根；它下属多个部门，每个部门又各有一个部门经理，相当于是树枝；每个部门又有多名员工，属于部门经理领导，相当于是树叶。

所以，企业的组织结构是一个树结构。

4、图结构

图结构是指数据中各元素之间具有多对多的关系。

这是数据结构中最复杂的结构。

如在一个城市交通图中，所有道路连接成一个复杂的图结构，交叉路口就是图中的顶点，每条道路就是图中的边，从一个交叉路口可以到达与其连接的其他交叉路口。

三、数据结构的图形表示

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

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

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

线性结构中的元素是一个接一个串联起来的，它有一个头元素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构成一对前驱和后继关系，对应图形中的一条有向边，它的起点为A，终点为B，它就构成了R中的一个有序对，同理，B和C、C和D等都是R中的有序对。

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

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

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

R={，，，，，}

因为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={，，，，，，，}

在线性结构和树结构中，若元素个数为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>}

对应的图形表示为：

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

在上面职工表中，还存在职工人员之间领导与被领导的关系，其中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）来代替，这样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，则该算法的时间复杂度为O（n）；对于一个含有双重循环的算法，循环次数的主体呈现在n2数量级上，所以则该算法的时间复杂度为O（n2）。

算法的时间复杂度通常具有O

（1）、O（

）、O（n）、O（log2n）、O（n*log2n）、O（n2）、O（n3）、O（2n）和O（n!

）等形式。

其中O

（1）表示算法的时间复杂度为常量，它不随数据量n的改变而改变，如访问一个数据表中第一个元素时，无论该表的大小如何，其时间复杂度均为O

（1）。

O（

）表示算法的时间复杂度与数据量大小n的平方根成正比，如计算满足不等式

中的最大i值时，其算法的时间复杂度就是O（

）。

具有O（n）数量级的算法被称为具有线性数量级的算法，其运行时间与n成正比，如对一个表进行顺序查找时，其时间复杂度就是O（n）。

有一些算法的时间复杂度为O（log2n），即与n的对数成正比，如在有序表上进行二分查找的算法就是如此。

对数组进行简单插入或选择排序的算法的时间复杂度为O（n2），当n加倍时，其运行时间将增长4倍。

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

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

intSequenceSearch（inta[],intn,intitem）

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

{

for（inti=0;i

if（a[i]==item）returni;

return-1;

}

此算法的时间复杂度主要取决于for循环体被反复执行的次数。

最好情况是第一个元素a[0]的值就等于item，此时只需要进行元素的一次比较就查找成功，相应的时间复杂度为O

（1）；最差情况是最后一个元素a[n-1]的值等于item，此时需要进行同全部n个元素的比较才能查找成功，相应的时间复杂度为O（n）；平均情况是：

每一个元素都有相同的概率（即均为

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

，相应的时间复杂度为O（n），它同最坏情况具有相同的数量级，因为它们之间的比较次数只在n的系数项和常数项上有差别，而在n的指数上没有差别。

当在数组a上顺序比较所有n个元素后仍找不到等于给定值item的元素，则表明查找失败，这种情况所对应的时间复杂度也为O（n）。

对于许多算法来说，平均和最差这两种情况下的时间复杂度的数量级形式往往是相同的，它们主要是差别在最高次幂的系数上。

另外有一些算法，其最好、最差和平均情况下的时间复杂度或相应的数量级都是相同的，如求出n个元素平均值的算法就是如此，其时间复杂度的最好、最差和平均情况均为O（n）。

上面从数据结构的分类、数据结构的定义、数据结构的二元组表示、数据结构的图形表示、数据结构的应用举例等多个方面，对数据结构的含义进行了详细地阐述，以便使同学们能够更好地利用数据结构组织数据和处理问题。

这一讲也同时简要地介绍了算法的时间复杂度，与时间复杂度相类似的还有算法的空间复杂度，它是算法在运行过程中临时占用内存空间大小的相对量度，它也有常量级O

（1）、平方根级O（

）、线性级O（n）、平方级O（n2）、对数级O（log2n）等不同级别。

例如，对于下面的算法：

intf（intn）{

if（n<0）return-1;

elseif（n==0）rerun0;

elseretunn+f（n-1）;

}

这是一个递归算法，其功能是计算出1+2+…+n的累加和，该算法要被递归调用n+1次，其参数值依次为n、n-1、…、1、0，每次调用都是执行一条条件语句，而且都要把n值保存起来，所以该算法的时间复杂度和空间复杂度均为O（n）。

第二讲集合与线性表

一、集合的定义

二、集合的抽象数据类型

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

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

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

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

一、集合的定义

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

该集合中数据元素的个数称为集合的长度，通常用n表示，n≥0。

当n=0时则为空集。

若集合为空，则表示为{}，若非空则表示为：

{a1,a2,…,ai,ai+1,…,an}

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

因为集合中的元素可以按任何次序排列，假定就按元素前后位置编号的次序排列，那么a1就是集合中的第一个元素，a2就是集合中的第二个元素,ai就是第i个元素,an就是第n个（即最后一个）元素。

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

集合中的元素类型可以为任何一种类型，假定用标识符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-1n↓n+1↓MaxSize-1

a1

a2

a3

…

an

在这里，a1元素被存储到数组中下标为0的数组单元中，a2元素被存储到下标为1的单元中，依次类推，最后一个元素an被存储到下标为n-1的单元中，存储集合长度len变量的值等于n，存储数组长度MaxSize变量的值等于数组空间的最大下标值加1。

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

1.初始化集合

初始化集合需要为集合动态分配数组存储空间，并使set指向这个数组空间，该空间的大小由参数ms决定，当然ms的值要大于等于1。

voidInitSet（SetSq&S,intms）

{

if（ms<=0）{cout<<"ms值非法!

"<

（1）;}

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

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

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

}

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

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

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

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

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

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

（4）集合长度增1；

（5）返回真表示插入成功。

对应的算法描述如下：

boolInsertSet（SetSq&S,ElemTypeitem）

{

if（S.len==S.MaxSize）{cout<<"集合空间满!

"<

（1）;}

for（inti=0;i

if（S.set[i]==item）{cout<<"元素已存在!

"<

S.set[S.len]=item;

S.len++;

returntrue;

}

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

此算法首先从集合中顺序查找值等于待删值item的元素，若存在则删除它，删除过程是把最后一个元素直接移动到该元素空出的位置，接着使集合长度减1，返回真表示删除成功；若不存在，则无法删除，返回假表示删除失败。

boolDeleteSet（SetSq&S,ElemTypeitem）

{

for（inti=0;i

if（S.set[i]==item）break;

if（i

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

S.len--;

returntrue;//删除成功返回真

}

else

returnfalse;//删除失败返回假

}

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

此算法首先从集合中顺序查找值等于待查值item的元素，若存在则把该元素值赋给item引用参数带回，并返回真表示查找成功；若不存在，则返回假表示查找失败。

通常