《数据结构介绍》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 1define FALSE 0define OK 1define ERROR 0define INFEASIBLE-1define 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；+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-13.change=FALSE；/1 或n-14.for(j=0；jaj+1)/n-1或n*(n-1)/26.aj aj+1；/0或n*(n-1)/27.change=TRUE；/0或n*(n-1)/28.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 n)if(n1）,T(n)=O(1)+T(n-1)=2*O(1)+T(n-2)=(n-1)*O(1)+T(1)=n*O(1)=O(n),T(n)=,利用递归跟踪或递推方程,47,例 7：设存在递归关系:0（n=1）T(n-1)+n-1（n1）分析其时间复杂度。T(n)=T(n-1)+(n-1)=T(n-2)+(n-2)+(n-1)=T(n-3)+(n-3)+(n-2)+(n-1)=(T(1)+1)+2+(n-1)=0+1+2+(n-1)=n(n-1)/2=O(n2),T(n)=,48,例 8：i=1;while(i=n)i*=3;设while语句执行f(n)次则3f(n)n，即f(n)log3n那么利用定义，T(n)Mf(n)Mlog3n=O(logn),49,增长率（阶）（从大到小）,nn n!cn(c1)：2n,3nnc(c1)：n3,n2nlog2 nnr(0r1.0)log2 nc,O(1)O(logn)O(n)O(nloglogn)O(nlogn)O(n2)O(n3)O(2n)O(n!)O(nn),50,常用的时间复杂度频率计数,51,算法效率的度量空间复杂度,一般情况下，算法的复杂度指的是算法的时间复杂度。算法的空间复杂度：S(n)=O(f(n)其中n为问题的规模(或大小)。表示随着问题规模n的增大，算法运行所需存储量的增长率与f(n)的增长率相同。若所需额外空间相对于输入数据量来说是常数，则称此算法为原地工作（就地工作）。若所需存储量依赖于特定的输入，则通常按最坏情况考虑。有时候，可以用空间换时间，如判断给定的一系列年份是否是闰年（两种做法）。,