北京邮电大学 计算机学院 数据结构第一章课件

张成文[e-mail]北京邮电大学计算机学院算法与数据结构平时(作业+实验+期中)：40%期末考试(闭卷)：60%成绩评定标准作业：概念，作业本实验：编程，电子版两个要素关于实验报告•电子版形式•统一实验报告格式•每次实验每人写一个实验报告•每次实验报告在下次上课前提交实验报告文档命名•个人word文档命名方式例子：–“实验1-班级-学号-名字.doc”•按班级统一压缩文档命名方式例子：–“实验1-班级.rar”•按班级统一发到指定邮箱，邮件标题例子：–“实验1-班级”•每次实验登记“学习登记表”，并一同发送到指定邮箱实验报告内容要求•问题描述、算法描述、附加了足够注释的程序代码•算法中使用的函数、过程、参数、变量的命名要能表示含义•注意算法格式(层次嵌套、不同功能块之间留空)实验报告评分标准•文档命名•报告内容是否齐全•报告内容是否正确数据结构---第1章绪论8第1章绪论数据结构---第1章绪论91.1学习数据结构的作用和意义•是为研究和解决如何有效地组织和处理非数值数据而产生的理论、技术和方法。数据结构:问题的数学模型算法:处理问题的策略程序设计:为计算机处理问题编制的一组指令集数据结构---第1章绪论10[例]查找某人的社会关系计算机中如何表示/存储和操作？张三李四王五陈六赵七数据结构---第1章绪论111.2基本概念和术语数据被计算机加工处理的对象。数据元素数据的基本单位，是数据集合中的一个个体。一个数据元素可由若干个数据项组成。数据项数据结构中讨论的数据的最小单位。组合项年月日学号姓名班号性别出生日期入学成绩原子项数据结构---第1章绪论12数据对象性质相同的数据元素的集合，是数据的一个子集。学号姓名班号性别出生日期入学成绩001刘影01女19840417623002李恒01男19831211679003陈诚02男19840910638………………数据结构具有结构的数据元素的集合。它包括数据对象的逻辑结构、存储结构和相适应的运算（结构的行为特征）。数据元素数据结构---第1章绪论14四种基本的逻辑结构(1)集合结构数据元素除了“属于同一集合”的联系之外，没有其它的关系。(2)线性结构数据元素之间存在一对一的关系。(3)树型结构数据元素之间存在一对多的关系。(4)图状结构或网状结构数据元素之间存在多对多的关系。成员关系长幼关系管理关系朋友关系逻辑结构数据元素之间的逻辑关系，与计算机无关。数据结构---第1章绪论15存储结构（物理结构）：指数据的逻辑结构在计算机存储器中的映象表示。•数据元素的映象•关系的映象数据结构---第1章绪论16数据存储方式（数据元素关系的存储）的四种常用结构(1)顺序存储：数据元素依次放在连续的存储单元中。a1a2...ai...an(2)链式存储：在存储结点中增加若干指针域，记录后继或者相关结点的地址（指针）。a11220...a31342...a21072...10001004100010041072107612201224指针结点结点数据结构---第1章绪论17(3)索引存储：将数据元素分为若干子表，子表的开始位置存放在索引表中。索引表班级addr主表01102310354……(4)散列存储：根据数据元素的关键字值，由散列函数计算出存储地址。LOC(ai)=H(key)……432……713……王小二李一凡1a12a2……31a31……数据结构---第1章绪论18运算（操作）：在数据逻辑结构上定义的一组数据被使用的方式，其具体实现要在存储结构上进行。数据结构---第1章绪论19数据的逻辑结构+运算的定义-------面向用户（抽象数据类型）概念层数据的存储结构+运算的实现-------面向计算机实现层•按照面向对象程序设计的观点，一种数据结构就是一个抽象数据类型的体现。•在面向对象程序设计语言中，一种数据结构通常使用一个类（Class）进行封装。•在非面向对象程序设计语言中，通常用结构（Structure）封装数据的存储结构，用函数（Function）封装一个运算的实现。分层模型数据类型（datatype）一组值的集合以及定义在这个值集上的一组操作的总称。在高级语言中，数据类型通常又分为原子类型（atomicdatatype）和结构类型（structuraldatatype）。原子类型（atomicdatatype）不可进一步分解的数据类型。结构类型（structuraldatatype）可进一步分解为原子类型或其它结构类型的数据类型。根据数据元素数目的不同又可分为固定聚合类型（fixed-aggregatedatatype）和可变聚合类型（variable-aggregatedatatype)。抽象数据类型（AbstractDataType-----ADT）定义在一个抽象的数学模型上的数据类型及相应操作。它只取决于数据类型的逻辑特性，而与数据类型在计算机内的表示和实现无关。数据结构---第1章绪论22抽象数据类型的描述方法其中基本操作的定义格式为:ADT抽象数据类型名{数据对象：〈数据对象的定义〉数据关系：〈数据关系的定义〉基本操作：〈基本操作的定义〉}ADT抽象数据类型名基本操作名（参数表）初始条件：〈初始条件描述〉操作结果：〈操作结果描述〉数据结构---第1章绪论23[例]抽象数据类型“复数”的定义ADTComplex{数据对象：D＝{e1,e2｜e1,e2∈RealSet}数据关系：R1＝{e1,e2|e1是复数的实数部分,|e2是复数的虚数部分}基本操作：AssignComplex(&Z,v1,v2)操作结果：构造复数Z,其实部和虚部分别被赋以参数v1和v2的值。DestroyComplex(&Z)操作结果：复数Z被销毁。GetReal(Z,&realPart)初始条件：复数Z已存在。操作结果：用realPart返回复数Z的实部值。……}ADTComplex数据结构---第1章绪论241.3算法的描述和分析1.3.1算法的概念建立在数据结构基础上的、求解问题的一系列确切的步骤。一个算法必须满足以下五个重要特性•有穷性：对任何合法输入执行有穷步后能结束。•确定性：每条指令必须有确切的含义。•可行性：算法的每一条指令均能执行。•输入：有零个或多个输入。•输出：有一个或多个输出。数据结构---第1章绪论25评价算法优劣的基本标准•正确性•可读性•健壮性•高效性（高效率与低存储量）算法效率的度量•时间复杂度•空间复杂度数据结构---第1章绪论261.3.2算法的描述数据结构是算法处理的对象，也是实现算法的基础。选择描述工具的原则不依赖于具体计算机与具体程序设计语言的一种形式化语言，可用于描述或表达算法思想。本课程采用类C语言或伪码语言特点它描述的算法自然易懂，具有较好的可移植性。•算法格式void函数名(参数表)返回值的类型函数名(参数表)//算法说明//算法说明{语句序列{语句序列}//函数名}//函数名包括顺序、判定和重复三种基本控制结构和自然语言成分数据结构---第1章绪论27•赋值语句变量名=表达式；变量名1=变量名2==变量名n=表达式；(变量名1,变量名2,…,变量名n)=(表达式1,表达式2,…,表达式n)；结构变量名=(成员1值,成员2值,…,成员n值)；数组变量名1[下标1.下标2]=数组变量名2[下标3..下标4]；变量名1变量名2；变量名=条件表达式？表达式T：表达式F；•条件语句if(条件表达式)语句;else语句;if(条件表达式)语句;数据结构---第1章绪论28•分情况语句（分支语句）switch(表达式){case值1：语句序列1；break;case值2：语句序列2；break;……case值n：语句序列n；break;default:语句n+1；}switch{case条件1：语句序列1；break;case条件2：语句序列2；break;……case条件n：语句序列n；break;default:语句n+1；}数据结构---第1章绪论29•循环语句while（条件表达式）语句；do{语句序列；}while（条件表达式）；break；//强制循环结束continue；//强制循环继续for（赋初值表达式；条件；修改表达式）语句；数据结构---第1章绪论30•输入输出语句scanf(变量表)；printf(变量表)；•转移语句goto语句标号；•引用语句函数名(参量表)；变量名=函数名(参量表)；•返回语句return；Return表达式；exit(异常代码)；•注释语句//注释内容/*注释内容*/数据结构---第1章绪论311.3.3算法分析——算法效率的度量一个具体问题的数据对象往往可以采用多种存储方式的一种，一个问题的解决又常常有多种可用的算法。数据结构---第1章绪论32通常有两种衡量算法效率的方法:事后统计法利用计算机内记时功能，不同算法的程序可以用一组或多组相同的统计数据区分事前分析估算法时间复杂度(渐进时间复杂度)空间复杂度缺点：必须执行程序其它因素掩盖算法本质如何估算算法的时间复杂度？从算法中选取一种对所研究的问题来说执行最频繁的基本操作为原操作,当问题规模n相当大时,该原操作执行时间占算法总执行时间的绝大部分,所以,把该原操作在算法中重复执行的次数(频度)作为算法运行时间的衡量准则。可近似认为：算法的执行时间与原操作的频度成正比估算时间复杂度时取频度的阶次时间复杂度•n–问题规模，一般为数据的输入量•算法的时间复杂度–算法中各语句的频度之和T(n)–T(n)=O(f(n))大O表示法时间复杂度•O的含义–存在正的常数c和n0，使得当nn0时，0T(n)c*f(n)表示随着问题规模n的增长,算法执行时间的增长率和f(n)的增长率相同,称f(n)为算法的渐近时间复杂度，简称时间复杂度，即，当n→∞时T(n)/f(n)→常数。数据结构---第1章绪论36[例1]交换i和j的内容(1)temp=i;(2)i=j;(3)j=temp;解：T(n)=3记作T(n)=O(1)常用的时间复杂度频率计数•算法中常用的时间复杂度频率计数有7种:O(1)常数型O(n)线性型O(n2)平方型O(n3)立方型O(2n)指数型O(log2n)对数型O(nlog2n)二维型按时间复杂度由小到大排列的频率表为：时间复杂度曲线•O(1)O(log2n)＜O(n)＜O(nlog2n)＜(n2)＜O(n3)＜＜O(2n)1、计算T(n)2、从T(n)中推断f(n)时间复杂度计算步骤数据结构---第1章绪论40[例2]nn矩阵相乘的算法语句for(i=1;i=n;i++)n+1for(j=1;j=n;j++)n(n+1){c[i,j]=0;n2for(k=1;k=n;k++)n2(n+1)c[i,j]=c[i,j]+a[i,k]*b[k,j];n3}解：语句频度T(n)=2n3+3n2+2n+1当nn0=1时，有T(n)8n3，即c=8，由此取f(n)=n3则T(n)=O(n3)算法中存在循环时，通常由嵌套层数最深的循环语句的最内层语句决定1、问题的规模2、输入实例的初态影响算法时间复杂度的因素最坏时间复杂度定义：算法在最坏情况下的时间复杂度，即为分析估计算法在最坏情况下执行时间的上界。数据结构---第1章绪论43[例3]在数组A[1..n]查找给定值K(1)i=n;(2)while(i1)&&A[i]KDO(3)i--;(4)return(i);解：最好情况的时间复杂度T(n)=O(1)最坏情况的时间复杂度T(n)=O(n)平均时间复杂度：所有可能的输入实例以等概率出现的情况T(n)=(1+2+...+n)/n=O(n)算法与数据状态有关时，需讨论不同情况1ni数据结构---第1章绪论442）空间复杂度算法的存储空间–输入数据所占空间–程序本身所占空间–辅助变量所占空间空间复杂度S(n)=O(f(n))表示随着问题规模n的增大，算法运行所需存储量的增长率与f(n)的增长率相同。存储密度d=数据本身