数据结构chap1剖析.ppt

数据结构在软件开发中的地位。 一个完整的软件开发过程有这样四个步骤:系统分析的结果是得到甲乙双方均认可的“软件需求说明”，是最后验收的标准文件。系统设计是确定实现方案并编程和测试完成。然后在甲方指定地点安装调试并试甲方人员完全掌握应用。随着使用过程出现的问题乙方还得不断进行软件的调整维护。 数据结构讨论的内容是软件的设计，即进行程序设计。 这是1976年沃尔斯写的一本书的书名，之后却成了人们常用的一句名言，因为它说出了程序设计的实质。 程序设计的目标是要编出让计算机按照人的旨意进行操作的指令，首先要解决两个问题:即算法和数据结构。 算法即处理问题的策略，数据结构即问题的数学模型。 我们从小学到中学到大学学了很多数学的课程，这说明很多科学问题需要抽象到数学问题去求解的，即使是不需要用计算机求解的简单问题也往往需要一个数学模型。例如大家在小学时就学的鸡兔同笼问题，又如在房屋设计或桥梁设计中的结构应力分析计算之后化解到线性代数方程组的问题，再如，天天看到的天气预报，它需要对环流模式方程求解。 以上都是数值计算的问题，他们的数学模型都是数学方程。当计算机进入非数值计算领域特别是用在管理上的时候，计算机的操作对象之间的关系就无法用数学方程加以描述。 例一的问题看起来简单，实际上存在一个无法表示的问题(1012)。 现在街上交叉路口的红绿灯不是一个，而是三个。 因此数据结构讨论的是类似的非数值计算程序设计中的数学模型问题。 这里当然不是讨论怎样从问题到数学模型的过程，而是讨论在非数值程序设计中经常应用的数学模型，它们的特点以及如何在计算机中表示它们和如何对它们进行操作。 这一节讨论的都是有关数据结构的概念，为了突出重点，将它分成三小节， 一是几个简单术语 二重点解释数据结构 三重点解释抽象数据类型 数据是个集合，如果用集合的表示方法来写的话，就是 数据={x|x是计算机操作的对象} 包括所有的数字和字符，图形和声音等信息最后也都可以转化为字符进行处理。 这些字符和数字是客观信息的一种描述。如“3000”，可以表示某个城市的3000万人口，也可表示3000元/平方的房价。 另一类是可以分割的数据元素，即本身是由多个“数据项”构成的。如学生包含多项信息，由于所有的款项合起来才是“学生”的完整信息，所以说数据元素是数据结构中讨论的基本单位。之所以不是最小单位是因为它可以由多个数据项构成，它的值是由软件决定的。 数据项本身也可以由多个数据项组合而成，称之为“组合项”，反之，称之为“原子项”。 又如，二维数组也是一个数据结构， 对2行3列的二维数据来说，它是6个数据元素的集合，并且在数据元素之间存在两个关系。每个关系是一个“次序” 关系。 如果在同样 6 个元素之间只存在一个次序关系，那它是另外一个数据结构。 可见，关系对数据结构的重要性，也正说明数据结构和数据对象之不同处。 因为这种关系是数据元素间客观存在的，和计算机没有关系，所以又称逻辑关系。 以上讨论的都是线性关系，对数据结构来讲，关系不一定是线性的，也可以是非线性的，如社会关系就是一种非线性的层次关系。 又如，在1.1中举例提到的，铺设煤气管道网线中各个点之间的关系是一个“网” 的关系。 由上页定义可见，不同的数据结构取决于数据元素之间存在的是什么关系？ 从关系不同可将数据结构分为四类，如果我们蒋没有关系页看成是一种关系，那它就是集合。这个集合和集合论中讨论的集合是同一概念。 分别如何表示数据元素和关系。 计算机中处理信息的最小单位是一个二进制的“位”，任何数值和字符都可以用二进制位串表示，因此所有数据元素都可以用这样的位串来表示。 当数据元素包括多个数据项时，每个数据项就是一个子位串。 因为关系是有序对的集合，因此关系的表示就落实到有序对的表示即可。也就是说如何来表示“y是x的后继”？ 有两种表示方法。 顺序映象:以相互之间确定的存储位置来表示。在约定的 C 值下，y 的存储位置随 x 而定。 用指针表示后继关系，x 和指针构成一个完整的信息。前者 y 的存储位置是被动确定的，而在此 y 的存储位置是主动的，而指针随 y的确定而确定。 以上是从最低层的数据元素的存储位置来解释存储结构。由于数据结构是在高级语言的层次上来讨论问题，因此也要借用高级语言来描述存储结构。 因为以为数组的实现和顺序映象一致，因此通常用一维数组描述次序关系。 而指针即地址，和语言中的指针概念一致。 同样，对数据元素也要借用语言中的数据类型来描述。 学习过高级语言之后，大家对数据类型的概念都不陌生，相信大家在调试程序中经常还碰到“变量没有说明”的编译出错的信息提示。通过它，编译系统可以帮助你检查出程序中的某些错误。 类型说明的作用是，对“变量”加上两个约束条件:一是变量可取值的范围，二是变量可作的操作。