数据结构培训PPT.ppt

数据结构？,数据结构？,数据结构？,数据 结构！,初步认识“数据结构”-揭开数据结构神秘的面纱！,1.什么是数据结构？,2.为什么要学数据结构？,3.如何学好数据结构？,1.什么是数据结构？,原始文字1：漆黑的头发没有麻子脚不大周正,演绎1：漆黑的头发，没有麻子，脚不大，周正。,演绎2：漆黑的头发没有，麻子，脚不大周正。,结论1：文字的不同组合，得到不同的含义！,1.什么是数据结构？,原始文字2：你，我，给，钱,演绎1：你给我钱,演绎2：我给你钱,结论2：文字的不同序列，得到不同的含义！,1.什么是数据结构？,趣味短信1：我一般不爱人,趣味短信2：我不爱一般人,趣味短信3：我爱人不一般,1.什么是数据结构？,对话一：甲：您好。您贵姓？乙：你谁呀？甲：我52。乙：干嘛?甲：我想把您的电话号码录下来。乙：我姓郭。甲：姓郭，好，谢谢啊。,结论1：不同的说话方式体现不同的素质,对话二：甲：您好。我52。我想把您的电话号码录下来。您贵姓？乙：我姓郭。甲：姓郭，好，谢谢啊。,结论2：语句的不同序列，得到不同的含义！,数据结构 数据结构,数据结构是相互之间存在着某种逻辑关系的数据元素的集合。,1.什么是数据结构？,你给我钱？,我给你钱！,2.为什么要学数据结构？,？人为什么吃饭,1）饥饿,？我们为什么学数据结构,2）享受,3）交流,学好数据结构：是进行程序设计的前提，也是人生处事的借鉴。,1）概念 2）算法 3）规范,4）提高信息素养 5）必须的,3.如何学好数据结构？,温故而知新，可以为师矣！复习学过的知识，可从中获得新的见解与体会了。凭借这点就可以当老师了！,学而时习之，不亦说乎？学了知识然后按一定时间去实习它，不也很高兴的吗？,3.如何学好数据结构？,学而不思则罔，思而不学则殆。只读书却不思考,就会感到迷茫而无所得，只是空想而不读书，就会让学业陷入困境。,知之为知之，不知为不知，是知也。知道的就是知道，不知道就是不知道，这就是智慧啊。,3.如何学好数据结构？,上课环节,1）预习 2）听讲 3）提问,3.如何学好数据结构？,课后环节,1）复习 2）整理笔记 3）作业 4）上机练习,5）交流 6）多问问题,http:/,充分利用网络资源,数据结构QQ群：82175087,http:/,第1章 绪论第2章 线性表第3章 栈和队列第4章 串第5章 数组,数据结构,第6章 树和二叉树第7章 图第9章 查找第10章 排序学时：56+24,1.1 数据结构讨论的范畴,1.2 基本概念,1.3 算法和算法的量度,第1章 绪论,1.1 数据结构讨论的范畴,一、计算机的主要用途早期：主要用于数值计算。后来：处理逐渐扩大到非数值计算领域（能处理多种复杂的具有一定结构关系的数据）。,二、什么是程序？,Niklaus Wirth：Algorithm+Data Structures=Programs,程序:算法:数据结构:,计算机处理问题的指令集,处理问题的策略,问题的数学模型,例如：计算机对弈,算法：?模型：?,对弈的规则和策略,棋盘及棋盘的格局,数据结构：是进行程序设计的基础。,数据结构是一门讨论“描述现实世界实体的数学模型(非数值计算)及其上的操作在计算机中如何表示和实现”的学科。数据结构是一门研究非数值计算的程序设计问题中计算机的操作对象以及它们之间的关系和操作的学科。,三、数据结构研究的范畴,1.2 基本概念,一、数据与数据结构,二、数据类型,三、抽象数据类型,一、数据与数据结构,1.数据 是对客观事物的符号表示，是所有能被输入到计算机中，且能被计算机处理的符号的集合。2.数据元素 是数据的基本单位，具有完整确定的实际意义。也是数据结构中讨论的基本单位。,3.数据项 是构成数据元素的项目，是具有独立含义的最小标识单位是数据结构中讨论的最小单位。三者之间的关系 数据 数据元素 数据项示例 通讯录 个人记录 姓名、年龄,4.数据结构：,带结构的数据元素的集合,假设用三个 4 位的十进制数表示一个含 12 位数的十进制数。,3214,6587,9345 a1(3214),a2(6587),a3(9345),则在数据元素 a1、a2 和 a3 之间存在着“次序”关系 a1,a2、a2,a3,3214，6587，9345 a1 a2 a3,6587，3214，9345 a2 a1 a3,例如:,又例，在2行3列的二维数组a1,a2,a3,a4,a5,a6中六个元素之间存在两个关系:,行的次序关系:列的次序关系:,row=,col=,a1 a3 a5 a2 a4 a6,a1 a2 a3a4 a5 a6,数据结构是相互之间存在着某种逻辑关系的数据元素的集合,结论：不同的“关系”构成不同的“结构”,5.数据的逻辑结构和物理结构,集合结构：仅同属一个集合线性结构:一对一（1:1)树形结构:一对多（1:n)网状结构:多对多(m:n),非线性,线 性,逻辑结构可细分为4类：集合、线性、树、图,指数据元素之间的逻辑关系，即从逻辑关系上描述数据，它与数据的存储无关，是独立于计算机的。,解释1：数据的逻辑结构,5.数据的逻辑结构和物理结构,物理结构亦称存储结构，是数据的逻辑结构在计算机存储器内的表示（或映像）。它依赖于计算机。,存储结构可分为4大类：,例：复数3.02.3i 的两种存储方式：,顺序、链式、索引、散列,法1：地址 内容,法2：地址 内容,2字节,解释2：数据的物理结构,6.数据结构的形式定义,数据结构是一个二元组,Data_Structures=(D,S),其中:D 是数据元素的有限集，S 是 D上关系的有限集。,7.数据的存储结构,逻辑结构在存储器中的映象,“数据元素”的映象？,“关系”的映象？,（1）数据元素的映象方法：,用二进制位位串表示数据元素,(321)10=(501)8=(101000001)2,A=(101)8=(001000001)2,（2）关系的映象方法：,（表示为x,y）,顺序映象,以相对的存储位置表示后继关系,链式映象,以附加信息(指针)表示后继关系,y x,x y,二、数据类型,数据类型是一个值的集合和定义在此集合上的一组操作的总称。,注意：不同类型的变量，其所能取的值的范围不同，所能进行的操作不同。,如：-9不能作开方运算！,数据类型=数集+操作,三、抽象数据类型(Abstract Data Type 简称ADT),ADT是指一个数学模型以及定义在此数学模型上的一组操作。,1.定义：,抽象数据类型可以用以下的三元组来表示：ADT=（D，R，P）,数据对象,D上的关系集,D上的操作集,2.抽象数据类型的定义格式：,数据对象：D.数据关系：R1 基本操作：,ADT 类型名,ADT 类型名,例如，抽象数据类型复数的定义：,数据对象：De1,e2e1,e2RealSet 数据关系：R|e1是复数的实数部分,e2是虚数部分,ADT Complex,基本操作：,AssignComplex(DestroyComplex(&Z)GetReal(Z,&realPart)GetImag(Z,&ImagPart)Add(z1,z2,&sum),ADT Complex,基本操作：,AssignComplex(&Z,v1,v2)操作结果：构造复数 Z,其实部和虚部 分别被赋以参数 v1 和 v2 的值。,DestroyComplex(&Z)操作结果：复数Z被销毁。,GetReal(Z,&realPart)初始条件：复数已存在。操作结果：用realPart返回复数Z的实部值。,GetImag(Z,&ImagPart)初始条件：复数已存在。操作结果：用ImagPart返回复数Z的虚部值。,Add(z1,z2,&sum)初始条件：z1,z2是复数。操作结果：用sum返回两个复数z1,z2 的 和值。,假设:z1和z2是上述定义的复数,则 Add(z1,z2,z3)操作的结果,即为用户企求的结果：z3=z1+z2,说明：Add(z1,z2,z3)具体内容应该 由程序设计人员编写。,3.抽象数据类型如何表示和实现,抽象数据类型可以通过固有的数据类型如：整型、实型等来表示和实现。,1）用C语言中的结构（struct)类型描述。2）用类C语言作为描述工具。3）用C+语言中的类（class)描述。,但上机时要用具体语言实现，如C或C+等,1.3 算法和算法的衡量,一、算法,二、算法设计的原则,三、算法效率的衡量方法和准则,四、算法的存储空间需求,算法是为了解决某类问题而规定的一个有限长的操作序列。,一、算法,1.算法及其特性：,一个算法必须满足的重要特性：,1)有穷性:对于任意一组合法输入值，在执行有穷步骤之后一定能结束，即：算法中的每个步骤都能在有限时间内完成。,2)确定性:对于每种情况下所应执行的操作，在算法中都有确切的规定，使算法的执行者或阅读者都能明确其含义及如何执行。并且在任何条件下，算法都只有一条执行路径。,3)可行性:算法中的所有操作都必须足够基本，都可以通过已经实现的基本操作运算有限次实现之。,4)有输入:作为算法加工对象的量值，通常体现为算法中的一组变量。有些输入量需要在算法执行过程中输入，而有的算法表面上可以没有输入，实际上已被嵌入算法之中。,5)有输出:它是一组与“输入”有确定关系的量值，是算法进行信息加工后得到的结果，这种确定关系即为算法的功能。,1)有穷性,2)确定性,3)可行性,4)有输入,5)有输出,注意：算法和程序的关系算法与程序的含义十分相似，但不相同：1.一个程序不一定满足有穷性，可以死循环；2.程序中的指令必须是可执行的，算法中的指令则无此限制；3.一个算法若用计算机语言来书写，则它就可以是一个程序。,2.算法的描述和实现,描述-可采用自然语言、数学语言或约定的符号语言。,实现-必须借助程序设计语言提供的数据类型及其运算。,本课的描述-采用类C语言。,二、算法设计的原则,算法设计应考虑达到以下目标：,1正确性,2.可读性,3健壮性,4高效率与低存储量需求,1.正确性,首先，算法应当满足以特定的“规格说明”方式给出的需求。C不同于Java,其次，对算法是否“正确”的理解可以有以下四个层次：,3）程序对于精心选择的、典型、苛刻且带有刁难性的几组输入数据能够得出满足要求的结果；,4）程序对于一切合法的输入数据都能得出满足要求的结果。,1）程序中不含语法错误；,2）程序对于几组输入数据能够得出满足要求的结果；,“正确”算法的四个层次：,2.可读性,算法主要是为了人的阅读与交流，其次才是为计算机执行，因此算法应该易于人的理解；另一方面，晦涩难读的程序易于隐藏较多错误而难以调试。,3.健壮性,当输入的数据非法时，算法应当恰当地作出反映或进行相应处理，而不是产生莫名奇妙的输出结果。并且，处理出错的方法不应是中断程序的执行，而应是返回一个表示错误或错误性质的值，以便在更高的抽象层次上进行处理。,4.高效率与低存储量需求,效率：算法执行时间存储量：算法执行所需最大存储空间共同点：两者都与问题的规模有关,三、算法效率衡量方法和准则,1.通常有两种衡量算法效率的方法:,事后统计法,事前分析估算法,缺点：1)必须执行程序 2)其它因素掩盖算法本质,2.和算法执行时间相关的因素：,1)算法选用的策略,2)问题的规模,3)编写程序的语言,4)编译程序产生的机器代码的质量,5)计算机执行指令的速度,3.时间复杂度 一个特定算法的“运行工作量”的大小，只依赖于问题的规模通常用整数量n表示。或者说，它是问题规模的函数。,假如：随着问题规模 n 的增长，算法执行时间的增长率和 f(n)的增长率相同，则可记作：T(n)=O(f(n)。称T(n)为算法的(渐近)时间复杂度。,复杂度高,复杂度低,时间复杂度T(n)按数量级递增顺序为：,4.如何估算 算法的时间复杂度？,算法=控制结构+原操作（固有数据类型的操作）,算法的执行时间=原操作(i)的执行次数原操作(i)的执行时间,算法的执行时间 与 原操作执行次数之和 成正比,因此：从算法中选取一种对于所研究的问题来说是基本操作的原操作，以该基本操作在算法中重复执行的次数作为算法运行时间的衡量准则。,例一两个矩阵相乘,void mult(int a,int b,int/for/mult,基本操作:乘法操作,时间复杂度:O(n3),例二选择排序,void select_sort(int&a,int n)/将 a 中整数序列重新排列成自小至大有序的整数序列。/select_sort,基本操作:比较(数据元素)操作,时间复杂度:O(n2),j=i;/选择第 i 个最小元素for(k=i+1;k n;+k)if(ak aj)j=k;,for(i=0;i n-1;+i)if(j!=i)aj ai,例三起泡排序,void bubble_sort(int-i)/bubble_sort,基本操作:赋值操作,时间复杂度:O(n2),change=FALSE;/change 为元素进行交换标志 for(j=0;j aj+1)aj aj+1;change=TRUE;/一趟起泡,四、算法的存储空间需求,算法的空间复杂度定义为:,表示随着问题规模 n 的增大，算法运行所需存储量的增长率与 g(n)的增长率相同。,S(n)=O(g(n),1.输入数据所占空间2.程序本身所占空间3.辅助变量所占空间,数据结构,数据,结构,数据元素,数据项,逻辑结构,物理结构,集合,线性结构,树结构,图结构,线性,非线性,顺序,链式,索引,散列,程序,算法,特性,原则,时间复杂度,正确性,可读性,健壮性,高效性,低存储,有穷性,确定性,可行性,有输入,有输出,O(f(n),知识回顾,1.熟悉各名词、术语的含义，掌握基本概念。,2.理解算法五个要素的确切含义。,本章小结,3.掌握计算语句频度和估算算法时间复杂度的方法。,巩固练习,1.下面的程序段违反了算法的（）原则void sam()int n=2;while(!odd(n)n+=2;printf(n);A.有穷性 B.确定性 C.可行性 D.健壮性,2.计算机算法必须具备输入、输出、（）等5个特性。A.可行性、可移植性和可扩展性 B.可行性、确定性和有穷性 C.确定性、有穷性和稳定性 D.易读性、安全性和稳定性,3.在数据结构中，逻辑上数据结构可分为（）A.动态结构和静态结构 B.线性结构和非线性结构 C.紧凑结构和非紧凑结构 D.内部结构和外部结构,作业：1.画出本章的知识层次图2.给出几个生活中可用数据结构解释的实例,