【精品数据结构】数据结构绪论

《【精品数据结构】数据结构绪论》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第一章绪论1.1数据结构讨论的范畴1.2基本概念1.3算法和算法的量度1.1数据结构讨论的范畴(数据结构在软件开发中的地位)系统分析系统设计系统实现系统维护系统设计NiklausWirthAlgorithm+DataStructures=Programs程序设计:算法:数据结构:为计算机处理问题编制一组指令集处理问题的策略问题的数学模型结构静力分析计算例如:数值计算的程序设计问题─━线性代数方程组─━环流模式方程(球面坐标系)全球天气预报非数值计算的程序设计问题例一:求一组(n个)整数中的最大值算法:?模型：？基本操作是“比较两个数的大小”取决于整数值的范围例

2、二：旅馆客房的管理算法：?模型：?先进后出队列例三：铺设城市的煤气管道算法：?模型：?如何规划使得总投资花费最少？图概括地说，数据结构是一门讨论“描述现实世界实体的数学模型(非数值计算)及其上的操作在计算机中如何表示和实现”的学科。1.2基本概念一、数据与数据结构二、数据类型三、抽象数据类型一、数据与数据结构所有能被输入到计算机中，且能被计算机处理的符号(数值、字符等)的集合。数据:是计算机操作的对象的总称。是计算机处理的信息的某种特定的符号表示形式。是数据（集合）中的一个“个体”,在计算机中通常作为一个整体进行考虑和处理。是数据结构中讨论的基本单位。数据元素

3、:如:整数“5”,字符“N”等。----是不可分割的“原子”其中每个款项称为一个“数据项”它是数据结构中讨论的最小单位数据元素也可以由若干款项构成。例如：描述一个学生的数据元素称之为组合项年月日姓名学号班号性别出生日期入学成绩原子项数据结构：带结构的数据元素的集合有一个特性相同的数据元素的集合，如果在数据元素之间存在一种或多种特定的关系，则称为一个数据结构。指的是数据元素之间存在的关系例如，当用三个4位的十进制数表示一个含12位数的十进制数时，3214,6587,9345─a1(3214),a2(6587),a3(9345)则在数据元素a1、a2和a3之间存在

4、着“次序”关系a1,a2、a2,a33214，6587，93456587，3214，9345例如:a1a2a3a2a1a3又例，在2行3列的二维数组中六个元素{a1,a2,a3,a4,a5,a6}之间存在两个关系:行的次序关系:row={,,,}col={,,}a1a2a3a4a5a6列的次序关系:若在6个数据元素{a1,a2,a3,a4,a5,a6}之间存在如下的次序关系:{

5、i=1,2,3,4,5}数据结构是相互之间存在着某种逻辑关系

6、的数据元素的集合。可见，不同的“关系”构成不同的“结构”则构成一维数组的定义。从关系或结构分，数据结构可归结为以下四类:线性结构树形结构图状结构集合结构数据结构包括“逻辑结构”和“物理结构”两个方面(层次):逻辑结构是对数据元素之间的逻辑关系的描述，它可以应一个数据元素的集合和定义在此集合上的若干关系来表示;物理结构是逻辑结构在计算机中的表示和实现，故又称“存储结构”。数据结构的形式定义描述为:数据结构是一个二元组Data_Structures=(D,S)其中:D是数据元素的有限集，S是D上关系的有限集。例如:定义“班集体”为一个数据结构Class=(D,S)

7、D={a,b1,…,bn,c1,…cn,d1,…dn}S={R1,R2}R1={,,}R2={,,

8、j=2,3,…,n}数据的存储结构——逻辑结构在存储器中的映象“数据元素”的映象？“关系”的映象？数据元素的映象方法：用二进制位(bit)的位串表示数据元素(321)10=(501)8=(101000001)2A=(101)8=(001000001)2关系的映象方法：（表示x,y的方法）顺序映象以相对的存储位置表示后继关系例如:令y的存储位置和x的存储位置之间差一个常量C而C是一个

9、隐含值，整个存储结构中只含数据元素本身的信息xy链式映象以附加信息(指针)表示后继关系需要用一个和x在一起的附加信息指示y的存储位置yx在不同的编程环境中，存储结构可有不同的描述方法，当用高级程序设计语言进行编程时，通常可用高级编程语言中提供的数据类型描述之。例如:以三个带有次序关系的整数表示一个长整数时，可利用C语言中提供的整数数组类型，typedefintLong_int[3]定义长整数为:typedefstruct{inty;//年号Yearintm;//月号Monthintd;//日号Day}DateType;//日期类型定义“日期”为:定义“学生”为

10、:typedefstruct{char