数据结构与算法分析第一章绪论ppt课件

.,1,第一章绪论,教学内容：1.1数据结构的原则1.2抽象数据类型和数据结构1.3问题、算法和程序学习要求：理解、掌握算法的基本概念和简单的算法分析、数据和数据结构的基本概念、数据的逻辑结构和存储结构的基本概念及其性质和两种结构之间的关系。,.,2,引言,二十一世纪是科学技术高速发展的信息时代，而计算机是处理信息的主要工具，因此，人们已经认识到，计算机知识已成为人类当代文化的一个重要组成部分。,.,3,计算机科学技术以惊人的速度向前发展，它的广泛应用已从传统的数值计算领域发展到各种非数值计算领域。在非数值计算领域里，数据处理的对象已从简单的数值发展到一般的符号，进而发展到具有一定结构的数据。,.,4,在这里，面临的主要问题是：针对每一种新的应用领域的处理对象，如何选择合适的数据表示（结构），如何有效地组织计算机存贮，并在此基础上又如何有效地实现对象之间的“运算”关系。传统的解决数值计算的许多理论、方法和技术已不能满足解决非数值计算问题的需要，必须进行新的探索。数据结构就是研究和解决这些问题的重要基础理论。因此，“数据结构”课程已成为计算机类专业的一门重要专业基础课。,.,5,1.1数据结构的原则,数据结构：一类数据的表示及其相关操作学习数据结构的必要性计算机功能强大更复杂的问题更复杂的问题更大的计算量工作越复杂越偏离人们的日常经验故：必须有一种数据结构来组织各种复杂的数据。任何一种数据项集合都必须具备查询、排序、修改的功能，如果选择一个好的数据结构和算法将会对程序的运行时间产生巨大的影响。,一、为什么要学习数据结构？1、什么是程序、软件？N.沃思（NiklausWirth)教授提出：程序=算法+数据结构,.,7,程序的主要目标是存储信息和检索信息,而基础是信息表示.程序设计核心目标：（）设计一种容易理解、编码和调试的算法（软件工程原理）（）设计一种能有效利用计算机资源的算法（数据结构和算法）程序简明清晰（简洁）,程序=算法+数据结构以上公式说明了如下两个问题：（1）数据上的算法决定如何构造和组织数据（算法数据结构）。（2）算法的选择依赖于作为基础的数据结构（数据结构算法）。软件=程序+文档（软件工程的观点）,2、电子计算机的主要用途：早期：主要用于数值计算。后来：处理逐渐扩大到非数值计算领域（能处理多种复杂的具有一定结构关系的数据）。,（1）数值计算解决问题的一般步骤：数学模型选择计算机语言编出程序测试最终解答。数值计算的关键是：如何得出数学模型（方程）？程序设计人员比较关注程序设计的技巧。,（2）非数值计算问题：数据元素之间的相互关系一般无法用数学方程加以描述,.,12,例1书目自动检索系统,书目文件,.,13,例2人机对奕问题,.,14,例3多叉路口交通灯管理问题,例4:电话号码查询问题：（1）按顺序存储方式：须遍历表（2）按姓氏索引方式：索引要写出好的查找算法，取决于这张表的结构及存储方式。电话号码表的结构和存储方式决定了查找（算法）的效率。,例5:田径赛的时间安排问题（无向图的着色问题）：设有六个比赛项目，规定每个选手至多可参加三个项目，有五人报名参加比赛（如下表所示）设计比赛日程表，使得在尽可能短的时间内完成比赛。,例6：田径赛的时间安排问题,跳高,跳远,标枪,铅球,200M,100M,1、任一选手所选中的项目中应该两两有边相连；2、任一两个有边相连的顶点颜色（时间）不能相同。,（1）设用如下六个不同的代号代表不同的项目：跳高跳远标枪铅球100米200米ABCDEF（2）用顶点代表比赛项目不能同时进行比赛的项目之间连上一条边。（3）某选手比赛的项目必定有边相连（不能同时比赛）。,解法如下：,A,E,B,F,D,C,只需安排四个单位时间进行比赛,总结：求解非数值计算的问题主要考虑的是设计出合适的数据结构及相应的算法。即：首先要考虑对相关的各种信息如何表示、组织和存储？因此，可以认为：数据结构是一门研究非数值计算的程序设计问题中计算机的操作对象以及它们之间的关系和操作的学科。,二、数据结构课程的形成和发展：形成阶段：60年代初期，“数据结构”有关的内容散见于操作系统、编译原理和表处理语言等课程。1968年，“数据结构”被列入美国一些大学计算机科学系的教学计划。发展阶段：数据结构的概念不断扩充，包括了网络、集合代数论、关系等“离散数学结构”的内容。70年代后期，我国高校陆续开设该课程。,数据结构课程所处的地位：,.,23,1.2抽象数据类型和数据结构一、名词解释,类型：是一组值的集合。如：整数数据项：一条信息或其值属于某种类型的一条记录。如：学生记录里的姓名项数据类型：一种类型和定义在该类型上的一组操作。如整型变量是整数数据类型的一个成员，而加法是定义在整数类型上的一种操作,.,24,抽象数据类型(ADT)：指数据结构作为一个软件组件的实现每个ADT的操作由它的输入和输出定义每个ADT的操作细节是封装的数据结构：是ADT的实现与ADT联系的操作都是由一个成员函数来实现“数据结构”常指计算机内存中的数据“文件结构”常指外存储器中数据的组织,.,25,二、什么是数据结构？基本概念和术语数据（data)所有能输入到计算机中去的描述客观事物的符号数据元素（dataelement）数据的基本单位，也称节点（node）或记录（record）数据项（dataitem）有独立含义的数据最小单位，也称域(field)数据结构（datastructure)数据元素和数据元素关系的集合,.,26,逻辑形式与物理形式,数据项包括逻辑与物理形式逻辑形式是由ADT给出的数据项的定义物理形式是数据结构中对数据项的实现,.,27,数据的逻辑结构只抽象反映数据元素的逻辑关系数据的存储（物理）结构数据的逻辑结构在计算机存储器中的实现,.,28,.,29,1536,元素2,1400,元素1,1346,元素3,元素4,1345,h,链式存储,h,.,30,2、数据结构的定义定义1-数据元素之间的相互关系称为结构，带有结构的数据元素的集合称为数据结构。定义2-按某种逻辑关系组织起来的一批数据（或称带结构的数据元素的集合）应用计算机语言并按一定的存储表示方式把它们存储在计算机的存储器中，并在其上定义了一个运算的集合。,.,32,数据结构定义:是一门研究非数值计算的程序设计问题中计算机的操作对象以及它们之间的关系和操作的学科,3、数据结构的三个方面的含义：逻辑结构-数据元素间抽象化的相互关系（简称为数据结构）。与数据的存储无关，独立于计算机，它是从具体问题抽象出来的数学模型。存储结构（物理结构）-数据元素及其关系在计算机存储器中的存储方式。是逻辑结构用计算机语言的实现，它依赖于计算机语言。运算（算法）,（1）逻辑结构-线性结构-有且仅有一个开始和一个终端结点，并且所有结点都最多只有一个直接前趋和一个后继。例如：线性表、栈、队列、串非线性结构-一个结点可能有多个直接前趋和直接后继。例如：树、图、多维数组、广义表等。,（2）存储结构存储结构两方面的内容：数据元素自身值的表示（数据域）该结点与其它结点关系的域（链域）四种基本的存储方法：顺序存储方法（结构）链接存储方法（链式存储结构）索引存储方法散列存储方法同一种逻辑结构可采用不同的存储方法（以上四种之一或组合），这主要考虑的是运算方便及算法的时空要求。,逻辑结构存储结构小结：（1）数据的逻辑结构、存储结构和数据的运算（算法）构成了数据结构三个方面的含义。（2）程序设计的实质是对实际问题选择一个好的数据结构，加之设计一个好的算法。而好的算法在很大程度上取决于描述实际问题的数据结构。,.,37,选择数据结构：（学生信息管理系统）分析问题，以确定任何算法均会遇到的资源限制确定必须支持的基本操作，并度量每种操作所受的资源限制。选择最接近这些开销的数据结构,效率：如果能在所要求的资源限制(resourceconstraint)内将问题解决好，则称该算法是有效率(efficient)的。代价：解决一个问题所耗费的关键资源(如时间、空间)。,选择数据结构要考虑的三个问题：1、开始时是将所有数据项都插入数据结构还是与其他操作混合在一起插入2、数据项能否删除3、所有数据项是否按某一个已经定义好的顺序排列，是否允许查找特定的数据项,.,38,代价与效益,每一个数据结构都与代价与效益联系在一起很难说一种算法在所有情况下都比其他算法好一个数据结构必须要求：空间存储数据项时间执行单个操作程序设计工作,每一个问题都有可利用空间和时间的限制只有对问题特性进行仔细分析后才能得到解决问题的最好的数据结构银行例子：开户：几分钟交易：几秒钟销户：月末（更长时间）,.,39,学习的目的,对每个数据结构加强对存在代价与效益的观念掌握常用的数据结构将常用的数据结构放入你的工具包理解怎样去衡量一个数据结构或程序的代价评价标准,.,40,1.3问题、算法和程序,问题：需要完成的任务一组输入必有一组相应的输出问题的定义应包括对任何行为可行方案所需资源的限制,.,41,问题,问题函数函数是输入(定义域domain)和输出(值域range)的一种映射关系函数的输入可是一个值或一个实例这些值组成的输入称为函数的参数对于一个给定的输入，函数每次计算所得的输出应必然相同,.,42,算法和程序,算法：解决一个问题的方法或过程.处方对于一个问题的算法给定一输入，必然会转化为一个输出输入输出的映射一个问题可用多种算法来解决算法的属性：正确性具体步骤确定性有限性可终止性程序：用某种程序设计语言对一种算法的实现,算法的概念和描述：一、算法的概念：所谓算法（Algorithm)是描述计算机解决给定问题的操作过程（解题方法），即为解决某一特定问题而由若干条指令组成的有穷序列。,1.算法-求解一个特定任务的指令的有限序列。例7.求a0.an-1中n个数的平均值(假定n0)。floataverage(floata,intn)inti；floats=0.0；/累加器赋初值for(i=0；in；i+)s=s+ai；/ai累加到s中s=s/n；/计算平均值printf(“ave=%f”,s)；/输出return(s)；/返回其中：a,n为输入量；s为输出量。,2.算法的5个特征,(1)有穷性：在有限步(或有限时间)之后算法终止。例8.i=0；s=0；while(i=10)s+=i；i+；/使i趋于10,(2)确定性：无二义性。例9：x=5；y=10；z=x+y；printf(“%d,%d,%d”,x,y,z)；x+y解释为：x+(+y)？还是(x+)+y？例:intx=0;表达式：x+x+的值,(3)可行性：可以在计算机上实现。for(i=1,s=0；i=0；i+)/死循环s+；/不能终止,例11floatsuanfa2()intx,y；scanf(“%d”,i=n;i+)/n+1for(j=1;j=n;j+)/n(n+1)cij=0;/n*nfor(k=1;k=n;k+)/n*n(n+1)cij=cij+aik*bkj;/n*n*n,2算法的简单分析：1、程序正确性的四个层面：（1）不含语法错误（2）程序对于n组输入数据能够得出满足规格说明要求的结果。（3）程序对于精心选择的典型、边界性的n组输入数据能得出满足规格说明要求的结果。（4）程序对于一切合适的输入数据都能得出满足规格说明要求的结果（穷举）。,2、算法效率的度量（1）程序运行所耗费的时间(由下列因素决定)：算法所选用的策略问题的规模书写程序所采用的语言编译程序所产生的机器代码的质量机器执行指令的速度一个算法耗费的时间=算法中每条语句的执行时间之和。若不考虑机器硬、软件因素，可以认为算法“运行工作量”的大小是问题规模的函数。,算法的时间复杂度-,算法(或程序)中基本操作(或语句)重复执行的次数的总和。设n为求解的问题的规模,基本操作(或语句)执行次数总和称为语句频度,记作f(n)；时间复杂度记作T(n),有：T(n)=O(f(n)例16ints；scanf(“%d”,for(i=1;i=n;i+)/n次t=1;/n次for(j=1;j=i;j+)/n*(n+1)/2次t*=i;/n*(n+1)/2次s+=t;/n次return(s);/1次f(n)=n+n+n*(n+1)/2+n*(n+1)/2+n+1=n2+4n+1T(n)=O(f(n)=O(n2),求i!,.,71,例20(续）：求解：S=1!+2!+.+n!算法2：longsum_of_fac(intn)longs=0,t,i;t=1;/1次for(i=1;i=n;i+)/n次t*=i;/n次s+=t;/n次return(s);/1次f(n)=1+n+n+n+n+1=3n+2T(n)=O(f(n)=O(n),求i!,.,72,Voidmain()intnum,fn,fn1,fn2,i;scanf(“%d”,讨论：当num1时，执行3+2+1+num+3*(num-1)+(num-1)+1=5*num+3个指令，执行次数为5*num+3,（2）问题的规模（size)-算法求解问题的输入量（或初始数据量）。（3）不考虑机器软硬件环境时算法的时间耗费：设：执行每条语句所需时间为单位时间，则：一个算法耗费的时间=所有语句的频度之和。时间复杂度T(n)-即：时间耗费，它是算法求解问题n的函数。渐近时间复杂度-即当问题的规模n时的时间复杂度T(n)的数量级（阶），记作：T(n)=O(f(n)评价一个算法的时间性能，主要标准是算法的渐近时间复杂度(TimeComplexity),.,74,例21以下为交换a和b的内容的算法，试分析其T(n)。temp=II=jj=temp分析：因为执行上述语句仅需常数时间，所以T(n)=O(1)。,.,75