数据结构课件、代码第1章绪论-48-2

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

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

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

4、2080,2120,(1),(2),(3),40Byte,张三 . 3118 3060 1596 王五 李四 .,2040,3060,3118,数据结构-第1章 绪论,12,数据结构的作用范畴,抽象数据对象的数学模型（逻辑结构） 例：图状结构 明确操作（运算的定义） 例：查找、插入、 在存储结构上映射数据（物理/存储结构） 例：顺序存储 实现操作,数据结构-第1章 绪论,14,1.2 基本概念和术语,数据 被计算机加工处理的对象。 数据元素（记录、表目） 数据的基本单位，是数据集合中的一个个体。 一个数据元素可由若干个数据项组成。数据项是数据结构中讨论的数据的最小单位。,原子项,数据结构-第1

5、章 绪论,15,数据对象 是性质相同的数据元素的集合，是数据的一个子集。 学号 姓名 班号 性别 出生日期 入学成绩 001 刘影 01 女 19840417 623 002 李恒 01 男 19831211 679 003 陈诚 02 男 19840910 638 数据结构 具有结构的数据元素的集合。它包括数据对象的逻辑结构、存储结构和相适应的运算（结构的行为特征）。,数据元素,数据结构-第1章 绪论,16,逻辑结构 数据元素之间的逻辑关系，与计算机无关。 可用一个二元组抽象表示： Data_Structure = (D,R) D数据元素的有穷集合，RD上关系的有穷集合。 例 设有数据结构

6、B = (D,R) ， 其中 D= d1, d2, d3, d4, d5, d6， R=r， r=, , , , ， 试画出其逻辑结构图。,数据结构-第1章 绪论,17,四种基本的逻辑结构,（以班级学生关系为例） (1)集合结构 数据元素除了“属于同一集合”的联系之外，没有其它的关系。 (2)线性结构 数据元素之间存在一对一的关系。 (3)树型结构 数据元素之间存在一对多的关系。 (4)图状结构或网状结构 数据元素之间存在多对多的关系。,成员关系,长幼关系,管理关系,朋友关系,数据结构-第1章 绪论,18,例 铺设城市通信管线，使总投资最少？,逻辑结构：图状结构,数据结构-第1章 绪论,19,

7、存储结构（物理结构）：指数据的逻辑结构在计算机存储器中的映象表示。 数据元素的映象 用二进制位(bit)的位串表示数据元素。 每个数据元素的映象称为结点 每个数据项的映象称为数据域 关系的映象 两种基本方法及其组合使用。 顺序映象：以相对的存储位置表示关系 链式映象：以附加信息(指针)表示关系 在不同的编程环境下，存储结构有不同的描述方式。 用高级程序语言编程时，通常可用其提供的数据类型描述。,数据结构-第1章 绪论,20,数据存储方式的四种常用结构,(1)顺序存储：数据元素依次放在连续的存储单元中。 a1 a2 . ai . an (2)链式存储：在存储结点中增加若干指针域，记录后继或者相关

8、结点的地址（指针）。 a1 1220 . a3 1342 . a2 1072 .,1000 1004,1000 1004 1072 1076 1220 1224,指针,结点,结点,数据结构-第1章 绪论,21,(3)索引存储：将数据元素分为若干子表，子表的开始位置存放在索引表中。 索引表 班级 addr 主表 01 1 02 31 03 54 (4)散列存储：根据数据元素的关键字值，由散列函数计算出存储地址。LOC(ai)=H(key) 432 713 王小二 李一凡,1 a1 2 a2 31 a31 ,数据结构-第1章 绪论,22,运算（操作）：在数据逻辑结构上定义的一组数据被使用的方式，其

9、具体实现要在存储结构上进行。 几种常用的运算有： (1)建立数据结构 (6)检索* (2)清除数据结构 (7)更新 (3)插入数据元素 (8)判空和判满* (4)删除数据元素 (9)求长* (5)排序 *操作为引用型操作，即数据值不发生变化；其它为加工型操作。,数据结构-第1章 绪论,23,数据的逻辑结构+运算的定义-面向用户 （抽象数据类型） 概念层 数据的存储结构+运算的实现-面向计算机 实现层,分层模型,数据结构-第1章 绪论,24,1.3 算法的描述和分析,1.3.1 算法的概念 建立在数据结构基础上的、求解问题的一系列确切的步骤。 一个算法必须满足以下五个重要特性 有穷性：对任何合法

10、输入执行有穷步后能结束。 确定性：每条指令必须有确切的含义。 可行性：算法的每一条指令均能执行。 输入：有零个或多个输入。 输出：有一个或多个输出。,数据结构-第1章 绪论,25,评价算法优劣的基本标准 正确性 可读性 健壮性 高效性（高效率与低存储量） 算法效率的度量 时间复杂度 空间复杂度,数据结构-第1章 绪论,26,1.3.2 算法的描述,数据结构是算法处理的对象，也是实现算法的基础。 选择描述工具的原则 不依赖于具体计算机与具体程序设计语言的一种形式化语言，可用于描述或表达算法思想。 本课程采用类 C语言 或 伪码语言 特点 它描述的算法自然易懂，具有较好的可移植性。 算法格式 vo

11、id 函数名(参数表) 返回值的类型 函数名(参数表) /算法说明 /算法说明 语句序列 语句序列 /函数名 /函数名,包括顺序、判定和重复三种基本控制结构和自然语言成分,数据结构-第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 ( 条件表达式) 语句;

12、 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 语句序列； whil

13、e （条件表达式）；,break；/强制循环结束,continue；/强制循环继续,for （赋初值表达式；条件；修改表达式） 语句；,数据结构-第1章 绪论,30,输入输出语句,scanf (变量表)；,printf (变量表)；,转移语句,goto 语句标号；,引用语句,函数名(参量表)；,变量名=函数名(参量表)；,返回语句,return；,Return 表达式 ；,exit (异常代码)；,注释语句,/注释内容,/* 注释内容 */,例 冒泡排序算法,数据结构-第1章 绪论,31,void bubble_sort(int a , int n ) /将a中n个数据序列重新排列成自小至大有

14、序的整数序列 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）数据元素类型约定为ElemType，使用时按需定义,数据结构-第1章 绪论,33,1.3.3 算法分析 算法效率的度

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

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

17、杂度，简称时间复杂度，即， 当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) 影响算法时间复杂度的因素 问题的规模 输入实例的初态,时间复杂度计算步骤,最坏时间复杂度,定义： 算法在最坏情况下的时间复杂度，即为分析

18、估计算法在最坏情况下执行时间的上界。,数据结构-第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