北邮算法与数据结构1

数据结构-第一章绪论,1,算法与数据结构,20112113092010211312班2012-2013学年第一学期周三3-4节（10:10）教3-433周五5-7节(13:30)教3-433教师：徐塞虹xush课件下载dsbupt_xu(,数据结构-第一章绪论,2,课程成绩=作业成绩+实验成绩+期中成绩+期末成绩,100%20%20%10%50%,要求：,1、作业按时交，不要互相抄袭；,2、上机实验不超过三人一组（报告中写明每人的工作任务），文档完备，不得抄袭；,数据结构-第一章绪论,3,空望坐等好还家，左右逢源非吾法。光阴好似流水过，恍然若失泪过颊。自欺欺人日日下，自怨自艾也白搭。不如且自将自话，暂祭人殇在天涯。某生试卷留言,数据结构-第一章绪论,4,第一章绪论,1.1课程的作用和意义1.2基本概念和术语1.3算法的描述和分析本章学习要点及习题,数据结构-第一章绪论,5,1.1学习数据结构的作用和意义,是为研究和解决如何有效地组织和处理非数值数据而产生的理论、技术和方法。是计算机科学中的一门综合性的专业基础课。涉及计算机软件、硬件以及数学等数据结构在软件开发中的地位：系统分析系统设计系统实现系统维护(NiklausWirth：数据结构+算法=程序),数据结构:问题的数学模型算法:处理问题的策略程序设计:为计算机处理问题编制的一组指令集,数据结构-第一章绪论,6,例查找某人的社会关系,计算机中如何表示/存储和操作？,张三,李四,王五,陈六,赵七,数据结构-第一章绪论,7,输入输出,CPU（CentralProcessingUnit）,控制器,运算器,寄存器(组),内存储器,外存储器,控制器：控制系统一步步从存储器中取出指令、译码运算器：根据指令完成算术/逻辑运算寄存器：保持程序运行状态、存储当前指令信息及下一条指令地址等,0,OxFF,操作系统,内存,（文件）,数据结构-第一章绪论,8,存储方案1：存储方案2：存储方案3：,张三.王五李四陈六李四王五.,2040,2080,2120,张三.234李四王五.,2040,2080,2120,(1),(2),(3),40Byte,张三.311830601596王五李四.,2040,3060,3118,数据结构-第一章绪论,9,数据结构的作用范畴,抽象数据对象的数学模型（逻辑结构）例：图状结构明确操作（运算的定义）例：查找、插入、在存储结构上映射数据（物理/存储结构）例：顺序存储实现操作,数据结构-第一章绪论,10,1.2基本概念和术语,数据被计算机加工处理的对象。数据元素（记录、表目）数据的基本单位，是数据集合中的一个个体。一个数据元素可由若干个数据项组成。,原子项,数据结构-第一章绪论,11,数据对象是性质相同的数据元素的集合，是数据的一个子集。学号姓名班号性别出生日期入学成绩001刘影01女19840417623002李恒01男19831211679003陈诚02男19840910638数据结构具有结构的数据元素的集合。它包括数据对象的逻辑结构、存储结构和相适应的运算（结构的行为特征）。,数据元素,数据结构-第一章绪论,12,逻辑结构数据元素之间的逻辑关系，与计算机无关。可用一个二元组抽象表示：Data_Structure=(D,R)D数据元素的有穷集合，RD上关系的有穷集合。例设有数据结构B=(D,R)，其中D=d1,d2,d3,d4,d5,d6，R=r，r=,，试画出其逻辑结构图。,数据结构-第一章绪论,13,四种基本的逻辑结构,（以班级学生关系为例）(1)集合结构数据元素除了“属于同一集合”的联系之外，没有其它的关系。(2)线性结构数据元素之间存在一对一的关系。(3)树型结构数据元素之间存在一对多的关系。(4)图状结构或网状结构数据元素之间存在多对多的关系。,成员关系,长幼关系,管理关系,朋友关系,数据结构-第一章绪论,14,例铺设城市通信管线，使总投资最少？,逻辑结构：图状结构,数据结构-第一章绪论,15,存储结构（物理结构）：指数据的逻辑结构在计算机存储器中的映象表示。数据元素的映象用二进制位(bit)的位串表示数据元素。每个数据元素的映象称为结点每个数据项的映象称为数据域关系的映象两种基本方法及其组合使用。顺序映象：以相对的存储位置表示关系链式映象：以附加信息(指针)表示关系在不同的编程环境下，存储结构有不同的描述方式。用高级程序语言编程时，通常可用其提供的数据类型描述。,数据结构-第一章绪论,16,数据存储方式的四种常用结构,(1)顺序存储：数据元素依次放在连续的存储单元中。a1a2.ai.an(2)链式存储：在存储结点中增加若干指针域，记录后继或者相关结点的地址（指针）。a11220.a31342.a21072.,10001004,100010041072107612201224,指针,结点,结点,数据结构-第一章绪论,17,(3)索引存储：将数据元素分为若干子表，子表的开始位置存放在索引表中。索引表班级addr主表01102310354(4)散列存储：根据数据元素的关键字值，由散列函数计算出存储地址。LOC(ai)=H(key)432713王小二李一凡,1a12a231a31,数据结构-第一章绪论,18,运算（操作）：在数据逻辑结构上定义的一组数据被使用的方式，其具体实现要在存储结构上进行。几种常用的运算有：(1)建立数据结构(6)检索*(2)清除数据结构(7)更新(3)插入数据元素(8)判空和判满*(4)删除数据元素(9)求长*(5)排序*操作为引用型操作，即数据值不发生变化；其它为加工型操作。,数据结构-第一章绪论,19,抽象数据类型ADT（AbstractDataType）：数据类型概念的引伸。指一个数学模型以及在其上定义的操作集合，与计算机无关。数据类型：一组值的集合和定义在其上的一组操作的总称。（例C语言的基本数据类型有：逻辑型bool、字符型char、整型int和浮点型float/双精度型double）ADT的特点：将它的使用和实现分离，提高软件复用程度。原子类型结构类型固定聚合类型：值由确定数目的成分构成可变聚合类型：值的成分数目不确定,例集合与集合的并、交、差运算可定义为一个ADT。,数据结构-第一章绪论,20,数据的逻辑结构+运算的定义-面向用户（抽象数据类型）概念层数据的存储结构+运算的实现-面向计算机实现层按照面向对象程序设计的观点，一种数据结构就是一个抽象数据类型的体现。在面向对象程序设计语言中，一种数据结构通常使用一个类（Class）进行封装。在非面向对象程序设计语言中，通常用结构（Structure）封装数据的存储结构，用函数（Function）封装一个运算的实现。,分层模型,数据结构-第一章绪论,21,抽象数据类型的描述方法,其中基本操作的定义格式为:,ADT抽象数据类型名数据对象：数据对象的定义数据关系：数据关系的定义基本操作：基本操作的定义ADT抽象数据类型名,基本操作名（参数表）初始条件：初始条件描述操作结果：操作结果描述,数据结构-第一章绪论,22,抽象数据类型的描述方法（续）,赋值参数(C语言值参)只为操作提供输入值。引用参数(C语言变参)除可提供输入值外，还将返回该参数值在操作后的变化结果注：在运算定义时，表达为“else语句;,if(条件表达式)语句;,数据结构-第一章绪论,28,分情况语句（分支语句）,switch(表达式)case值1：语句序列1；break;case值2：语句序列2；break;case值n：语句序列n；break;default:语句n+1；,switchcase条件1：语句序列1；break;case条件2：语句序列2；break;case条件n：语句序列n；break;default:语句n+1；,数据结构-第一章绪论,29,循环语句,while（条件表达式）语句；,do语句序列；while（条件表达式）；,break；/强制循环结束,continue；/强制循环继续,for（赋初值表达式；条件；修改表达式）语句；,数据结构-第一章绪论,30,输入输出语句,scanf(变量表)；,printf(变量表)；,转移语句,goto语句标号；,引用语句,函数名(参量表)；,变量名=函数名(参量表)；,返回语句,return；,Return表达式；,exit(异常代码)；,注释语句,/注释内容,/*注释内容*/,例冒泡排序算法,数据结构-第一章绪论,31,voidbubble_sort(inta,intn)/将a中n个数据序列重新排列成自小至大有序的整数序列for(i=n-1,change=TRUE;i=1/bubble_sort,数据结构-第一章绪论,32,一些约定,1）预定义常量和类型：/函数结果状态代码#defineTRUE1#defineFALSE0#defineOK1#defineERROR0#defineINFEASIBLE-1#defineOVERFLOW-2/Status作为函数的类型，其值是函数结果状态代码typedefintStatus;2）数据元素类型约定为ElemType，使用时按需定义,数据结构-第一章绪论,33,1.3.3算法分析算法效率的度量,一个具体问题的数据对象往往可以采用多种存储方式的一种，一个问题的解决又常常有多种可用的算法。1）时间复杂度算法的消耗时间：算法中每条语句执行时间之和。时间复杂度：算法中各语句的频度之和T(n)。频度语句的执行次数；n问题的规模，一般为数据的输入量渐近时间复杂度：当问题的规模n趋于无穷大时，T(n)的数量级(阶)。记为T(n)=O(f(n)。O的严格含义存在正的常数c和n0，使得当nn0时，0T(n)c*f(n)实际中，将渐近时间复杂度简称为时间复杂度，用以描述算法的时间特性。,和算法消耗时间相关的因素：算法选用的策略问题的规模编写程序的语言编译程序产生的机器代码的质量计算机执行指令的速度,数据结构-第一章绪论,34,时间复杂度的求法计算T(n)从T(n)中推断f(n)影响算法时间复杂度的因素问题的规模输入实例的初态常见的时间复杂度O(1),O(log2n),O(n),O(nlog2n),O(n2),O(n3),O(2n)好差,数据结构-第一章绪论,35,例1交换i和j的内容(1)temp=i;(2)i=j;(3)j=temp;解：T(n)=3记作T(n)=O(1),数据结构-第一章绪论,36,例2nn矩阵相乘的算法语句for(i=1;i=n;i+)n+1for(j=1;j=n;j+)n(n+1)ci,j=0;n2for(k=1;k=n;k+)n2(n+1)ci,j=ci,j+ai,k*bk,j;n3解：语句频度T(n)=2n3+3n2+2n+1当nn0=1时，有T(n)8n3，即c=8，由此取f(n)=n3则T(n)=O(n3)算法中存在循环时，通常由嵌套层数最深的循环语句的最内层语句决定,数据结构-第一章绪论,37,例3在数组A1.n查找给定值K(1)i=n;(2)while(i1)解：最好情况的时间复杂度T(n)=O(1)最坏情况的时间复杂度T(n)=O(n)平均时间复杂度：所有可能的输入实例以等概率出现的情况T(n)=(1+2+.+n)/n=O(n)算法与数据状态有关时，需讨论不同情况,1,n,数据结构-第一章绪论,38,2）空间复杂度算法的存储空间输入数据所占空间程序本身所占空间辅助变量所占空间空间复杂度S(n)=O(f(n)表示随着问题规模n的增大，算法运行所需存储量的增长率与f(n)的增长率相同。存储密度d=数据本身存储量/实际所占存储量,数据结构-第一章绪论,39,1.熟悉各名词、术语的含义，掌握基本概念。,2.理解算法五个要素的确切含义。,本章学习要点,3.掌握计算语句频度和估算算法时间复杂度的方法。,数据结构-第一章绪论,40,关于程序设计能力的培养,程序设计能力源于实践；是实践的积累。程序设计能