数据结构丽水学院课件.ppt

1、数据结构丽水学院工学院数据结构丽水学院工学院v编程基础编程基础v计算机及相关专业考研考博课程计算机及相关专业考研考博课程v计算机等级考试课程计算机等级考试课程v程序员考试课程程序员考试课程为什么要学习数据结构为什么要学习数据结构数据结构丽水学院工学院课程学习指导课程学习指导 1.1.提前提前预习预习、认真听课、按时完成书面及上机、认真听课、按时完成书面及上机作业作业 2.2.注意先修课程的知识准备注意先修课程的知识准备离散数学、离散数学、C C语言语言 3.3.注意循序渐进：注意循序渐进：基本基本概念概念、基本、基本思想思想、基本、基本步骤步骤、算法算法设计设计 4.4.注意培养算法设计的能力

2、注意培养算法设计的能力理解所讲算法、对此多做理解所讲算法、对此多做思考思考：若问题要求不同，：若问题要求不同，应如何选择数据结构，设计有效的算法应如何选择数据结构，设计有效的算法课程特点：课程特点：内容抽象、概念性强、内容灵活、不易掌握内容抽象、概念性强、内容灵活、不易掌握数据结构 平时成绩平时成绩 :40%:40%考勤考勤20%20%、课堂表现、课堂表现10%10%、作业、作业20%20%、实验、实验50%50%课堂纪律课堂纪律无故迟到：无故迟到：无故旷课：无故旷课：-5-5上机：上机：玩游戏、上网聊天玩游戏、上网聊天-5-5 期末成绩期末成绩 :60%(:60%(闭卷笔试闭卷笔试)考核方式

3、考核方式丽水学院工学院数据结构教材和参考书教材和参考书教材：教材：数据结构数据结构(第第2 2版版)，严蔚敏，李冬梅等，人民邮电出版社，严蔚敏，李冬梅等，人民邮电出版社 参考书：参考书：数据结构数据结构，严蔚敏，清华大学出版社，严蔚敏，清华大学出版社 数据结构数据结构用面向对象方法与用面向对象方法与C+C+描述描述，殷人昆等，清华大，殷人昆等，清华大学出版社学出版社 算法艺术与信息学竞赛算法艺术与信息学竞赛，刘汝佳，黄亮清华大学出版社，刘汝佳，黄亮清华大学出版社丽水学院工学院数据结构第第1 1章绪论章绪论1.1.了解数据结构研究的主要内容了解数据结构研究的主要内容2.2.掌握数据结构中涉及的基

4、本概念掌握数据结构中涉及的基本概念3.3.掌握算法的时间、空间复杂度及其分析的掌握算法的时间、空间复杂度及其分析的简易方法简易方法 教学目标教学目标丽水学院工学院数据结构1.1 1.1 数据结构的研究内容数据结构的研究内容1.2 1.2 基本概念和术语基本概念和术语1.3 1.3 抽象数据类型的表示与实现抽象数据类型的表示与实现 1.4 1.4 算法与算法分析算法与算法分析教学内容教学内容丽水学院工学院数据结构丽水学院工学院&N.N.沃思（沃思（Niklaus Wirth)Niklaus Wirth)教授提出：教授提出：程序程序=算法算法+数据结构数据结构&电子计算机的主要用途：电子计算机的主

5、要用途：早期：早期：主要用于数值计算主要用于数值计算 后来：后来：处理逐渐扩大到非数值计算领域，能处理多种处理逐渐扩大到非数值计算领域，能处理多种复杂的具有一定结构关系的数据复杂的具有一定结构关系的数据1.1 1.1 数据结构的研究内容数据结构的研究内容数据结构书目自动检索系统登录号：书名：作者名：分类号：出版单位：出版时间：价格：书目卡片001高等数学樊映川S01002理论力学罗远祥L01003高等数学华罗庚S01004线性代数栾汝书S02书目文件按书名按作者名按分类号高等数学001，003理论力学002，.线性代数004，.樊映川001,华罗庚002,.栾汝书004,.L002,S001,

6、003,索引表线性表丽水学院工学院数据结构丽水学院工学院人机对奕问题树.数据结构/(root)binlibuseretcmathdsswyintaoxieStack.cppQueue.cppTree.cpp文件系统的系统结构图文件系统的系统结构图树丽水学院工学院数据结构丽水学院工学院 8:23 多叉路口交通灯管理问题CEDABABACADBABCBDDADBDCEAEBECED图顶点：顶点：一条通路连线：连线：不能同时通行染色：染色：有连线的两个顶点不能具有相同颜色数据结构丽水学院工学院&求解非数值计算的问题：求解非数值计算的问题：设计出合适的数据结构及相应的算法设计出合适的数据结构及相应的算

7、法 即：首先要考虑即：首先要考虑对相关的各种信息如何表示、组织对相关的各种信息如何表示、组织和存储？和存储？数据结构的研究内容为：数据结构的研究内容为：研究非数值计算的程序设计问题中计算机的研究非数值计算的程序设计问题中计算机的操作操作对象对象以及它们之间的以及它们之间的关系和操作关系和操作。数据结构北京林业大学信息学院 8:23 丽水学院工学院数据结构1 1、数据、数据（data)data)所有能输入到计算机中去的所有能输入到计算机中去的描述客观事物的符号描述客观事物的符号u数值性数据数值性数据u非数值性数据（多媒体信息处理）非数值性数据（多媒体信息处理）2 2、数据元素、数据元素（data

8、 elementdata element）数据的数据的基本单基本单位位，也称结点（，也称结点（nodenode）或记录（或记录（recordrecord）3 3、数据项、数据项（data itemdata item）有独立含义的数据有独立含义的数据最最小单位小单位，也称域，也称域(field)field)三者之间的关系：数据三者之间的关系：数据 数据元素数据元素 数据数据项项例：学生表例：学生表 个人记录个人记录 学号、姓名学号、姓名1.2 1.2 基本概念和术语基本概念和术语丽水学院工学院数据结构丽水学院工学院u整数数据对象整数数据对象 N=0,N=0,1,1,2,2,u学生数据对象学生数据

9、对象 学生记录的集合学生记录的集合4 4、数据对象数据对象(Data Object)(Data Object)：相同特性相同特性数据元素的集合，是数据的一个子集数据结构5 5、数据结构（、数据结构（Data StructureData Structure）是相互之间存是相互之间存在一种或多种特定关系的数据元素的集合。在一种或多种特定关系的数据元素的集合。数据结构是带数据结构是带“结构结构”的数据元素的集合，的数据元素的集合，“结构结构”就是指数据元素之间存在的关系。就是指数据元素之间存在的关系。丽水学院工学院数据结构&数据结构的两个层次：数据结构的两个层次：&逻辑结构逻辑结构-数据元素间抽象化

10、的相互关系，与数据的存储无关，独数据元素间抽象化的相互关系，与数据的存储无关，独立于计算机，它是从具体问题抽象出来的数学模型。立于计算机，它是从具体问题抽象出来的数学模型。&存储结构（物理结构）存储结构（物理结构）-数据元素及其关系在计算机存储器中的存储方式。数据元素及其关系在计算机存储器中的存储方式。丽水学院工学院数据结构划分方法一划分方法一（1 1）线性结构）线性结构-有且仅有一个开始和一个终端结点，并且所有有且仅有一个开始和一个终端结点，并且所有结点都最多只有一个直接前趋和一个后继。结点都最多只有一个直接前趋和一个后继。例如：线性表、栈、队列、串例如：线性表、栈、队列、串（2 2）非线性

11、结构）非线性结构-一个结点可能有多个直接前趋和直接后继。一个结点可能有多个直接前趋和直接后继。例如：树、图例如：树、图逻辑结构逻辑结构丽水学院工学院数据结构线性结构线性结构一个对一个，如线性表、栈、队列一个对一个，如线性表、栈、队列树形结构树形结构一个对多个，如树一个对多个，如树集合集合数据元素间除数据元素间除“同属于一个集合同属于一个集合”外，无其它关系外，无其它关系图形结构图形结构多个对多个，如图多个对多个，如图逻辑结构逻辑结构划分方法二划分方法二丽水学院工学院数据结构存储结构分为：存储结构分为：顺序顺序存储结构存储结构借助元素在存储器中的借助元素在存储器中的相对位置相对位置来表示来表示

12、数据元素间的逻辑关系数据元素间的逻辑关系链式链式存储结构存储结构借助指示元素存储地址的借助指示元素存储地址的指针指针表示数据表示数据 元素间的逻辑关系元素间的逻辑关系存储结构存储结构丽水学院工学院数据结构元素元素n n.元素元素i i.元素元素2 2元素元素1 1LoLo+mLo+(i-1)*mLo+（n-1)*m存储地址存储地址存储内容存储内容Loc(元素元素i)=Lo+（i-1)*m顺序存储顺序存储丽水学院工学院数据结构1536元素元素2 21400元素元素1 11346元素元素3 3 元素元素4 41345h存储地址存储地址 存储内容存储内容 指针指针 1345 1345 元素元素1 1

13、 14001400 1346 1346 元素元素4 4 .14001400 元素元素2 2 1536 1536 .1536 1536 元素元素3 3 1346 1346 链式存储链式存储 h丽水学院工学院数据结构丽水学院工学院 逻辑结构和存储结构都相同逻辑结构和存储结构都相同,但运算不同但运算不同,则则数据结构不同。例如数据结构不同。例如,栈与队列栈与队列 对于一种数据结构对于一种数据结构,常见的运算常见的运算插入插入删除删除修改修改查找查找排序排序数据的运算数据的运算数据结构丽水学院工学院n定义：定义：在一种程序设计语言中，变量所具有在一种程序设计语言中，变量所具有的数据种类的数据种类数据类

14、型数据类型FORTRANFORTRAN语言：语言：整型、实型、和复数型整型、实型、和复数型 C C语言语言：基本数据类型：基本数据类型：char int float double voidchar int float double void构造数据类型：构造数据类型：数组、结构体、共用体、文件数组、结构体、共用体、文件 数据类型是一组性质相同的值的集合数据类型是一组性质相同的值的集合,以及以及定义于这个集合上的一组运算的总称定义于这个集合上的一组运算的总称数据结构丽水学院工学院抽象数据类型(ADTs:Abstract Data Types)u更高层次的数据抽象更高层次的数据抽象u由用户定义，用

15、以表示应用问题的由用户定义，用以表示应用问题的数据模型数据模型u由由基本的数据类型基本的数据类型组成组成,并包括并包括一组相关的一组相关的操作操作抽象数据类型抽象数据类型数据结构抽象数据类型抽象数据类型可以用以下的三元组来表示：可以用以下的三元组来表示：ADT=ADT=（D D，S S，P P）数据对象数据对象 D D上的关系集上的关系集 D D上的操作集上的操作集 ADTADT抽象数据类型名抽象数据类型名 数据数据对象对象：数据数据关系关系：基本基本操作操作 ：ADT ADT抽象数据类型名抽象数据类型名ADTADT常用常用定义定义格式格式丽水学院工学院数据结构1.3 1.3 抽象数据类型的表

16、示与实现抽象数据类型的表示与实现抽象数据类型可以通过抽象数据类型可以通过固有的固有的数据类型（如整数据类型（如整型、实型、字符型等）来表示和实现。型、实型、字符型等）来表示和实现。它有些类似它有些类似C C语言中的语言中的结构（结构（struct)struct)类型类型，但增加，但增加了相关的了相关的操作操作教材中用的是教材中用的是类类C C语言（介于伪码和语言（介于伪码和C C语言之间）语言之间）作为描述工具作为描述工具但上机时要用具体语言实现，如但上机时要用具体语言实现，如C C或或C+C+等等丽水学院工学院数据结构丽水学院工学院(1)(1)预定义常量及类型预定义常量及类型/函数结果状态代

17、码函数结果状态代码#define OK 1#define OK 1#define ERROR 0#define ERROR 0#define OVERFLOW-2#define OVERFLOW-2 /Status/Status是函数返回值类型，其值是函数结果是函数返回值类型，其值是函数结果状态代码。状态代码。typedef typedef int int Status;Status;数据结构丽水学院工学院(2)(2)数据元素被约定为数据元素被约定为ElemType ElemType 类型，类型，用用户需要根据具体情况，自行定义该数据类型。户需要根据具体情况，自行定义该数据类型。(3)(3)算

18、法描述为以下的函数形式：算法描述为以下的函数形式：函数类型函数类型 函数名（函数参数表）函数名（函数参数表）语句序列；语句序列；数据结构（4 4）内存的动态分配与释放）内存的动态分配与释放使用使用newnew和和deletedelete动态分配和释放内存空间动态分配和释放内存空间分配空间指针变量分配空间指针变量=new=new数据类型数据类型;释放空间释放空间deletedelete指针变量指针变量;（5 5）赋值语句）赋值语句（6 6）选择语句）选择语句（7 7）循环语句）循环语句丽水学院工学院数据结构（8 8）使用的结束语句形式有：）使用的结束语句形式有：函数结束语句函数结束语句 retu

19、rn return 循环结束语句循环结束语句 break;break;异常结束语句异常结束语句 exitexit（异常代码）；（异常代码）；丽水学院工学院数据结构（9 9）输入输出语句形式有：）输入输出语句形式有：输入语句输入语句 cin (scanf()cin (scanf()输出语句输出语句 cout(printf()cout(printf()（1010）扩展函数有：）扩展函数有：求最大值求最大值 maxmax求最小值求最小值 minmin丽水学院工学院数据结构丽水学院工学院1.4 1.4 算法和算法分析算法和算法分析数据结构丽水学院工学院数据结构丽水学院工学院数据结构丽水学院工学院 算法

20、效率：用依据该算法编制的程序在计算机上算法效率：用依据该算法编制的程序在计算机上执行所消耗的时间来度量执行所消耗的时间来度量事后统计事后统计事前分析估计事前分析估计数据结构1.1.事后统计：事后统计：利用计算机内的计时功能，不同算法利用计算机内的计时功能，不同算法的程序可以用一组或多组相同的统计数据区分的程序可以用一组或多组相同的统计数据区分 缺点：缺点：必须先运行依据算法编制的程序必须先运行依据算法编制的程序所得时间统计量依赖于硬件、软件等环境因素，掩盖所得时间统计量依赖于硬件、软件等环境因素，掩盖算法本身的优劣算法本身的优劣 丽水学院工学院数据结构2.2.事前分析估计：事前分析估计：一个高

21、级语言程序在计算机上运行所消耗的时间取一个高级语言程序在计算机上运行所消耗的时间取决于：决于：依据的算法选用何种策略依据的算法选用何种策略 问题的规模问题的规模 程序语言程序语言 编译程序产生机器代码质量编译程序产生机器代码质量 机器执行指令速度机器执行指令速度 同一个算法用不同的语言、不同的编译程序、在不同同一个算法用不同的语言、不同的编译程序、在不同的计算机上运行，效率均不同，的计算机上运行，效率均不同，使用使用绝对时绝对时间单位间单位衡量算法效率不合适衡量算法效率不合适丽水学院工学院数据结构算法中算法中基本语句重复执行的次数基本语句重复执行的次数是是问题规模问题规模n n的某个函数的某个

22、函数f(n),f(n),算法的时间量度记作：算法的时间量度记作：T(n)=O(f(n)T(n)=O(f(n)时间复杂度的渐进表示法时间复杂度的渐进表示法数学符号数学符号“O O”的定义为：的定义为：若若T T(n n)和和f f(n n)是定义在正整数集是定义在正整数集合上的两个函数，则合上的两个函数，则T T(n n)=O()=O(f f(n n)表示存在正的常数表示存在正的常数C C和和n n0 0，使得当，使得当n nn n0 0时都满足时都满足0 0T T(n n)C Cf f(n n)。表示随着表示随着n n的增大，算法执行的时间的增长率和的增大，算法执行的时间的增长率和f(n)f(

23、n)的增长率相同，称的增长率相同，称渐近时间复杂度渐近时间复杂度。n n越大算法的执行时间越长越大算法的执行时间越长u排序：排序：n n为记录数为记录数u矩阵：矩阵：n n为矩阵的阶数为矩阵的阶数u多项式：多项式：n n为多项式的项数为多项式的项数u集合：集合：n n为元素个数为元素个数u树：树：n n为树的结点个数为树的结点个数u图：图：n n为图的顶点数或边数为图的顶点数或边数u算法中重复执算法中重复执行次数和算法行次数和算法的执行时间成的执行时间成正比的语句正比的语句u对算法运行时对算法运行时间的贡献最大间的贡献最大丽水学院工学院数据结构n*n阶矩阵加法：阶矩阵加法：for(i=0;i

24、n;i+)for(j=0;j n;j+)cij=aij+bij;语句的频度语句的频度（Frequency Count):重复执行的次数：重复执行的次数：n*n;T(n)=O(n 2)即：矩阵加法的运算量和问题的规模即：矩阵加法的运算量和问题的规模n的平方是同一个量级的平方是同一个量级丽水学院工学院数据结构x=0;y=0;for(int k=0;k n;k+)x+;for(int i=0;i n;i+)for(int j=0;j n;j+)y+;找出找出语句频度最大语句频度最大的那条语句作为的那条语句作为基本语句基本语句计算计算基本语句基本语句的频度得到问题规模的频度得到问题规模n n的某个函数

25、的某个函数f f(n n)取其数量级用符号取其数量级用符号“O O”表示表示分析算法时间复杂度的基本方法分析算法时间复杂度的基本方法f(n)=n2T(n)=O(n2)丽水学院工学院数据结构 void exam(float x ,int m,int n)float sum ;for(int i=0;i m;i+)sumi=0.0;for(int j=0;j n;j+)sumi+=xij;for(i=0;i m;i+)cout i “:”sum i endl;时间复杂度是由时间复杂度是由嵌套最深层嵌套最深层语句的频度决定的语句的频度决定的f(n)=m*nT(n)=O(m*n)丽水学院工学院数据结构

26、例1：NN矩阵相乘for(i=1;i=n;i+)for(j=1;j=n;j+)cij=0;for(k=1;k=n;k+)cij=cij+aik*bkj;算法中的基本操作语句为算法中的基本操作语句为cij=cij+aikcij=cij+aik*bkj;bkj;233111111()1()nnnnnnijkijiT nnnno n 3T nO n丽水学院工学院数据结构例例2：for(i=1;i=n;i+)for(j=1;j=i;j+)for(k=1;k=j;k+)x=x+1;niniijniijjkiij1111112)1(1211121(1)(21)(1)262(1)(2)6nniiiin nn

27、n nn nn语句频度语句频度=定理定理1.1若若f(n)=amnm+am-1nm-1+a1n+a0是是m次多项式，则次多项式，则T(n)=O(nm)。忽略所有忽略所有低次幂项和低次幂项和最高次幂系数最高次幂系数，体现，体现出增长率的含义出增长率的含义丽水学院工学院数据结构例例3 3：分析以下程序段的时间复杂度：分析以下程序段的时间复杂度i=1;while(i=n)i=i*2;nnf)(2即即f(n)log2n，取最大值取最大值f(n)=log2n所以该程序段的时间复杂度所以该程序段的时间复杂度T(n)=T(n)=O(logO(log2 2n)n)丽水学院工学院数据结构例例4 4：顺序查找，在

28、数组：顺序查找，在数组aiai中查找值等于中查找值等于e e的元素的元素，返回其所在位置。，返回其所在位置。for(i=0;i n;i+)for(i=0;i n;i+)if(ai=e)return i+1;if(ai=e)return i+1;return 0;return 0;有的情况下，算法中基本操作重复执行的次数还有的情况下，算法中基本操作重复执行的次数还随问题的随问题的输入数据集输入数据集不同而不同不同而不同最好情况：最好情况：1 1次次 最坏情况：最坏情况：n n平均时间复杂度为平均时间复杂度为:O(n):O(n)丽水学院工学院数据结构复杂度高复杂度高复杂度低复杂度低当当n n取得很

29、大时，指数时间取得很大时，指数时间算法和多项式时间算法在算法和多项式时间算法在所需时间上非常悬殊所需时间上非常悬殊丽水学院工学院数据结构 空间复杂度空间复杂度:算法所需存储空间的度量，记作算法所需存储空间的度量，记作:S(n)=O(f(n)S(n)=O(f(n)其中其中n n为问题的规模为问题的规模(或大小或大小)n算法要占据的空间算法要占据的空间算法本身要占据的空间，输入算法本身要占据的空间，输入/输出，指令，输出，指令，常数，变量等常数，变量等算法要使用的算法要使用的辅助空间辅助空间渐进空间复杂度渐进空间复杂度丽水学院工学院数据结构【算法算法1 1】for(i=0;in/2;i+)for(

30、i=0;in/2;i+)t t=ai;=ai;ai=an-i-1;ai=an-i-1;an-i-1=an-i-1=t t;【算法算法2 2】for(i=0;in;i+)for(i=0;in;i+)bi=bi=an-i-1;an-i-1;for(i=0;in;i+)for(i=0;in;i+)ai=ai=bibi;例例5 5：将一维数组：将一维数组a a中的中的n n个数逆序存放到原数组中。个数逆序存放到原数组中。S(n)=O(n)S(n)=O(n)S(n)=O(1)S(n)=O(1)原地工作原地工作丽水学院工学院数据结构 1 1、数据、数据元素、数据项、数据结构等基、数据、数据元素、数据项、数据结构等基本概念本概念 2 2、对数据结构的两个层次的理解对数据结构的两个层次的理解 逻辑结构逻辑结构 存储结构存储结构 3 3、抽象数据类型的表示方法、抽象数据类型的表示方法 4 4、算法、算法的时间复杂度及其分析的简易算法、算法的时间复杂度及其分析的简易方法方法小结小结丽水学院工学院