数据结构绪论0906课件

中山大学1学习<数据结构>的意义：数据结构是计算机及相关专业中一门重要的专业基础课程。数据的表示及数据的处理是用计算机来解决实际问题时，首要涉及的主要问题，而数据表示及数据处理正是数据结构课程的主要研究对象。数据结构是后续专业课程（操作系统等）的基础，为软件方面的课程打下了厚实的知识基础，同时也提供了必要的技能训练。。

中山大学2学习<数据结构>的要求：在基础方面，要求学生掌握常用数据结构的基本概念及其不同的实现方法；在技能方面，通过系统学习能够在不同存储结构上实现不同的运算，并对算法设计的方式和技巧有所体会。中山大学3本课程讲述的主要内容本课程将分别讲述数据结构的基本概念、线性表、栈和队列、串和数组、树形结构、图结构、查找、排序和文件等内容。中山大学4学习本课程的基本方法上课认真听讲；仔细阅读教材中的大量例题，从而体会并最终掌握数据结构中的基本概念；独立完成每个章节后面的练习题；多上机实验，用程序验证算法的正确性。在实践中体会构造性思维的方法，掌握数据组织与程序设计的技术。中山大学5第一章绪论1.1数据结构研究的主要内容；1.2基本概念；1.3算法和算法的衡量；中山大学6

早期计算机应用的特点：数值计算的程序设计问题。

结构应力分析计算： －－－线性代数方程组全球天气预报： －－－环流模式方程1.1数据结构研究的主要内容中山大学71.1数据结构研究的主要内容当今计算机应用的特点：1、所处理的数据量大且具有一定的关系；2、对其操作不再是单纯的数值计算，而更多地是需要对其进行组织、管理和检索。

中山大学8应用举例1——学籍档案管理假设一个学籍档案管理系统应包含如下表1-1所示的学生信息。中山大学9应用举例1——学籍档案管理

特点：每个学生的信息占据一行，所有学生的信息按学号顺序依次排列构成一张表格；表中每个学生的信息依据学号的大小存在着一种前后关系，这就是我们所说的线性结构；对它的操作通常是插入某个学生的信息，删除某个学生的信息，更新某个学生的信息，按条件检索某个学生的信息等等。中山大学10应用举例2——制定教学计划在制定教学计划时，需要考虑各门课程的开设顺序。有些课程需要先导课程，有些课程则不需要，而有些课程又是其他课程的先导课程。比如，计算机专业课程的开设情况如下表1-2所示：中山大学11应用举例2——制定教学计划c1c9c4c2c12c10c11c5c3c6c7c8图1-2计算机专业必修课程开设先后关系中山大学12应用举例2——制定教学计划特点：1、课程之间的先后关系用图结构描述；2、通过实施创建图结构，按要求将图结构中的顶点进行线性排序。

在八皇后问题中，处理过程不是根据某种确定的计算法则，而是利用试探和回溯的探索技术求解。为了求得合理布局，在计算机中要存储布局的当前状态。从最初的布局状态开始，一步步地进行试探，每试探一步形成一个新的状态，整个试探过程形成了一棵隐含的状态树。如图1.2所示（为了描述方便，将八皇后问题简化为四皇后问题）。回溯法求解过程实质上就是一个遍历状态树的过程。在这个问题中所出现的树也是一种数据结构，它可以应用在许多非数值计算的问题中。应用举例3——八皇后问题中山大学14结论由以上三个例子可见，描述这类非数值计算问题的数学模型不是数学方程，而是表、图和树之类的数据结构。因此从广义上讲，数据结构描述现实世界实体的数学模型及其上的操作在计算机中的表示和实现。学习数据结构的目的是为了了解计算机处理对象的特性，将实际问题中所涉及的处理对象在计算机中表示出来并对它们进行处理。与此同时，通过算法训练来提高学生的思维能力，通过程序设计的技能训练来促进学生的综合应用能力和专业素质的提高。中山大学151.2.基本概念一、数据和数据结构；二、数据类型；三、抽象数据类型ADT；

中山大学16一、数据和数据结构1、数据的定义:定义一：数据是客观事物的符号表示。例：张三的C语言考试成绩为92分，92就是该同学的成绩数据。中山大学17一、数据和数据结构定义二：能输入到计算机中并被计算机程序处理的符号的总称。例：图像、声音等。总结：现实世界信息的分析、复制、传播首先要符号化，这样才便于处理，尤其是便于计算机的处理。家长、社会要了解一个学生的学习成绩和能力，要看他的学习档案，而学习档案即是说明该学生学习情况的数据。中山大学182、数据元素和数据项:数据的基本单位。在计算机程序中常作为一个整体进行考虑和处理。有时一个数据元素可以由若干数据项(DataItem)组成。数据元素又称为元素、结点、记录。

一、数据和数据结构中山大学19一、数据和数据结构有两类数据元素:一类是不可分割的“原子”型数据元素，如整数“3”，字符”N”等；一类是由多个款项构成的数据元素，其中每个款项称为“数据项”。例如描述一个学生的信息的数据元素可由下列6个数据项组成。其中的出身日期又可以由三个数据项："年"、"月"和"日"组成，则称"出身日期"为"组合项"，而其它不可分割的数据项为"原子项"。

中山大学20一、数据和数据结构数据项是具有独立含义的最小标识单位，数据元素是数据项的集合。关键字：指的是能识别一个或多个数据元素的数据项。若能起唯一识别作用，则称之为“主”关键字，否则称之为"次"关键字。

中山大学213、数据对象：

具有相同性质的数据元素的集合。是数据的一个子集。整数数据对象：N={0,1,2,…}字母字符数据对象： C={‘A’,‘B’,‘C’,…‘F’}一个班级的成绩表可以看作一个数据对象。一、数据和数据结构中山大学224、数据结构： 若在特性相同的数据元素集合中的数据元素之间存在一种或多种特定的关系，则称该数据元素的集合为“数据结构”，换句话说，数据结构是带“结构”的数据元素的集合。“结构”即指数据元素之间存在的关系。

一、数据和数据结构中山大学23例1:在2行3列的数组{a1,a2,a3,a4,a5,a6}中6个元素之间存在两个关系:a1,a3,a5a1,a2,a3

a2,a4,a6a4,a5,a6行的次序关系:row={<a1,a2>,<a2,a3>,<a4,a5>,<a5,a6>}列的次序关系:col={<a1,a4>,<a2,a5>,<a3,a6>}一、数据和数据结构中山大学24例2:一维数组{a1,a2,a3,a4,a5,a6}中存在次序关系:

{<ai,ai+1>|i=1,2,3,4,5} 不同的关系构成不同的结构，所以说数据结构是带有结构的数据元素的集合。一、数据和数据结构中山大学25数据结构的形式定义为：数据结构是一个二元组，数据结构可描述为

Data_Structures=（D，S）有限个数据元素的集合有限个结点间关系的集合一、数据和数据结构其中，D是数据元素的有限集，S是D上关系的有限集。中山大学26数据的逻辑结构从逻辑关系上描述数据，与数据的存储无关；从具体问题抽象出来的数据模型；与数据元素本身的形式、内容无关；一、数据和数据结构中山大学27数据的逻辑结构可归结为以下四类:

1.集合：元素间为松散的关系。结构中的数据元素除了同属于一种类型外，别无其它关系;一、数据和数据结构中山大学282.线性结构：结构中的数据元素之间为严格的一对一关系。86胡孝臣986110395刘忠赏9861107100张卓9861109成绩姓名学号一、数据和数据结构中山大学293.树形结构：结构中的数据元素之间为严格的一对多关系。一、数据和数据结构中山大学304.图状结构或网状结构：结构中的数据元素之间为多对多关系。一、数据和数据结构中山大学31数据的存储结构数据结构在计算机中的表示。数据的存储结构依赖于计算机语言。顺序存储表示链接存储表示索引存储表示散列存储表示一、数据和数据结构中山大学32数据的存储结构－数据的逻辑结构在存储器中的映象。“数据元素”的映象？“关系”的映象？

一、数据和数据结构中山大学33数据元素的映象方法：用二进制位（bit）的位串表示数据元素。计算机中存储信息的最小单位：位，8位为一字节，两个字节为一字，字节、字或更多的二进制位可称为位串。在逻辑描述中，把位串称为元素或结点。一、数据和数据结构中山大学34当数据元素由若干数据项组成时，位串中对应于各个数据项的子位串称为数据域。例：学生成绩表数据用C语言的结构体数组

classonestu[50]来存储：

structstu{

intstuno;/*数据项，也称stu位串中的一个子位串，或叫做数据域*/

charname[20];

intmaths;

intlanguage;

intc_language;

}classonestu[50];一、数据和数据结构中山大学35“关系”的映象方法：

（表示

x,y

的方法）

顺序映象：以相对的存储位置表示后继关系。例如:令y的存储位置和x的存储位置之间差一个常量C。而C是一个隐含值，整个存储结构中只含数据元素本身的信息。一、数据和数据结构cyx中山大学36链式映象：以附加信息(指针)表示后继关系。以和x绑定在一起的附加信息（指针）表示后继关系，来指示y的存储位置。一、数据和数据结构yx中山大学37在不同的编程环境中， 存储结构可有不同的描述方法，当用高级程序设计语言进行编程时，通常可用高级编程语言中提供的数据类型描述之。一、数据和数据结构中山大学38二、数据类型数据类型

定义：一组性质相同的值集合以及定义在这个值集合上的一组操作的总称。数据类型中定义了两个集合，即该类型的取值范围，该类型中可允许使用的一组运算。中山大学39数据类型是和数据结构密切相关的一个概念。它最早出现在高级程序设计语言中，用以刻划程序中操作对象的特性。高级语言中的数据类型就是已经实现的数据结构的实例。从这个意义上讲，数据类型是高级语言中允许的变量种类，是程序语言中已经实现的数据结构（即程序中允许出现的数据形式）。在高级语言中的整型类型，则它可能的取值范围是-32768到+32767之间，可用的运算符集合为加、减、乘、除、乘方、取模（如C语言中+，-，*，/，%）。中山大学40二、数据类型在高级程序设计语言中，数据类型可分为两类：

数据类型封装了数据存储与操作的具体细节

中山大学41三、抽象数据类型抽象数据类型(AbstractDataType简称ADT)定义了一个数据对象，数据对象间各元素间的结构关系，以及一组处理数据的操作。抽象数据类型的最重要特点是：数据抽象信息隐藏。中山大学42三、抽象数据类型数据抽象：抽象的本质是抽取反映问题的本质点，忽视非本质的细节，从而使设计的数据结构更具有一般性，可以解决一类问题。信息隐藏：

对用户隐藏数据存储和操作实现的细节，使用者仅需了解操作或界面服务，通过使用界面服务来访问数据。中山大学43三、抽象数据类型ADT包括定义和实现两方面，其中定义是独立于实现的。定义：ADT定义该抽象数据类型需要包含哪些信息，并根据功能确定公共界面的服务，使用者可以使用公共界面中的服务对该抽象数据类型进行操作。实现：ADT实现作为私有部分封装在其实现模块内，使用者不能看到，也不能直接操作该数据类型所存储的数据，只有通过界面中的服务来访问这些数据。中山大学44三、抽象数据类型抽象数据类型的描述抽象数据类型可用（D，S，P）三元组表示 其中，D是数据对象，S是D上的关系集，P是对D的基本操作集。 ADT抽象数据类型名{

数据对象：〈数据对象的定义〉

数据关系：〈数据关系的定义〉

基本操作：〈基本操作的定义〉 }ADT抽象数据类型名其中,数据对象、数据关系用伪码描述；基本操作定义格式为：

基本操作名（参数表） 初始条件：〈初始条件描述〉 操作结果：〈操作结果描述〉基本操作有两种参数：赋值参数只为操作提供输入值；引用参数以&打头，除可提供输入值外，还将返回操作结果。“初始条件”描述了操作执行之前数据结构和参数应满足的条件，若不满足，则操作失败，并返回相应出错信息。“操作结果”说明了操作正常完成之后，数据结构的变化状况和应返回的结果。若初始条件为空，则省略之。中山大学46例：抽象数据类型复数的数据结构定义如下：

ADTComplex｛

数据对象：

D=｛e1，e2|e1，e2属于实数集｝

数据关系：

S＝｛<e1，e2>

|e1是复数的实数部分，e2是复数的虚数部分｝三、抽象数据类型中山大学47基本操作：InitComplex（&Z，v1，v2）操作结果：构造复数Z，其实部和虚部分别被赋予参数v1，v2的值。DestroyComplex（&Z）操作结果：复数Z被销毁。GetReal（Z，&realPart）初始条件：复数Z已存在。操作结果：用realPart返回复数Z的实数部分值。三、抽象数据类型中山大学48GetImage（Z，&ImagePart）：初始条件：复数Z已存在。操作结果：用RealPart返回复数Z的虚数部分值。Add（Z1

，Z2

，&Sum）：初始条件：Z1

，Z2是复数。操作结果：用Sum返回两个复数Z1

，Z2

的和值。｝ADTComplex三、抽象数据类型中山大学491.3算法和算法的衡量定义：算法是为了解决某类问题而规定的一个有限长的操作序列。计算机对数据的操作可以分为数值性和非数值性两种类型。在数值性操作中主要进行的是算术运算；而在非数值性操作中主要进行的是检索、排序、插入、删除等等。中山大学50一、算法的五个特性1.有穷性：对于任意一组合法的输入值，在执行有穷步骤之后一定能结束，且算法中的每个步骤都可在有限时间内完成；haha(){/*onlyajoke,donothing.*/

}

main(){printf(“请稍等...您将知道世界的未日...”);

while(1)

haha();

}中山大学51一、算法的五个特性2.确定性：对于每种情况下所应执行的操作，在算法中都有确切的规定，使算法的阅读者或执行者都能明确其含义及如何执行。并且在任何条件下，算法只能有唯一的一条执行路径，即对于相同的输入只能得出相同的输出。中山大学52一、算法的五个特性3.可行性：算法中描述的操作都必须足够基本，都可以通过已经实现的基本运算执行有限次来实现的.中山大学53一、算法的五个特性4.有输入：作为算法加工对象的量值，通常体现为算法中的一组变量。有些输入量需要在算法执行过程中输入，而有的算法表面上可以没有输入，实际上已被嵌入算法之中。中山大学54一、算法的五个特性5.有输出:它是一组与“输入”有确定关系的量值，有一个或多个输出，是算法进行信息加工后得到的结果，这种确定关系即为算法的功能。中山大学55算法与程序的区别算法是解决问题的一种方法或一个过程，考虑如何将输入转换成输出，一个问题可以有多种算法。程序是用某种程序设计语言对算法的具体实现。主要区别在：有穷性和描述方法1、程序可以是无穷的，例如OS，算法是有穷的；2、程序是用程序设计语言描述，在机器上可以执行；算法还可以用框图、自然语言等方式描述。中山大学56二、算法设计的原则设计算法时，通常应考虑达到以下目标：1．正确性2.可读性3．健壮性4．高效率与低存储量需求中山大学57二、算法设计的原则1.正确性：

首先，算法应当满足以特定的“规格说明”方式给出的需求。 其次，对算法是否“正确”的理解可以有以下四个层次： a、程序不含语法错误；b、程序对于几组输入数据能够得出满足规格说明要求的结果；中山大学58二、算法设计的原则c、程序对于精心选择的典型、苛刻而带有刁难性的几组输入数据能够得出满足规格说明要求的结果。d、程序对于一切合法的输入数据都能产生满足规格说明要求的结果。中山大学59中山大学60二、算法设计的原则2.可读性：

算法主要是为了人的阅读和交流，其次才是为计算机执行。因此，算法应该易于人的理解；另一方面，晦涩难读的程序易于隐藏较多的错误而难以调试；中山大学61二、算法设计的原则3.健壮性：

算法应具有容错处理。当输入非法数据时，算法应对其作出反应，而不是产生莫名其妙的输出结果。并且，处理出错的方法不应是中断程序的执行，而应是返回一个表示错误或错误性质的值，以便在更高的抽象层次上进行处理。中山大学62二、算法设计的原则4、高效率与低存储量需求：

通常，效率指的是算法执行的时间；对于解决同一问题的多个算法，执行时间短的算法效率高。存储量需求指算法执行过程中所需要的最大存储空间。一般，这两者与问题的规模有关。二、算法设计的原则中山大学63设计实现算法过程步骤1.找出与求解有关的数据元素之间的关系2.确定在某一数据对象上所施加运算3.考虑数据元素的存储表示4.选择描述算法的语言5.设计实现求解的算法，并用程序语言加以描述。中山大学64中山大学65最简单的方法是使用自然语言。用自然语言来描述算法的优点是简单且便于人们对算法的阅读。缺点是不够严谨。可以使用程序流程图、N-S流程图等算法描述工具。其特点是描述过程简洁、明了。用以上两种方法描述的算法不能够直接在计算机上执行，若要将它转换成可执行的程序还有一个编程的问题。

三、算法的描述中山大学66

使用某种程序设计语言来描述算法，与具体的语言结合紧密，为具体程序设计语言量身定制，易于用所用的具体语言实现；但描述算法时需要考虑具体程序设计语言的要求(语法，类的定义、继承、扩展等)，不利于从整体上描述算法思想，所描述的算法可读性差，算法性能分析较困难，不同的语言，算法描述差异较大，缺乏通用性；

三、算法的描述中山大学67为了解决理解与执行这两者之间的矛盾，人们常常使用一种称为伪码语言的描述方法来进行算法描述。

伪码语言介于高级程序设计语言和自然语言之间，它忽略高级程序设计语言中一些严格的语法规则与描述细节，因此它比程序设计语言更容易描述和被人理解，而比自然语言更接近程序设计语言。它虽然不能直接执行但很容易被转换成高级语言。

三、算法的描述中山大学68三、算法的描述

“类C”描述语言是通过对C语言进行精心筛选保留的一个核心子集，并为了便于描述，又做了若干扩展修改，从而，增强了语言的描述功能。中山大学69#defineTRUE1#defineFALSE0#defineOK1#defineERROR0#defineOVERFLOW-1数据结构的表示都用类型定义typedef的方式描述。数据元素被约定为ElemType类型，用户需要根据具体情况，自行定义该数据类型。

1.预定义常量及类型中山大学70函数类型函数名（函数参数表）{

语句序列；

}为了简化函数的书写，提高算法描述的清晰度，我们规定除函数参数表中的参数需要说明数据类型外，函数中使用的局部变量可以不做变量说明，必要时给出相应的注释即可。另外，在书写算法时，应该养成对重点语句段落添加注解的良好习惯。2.算法描述为以下的函数形式中山大学71简单赋值变量名=表达式；串联赋值变量名1=变量名2=...=变量名n=表达式；成组赋值

（变量名1，...，变量名n）=（表达式1，...，表达式n）；3.

使用的赋值语句形式有中山大学72结构赋值结构名1=结构名2；结构名=（值1，值2，...，值n）；条件赋值变量名=条件表达式?表达式1：表达式2；交换赋值变量名1

变量名2；3.

使用的赋值语句形式有中山大学73条件语句1if（表达式）语句；条件语句2if（表达式）语句；

else语句；开关语句1switch（表达式）{case值1：语句序列1；break；case值2：语句序列2；break；...case值n：语句序列n；break；default：语句序列n+1；}4.使用的选择结构语句形式有中山大学745.使用的循环结构语句形式有for循环语句

for（表达式1；循环条件表达式；表达式2）语句；while循环语句while（循环条件表达式）语句；

do-while循环语句do{语句序列；}while（循环条件表达式）；中山大学756.使用的结束语句形式有函数结束语句return表达式；return;case或循环结束语句break;异常结束语句exit（异常代码）；中山大学767.使用的输入输出语句形式有输入语句scanf([格式串]，变量名1，...，变量名n)；输出语句printf([格式串]，表达式1，...，表达式n);方括号（[]）中的内容是可以省略的部分。中山大学778.使用的扩展函数和注释格式求最大值max（表达式1，...，表达式n）；这个函数返回参数表中n个表达式计算结果中的最大值。求最小值min（表达式1，...，表达式n）；这个函数返回参数表中n个表达式计算结果中的最小值。单行注释//文字序列中山大学78四、算法效率的衡量方法和准则

评价算法的标准： 评价一个算法主要看这个算法所占用机器资源的多少，而这些资源中时间代价与空间代价是两个主要的方面，通常是以算法执行所需的机器时间和所占用的存储空间来判断一个算法的优劣。

中山大学79四、算法效率的衡量方法和准则

算法执行的时间是算法问题规模的函数。评价一个算法的优劣，可以在相同的规模下，考察算法执行时间的长短来进行判断。而一个程序的执行时间通常有两种方法：

1、事后统计法；缺点：1、必须执行程序2、其它因素掩盖算法本质2、事前分析估算法；

中山大学80四、算法效率的衡量方法和准则和算法执行时间相关的因素：1、算法本身选用的策略；2、问题的规模（规模越大，消耗时间越多）；3、编写程序的语言（语言越高级，消耗时间越多）；4、编译程序产生的机器代码质量；5、计算机执行指令的速度；中山大学81四、算法效率的衡量方法和准则

1、算法的执行时间：一个算法的执行时间大致上等于其所有语句执行时间的总和，对于语句的执行时间是指该条语句的执行次数和执行一次所需时间的乘积。中山大学82四、算法效率的衡量方法和准则

分析：由于语句的执行要由源程序经编译程序翻译成目标代码、目标代码经装配再执行，语句执行一次实际所需的具体时间是与机器的软、硬件环境（机器速度、编译程序质量、输入数据量等）密切相关，与算法设计的好坏无关，所以，所谓的算法分析不是针对实际执行时间的精确的算出算法执行具体时间的分析，而是针对算法中语句的执行次数做出估计，从中得到算法执行时间的信息。中山大学83四、算法效率的衡量方法和准则

2、语句频度：该语句在一个算法中重复执行的次数。中山大学843、时间复杂度:一个算法的时间复杂度是该算法的时间耗费，一般地说，时间复杂度是问题规模的函数－T(n)。算法中语句重复执行次数的数量级就是时间复杂度。四、算法效率的衡量方法和准则中山大学85时间复杂度的表示方法：T(n)=O(f(n))

f(n)表示基本操作重复执行的次数，是n的某个函数，随问题规模n的增大，算法执行时间的增长率和f(n)的增长率属于同一数量级；O表示f(n)和T(n)只相差一个常数倍。T（n)称做渐进时间复杂度，简称时间复杂度。一般情况下，随n的增大，T（n)的增长较慢的算法为最优的算法。四、算法效率的衡量方法和准则中山大学861、我们假定，每条语句一次执行的时间都是相同的，为单位时间。这样我们对时间的分析就可以独立于软硬件系统。算法的时间复杂度是该算法中所有语句的执行频度之和。算法时间复杂度分析例：求两个方阵的乘积C＝A*B＃definen自然数MATRIXMLT(floatA[n][n],floatB[n][n],floatC[n][n]){inti,j,k;for(i=0;i<n;i++)//n+1for(j=0;j<n;j++)//n(n+1){C[i][j]=0;//n*nfor(k=0;k<n;k++)//n*n*(n+1)C[i][j]=A[i][k]*B[k][j]//n*n*n}}中山大学882、一般情况下，对步进循环语句只考虑循环体语句的执行次数，而忽略该语句中部长加一、终值判别、循环转移等成份。因此，当有若干个循环语句时，算法的时间复杂度是由嵌套层数最多的循环语句中最内层语句的频度所决定的。算法时间复杂度分析例：x=0;y=0;for(k=1;k<=n;k++)x++;for(i=1;i<=n;i++)

for(j=1;j<=n;j++)

y++;

//n*n

T(n)

=

n2算法时间复杂度分析中山大学903、选择执行的成分，如if语句的执行时间，决定于then子句、else子句耗时较多的部分4、如果算法的执行时间是一个与问题规模n无关的常数，则算法的时间复杂度为常数阶，记作T(n)=O(1)。例：temp=i;i=j;j=temp;

算法时间复杂度分析中山大学915、很多算法的时间复杂度不仅与问题的规模有关，而且还与它所处理的数据集的状态有关。通常是根据数据集中可能出现的最坏情况估计出算法的最坏时间复杂度。算法时间复杂度分析中山大学92算法时间复杂度分析例.对n个整数的序列进行冒泡排序，其中序列的“长度”n为问题的规模。voidbubble-sort(inta[]，intn)for(I=n-1;change=TURE;I>1&&change;--I){//将a中整数序列重新排列成自小至大有序的整数序列。change=false;for(j=0;j<I;++j)if(a[j]>a[j+1]){