《数据结构》讲义

1第一章：绪论课程：数据结构课题：第一章1.1—1.4小节（共4个课时）1.1什么是数据结构1.2基本概念和术语1.3抽象数据类型的表现与实现1.4算法和算法分析目的要求：理解数据、数据元素、数据项的概念；掌握逻辑结构和存储结构的关系；理解算法的基本概念；学会分析算法的时间复杂性和空间复杂性。新课重点、难点：数据、数据元素、数据项、时间复杂性和空间复杂性教学方法：课堂讲解、例题演示，课件演示教学内容及过程：……………………………第1-2课时……………………………计算机的应用不再局限于科学计算，更多地用于控制，管理，数据处理等非数值计算的处理工作。计算机加工处理的对象：数值，字符，表格，图形声音，图象等具有一定结构的数据。进行程序设计时必须分析待处理的对象的特性及各对象之间存在的关系———产生背景。1.1什么是数据结构计算机解题步骤：建立数学模型——设计解此数学模型的算法——编制程序——进行测试调整——解答。其中建立数学模型的实质：找出操作对象之间的关系。例1.图书馆书目检索——对应线性关系例2.博奕树——对应树型关系例3.交叉路口交通灯管理——对应图状结构。数据结构是一门研究非数值计算的程序设计问题中计算机的操作对象及它们之间的关系和操作等的学科。（地位）1.2数据结构的基本概念和术语1.数据（Data）数据是描述客观事物的数值、字符以及能输入机器且能被处理的各种符号集合。换句话说，数据是对客观事物采用计算机能够识别、存储和处理的形式所进行的描述；是计算机加工处理的对象。包括数值、字符、声音、图象等。2.数据元素（DataElement）数据元素是组成数据的基本单位,是数据集合的个体，在计算机中通常作为一个逻辑整体进行考虑和处理。一个数据元素可由若干个数据项组成（DataItem）。3.数据对象（DataObject）数据对象是性质相同的数据元素的集合，是数据的一个子集。例如：整数数据对象是集合N={0，±1，±2，…}，字母字符数据对象是集合C={′A′，′B′，…，′Z′}，表1-1所示的学籍表也可看作一个数据对象。由此可看出，不论数据元素集合是无限集（如整数集）、有限集（如字符集），还是由多个数据项组成的复合数据元素（如学籍表），只要性质相同，都是同一个数据对象。综上1~3所述，再分析数据概念：24.结构（DataStructure）数据元素相互之间的关系称为结构（Structure），有四种基本结构。(1)集合结构：结构中的数据元素之间除了同属于一个集合的关系外，无任何其它关系。(2)线性结构：结构中的数据元素之间存在着一对一的线性关系。(3)树形结构：结构中的数据元素之间存在着一对多的层次关系。(4)图状结构或网状结构：结构中的数据元素之间存在着多对多的任意关系。线性结构——线性表、栈、队、字符串、数组、广义表非线性结构——树、图数据结构的形式定义：数据结构是一个二元组Data_structure=(D,S)。其中：D为数据结构的有限集，S是D上关系的有限集。例：复数结构Complex=(C,R)其中：C为含两个实数的集合{c1,c2}；R={P}，P是集合C上的一种关系，P={c1,c2}，c1,c2为有序偶，c1表示复数的实部，c2表示复数的虚部。存储结构存储结构（又称物理结构）是逻辑结构在计算机中的存储映象，是逻辑结构在计算机中的实现，它包括数据元素的表示和关系的表示。形式化描述：D要存入机器中，建立一从D的数据元素到存储空间M单元的映象S，D→M，即对于每一个d，d∈D,都有唯一的m∈M，使S（D）=m,同时这个映象必须明显或隐含地体现关系R。逻辑结构与存储结构的关系为：存储结构是逻辑关系的映象与元素本身的映象。逻辑结构是数据结构的抽象，存储结构是数据结构的实现，两者综合起来建立了数据元素之间的结构关系。顺序映象（顺序存储结构）顺序结构用元素在存储器中的相对位置表示数据元素之间的逻辑关系。非顺序映象（非顺序存储结构）非顺序映像借助指示元素存储地址的指针表示元素之间的逻辑关系。一维数组来描述顺序存储结构，用指针来描述链式存储结构。运算的集合数据结构的内容可归纳为三个部分：逻辑结构、存储结构和运算集合。按某种逻辑关系组织起来的一批数据，按一定的映象方式把它存放在计算机的存储器中，并在这些数据上定义了一个运算的集合，就叫做数据结构。数据类型(DataType)3数据类型是一组性质相同的值集合以及定义在这个值集合上的一组操作的总称。数据类型中定义了两个集合，即该类型的取值范围，以及该类型中可允许使用的一组运算。例如高级语言中的数据类型就是已经实现的数据结构的实例。从这个意义上讲，数据类型是高级语言中允许的变量种类，是程序语言中已经实现的数据结构（即程序中允许出现的数据形式）。在高级语言中，整型类型可能的取值范围是-32768~+32767，可用的运算符集合为加、减、乘、除、取模（如C语言中+，-，*，/，%）。抽象数据类型１）数据的抽象计算机中使用的是二进制数，汇编语言中则可给出各种数据的十进制表示，如98.65、9.6E3等,它们是二进制数据的抽象;使用者在编程时可以直接使用,不必考虑实现细节。在高级语言中，则给出更高一级的数据抽象，出现了数据类型，如整型、实型、字符型等。到抽象数据类型出现，可以进一步定义更高级的数据抽象，如各种表、队、栈、树、图、窗口、管理器等，这种数据抽象的层次为设计者提供了更有利的手段，使得设计者可以从抽象的概念出发，从整体考虑，然后自顶向下、逐步展开，最后得到所需结果。可以这样看，高级语言中提供整型、实型、字符、记录、文件、指针等多种数据类型，可以利用这些类型构造出像栈、队列、树、图等复杂的抽象数据类型。２）抽象数据类型(AbstractDataType)抽象数据类型（简称ADT）是指基于一类逻辑关系的数据类型以及定义在这个类型之上的一组操作。抽象数据类型的定义取决于客观存在的一组逻辑特性，而与其在计算机内如何表示和实现无关，即不论其内部结构如何变化，只要它的数学特性不变，都不影响其外部使用。从某种意义上讲，抽象数据类型和数据类型实质上是一个概念。整数类型就是一个简单的抽象数据类型实例。“抽象”的意义在于教学特性的抽象。一个ADT定义了一个数据对象，数据对象中各元素间的结构关系，以及一组处理数据的操作。ADT通常是指由用户定义且用以表示应用问题的数据模型，通常由基本的数据类型组成，并包括一组相关服务操作。抽象数据类型是近年来计算机科学中提出的最重要的概念之一，它集中体现了程序设计中一些最基本的原则：分解、抽象和信息隐藏。一个抽象数据类型确定了一个模型，但将模型的实现细节隐藏起来；它定义了一组运算，但将运算的实现过程隐藏起来。数学模型→抽象数据类型→数据结构，恰好反应了信息结构转换的三个重要阶段，而在这个转换过程中，数据结构是基础，抽象数据类型是中枢。一个线性表的抽象数据类型的描述如下：ADTLinear-list数据元素所有ai属于同一数据对象，i=1，2，…，n,n≥0；逻辑结构所有数据元素ai（i=1，2，…，n-1）存在次序关系ai，ai+1，ai无前趋，an无后继；操作设L为Linear-list:Initial(L):初始化空线性表;Length(L):求线性表的表长;Get(L,i):取线性表的第i个元素；Insert(L,i,b):在线性表的第i个位置插入元素b；Delete(L,i):删除线性表的第i个元素。３）抽象数据类型实现第一种情况：传统的面向过程的程序设计。第二种情况：“包”、“模型”的设计方法。第三种情况：面向对象的程序设计（ObjectOrientedProgramming，简称OOP）。４）ADT的定义ADT的定义格式不唯一,我们采用下述格式定义一个ADT:ADT抽象数据类型名{数据对象:数据对象的定义数据关系:结构关系的定义基本操作:基本操作的定义4}ADT抽象数据类型名其中数据对象和结构关系的定义采用数学符号和自然语言描述,而基本操作的定义格式为:操作名称(参数表)初始条件:初始条件描述操作结果:操作结果描述关于参数传递参数表中的参数有两种：第一种参数只为操作提供待处理数据,又称值参；第二种参数既能为操作提供待处理数据,又能返回操作结果，也称变量参数。操作前提描述了操作执行之前数据结构和参数应满足的条件,操作结果描述操作执行之后,数据结构的变化状况和应返回结果。ADT可用现有计算机语言中已有的数据类型,即固有数据类型来表示和实现。不同语言的表示和实现方法不尽相同，如ADT中“返回结果的参数”，PASCAL语言用“变参”实现,C++语言通过“引用型参数”实现,而C语言用“指针参数”实现。用标准C语言表示和实现ADT描述时，主要包括以下两个方面:(1)通过结构体将int、float等固有类型组合到一起,构成一个结构类型,再用typedef为该类型或该类型指针重新起一个名字。(2)用C语言函数实现各操作。基本操作主要有以下几种：(1)插入：在数据结构中的指定位置上增添新的数据元素；(2)删除：删去数据结构中某个指定数据元素；(3)更新：改变数据结构中某个元素的值，在概念上等价于删除和插入操作的组合；(4)查找：在数据结构中寻找满足某个特定要求的数据元素（的位置和值)；(5)排序：（在线性结构中）重新安排数据元素之间的逻辑顺序关系，使数据元素按值由小到大或由大到小的次序排列。结构化的开发方法与面向对象的开发方法的不同点，结构化的开发方法是面向过程的开发方法，首先着眼于系统要实现的功能。从系统的输入和输出出发，分析系统要实现的功能，用自顶向下、逐步细化的方式建立系统的功能结构和相应的程序模块结构。一旦程序功能需要修改，就会涉及多个模块，修改量大，易于出错，并会引起程序的退化。作业1：1：理解和掌握几个重要的基本概念：数据结构；抽象数据类型等；2：理解和运用四种逻辑结构；并进行合理的划分。……………………………第3-4课时……………………………1．3抽象数据类型的表示和实现(1)预定义常量和类型。本书中用到以下常量符号，如True、False、MAXSIZE等，约定用如下宏定义预先定义：＃defineTRUE1＃defineFALSE0＃defineMAXSIZE100＃defineOK1＃defineERROR0(2)本书中所有的算法都以如下的函数形式加以表示，其中的结构类型使用前面已有的定义。［数据类型］函数名（［形式参数及说明］）{内部数据说明；执行语句组；}/*函数名*/函数的定义主要由函数名和函数体组成，函数体用花括号“{”和“}”括起来。函数中用方括号括起来的部分如“［形式参数］”为可选项，函数名之后的圆括号不可省略。5(3)赋值语句。1、简单赋值;（1）〈变量名〉=〈表达式〉，它表示将表达式的值赋给左边的变量；（2）〈变量〉++，它表示变量加1后赋值给变量；（3）〈变量〉--，它表示变量减1后赋值给变量。2、串联赋值#;〈变量1〉=〈变量2〉=〈变量3〉=…=〈变量k〉=〈表达式〉；3、成组赋值#;（〈变量1〉，〈变量2〉，〈变量3〉，…,〈变量k〉)=（〈表达式1〉，〈表达式2〉，〈表达式3〉，…,〈表达式k〉）；〈数组名1〉［下标1］［下标2］=〈数组名2〉［下标1］［下标2］；4、条件赋值;〈变量名〉=〈条件表达式〉？〈表达式1〉:〈表达式2〉；(4)条件选择语句。if（〈表达式〉）语句；if（〈表达式〉）语句1；else语句2；(5)循环语句。1、for语句for(表达式1；表达式2；表达式3）{循环体语句；}首先计算表达式1的值，然后求表达式2的值，若结果非零（即为真）则执行循环体语句，最后对表达式3运算，如此循环，直到表达式2的值为零（即不成立为假）时为止。2、while语句while(条件表达式）{循环体语句；}while循环首先计算条件表达式的值，若条件表达式的值非零（即条件成立），则执行循环体语句，然后再次计算条件表达式的值，重复执行，直到条件表达式的值为零（即为假）时退