数据结构基础教程.ppt

数据结构（C语言版）,任课教师：冯 向阳,开课周次：1-16周 周一：5、6节，松1318 周四：1、2节，松1318 上机实践： 周四：1、2节 (第3周16周) 158 期终考试形式： 闭卷考试,教学计划安排,本课程的内容及学习的基本方法,本课程讲述的主要内容： 将分别讲述数据结构的基本概念、线性表、栈和队列、数组、树型结构、图结构、查找、排序等内容。 学习本课程的基本方法： 上课认真听讲。 仔细阅读教材及课件的讲授内容，体会并灵活掌握数据结构中的基本概念和知识点。 仔细阅读教材及课件中的大量例题，多做算法练习。,本课程成绩计算,平时成绩占10% 上机实践实验占20% 期终考试占70% E-mail地址： 网络硬盘URL：,第1章 绪论,学习要点 熟悉各名词、术语的含义，掌握基本概念，特别是数据的逻辑结构和存储结构之间的关系。分清哪些是逻辑结构的性质，哪些是存储结构的性质。 了解抽象数据类型的定义、表示和实现方法。 熟悉类C语言的书写规范、表示和实现方法。 理解算法五个要素的确切含义和对算法正确性的理解。 掌握计算语句频度和估算算法时间复杂度的方法。,数据结构的发展史,数据结构作为一门独立的课程在国外是从1968年才开始设立的。 1968年美国唐欧克努特教授开创了数据结构的最初体系，他所著的计算机程序设计技巧第一卷基本算法是第一本较系统地阐述数据的逻辑结构和存储结构及其操作的著作。 随着计算机技术的不断发展，数据结构广泛应用于计算机科学的各个领域。 编译程序利用堆栈、符号表和语法分析树； 操作系统由过程并列表和文件支持，并利用由可用空间的并列表或表格组成的存储管理模式； 人工智能程序利用堆栈、队列、集、搜索树、表格和图； 数据库利用串、并列表、树、环和表格。,数据结构讨论的范畴,数据结构是计算机相关专业的一门重要的专业基础课。它主要研究计算机加工对象的逻辑结构、在计算机中的表示形式以及实现各种基本操作的算法。它是学习操作系统、编译原理、数据库原理等计算机专业核心课程的基础。掌握好这门课程的内容，是学习计算机其他相关课程的必备条件。 Nikalaus Wirth (Pascal语言之父) Algorithm + Data Structures = Programs,问题求解,程序编写,数据结构,程序设计,算法,数据结构讨论的范畴,数据处理的种类,数值数据,非数值数据,数值 (整数,实数) 字符 字符串 文字 图形 图象 声音,数值性计算,数值性计算： 数值计算问题的数学模型通常可以用一组线性或非线性的代数方程组或微分方程组来描述。 即使是不需要用计算机求解的简单问题也需要一个数学模型来描述。 鸡兔同笼问题：二元一次方程组 房屋设计或桥梁设计中的结构应力分析：线性代数方程组 天气预报：环流模式方程,数值性计算,例 已知：游泳池的长len和宽wide，求面积area,(2)设计 求解问题的方法 (3)编程 main ( ) int len, wide ,area ; scanf (“%d %d%n”, ,(1)建模型： 问题涉及的对象：游泳池的长len，宽wide，面积area； 对象之间的关系：area = len wide,非数值性计算,非数值性计算： 当操作对象的关系更加复杂，操作形式不再是单纯的数值计算，而更多地是对这些具有一定关系的数据进行组织管理，就需要对之进行非数值性处理。 当计算机进入非数值计算领域，特别是用在管理上的时候，计算机的操作对象之间的关系就无法用数学方程加以描述了。 应用举例1 学籍档案管理 假设一个学籍档案管理系统应包含如下页的表1-1所示的学生信息。,表1-1 学生基本情况,非数值性计算(举例1),非数值性计算(举例1),特点： 每个学生的信息占据一行，所有学生的信息按学号顺序依次排列构成一张表格。 表中每个学生的信息依据学号的大小存在着一种前后关系，这就是我们所说的线性结构。 对它的操作通常是插入某个学生的信息，删除某个学生的信息，更新某个学生的信息，按条件检索某个学生的信息等等。,非数值性计算(举例2),1,12,21,123,132,312,213,231,321,3个对象的全排列过程,应用举例2：输出n个对象的全排列 可以使用下页所示的图示描述。,非数值性计算(举例2),特点： 在求解过程中，所处理的数据之间具有层次关系，这就是我们所说的树形结构。 对它的操作有：建立树形结构，输出最底层结点内容等等。 应用举例3 制定教学计划 在制定教学计划时，需要考虑各门课程的开设顺序。有些课程需要先导课程，有些课程则不需要，而有些课程又是其他课程的先导课程。比如，计算机专业课程的开设情况如下页的表1-2所示。,非数值性计算(举例3),表1-2 计算机专业学生的必修课程,非数值性计算(举例3),C4,C5,C2,C1,C9,C3,C7,C10,C11,C6,C8,C12,图1-2 课程先后关系的图形描述形式,非数值性计算(举例3),特点： 课程之间的先后关系用图结构描述。 通过实施创建图结构，按要求将图结构中的顶点进行线性排序。 结论： 以上所举例子中的数学模型正是数据结构要讨论的问题。因此，简单地说，数据结构是一门讨论描述现实世界实体的数学模型(非数值计算) 及其上的操作在计算机中如何表示和实现的学科。,基本概念和术语(数据),数据(data) 数据是对客观事物的符号表示。在计算机科学中，其含义是指所有能够输入到计算机中并被计算机程序处理的符号集合。 例如，一个个人书库管理程序所要处理的数据可能是下表所示的表格。,基本概念和术语(数据元素),数据元素(data element) 数据元素也称为结点，是数据集合中的一个实体，是数据结构中讨论的基本单位。 数据元素按其组成可分为简单型数据元素和复杂型数据元素。前者由一个数据项组成；后者由多个数据项组成，它通常携带着一个概念的多方面信息。,基本概念和术语(数据项),数据项(data item) 一般情况下，一个数据元素中含有若干个字段，也称为数据项。数据元素是数据项的集合。 数据项是数据结构中讨论的最小单位。,数据项之间的关系,数据项和数据项之间存在次序关系 例如，一个含12位数的十进制数可以用三个4位的十进制数来表示。 3214,6587,9345 = a1(3214),a2(6587),a3(9345) 在a1、a2和a3之间存在次序关系：、 3214,6587,9345 6587,3214,9345 a1 a2 a3 a2 a1 a3,数据项之间的关系(续),数据项和数据项之间存在次序关系 又例，2行3列的二维数组a1,a2,a3,a4,a5,a6 行的次序关系: row = , , , 列的次序关系: col = , , ,基本概念和术语(数据结构),数据结构(data structure) 数据结构是以数据项为元素的一种结构。 数据结构的组成是由各数据项之间的关系和用来存储、恢复这些数据项的存取函数来确定的。 为了叙述上的方便和避免产生混淆，通常把数据的逻辑结构(logic structure)统称为数据结构，把数据的物理结构统称为存储结构(storage structure)。,数据的逻辑结构,数据的逻辑结构(logic structure) 数据元素和数据元素之间的逻辑关系成为数据的逻辑结构。 如下的表格数据中，各数据元素之间在逻辑上有一种线性关系。,数据的逻辑结构的分类,数据的逻辑结构可归结为以下四类： 线性结构：结构中的数据元素之间存在一个对一个的关系。 树形结构：结构中的数据元素之间存在一个对多个的关系。 图状结构：结构中的数据元素之间存在多个对多个的关系。 集合：结构中的数据元素除了同属于一个集合的关系外，别无其他关系。,数据的逻辑结构的分类(续),数据的逻辑结构可归结为以下四类： 线性结构 树形结构 图状结构 集合结构,数据结构的形式定义,数据结构的形式定义为： 数据结构是一个二元组： Data_Structure = (D,S) 其中: D是数据元素的有限集，S是D上关系的有限集。 严格地讲，以上定义仅是数据的逻辑结构的定义。 例如，在计算机科学中，复数可看成一种数据结构 Complex = (C,R) 其中，C是含两个实数的集合c1,c2；R = P，而P 是定义在集合C上的一种关系，其中有序偶表示c1是复数的实部，c2是复数的虚部。,数据的存储结构,数据的存储结构(storage structure) 是指数据结构在计算机中存储器中的具体实现。 与孤立的数据元素的表示形式不同，数据结构中的数据元素不但要表示其本身的实际内容，还要表示清楚数据元素之间的逻辑关系。 数据元素之间的关系在计算机中有两种不同的表示方法：顺序映像和非顺序映像，并由此得到两种不同的存储结构：顺序存储结构和链式存储结构。,数据的存储结构(续),顺序存储结构： 特点是借助于数据元素的相对存储位置来表示数据元素之间的逻辑结构。 链式存储结构： 特点是借助于指示数据元素地址的指针来表示数据元素之间的逻辑结构。 在不同的编程环境中，存储结构可有不同的描述方法。 用高级语言程序设计语言进行编程时，通常可用该语言提供的数据类型来描述。,数据类型,数据类型： 是指程序设计语言中各变量可取的数据类型。数据类型是高级程序设计语言中的一个基本概念，它和数据结构的概念密切相关。 一方面，在程序设计语言中，每一个数据都属于某种数据类型。类型明显或隐含地规定了数据的取值范围、存储方式以及允许进行的运算。可以认为，数据类型是在程序设计中已经实现了的数据结构。 另一方面，在程序设计过程中，当需要引入某种新的数据类型时，总是借助编程语言所提供的数据类型来描述数据的存储结构。,C+的基本数据类型及取值的范围,抽象数据类型,抽象数据类型(Abstract Data Type 简称ADT)： ADT是指一个数学模型以及定义在此数学模型上的一组操作。 ADT的两个重要特征： 数据抽象：用ADT描述程序处理的实体时，强调的是其本质的特征、其所能完成的功能以及它和外部用户的接口(即外界使用它的方法)。 数据封装：将实体的外部特征和其内部实现细节分离，并且对外部用户隐蔽其内部实现细节。 ADT需要通过固有数据类型(高级编程语言中已实现的数据类型)来实现。,抽象数据类型的格式定义,ADT的格式定义： 和数据结构的形式定义相对应，ADT可用一个三元组表示： ADT_Data_Structure = (D,S,P) 其中: D是数据对象，S是D上的关系集，P是对D的基本操作集。 ADT可用以下格式来定义： ADT抽象数据类型名 数据对象： 数据关系： 基本操作： ADT抽象数据类型名,抽象数据类型(举例),例如，抽象数据类型复数的定义： ADT Complex 数据对象：D = e1,e2 | e1,e2 RealSet 数据关系：R1 = | e1是复数的实数部分， | e2是复数的虚数部分 基本操作： InitComplex( &Z,v1,v2 ) 操作结果：构造复数Z，其实部和虚部分别被赋以参数v1和v2的值。 DestroyComplex( &Z ) 操作结果：复数Z被销毁。 GetReal( Z, &RealPart) 初始条件：复数已存在。 操作结果：用RealPart返回复数Z的实部值。 GetImag( Z, &ImagePart) 初始条件：复数已存在。 操作结果：用ImagePart返回复数Z的虚部值。 Add( z1,z2,&sum) 初始条件：z1,z2是复数。 操作结果：用sum返回两个复数z1,z2的和值。 ADT Complex,抽象数据类型(举例),其中，数据对象和数据关系的定义用伪码描述，基本操作的定义格式为： 基本操作名 (参数表) 初始条件： 操作结果： 基本操作有两种参数：赋值参数只为操作提供输入值；引用参数以&打头，除可提供输入值外，还将返回操作结果。 初始条件描述了操作执行之前数据结构和参数应满足的条件，若不满足，则操作失败，并返回相应出错信息。若初始条件为空，则省略之。 操作结果说明了操作正常完成之后，数据结构的变化状况和应返回的结果。,算法和算法设计的过程,算法(algorithm)： 算法是解决某个特定问题的一种方法或一个过程。 计算机对数据的操作可以分为数值性和非数值性两种类型。在数值性操作中主要进行的是算术运算；而在非数值性操作中主要进行的是检索、排序、插入、删除等等。 设计算法的基本过程： 通过对问题进行详细地分析，抽象出相应的数学模型。 确定使用的数据结构，并在此基础上设计对此数据结构实施各种操作的算法。 选用某种语言将算法转换成程序。 调试并运行这些程序。,算法的特征,算法应该具有下列五个特性： 有穷性：一个算法必须在执行有穷步之后结束。 确定性：算法中的每一步，必须有确切的含义，在他人理解时不会产生二义性。 可行性：算法中描述的每一步操作都可以通过已有的基本操作执行有限次实现。 输入：一个算法应该有零个或多个输入。 输出：一个算法应该有一个或多个输出。这里所说的输出是指与输入有某种特定关系的量。,算法(举例),举例： 问题：按从大到小的顺序重新排列x,y,z三个数值的内容。 算法： 输入x,y,z三个数值； 从三个数值中挑选出最小者并换到x中； 从y,z中挑选出最小者并换到y中； 输出排序后的结果。,选择算法描述语言的原则,选择算法描述语言的原则： 该语言应该具有描述数据结构和算法的基本功能； 该语言应该尽可能地简捷，以便于掌握、理解； 使用该语言描述的算法应该能够比较容易地转换成任何一种程序设计语言。 类C描述语言是通过对C语言进行精心筛选保留的一个核心子集，并为了便于描述，又做了若干扩展修改，从而增强了语言的描述功能。 以下对其作简要说明。,算法描述语言(续),预定义常量及类型： #define TRUE 1 #define FALSE 0 #define OK 1 #define ERROR 0 #define OVERFLOW -1 数据元素被约定为ElemType类型，用户需要根据具体情况，自行定义该数据类型。 typedef char ElemType,算法描述语言(续),算法描述为以下的函数类型： 函数类型 函数名 (函数参数表) 语句序列； 为了简化函数的书写，提高算法描述的清晰度，我们规定除函数参数表中的参数需要说明数据类型外，函数中使用的局部变量可以不做变量说明，必要时给出相应的注释即可。另外，在书写算法时，应该养成对重点语句段落添加注解的良好习惯。,算法描述语言(续),在算法描述中可以使用的赋值语句形式有： 简单赋值 变量名 = 表达式； 串联赋值 变量名1 = 变量名2 = = 变量名n = 表达式； 成组赋值 (变量名1，变量名n) = (表达式1， ，表达式n)； 结构赋值 结构名1 = 结构名2； 结构名 = (值1，值2，值n)； 条件赋值 变量名 = 条件表达式?表达式1：表达式2； 交换赋值 变量名1 变量名2；,算法描述语言(续),在算法描述中可以使用的选择结构语句形式有： 条件语句1 if (表达式) 语句； 条件语句2 if (表达式) 语句； else 语句； 开关语句1 switch (表达式) case 值1：语句序列1；break; case 值n：语句序列n；break； default： 语句序列n+1; ,算法描述语言(续),在算法描述中可以使用的选择结构语句形式有： 开关语句2 switch (表达式) case 条件1：语句序列1；break; case条件n：语句序列n；break； default： 语句序列n+1; ,算法描述语言(续),在算法描述中可以使用的循环结构语句形式有： for 循环语句 for (表达式1；循环条件表达式；表达式2) 语句； while 循环语句 while (循环条件表达式) 语句； do-while 循环语句 do 语句序列； while (循环条件表达式)；,算法描述语言(续),在算法描述中可以使用的结束语句形式有： 函数结束语句 return 表达式； return; case或循环结束语句 break； 异常结束语句 exit (异常代码)； 在算法描述中可以使用的输入输出语句形式有： 输入语句 scanf (格式串，表达式1，表达式n)； 输出语句 printf (格式串，表达式1，表达式n)； 方括号()中的内容是可以省略的部分。,算法描述语言(续),在算法描述中使用的注释格式有： 单行注释 / 文字序列 在算法描述中可以使用的扩展函数有： 求最大值 max (表达式1，表达式n)； 这个函数返回参数表中n个表达式计算结果中的最大值。 求最小值 min (表达式1，表达式n)； 这个函数返回参数表中n个表达式计算结果中的最小值。,算法描述语言(举例),【算法1-1】用类C描述将三个数值排序的算法： void Three_Sort (int *x, int *y, int *z) / 将x,y,z三个指针所指示的内容按从大到小的顺序重新排列 if( *y *x & *y *z ) *x *y； / 挑选出最小的数值并换到x指针所指的存储单元中 else if( *z *x & *z *y ) *x *z ； if( *z *y ) *y *z； / 在y和z所指示的存储单元中挑选出较小者换到y中 ,算法设计的原则,算法设计的原则： 正确性：要求算法能够正确地执行预先规定的功能，并达到所期望的性能要求。 可读性；算法主要是为了人的阅读与交流，其次才是为计算机执行。因此算法应该易于人的理解；另一方面，晦涩难读的程序易于隐藏较多错误而难以调试。 健壮性：当输入的数据非法时，算法应当恰当地做出反应或进行相应处理，而不是产生莫名其妙的输出结果。并且，处理出错的方法不应是中断程序的执行，而应是返回一个表示错误或错误性质的值，以便在更高的抽象层次上进行处理。 时间与空间效率：算法的时间与空间效率是指将算法交换为程序后，该程序在计算机上运行时所花费的时间及所占据空间的度量。,算法正确性的理解,对算法是否正确的理解可以有以下四个层次： 程序中不含语法错误； 程序对于几组输入数据能够得出满足要求的结果； 程序对于精心选择的、典型、苛刻且带有刁难性的几组输入数据能够得出满足要求的结果； 程序对于一切合法的输入数据都能得出满足要求的结果。 通常以第3层的正确性作为衡量一个算法是否合格的标准。,算法的时间效率,算法的时间效率主要由两个因素组成： 所需处理问题的数据量大小，数据量大，所花费的时间就多； 在解决问题的过程中，基本操作的执行次数。 通常有两种衡量算法效率的方法： 事后统计法 有两个缺陷 必须执行程序； 其他因素掩盖算法本质。 事前分析估算法 和算法执行时间相关的因素： 算法选用的策略； 问题的规模； 编写程序的语言； 编译程序产生的机器代码的质量； 计算机执行指令的速度。,算法的时间复杂度,时间复杂度 一般情况下，可以将一个算法所花费的时间设计成一个以数据量n为自变量的函数T(n)=O(f(n)。 这个函数在正整数定义域范围内一定是单调递增的。它表示随数据量n的增大，算法执行时间函数T(n)的增长率和函数f(n)的增长率相同。称函数T(n)为算法的(渐进)时间复杂度。,算法的时间复杂度,大O记法： 这种描述中使用的基本参数是n，即问题实例的规模，把复杂性或运行时间表达为n的函数。 这里的O表示量级(order)。例如，二分检索是O(logn)的，就是说它需要通过logn量级的步骤去检索一个规模为n的数组。 记法O(f(n)表示：当n增大时，运行时间至多将以正比于f(n)的速度增长。 从算法中选取一种对于所研究的问题来说是基本操作的原操作，以该基本操作在算法中重复执行的次数作为算法运行时间的衡量标准。 算法的执行时间 = 原操作(i)的执行次数 原操作(i)的执行时间,算法的时间复杂度(举例1),例一：在下列程序段中 for( i = 1; i = n; +i ) for( j = 1; j = n; +j ) ci,j = 0; for( k = 1; k = n; +k ) ci,j += ai,k * bk,j; 基本操作：乘法操作 时间复杂度：O(n3),算法的时间复杂度(举例2),例二：在下列程序段中 Void select_sort( int a, int n ) / 将a中的整数序列重新排列成自小至大的顺序 for( i = 0; i n 1; + i ) j = i; for(