《数据结构课件、代码》第1章绪论.ppt

《《数据结构课件、代码》第1章绪论.ppt》由会员分享，可在线阅读，更多相关《《数据结构课件、代码》第1章绪论.ppt（48页珍藏版）》请在三一办公上搜索。

1、张成文北京邮电大学计算机学院,数据结构,平时(实验)：40%期末考试(闭卷)：60%,成绩评定标准,关于实验报告,电子版形式统一实验报告格式每次实验写一个实验报告每次实验报告在下次上课前提交,实验报告文档命名,个人word文档命名方式例子：“实验1-班级-学号-名字.doc”按班级统一压缩文档命名方式例子：“实验1-班级.rar”按班级统一发到指定邮箱，邮件标题例子：“实验1-班级”每次实验登记“学习登记表”，并一同发送到指定邮箱,实验报告内容要求,问题描述、算法描述、附加了足够注释的程序代码算法中使用的函数、过程、参数、变量的命名要能表示含义注意算法格式(层次嵌套、不同功能块之间留空),实验

2、报告评分标准,文档命名报告封面内容是否齐全报告格式是否正确报告内容是否齐全报告内容是否正确,数据结构-第1章 绪论,7,第1章 绪 论,数据结构-第1章 绪论,8,1.1 学习数据结构的作用和意义,是为研究和解决如何有效地组织和处理非数值数据而产生的理论、技术和方法。是计算机科学中的一门综合性的专业基础课。涉及计算机软件、硬件以及数学等数据结构在软件开发中的地位：系统分析 系统设计 系统实现 系统维护(Niklaus Wirth：数据结构+算法=程序),数据结构:问题的数学模型算法:处理问题的策略程序设计:为计算机处理问题编制的一组指令集,数据结构-第1章 绪论,9,例 查找某人的社会关系,计

3、算机中如何表示/存储和操作？,张三,李四,王五,陈六,赵七,数据结构-第1章 绪论,10,输入 输出,CPU,控制器,运算器,寄存器(组),内存储器,外存储器,控制器：控制系统一步步从存储器中取出指令、译码运算器：根据指令完成算术/逻辑运算寄存器：保持程序运行状态、存储当前指令信息 及下一条指令地址等,0,OxFF,操作系统,内存,（文件）,数据结构-第1章 绪论,11,存储方案1：存储方案2：存储方案3：,张三.王五李四陈六李四王五.,2040,2080,2120,张三.234李四王五.,2040,2080,2120,(1),(2),(3),40Byte,张三.311830601596王五李

4、四.,2040,3060,3118,数据结构-第1章 绪论,12,数据结构的作用范畴,抽象数据对象的数学模型（逻辑结构）例：图状结构明确操作（运算的定义）例：查找、插入、在存储结构上映射数据（物理/存储结构）例：顺序存储实现操作,数据结构-第1章 绪论,14,1.2 基本概念和术语,数据 被计算机加工处理的对象。数据元素（记录、表目）数据的基本单位，是数据集合中的一个个体。一个数据元素可由若干个数据项组成。数据项是数据结构中讨论的数据的最小单位。,原子项,数据结构-第1章 绪论,15,数据对象 是性质相同的数据元素的集合，是数据的一个子集。学号 姓名 班号 性别 出生日期 入学成绩 001 刘

5、影 01 女 19840417 623 002 李恒 01 男 19831211 679 003 陈诚 02 男 19840910 638 数据结构 具有结构的数据元素的集合。它包括数据对象的逻辑结构、存储结构和相适应的运算（结构的行为特征）。,数据元素,数据结构-第1章 绪论,16,逻辑结构 数据元素之间的逻辑关系，与计算机无关。可用一个二元组抽象表示：Data_Structure=(D,R)D数据元素的有穷集合，RD上关系的有穷集合。例 设有数据结构 B=(D,R)，其中 D=d1,d2,d3,d4,d5,d6，R=r，r=,，试画出其逻辑结构图。,数据结构-第1章 绪论,17,四种基本的

6、逻辑结构,（以班级学生关系为例）(1)集合结构 数据元素除了“属于同一集合”的联系之外，没有其它的关系。(2)线性结构 数据元素之间存在一对一的关系。(3)树型结构 数据元素之间存在一对多的关系。(4)图状结构或网状结构 数据元素之间存在多对多的关系。,成员关系,长幼关系,管理关系,朋友关系,数据结构-第1章 绪论,18,例 铺设城市通信管线，使总投资最少？,逻辑结构：图状结构,数据结构-第1章 绪论,19,存储结构（物理结构）：指数据的逻辑结构在计算机存储器中的映象表示。数据元素的映象 用二进制位(bit)的位串表示数据元素。每个数据元素的映象称为结点 每个数据项的映象称为数据域关系的映象两

7、种基本方法及其组合使用。顺序映象：以相对的存储位置表示关系链式映象：以附加信息(指针)表示关系在不同的编程环境下，存储结构有不同的描述方式。用高级程序语言编程时，通常可用其提供的数据类型描述。,数据结构-第1章 绪论,20,数据存储方式的四种常用结构,(1)顺序存储：数据元素依次放在连续的存储单元中。a1 a2.ai.an(2)链式存储：在存储结点中增加若干指针域，记录后继或者相关结点的地址（指针）。a1 1220.a3 1342.a2 1072.,1000 1004,1000 1004 1072 1076 1220 1224,指针,结点,结点,数据结构-第1章 绪论,21,(3)索引存储：将

8、数据元素分为若干子表，子表的开始位置存放在索引表中。索引表 班级 addr 主表 01 1 02 31 03 54(4)散列存储：根据数据元素的关键字值，由散列函数计算出存储地址。LOC(ai)=H(key)432 713 王小二 李一凡,1 a12 a2 31 a31,数据结构-第1章 绪论,22,运算（操作）：在数据逻辑结构上定义的一组数据被使用的方式，其具体实现要在存储结构上进行。几种常用的运算有：(1)建立数据结构(6)检索*(2)清除数据结构(7)更新(3)插入数据元素(8)判空和判满*(4)删除数据元素(9)求长*(5)排序*操作为引用型操作，即数据值不发生变化；其它为加工型操作。

9、,数据结构-第1章 绪论,23,数据的逻辑结构+运算的定义-面向用户（抽象数据类型）概念层 数据的存储结构+运算的实现-面向计算机 实现层,分层模型,数据结构-第1章 绪论,24,1.3 算法的描述和分析,1.3.1 算法的概念 建立在数据结构基础上的、求解问题的一系列确切的步骤。一个算法必须满足以下五个重要特性有穷性：对任何合法输入执行有穷步后能结束。确定性：每条指令必须有确切的含义。可行性：算法的每一条指令均能执行。输入：有零个或多个输入。输出：有一个或多个输出。,数据结构-第1章 绪论,25,评价算法优劣的基本标准正确性可读性健壮性高效性（高效率与低存储量）算法效率的度量时间复杂度空间复

10、杂度,数据结构-第1章 绪论,26,1.3.2 算法的描述,数据结构是算法处理的对象，也是实现算法的基础。选择描述工具的原则 不依赖于具体计算机与具体程序设计语言的一种形式化语言，可用于描述或表达算法思想。本课程采用类 C语言 或 伪码语言特点 它描述的算法自然易懂，具有较好的可移植性。算法格式 void 函数名(参数表)返回值的类型 函数名(参数表)/算法说明/算法说明 语句序列 语句序列/函数名/函数名,包括顺序、判定和重复三种基本控制结构和自然语言成分,数据结构-第1章 绪论,27,赋值语句,变量名=表达式；变量名1=变量名2=变量名n=表达式；(变量名1,变量名2,变量名n)=(表达式

11、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

12、 条件n：语句序列n；break;default:语句n+1；,数据结构-第1章 绪论,29,循环语句,while（条件表达式）语句；,do 语句序列；while（条件表达式）；,break；/强制循环结束,continue；/强制循环继续,for（赋初值表达式；条件；修改表达式）语句；,数据结构-第1章 绪论,30,输入输出语句,scanf(变量表)；,printf(变量表)；,转移语句,goto 语句标号；,引用语句,函数名(参量表)；,变量名=函数名(参量表)；,返回语句,return；,Return 表达式；,exit(异常代码)；,注释语句,/注释内容,/*注释内容*/,例 冒泡排序

13、算法,数据结构-第1章 绪论,31,void bubble_sort(int a,int n)/将a中n个数据序列重新排列成自小至大有序的整数序列 for(i=n-1,change=TRUE;i=1/bubble_sort,数据结构-第1章 绪论,32,一些约定,1）预定义常量和类型：/函数结果状态代码#define TRUE 1#define FALSE 0#define OK 1#define ERROR 0#define INFEASIBLE-1#define OVERFLOW-2/Status作为函数的类型，其值是函数结果状态代码typedef int Status;2）数据元素类型约

14、定为ElemType，使用时按需定义,数据结构-第1章 绪论,33,1.3.3 算法分析 算法效率的度量,一个具体问题的数据对象往往可以采用多种存储方式的一种，一个问题的解决又常常有多种可用的算法。,数据结构-第1章 绪论,34,通常有两种衡量算法效率的方法:,事后统计法 利用计算机内记时功能，不同算法的程 序可以用一组或多组相同的统计数据区分,事前分析估算法时间复杂度(渐进时间复杂度)空间复杂度,缺点：必须执行程序 其它因素掩盖算法本质,和算法执行时间相关的因素,(1)程序运行时所需输入的数据总量（问题规模）(2)对源程序进行编译所需时间(3)计算机执行每条指令所需时间(4)程序中指令重复执

15、行的次数,如何估算算法的时间复杂度？,从算法中选取一种对所研究的问题来说执行最频繁的基本操作为原操作,当问题规模 n 相当大时,该原操作执行时间占算法总执行时间的绝大部分,所以,把该原操作在算法中重复执行的次数(频度)作为算法运行时间的衡量准则。可近似认为：算法的执行时间 与 原操作的频度 成正比 估算时间复杂度时取频度的阶次,时间复杂度,n问题规模，一般为数据的输入量算法的时间复杂度算法中各语句的频度之和T(n)T(n)=O(f(n)大O表示法,时间复杂度,O的含义 存在正的常数c和n0，使得当n n0时，0 T(n)c*f(n)表示随着问题规模 n 的增长,算法执行时间的增长率和 f(n)

16、的增长率相同,称 T(n)为算法的渐近时间复杂度，简称时间复杂度，即，当n 时 T(n)/f(n)常数。,常用的时间复杂度频率计数,算法中常用的时间复杂度频率计数有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),时间复杂度的求法计算T(n)从T(n)中推断f(n)影响算法时间复杂度的因素问题的规模输入实例的初态,时间复杂度计算步骤,最坏时间复杂度,定义：算法在最坏情况下

17、的时间复杂度，即为分析估计算法在最坏情况下执行时间的上界。,数据结构-第1章 绪论,43,例1 交换i和j的内容(1)temp=i;(2)i=j;(3)j=temp;解：T(n)=3 记作T(n)=O(1),数据结构-第1章 绪论,44,例2 nn矩阵相乘的算法语句 for(i=1;i=n;i+)n+1 for(j=1;j=n;j+)n(n+1)ci,j=0;n2 for(k=1;k=n;k+)n2(n+1)ci,j=ci,j+ai,k*bk,j;n3 解：语句频度 T(n)=2 n3+3 n2+2n+1 当nn0=1时，有T(n)8n3，即c=8，由此取f(n)=n3 则T(n)=O(n3)

18、算法中存在循环时，通常由嵌套层数最深的循环语句的最内层语句决定,数据结构-第1章 绪论,45,例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,数据结构-第1章 绪论,46,2）空间复杂度算法的存储空间输入数据所占空间程序本身所占空间辅助变量所占空间空间复杂度 S(n)=O(f(n)表示随着问题规模 n 的增大，算法运行所需存储量的增长率与 f(n)的增长率相同。存储密度 d=数据本身存储量/实际所占存储量,空间复杂度度量,存储空间的固定部分程序指令代码的空间，常数、简单变量、定长成分(如数组元素、结构成分、对象的数据成员等)变量所占的空间可变部分尺寸与实例特性有关的成分变量所占空间、引用变量所占空间、递归栈所用的空间、通过malloc和free命令动态使用的空间,若输入数据所占空间只取决于问题本身，和算法无关，则只需要分析除输入和程序之外的辅助变量所占额外空间。若所需额外空间相对于输入数据量来说是常数，则称此算法为原地工作.若所需存储量依赖于特定的输入,则通常按最坏情况考虑。,