数据库基础知识线形表.doc

第1章 数据结构的基本概念及算法什么是数据结构？为什么要学习数据结构？是学生学习这门课程之前最希望了解的。本章内容就是阐述这些问题。11 什么是数据结构什么是数据结构？为什么信息类的学生要学习数据结构？目前，随着计算机技术的发展，你将看见越来越多的大程序出现，而软件相对独立性及某些结构化和海量化的方法应用，使得人们更加重视数据结构。而程序设计的本质就是对给出的问题选择出一种好的数据结构和设计一个好的算法。数据结构是随着计算机的产生和发展而发展起来的一门介于数学、计算机硬件和计算机软件三者之间的一门核心课程。那数据结构究竟学习什么？我们知道，最近几年，计算机的发展突飞猛进，不仅仅体现在计算机本身的运算速度提升、价格持续走低、存储能力大幅度提高等方面，而且其应用无所不在，范围之广。随着计算机应用扩展，与此相适应，计算机加工处理的对象，也从最简单的数字处理到字符、图像、声音等各种复杂的、具有一定结构的数据。什么是数据结构呢？不妨先举一个简单的例子说明，然后再给出确切的定义。假定某大学有一个学生管理系统，专门记录学生的同学通讯录，记录了本学校所有的学生的姓名、家庭地址、联系电话、电子邮件、QQ号码等。现在要求设计一个程序或算法，当给定任何一个学生姓名的时候，计算机能查出该学生的各种联系发誓，如果根本没有这个人，计算机也能明确告诉“查不到此人”！那么这个工作就是“查找”。而根据学生姓名在同学通讯录表中的位置不同，查找的快慢就很不同。比如，现在校长想找某个学生谈话，而现在一个较大高校一般有2万在校学生，所有学生都站在操场集合。一种方法是学生任意排列，其次序没有任何规律。那么校长就很辛苦，只能依次从第一个学生逐个与要找的学生比较（即顺序查找），直到找得到或找不到此人。试想：2万学生，校长什么时候比较完？这样的效率太低了。如果，我们对学生进行适当的组织，即按字母的顺序排列或按专业再构造一个索引表，用这个表来登记每一个字母。这样就可以大为改善。所以采用了不同的结构，就可以写出不同的算法或程序。上述学生管理系统的组织方式就是一个数据结构问题。两种不同的数据结构，可以得到两种完全不同的算法。由此可见，计算机的算法与数据结构密切相关。即任何一个数据结构依赖与具体的数据结构，数据结构直接影响着算法或程序的效率。又如：当新生报到后，要添加新学生的数据信息；当老生毕业时，要删除该生的相关信息；当某个学生转专业了，要修改信息等等。所以数据结构必须给出相应的插入、删除、修改等运算。通过这个例子，简单地说：数据结构是一种构造解决问题的方法或策略。实际更是一门研究程序设计中计算机处理对象以及它们之间关系和运算的一门计算机学科。12 数据结构的基本概念和术语在计算机科学中，数据（data）是计算机程序加工处理的对象。抽象地描述，数据是对客观事物所进行的描述，而这种描述是采用了计算机系统所能识别、存储和处理的形式来进行的。比如数据结构期末成绩，其数据就是实数。因此，对计算机而言，数据含义很广，包括声音、图像、色彩等非数值数据。前面举例中学生相关信息就是数据。数据元素（data element）:是数据的基本单位，即数据这个集合中的一个客体，在计算机程序中通常作为一个整体进行考虑和处理。而数据项:有时，一个数据元素可由多个数据项组成。数据项是数据的不可分割的最小单位。数据对象（data object）：是性质相同的数据元素的集合，是数据的一个子集。例如：某班级本学期数据结构期末成绩集合23，89，98 。数据对象可以是有限的，也可以是无限的。数据类型、抽象数据类型数据类型:是一个值的集合和定义在这个值集上的所有的操作。例如，整数类型。数据类型可分为：非结构的原子类型和结构类型。原子类型的值是不可分解的，结构类型的值是由若干成分按某种结构组成的。 抽象数据类型:是指一个数学模型以及定义在该模型上的一组操作。抽象数据类型和数据类型实质上是一个概念，它仅取决于数据类型的逻辑性，而与其在计算机内部如何表示和实现是无关的。 抽象数据类型的定义由一个值域和定义在该值域上的一组操作组成。抽象数据类型按其值的不同特性，分为三种类型： 原子类型:变量的值是不可分解的。 固定聚合类型:变量的值由确定数目的成分按某种结构组成。 可变聚合类型:其值的成分数目不确定。抽象数据类型的形式定义：我们用一个三元组来表示一个抽象数据类型。（D，S，P）D是数据对象， S是D上的关系集， P是对D的基本操作。格式：ADT 抽象数据类型名数据对象：数据对象的定义数据关系：数据关系的定义基本操作：基本操作的定义ADT 抽象数据类型名。数据对象和数据关系的定义用伪码描述。数据基本操作的定义格式：基本操作名（参数表）初始条件：初始条件描述操作结果：操作结果描述例：ADT Triplet数据对象：D=e1，e2,e3 |e1,e2,e3Elemset(定义了关系运算的某个集合)数据关系：R1=e1,e2,基本操作：InitTriplet(&T,v1,v2,v3)DestroyTriplet（&T）Get（T,i,&e）Put(&T,i,e)IsAscending(T)IsDescending(T)Max(T,&e)Min(T,&e)ADT Triplet 多形数据类型:是其值的成分不确定的数据类型。除了最简单的数据对象之外，一般来说，数据对象中数据不是孤立的，而是彼此相关的，而这种相关关系就是“结构”。数据结构（data structure）：是相互之间存在一种或多种特定关系的数据元素的集合。数据结构就是研究数据元素之间抽象化的相互关系和这种关系在计算机中的存储表示。在对每种具体数据结构定义各自的运算，设计相应的算法。不过，数据结构不涉及数据元素本身的内容。依据元素之间的关系，可以划分为四类基本结构：集合、线性结构、树形结构、图形结构或网状结构。数据结构的形式定义：数据结构是一个二元组Data_Structure=(D,S)其中，D 是数据元素的有限集， S 是D上关系的有限集。例：复数 Complex=(C,R)严格地讲，数据结构一般包括三方面的内容： 逻辑结构（logical structure）：数据元素之间的逻辑关系，是用户按使用需要建立起来，并呈现在用户面前的数据元素的结构形式。 物理结构(physical structure)：又称存储结构，数据元素及其关系在计算机存储器的表示。指数据在计算机内实际的存储形式。 数据的运算：对数据施加的操作。算法的设计取决于选定的数据逻辑结构，而算法的实现依赖于采用的存储结构。数据结构的主要运算包括有：（1）创建和销毁一个数据结构的运算；（2）在已有数据结构中插入一个新元素或者删除一个元素；（3）对一个数据结构进行访问；（4）对已有的数据结构进行修改；（5）对已有数据结构进行查找或排列顺序。13 算法著名的计算机科学家、PASCAL语言发明者Niklaus Wirth教授曾提出一个著名的公式：算法+数据结构=程序它清楚地揭示了算法与数据结构这两个计算机科学重要支柱的重要与统一性。我们不能离开数据结构去抽象地分析求解问题的算法，也不能脱离算法去研究程序的数据结构。通常，算法的选择常常在很大程度上依赖数据结构。131 算法定义及特点什么是算法？算法是计算机科学和技术中一个很重要的概念。算法（algorithm）是执行特定计算的有穷过程，是对特定问题求解步骤的一种描述，它是指令的有限序列，其中每一条指令表示一个或多个操作。算法有五个特点：（1） 有限性 当执行一个算法时，不论什么情况，在经过有限步骤后，这个算法一定要结束，并且每一步都必须在有限的时间内完成。（2） 确定性 算法中的每一条指令都必须清楚，读者在理解的时候不会产生二义性。并且对同一个输入数据源，得到的输出结果只能是相同的。（3） 可行性 每一条指令都是能行的，即算法在原则上可由人在有限的时间内也能完成计算，也就是算法中描述的操作都是可以通过已经实现的基本操作运算执行有限次数来实现的。（4） 输入 一个算法有零个或多个由外界提供的量，这个输入取自某个特定的数据对象集合。（5） 输出 产生一个或多个量的输出。由此可见，算法与程序是有区别的，即程序未必具有有限性的特点。例如：程序出现死循环的现象。132 算法的描述我们在讨论各种数据结构的基本运算时，都会给出相应的算法。对于算法的描述，我们力求做到通俗易懂和便于自学，所以采用文本框进行示意。读者在掌握和理解框图所示的设计思想后，可以比较方便使用自己熟悉的算法语言来编程。另外，一般高校都在低年级开始了C语言，由于C语言能体现结构化程序设计的思想，所以本书将给出部分有C的伪码编写的算法。椭圆形矩 形菱形平行四边形 这是最常见的文字框图，它们各自的含义是：（1） 椭圆形：表示算法的“开始”或者“结束”，框中用文字说明。（2） 矩形框：表示某种操作，比如赋值、组织循环等，又称为操作框。(3) 平行四边形框：表示输入或输出操作，即提供运算所需的数据或记录，包括运算结果的输出。（4） 平行四边形框：表示判断，依据比较的结果来判断算法的走向。（5） 箭头：表示算法的走向。为了便于读者阅读和书写算法，通常做如下规定：（1） 书写算法说明。算法说明是一个完整算法不可或缺的部分。它包括这几个部分：指明算法的功能；形式参数表及作用；算法中的全局变量还是局部变量；那些限制条件等等。算法说明一般以注释的形式写在算法的最前面。（2） 算法的输入和输出实现途径。一是通过标准过程read（变量表）和write（变量表）实现，其特点是实现了算法和计算机环境的信息交换；二是通过算法中的参数作为输入输出的中介；三是通过变量隐式地传递信息。其中后面两种方法是实现一个算法与其它调用者之间的信息交换。（3） 所有的算法最好都写成函数的形式。（4） 算法中难以理解的地方，都应该加一定的注释，可以提高算法的可读性。133 算法的评价评价一个算法一般从以下几个方面进行：（1）正确性 算法是否正确，这是最基本的要求，它表示算法应该满足具体问题的需求。具体的含义包括：程序不存在语法错误；对合法的数据输入都能产生满足规格说明要求的结果。这两点，在软件测试中经常要考虑。（2）简单性 算法的主要目的是让读者阅读和理解，其次才是执行。简单有助于阅读。（3）稳健性 算法能对异常情况进行处理（4）运行时间和占用空间 一个算法在计算机上的运行所花费的时间尽可能的少，同时所花费的存储空间尽可能的小。这也就是指算法的效率，时空复杂度的问题。134算法分析在计算机程序设计中，算法分析是十分重要的。因为，对一个特定问题的求解方法，有很多，也就往往可以设计出若干个算法。在这中间就有一个最优的问题？往往通过算法执行时间来度量。而度量常常两种方法。事后统计 依据计算机系统的时钟，来统计所花费的时间。事前估计 一个问题的求解所花费的时间和占用的空间，有以下几个因素决定：（1） 问题的规模；（2） 采用何种策略；（3） 采用何种语言及运行环境；（4） 编译方式及质量；（5） 机器指令执行速度。举例，设有程序段如下：（1） for ( i=1; in ; i+)（2） for ( j=0 ; jn ; j+)（3） x=x+1;分析该算法三个语句的执行次数，我们分别可以得到是n、n2、n2 。显然，被称作问题的基本操作的原操作应该是其重复执行次数和算法的执行时间成正比的原操作。这里有一个重要的概念，语句的“频度”，就是该语句重复执行的次数。例： （a）+x;s=0;（b）for (i=1;i=n;+i) +x;s+=x;（c）for (j=1;j=n;+j)for (k=1;k=n;k+)+x;s+=x;含基本操作“x增1”的语句的频度分别为1,n和n2时间复杂度是O(1),O(n)和O(n2)。时间复杂度有时与输入有关。另外，算法的存储空间需求，是指算法运行过程中所占用存储空间。本章小结主要内