第2章数据结构

《第2章数据结构》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第2章数据结构&为什么要学习数据结构？&什么是程序、软件？N.沃思（NiklausWirth)教授提出：程序=算法+数据结构以上公式说明了如下两个问题：（1）数据上的算法决定如何构造和组织数据（算法→数据结构）。（2）算法的选择依赖于作为基础的数据结构（数据结构→算法）。软件=程序+文档（软件工程的观点）程序设计:为计算机处理问题编制一组指令集算法:处理问题的策略数据结构:问题的数学模型例如:数值计算的程序设计问题结构静力分析计算─━线性代数方程组全球天气预报─━环流模式方程非数值计算的程序设计问题例一:求一组(n个)整数中的最大值算法:基本操作是“比较两个数的大小”模型：？例二：计算机对弈算

2、法：对弈的规则和策略模型：？例三：足协的数据库管理算法：需要管理的项目？如何管理？用户界面？模型：？简言之，数据结构讨论描述现实世界实体的数学模型及其上的操作在计算机中的表示和实现。2.1基本概念&什么是数据结构？&几个概念：数据(Data):是对信息的一种符号表示。在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号的总称。所有能被输入到计算机中，且被计算机处理的符号的集合是计算机操作的对象的总称是计算机处理的信息的某种特定的符号表示形式数据元素(DataElement):是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。数据中的一个“个体”，数据结构中讨论的基本单位

3、。数据元素是数据项的集合姓名俱乐部名称出生日期入队日期职位业绩年月日组合项数据项：数据结构中讨论的最小单位一个数据元素可由若干个数据项组成。数据项是数据的不可分割的最小单位。数据记录:是数据处理领域组织数据的基本单位。数据中的每个数据元素在许多场合被组织成记录的结构。一个数据记录由一个或若干个数据项所组成。数据对象(DataObject)：是性质相同的数据元素的集合。是数据的一个子集。数据类型：在一种程序设计语言中，变量所具有的数据种类。例1、在FORTRAN语言中，变量的数据类型有整型、实型、和复数型例2、在C语言中数据类型：基本类型和构造类型基本类型：整型、浮点型、字符型构造类型：数组、结

4、构、联合、指针、枚举型、自定义数据结构：数据结构指的是数据之间的结构关系。具体地说，它包括数据的逻辑结构和数据的物理结构。数据的逻辑结构——仅考虑数据元素之间的逻辑关系。它包括线性结构（如线性表、栈、队）和非线性结构（如树、二叉树和图）。数据的物理结构——指数据元素在存储器中的表示，即存储结构。比如向量、链表。例如一个含12位数的十进制数可以用三个4位的十进制数表示3214,6587,9345─━a1(3214),a2(6587),a3(9345)在a1、a2和a3之间存在“次序”关系、数据的逻辑结构线性结构树形结构图状结构集合结构数据的物理结构─━逻辑结构在存储器

5、中的映象数据元素的映象方法：用二进制位(bit)的位串表示数据元素(321)10——→(501)8——→(101000001)2A——→(101)8——→(001000001)2关系的映象方法：（表示关系的基本单位是有序对）顺序映象以x和y存储位置的相对关系表示有序对最简单的方法就是使y和x的存储位置之间差一个常量C，而C是一个隐含值，整个存储结构中只含数据元素本身的信息例如:(a1,a2,a3)a1a2a3链式映象x和y的存储位置随意，则需要用一个和x在一起的附加信息指示y的存储位置，这个附加信息和x绑定在一起，此时，两者合在一起作为x的存储映象yx通常可用高级编程语言中

6、提供的数据类型描述之例如:当用三个带有次序关系的整数表示一个长整数时，可以借用C语言的整数类型来表示:typedefintLong_int[3]抽象数据类型是指一个数学模型以及定义在此数学模型上的一组操作例如：矩阵+（求转置、加、乘、求逆、求特征值）构成一个矩阵的抽象数据类型数据结构+定义在此数据结构上的一组操作=抽象数据类型抽象数据类型的描述方法抽象数据类型可用（D，S，P）三元组表示其中，D是数据对象，S是D上的关系集，P是对D的基本操作集。ADT抽象数据类型名{数据对象：〈数据对象的定义〉数据关系：〈数据关系的定义〉基本操作：〈基本操作的定义〉}ADT抽象数据类型名其中，数据对象和数据关

7、系的定义用伪码描述，基本操作的定义格式为基本操作名（参数表）初始条件：〈初始条件描述〉操作结果：〈操作结果描述〉基本操作有两种参数：赋值参数只为操作提供输入值；引用参数以&打头，除可提供输入值外，还将返回操作结果。“初始条件”描述了操作执行之前数据结构和参数应满足的条件，若不满足，则操作失败，并返回相应出错信息。“操作结果”说明了操作正常完成之后，数据结构的变化状况和应返回的结果。若初始条件为空，