数据结构讨论的是数据的逻辑结构

,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,第1章 概论,数据结构讨论的是数据的逻辑结构、存储方式以及相关操作的实现等问题，为学习后续专业课程打下基础。本章讲述数据结构的基本概念及相关术语，介绍数据结构、数据类型和抽象数据类型之间的联系，介绍了算法的特点及算法的时间与空间复杂性。,1.1数据结构,1.1.1,数据结构,随着计算机软、硬件的发展，计算机的应用范围在不断扩大，计算机所处理的数据的数量也在不断扩大，计算机所处理的数据已不再是单纯的数值数据，而更多的是非数值数据。,需要处理的数据并不是杂乱无章的，它们一定有内在的联系，只有弄清楚它们之间的本质的联系，才能使用计算机对大量的数据进行有效的处理。,某电信公司的市话用户信息表格如下图所示：,序号,用户名,电话号码,用户住址,街道名,门牌号,00001,万方林,3800235,北京西路,1659,00002,吴金平,3800667,北京西路,2099,00003,王,冬,5700123,瑶湖大道,1987,00004,王,三,5700567,瑶湖大道,2008,00005,江,凡,8800129,学府大道,5035,这里序号、用户名、电话号码等项称为基本项，它是有独立意义的最小标识单位，而用户住址称为组合项，组合项是由一个或多个基本项或组合项组成，是有独立意义的标识单位，每一行称为一个结点，每一个组合项称为一个字段。,使用计算机处理用户信息表中的数据时，必须弄清楚下面3个问题：,1,数据的逻辑结构,这些数据之间有什么样的内在联系？,除最前和最后两个结点之外，表中所有其它的结点都有且仅有一个和它相邻位于它之前的一个结点，也有且仅有一个和它相邻位于它之后的一个结点，这些就是用户信息表的逻辑结构。,2 数据的存储结构,将用户信息表中的所有结点存入计算机时，就必须考虑存储结构，使用,C,语言进行设计时，常见的方式是用一个结构数组来存储整个用户信息表，每一个数组元素是一个结构，它对应于用户信息表中的一个结点。数据在计算机的存储方式称为存储结构。,3 数据的运算集合,数据处理必涉及到相关的运算，在上述用户信息表中，可以有删除一个用户、增加一个用户和查找某个用户等操作。应该明确指明这些操作的含义。比如删除操作，是删除序号为5的用户还是删除用户名为王三的用户是应该明确定义的，如果需要可以定义两个不同的删除操作，为一批数据定义的所有运算（或称操作）构成一个运算（操作）集合。,对待处理的数据，只有分析清楚上面3个方面的问题，才能进行有效的处理！,数据结构,就是指按一定的逻辑结构组成的一批数据，使用某种存储结构将这批数据存储于计算机中，并在这些数据上定义了一个运算集合。,1.1.2数据的逻辑结构,数据的逻辑结构是数据和数据之间所存在的逻辑关系，它可以用一个二元组,B=,（,K,，,R,）,来表示，其中K是数据、即结点的有限集合；R是集合K上关系的有限集合，这里的关系是从集合K到集合K的关系，这里一般只涉及到一个关系的逻辑结构。,例如，有,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=,逻辑结构的,图形表示,方式，对,K,中的每个结点,k,i,用一个方框表示，而结点之间的关系用带箭头的线段表示，这,5,人之间的逻辑结构用图形的方式表达如下图,所示。,若k,i,K，k,j,R，r，则称k,i,是k,j,的相对于关系r的,前驱结点,，k,j,是k,i,的相对于关系r的,后继结点,，因为一般只讨论具有一种关系的逻辑结构，即R=r，所以简称k,i,是k,j,前驱，k,j,是k,i,的后继。如果某个结点没有前驱结点，称之为,开始结点,；如果某个结点没有后继结点，称之为,终端结点,；既不是开始结点也不是终端结点的结点称为,内部结点,。,1.1.3数据的存储结构,数据的逻辑结构是独立于计算机的，它与数据在计算机中的存储无关，要对数据进行处理，就必须将数据存储在计算机中。如果将数据在计算机中无规律地存储，那么在处理时是非常糟的，是没有用的。试想一下，如果一本英汉字典中的单词是随意编排的，这本字典谁会用！,对于一个数据结构,B=,（,K,，,R,），必须建立从结点集合到计算机某个存储区域,M,的一个映象，这个映象要,直接或间接,地表达结点之间的关系,R,。数据在计算机中的存储方式称为数据的存储结构。,数据的存储结构主要有,4,种。,数据的存储结构主要有,4,种。,1,顺序存储,顺序存储通常用于存储具有线性结构的数据。将逻辑上相邻的结点存储在连续存储区域M的相邻的存储单元中，使得逻辑相邻的结点一定是物理位置相邻。,对于一个数据结构,B=,（,K,，,R,）,其中,K=k,1,k,2,k,3,k,4,k,5,k,6,k,7,k,8,k,9,R=r r=,它的顺序存储方式如图所示,2,链式存储,链式存储方式是给每个结点附加一个指针段，一个结点的指针所指的是该结点的后继的存储地址，因为一个结点可能有多个后继，所以指针段可以是一个指针，也可以是一个多个指针。,例，数据的逻辑结构,B=,（,K,，,R,）,其中,K=k,1,k,2,k,3,k,4,k,5,R=r,R=,这是一个线性结构，它的链式存储如图所示。,3,索引存储,在线性结构中，设开始结点的索引号为1，其它结点的索引号等于其前继结点的索引号加1，则每一个结点都有唯一的索引号，索引号就是根据结点的索引号确定该结点的存储地址。,4,散列存储,散列存储的思想是构造一个从集合K到存储区域M的一个函数h，该函数的定义域为K，值域为M，K中的每个结点k,i,在计算机中的存储地址由h(k,i,)确定。,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,个或多个输入。,输出，,算法一定有输出结果,可行性，算法中的运算都必须是可以实现的。,算法具有有穷性，程序不需要具备有穷性。一般的程序都会在有限时间内终止，但有的程序却可以不在有限时间内终止，如一个操作系统在正常情况下是永远都不会终止的。,1.3.2算法的时间和空间复杂性,一个算法的优劣主要从算法的执行时间和所需要占用的存储空间两个方面衡量，算法执行时间的度量不是采用算法执行的绝对时间来计算的，因为一个算法在不同的机器上执行所花的时间不一样，在不同时刻也会由于计算机资源占用情况的不同，使得算法在同一台计算机上执行的时间也不一样，所以对于算法的时间复杂性，采用算法执行过程中其基本操作的执行次数，称为计算量来度量。,算法中基本操作的执行次数一般是与问题规模有关的，对于结点个数为n的数据处理问题，用T(n)表示算法基本操作的执行次数。,在评价算法的时间复杂性时，不考虑两算法执行次数之间的细小区别，而只关心算法的本质差别。为此，引入一个所谓的O()记号，则T1(n)=2n=O(n),T2(n)=n+1=O(n)。,一个函数f(n)是O(g(n)的，则一定存在正常数c和m，使对所有的nm，都满足f(n)c*g(n)。,下面的表格给出了一些具体函数的,O(),的表示，如图所示。,f(n),O(g(n),量级,35,O(1),常数阶,2n+7,O(n),线性阶,n,2,+10,O(n,2,),平方阶,2n,3,+n,O(n,3,),立方阶,算法的时间复杂性不仅和问题的规模大小有关，还与问题数据的初始状态有关。,这样就有了算法在最好、最坏以及在平均状态下的时间复杂性的概念。,算法在最好情况下的时间复杂性是指算法计算量的最小值。,算法在最坏情况下的时间复杂性是指算法计算量的最大值。,算法的平均情况下的时间复杂性是指算法在所有可能的情况下的计算量经过加权计算出的平均值。,