数据结构——C语言描述第1章-绪论.pptxVIP

数据结构——C语言描述（慕课版）

第1章绪论

编著：张同珍学校：上海交通大学

绪论

数据结构定义

基本操作

存储结构

逻辑结构

算法

算法的时空复杂度

数据结构：

数据是外界信息进入计算机，并被计算机处理的符号，数据元素是数据的基本单位。

如有一组学生信息，每个学生信息是一个结构类型数据，包含了学号、姓名、年龄等字段，那么这组学生信息是数据，每一个学生信息是数据元素。

数据结构：是指相互之间具有一定关系的相同类型的数据元素的集合。

数据结构的研究对象：

1.元素之间的关系（逻辑结构）

2.元素关系操作

3.元素和关系在内存中的存储（物理结构）

4.在各种存储方式下关系操作的实现

5.每种数据结构的典型应用

研究数据的逻辑结构就是研究类型相同的一组元素和元素间的关系。

数据的逻辑结构

集合关系：元素间呈松散关系，结构中不同元素除了同属于一个集合，相互间并无其他制约关系。如同班级里同学间的关系。

线性关系：元素间呈现出你先我后的顺序，是一种一对一的关系。如队列中元素间的关系。除了队首，每个元素有且只有一个唯一的直接前驱元素；除了队尾，每个元素有且只有一个唯一的直接后继元素。

树形关系：元素间呈现出一对多的关系。如家谱中人物间关系，一个人可以有多个儿子，却只能有一个父亲。即每个元素可以有多个后继，却只能有一个前驱。

图关系：元素间呈现多对多的关系。如城市间通过飞机航线形成的关系，例如上海、北京、西安3个城市中，任何两个城市间都可以有直飞航线。

分以下几种：

数据的逻辑结构：

逻辑结构通常可以用二元组描述:Data_Struct=(D,R)，其中D是元素的集合，R是关系的集合。

例如整数1~10组成的有序集就是一个线性结构。

D={𝑥|1≤𝑥≤10，𝑥∈𝑁}，R={〈𝑥1,𝑥2〉│𝑥1∈𝐷,𝑥2∈𝐷}。其中〈𝑥1,𝑥2〉表示一个有序偶，即x1和x2有顺序关系，x1是直接前驱，x2是直接后继。

关系操作（或称基本操作）

是和数据的逻辑结构紧密相关的，它来源于关系自身的特点。

构造类：在内存中建立这种数据结构。如一个空的队列。

基本操作都可以分为五大类：构造类、属性类、数据操纵类、遍历类、典型应用类。

属性类：对元素及元素之间的关系的各类查询。属于东瞧瞧、西看看，不影响元素及元素关系本身。

数据操纵类：对元素或元素关系有改变的操作，如插入或删除某个元素。修改可视作删除后插入。

遍历类：对结构中的每个元素访问且只访问一遍。

典型应用类：所属结构独特的应用，不同结构其典型应用各不相同。

数据的逻辑结构+基本操作=抽象数据类型ADT（AbstractDataType）。

ADT和在计算机内的表示、实现无关，只和数据自身的逻辑特征相关。

ADT类似高级语言中的数据类型，如整型:一个整数集合以及在这个集合中系统支持的基本操作（四则运算、比较运算等）。

ADT区别于具体某种类型，只关心元素关系和关系操作，不实际要求数据的具体类型，只要元素类型一致。

ADT的描述可以用自然语言也可以用伪代码，其内容包含元素集合、元素关系集合、基本操作。

基本操作表明生活中的一个个基本的问题，有明确的已知条件和结果要求。

基本操作的具体实现依赖于数据和数据关系在内存中如何存储，在逻辑结构分析阶段并不知道存储方式，因此无法给出，也不需要考虑。

顺序存储是用一块连续的空间来存储数据，同时借助这组空间在地址上的邻接及有序性来存储元素之间的关系，顺序存储的结构称顺序结构。

高级语言中的数组可以实现连续空间的获取，帮助实现顺序结构。

链式存储是在内存中使用多个独立的内存空间，每个独立的空间除了包括存储元素的空间，还包括附加的空间来存储元素之间的关系。

链式存储的数据结构称链式结构。

存储结构：也称物理结构，是指数据结构在内存中的表示。

常见的存储方式有顺序存储和链式存储两种。

算法及其要求

这里算法是指用计算机解决一个具体问题的方法和步骤。算法必须满足五个特性：

一个算法中的每一步要在有限的时间内完成，而整个算法必须在有限步之后完成。

有穷性：

算法中的每一步都有确定的含义，没有二义性。

确定性：

算法中的每一步都是经过有限次基本操作就可以完成的，每一步自身没有复杂的算法问题。

可行性：

根据问题需要，一个算法可以有零个或者若干个输入作为解决问题的已知条件。

有输入：

算法执行结束后，有零个或者若干个输出作为算法运行结果。

有输出：

算法及其要求

度量算法优劣的几个要素：

准确反映并能满足具体问题的要求，即对于任意一个合法的输入，都能给出正确的结果。

正确性：

可供人们阅读的容易程度，可读性好的算法便于阅读、理解、交流、调试和纠错。

可读性：

对各种不同的输入都要有相应的反应。输入数据合法，要有相应的输出；输入数据不合法，要有相应的响应处理。