数据结构基础概念.docVIP

数据结构基础概念摘要：进一步,对于不同的处理对象,要想设计出高质量的程序,就必须研究,如何组织数据和处理数据,根据问题的要求及数据元素之间的特性,确定相应的存储结构和算法,这些都是.关键词：数据,结构,算法类别：专题技术来源：牛档搜索（Niudown.COM）本文系牛档搜索（Niudown.COM）根据用户的指令自动搜索的结果，文中内涉及到的资料均来自互联网，用于学习交流经验，作品其著作权归原作者所有。不代表牛档搜索（Niudown.COM）赞成本文的内容或立场，牛档搜索（Niudown.COM）不对其付相应的法律责任！第五章 数据结构基础概念本章我们将介绍有关数据结构的基础知识，要求大家熟悉数据结构中常用的名词、术语，掌握基本概念，分清逻辑结构和存储结构的性质；了解线性表的逻辑结构特性及其在计算机中的表示。掌握线性表的顺序存储结构及其插入和删除操作的基本思想；掌握栈和队列的特点，能根据实际问题正确地选用它们，掌握栈满、栈空、队满、队空的判别方法；熟悉树型结构的描述方法，了解图的术语和概念。51 数据结构基本概念1数据结构是怎样产生的？我们知道计算机已经不仅仅是用于科学计算了，早期的计算机确实主要用于数值处理，用于科学计算，随着计算机技术的飞速发展，计算机的应用范围不断扩大，已不再局限于单纯的数值计算，更多地应用于控制、管理及数据处理等非数值计算的处理工作。非数值型的问题在我们日常生活中是非常多的，也需要我们使用计算机来处理这些非数值问题。例如：在城市交通运输中，从A点到B点有很多条道路，每条道路的长度不同，拥挤程度不同，我们要选择一条最快的线路到达目的地，该如何选择？再比如：图书馆有成千上万的图书资料，我们该如何进行管理才能使我们可以快速查找到需要的资料。北京市有上千万的人口，我们应该怎样保存这些人口的资料信息，才能使我们可以快速查找到所需要查找的人。象这样的问题都是典型的非数值问题。要用计算机处理这些非数值问题，就为我们提出了一个课题：如何在计算机内部描述这些非数值问题，采用什么样的算法可以快速、有效地完成问题的求解。随着计算机技术的发展，于是就产生了数据结构。进一步，对于不同的处理对象，要想设计出高质量的程序，就必须研究，如何组织数据和处理数据，根据问题的要求及数据元素之间的特性，确定相应的存储结构和算法，这些都是数据结构研究的内容。我们可以通过下面的例子来认识数据结构。电话是我们通讯联络必不可少的工具。如何用计算机来实现自动查询电话号码呢？要求对于给定的任意姓名，如果该人有电话号码，则迅速给出电话号码，否则，给出查找不到该人电话号码的信息。对于这样的问题，我们可以按照客户向电信局申请电话号码的先后次序建立电话号码表，存储到计算机中。在这种情况下，由于电话号码表是没有任何规律的，查找时只能从第一个号码开始逐一进行，这样的逐一按顺序进行查找效率非常低。为了提高查询的效率，我们可以根据每个用户姓名的第一个拼音字母，按照26个英文字母的顺序进行排列，这样根据姓名的第一个字母就可以迅速地进行查找，从而极大地减少了查找所需的时间。进一步，我们可以按照用户的中文姓名的汉语拼音顺序进行排序，这样就可以进一步提高查询效率了。在上述例子中，我们感兴趣的是如何提高查找效率。为了解决这个问题，就必须了解待处理对象之间的关系，以及如何存储和表示这些数据。在电话号码查询的例子中，每一个电话号码就是一个要处理的数据对象，我们也称为数据元素，在数据结构中为了抽象地表示不同的数据元素，为了研究对于具有相同性质的数据元素的共同特点和操作，我们将数据元素又称为数据结点，简称为结点。电话号码经过处理，按照拼音排好了顺序，每个电话号码之间的先后次序就是数据元素之间的关系。数据结构就是研究这类非数值处理的程序设计问题。2数据结构研究什么内容？数据结构一般包含三个方面的内容：数据的逻辑结构、数据的存储结构和数据的运算。 数据的逻辑结构是指数据元素之间的逻辑关系，与数据的在计算机内部是如何存储无关，数据的逻辑结构独立于计算机。例如在城市交通中，两个地点之间就存在一种逻辑关系，两个地点之间的逻辑关系分为三种：第一种是：两个地点之间有公共汽车可以直达；第二种是：两个地点之间没有公共汽车可以直达，但可以通过中途换乘其他公共汽车而到达；第三种逻辑关系就是：两个地点之间没有公共汽车可以达到。又如在电话号码本中，电话号码如何进行分类，按照什么顺序进行排列等都是数据之间的逻辑关系。 数据的存储结构是指数据元素在计算机存储设备中的存储方式，可以用顺序存储方式，也可以用链式存储方式。例如在城市交通的例子中，我们就要研究如何在计算机中表示1个地点，任何在计算机中表示两个地点之间存在一条公共汽车线路，该线路有多长等。又如对于电话号码资料信息在计算机中如何保存，如何表示资料的分类，如何表示排好顺序的电话号码之间的先后次序关系。 数据的运算主要包括：插入、删除、检索和排序等与问题相关的处理。例如在城市交通问题中，我们就要设计求两点之间最短线路的算法，要能够判断从城市的任一点出发乘坐公共汽车是否可以达到城市的任何地方。在电话号码问题中，我们就要设计如何插入一个新的电话号码信息，如何删除一个作废的电话号码信息，如何对电话号码进行快速整理排序，如何高效快速查找资料等算法。为了进一步研究数据的逻辑结构，我们可以将数据的逻辑结构分为线性结构和非线性结构两大类。线性结构包括：线性表、栈和队列等。其主要特征为各个数据之间有明确的、唯一的“先后”顺序。在现实生活中具有线性结构的实例非常多，例如我们在日常生活中的排队购物，队列中的每个人都有一个明确先后次序关系。 非线性结构包括树和图型结构。树型结构的主要特征是结点之间存在着一种层次的关系，每一个结点对应着下一层的多个结点，也就是说，数据元素之间的关系是“一对多”的关系。例如：我们一所学校下面有好几个系，每个系下面有好多班，每个班下面有好多学生。我们说：学校系班学生，每一层之间都是一个一对多的关系，这就是一个典型的树型结构。而在图型结构中，任何两个结点之间都可能存在着联系，数据元素之间存在着多对多的关系。典型的图型结构就是城市交通。如果城市中有单行线路，则从城市中的一个地点A出发，可以到达N个不同的地方，从城市的M个不同的地方出发又可以到达地点A。城市交通就是一个典型的“多对多”的图型结构。数据结构通常具有下列一些基本操作：1插入：在数据结构的指定位置上添加一个新结点。2删除：删去数据结构中指定位置的结点。3更新：修改数据结构中某个结点的值。4查找：在数据结构中寻找满足指定条件的结点及其位置。5排序：按照指定的顺序，使结点重新排列。52 线性结构的基本概念 线性结构是最常用且最简单的数据结构，它包括线性表、栈和队列等。 521 线性表日常生活中大量存在着这样的表格，例如一份学生名单表，一张仓库设备清单等，我们把一个人、一台设备都抽象地看成是一个数据元素，这些数据元素之间除了在表中的排列次序即先后次序不同外，没有其它的联系，这一类的表属于线性表。这里我们使用“结点”的概念来描述线性表。结点就是对数据的一种抽象。例如在学生名单中，我们可以认为一个学生数据就是一个结点，如果一长学生名单有1000人组成，我们就可以抽象地认为，学生名单这样的线性表就是由1000个结点组成的。再比如，在一张仓库设备清单中有800台设备，我们就可以抽象地认为，仓库设备清单就是一张线性表，表中有800个结点。在这样的抽象的意义上，我们就不再关心，我们是处理学生数据还是处理设备数据，我们可以认为我们处理的数据就是“结点”。这样可以使得我们数据结构研究的算法具有通用性和一般性。那么，从数据结构的角度出发，线性表是n（n0）个数据元素组成的有限序列，记为：（a1，a2an）当n=0时，线性表为空表。在线性表中，除了第一个和最后一个数据元素外，每一个数据元素都有一个直接前趋结点和一个直接后继结点。所谓直接前驱结点就是排列在它的前一个的那一个结点，直接后继结点就是排列在它后面的下一个结点。线性表中的数据元素在不同的场合代表不同的含义，例如，在学生名单表及仓库设备清单表中不难看出，同一线性表具有相同的数据类型，学生和设备分别是两个表中的数据元素，各自代表不同的含义。以管理仓库设备清单为例：工厂有时会根据需要，从仓库调出一台设备，或者新购进一批设备以备工程使用，对设备清单表而言，就是要进行删除或添加操作，这就转化为对线性表的运算。在线性表中的基本运算包括：1求表长；2在线性表的指定位置插入一个数据元素；3删除线性表中指定位置的数据元素；4取线性表中指定位置的数据元素。为了实现这些基本操作，我们先来研究一下，线性表是如何存储在计算机中的。1线性表的存储结构线性表可以用不同的方式存储在计算机中，其中最简单也是最常见的是用一组地址连续的存储空间，依次存放线性表中的每一个数据元素，称为线性表的顺序存储结构，用这种方法存储的线性表称为顺序表。在高级语言中，可以用一维数组来实现。线性表还可以采用链式方式进行存储。每一个数据结点独立保存在内存的一片连续区域之中，结点之间通过“链”相互连接，这样就可以通过链来表示数据之间的先后次序关系了。链式方式可以采用C语言中的结构来实现。2线性表的插入和删除操作大家知道，在商场排队购物时，如果有一个人插入到队伍中，他后面的人们就不得不后退一步，以保持正常的队形。在线性表中插入一个数据元素，就与这一情况类似。那么，怎样让计算机来实现呢？首先应指明插入位置，假如在第i个元素之前插入一个新的数据元素a，为了保持线性表的连续性，就需要腾空第i个位置用于存放新插入的元素。为了实现这一操作，就必须从第i个元素开始到最后一个元素为止，把数据元素依次向后移动一个位置。移动从最后一个位置的数据元素开始，依次向后移动，使长度为n的线性表（s1,s2si-1,sisn）变成长度为n+1的线性表（s1,s2,si-1,a,si,sn）。这一过程用计算机来实现就是算法处理的基本思想。如图5.1所示：(a) 插入前n = 7 (b) 插入后n = 8图5.1 线性表的插入过程（在第4个位置前插入100）对于删除操作，如果要删除第i个数据元素，由于线性表中的元素必须连续排列，故删除第i个元素以后要使它后面的所有元素向前移动一个位置，使长度为n的线性表（s1,si-1,si,si+1,sn）变成长度为n-1的线性表（s1,si-1,si+1,sn）。请看图5.2，在线性表中删除17。(a) 删除前n = 8 (b) 删除后n = 7图5.2 线性表的删除过程（删除第6个位置的元素17）522 栈栈的概念是从日常生活中货物在货栈内的存取过程抽象出来的，最后入栈的货物最先被取出来，例如从图书馆的书架中取书放到桌子上，第一次取出的放在最底层，第二次被取出的书放在第一本书的上面，依次叠放，最后被取出来的放在最上面，当我们在这一摞中取书时，最后放入的被最先取出，符合先入后出，后进先出的原则，因此，栈也称作后进先出表。从逻辑上说，栈就是一种特殊的线性表，栈是一种受限的线性表，它限定在表的一端进行插入和删除操作。表中允许进行插入、删除操作的一端称为栈顶，另一端称为栈底。随着插入、删除操作的不断进行，栈顶的位置是动态变化的，用栈顶指针top指示。当栈中没有数据元素时，称为空栈，当top等于最大下标时，称为栈满。栈的插入操作通常称为进栈或入栈，删除操作称为退栈或出栈。图5.3是栈的动态示意图。 (a)空栈 (b)插入A后 (c)插入A、B、C、D、E、F后 (d)删除F后 (e) 删除E、D、C、B、A后 栈空523 队列日常生活中随处可看到排队的例子。例如：在商场排队购物，大家共同遵守一个规则，即先到者先购物，后到者必须排在队尾，按次序依次等待购物。队列与排队是一致的，最早进入队列的数据元素最早离开，符合先进先出原则。队列是线性表，也是一种受限的线性表，它限定只能在表的一端进行插入，另一端进行删除操作。允许插入的一端称作队尾，允许删除的一端称为队头。在队列中，随着插入、删除操作的不断进行，队头和队尾都是在动态变化的，因此，我们设置两个指针：front为头指针，rear为尾指针，rear指向队尾元素，front指向当前队头元素的前一个位置。通常可以用一组地址连续的存储空间存放队列元素，称为队列的顺序存储结构。图5.5 是队列的变化过程。（a）表示空队列，其头、尾指针front=rear=0；（b）表示元素a,b,c相继入队，此时front=0，rear=2；（c）d,e,f相继入队，尾指针rear = 5，队满；（d）a,b相继出队，头指针front = 1，此时再作入队操作，由于尾指针rear = 5，指向存储单元的最后一个位置而无法入队，但队列中仍有空余空间，并没有占满，这种现象称为队列的假溢出。图5.5队列变化过程为了解决假溢出，通常采用循环队列的方法，即把队列的存储空间设想成一个头尾相接的环状结构，如图5.6中的（a），我们将这种队列称为循环队列。当尾指针rear指向存储单元的最后1个位置，再作入队操作时，就能利用已被删除的数据元素的空间，进行入队操作，克服了假溢出。令 maxsize表示循环队列能容纳的元素个数，为了实现头、尾指针的循环移动，我们利用模运算。出队时： front=(front+1) % maxsize入队时： rear=(rear+1) % maxsize在循环队列中，为了区别队空和队满，我们不得不牺牲一个存储空间，来作为判别队满的条件。队满时： (rear +1) % maxsize= front队空时： front=rear图5.6 循环队列的头尾指针变化过程53 树型结构概述除了前面讨论的线性结构外，在客观世界中，还广泛存在着另一种非常重要的非线性数据结构，用于描述数据元素之间的层次关系。例如，人类社会的家族关系以及各种社会组织机构的表示，计算机文件管理和信息组织等等。531 树的概念和术语我们首先看下面二个例子，例如某一家族中，老王为爷爷辈，有两个儿子王一和王二，王一有二个儿子，而王二有一个儿子，这种家庭关系如图5.7所示。又如某大学中，下设电信学院、机电学院、医学院、工商管理学院，每个学院又有不同的专业，其行政组织机构如图5.8。从这两个例子中我们发现，它们都存在着一种层次的关系，而这两个图的形状又与自然界中的树非常相似，树型结构由此得名。下面从数据结构的角度，给出树的定义。图5.7家庭关系图图5.8大学行政组织机构一、树的定义树（tree）是由一个或多个结点组成的有限集合T，其中：有一个特定的结点称为该树的根（root）；除根结点外的其余结点可分为m(m0)个互不相交的有限集合T1、T2Tn，其中每一个集合Ti本身又是一棵树，称为根的子树。二、树的基本术语树型结构如图5.9所示，常常要用到一些基本术语，其中：结点表示树中的元素；结点的度是结点子树的个数，如图5.9中， A结点度为3， B结点度为2，E、F、G、I、J、K的度为零，它们也称为叶子结点； B、C、D是根结点A的孩子结点；而结点A是结点B、C、D的双亲，B、C、D之间互为兄弟； 结点的层次，从根结点开始为第一层，其余结点的层次为双亲结点的层次加1；树的深度是该树中结点的最大层次数。图5.9中的树共有4层，树的深度为4。532二叉树一、二叉树的定义：二叉树是n（n0）个结点的有限集合，它或为空树（n=0），或由一个根结点和两棵被分别称为左子树和右子树的互不相交的二叉树构成。由上述定义可知，二叉树与树是有区别的，在二叉树中，一个结点的子树有左、右之分不能互换位置，而树则无此限制，如图5.11中（a）(b)两棵树，若看成树，二者没有区别，若看成二叉树，对（a） 根结点T只有左子树A，右子树为空，