数据结构-第1章.ppt

1、2020/7/11,1,数据结构,第1章 绪论 北京邮电大学电信工程学院 计算机技术中心,2020/7/11,-2-,数据结构,任课教师 徐雅静 Email :phoenix- 办公室：教2-415 电话：2100,2020/7/11,-3-,数据结构,一、学习方法 勤于思考、亲手实践 二、课程组成 实验：30分 平时作业: 10分 期末考试：60分,2020/7/11,-4-,数据结构,数据结构是什么？ 数据结构是人们在长期写程序的过程中总结出来的对数据组织,数据操作方面的精华,2020/7/11,-5-,数据结构,为什么要学习数据结构？ 数据结构就是教你怎样用最精简的语言，利用最少的资源（

2、包括时间和空间）编写出最优秀最合理的程序。 换句话说数据结构存在的意义就是使程序最优化。,2020/7/11,-6-,数据结构不是教你怎样才能编程，而是教你怎样才能编好程，一种思维方式的学习。,2020/7/11,-7-,数据结构在软件开发中的地位,系统分析,系统实现,系统维护,系统设计,2020/7/11,-8-,思考题,题目： 已知有n个整数的序列，查找指定数值key是否在该序列中，如果存在，找出该数值在序列中的位置。,1、数据组织,2、数据操作,2020/7/11,-9-,算法实现,int search(int a, int n, int key) int i； for (i=0; in

3、; i+) if(ai=key) return i+1; return 0; ,如何优化？,1、分析程序耗时的地方,2020/7/11,-10-,分析程序耗时的关键点,int search(int a, int n, int key) for (int i=0; in; i+) if(ai=key) return i+1; return 0; ,二次比较,1、训练思维方式？,2020/7/11,-11-,经典的顺序查找,int search(int a, int n, int key) a0 = key; for (int i=n; ai!=key ; i-); return i; ,哨兵,从

4、后向前查找,2020/7/11,-12-,总结,我们做了哪些事情？ 1 数据组织 2 数据操作（处理数据的策略） 3 分析程序执行效率 4、优化,2020/7/11,-13-,教学要求,提高分析能力 分析计算机处理的数据特性 选择合理的逻辑结构、存储结构及相应算法 初步掌握算法的时间和空间分析的技术 数据抽象能力 提高实践能力 编程结构清楚，正确易读。 优化程序,2020/7/11,-14-,课程安排：共40课时,1 绪论 2 线性表 3 栈、队列、串 4 多维数组 5 树和二叉树 6 图 7 查找 8 排序,2020/7/11,-15-,课程安排：共40课时,2020/7/11,-16-,第

5、一章 绪论,计算机能够处理哪些问题？ 数值计算 非数值计算：控制、管理、数据分析等 数据结构用来解决非数值计算问题，包括 如何组织数据？ 如何操作数据？,2020/7/11,-17-,1.1 数据结构的发展,起源 1968年克努思教授开创了数据结构的最初体系，著作计算机程序设计艺术 20世纪70年代，数据结构进入大学课堂,2020/7/11,-18-,1.1 数据结构的发展,发展 1971年Niklaus Wirth提出结构化程序设计，并给出了一个著名公式： 算法 + 数据结构 = 程序 Algorithm + Data Structures = Programs 算法: 处理问题的策略 数据

6、结构: 问题的数学模型 程序: 为计算机处理问题编制一组指令集,2020/7/11,-19-,1.1 数据结构的发展,目前 面向对象阶段的数据结构采用： 思想：1）数据之间的关系 2）针对这些关系的操作,2020/7/11,-20-,1.2 数据结构的研究对象,问题的引入 计算机解决一个具体问题的步骤 抽象出问题模型 提取对象 找出关系 自然语言描述 设计算法 编程调试,2020/7/11,-21-,1.2 数据结构的研究对象,举例 1、学籍管理 2、人机对弈 3、电话号码查询问题 4、田径赛的时间安排问题,2020/7/11,-22-,非数值计算问题的描述和处理,例1 学籍管理问题,2020

7、/7/11,-23-,非数值计算问题的描述和处理,例2.人机对弈问题树形结构,2020/7/11,-24-,例3：电话号码查询问题,题目 编写一个程序，查询某个城市或单位的私人电话号码。对于任意给出一个姓名，若他有电话号码，则要迅速找到其电话号码。 提示： 1、电话号码表的存储结构 2、针对不同的结构的查找算法,2020/7/11,-25-,例3 ：电话号码查询问题,方法一 数据结构： 无规则的任意排列 算法： 从头开始顺序查找 缺点： 查找速度慢,2020/7/11,-26-,例3 ：电话号码查询问题,方法二 数据结构 建立索引表 算法 分块查找 优点 执行效率提高,2020/7/11,-2

8、7-,例3 ：电话号码查询问题,扩展思维 如果要求按电话号码查询人名，如何设计存储结构和算法？,2020/7/11,-28-,六个项目跳高A、跳远B、标枪C、铅球D、100米E、200米F，五名选手的选择的项目如下：,例4：田径赛时间安排,如何安排比赛使时间最短？,2020/7/11,-29-,数据结构建模,我们可以使用图结构来表示 结点：比赛项目 连线：这两项不能同时进行,如果结点之间无连线则表示？,2020/7/11,-30-,数据结构分析,A，C,B，D,E,F,2020/7/11,-31-,数据结构存储实现,如何存储这张图？ 数组？,二维数组,2020/7/11,-32-,数据结构算法

9、实现,算法 1）如何生成图中结点的关系？ 2）如何判断图中结点是否相联？ 3）,2020/7/11,-33-,数据结构算法实现,2020/7/11,-34-,扩展思维,地图染色问题 地图上相邻的国家使用不同的颜色标注，则最少使用多少种颜色？,2020/7/11,-35-,总结,数值计算 比如：概率统计问题、求极限、求面积这类的问题，解决的方法：数学建模、公式推导。 非数值计算 比如：学籍管理问题、对弈问题，解决的方法：数据结构。,2020/7/11,-36-,1.3 数据结构的基本概念,构成数据元素的最小单位,数据的基本单位,相同性质的数据元素的集合,所有能被计算机处理的符号,2020/7/1

10、1,-37-,1.3 数据结构的基本概念,找出对应的数据项、数据元素、数据对象？,2020/7/11,-38-,1.3 数据结构的基本概念,什么是数据结构？,2020/7/11,-39-,逻辑结构4种,集合,线性,树,图,数据结构不讨论集合,2020/7/11,-40-,逻辑结构用途,学籍管理系统 对弈问题 地图染色问题,线性,树,图,2020/7/11,-41-,存储结构2种,1、顺序结构 利用元素在存储器中的相对位置表示数据之间的逻辑关系，比如：数组 2、链式结构 借助指示元素存储地址的指针表示数据之间的逻辑关系，比如：单链表,2020/7/11,-42-,存储结构和逻辑结构的关系,关系

11、每一种逻辑结构都可以使用这两种存储结构来实现， 关键：针对不同的应用，算法效率不同。,2020/7/11,-43-,抽象数据类型ADT,为什么要使用ADT? 数据结构不针对任何一种具体的程序设计语言，因此，数据结构中使用ADT来描述一个数据结构以及定义在该结构上的操作。,2020/7/11,-44-,抽象数据类型ADT,注意 ADT的设计不涉及实现细节 C+中的模板类体现了ADT的思想,2020/7/11,-45-,1.4 算法分析,构成一个算法的5要素 1）输入 2）输出 3）有穷性 4）确定性 5）可行性 算法与具体的程序设计语言无关，算法的具体实现就是程序。,2020/7/11,-46-

12、,1.4 算法分析,如何评价一个算法？ 1）正确性 2）鲁棒性（健壮性） 3）简单性 4）抽象性 5）高效性,2020/7/11,-47-,1.4 算法分析,如何描述一个算法？ 1）自然语言 2）流程图：适合简单的算法 3）程序设计语言：针对具体语言的实现 4）伪代码：最适合算法的描述,2020/7/11,-48-,1.4 算法分析,如何度量一个算法的效率？ 1）时间效率 使用时间复杂度来计算 2）空间效率 使用空间复杂度来计算 一般采用上述两种方法对算法进行事先估算来进行评价。,2020/7/11,-49-,算法分析,时间复杂度 频度：每条语句执行的次数 时间耗费：所有语句执行次数的总和,2

13、020/7/11,-50-,时间耗费?,求下面这段代码的时间耗费(n0)？ for(int i=0; in; i+) n+1 for(int j=i; jn; j+) n*(n+3)/2 x+; n*(n+1)/2,时间耗费： T(n)=n2+3n+1 时间复杂度：记作O(n2),2020/7/11,-51-,时间复杂度,时间复杂度T(n) 本质：所有语句频度之和，一般为问题的规模的函数 记作: T(n) = O(f(n) n-无穷大 表示: 随着问题规模 n 的增大，算法执行时间的增长率和 f(n) 的增长率相同。 例如： limT(n)/n2 = lim(n2+3n+1)/n2=1 说明T

14、(n)和n2是同价的，记作O(n2).,2020/7/11,-52-,时间复杂度,x=x+1; O(1) for(int i=0;in;i+) x+; O(n) for(int i=0;in;i+) for(int j=0;jm;j+) x+; O(n*m) or O(n2) for(int i=1;in; i=2*i) +x; O(log2n),2020/7/11,-53-,算法分析,空间复杂度 算法在执行过程中，需要的辅助空间的数量。辅助空间是指除了算法本身和输入和输出以外临时开辟的空间。也是问题规模n的函数，计算方法与时间复杂度类似。,本章总结,绪 论,数据结构,算 法,基本概念,逻辑结

15、构,存储结构,数据 数据元素 数据对象 ADT,逻辑结构 数据结构 的分类,存储结构 常用存储 方法,基本概念,算法分析,算法 算法特性 评价算法 描述算法,问题规模 基本语句 时间复杂度 大O记号,关 系,2020/7/11,-55-,思考题,如何生成不重复的随机数？ 题目： 生成值是1-7的7个不同的随机数，考虑时间效率,2020/7/11,-56-,思考1,公元5世纪末，我国古代数学家张丘建在它所撰定的算经中，提出这样一个问题：“鸡翁一，值钱五；鸡母一，值钱三，鸡雏三，值钱一，百钱买百鸡，问鸡翁、母、雏各几何？” 试设计算法求解该问题，并分析你的算法的时间复杂度。,2020/7/11,-57-,关键函数,void main() for(int i=0; i20; i+) for(int j=0;j33-i; j+) int k=100-i-j; if (5*i+3*j+k/3.0=100) cout鸡翁：i 鸡母：j 鸡雏：kendl; 时间复杂度：O(n2),2020/7/11,-58-,运行结果,2020/7/11,-59-,思考2,一个小孩买了价值少于1美元的糖，并将1美元的钱交给售