数据结构 李云清 杨庆红 揭安全 第01章_概论

李云清杨庆红揭安全高等学校精品课程人民邮电出版社（第2版）[e-mail]（第2版）2首页上一页下一页返回退出什么是数据结构数据类型和抽象数据类型算法和算法分析第一章概述3首页上一页下一页返回退出瑞士著名的计算机科学家NicklausWirth在1976年出版了一本书，书名为《算法+数据结构=程序设计》，它正说明了数据结构在程序设计中的作用。程序设计的实质即为计算机处理问题编制一组指令，首先需要解决两个问题：即算法和数据结构。算法即处理问题的策略，而数据结构即为问题的数学模型。很多数值计算问题的数学模型通常可用一组线性或非线性的代数方程组或微分方程组来描述，而大量非数值计算问题的数学模型正是本门课程要讨论的数据结构。第一章概述4首页上一页下一页返回退出例一、求n个整数中的最大值。这似乎不成问题，但如果这些整数的值有可能达到1012，那么对32位的计算机来说，就存在一个如何表示的问题。例二、交叉路口的红绿灯管理。如今十字路口横竖两个方向都有三个红绿灯，分别控制左拐、直行和右拐，那么如何控制这些红绿灯既使交通不堵塞，又使流量最大呢？若要编制程序解决问题，首先要解决一个如何表示的问题。例三、煤气管道的铺设问题。如图需为城市的各小区之间铺设煤气管道，对n个小区只需铺设n-1条管线，由于地理环境不同等因素使各条管线所需投资不同(如图上所标识)，如何使投资成本最低？这是一个讨论图的生成树的问题。5首页上一页下一页返回退出ABHIGCEDF1812979525631108598672145834（a）城市距离图ABHIGCEDF12979311021834（b）联通各城市最小生成树6首页上一页下一页返回退出以上所举例子中的数学模型正是数据结构要讨论的问题。因此，简单地说，数据结构是一门讨论描述现实世界实体的数学模型(非数值计算)及其上的操作在计算机中如何表示和实现的学科。7首页上一页下一页返回退出而信息的表示和组织又直接关系到处理信息的程序的效率。随着计算机的普及，信息量的增加，信息范围的拓宽，使许多系统程序和应用程序的规模很大，结构又相当复杂。因此，为了编写出一个“好”的程序，必须分析待处理的对象的特征及各对象之间存在的关系，这就是数据结构这门课所要研究的问题。计算机是一门研究用计算机进行信息表示和处理的科学。这里面涉及到两个问题：信息的表示信息的处理综上所述8首页上一页下一页返回退出1.1数据结构1.1.1数据结构随着计算机软、硬件的发展，计算机的应用范围在不断扩大，计算机所处理的数据的数量也在不断扩大，计算机所处理的数据已不再是单纯的数值数据，而更多的是非数值数据。需要处理的数据并不是杂乱无章的，它们一定有内在的联系，只有弄清楚它们之间的本质的联系，才能使用计算机对大量的数据进行有效的处理。9首页上一页下一页返回退出例4某电信公司的市话用户信息表格如下图所示：序号用户名电话号码用户住址街道名门牌号00001万方林3800235北京西路165900002吴金平3800667北京西路209900003王冬5700123瑶湖大道198700004王三5700567瑶湖大道200800005江凡8800129学府大道503510首页上一页下一页返回退出这里序号、用户名、电话号码等项称为基本项，它是有独立意义的最小标识单位，而用户住址称为组合项，组合项是由一个或多个基本项或组合项组成，是有独立意义的标识单位，每一行称为一个结点，每一个组合项称为一个字段。使用计算机处理用户信息表中的数据时，必须弄清楚下面3个问题：11首页上一页下一页返回退出1数据的逻辑结构这些数据之间有什么样的内在联系？除最前和最后两个结点之外，表中所有其它的结点都有且仅有一个和它相邻位于它之前的一个结点，也有且仅有一个和它相邻位于它之后的一个结点，这些就是用户信息表的逻辑结构。2数据的存储结构将用户信息表中的所有结点存入计算机时，就必须考虑存储结构，使用C语言进行设计时，常见的方式是用一个结构数组来存储整个用户信息表，每一个数组元素是一个结构，它对应于用户信息表中的一个结点。数据在计算机的存储方式称为存储结构。12首页上一页下一页返回退出3数据的运算集合数据处理必涉及到相关的运算，在上述用户信息表中，可以有删除一个用户、增加一个用户和查找某个用户等操作。应该明确指明这些操作的含义。比如删除操作，是删除序号为5的用户还是删除用户名为王三的用户是应该明确定义的，如果需要可以定义两个不同的删除操作，为一批数据定义的所有运算（或称操作）构成一个运算（操作）集合。对待处理的数据，只有分析清楚上面3个方面的问题，才能进行有效的处理！数据结构就是指按一定的逻辑结构组成的一批数据，使用某种存储结构将这批数据存储于计算机中，并在这些数据上定义了一个运算集合。基于这个二维表格，我们可以在上面执行的操作有：增加一个元素，删除元素，查找元素等。存在的问题：线性查找的效率较低（等概率情况下为n/2）。数组存储时插入一个元素与删除一个元素效率较低。解决办法：改变数据存储结构，在新的存储结构上开发新的算法。找95找35例5、旅游交通网络图实际问题：如何选择任意两个城市之间的最短路径？建立通信网络时，如何在n个城市之间找到n-1连线，使得这n-1条连线的和最小。（即花费最小的代价连通各个城市）解决办法：将城市与城市之间的距离等数据在计算机中采用图型结构组织（点与点之间存在多对多的关系）。上述问题便可转化为图中两点之间的最短距离和图的最小生成树问题。15首页上一页下一页返回退出1.1.2数据的逻辑结构数据的逻辑结构是数据和数据之间所存在的逻辑关系，它可以用一个二元组B=（K，R）来表示，其中K是数据、即结点的有限集合；R是集合K上关系的有限集合，这里的关系是从集合K到集合K的关系，这里一般只涉及到一个关系的逻辑结构。16首页上一页下一页返回退出1.1.2数据的逻辑结构例如，有5个人，分别记为a,b,c,d,e,其中a是b的父亲，b是c的父亲，c是d的父亲,d是e的父亲，如果只讨论他们之间所存在的父子关系，则可以用下面的二元组形式化地予以表达。B=（K，R）其中：K={a,b,c,d,e}R={r}r={a,b,b,c,c,d,d,e}逻辑结构的图形表示方式，对K中的每个结点ki用一个方框表示，而结点之间的关系用带箭头的线段表示，这5人之间的逻辑结构用图形的方式表达如下图所示。若ki∈K，kj∈R，ki,kj∈r，则称ki是kj的相对于关系r的前驱结点，kj是ki的相对于关系r的后继结点，因为一般只讨论具有一种关系的逻辑结构，即R={r}，所以简称ki是kj前驱，kj是ki的后继。如果某个结点没有前驱结点，称之为开始结点；如果某个结点没有后继结点，称之为终端结点；既不是开始结点也不是终端结点的结点称为内部结点。abcde线性逻辑结构二、树型结构结构中的数据元素之间存在一对多的关系。125643三、图状结构或网状结构结构中的数据元素之间存在多对多的关系。12345671.1.3数据的存储结构数据的逻辑结构是独立于计算机的，它与数据在计算机中的存储无关，要对数据进行处理，就必须将数据存储在计算机中。如果将数据在计算机中无规律地存储，那么在处理时是非常糟的，是没有用的。试想一下，如果一本英汉字典中的单词是随意编排的，这本字典谁会用！对于一个数据结构B=（K，R），必须建立从结点集合到计算机某个存储区域M的一个映象，这个映象要直接或间接地表达结点之间的关系R。数据在计算机中的存储方式称为数据的存储结构。数据的存储结构主要有4种。数据的存储结构主要有4种。1顺序存储顺序存储通常用于存储具有线性结构的数据。将逻辑上相邻的结点存储在连续存储区域M的相邻的存储单元中，使得逻辑相邻的结点一定是物理位置相邻。对于一个数据结构B=（K，R）其中K={k1,k2,k3,k4,k5,k6,k7,k8,k9}R={r}r={k1,k2,k2,k3,k3,k4,k4,k5,k5,k6,k6,k7,k7,k8,k8,k9}它的顺序存储方式如图所示k1k2k3k6k5k4k7k8k9存储地址M100110021003100410051006100710081009特点：用物理相邻的位置关系表示其逻辑关系2链式存储链式存储方式是给每个结点附加一个指针段，一个结点的指针所指的是该结点的后继的存储地址，因为一个结点可能有多个后继，所以指针段可以是一个指针，也可以是一个多个指针。例，数据的逻辑结构B=（K，R）其中K={k1,k2,k3,k4,k5}R={r}r={k1,k2,k2,k3,k3,k4,k4,k5}这是一个线性结构，它的链式存储如图所示。100010011002100310041005100610071008存储地址infonextk41006k21007k11003k5∧k31005特点:逻辑上相邻物理上不一定相邻。3索引存储在线性结构中，设开始结点的索引号为1，其它结点的索引号等于其前继结点的索引号加1，则每一个结点都有唯一的索引号，索引号就是根据结点的索引号确定该结点的存储地址。4散列存储散列存储的思想是构造一个从集合K到存储区域M的一个函数h，该函数的定义域为K，值域为M，K中的每个结点ki在计算机中的存储地址由h(ki)确定。1.1.4数据的运算集合对于一批数据，数据的运算是定义在数据的逻辑结构之上的，而运算的具体实现就依赖于数据的存储结构。数据的运算集合要视情况而定，一般而言，数据的运算包括插入、删除、检索、输出、排序等。插入：在一个结构中增加一个新的结点。删除：在一个结构删除一个结点。检索：在一个结构中查找满足条件的结点。输出：将一个结构中所有结点的值打印、输出。排序：将一个结构中所有结点按某种顺序重新排列。在程序设计中，数据和运算是两个不可缺少的因素。所有的程序设计活动都是围绕着数据和其上的相关运算而进行的。从机器指令、汇编语言中的数据没有类型的概念，到现在的面向对象程序设计语言中抽象数据类型概念的出现，程序设计中的数据经历了一次次抽象，数据的抽象经历了三个发展阶段。1.2数据类型和抽象数据类型从无类型的二进制数到基本数据类型的产生从基本数据类型到用户自定义类型的产生从用户自定义类型到抽象数据类型的出现1.2.1数据类型数据类型（或简称类型）反映了数据的取值范围以及对这类数据可以施加的运算。1.2.2数据结构数据结构是计算机科学中广泛使用的一个术语，在计算机科学中具有非常重要的作用。数据结构包括三个方面的内容：一组数据中各数据之间的逻辑关系；这组数据在计算机中的存储方式；对这组数据所能施加的运算的集合。数据结构是数据存在的形式。所有的数据都是按照数据结构进行分类的。简单数据类型对应于简单的数据结构；构造数据类型对应于复杂的数据结构。1.2.3抽象数据类型抽象数据类型是与表示无关的数据类型，是一个数据模型及定义在该模型上的一组运算。对一个抽象数据类型进行定义时，必须给出它的名字及各运算的运算符名，即函数名，并且规定这些函数的参数性质。1.2.4抽象数据类型的描述和实现抽象数据类型的描述包括给出抽象数据类型的名称、数据的集合、数据之间的关系和操作的集合等方面的描述。抽象数据类型的设计者根据这些描述给出操作的具体实现，抽象数据类型的使用者依据这些描述使用抽象数据类型。抽象数据类型描述的一般形式如下：ADT抽象数据类型名称{数据对象：……数据关系：……操作集合：操作名1：…………操作名n：}ADT抽象数据类型名称1.3算法和算法分析1.3.1算法为了求解某问题，必须给出一系列的运算规则，这一系列的运算规则是有限的，表达了求解问题方法和步骤，这就是一个算法。一个算法可以用自然语言描述，也可以用高级程序设计语言描述，也可以用伪代码描述。本书采用C语言对算法进行描述。算法具有五个基本特征：①有穷性，算法的执行必须在有限步内结束。②确定性，算法的每一步骤必须是确定无二义性的。③输入，算法可以有0个