数据结构chap1.

软件开发的过程:系统分析系统实现系统维护系统设计系统设计确定系统所要达到的目标确定实现方案并生成系统实地安装调试系统修整完善1.1什么是数据结构NiklausEmilWirth尼克莱斯·沃思-----瑞士计算机科学家《Algorithm+DataStructures=Programs》程序设计:算法:数据结构:为计算机处理问题编制一组指令集处理问题的策略问题的数学模型例如:鸡兔同笼问题二元一次代数方程组结构静力分析问题全球天气预报高次线性代数方程组球面坐标系下的环流模式方程更多的非数值计算问题，无法用数学方程加以描述例一求一组(n个)整数中的最大值例二交叉路口的交通管制问题例三煤气管道的铺设问题例四数据库中表格管理问题非数值计算的程序设计问题概括地说，数据结构是一门讨论“描述现实世界实体的数学模型(非数值计算)及其上的操作在计算机中如何表示和实现”的学科。计算机的程序是对信息进行加工处理。在大多数情况下，这些信息是有组织的，信息（数据）之间往往具有重要的结构关系，这就是数据结构的内容。那么，什么是数据结构呢？先看以下几个例子。什么是数据结构？设有一个电话号码薄，它记录了N个部门的名字和其相应的电话号码，假定按如下形式安排：(a1，b1)(a2，b2)…(an，bn)其中ai，bi(i=1，2…n)分别表示某部门的名字和对应的电话号码要求设计一个算法。当给定任何一个部门的名字时，该算法能够打印出对应的电话号码，如果该电话簿中根本就没有这个部门，则该算法也能够报告没有这个部门的标志。例1电话号码查询系统这个问题是一种典型的表格问题。例如表1，数据与数据成简单的一对一的线性关系。部门名称电话号码图书馆58290810财务处58290889……表1线性表结构例2磁盘目录文件磁盘根目录下有很多子目录及文件，每个子目录里又可以包含多个子目录及文件，但每个子目录只有一个父目录，依次类推。这是一种典型的树形结构问题如图2，数据与数据之间成一对多的非线性关系——树形结构。例3交通网络图从一个地方到另一个地方可以有很多条路径。这是一种典型的网状结构问题。如图3，数据与数据成多对多的非线性关系——图状结构。1.2与数据结构相关的概念1.2.1基本概念和术语数据(Data):是对信息的一种符号表示。在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号的总称。数据元素(DataElement):是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。对计算机科学而言，数据的含义很广，例如图像、声音等，都可以通过编码处理为数据。一个数据元素可由若干个数据项(DataItem)组成。数据项是数据的不可分割的最小单位。例如，整数5,字符N等。----是不可分割的“原子”称之为组合项年月日姓名学号班号性别出生日期入学成绩原子项又如,描述一个学生的数据元素由多个款项构成，其中每个款项为一个“数据项”。它是数据结构中讨论的最小单位。关键字能识别一个或几个数据元素的数据项。若能起唯一识别作用，则被称为“主”关键字，否则称为“次”关键字。数据对象(DataObject)：是性质相同的数据元素的集合，是数据的一个子集。如整数集合、实数集合等。例如，可用三个4位的十进制数表示一个含12位数的“长整数”。对长整数进行运算的程序中的操作对象是一个含三个数据元素{a1,a2,a3}的集合，且三者之间存在下列“次序”关系:{a1,a2、a2,a3}。3214,6587,9345─a1(3214),a2(6587),a3(9345)数据结构(DataStructure)：是相互之间存在一种或多种特定关系的数据元素的集合。又如，在2行3列的二维数组中六个元素{a1,a2,a3,a4,a5,a6}之间存在着两个关系:“行”的次序关系:row={a1,a2,a2,a3,a4,a5,a5,a6}col={a1,a4,a2,a5,a3,a6}“列”的次序关系:a6a5a4a3a2a1在含6个数据元素{a1,a2,a3,a4,a5,a6}的集合上存在如下的次序关系:{ai,ai+1|i=1,2,3,4,5}“数据结构”是相互之间存在着某种逻辑关系的数据元素的集合。可见，不同的“关系”构成不同的“结构”则构成“一维数组”。班主任班长1班长2舍长1舍长k舍长k+1舍长p学生1学生2学生3学生4学生n-3学生n-2学生n-1学生n…………可用如下的数据结构描述“班集体”:{班主任，班长1，班长2，舍长1，……，舍长p,学生1，学生2，……，学生n}{班主任，班长1，班主任，班长2，班长1，舍长1，……，班长2，舍长p,舍长1，学生1，舍长1，学生2，……，舍长p，学生n}1.2.2数据结构数据结构的形式定义描述为:数据结构是一个二元组Data_Structures=(D,S)其中:D是数据元素的有限集，S是D上关系的有限集。数据结构包括“逻辑结构”和“物理结构”两个方面:逻辑结构是对数据元素之间的逻辑关系的描述，它可以用一个数据元素的集合和定义在此集合上的若干关系来表示;线性结构：结构中的数据元素之间存在一对一的关系。树形结构：结构中的数据元素之间存在一对多的关系。图状结构或网状结构：结构中的数据元素之间存在多对多的关系。集合:结构中的数据元素除了”同属于一个集合”外，别无其它关系。数据的逻辑结构通常分为四类基本结构：存储结构是逻辑结构在存储器中的映象，包括“数据元素”的映象“关系”的映象用二进制位(bit)的位串表示数据元素(321)10=(501)8=(101000001)2A=(101)8=(001000001)2物理结构是逻辑结构在计算机中的表示和实现，故又称“存储结构”。元素之间的“关系”的两种映象方法：（表示x,y的方法）以x和y之间相对的存储位置表示后继关系例如:令y的存储位置和x的存储位置之间相差一个预设常量C，而C是一个隐含值，存储结构中只包含数据元素本身的信息xy顺序映象用数据元素在存储器中的相对位置来表示数据元素之间的逻辑关系。以附加信息(指针)表示后继关系需要用一个和x绑定在一起的附加信息(指针)指示y的存储位置yx以“由数据元素x的存储映象和附加的指针合成的结点”表示数据元素。链式映象在每一个数据元素中增加一个存放地址的指针（pointer），用此指针来表示数据元素之间的逻辑关系。存储结构的描述方法随编程环境的不同而不同，当用高级程序设计语言进行编程时，通常可用高级编程语言中提供的数据类型描述之。typedefintLong_int[3]例如，当以“顺序映象”表示长整数时，可定义为:定义“日期”为:typedefstruct{inty;//年号Yearintm;//月号Monthintd;//日号Day}DateType;//日期类型定义“学生”为:typedefstruct{charid[8];//学号charname[16];//姓名charsex;//性别‘M/F’:男/女DateTypebdate;//出生日期}Student;//学生类型数据的逻辑结构和物理结构是密不可分的两个方面。一个算法的设计取决于选定的逻辑结构，而算法的实现依赖于采用的存储结构。数据结构的三个组成部分：逻辑结构：数据元素之间逻辑关系的描述Data_Structures=(D,S)存储结构：数据元素在计算机中的存储及其逻辑关系的表现称为数据的存储结构或物理结构。数据操作：对数据进行的运算。我们将要讨论三种逻辑结构及其采用的存储结构何谓“数据类型”？在用高级程序语言编写的程序中，必须对程序中出现的每个变量、常量或表达式，明确说明它们所属的数据类型。例如，C++语言中的基本数据类型有:逻辑型bool、字符型char、整型int和实型(浮点型float和双精度型double)1.3数据类型和抽象数据类型数据类型（DataType）：是一个“值”的集合和定义在此集合上的“一组操作”的总称。对程序员而言，各种语言中的整数类型都是一样的，因为它们的数学特性相同。从这个意义上可称“整数”是一个抽象数据类型。抽象数据类型和数据类型的实质相同，范畴更广，不局限于语言中的数据类型。抽象数据类型(AbstractDataType简称ADT)是指一个数学模型以及定义在该模型上的一组操作。通常称语言中已经实现的数据类型为固有数据类型。抽象数据类型有两个重要特征:“数据抽象”和“数据封装”数据抽象用ADT描述程序处理的实体时，强调的是其本质的特征、其所能完成的功能以及它和外部用户的接口（即外界使用它的方法）。数据封装将实体的外部特性和其内部实现细节分离，并且对外部用户隐藏其内部实现细节抽象数据类型的形式化定义是三元组ADT=（D，S，P）其中:D是数据对象，S是D上的关系集，P是对D的基本操作集。数据对象是特性相同的数据元素的集合，是数据的一个子集。基本操作包括①建立（Create）一个数据结构②消除（Destroy）一个数据结构③从一个数据结构中删除（Delete）一个数据元素④把一个数据元素插入（Insert）到一个数据结构中⑤对一个数据结构进行访问（Access）⑥对一个数据结构（中的数据元素）进行修改（Modify）⑦对一个数据结构进行排序（Sort）⑧对一个数据结构进行查找（Search）ADT抽象数据类型名{数据对象：〈数据对象的定义〉数据关系：〈数据关系的定义〉基本操作：〈基本操作的定义〉}ADT抽象数据类型名其中基本操作的定义格式为:基本操作名(参数表)初始条件：〈初始条件描述〉操作结果：〈操作结果描述〉抽象数据类型的一般定义形式是:赋值参数只为操作提供输入值；引用参数以&打头，除可提供输入值外，还将返回操作结果。初始条件描述操作执行之前的数据结构和参数应满足的条件，若不满足，则操作失败，并返回相应出错信息。操作结果说明在操作正常完成之后，数据结构的变化状况和应返回的结果。初始条件可以为空，并可省略。例如,抽象数据类型“复数”的定义:R1＝{e1,e2|e1是复数的实数部分,|e2是复数的虚数部分}ADTComplex{数据对象：D＝{e1,e2｜e1,e2∈RealSet}数据关系：基本操作：AssignComplex(&Z,v1,v2)操作结果：构造复数Z,其实部和虚部分别被赋以参数v1和v2的值。DestroyComplex(&Z)操作结果：复数Z被销毁。GetReal(Z,&realPart)初始条件：复数Z已存在。操作结果：用realPart返回复数Z的实部值。GetImag(Z,&ImagPart)初始条件：复数已存在。操作结果：用ImagPart返回复数Z的虚部值。Add(z1,z2,&sum)初始条件：z1,z2是复数。操作结果：用sum返回两个复数z1,z2的和值。}ADTComplex……抽象数据类型的表示和实现抽象数据类型需要通过固有数据类型(高级编程语言中已实现的数据类型)来实现。例如，对之前定义的复数类型typedefstruct{floatrealpart；floatimagpart；}complex；//存储结构的定义//基本操作的函数原型说明voidAssign(complex&Z,floatrealval,floatimagval)；//构造复数Z,其实部和虚部分别被赋以参数realval//和imagval的值floatGetReal(cpmplexZ)；//返回复数Z的实部值floatGetimag(cpmplexZ)；//返回复数Z的虚部值voidadd(complexz1,complexz2,complex&sum)；//以sum返回两个复数z1,z2的和……//基本操作的实现voidadd(complexz1,complexz2,complex&sum)//以sum返回两个复数z1,z2的和{sum.realpart=z1.realpart+z2.realpart;sum.imagpart=z1.imagpart+z2.imagpart;}一个