《数据结构》课件第1章.ppt

1、第一章第一章 绪绪 论论 课程简介课程简介 基本概念基本概念 算法算法 算法语言的说明算法语言的说明开设本课程的必要性以及课程的特点：开设本课程的必要性以及课程的特点：1.计算机专业重要的专业基础课之一计算机专业重要的专业基础课之一.2.需要有关需要有关“程序设计语言程序设计语言”和和“离散数学离散数学”的知识作为课程的基础的知识作为课程的基础.3.实践性较强实践性较强.课程简介课程简介 在计算机发展的初期，计算机主要用于科在计算机发展的初期，计算机主要用于科学计算，因此程序设计者的主要精力集中在程学计算，因此程序设计者的主要精力集中在程序设计的技巧上，而不重视数据结构。当时处序设计的技巧上，

2、而不重视数据结构。当时处理一个计算问题的一般步骤为：理一个计算问题的一般步骤为：具体数值问题具体数值问题 数学模型数学模型 设计算法设计算法 编程编程抽象出抽象出 随着计算机的推广普及，计算机越来越多随着计算机的推广普及，计算机越来越多地应用于非数值领域，使人们逐渐认识到选择地应用于非数值领域，使人们逐渐认识到选择一门好的数据结构，从而设计一种好的算法是一门好的数据结构，从而设计一种好的算法是得到一个好的程序的基础。得到一个好的程序的基础。算法算法+数据结构数据结构=程序程序(Niklaus Wirth)（Algorithm+Data structure=Program)例例 人机对奕问题人机

3、对奕问题.登录号登录号书名书名作者作者分类号分类号172832172832离散数学离散数学樊映川樊映川S01S01172833172833理论力学理论力学罗远祥罗远祥S01S01172834172834高等数学高等数学华罗庚华罗庚S01S01172835172835线性代数线性代数滦汝书滦汝书S02S02书名书名登录号登录号高等数学高等数学1 7 2 8 3 2、172834理论力学理论力学172833线性代数线性代数172835作者作者登录号登录号樊映川樊映川172832华罗庚华罗庚172834滦汝书滦汝书172835类别类别登录号登录号L172833S1 7 2 8 3 2、172834

4、1.研究数据元素之间的客观联系研究数据元素之间的客观联系。2.研究具有某种逻辑关系的数据在计算机存储研究具有某种逻辑关系的数据在计算机存储 器内的存储方式。器内的存储方式。3.研究如何在数据的各种结构研究如何在数据的各种结构(逻辑的和物理的逻辑的和物理的)的基础上对数据实施一系列有效的基本操作。的基础上对数据实施一系列有效的基本操作。逻辑结构逻辑结构存储结构存储结构数据结构课程研究的主要内容数据结构课程研究的主要内容算法算法 基本概念基本概念 1 1）集合：集合中任何两个结点之间都）集合：集合中任何两个结点之间都没有逻辑关系，组织形式松散。没有逻辑关系，组织形式松散。2 2）线性结构：元素之间

5、存在着一对一）线性结构：元素之间存在着一对一的关系。依次排列形成一条的关系。依次排列形成一条“锁链锁链”。3 3）树形结构：数据元素之间存在着一对）树形结构：数据元素之间存在着一对多的关系，具有分支、层次特性。多的关系，具有分支、层次特性。4 4）图状结构：数据元素之间存在多对多）图状结构：数据元素之间存在多对多的关系，元素之间互相缠绕，任何两个的关系，元素之间互相缠绕，任何两个元素都可以邻接。元素都可以邻接。1 1）顺序存储方式（向量存储）顺序存储方式（向量存储）2 2）链式存储方式）链式存储方式3 3）索引存储方式）索引存储方式4 4）散列存储方式）散列存储方式特性特性数据抽象：用数据抽象

6、：用ADT描述程序处理的实体时，强调的是其本描述程序处理的实体时，强调的是其本 质的特征，其完成的功能以及和外部的接口质的特征，其完成的功能以及和外部的接口数据封装：将实体的外部特性和其内部实现分离，并对外数据封装：将实体的外部特性和其内部实现分离，并对外 部用户隐藏其内部实现细节部用户隐藏其内部实现细节ADT 抽象数据类型名抽象数据类型名 数据对象：数据对象：数据关系：数据关系：基本操作：基本操作：ADT 抽象数据类型名抽象数据类型名例如例如:抽象数据类型复数的定义抽象数据类型复数的定义RealsetRealset 数据关系：数据关系：R1=|e1R1=|e1是复数的实数部分、是复数的实数部

7、分、e2e2是是 复数的虚数部分复数的虚数部分 基本操作：基本操作：InitComplex(v1,v2)InitComplex(v1,v2)DestroyComplex(Z)DestroyComplex(Z)GetReal(Z,realPart)GetReal(Z,realPart)GetImag(Z,ImagPart)GetImag(Z,ImagPart)Add(Z1,Z2,Sum)Add(Z1,Z2,Sum)Subtract(Z1,Z2,Difference)Subtract(Z1,Z2,Difference)Multiply(Z1,Z2,Product)Multiply(Z1,Z2,Pr

8、oduct)ADT Complex ADT Complex 注：对于数据成员完全相同的数据类型，如果给它们赋予不同的语义，注：对于数据成员完全相同的数据类型，如果给它们赋予不同的语义，则可形成不同的抽象数据类型则可形成不同的抽象数据类型。算法算法算法：算法：解决问题的方法和策略，指为解决一个或解决问题的方法和策略，指为解决一个或一类问题给出的一个确定的、有限长的操作序列。一类问题给出的一个确定的、有限长的操作序列。算法的特性算法的特性:1.有穷性有穷性2.确定性确定性3.可行性可行性4.有输入有输入5.有输出有输出算法设计的原则算法设计的原则1.正确性正确性a.a.程序中不含语法错误程序中不含

9、语法错误b.b.程序对于几组给定的输入数据能得出满足要求的结果程序对于几组给定的输入数据能得出满足要求的结果c.c.程序对于精心选择的、典型的、苛刻的且带有刁难程序对于精心选择的、典型的、苛刻的且带有刁难 性的几组输入能得出满足要求的结果性的几组输入能得出满足要求的结果d.d.程序对一切合法输入都能得出满足要求的结果程序对一切合法输入都能得出满足要求的结果2.可读性：可读性：算法主要是为了人的阅读与交流，其次才是为了计算算法主要是为了人的阅读与交流，其次才是为了计算 机执行，因此算法应该易于理解；另外，晦涩难懂的机执行，因此算法应该易于理解；另外，晦涩难懂的 程序易于隐藏较多错误而难于调试程序

10、易于隐藏较多错误而难于调试3.健壮性：健壮性：当输入的数据非法时，算法应当恰当地做出反应或进当输入的数据非法时，算法应当恰当地做出反应或进 行相应的处理，而不是产生莫名其妙的错误输出；并行相应的处理，而不是产生莫名其妙的错误输出；并 且处理错误的方法不应该是中断程序的执行，而应是且处理错误的方法不应该是中断程序的执行，而应是 返回一个表示错误或错误性质的值，以便在更高的抽返回一个表示错误或错误性质的值，以便在更高的抽 象层次进行处理象层次进行处理4.4.高效率和低存储量需求：高效率和低存储量需求：效率：指算法的执行时间效率：指算法的执行时间 存储量：算法执行过程中所需的最大存储空间存储量：算法

11、执行过程中所需的最大存储空间 两者都与问题的规模有关两者都与问题的规模有关算法的复杂性算法的复杂性复杂性：复杂性：指实现或运行某一算法所需资源的多少。指实现或运行某一算法所需资源的多少。时间复杂性时间复杂性空间复杂性空间复杂性人工复杂性人工复杂性(指编程、调试等所需的人工指编程、调试等所需的人工)和算法执行时和算法执行时间相关的因素：间相关的因素：1.1.算法选用的策略算法选用的策略2.2.问题的规模问题的规模3.3.编写程序的语言编写程序的语言4.4.编译程序产生的机器代码的质量编译程序产生的机器代码的质量5.5.计算机执行指令的速度计算机执行指令的速度一个特定算法的一个特定算法的“运行工作

12、量运行工作量”的大小，只依赖于问题的规模（通的大小，只依赖于问题的规模（通常用整数量常用整数量n n来表示），或者说它是问题规模的函数。来表示），或者说它是问题规模的函数。算法的时间复杂性：算法的时间复杂性：假如随着问题规模假如随着问题规模n的增长，的增长，算法执行时间的增长率和算法执行时间的增长率和f(n)的增长率相同，则的增长率相同，则记作记作T(n)=O(f(n)，称，称T(n)为算法的时间复杂性。为算法的时间复杂性。算法时间复杂性的度量：算法时间复杂性的度量：任何一个算法都是由一个控制结构和若干原子操作组成任何一个算法都是由一个控制结构和若干原子操作组成 算法的执行时间算法的执行时间=

13、原操作原操作(i)(i)的执行次数的执行次数*原操作原操作(i)(i)的执行时间的执行时间 因为原操作的执行时间相对问题的规模因为原操作的执行时间相对问题的规模n n而言是个常量，所以而言是个常量，所以 算法的执行时间与原操作执行次数之和成正比。算法的执行时间与原操作执行次数之和成正比。从算法中选取一种对于所研究的问题来说是基本操作的原操从算法中选取一种对于所研究的问题来说是基本操作的原操 作，以该基本操作在算法中重复执行的次数作为时间复杂的依据。作，以该基本操作在算法中重复执行的次数作为时间复杂的依据。这种衡量效率的办法所得出的不是时间量，而指一种增长趋势的这种衡量效率的办法所得出的不是时间

14、量，而指一种增长趋势的 度量，它与软、硬件无关，只揭示出算法本身执行效率的优劣。度量，它与软、硬件无关，只揭示出算法本身执行效率的优劣。例如：例如：k=k+1 时间复杂度为时间复杂度为O(1)例如：例如：for(i=0;in;i+)k=k+1 时间复杂度为时间复杂度为O(n)例如：例如：for(i=0;in;i+)for(j=0;jn;j+)k=k+1 时间复杂度为时间复杂度为O(n2)例如：例如：for(i=0;in;i+)for(j=0;jn;j+)cij=0;for(k=0;kn;k+)cij=cij+aik*bkj;时间复杂度为时间复杂度为O(n3)-n+1 -n(n+1)-n2 -n

15、2(n+1)-n3对于足够大的对于足够大的n，存在下述关系：，存在下述关系：O(log n)O(n)O(nlog n)O(n2)O(n3)O(2n)O(3n)O(n!)算法的空间复杂性：算法的空间复杂性：假如随着问题规模假如随着问题规模n的增长，的增长，算法执行所需存储量的增长率和算法执行所需存储量的增长率和g(n)的增长率相的增长率相同，则记作同，则记作S(n)=O(g(n)，称，称S(n)为算法的空间为算法的空间复杂性。复杂性。算法的存储量：算法执行过程中所需的最大存储空间。算法的存储量：算法执行过程中所需的最大存储空间。算法的存储空间算法的存储空间1.1.输入数据所占的空间输入数据所占的

16、空间2.2.程序本身所占的空间程序本身所占的空间3.3.辅助变量所占的空间辅助变量所占的空间1.采用自然语言来描述采用自然语言来描述问题问题：求两个正整数：求两个正整数M M与与N N的最大公因子。的最大公因子。(1)M除以除以N，将余数送中间变量，将余数送中间变量R；(2)测试余数测试余数R是否等于零？是否等于零？a)若若R等于零，求得的最大公因子为当前等于零，求得的最大公因子为当前N 的值的值,算法到此结束。算法到此结束。b)若若R不等于零，将不等于零，将N送入送入M，将，将R送送N,重重 复算法的复算法的(1)和和(2)。分类：分类：1.非形式算法（自然语言算法）非形式算法（自然语言算法

17、）2.流程图语言流程图语言3.程序设计语言描述的算法程序设计语言描述的算法算法描述语言：算法描述语言：4.伪语言描述的算法伪语言描述的算法开始开始M除以除以N的余数送的余数送R余数余数R为为0否？否？输出输出N的值的值结束结束将将N送送M将将R送送Nnoyes2.采用程序流程图的形式来描述采用程序流程图的形式来描述3.采用采用某种具体程序语言某种具体程序语言来描述来描述COMFACTOR(int M,int N)int R;while(1)R=M%N;if (R=0)return N;M=N;N=R;来自对来自对C C语言的修改，它描述的算法是不能直语言的修改，它描述的算法是不能直接在机器上执

18、行的程序过程。它与标准接在机器上执行的程序过程。它与标准C C的主要区的主要区别如下：别如下：1.1.局部变量的说明可以省略局部变量的说明可以省略(但形参表中及函数类型的但形参表中及函数类型的 说明必须保留说明必须保留)，重要的变量须在注解中说明其类，重要的变量须在注解中说明其类型和作用。型和作用。2.2.算法写成函数的形式。算法写成函数的形式。函数类型函数类型 函数名函数名(函数参数表）函数参数表）/算法说明算法说明 语句序列语句序列;/函数名函数名 类类C C语言说明语言说明3.3.在函数中除了值调用方式之外，增添了在函数中除了值调用方式之外，增添了C+C+语语言的引用调用的参数传递方式。

19、在形参表中，言的引用调用的参数传递方式。在形参表中，以以&打头的参数即为引用参数，引用参数能被打头的参数即为引用参数，引用参数能被函数本身更新值，可以作为输出数据的管道。函数本身更新值，可以作为输出数据的管道。4.4.内存的动态分配与释放内存的动态分配与释放 使用使用newnew和和deletedelete动态分配和释放内存空间。动态分配和释放内存空间。分配空间分配空间 指针变量指针变量=new=new 数据类型；数据类型；释放空间释放空间 delete delete 指针变量；指针变量；5.5.不含不含goto goto 语句，增加以下两条语句语句，增加以下两条语句:1)1)出错处理语句：出错处理语句：Error(Error(字符串字符串)，其功能是终止它所在算法，其功能是终止它所在算法 的执行，并回送表示出错信息的字符串。的执行，并回送表示出错信息的字符串。2)2)返回语句：返回语句：ReturnReturn和和Return(Return(表达式表达式)，其功能是终止函数的，其功能是终止函数的执行，执行，Return(Return(表达式表达式)终止函数的执行并将表终止函数的执行并将表达式的值回传给函数名。达式的值回传给函数名。6.6.在算法中任何处均可插入在算法中任何处均可插入/,/,进行单行注释。进行单行注释。