数据结构-西南财经大学.ppt

数 据 结 构 刘家芬 Sept 2011 第一章 绪 论 1.1 什么是数据结构 1.2 基本概念和术语 1.3 抽象数据类型的表示与实现 1.4 算法和算法分析 1.4.1 算法 1.4.2 算法设计的要求 1.4.3 算法效率的度量 1.4.4 算法的存储空间的需求 为什么我们需要学习这门课程？ Programmer VS Coder？ 程序设计语言的后续课程：数据结构+算法 计算机解决问题的步骤：从具体问题抽象出数学模型，针对此模型设计算法，然后用哪个程序实现。 问：我不想成为程序员，也需要学习这门课吗? 答：这是一门通用学科，有助于我们理清解决问题的思路，明确解决问题的步骤。 计算机的程序就是对信息进行加工处理。 在大多数情况下，这些信息并不是没有组织，他们之间往往具有重要的结构关系，这就是数据结构的研究内容。 我们实际上已经学过一些数据结构，请举例。 1.1什么是数据结构 设有一个电话号码薄，它记录了N个人的名字和其相应的电话号码。 要求设计一个算法，当给定任何一个人的名字时，该算法能够打印出此人的电话号码，如果该电话簿中根本就没有这个人，该算法能够给出提示信息。 例：电话号码查询算法 例1、图书馆的书目检索系统自动化问题 例2、计算机和人对弈问题 例3、多叉路口交通灯的管理问题 总结：数据结构就是研究数据的逻辑结构和物理结构以及它们之间相互关系，并利用这种关系进行计算的学科。 特点：通用学科 + 交叉学科 数据结构的研究内容？ 数据(Data):对客观事物的符号表示。在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号的总称。 数据元素(Data Element):是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。 一个数据元素可由若干个数据项组成。数据项是数据的不可分割的最小单位。 例如：电话簿上的一条信息可以看做一个数据元素，但信息的每一项（人名、电话号码）是一个数据项。 1.2 基本概念和术语 数据对象(Data Object)：是性质相同的数据元素的集合，是数据的一个子集。 整数数据对象{…-2，-1，0，1，2，…} 字符数据对象{‘1’, ‘$’, ‘A’,‘B’, ‘C’, …} 数据结构(Data Structure)：是相互之间存在一种或多种特定关系的数据元素的集合。 物理结构 逻辑结构 1.2 基本概念和术语 逻辑结构可分为四类： 集合 结构中的数据元素除了同属于一种类型外，别无其它关系。 线性结构 结构中的数据元素之间存在一对一的关系。 树型结构 结构中的数据元素之间存在一对多的关系。 图状结构或网状结构 结构中的数据元素之间存在多对多的关系 逻辑结构的分类 * 用图形表示下列数据结构，并指出它们是属于线性结构还是非线性结构。 S=(D, R) D={ a, b, c, d, e, f } R={(a,e), (b,c), (c,a), (e,f), (f,d)} 上述表达式可用图形表示为： b c a e f d 此结构为线性的。 例：逻辑结构 * 用图形表示下列数据结构，并指出它们是属于线性结构还是非线性结构。 S=(D, R)D={di | 1≤i≤5}R={(di , dj ), ij} 例：逻辑结构 d1 d5 d2 d4 d3 该结构是非线性的。 数据结构在计算机中的表示称为数据的物理结构，又称为存储结构。 顺序存储：借助元素在存储器中的相对位置来表示数据元素之间的逻辑关系。 非顺序存储（链式存储）：借助指针表示数据元素之间的逻辑关系。 物理结构 数据结构是一个二元组： Data-Structure=(D，S) 其中：D是数据元素的有限集， S是D上关系的有限集。 例1-5：P5 数据结构的形式化定义 数据类型 可以理解为数据对象在高级程序设计语言中的实现。 一个值的集合 + 在这个集合上定义的一组操作 可分为原子类型和结构类型 在C语言中 原子类型：整型、浮点型、字符型 结构类型：数组、结构体、共用体、指针 数据类型 抽象数据类型（ADT）：一个数学模型以及定义在该模型上的一组操作。 抽象数据类型实际上就是对某种数据结构的定义，例如数组。 抽象数据类型 抽象数