《数据结构介绍》PPT课件.ppt

1,数 据 结 构 (Data Structure),任课教师： 赵少卡 E-MAIL: ,数计系2012级计算机科学与技术、网络工程专业,2,课程性质：专业核心基础课 教材: 严蔚敏、吴伟民. 数据结构 (C语言版).北京:清华大学出版社,2011. 1981年初稿，使用面最广 周学时：4（理论授课）+ 2（上机实践） 考核：平时成绩（作业、考勤）20% +期中成绩20% +期末成绩60%,3,保持课堂安静，头脑清醒，思维活跃 课后及时复习巩固 认真、独立、按时完成并提交作业 多思考多动手，重视上机实践,课程要求,4,数据结构,基础数据结构,应用数据结构,非线性结构,线性结构,线 性 表,栈,队 列,串,数 组,广 义 表,树,二 叉 树,图,查 找,内 部 排 序,外 部 排 序,文 件,动 态 存 储 管 理,本课程的内容框架,5,讲授篇章,第1章 绪论,第7章 图,第2章 线性表,第9章 查找,第3章 栈和队列,第6章 树和二叉树,第10章 内部排序,6,第 1 章 绪 论,问题求解(Problem Solving)：,7,计算机求解问题的分类,数值计算(科学运算):解方程(组)、 函数求值、 概率统计等。 应用：天气预报(环流模式方程)、结构静力分析（线性代数方程组）、水库大坝的应力计算、预报人口增长等。 非数值计算：字符、表格、图像、声音等。,8,基本概念和术语,数据：计算机程序处理的符号的总称，包含整型、实型、布尔型、图象、字符、声音等一切可以输入到计算机中的符号集合。 数据元素：数据的基本单位（数据中的一个“个体”），通常作为一个整体进行处理。 数据项：数据的具有意义的不可分割的最小单位。一个数据元素可以由若干个数据项构成。,9,数据对象：性质相同的数据元素的集合。 如：整数数据对象 N = 0, 1, 2, （无限集） 字母字符数据对象C= A, B, C, Z （有限集） 因此： 数据元素是数据的一个个体； 数据对象是数据的一个子集。,10,例：a1,a2,a3,a4,a5,a6存在次序为： （1）| i=1，2，3，4，5 （2）Row=, , Col =, , 所谓结构就是数据元素之间的关系，即描述数据元素之间的运算与运算规则。 数据结构：相互间存在一种或多种特定关系的数据元素的集合。,11,数据的逻辑结构,数据的存储结构 （物理结构、映像）,数据的运算：查找、排序、插入、删除、修改等,线性结构,非线性结构,顺序存储,链式存储,线性表,栈,队列,树形结构,图形结构,数据结构的三个方面：,集合结构,串,索引存储,散列存储,12,主要逻辑结构举例 集合：其中的数据元素之间除了“属于同一个集合”的关系以外，别无其他关系。 线性结构：其中的数据元素之间存在一对一的关系。 树型结构：其中的数据元素之间存在一对多的关系。 图状结构（网状结构）：其中的数据元素之间存在多对多的关系。,13,例1 书目自动检索系统,书目文件,14,例2 人机对弈问题,15,例3 多叉路口交通灯管理问题,有连线的节点用不同的颜色标记, 表示不能同时通行。 要求使用的颜色数尽可能少, 以使减少等待时间。,16,逻辑结构与存储结构,逻辑结构: 数据元素间的逻辑关系，与数据元素的相对位置无关。 存储结构: 逻辑结构在计算机存储器中的表示，如：,顺序存储结构借助元素在存储器中的相对位置来表示 数据元素间的逻辑关系 链式存储结构借助指示元素存储地址的指针表示数据 元素间的逻辑关系,17,18,1536,元素2,1400,元素1,1346,元素3,元素4,1345,h,链式存储结构,h,19,数据类型与抽象数据类型,数据类型（Data Type）：值的集合以及定义在这个集合上的一组操作。 数据类型分类： （1）原子类型：每个数据都无法再分割。（整型、实型、字符型等） （2）结构类型：结构类型中的数据可以分解为若干原子类型或结构类型数据。（数组、记录、结构体、联合体、串、文件等）,20,抽象数据类型(Abstract Data Type ，ADT):数学模型以及定义在该模型上的一组操作，与其在计算机中的表示和实现无关。 例如：矩阵 + 求转置、加、乘、求逆、求特征值等操作构成一个矩阵的抽象数据类型。 ADT 可用三元组表示：（D,R,P） D 数据对象 R D上的关系的有限集 P 对D的基本操作集,21,抽象数据类型的定义,ADT抽象数据类型名 数据对象：数据对象的定义 数据关系：数据关系的定义 基本操作： 基本操作名（参数表） 初始条件：初始条件描述 操作结果：操作结果描述 ADT抽象数据类型名 在定义抽象数据类型中的数据部分和操作部分时，要求只定义数据的逻辑结构和操作说明，不考虑数据的存储结构和操作的具体实现。,22,基本操作有两种参数：赋值参数只为操作提供输入值；引用参数以&打头，除可提供输入值外，还将返回操作结果。 “初始条件”描述了操作执行之前数据结构和参数应满足的条件，若不满足，则操作失败，并返回相应出错信息。 “操作结果”说明了操作正常完成之后，数据结构的变化状况和应返回的结果。若初始条件为空，则省略之。,23,抽象数据类型三元组的定义,ADT Triplet 数据对象：D = e1,e2,e3 | e1,e2,e3Elemset(定义了关系运算的某个集合) 数据关系：R1 = e1,e2，e2,e3 基本操作P： InitTriplet(&T,v1,v2,v3) 初始条件: 操作结果: 构造三元组T,元素e1,e2和e3分别被赋予参数v1,v2和v3的值。 DestroyTriplet(&T) 初始条件: 三元组T已经存在。 操作结果: 销毁三元组T。 Get(T,i,&e) 初始条件: 三元组T已经存在,1=i=3。 操作结果: 用e返回三元组T的第i个元素。,24,Put( 否则返回FALSE。 Max(T,&e) 初始条件: 三元组T已经存在。 操作结果: 用e返回三元组T的最大值。 Min(T,&e) 初始条件: 三元组T已经存在。 操作结果: 用e返回三元组T的最小值。 ADT Triplet,25,又例：抽象数据类型圆（Circle）的定义。 ADT Circle 数据对象：D=r | r实型数集合 数据关系：R= 基本操作P： InitCircle(&r,c) 初始条件：c为圆的半径（c0） 操作结果：构造一个圆r，使其半径为c DestroyCircle(&r) 初始条件：圆r已存在 操作结果：撤消圆r（使其半径为0） AreaCircle(r，&A) 初始条件：圆r已存在 操作结果：用A返回圆的面积 CircumferenceCircle(r，&C) 初始条件：圆r已存在 操作结果：用C返回圆的周长 ADT Circle,26,抽象数据类型的表示与实现,类C语言（对C语言作了扩充和修改）表示。 如：预定义常量和类型 define TRUE 1 define FALSE 0 define OK 1 define ERROR 0 define INFEASIBLE -1 define OVERFLOW -2 typedef int Status；,27,三元组基本操作实现-举例,Status InitTriplet(Triplet /InitTriplet,28,三元组基本操作实现-举例,Status Get(Triple T, int i, Elemtype /Get,29,#include void fa(int a) a+; printf(“在函数fa中：a=%dn“,a); void fb(int *a) /* a为指针类型，在函数中改变*a，改变后的值将带回主调函数 */ (*a)+; printf(“在函数fb中：*a=%dn“,*a); void main( ) int n=1; printf(“调用函数fa之前：n=%dn“,n); fa(n); printf(“调用函数fa之后,调用函数fb之前：n=%dn“,n); fb( ,30,抽象数据类型（ADT）明确地把数据模型与该模型上的运算紧密地联系起来。 从使用的角度看，ADT隐藏了所有使用者不关心的实现细节，对用户透明（提供接口），使程序模块的实现与使用分离，从而能够独立地考虑模块的外部界面、内部算法和数据结构的实现，做到了信息隐蔽与数据封装。,Abstract Data Type (ADT),user1,user2,usern,.,实现1,实现2,实现3,31,算法与程序,算法（Algorithm）是对特定问题求解步骤的一种描述，是指令的有限序列，其中每一条指令表示一个或多个操作。算法的描述工具有： （1） 自然语言 （2） 程序设计语言 （3） 流程图（框图） （4） 伪码语言：是一种包括高级程序设计语言的三种基本结构（顺序、选择、循环）和自然语言成分的“面向读者”的语言。 程序是用某种程序设计语言对算法的具体实现。如果一个算法采用机器可执行的语言来书写，那么它就是一个程序。,32,算法的5个特征,(1)有穷性：在有限步(或有限时间)之后算法终止。 例：void suanfa1( ) int i,s=0； for (i=0；i=0；i+) s+； (2)确定性：无二义性。 例： x=5；y=10； z=x+y； printf(“%d,%d,%d“ ,x,y,z)； x+y 解释为：x + (+y)？还是 (x+)+ y？,33,(3)可行性(正确性)：可以在计算机上实现。 for( i=1,s=0；i1000000000000；+i) s+；？ (4)输入：有0个（算法本身确定了初始条件） 或多个输入量。 (5)输出：至少有一个输出量。,34,算法设计要求 如何设计一个“好”的算法,(1)正确性（4个层次） a.无语法错误； b.对n组输入产生正确结果； c.对特殊输入产生正确结果； d.对所有输入产生正确结果。 (2)可读性：“算法主要是为了人的阅读与交流”。 (3)健壮性（鲁棒性） scanf(“%d“,&x)； y/=x；？ (4)高效与低存储量（如何度量？能使用“绝对时间单位”衡量算法效率吗？） 不能，因为同一个算法用不同的语言、不同的编译程序、在不同的计算机上运行，效率均不同。,35,算法效率的度量(主要是度量程序的执行时间)通常有两种方法： (1) 事后统计法（缺点：a.必须执行程序，b.软硬件环境因素易掩盖算法本质）； (2) 事前分析估算法（根据与算法相关的因素估算算法的执行工作量）。,36,算法效率的度量时间复杂度,算法的时间复杂度是指：算法(或程序)中基本操作(或语句)重复执行的次数的总和。 设n为求解的问题的规模，基本操作(或语句)执行次数总和称为语句频度，记作f(n)。 算法的时间量度T(n)是随算法计算量n而增长的趋势(极限) 。如果存在正的常数M和n0，当问题的规模nn0后，T(n)Mf(n)，那么该算法的时间复杂度 T(n) =O(f(n),表示随着问题规模n的 增大，算法运行所需时间 的增长率与f(n)的增长率 相同（在渐进意义下的阶数）。,37,例1： int s； scanf(“%d“, 时间复杂度也为O(1)。,38,例2： void sum(int a,int n) int s=0,i； / 1次 for(i=0；in；i+) / n次(严格为2*(n+1)次） s=s+ai； / n次 printf(“%d“,s)； / 1次 其中：语句频度为：f(n)=1+n+n+1 时间复杂度为：T(n)=O(f(n)=O(2n+2)=O(n) O(n)称成为线性阶/线性数量级 定理：若A(n)=amnm +a m-1nm-1 +a1n+a0是一个m次多项式， 则A(n)=O(nm)。,39,例3： 1. void sum (int m,int n) 2. int i,j,s=0； / 1次 3. for(i=1；i=m；i+) / m次 4. for(j=1；j=n；j+) / m*n次 5. s+； / m*n次 6. printf(“%d“,s)； / m次 7. 8. 其中: f(m,n)=1+m+2*m*n+m=2mn+2m+1 当m=n时，f(n)=2n2+2n+1 T(n)=O(f(n)=O(2n2+2n+1)=O(n2) O(n2 ) 称成为平方阶/平方数量级,40,1. void sum(int n) 2. int i,j,s=0； / 1次 3. for(i=1；i=n；i+) / n次 4. for(j=1；j=i；j+) / ?次 5. s+； / ?次 6. printf(“%d“,s)； / n次 7. 8. 其中：第4行的次数为 1+2+.+n=n(1+n)/2 第5行的次数为 1+2+.+n=n(1+n)/2 f(n)=1+n+n(n+1)+n=n2+3n+1 T(n)=O(f(n)=O(n2),例4：,41,例5：1. void bubble1(int a,int n) 2. int i,j,temp； 3. for(i=0；iaj+1) / n(n-1)/2次 6. temp=aj； / 0 或n(n-1)/2次 7. aj=aj+1； / 0 或n(n-1)/2次 8. aj+1=temp； / 0 或n(n-1)/2次 9. 10. for(i=0；in；i+) / n 次 11. printf(“%d“,ai)； / n 次 12. 算法中基本操作重复执行的次数随问题的输入数据集不同而不同： 在最好情况下，f(n)= n-1+n(n-1)+2n=n2+2n-1 在最坏情况下，f(n)=5n2/2+n/2-1 T最好(n)= T最坏(n) = O(n2) 算法时间复杂度： T(n)= T最坏(n)= O(n2)（没有特殊说明，一般指最坏时间复杂度）,42,一般情况： 原序列：10 3 7 8 5 2 1 4 9 6 第1趟： 3 7 8 5 2 1 4 9 6 10 第2趟： 3 7 5 2 1 4 8 6 9 10 第3趟： 3 5 2 1 4 7 6 8 9 10 第4趟： 3 2 1 4 5 6 7 8 9 10 第5趟： 2 1 3 4 5 6 7 8 9 10 第6趟： 1 2 3 4 5 6 7 8 9 10 第7趟： 1 2 3 4 5 6 7 8 9 10 第8趟： 2 1 3 4 5 6 7 8 9 10 第9趟： 1 2 3 4 5 6 7 8 9 10,43,1. void bubble2(int a,int n) 2. for(i=n-1,change=TRUE；i=1 & change；i-) /1 或n-1 3. change=FALSE； /1 或n-1 4. for(j=0；jaj+1) /n-1或n*(n-1)/2 6. aj aj+1； /0或n*(n-1)/2 7. change=TRUE； /0或n*(n-1)/2 8. 9. 10. 在最好情况下： T最好(n)=O(f最好(n)= O(n) 在最坏情况下： T最坏(n)=O(f最坏(n)= O(n2) 算法时间复杂度： T(n)= T最坏(n)= O(n2) 课后思考：选择排序的时间复杂度。,44,小结：T(n) 的计算方法,（1）找出基本操作(若存在循环，一般取最深层循环内的语句所描述的操作)，确定问题规模n； （2）计算出关于n的语句频度函数f(n)； （3）使用“掐头去尾占高枝儿”等方法得出T(n)。,45,思考： int SequenceSearch(int a ,int n,int key) for(int i=0;in;i+) if(ai=key) return i； return -1； 最好情况：O(1) 最坏情况：O(n) 平均时间复杂度为:O(n),46,例 6 ： fact(int