数据结构绪论ppt.pptxVIP

;说在课程学习之前;为什么学习数据结构与算法？;为什么学习数据结构？;学时数：64（+16） 教 材：严蔚敏等，数据结构（C语言版），清华大学出版社 参考书： [1]算法导论（第2版），Cormen等，机械工业出版社 [2]计算机程序设计艺术（第3版）（Vol.1-3），D. E. Knuth，清华大学出版社 [3] 高一凡，《数据结构》算法实现及解析(第二版)西安电子科技大学出版社 [4] 唐发根，《数据结构教程》，北京航空航天大学出版社，2005年5月，第2版 [5]王玲主编，《数据结构实验教程》，四川大学出版社，2002年;师生沟通渠道;学习目的与考核形式;第1章 绪论;教学目标;;;1.1 基本概念与术语;1. 1.1数据、数据元素、数据项、数据对象;1.1.2 数据结构;登录号;应用实例2： 智力游戏;; 以上例子的解决，都不是数值计算问题。描述这类非数值问题的数学模型不再是数学方程，而是诸如表、树、图之类的数据结构。 因此简单说来，数据结构是一门研究非数值计算的程序设计中计算机的操作对象以及它们之间的关系和操作等的学科。 主要研究： 数据的逻辑结构--数据关系之间的逻辑关系 数据的存储结构--数据的逻辑结构在计算机中的表示 操作算法--插入、删除、修改、查询、排序等;逻辑结构： 设有一个表(a1,a2,a3,a4,a5)，它的抽象描述可表示为：Line＝（D，S） 其中：D＝{a1,a2,a3,a4,a5}，D表示数据元素的有限集 S＝{a1,a2,a2,a3,a3,a4,a4,a5}， S表示D 上关系的有限集 则：它的逻辑关系图示如下：;应用实例4: 工厂的组织管理。;设一个数据结构的抽象描述为: Tree＝（D，S） 其中：D ＝{r,a,b,c,d,e,f,g,h}, S ＝{r,a,r,b,a,c,a,d,a,e,b,f,e,g ,e,h} 则：它的逻辑关系图示如下： ;应用实例5：田径赛的时间安排问题： 设有六个比赛项目，规定每个选手至多可参加三个项目，有五人报名参加比赛（如下表所示）设计比赛日程表，使得在尽可能短的时间内完成比赛。 ;（1）设用如下六个不同的代号代表不同的项目： 跳高 跳远 标枪 铅球 100米 200米 A B C D E F （2）用顶点代表比赛项目 不能同时进行比赛的项目之间连上一条边。 （3）某选手比赛的项目有边相连,则不能同时比赛。 ;姓名; 一般来说，根据数据元素之间的关系的不同特性，通常有如下4类基本结构： ; 在集合结构中的数据元素之间仅存在“同属于一 个集合”的关系。如下图所示。 ; 元素之间是一一对应的关系，首元素无前趋，尾元素无后继，其他元素都只有一个前驱和后继。; 元素之间存在一对多的关系，其中只有一个元素没有前驱，称为根。其他元素只有一个前驱，但可以有多个后继。; 在图状结构中，每个结点可以有多个前驱和任意个后继。元素之间存在多对多的关系，任何元素之间都可以存在关系。;;;数据的逻辑结构与存储结构密切相关 算法设计 逻辑结构 算法实现 存储结构 ;元素n;1536;应用实例6：电话号码查询问题： 设有一个电话号码薄，它记录了N个人的名字和其相应的电话号码，假定按如下形式安排： (a1，b1)(a2，b2)…(an，bn) 其中ai，bi(i=1，2…n) 分别表示某人的名字和对应的电话号码，要求设计一个算法，当给定任何一个人的名字时，该算法能够打印出此人的电话号码，如果该电话簿中根本就没有这个人，则该算法也能够给出没有这个人的报告。 ;;方法1：顺序存储，顺序查找 ;方法2：建立索引表 ;1.1.3 抽象数据类型;1.1.3 抽象数据类型;1.1.3 抽象数据类型;1.1.3 抽象数据类型;1.2 应用举例----ADT Triplet（P9）;数据结构的主要内容;1.3 算法与算法分析;1.3.1 算法的基本概念;算法的不同直接影响着程序的执行效率;补充：利用timeb函数计算程序段运行的时间;补充：利用timeb函数计算程序段运行的时间;1.3.2 算法描述;1.3.2 算法描述;;例如：抽象数据类型Triplet的表示和实现;1.3.3 算法的评价;1.3.3 算法的评价;;1.3.3 算法的评价;3n+2=O(n) //