第一章数据结构与算法概述.ppt
《第一章数据结构与算法概述.ppt》由会员分享,可在线阅读,更多相关《第一章数据结构与算法概述.ppt(63页珍藏版)》请在三一文库上搜索。
1、写在前面的话,本课程学习的是什么?,学习在思考问题时, 不仅按人的逻辑方式思考,也按计算机的逻辑思维方式思考,学习在解决问题时, 不仅考虑人的处理方式,也要考虑计算机的处理方式,为什么要学数据结构? 数据结构研究什么? 重新理解算法。 如何分析算法的优劣?,第一章 概论,第一问题: 为什么要学数据结构,Data Structure,?,用计算机处理的实际问题可分为两大类问题: 数值计算 非数值计算 数值计算问题: 在计算机发展初期,人们主要应用计算机来完成科学计算,即处理数值计算问题,对于这类问题,可以通过抽象出合适的数学模型,然后设计一个相应的算法来解决。 在建筑设计时计算梁结构的应力要求解
2、线性方程组 预报人口增长情况时要求解微分方程等。 非数值计算问题: 但是随着计算机应用领域的不断扩大,计算机更多地应用于处理非数值计算问题,这类问题涉及到数据元素间复杂的相互关系,一般无法用数学方程来描述。,现实中对象之间的关系,线性关系:如列车中各车箱之间的关系、排队买车票人之间的关系、一叠盘子中各盘子之间的关系等。 层次关系:如学校的组织结构、人的辈分关系等。 网状关系:如城市铁路交通网、电话网、计算机网络等。,实际问题中对象之间的关系 例1:学生成绩管理,学生成绩表,关系:线性 特征:一个直接前趋, 一个直接后继,实际问题中对象之间的关系,例2:“井字棋”的人机对弈,关系:树型 特征:一
3、个直接前趋, 多个直接后继,实际问题中对象之间的关系,例3:交通图的最短路径问题,A4,A2,A6,A3,A1,A5,5,4,7,9,8,6,1,2,关系:图型 特征:多个直接前趋, 多个直接后继,第一问题: 什么要学数据结构,?,解决非数值问题的首要任务是选取一种合适的数据结构表示该问题,然后才考虑如何编写有效的算法。,计算机处理的大多属于非数值计算问题。,第二问题 数据结构研究什么,?,几个基本概念,1. 数据 2. 数据元素 3. 数据项,所有能被输入到计算机中,且能被计算机处理的符号(数值、字符等)的集合。,1.数据:,2.数据元素:,如果把数据作为一个集合,则集合中的每一个独立“个体
4、”称为数据元素。数据元素是数据结构中讨论的基本单位。,数据集合中的所有数据元素的属性相同。,例如:,描述一个学生信息的数据元素,称之为组合项,原子项,3.数据项,数据元素也可以由若干数据项构成。,数据结构的研究内容,研究数据之间的相互关系,即数据的组织形式,包括: 数据元素之间的逻辑关系,也称为数据的逻辑结构(Logical structure)。 数据元素及其关系在计算机存储器内的表示,称为数据的存储结构(storage structure)。 数据的运算,即基于某种存储结构对数据施加的操作或运算。,4. 数据结构:,带结构的数据元素的集合,对于一个有相同特性的数据元素的集合,如果在数据元素
5、之间存在一种或多种特定的关系,则称为一个数据结构。,指的是数据元素之间存在的关系,不同的“关系”构成不同的“结构”,例如,IP地址(IPv4)是一个用四个 3 位的十进制数表示一个数据结构。,166,111,102,2 a1(166),a2(111),a3(102),a4(2),则在数据元素 a1、a2 、 a3 和a4之间存在着“次序”关系 a1,a2、a2,a3、a3,a4,166,111,102, 2 a1 a2 a3 a4,111,166,102, 2 a2 a1 a3 a4,又例,在2行3列的二维数组 a1, a2, a3, a4, a5, a6中六个 元素之间存在什么关系?,行的次
6、序关系: 列的次序关系:,row = ,col = ,a1 a3 a5 a2 a4 a6,a1 a2 a3 a4 a5 a6,从关系或结构分,数据结构可归结为以下四类:,线性结构,树形结构,图状结构,集合结构,5.分类,数据结构包括“逻辑结构” 和“物理结构”两个方面(层次):,逻辑结构 是对数据元素之间的逻辑关系的描述。它对应一个数据元素的集合和定义在此集合上的若干关系;,物理结构 是逻辑结构在计算机中的表示和实现,故又称“存储结构” 。,6. 逻辑结构和物理结构,7. 数据结构的存储结构, 逻辑结构在存储器中的映象,“数据元素”的映象,“关系”的映象,所有数据元素都映象为二进制位串,(32
7、1)10 = (501)8 = (101000001)2,A = (101)8 = (001000001)2,顺序映象 和链式映象,8. 顺序映象,逻辑上相邻的数据元素存储在物理位置也相邻的存储单元里,例如:令 y 的存储位置和 x 的存储位置之间差一个常量 C,而 C 是一个隐含值,整个存储结构中只含数据元素本身的信息,9. 链式映象,以附加信息(指针)表示后继关系,需要用一个和 x 在一起的附加信息指示 y 的存储位置,y x,为方便起见,数据的逻辑结构简称为数据结构,物理结构称为存储结构,结构,运算,逻辑结构,存储结构,+,数据结构,瑞士计算机科学家沃思(N.Wirth)教授提出:,数据
8、结构在计算机科学中的地位,程序设计的实质是对实际问题选择一种好的数据结构,加之设计一个好的算法,而好的算法在很大程度上取决于描述实际问题的数据结构。 数据结构是计算机软件和计算机应用专业的核心课程之一,由于在计算机系统软件和应用软件中都要用到各种数据结构,要想更有效地使用计算机,就必须学习数据结构的有关知识。,数据结构在软件从业人员的知识与技能结构中的地位,数据结构在软件从业人员的知识与技能结构中的地位,编程语言,解决问题的思想,推荐阅读- 程序员杂志,特别策划算法的力量 李开复.算法的力量 百度首席架构师揭密:算法是百度工程师的利器 影响算法世界的十位大师 特别策划程序员的七种武器 左轻候.
9、最基础的数据结构,任何受过专业训练的程序员,对“数据结构”这门课程中涉及到的各种数据结构都不会陌生,但是在实际的编程工作中,大部分的数据结构都不会用到,而且也永远都不会用到。虽然如此,深入地理解基本数据结构的概念和实现细节,仍然是每个程序员的任务。这不仅仅是因为,掌握这些知识将有利于更加正确和灵活地应用它们,而且也是因为,对于语言背后的实现细节的求知欲是一个优秀程序员的素质。 -摘自最基础的数据结构,关于数据结构中的结构,数据的逻辑结构是从逻辑关系上描述数据,它与数据的存储无关,是独立于计算机的,可以看作是从具体问题抽象出来的数学模型。数据的逻辑结构有两大类: 线性结构:线性表 非线性结构:树
10、和图 数据的存储结构是逻辑结构用计算机语言的实现,它是依赖于计算机语言的。数据的存储结构有以下四种基本的存储方法。 顺序存储方法 链接存储方法 索引存储方法 散列存储方法,关于数据结构中的算法,数据的运算是定义在数据的逻辑结构上的,每种逻辑结构都有一个运算的集合。 最常用的运算有查找、插入、删除、更新、排序等。 重点研究的两类基本算法: 查找 排序,本课程的结构,线性表 栈 队列 串 多维数组 树 图 查找 排序,线性结构,非线性结构,算法,第二问题 数据结构研究什么,?,运算,逻辑结构,存储结构,第三问题 重新理解算法Algorithm,算法和算法的分析,一、算法,二、算法设计的原则,三、算
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 第一章 数据结构 算法 概述
链接地址:https://www.31doc.com/p-2255383.html