数据结构课件NO.1基本概念.ppt

第一章 数据结构,主要内容,1.1数据结构的基本概念与算法 1.2 线性表 1.3 栈和队列 1.4 树和二叉树 1.5 查找 1.6 排序,数据结构国家等级考试大纲要求,1. 算法的基本概念；算法复杂度的概念和意义（时间复 杂度与空间复杂度）。 2. 数据结构的定义；数据的逻辑结构与存储结构；数据 结构的图形表示；线性结构与非线性结构的概念。 3. 线性表的定义；线性表的顺序存储结构及其插入与删 除运算。 4. 栈和队列的定义；栈和队列的顺序存储结构及其基本 运算。 5. 线性单链表、双向链表与循环链表的结构及其基本运 算。 6. 树的基本概念；二叉树的定义及其存储结构；二叉树 的前序、中序和后序遍历。 7. 顺序查找与二分法查找算法；基本排序算法（交换类 排序，选择类排序，插入类排序）。,1.1 数据结构的基本概念与算法,1.1.1 数据结构的基本概念,1.数据结构的定义,(1)数据：信息载体，能够被计算机识别、存储和加工处理。可以使数值数据(整数、实数)，也可以是非数值数据(声音、图像等) 。,(2)数据元素：数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理(又称结点、记录)。,数据项：一个数据元素由若干数据项组成，数据的不可分割的最 小单位。,关键码：其值能唯一确定一个数据元素的数据项。,举例：图书管理系统 数据元素 数据项 关键码 (一本书)书目信息 书目信息每一项 书号(唯一确定一本书),4个数据元素,5个数据项,1个数据项,1个数据元素,(3)数据对象：具有相同性质的数据元素的集合。数据元素是数据对象类的一个实例。,关键码：值唯一能区别不同的 数据元素的数据项,数据对象-由4个记录组成,表中每行是一个记录,每个记录由5个数据项组成.,(4)数据结构,定义:相互之间存在着一种或多种关系的数据元素的集合。,研究内容:,数据的逻辑结构：各数据元素之间的逻辑关系 数据的存储结构：各数据元素在计算机中的存储关系 对各种数据结构进行的运算：添加，删除，排序等。,2.数据的逻辑结构,四类基本逻辑结构,(1)集合结构：数据元素间的关系是“属于同一个集合” (2)线性结构：数据元素之间存在一个对一个的关系。 (3)树形结构：数据元素之间存在一个对多个的关系。 (4)图形结构：数据元素之间存在多个对多个的关系。,集合结构,线性结构,树型结构,图形结构：数据元素之间存在多个对多个的关系，图形结构也称作网状结构。,线性结构与非线性结构,概念,结点:组成数据结构的数据元素称为一个结点。,前后件关系:,数据元素之间的固有关系可以用前后件关系(前驱与后继关系)描述。 举例：家庭成员辈分关系(父亲、儿子、女儿)，“父亲”是“儿子”和“女儿”的前件， “儿子”和“女儿”是 “父亲”后件。,线性结构,有且只有一个根结点 每个结点最多有一个前件，也最多有一个后件,非线性结构,一个数据结构如果不是线性结构，则称之为非线性结构。数据元素的前后关系复杂，一个结点既可以有多个前件，也可以有多个后件。树型、图形结构属于非线性结构。,3.数据的存储结构,定义：数据的逻辑结构在计算机存储空间中的存放形式。数据存储结构中不仅存放各数据元素信息，还存放前后件关系的信息。,实现方式：,(1)顺序存储方式：逻辑上相邻的元素存储在物理位置相邻的存储单元中。主要用于线性结构。通常借助于数组来实现。,顺序存储结构的线性表,线性表(a1, a2, a3, a4),存储单元的地址即物理地址,(2)链式存储方式：对逻辑上相邻的元素不要求其物理地址相邻，元素间逻辑关系通过附加的指针字段来表示。通常借助于指针类型实现。,链式存储结构的线性表,线性表(a1, a2, a3, a4),存储单元的地址即物理地址,指针域：存放下一个结点的地址,a1,a2在逻辑上相邻,而在机内存储时,存储单元的地址(100,105)并不相邻.,链式存储结构的特点,每个结点由两部分组成：一部分存放数据，另一部分存储指向前件或后件结点的指针域。 逻辑上相邻的结点物理上不必相连。 数据运算(插入和删除等)灵活。,(3)索引存储方法和散列存储方法(为了查找方便),4.数据结构的表示,(1)二元关系表示,B=( D, R ),B：数据结构 D：数据元素的集合 R：D上的关系 (反映数据元素前后件关系),家庭成员数据结构 B=( D, R ) D =父亲,儿子,女儿 R =(父亲,儿子),(父亲,女儿),(2)图形表示,D中每个数据元素用标有元素值的方框表示,简称结点。 R中每个二元组,用一条有向线段从前件结点指向后件结点。,根结点：没有前件的结点 叶子结点(终端结点)：没有后件的结点,几种基本数据结构的节点图：,叶子结点,根结点,叶子结点,根结点,5.数据的运算,定义：在数据的逻辑结构上定义的操作算法,常见运算：插入、删除、查找、排序和更新等,分类：,加工型运算：运算改变了数据结构的值 引用型运算：不改变值，只查询或求得结构的值。,6.数据类型及其分类,定义：数据类型是一个值的集合和定义在这个值集上的一组操作的总称。例：C语言中的整型变量，其值为某个区间上整数，定义在其上的操作为：加，减、乘、除和求余数等算术运算。,分类：非结构的原子类型和结构类型,（1）非结构的原子类型：原子类型的值是不可分解的。如：程序设计语言中的基本类型（整型，实型，字符型，指针类型和空类型）。,（2）结构类型：结构类型的值是由若干成分按某种结构组成的，因此是可分解的，并且它的成分可以是非结构的，也可以是结构的。,例如：用C语言编程序时，描述一个学生信息的结构可以如下表示：,typedef struct int yy; / 年号 int mm; / 月号 int dd; / 日号 datetype; / 日期类型 typedef struct char nm8; / 学号 char name18; / 姓名 char sex; / 性别 datetype date; / 出生日期 studenttype; / 学生类型,1.1 数据结构的基本概念与算法 总结,1.数据结构定义 2. 数据的逻辑结构（集合、线性、树形、图形） 3. 数据的存储结构（顺序、链式） 4. 数据结构的表示 5. 数据运算：插入、删除、查找、排序和更新等 6. 数据类型及其分类,一. 算法的基本概念 1.定义： 为解决某个特定问题而采取的确定且有限的步骤。,1.1 数据结构的基本概念与算法,1.1.2 算法及算法分析,首先要从具体问题抽象出一个适当的数学模型； 然后设计一个解此数学模型的算法； 最后采用一种计算机语言编出程序，调试、修改 直至得到最终答案。,用计算机解决一个具体问题时，大致需要经过下列几个步骤：,一. 算法的基本概念 1.定义： 为解决某个特定问题而采取的确定且有限的步骤。,1.1 数据结构的基本概念与算法,1.1.2 算法及算法分析,2.算法特性： 有穷性： 一个算法应包含有限个操作步骤，而且每一步都应在有限时间内完成。 确定性：算法中每一条指令必须有确切的含义，确保不会产生二义性。 可行性：算法中指定的操作都是可以通过基本运算执行有限次后实现。 输入：一个算法有零个或多个的输入，这些输入取自于某个特定的对象集合。 输出：一个算法有一个或多个的输出，这些输出是同输入有着某些特定关系的量。,一. 算法的基本概念 1.定义： 为解决某个特定问题而采取的确定且有限的步骤。,2.算法特性： 有穷性： 一个算法应包含有限个操作步骤，而且每一步都应在有限时间内完成。 确定性：算法中每一条指令必须有确切的含义，确保不会产生二义性。 可行性：算法中指定的操作都是可以通过基本运算执行有限次后实现。 输入：一个算法有零个或多个的输入，这些输入取自于某个特定的对象集合。 输出：一个算法有一个或多个的输出，这些输出是同输入有着某些特定关系的量。,二. 算法的基本要素及描述,1.1 数据结构的基本概念与算法,1.1.2 算法及算法分析,1.算法基本要素构成,对数据对象的运算和操作,算法的控制结构,算术运算: 加、减、乘、除 逻辑运算：与、或、非等运算 关系运算：大于、小于、等于等 数据传输：赋值、输入、输出,顺序 选择 循环（重复）,2. 算法的描述: 自然语言，伪代码，流程图, N-S图, 类C,一. 算法的基本概念 1.定义： 为解决某个特定问题而采取的确定且有限的步骤。,1.1 数据结构的基本概念与算法,1.1.2 算法及算法分析,2.算法特性： 有穷性： 一个算法应包含有限个操作步骤，而且每一步都应在有限时间内完成。 确定性：算法中每一条指令必须有确切的含义，确保不会产生二义性。 可行性：算法中指定的操作都是可以通过基本运算执行有限次后实现。 输入：一个算法有零个或多个的输入，这些输入取自于某个特定的对象集合。 输出：一个算法有一个或多个的输出，这些输出是同输入有着某些特定关系的量。,二. 算法的基本要素及描述,1.算法基本要素构成,对数据对象的运算和操作,算法的控制结构,算术运算:加、减、乘、除 逻辑运算：与、或、非等运算 关系运算：大于、小于、等于等 数据传输：赋值、输入、输出,顺序 选择 循环（重复）,2. 算法的描述: 自然语言，伪代码，流程图, N-S图, 类C,三.算法设计要求（评价算法标准）,1.正确性：执行结果应满足预先的功能和性能要求 2.可读性：思路清晰、层次分明、简单明了、易读易懂。 3.健壮性：输入数据非法时，算法能作适当处理，不致于引 起严重后果 4 .效率： 有效使用存储空间和较高的时间效率。,四.算法设计的基本方法,1. 列举法： 列举出所有可能情况，用给定条件检验哪些是需要的，哪些是不需要的(如用循环解决百元买百鸡问题）。 2. 归纳法： 列举少量简单而又特殊的情况，分析归纳出一般结论。,3.递推法： 从已知初始条件出发，逐步推出各种中间结果和最后结果（如猴子吃桃）。 4.递归法： 解决复杂问题时，将问题逐层分解，归纳为一些简单问题，解决了最后简单问题后，再沿原来的逆过程逐步综合（如求某数的阶乘）。,5.减半递推技术（分治法）：(补充） 减少：把问题规模减半，而性质不变 递推：重复减半的过程,6. 回溯法 （补充） 在工程上有些实际问题很难归纳出一组简单的递推公式或直关的求解步骤，并且也不能进行无限的列举。对于这类问题，一种有效的方法是“试”，通过对问题的分析，找出一个解决问题的线索，然后沿着这个线索逐步试探，若试探成功，就得到问题的解，若试探失败，就逐步回退，换其他路线再逐步试探。,一. 算法的基本概念 1.定义： 为解决某个特定问题而采取的确定且有限的步骤。,二. 算法的基本要素及描述,三.算法设计要求（评价算法标准）,四.算法设计的基本方法,1.1 数据结构的基本概念与算法,1.1.2 算法及算法分析,1.1.3 算法分析技术初步,1.评价算法标准 算法所占用计算机资源，即时间代价(算法所需要的时间）和空间代价（算法所需要的存储空间）。 算法所需要的时间包括： 程序运行时所需要的数据总量； 源程序进行编译所需要的时间； 计算机执行每条指令所需要的时间； 程序中指令重复执行的次数，而本条正是讨论算法中的重点内容 （常考）,1.1.3 算法分析技术初步,2.相关名词：,(1)问题规模：不同种类问题，问题规模含义不同。如矩阵运算取决于矩阵阶数，多项式运算取决于项数。,(2)算法运行时间：大致等于其所有语句执行时间的总和。,(3)语句频度：该语句在算法中重复执行的次数。,1.1.3 算法分析技术初步,3.算法的时间复杂度： 定义： 算法运行从开始到结束所需要的计算工作量.,说明: 同一个算法使用不同的语言实现,或者用不同的编译程序进行编译,或者在不同的计算机上运行,效率均不同,这表明使用绝对的时间单位衡量算法的效率是不合适的,撇开这些与计算机硬件、软件有关的因素,可以认为一个特定算法 “运行工作量”的大小,只依赖于问题的规模(通常用整数n表示),它是问题的规模函数,即 算法的工作量=f(n),1.1.3 算法分析技术初步,3.算法的时间复杂度： 定义：,T (n)=O( f (n) ),T (n)：算法中所有语句频度之和 n：问题规模。 T (n) 是n的某个函数。 O：数量级。 当问题规模趋向无穷时， T (n)的数量级称为时间复杂度。,2）表示：, x+=5; 单个语句的频度为1，则 程序段的时间复杂度为, for(i=0;in; i+) for(j=0 ;jn;j+) cij=i*j;,一个算法是由控制结构和原操作构成的，则算法时间取决于两者的的综合效果。为了便于比较同一个问题的不同算法，通常从算法中选取一种对于所研究的问题(或算法类型）来说是基本操作的原操作（其应是重复执行次数和算法的执行时间成正比的原操作,多数情况下它是最深层循环内的语句中的原操作）以该基本操作重复执行的次数作为算法的时间度量。,最优算法：随n的增大， T (n)增长较慢的算法。,T(n)=O(1),则：T(n)= O(n2),for(i=1;i=n;+i) for(j=1;j=n;+j) cij=0; for(k=1;k=n;+k) cij+=aik*bkj; ,由于是一个三重循环，每个循环从1到n，则总次数为: nnn=n3,时间复杂度为T(n)=O(n3),for(i=1;i=n;+i) +x; s+=x; 语句频度为：2n,其时间复杂度为：O(n), for(i=2;i=n;+i) for(j=2;j=i-1;+j) +x; aij=x;,语句频度为： 1+2+3+n-2 =(1+n-2) (n-2)/2 =(n-1)(n-2)/2 =n2-3n+2,时间复杂度为O(n2),1.1.3 算法的分析,3.算法的时间复杂度： 定义：,2）表示：,3）平均时间复杂度：所有可能的输入实例均以等概率出现的情况下，算法的期望运行时间。 4）最坏时间复杂度：最坏情况下算法的时间复杂度。,算法的时间复杂度不仅与问题规模有关,而且与输入数据有关,即输入数据所有的可能取值范围及输入各种数据或数据集的概率有关,以下六种计算算法时间的多项式是最常用的。其关系为： O(1)O(logn)O(n)O(nlogn) O(n2)O(n3),1.1.3 算法的分析,算法的时间复杂度例题,1.下面( )的时间复杂性最好,即执行时间最短。 A.O(n) B.O(logn) C. O(nlogn) D. O(n2),B,2.下面程序段的时间复杂性的量级为( )。 for(int i=0;im;i+) for(int j=0;jn;j+) aij=i*j; A.O(m2) B.O(n2) C. O(m*n) D. O(m+n),C,1.1.3 算法的分析,3.算法的时间复杂度：,4.算法的空间复杂度：,定义：算法运行从开始到结束所需的存储空间量,包括 固定部分和可变部分。,固定部分：此部分空间与所处理数据的大小和规模无关。通常用来保存本身所用的程序代码、常量、变量等。 可变部分：此部分空间与处理的数据的大小和规模有关，即执行算法时所需额外空间。,1.1 基本数据结构与算法思考题,研究数据结构的目的是什么？ 数据结构研究哪三方面的问题?关系如何? 在数据结构中数据项、数据元素及数据对象的关系？ 数据的逻辑结构分为哪两大类？各有何特点？ 数据的存储结构中的顺序存储与链式存储各有什么特点？ 什么是算法？有何特点？ 算法设计的基本要求？ 算法设计的方法？ 如何评价算法？ 什么是时间复杂度？时间复杂度与哪些因素有关？ 什么是空间复杂度？包括哪两部分？,1.1数据结构与算法补充习题讲解,1.数据处理的最小单位是_。 A. 数据 B. 数据元素 C. 数据项 D. 数据结构 2. 数据结构中，与所使用的计算机无关的是数据的_。 A. 存储结构 B. 物理结构 C. 逻辑结构 D. 物理和存储结构 3. 下面叙述正确的是_。 A. 算法的执行效率与数据的存储结构无关 B. 算法的空间复杂度是指算法程序中指令（或语句）的条数 C. 算法的有穷性是指算法必须能在执行有限个步骤之后终止 D. 以上三种描述都不对 4. 算法的时间复杂度是指_。 A. 执行算法程序所需要的时间 B. 算法程序的长度 C. 算法执行过程中所需要的基本运算次数 D. 算法程序中的指令条数 5. 算