《数据结构 第1章 绪论.ppt》由会员分享，可在线阅读，更多相关《数据结构 第1章 绪论.ppt（88页珍藏版）》请在三一办公上搜索。
1、数据结构 与 算法,第一讲：绪论,我是谁?,14/11/2023,2,郑炜 老师现在：厦门大学计算机系讲师之前：清华大学计算机系本科硕士-英国曼彻斯特大学博士,欢迎提问；欢迎提建议。,学好数据结构与算法的理由,14/11/2023,3,数据结构很枯燥，不好学下列情况中，你属于哪一种？我想拿学位核心基础专业课程我想考研必考科目我想当优秀的程序员内功心法我喜欢计算机科学向你致敬，请感受编程之美打酱油的,如果有一天，你真的在写程序,比如，有一个客服电话系统需要开发。你负责编写客户排队模块的代码如果你用数据库设计一张客户排队表你的数据结构白学了。杀鸡焉用宰牛刀？如果你直接用数组去实现一张客户排队表你的
2、数据结构白学了。溢出怎么办？新增和删除怎么办？所以学了这门课你应该知道在这种情况下用哪种数据结构合适。我们所学的数据结构在编程语言的开发工具包里好像都实现了，还有必要上这门课吗？是的，授人以鱼不如授人以渔。,14/11/2023,4,本课程的主要内容,数据结构的基本概念线性表栈和队列串数组树图查找排序,14/11/2023,5,学习方法,认真听讲，积极互动阅读/分析大量例程序勤于思考，善于联系身边的例子独立完成各算法的程序设计和调试训练手写伪代码的能力,14/11/2023,6,今天的任务,数据结构研究的主要内容,14/11/2023,7,数据结构中涉及的基本概念,算法的概念、描述方法以及评价
3、标准,学习要点,了解数据结构有关概念的含义，特别是数据的逻辑结构和存储结构之间的关系；（重点）熟悉类C语言的书写规范；了解计算算法时间复杂度的方法。（难点）,14/11/2023,8,数据结构是什么,14/11/2023,9,数据结构的起源和发展,从计算器到计算机从“不可编程”到“可编程”从“纯数值计算”到“非数值计算”数据结构问题起源于程序设计程序设计主要关心数据如何表示：数据的组织和存储数据如何处理：求解问题的步骤非数值计算涉及的信息如何表示、组织、存储和处理？1968年，数据结构课程元年。（D.E.Kruth）70年代后，大型程序软件的开发使数据结构受到更多重视关于数据结构的研究并不曾结
4、束GIS，空间数据库，多维数据结构,14/11/2023,10,基本概念和术语,【数据】是对信息的一种符号表示。是可以输入计算机中，能被计算机识别处理和输出的一切符号集合。【数据元素】是数据的基本单位，在计算机中通常作为一个整体进行考虑和处理。也称为记录。【数据项】一个数据元素可由若干个数据项组成。是数据不可分割的最小单位。【数据对象】是性质相同的数据元素的集合。是数据的一个子集。,14/11/2023,11,【数据结构】相互之间存在一种或多种特定关系的数据元素的集合,从不同的视角看数据结构,14/11/2023,12,数据结构,人的思考：如何组织,计算机：如何存储,逻辑结构,存储（物理）结构
5、,逻辑结构,14/11/2023,13,数据元素之间的逻辑关系。即从逻辑关系上描述数据，与数据的存储无关，是独立于计算机的。,逻辑结构的例子（1）,学籍管理问题信息的组织？各表项之间的关系？通常进行的操作？,14/11/2023,14,逻辑结构的例子（2）,人机对弈问题树结构各棋盘格局之间是什么关系？通常进行的操作？,14/11/2023,15,逻辑结构的例子（3）,教学计划安排图结构课程之间是什么关系？通常进行的操作？,14/11/2023,16,四种基本逻辑结构,14/11/2023,17,【集合】数据元素间除了“同属于一个集合”外，无其他关系。,【线性结构】1对1的关系比如线性表、栈、队
6、列。,【树形结构】1对多的关系比如树。,【图形结构】多对多的关系比如图。,数据（逻辑）结构的形式定义,数据结构是一个二元组 Data_Structure=(D,R)其中:D 是数据元素的有限集，R 是 D 上关系的有限集。例如:一维数组a1,a2,a3,a4,a5,a6的形式定义D=a1,a2,a3,a4,a5,a6R=|i=1,2,3,4,5,14/11/2023,18,不同的“关系”构成不同的“结构”！,集合的形式定义,SET=(D,R)D=01,02,03,04,05,06,07R=,14/11/2023,19,01,05,03,04,02,06,07,线性结构的形式定义,14/11/2
7、023,20,LINEAR=(D,R)D=01,02,03,04,05,06,07R=,01,02,03,04,05,06,07,树结构的形式定义,14/11/2023,21,TREE=(D,R)D=01,02,03,04,05,06,07R=,01,02,03,04,05,06,07,图结构的形式定义,14/11/2023,22,GRAPH=(D,R)D=01,02,03,04,05,06,07R=,01,02,03,04,05,06,07,存储结构,14/11/2023,23,亦称物理结构，是数据的逻辑结构在计算机存储器内的表示（或映像）。它依赖于计算机。,存储结构（1）,顺序存储结构用一
8、组地址连续的存储单元依次存储数据元素数据间的逻辑关系由元素的存储位置来决定优点：简单缺点：不易变动,14/11/2023,24,001,002,003,004,005,006,007,008,数据,(虚拟)地址,存储结构（2）,链式存储结构用一组任意的存储单元存储数据元素数据之间的逻辑关系用指针来表示优点：修改灵活缺点：复杂,14/11/2023,25,001,042,043,044,105,106,107,108,数据,(虚拟)地址,复数 3.0-2.3i 的两种存储方式,14/11/2023,26,3.0,-2.3,3.0,0415,-2.3,0300,0302,0415,0611,061
9、3,数据,(虚拟)地址,数据,(虚拟)地址,逻辑结构与存储结构的关系,逻辑结构是数据关系在人脑中的抽象存储结构是逻辑结构在计算机中的实现两者综合起来建立了数据元素之间的结构关系，即数据结构,14/11/2023,27,数据运算,如何在数据的各种（逻辑的和存储的）结构的基础上对数据实施一系列有效的基本操作。常用的数据运算：插入：添加一个数据元素删除：移除一个数据元素修改：更改一个数据元素查找：寻找一个数据元素排序：把数据元素按照某种顺序关系排列起来,14/11/2023,28,数据结构课程学什么,14/11/2023,29,数据结构课程学习的主要内容,14/11/2023,30,如何对数据进行逻
10、辑组织（逻辑结构）一个具体问题的逻辑数据结构是什么？如何把数据存储到计算机中去（存储结构）适宜选用什么样的存储结构？相关的数据运算的定义与实现（算法）采用什么样的操作实现算法效率更高？,“程序=数据结构+算法”（Niklaus Wirth),课程内容的组织,14/11/2023,31,线性表栈和队列串数组树图查找排序,数据结构,逻辑结构,存储结构,数据运算,线性结构（线性表/栈/队列/串/数组）,非线性结构,树结构,图结构,顺序结构,链式结构,插入运算,删除运算,修改运算,查找运算,排序运算,用什么形式来定义一个具体的数据结构,14/11/2023,32,数据类型,最早出现于高级语言中，是指一
11、组性质相同的值的集合及定义在集合上的一些操作的总称。在高级语言中，每个变量、常量、表达式都有各自的类型类型用来说明变量或表达式的取值范围和允许施加的操作数据类型的分类原子类型：不可再分解的基本类型，如整型、字符型结构类型：由若干个类型组成、可分解，如整型数组。可看成由一种数据结构和定义在其上的一组操作组成。,14/11/2023,33,抽象数据类型,抽象是指抽取出事物具有的普遍性本质。抽象数据类型（Abstract Data Type,ADT)是指一个数学模型及定义在该模型上的一组操作，与其在计算机内部如何表示无关。实际上和数据类型是一个概念。“整型”就是一个抽象数据类型不同计算机硬件系统实现
12、整数和整数运算的细节是不一样的编程者看来它们的定义和操作却是相同的范畴更广，包括自定义数据类型比如，复数类型以数据为中心的软件开发思路。抽象数据类型的特征：使用与实现分离，实行封装和信息隐藏,14/11/2023,34,抽象数据类型的定义,抽象数据类型实际上就是对该数据结构的定义。用三元组描述如下:ADT=(D,S,P)其中：D 是数据对象，S 是 D 上的关系的集合，P 是对 D 的基本操作的集合。ADT抽象数据类型名数据对象：数据关系：基本操作：ADT 抽象数据类型名,14/11/2023,35,抽象数据类型表示的示例,ADT 抽象数据类型名Data数据对象的定义数据元素之间逻辑关系的定义
13、Operation操作 1初始条件操作结果描述操作 2操作 n endADT,14/11/2023,36,ADT ComplexD=r1,r2|r1,r2 都是实数S=|r1是实部，r2是虚部assign(&C,v1,v2)初始条件：复数C已存在 操作结果：构造复数C，r1,r2分别 被赋以参数v1,v2的值。destroy(&C)初始条件：复数C已存在 操作结果：复数C被销毁。ADT Complex,用C语言定义抽象数据类型,typedef double ItemType/*定义数据项类型*/typedef structItemType r;/*实部*/ItemType m;/*虚部*/Co
14、mplex/*定义复数抽象类型*/void assign(Complex*A,ItemType r,ItemType m);/*赋值*/void add(Complex*A,Complex B);/*A+B*/void minus(Complex*A,Complex B);/*A-B*/void multiply(Complex*A,Complex B);/*A*B*/void divide(Complex*A,Complex B);/*A/B*/,14/11/2023,37,用C语言实现抽象数据类型,14/11/2023,38,Void assign(Complex*A,ItemType r
15、eal,ItemType imaginary)A-r=real;/*实部赋值*/A-m=imaginary;/*虚部赋值*/*End of assign()*/void add(Complex*A,Complex B);/*A=A+B*/A-r+=B.r;/*实部相加*/A-m+=B.m;/*虚部相加*/*End of Add()*/,有没有更合适的方法描述抽象数据类型,14/11/2023,39,抽象数据类型的表示和实现,表示和实现抽象数据类型时可以使用固有的数据类型（如整型、实型、字符型等）。抽象数据类型有些类似C语言中的结构（struct）类型，但增加了相关的服务。我们采用类C语言（介于
16、伪代码和C语言之间）作为描述工具。不拘泥于C语言的细节又容易实现。注意：上机时仍要用具体的编程语言实现，如C或C+。,14/11/2023,40,类C语言简要说明（一）,1、预定义常量和类型/函数结果状态代码#define TRUE 1#define FALSE 0#define OK 1#define ERROR 0#define INFEASIBLE-1#define OVERFLOW-2/Status 是函数的类型，其值是函数结果状态代码typedef int Status;2、数据结构的表示(数据的存储结构)用C的类型定义(typedef)描述，数据元素类型约定为ElemType,由用
17、户在使用该数据类型时自行定义。,类C语言简要说明（二）,3、基本操作的算法的函数描述 函数类型 函数名(函数参数表)/算法说明 语句序列/函数名(1)除了函数的参数需要说明类型外，算法中使用的辅助变量可以不作变量说明，必要时对其作用给予注释。(2)一般而言，a、b、c、d、e等用作数据元素名，i、j、k、l、m、n等用作整型变量名，p、q、r等用作指针变量名。(3)当函数返回值为函数结果状态代码时，函数定义为Status类型。(4)除了值调用方式外，增添了C+语言的引用调用的参数传递方式。在形参表中，以&打头的参数即为引用参数。,类C语言简要说明（三）,4、赋值语句简单赋值 变量名=表达式；串
18、联赋值 变量名1=变量名2=变量名k=表达式；成组赋值（变量名1,变量名k）=（表达式1,表达式k）；结构赋值 结构名=结构名；结构赋值 结构名=（值1,值k）；数组赋值 变量名=表达式；数组赋值 变量名始下标.终下标=变量名起始下标.终止下标；交换赋值 变量名变量名；条件赋值 变量名=条件表达式？表达式T;表达式F；,类C语言简要说明（四）,5、选择语句条件语句1 if(表达式)语句；条件语句2 if（表达式）语句；else 语句；开关语句1 switch（表达式）case值1：语句序列1；break；case值n：语句序列n；break；default：语句序列n+1；开关语句2 swit
19、ch case条件1：语句序列1；break；case条件n：语句序列n；break；default：语句序列n+1；,类C语言简要说明（五）,6、循环语句for语句 for(赋初值表达式序列；条件；修改表达式序列)语句序列；while语句 while(条件)语句序列；do-while语句 do 语句序列；while(条件);7、结束语句函数结束语句 return 表达式；return;case结束语句 break;异常结束语句 exit(异常代码),类C语言简要说明（六）,8、输入和输出语句有 输入语句 scanf(格式串，变量1，变量n);输出语句 printf(格式串，表达式1，表达式n
20、);通常省略格式串。9、注释 单行注释/文字序列10、基本函数有 求最大值 max(表达式1，表达式n)求最小值 min(表达式1，表达式n)求绝对值 abs(表达式)求不足整数值floor(表达式)求进位整数值ceil(表达式)判定文件结束eof(文件变量)或eof 判定行束 eoln(文件变量)或eoln11、逻辑运算约定 与运算&对于A&B，当A的值为0时，不再对B求值。或运算|对于A|B，当A的值为非0时，不再对B求值。,课程名数据结构与算法，什么叫算法？,14/11/2023,47,数据结构和算法的关系,14/11/2023,48,不能只谈数据结构而不谈算法老师下周就可以结课学生不知
21、道数据结构有什么用不可能涉及算法的全部内容算法可以独立开一门新课这里，学习算法是为了更好的理解数据结构,算法的概念,算法是解决某个特定问题的求解步骤的描述。算法在计算机中表现为指令的有限序列，每条指令表示一个或多个操作。计算机对数据的操作可以分为数值性和非数值性两种类型。在数值性操作中主要进行的是算术运算；而在非数值性操作中主要进行的是检索、排序、插入、删除等等。程序不等于算法：计算机程序是算法的具体实现。,14/11/2023,49,（1）有穷性：一个算法必须在执行有穷步之后结束。（2）确定性：算法中的每一步，必须有确切的含义，在他人理解时不会产生二义性。（3）可行性：算法中描述的每一步操作
22、都可以通过已有的基本操作执行有限次实现。（4）输入：一个算法应该有零个或多个输入。（5）输出：一个算法应该有一个或多个输出。这里所说的输出是指与输入有某种特定关系的量。,算法的性质,算法设计的要求,正确性（四个境界）没有语法错误对于合法的输入数据能够产生满足要求的输出对于非法的输入数据能够得出满足规格说明的结果对于任何测试数据都有满足要求的输出结果可读性：便于阅读、理解和交流健壮性：不合法数据也能合理处理时间效率高和存储量低,14/11/2023,51,算法的基本结构,顺序结构表示程序执行的流程确定地按照某一次序进行。,14/11/2023,算法与算法描述,52,选择结构表示程序的流程可能有多
23、种选择，只有结合输入才知道究竟按哪一个流程执行。,循环结构表示程序的流程在某些步骤上要反复执行，直到满足某条件。,True,True,False,算法的六种表示方法,算法的自然语言表示算法的流程图表示算法的N-S图表示算法的PAD图表示算法的伪代码表示算法的类C语言表示,14/11/2023,53,算法表示方法(1),用自然语言表示算法S1：输入s与v；S2：判断v是否为0，若v=0，则输出错误信息；否则计算s/vt，且输出t,问题：计算并输出t=s/v。,点评：优点-直白缺点-层次结构不清晰，容易发生歧义，不适合描述大规模程序,14/11/2023,54,算法表示方法(2),用流程图表示算法
24、,问题：计算并输出t=s/v。,V=0,计算s/v t,14/11/2023,55,输入s与v,输出t,输入错误信息,成立,不成立,算法表示方法(3),用N-S流程图表示算法,问题：计算并输出t=s/v。,输入s与v,V=0,输出错误信息,计算s/v t,成立,不成立,14/11/2023,56,输出t,算法表示方法(4),用PAD图表示算法,问题：计算并输出t=s/v。,输入s与v,输出错误信息,计算s/v t，且输出t,V=0,点评：优点-直观、易懂、逻辑关系清晰。缺点-费事，难改。,14/11/2023,57,成立,不成立,算法表示方法(5),用伪代码表示算法INPUT s,vIF(v=
25、0)THENOUTPUT“ERROR”ELSEt=s/vOUTPUT t,问题：计算并输出t=s/v。,点评：容易理解；不必画图；接近程序设计风格，容易转化为程序,14/11/2023,58,算法表示方法(6),用类C语言表示算法scanf(“%d,%d”,问题：计算并输出t=s/v。,14/11/2023,59,点评：特点同伪代码，更容易转化为C程序,怎样衡量算法的效率？,14/11/2023,60,算法效率的度量方法,事后统计方法通过设计好的测试程序和数据，利用计算机测量其运行时间。缺陷：需要先编写程序；和计算机软硬件相关；和测试数据相关。事前分析估算方法（我们的选择）依据统计方法对算法进
26、行估算。m=f(n)，m是语句总的执行次数，n是输入的规模。和问题输入规模相关，独立于程序设计语言和计算机软硬件,14/11/2023,61,事先分析估算方法的例子,int i,sum=0,n=100;/执行了1次；for(i=1;i=n;i+)/执行了n+1次；sum=sum+i;/执行了n次；printf(“%d”,sum);/执行了1次；,14/11/2023,62,int i,sum=0,n=100;/执行了1次；sum=(1+n)*n/2;/执行了1次；printf(“%d”,sum);/执行了1次；,2n+3次,3次,连续自然数求和的第一种算法,连续自然数求和的第二种算法,函数的渐
27、进增长,给定两个函数f(n)和g(n)，如果存在一个整数N，使得对于所有的 n N，f(n)总是比g(n)大，那么，我们说f(n)的渐进增长快于g(n)。,14/11/2023,63,算法时间复杂度,14/11/2023,64,在进行算法分析时，语句的总执行次数 T(n)是关于问题规模 n 的函数，进而分析 T(n)随 n 的变化情况并确定 T(n)的数量级。算法的时间复杂度，也就是算法的时间量度，用“大O记法”记作：T(n)=O(f(n)。由此得到的 T(n)的数量级叫“大O阶”。它表示随问题规模 n 的增大，算法执行时间增长率和 f(n)的增长率相同，称作算法的渐进时间复杂度，简称时间复杂
28、度。其中 f(n)是问题规模 n 的某个函数。一般情况下，T(n)增长越慢，算法越优。,大O阶的数学定义,当n时，有f(n)/g(n)=常数0，则称函数f(n)与g(n)同阶,或者说，f(n)与g(n)同一 个数量级，记作 f(n)=O(g(n)称上式为算法的时间复杂度,或称该算法的时间复杂 度为O(g(n)。其中,n为问题的规模(大小)的量度。,则算法的时间复杂度为O(n3),推导大O阶的方法,14/11/2023,66,用常数 1 取代运行时间中的所有加法常数。在修改后的运行次数函数中，只保留最高阶项。如果最高阶项存在且不是 1，则移除与这个项相乘的常数。,由此得到的结果就是大O阶。,常数
29、阶 O(1),14/11/2023,67,int i,sum=0,n=100;/执行了1次；sum=(1+n)*n/2;/执行了1次；printf(“%d”,sum);/执行了1次；,3次,注意：不管常数是什么，我们都记作O(1)。没有O(3)，只有O(1)!,线性阶 O(n),14/11/2023,68,int i;for(i=1;i=n;i+)/*时间复杂度为O(1)的程序步骤序列*/,int i=0;while(i n)i+;/*时间复杂度为O(1)的程序步骤序列*/,对数阶 O(logn),14/11/2023,69,int count=1;while(count n)count=co
30、unt*2;/*时间复杂度为O(1)的程序步骤序列*/,平方阶 O(n),14/11/2023,70,int i,j;for(i=0;i n;i+)for(j=0;ji;j+)/*时间复杂度为O(1)的程序步骤序列*/,(a)如果第二行 i n 换成 i m 呢？(b)如果第四行 j=0 换成 j=i 呢？,时间复杂度的叠加,14/11/2023,71,int i,j,k;for(i=0;i n;i+)for(j=0;jn;j+)/*时间复杂度为O(1)的程序步骤序列*/for(k=1;k=n;k+)/*时间复杂度为O(1)的程序步骤序列*/,O(n2)+O(n)=O(n2),函数调用对时间复
31、杂度的影响,14/11/2023,72,int i;for(i=1;i=n;i+)function(i);/执行步骤为 n(n+1)/2,void function(int count)int j;for(j=0;jcount;j+)/*时间复杂度为O(1)的程序步骤序列*/,常见的时间复杂度,14/11/2023,73,O(1)O(log n)O(n)O(nlog n)O(n2)O(n3)O(2n)O(n!)O(nn),最好情况、最坏情况 与 平均情况,时间复杂度一般指的都是最坏情况的运行时间。为什么？平均情况的运行时间有什么意义？为什么不使用最好情况的运行时间来衡量算法效率？,14/11/
32、2023,74,算法空间复杂度,14/11/2023,75,算法的空间复杂度通过计算算法所需的存储空间实现，算法空间复杂度的计算公式记作：S(n)=O(f(n)，其中，n 为问题的规模，f(n)为语句关于 n 所占存储空间的函数。,(a)如何用空间换时间？(b)我们主要讨论时间复杂度问题。,算法举例,【例】百钱买百鸡问题:100元钱买100只鸡，母鸡每只5元，公鸡每只3元，小鸡3只1元，问共可以买多少只母鸡、多少只公鸡、多少只小鸡？算法：（）设母鸡、公鸡、小鸡各为x,y,z只。（）x+y+z=100；5x+3y+z/3=100；只需要解出本方程就可以得到答案。但是得出答案的方法有许多种：,算法
33、：三重循环,for(i=0;i=100;i+)for(j=0;j=100;j+)for(k=0;k=100;k+)if(k%3=0,算法：二重循环,因总共买100只鸡，所以小鸡的数目可以由母鸡数和公鸡数得到。,for(i=0;i100;i+)for(j=0;j100;j+)k=100-i-j;if(k%3=0,算法：改进二重循环,for(i=0;i=20;i+)for(j=0;j33;j+)k=100-i-j;if(k%3=0,算法：一重循环,由x+y+z=100和5*x+3*y+z/3=100合并为一个方程：14*x+8*y=200,简化:7*x+4*y=100 得:x不超过14，x必为4的
34、倍数？!,for(i=0;i=14;i+=4)j=(100-7*i)/4;k=100-i-j;printf(“%d,%d,%dn”,i,j,k);,算法分析,上面四个方法中，第一个方法的循环次数为：100*100*100,一百万次；第二个方法的循环次数为：100*100，1万次；第三个方法为：20*34，680次;第四个方法为：4次.由此可见，算法的设计至关重要。,习题（一）,14/11/2023,82,习题（一）,14/11/2023,83,习题（一）,14/11/2023,84,习题（一）,14/11/2023,85,习题（二）,14/11/2023,86,习题（三）,14/11/2023,87,习题（四）,14/11/2023,88,
