第1章数据结构(c++描述).ppt

* 第1章 绪论 数据结构（C++描述） 目录 1。1 什么是数据结构 1。2 算法的描述 1。3 算法分析 1。4 退出 1.1什么是数据结构 1.1.1 数据结构示例 1。线性表示例 2。树形结构示例 一层 二层 三层 四层 3。图形结构示例 2．数据元素（data element） 数据元素是组成数据的基本单位。 数据元素是一个数据整体中相对独立的单位。但它还可以分割成若干个具有不同属性的项（字段），故不是组成数据的最小单位。 1.1.2基本术语 1． 数据（data） 数据是指能够输入到计算机中，并被计算机识别和处理的符号的集合。 例如：数字、字母、汉字、图形、图像、声音都称为数据。 3． 数据对象（data object） 是性质相同的数据元素组成的集合，是数据的一个子集。 例如，整数数据对象的集合可表示为N＝{0，±1，±2…….}，字母字符数据对象的集合可表示为C={‘A’,’B’,…’Z’}。 4． 数据类型（data type） 是一组性质相同的值的集合以及定义于这个值集合上的一组操作的总称。 例如，高级语言中用到的整数数据类型，是指由－32768到32767中值构成的集合及一组操作（加、减、乘、除、乘方等）的总称。 5． 抽象数据类型（Abstract Data Type） 是指一个数学模型以及定义在该模型上的一组操作。 在本书中，描述一种抽象数据类型将采用如下书写格式： ADT 抽象数据类型名 is Data: 数据描述 Operations:操作声明 END 1.1.3 数据结构 1． 数据结构（data structure） 是指相互之间存在一种或多种特定关系的数据元素所组成的集合。具体来说，数据结构包含三个方面的内容，即数据的逻辑结构，数据的存贮结构和对数据所施加的运算。这三个方面的关系为： （1）数据的逻辑结构独立于计算机，是数据本身所固有的。 （2）存贮结构是逻辑结构在计算机存贮器中的映像，必须依赖于计算机。 （3）运算是指所施加的一组操作总称。运算的定义直接依赖于逻辑结构，但运算的实现必依赖于存贮结构。 2． 从逻辑结构划分数据结构 数据结构从逻辑结构划分为： （1）线性结构 元素之间为一对一的线性关系，第一个元素无直接前驱，最后一个元素无直接后继，其余元素都有一个直接前驱和直接后继。 （2）非线性结构 元素之间为一对多或多对多的非线性关系，每个元素有多个直接前驱或多个直接后继。 3． 从存贮结构划分数据结构 数据结构从存贮结构划分为： (1)顺序存贮（向量存贮） 所有元素存放在一片连续的存贮单元中，逻辑上相邻的元素存放到计算机内存仍然相邻。 (2) 链式存贮 所有元素存放在可以不连续的存贮单元中，但元素之间的关系可以通过地址确定，逻辑 上相邻的元素存放到计算机内存后不一定是相邻的。 (3)索引存贮 使用该方存放元素的同时，还建立附加的索引表，索引表中的每一项称为索引项，索引项的一般形式是：（关键字，地址），其中的关键字是能唯一标识一个结点的那些数据项。 (4)散列存贮 通过构造散列函数，用函数的值来确定元素存放的地址。 4． 数据结构的抽象描述 数据结构可用二元组D=(K,R)的形式来描述。其中，K={a1,a2,…,an}为元素集合，R={r1,r2,…,rm}为关系的集合。 例1-5 设有一个线性表(a1,a2,a3,a4,a5)，它的抽象描述可表示为D=(K,R),其中K={a1,a2,a3,a4,a5},R={a1,a2,a2,a3,a3,a4,a4,a5}，则它的逻辑结构用图描述见图1-4 。 a1 a2 a3 a4 a5 图1-4 线性表的逻辑结构描述 例1-6 设一个数据结构的抽象描述为D=(K,R),其中K={a,b,c,d,e,f,g,h},r={a,b,a,c,a,d,b,e,c,f,c,g,d,h},则它的逻辑结构用图描述见图1-5。 例 1-7 设一个数据结构的抽象描述为D=(K,R),其中K={1,2,3,4},而R={(1,2),(1,3),(1,4),(2,3),(2,4),(3,4)}, 则它的逻辑结构用图描述见图1-6。 1.2 算法的描述 1.2.1 基本概念 1．算法（algorithm） 通俗地讲，算法就是一种解题的方法。更严格地说，算法是由若干条指令组成的有穷序列，它必须满足下述条件（也称为算法的五大特性）： （1）输入：具有0个或多个输入的外界量（算法开始前的初始量） （2）输出：至少产生一个输出，它们是算法执行完后的结果。 （3有穷性：每条指令的执行次数必须是有限的。 （4)确定性：每条指令的含义都必须明确，无二义性。 （5