计算机导论PPT第九章_数据结构_数据类型(1)

第九章数据结构概述数据类型复合数据类型（数组和记录）典型数据结构（栈、队列、树、图的表示）抽象数据类型（栈、队列、树、图的基本操作）主要内容1概述NiklausWirth：Algorithm+DataStructures=Programs程序设计:算法:数据结构:为计算机处理问题编制一组指令集处理问题的策略问题的数学模型例一:求一组(n个)整数中的最大值算法:?模型:？基本操作是“比较两个数的大小”取决于整数值的范围例二：计算机和人对弈问题算法：?模型：?对弈的规则和策略棋盘及棋盘的格局2数据类型数学中，运算都是抽象的，数值的运算是绝对准确的1/3的值是0.33333333…（循环小数）计算机中，数据是存在存储单元中的，是具体存在的对存储单元的引用方式地址变量每个变量都有一个它所属的确定的数据类型类型就是对数据分配存储单元的安排，包括存储单元的长度以及数据的存储形式。类型明显或隐含地规定了在程序执行期间变量或表达式所有可能取值的范围，以及在这些值上允许进行的操作数据类型是一个值的集合和定义在这个值集上的一组操作的总称.i不同的数据类型在内存中占用的存储单元长度不同TuborC2.0中为char型数据分配1个字节，而为int型数据分配2个字节可分为三类基本数据类型：int,char,float复合数据类型：数组，记录抽象数据类型：复数，栈2.1基本整型占用的存储单元长度与编译系统相关TuborC2.0分配2个字节VisualC++6.0分配4个字节在存储单元中以整数的补码形式存放如分配两个字节，则存储单元中能存放的最大值为0111111111111111，第一位为0代表整数，此数值为215-1，十进制数32767分配四个字节的情况2.2字符型大多数系统采用ASCII字符集(AmericanStandardCodeforInformationInterchange)字母：A~Z，a~z数字：0-9专门符号：29个：!”#&‘()*等空格符：空格、水平制表符、换行等字符是按其代码(整数)形式存储的，C99把字符型数据作为整数类型的一种，字母’a’的ASCII代码，十进制97，二进制1100001数字字符’1’ASCII代码，十进制49，二进制0110001在TuborC2.0占用一个字节的存储单元小写字母’a’在内存中的存储情况：01100001字符’1’和整数1是不同的概念：字符’1’只是代表一个形状为’1’的符号，在需要时按原样输出，在内存中以ASCII码形式存储，占1个字节00110001整数1是以整数存储方式(二进制补码方式)存储的，占2个字节00000000000000012.3浮点型浮点型数据是用来表示具有小数点的实数实数是以指数形式存放在存储单元中的一个实数表示指数可以有多种表示形式，但只有一个规范化的指数形式以规范化的二进制形式存放在存储单元中将实型数据分成小数部分和指数部分分别存放，小数部分的小数点前面的数位0。如3.14159在内存中的存放形式如下:+.3141591数符小数部分指数+.3141591013.14159根据能够表示的实数的精度，可分为单精度浮点型:4字节，6为有效数字双精度浮点型:8字节，15为有效数字长双精度型:受编译系统影响TuborC:8字节，15位有效数字VisualC++6.0:16字节，19位有效数字复杂数据类型是可分解为多个数据类型的数据类型，是由若干个成分按照某种结构组成，其成分可是基本类型，也可以是复杂类型，如数组、记录等3复合数据类型假设有100个分数。我们需要将其读入，处理后进行打印。同时还要求这100个数在处理过程中保留在内存里。对于这种情况，我们可以定义100个具有不同名字的变量图3.1100个独立变量3.1数组但定义100个不同名字的变量带来了其它问题，我们需要100个引用来读取它们，100个引用来处理它们，和100引用写它们图3.2独立变量的处理数组是元素的顺序集合。虽然一些编成语言允许数组含有不同类型的数据元素，但大部分都要求这些元素具有相同的数据类型。我们可以称数组中的元素为第一个元素、第二个元素等等，直到最后一个元素。图3.3带索引的数组可以使用循环来读些数组中的元素并对其进行处理。无论处理的是100个、1000个还是10000个元素，通过循环可以很方便对它们进行处理。通过一个整数变量控制循环，只要变量的值小于数组中元素的个数，那就还在循环体里面。图3.4数组的处理这里数组索引是从1开始的，有些语言中数组的索引是从0开始的，如C，Java等i示例3.1比较处理图3.2和图3.4中对100个独立元素进行处理所需要的指令条数。解第一种情况，需要100条指令去读，100条指令去写，100条指令去处理，共300条指令第二种情况，有三个循环，每个循环中有两条指令，共6条指令。但我们还需要3条指令来初始化索引，3条指令来检索索引的值，所以总共有12条指令示例3.2当我们使用数组时，计算机需要执行的的周期次数（取码、译码和执行阶段）并没有减少，相反需要的周期次数还会增加。这主要是是因为有额外的初始化、增加和测试索引值等负担。但多数情况下我们关注的并不是周期的次数，而是我们需要写的程序的行数。示例3.3在计算机科学中，一个很大的问题就是程序的重用性。例如，如果数据项的数目改变了，程序中有多少地方需要修改。假定我们写两个程序分别处理图3.2和图3.4中的分数，如果分数的数目从100变成1000，我们需要在每个程序中做多少修改？在第一个程序中，需要增加条3×900=2700指令，在第二个程序中我们只需要修改三个条件(I100toI1000)。实际上只需要修改以条指令。数组名与元素名在数组中存在两种标识符：数组名和各元素名。数组名是整个结构的名字，而元素名是对相应元素的一个引用。在图3.3所示的数组中，数组名为scores，而每个元素的名字是这个名字后边加上索引，如scores[1],scores[2]等。本部分我们多数时候需要的是元素的名字，有时我们也需要使用数组的名字。多维数组目前为止我们讨论的都是一维数组，数据是沿着一个方向线性组织在一起的。很多应用要求处理的数据是多维的。常见的例子如表格就是包含行和列的数组，图3.5给出的表格就是一个二维数组。图3.5二维数组存储配置一维数组直接定义了元素在内存中的相对位置。图3.6给出了二维数组以及它是如何以行主序存储和列主序存储的。行主序的方式更为常见。图3.6数组的存储配置示例3.4在内存中有一个100×4(100行4列)的二维数组students。假设元素students[1][1]所在的存储地址为1000，每个元素只占一个存储位置并采用行主序存储方式，求元素students[5][3]的存储地址解当每个元素只占一个存储位地址时，我们可以采用下面公式找到元素的地址如果第一个元素占据的地址是1000，那么目标元素占据的地址为1018记录是一组相关元素的集合，它们的类型可以不同，但整个记录有一个单独的名称。记录中的每个元素称为域(field)。域是具有含义的最小命名数据单元。它有类型且存在内存中，能被赋值，也能被选择和操纵。域与变量不同之处在于它是记录的一部分。3.2记录图3.7给出了两个记录的实例。第一个例子中，fraction含有两个整数域。第二个例子中，student包含三个不同类型的域。图3.7记录记录名versus域名与数组一样，记录中也有两种标识符：记录名和记录中各个域的名字。记录的名是整个结构的名字，每个域的名字是域的引用。例如，在图3.7的记录中，记录的名字是student，域名分别为student.id,student.name和student.grade。多数编程语言使用period(.)来分隔结构名和它的成员的名字。示例3.5下面显示的是图3.7中的域值是如何被存储的。数组和记录的比较我们可以从概念上对数组和记录进行比较。这有助于我们理解什么时候使用数组，什么时候使用记录。数组定义了元素的集合，而记录定义了一个元素可确认的部分。例如，数组可以定义一个班级的学生，而记录定义了学生不同的属性，如，标识、姓名或成绩等记录数组如果我们需要定义元素的集合，且同时还需要定义元素的属性，那么就可以使用记录数组。例如，有一个30个学生的班级中，我们可以有一个30个记录的数组，每个记录表示一位学生。图3.8记录数组示例3.6下面显示了如何访问学生数组中每个记录的域，并对相应的域进赋值。示例3.7但通常我们都是采用循环来读取记录数组中的数据。算法3.1给出了这个过程的部分代码。算法3.1读学生记录的部分代码数组与记录数组数组和记录数组代表的都是数据项的列表。数组可看成是记录数组的一种特例，每个元素只含有一个记录。模型：树形结构例一：计算机和人对弈4典型数据结构CDBAE图一个交叉路口的模型为了设计一个交通信号灯的管理系统，首先需要分析一下所有车辆的行驶路线的冲突问题。这个问题可以归结为对车辆的可能行驶方向作某种分组，对分组的要求是使任一个组中各个方向行驶的车辆可以同时安全行驶而不发生碰撞。例二：多叉路口交通灯管理问题根据这个路口的实际情况可以确定13个可能通行方向：A→B，A→C，A→D，B→A，B→C，B→D，D→A，D→B，D→C，E→A，E→B，E→C，E→D。可以把A→B简写成AB，用一个结点表示，在不能同时行驶ABACADBABCBDDADBDCEAEBECED图交叉路口的图式模型问题分析:的结点间画一条连线(表示它们互相冲突)，便可以得到如右图所示的表示。这样得到的表示可以称之为“图”。栈是一种限制线性表，该表的添加和删除操作只能在一端实现，称为栈顶。如果将一系列数据插入到栈中，然后在移出它们，那么数据的顺序将被倒转。这种倒转的属性也正是栈被称为后进先出(LIFO)数据结构的原因。图4.1栈的三个示例4.1栈4-2队列Aqueueisalinearlistinwhichdatacanonlybeinsertedatoneend,calledtherear,anddeletedfromtheotherend,calledthefront.Theserestrictionsensurethatthedataisprocessedthroughthequeueintheorderinwhichitisreceived.Inotherwords,aqueueisafirstin,firstout(FIFO)structure.图4.6队列示意图数是由一组有限的分别称为节点(顶点)和有向弧的元素组成，每条弧用来连接两个顶点。图4.11树的示意图4.3树树中的节点可以分为三类：根节点、叶节点和内部节点。表4.1给出了每类节点允许的入弧和出弧的数量。表-4.1入弧和出弧树中每个节点都有子树。每个节点的子树含有它的一个孩子和这个孩子的所有后代。图4.7给出了图4.6中树的所有子树。图4.12子树图是由一组节点(顶点)和一组节点间的连线(边/弧)构成的。树是定义成层次结构的，每个节点只能有一个父节点，而图中每个节点可以有多个父节点。图可以是有向的，也可以是无向的，如图4.8所示4.4图图4.13图示例4.2城市的地图和连接城市的道路可以表示成计算机中的无向图。顶点表示城市，边表示连接它们之间的道路。如果我们要显示出城市之间的距离，可以使用加权图。在加权图中每条边都有一个用来表示城市之间距离的权重。示例4.3图的另一个应用是在计算机网络中。顶点可以代表节点或集线器，边代表路由。每条边可以有一个权重，用来定义从一个集线器到相邻集线器的代价。路由器可以使用图算法找到一个包由它到目的节点经历的最短路径。5抽象数据类型使用计算机解决问题就意味着需要处理数据。为了处理数据，我们需要定义数据对象和在这些数据对象上进行的操作。数据对象的定义和应用于数据对象上操作的定义是隐藏在抽象数据类型(ADT)当中的-为了隐藏数据是如何被操作的。换句