数据结构培训资料.ppt

第1章绪论,1.1什么是数据结构1.2基本概念和术语1.3抽象数据类型的表示与实现1.4算法和算法分析,电子计算机的主要用途：早期：主要用于数值计算。解决问题的步骤：数学模型解题算法选择计算机语言编程测试最终解答关键：如何得出数学模型当今：扩大到非数值计算领域。计算机的操作对象的关系更加复杂，数据元素间的相互关系有时无法用数学方程来描述。所处理的数据量大且具有一定的关系；而对其的操作也不再是单纯的数值计算，更多地是对其进行组织、管理和检索等。,例1：学籍档案管理,假设一个学籍档案管理系统应包含如下表所示的学生信息：,特点：,每个学生的信息占据一行，所有学生的信息按学号顺序依次排列构成一张表格；每列的数据类型一样；表中每个学生的信息依据学号的大小存在着一种前后关系，这就是我们所说的线性结构；对它的操作通常是插入、删除、更新、按条件检索某个学生的信息等等。,例2：输出n个对象的全排列,输出3个对象的全排列可以使用下图所示的形式描述：,特点：,在求解过程中，所处理的数据之间具有层次关系，这是我们所说的树形结构；对它的操作有：建立树形结构，输出最低层结点内容等等。,例3：制定教学计划,制定教学计划时，需考虑各门课程的开设顺序。有些课程需要先导课程，有些课程则不需要，而有些课程又是其他课程的先导课程。比如，计算机专业课程的开设情况如下表所示：,课程先后关系如图：,c1,c9,c4,c2,c12,c10,c5,c3,c6,c7,c8,c11,特点：,课程之间的先后关系用图结构描述；通过实施创建图结构，按要求将图结构中的顶点进行线性排序。,结论,要使计算机能够更有效地进行这些非数值性处理，就必须弄清楚这些操作对象的特点、之间的关系，在计算机中的表示方式及各种操作的具体实现手段。因此，数据结构研究的主要内容是：数据元素之间的逻辑关系数据的存储结构采用何种操作实现算法的效率更高,程序设计：为计算机处理问题编制一组指令集。算法：处理问题的策略。数据结构：问题的数学模型。程序设计的实质是对确定的问题选择一种好的结构，加上设计一种好的算法。,程序=算法+数据结构,“Programs=Algorithm+DataStructures”瑞士学者NiklausWirth于1976年出版的书名。,课程任务：1.讨论现实世界中数据的各种逻辑结构及在计算机中的存储结构；2.进行各种非数值运算的算法。,课程目的：掌握数据组织、存储和处理的常用法，为进行软件开发或后续专业课程学习打下良好的基础。,课程内容：数据结构的基本概念、线性表、栈和队列、串和数组、树形结构、图结构、查找、排序和文件等内容。,第1章绪论,1.1什么是数据结构1.2基本概念和术语1.3抽象数据类型的表示与实现1.4算法和算法分析,1.数据是对客观事物的符号表示。在计算机科学中是指所有能输入到计算机中并被计算机处理的符号的总称。计算机程序加工的“原料”。,例：,一个利用数值分析方法解代数方程的程序，其处理对象是整数和实数；一个编译程序或文字处理程序的处理对象是字符串。还有声音、图象、视频等等通过编码都属于数据的范畴。,2.数据元素是数据的基本单位。数据中的一个“个体”，数据结构中讨论的基本单位。在计算机中通常作为一个整体进行考虑和处理。,例：一个整数“5”；一个字符“N”；图中的一个顶点等。复杂型数据元素由多个数据项组成，它通常携带着一个概念的多方面信息。例：一个学生的基本信息就是一个数据元素，其中的学号、姓名等被称为“数据项”。因此数据项是数据结构中讨论的最小单位。数据元素是数据项的集合，数据项是数据的不可分割的最小单位。,3.数据对象性质相同的数据元素的集合。是数据的子集。,例：整数数据对象是集合N=0，1，2，。英文字母数据对象是集合C=A，Z。如何选定数据对象将依问题而定！譬如，在学生管理系统中，可能以一个班级的学生记录作为数据对象，也可能以一个年级的学生记录作为数据对象。,4.数据的逻辑结构讨论计算机系统中数据的组织形式及其相互关系。即相互之间存在一种或多种特定关系的数据元素的集合。数据逻辑结构的形式定义：数据逻辑结构是一个二元组：Data_structure=D,R其中，D是数据元素的有限集，R是D上的关系的集合。,例：在计算机科学中，复数可取如下定义：复数数据的逻辑结构Complex=(C,R)其中：C是含两个实数的集合c1,c2;R=P，而P是定义在集合C上的一种关系，其中有序偶表示c1是复数的实部，c2是复数的虚部。,4数据的逻辑结构,例：list=(D,S1),tree=(D,S2),graph=(D,S3)D=a,b,c,d,eS1=,S2=,S3=,逻辑结构示意图,称a是b的前驱，b是a的后继。若某结点没有前驱，则称该结点为开始结点；若某结点没有后继，则称该结点为终端结点；,（a,b,c,d,e）,4.数据的逻辑结构数据结构中所说的“关系”实际上是指数据元素之间的逻辑关系，又称此为逻辑结构。,数据的逻辑结构可归结为以下四类:1）集合：数据元素之间除“同属于一个集合”的关系外无其它关系。2）线性结构：数据元素间存在一对一的关系。3）树形结构：数据元素间存在一对多的关系。4）图（网）状结构：数据元素间存在多对多的关系。,集合,5.数据的存储结构（物理结构）存储结构：逻辑结构在计算机中的表示(又称映象)称为数据的物理结构，又称存储结构。包括数据元素的表示和关系的表示。计算机中表示信息的最小单位是二进制数的一位(bit)。可用一个由若干位组合起来形成的一个位串表示一个数据元素，通常称这个位串为元素(Element)或结点(Node)。当数据元素由若干数据项组成时，位串中对应于各个数据项的子位串称为数据域(DataField)。,5.数据的存储结构（物理结构）,存储的要求：既存储各结点的数值又要存储结点与结点之间的逻辑关系。四种基本的存储结构：顺序、链接、索引、散列存储。内存空间、内存地址程序在运行期间所需存储空间都在内存中分配.1.顺序存储（用数组实现）,存储方法:把逻辑上相邻的结点存储在一组连续的存储单元中,其结点之间的逻辑关系由存储单元地址间的关系隐含表示。例：list的顺序存储结构如下,200201202203204,优点：节省存储空间，可实现对各结点的随机访问。loc（i）q（i1）pq是第一个结点所占存储单元的首地址；p是每个结点所占单元数。,缺点：不便于修改。进行插入、删除运算时可能要移动一系列的数据元素。例：若删除list结构中的第三个结点c，则list的逻辑结构变成(a,b,d,e)。若在结点c前插入一个新的结点x，则list的逻辑结构变成(a,b,x,c,d,e)。逻辑结构发生变化后，相应的存储结构同样发生变化。e,b,a,dc,x,d,e,a,b,2.链接存储(用指针实现),存储方法：给每个机结点附加指针字段，用于存放相邻结点的存储地址。优点：便于修改缺点：浪费存储空间例：list（a,b,c,d,e）的存储结构示意图如下,删除结点c后(a,b,d,e),插入结点x后（a,b,x,c,d,e）,3.索引存储（用数组实现）,存储方法：根据结点的序号确定结点的存储地址。具体做法：建立索引表和结点表；将各结点的数值按任意顺序存放在结点表中，而将每个结点的存储地址用顺序存储方法存入索引表中。例：list（a,b,c,d,e)的索引存储结构如下,100101102103104,200201202203204,索引表,结点表,索引表,100101102103104,删除结点c后,删除结点c前后无变化,4.散列存储(用数组实现),存储方法：根据结点的值确定结点的存储地址。具体做法：以结点中某个字段的值为自变量，通过某个函数（称为散列函数）计算出对应的函数值i，再把i当作结点的存储地址。例：假定list结构中的5个结点数值是下列5个字符WuhanNanjingShanghaiXianBeijing散列函数：Loc(key)=asc(left(key,1)mod8KeyWuhanNanjingShanghaiXianBeijingasc(key)8778838866Loc(key)76302,01234567,数据的逻辑结构和物理结构是密切相关的两个方面，在后面的课程中我们会看到，任何一个算法的设计取决于选定的数据（逻辑）结构，而算法的实现依赖于所采用的存储结构。,完整的数据结构概念可认为是由数据的逻辑结构、存储结构及基本操作集三个部分组成：Data_Structure（D，R，P）其中D是数据元素的有限集合；R是D集上关系的有限集合，P是对D的基本操作集。,数据结构研究的内容,6.数据类型是和数据结构密切相关的一个概念，它最早出现在高级程序语言中，用以刻画（程序）操作对象的特性。数据类型：是一组性质相同的值的集合及定义于这个值集合上的一组操作的总称。,通用的计算机高级语言常见的有整数、实数（浮点数）、枚举、字符、字符串、指针、数组、记录文件等数据类型。譬如：整数类型通常用两个字节或四个字节表示，分别表示范围：-215215-1、-231231-1。对其允许施加的操作通常有：单目和双目，分别是取正或取负运算；加、减、乘、除、取模、等于、不等于、大于等关系（比较）运算。,依据“值”的不同特性，高级语言中数据类型可分为两类：1）原子类型原子类型的值是不可分解。如：C语言中的基本类型（整型、实型、字符型和枚举型），指针型。2）结构类型结构类型的值是由若干成分按某种结构组成，因此可以分解，且它的成分可以是非结构的，也可以是结构的。如：数组类型。,7.抽象数据类型（简称ADT）指一个数学模型及定义在此数学模型上的一组操作。“抽象”的意义在于数据类型的数学抽象特性。为提高软件复用率，近代程序设计方法学指出，一个软件系统的框架应建立在数据之上，而不是操作之上（后者是传统的软件设计方法所为）。即在构成软件系统的每个相对独立的模块上，定义一组数据和施于这些数据上的一组操作，并在模块内部给出这些数据的表示及其操作细节，而在模块外部使用的只是抽象的数据和操作。,ADT有两个重要特征:1）数据抽象用ADT描述程序处理的实体时，强调的是其本质的特征、其所能完成的功能以及它和外部用户的接口（即外界使用它的方法）。2）数据封装将实体的外部特性和其内部实现细节分离，并且对外部用户隐藏其内部实现细节。,抽象数据类型的描述方法：三元组表示（D，S，P）其中，D是数据对象，S是D上的关系集，P是对D的基本操作集。,ADT抽象数据类型名数据对象：数据对象的定义数据关系：数据关系的定义基本操作：基本操作的定义ADT抽象数据类型名其中，数据对象和数据关系的定义用伪码描述，基本操作的定义格式为：基本操作名（参数表）初始条件：初始条件描述操作结果：操作结果描述,基本操作有两种参数：1）赋值参数：只为操作提供输入值2）引用参数：以else语句；,开关语句1switch（表达式）case值1:语句序列1；break；case值n:语句序列n；break；default:语句序列n+1；开关语句2switchcase条件1:语句序列1；break；case条件n:语句序列n；break；default:语句序列n+1；,（6）循环语句For语句for（赋初值表达式序列；条件；修改表达式序列）语句序列；While语句while（条件）语句序列；Do-While语句do语句序列；while（条件）,（7）结束语句函数结束语句return表达式；return；Case结束语句break；异常结束语句exit（异常代码）；,（8）输入输出语句输入语句scanf（格式串，变量1，变量n）；输出语句printf（格式串，表达式1，表达式n）；通常省略格式串。,（9）注释单行注释/文字序列；（10）逻辑运算约定与运算in-1;+i)j=i;for(k=i+1;kn;+k)if(ak1change=TRUE/bubble_sort基本操作:赋值操作；时间复杂度:O（n2）,定理：若A(n)=amnm+am-1nm-1+a1n+a0是一个m次多项式，则A(n)=O(nm)如果算法的执行时间T(n)与问题规模n无关，是个常数，则记作T(n)=O(1)。例+x;s=0;将x自增看成是基本操作，则语句频度为，即时间复杂度为(1)。以下六种计算算法时间的多项式是最常用的。其关系为：O(1)O(n)O(n)O(nn)O(n2)O(n3)指数时间的关系为：O(2n)O(n!)O(nn),当n取得很大时，指数时间算法和多项式时间算法在所需时间上非常悬殊。因此，只要有人能将现有指数时间算法中的任何一个算法化简为多项式时间算法，那就取得了一个伟大的成就。有的情况下，算法中基本操作重复执行的次数还随问题的输入数据集不同而不同。,算法的存储空间需求空间复杂度(Spacecomplexity)：是指算法编写成程序后，在计算机中运行时所需存储空间大小的度量。记作：S(n)=O(g(n)其中：n为问题的规模(或大小)表示随着问题规模n的增大，算法运行所需存储量的增长率与g(n)的增长率相同。算法的存储量包括:1输入数据所占空间2程序本身所占空间3辅助变量所占空间,例：1.sum=0;for(j=1;j=n;j+)sum=sum+j;printf(“%d”,sum);,T(n)=O(f(n)=O(2n+3)=O(n),1n+1n1,2.Sum=0;for(I=1;I=n;I+)for(j=1;j=(y+1)*(y+1)y+;,T(n)=O(n),4.x=n;for(j=1;j=100;j+)x=x+j;,T(n)=O(1),若输入数据所占空间只取决于问题本身，和算法无关，则只需要分析除输入和程序之外的额外空间。若所需额外空间相对于输入数据量来说是常数，则称此算法为原地工作。若所需存储量依赖于特定的输入，则通常按最坏情况考虑。,本章小结,1.概念和术语数据数据元素数据对象数据结构逻辑结构存储结构抽象数据类型算法2.数据结构的研究目的和研究内容目的：寻求有效地组织和处理非数值数据的理论、技术和方法。内容：数据的逻辑结构、存储结构以及相应的基本操作运算的定义和实现。3.逻辑结构的四种基本形态集合结构、线性结构、树形结构、图状结构,本章小结,4.数据存储结构的基本组织方式顺序、链式5.数据结构引入ADT概念的优点运用ADT的概念实际上是将数据结构的讨论分成两部分：一是其概念所涵盖的数据逻辑结构的说明和运算的定义