数据结构-绪论课件.ppt

1、1数 据 结 构 2课程意义1001001111姓名学号年龄张三06010120李四06010219ABCDEFG“好好”的程序算法+数据结构数据结构=程序3内容安排第1章 绪论 2 课时第2章 线性表 8 课时第3章 栈和队列 4 课时第4章 串 2 课时第5章 数组与广义表 4 课时第6章 树与二叉树 8 课时第7章 图 8 课时第9章 查找 8 课时第10章 内部排序 4 课时上机实验（线性表 2，二叉树3，图 3）8 课时4考核方法平时成绩 10%考勤作业上机实验 10%（程序+实验报告）线性表链式应用 二叉树有关运算 图有关运算 期末考试成绩 80%（闭卷笔试）5课程信息教材：严蔚敏

2、,吴伟民编著.数据结构.清华大学出版社（C语言版）,1997年4月第一版.先修课程：C+程序设计6第一章 绪 论1.1 什么是数据结构1.2 基本概念和术语1.3 抽象数据类型的表示与实现1.4 算法和算法分析71.1 什么是数据结构计算机解决问题具体问题数学模型设计算法测试调整很多非数值计算问题无法用数学方程描述例1.1 图书馆书目检索系统线性（书p.1-2）例1.2 计算机和人对弈问题树型（书p.1-2）8例1.3 多叉路口交通灯管理系统ABCDEABACADBABCBDDADBDCEAEBECEDABACADBADCEDEABCBDDADBEBEC13条通路，考察任意两条通路是否互相碰撞

3、，在78种情况下有20种情况会碰撞（用连线表示）设置交通灯的问题等价于对图的顶点着色问题：要求对图上的每一个顶点染一种颜色，并且要求有线相连的两个顶点不能具有相同颜色，而总的颜色种类应尽可能地少。9数据结构课程数据结构是一门研究非数值计算的程序设计问题中计算机的操作对象以及它们之间的关系和操作等等的学科。数学代数系统文件系统 数据组织 信息查询软件存储装置硬件编码理论 算子关系数据类型 数据表示 数据运算 数据结构 数据存取 机器组织101.2 基本概念与术语数据数据(Data):是对信息的一种符号表示。在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号的总称。数据元素数据元素(D

4、ata Element):是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。一个数据元素可由若干个数据项数据项(Data Item)组成。数据项是数据的不可分割的最小单位。数据对象数据对象(Data Object):是性质相同的数据元素的集合。是数据的一个子集。数据结构数据结构(Data Structure):是相互之间存在一种或多种特定关系的数据元素的集合。11数据的逻辑结构数据元素之间的相互关系称为逻辑结构。通常分为四类基本结构：集合：集合：结构中的数据元素除了同属于一种类型外，别无其它关系线性结构：线性结构：结构中的数据元素之间存在一对一的关系树型结构：树型结构：结构中的数

5、据元素之间存在一对多的关系图状结构或网状结构：图状结构或网状结构：结构中的数据元素之间存在多对多的关系12数据结构的形式定义数据结构的形式定义为：数据结构是一个二元组 Data_Structure=(D，S)例例1.4 在计算机科学中，复数可取如下定义：复数是一种数据结构：Complex=（C，R）D是数据元素的有限集S是D上关系的有限集C是含两个实数的集合c1，c2R=，这里有序偶表示c1是复数的实部，c2是复数的虚部13数据的存储结构数据结构在计算机中的表示称为数据的存储结构或数据的物理结构。例：例：复数z=3.0-2.3i的两种表示见下图。3.0-2.303000302：-2.33.00

6、415041506130611：顺序映象顺序映象顺序存储结构顺序存储结构非顺序映象非顺序映象链式存储结构链式存储结构指针(Pointer)14数据类型数据类型就是在程序设计语言中，变量所具有的数据种类。换句话说，数据类型是一个值的集合和定义在这个值集上的一组操作的总称。例如：在FORTRAN语言中，变量的数据类型有整型、实型、和复数型 例如：在C+语言中，数据类型：基本类型和构造类型整型、浮点型、字符型数组、结构、联合、指针、枚举型、自定义15数据结构的分类数据结构逻辑结构存储结构非线性结构线性结构线性表栈和队列串数组广义表树、二叉树图文件顺序存储结构（顺序映象）链式存储结构（非顺序映象）16

7、1.3 抽象数据类型的表示与实现抽象数据类型抽象数据类型(Abstract Data Type简称简称ADT)是指一个数学模型以及定义在该模型上的一组操作。抽象数据类型可用以下三元组表示 ADT=（D，S，P）D是数据对象S是D上关系的有限集P是对D的基本操作集。17抽象数据类型三元组例：ADT Triplet 数据对象：D=e1,e2,e3|e1,e2,e3ElemSet 数据关系：R1=,基本操作：InitTriplet(&T,v1,v2,v3);DestroyTriplet(&T);Get(T,i,&e);Put(&T,i,e);IsAscending(T);IsDescending(T

8、);Max(T,&e);Min(T,&e);ADT Triplet线性结构18类C语言可以采用介于伪码和C语言之间的类C语言作为抽象数据类型的描述工具。这使得数据结构和算法的描述和讨论简明清晰，不拘泥于C语言的细节，又能够容易转换成C或者C+程序。类C语言精选了C语言的一个核心子集，同时作了若干扩充修改，增强了语言的描述功能。关于类C语言见教材p10-p13191.4 算法和算法分析算法：算法：是对特定问题求解步骤的一种描述，是指令的有限序列，其中每一条指令表示一个或多个操作。算法具有以下五个特性：有穷性有穷性 一个算法必须总是在执行有穷步之后结束，且每一步都在有穷时间内完成。确定性确定性 算

9、法中每一条指令必须有确切的含义。不存在二义性。可行性可行性 一个算法是可行的。即算法描述的操作都是可以通过已经实现的基本运算执行有限次来实现的。输入输入 一个算法有零个或多个输入，这些输入取自于某个特定的对象集合。输出输出 一个算法有一个或多个输出，这些输出是同输入有着某些特定关系的量。20算法设计的要求正确性正确性 算法应满足具体问题的需求。“正确”有四个层次：(a)不含语法错误；(b)对几组输入正确；(c)对精心设计的测试输入正确；(d)对一切合法输入正确可读性可读性 算法应该好读。以有利于阅读者对程序的理解。健状性健状性 算法应具有容错处理。当输入非法数据时，算法应对其作出反应，而不是产

10、生莫名其妙的输出结果。效率与存储量需求效率与存储量需求 效率指的是算法执行的时间；存储量需求指算法执行过程中所需要的最大存储空间。一般，这两者与问题的规模有关。21算法效率的度量算法执行时间需通过依据该算法编制的程序在计算机上运行时所消耗的时间来度量。通常有两种方法：事后统计的方法事后统计的方法 收集此算法的执行时间和实际占用空间的统计资料事前分析估算的方法事前分析估算的方法 求出该算法的一个时间界限函数例：例：for(i=1;i=n;+i)for(j=1;j=n;+j)cij=0;for(k=1;k=n;+k)cij+=aik*bkj;一个算法是由控制结构（顺序、分支和循环三种）和原操作（指

11、固有数据类型的操作）构成的，则算法时间取决于两者的综合效果。为了便于比较同一问题的不同算法，通常的做法是，从算法中选取一种对于所研究的问题来说是基本操作的原操作原操作，以该基本操作重复执行的次数作为算法的时间量度。撇开与计算机硬件、软件有关的因素，可以认为一个特定算法“运行工作量”的大小只依赖于问题的规模（通常用整数量n表示）。22渐近时间复杂度一般情况下，算法中基本操作重复执行的次数是问题规模n的某个函数，算法的时间量度记作 T(n)=O(f(n)称作算法的渐近时间复杂度渐近时间复杂度(Asymptotic Time Complexity)。定义：如果g(n)是正整数n的一个函数，若存在两个

12、正常数c和n0，对于所有的nn0，有|g(n)|c|f(n)|，则记作 g(n)=O(f(n)。23频度频度频度是指语句重复执行的次数。例例1 1 +x;s=0;将x自增看成是基本操作，则语句频度为，即时间复杂度为(1)。如果将s=0也看成是基本操作，则语句频度为1，其时间复杂度仍为(1)，即常量阶。例例2 2 for(i=1;i=n;+i)+x;s+=x;语句频度为：n其时间复杂度为：O(n)，即时间复杂度为线性阶。24时间复杂度举例例例3 3 for(i=1;i=n;+i)for(j=1;j=n;+j)+x;s+=x;语句频度为：n2,其时间复杂度为：O(n2)，即时间复杂度为平方阶。例例

13、4 4 for(i=0;i=n-1;+i)for(j=0;j=i;+j)aij=0;时间复杂度为：O(n2)i=0:赋值次赋值次i=2:赋值赋值 3 次次i=n-1:赋值赋值 n 次次.+1+2+3+n=(1+n)n/2=n2/2+n/225时间复杂度的不同量级最常用的六种多项式时间及其关系为：O(1)O(logn)O(n)O(nlogn)O(n2)O(n3)最常用的三种指数时间及其关系为：O(2n)O(n!)0;i-)for(j=0;jaj+1)aj aj+1;最好情况：0次 （输入1,3,5升序序列）最坏情况：每次都换，(n2)（输入5,3,1升序序列）27空间复杂度空间复杂度:算法所需存储空间的度量，记作:S(n)=O(f(n)其中n为问题的规模(或大小)时间与空间往往是对矛盾，要综合考虑。28本章学习要点熟悉各名词、术语的含义，掌握基本概念。理解算法五个要素的确切含义。掌握计算语句频度和估算算法时间复杂度的方法。29作业11.1 试分析时间复杂度 sum=1;for(i=0;sumn;i+)sum+=i;1.2 试给出一个时间复杂度为O(log(n)的程序段。