数据结构PPT.ppt
《数据结构PPT.ppt》由会员分享,可在线阅读,更多相关《数据结构PPT.ppt(34页珍藏版)》请在三一办公上搜索。
1、第1章 概述,1.1 什么是数据结构1.2 基本概念和术语1.3 抽象数据类型的表示与实现 1.4 算法和算法分析,提出预备知识,(1)typedef的格式与用法(2)数组(特别是结构体数组)的定义和使用(3)结构体的定义与使用(4)链表的建立、插入与删除(5)递归函数的定义与使用,1938年出生,25岁毕业于加州理工学院数学系,博士毕业后留校任教,28岁任副教授。30岁时,加盟斯坦福大学计算机系,任教授。从31岁起,开始出版他的历史性经典巨著:The Art of Computer Programming他计划共写7卷,然而出版三卷之后,已震惊世界,使他获得计算机科学界的最高荣誉图灵奖,此时
2、,他年仅36岁。,数据结构的创始人克努思,数据结构的兴起和发展,程序设计的实质是什么?,数据表示:将数据存储在计算机中数据处理:处理数据,求解问题,数据结构问题起源于程序设计,数据结构的兴起和发展,数据结构随着程序设计的发展而发展,无结构阶段结构化阶段:数据结构算法程序面向对象阶段:(数据结构算法)程序,数据结构的发展并未终结,1.1 什么是数据结构,计算机求解问题 问题抽象出问题的模型求模型的解问题数值问题、非数值问题 数 值 问 题数学方程 非数值问题数据结构,例1 学籍管理问题表结构,完成什么功能?各表项之间是什么关系?,1.1 什么是数据结构,例2 人机对弈问题树结构,如何实现对弈?各
3、格局之间是什么关系?,1.1 什么是数据结构,例3 教学计划编排问题图结构,1.1 什么是数据结构,如何表示课程之间的先修关系?,1.1 什么是数据结构,数据结构一般包括以下三方面内容:数据元素之间的逻辑关系,也称数据的逻辑结构(Logical Structure);数据的逻辑结构是从逻辑关系上描述数据,与数据的存储无关,是独立于计算机的。数据的逻辑结构可以看作是从具体问题抽象出来的数学模型。,1.1 什么是数据结构,数据结构一般包括以下三方面内容:数据元素及其关系在计算机存储器内的表示,称为数据的存储结构(Storage Structure);数据的存储结构是逻辑结构用计算机语言的实现(亦称
4、为映象),它依赖于计算机语言。,1.1 什么是数据结构,数据结构一般包括以下三方面内容:数据的运算,即对数据施加的操作。数据的运算定义在数据的逻辑结构上,每种逻辑结构都有一个运算的集合。最常用的检索、插入、删除、更新、排序等运算实际上只是在抽象的数据上所施加的一系列抽象的操作。所谓抽象的操作,是指我们只知道这些操作是做什么,而无须考虑如何做。只有确定了存储结构之后,才考虑如何具体实现这些运算。,1.1 什么是数据结构,数据结构是指:数据之间逻辑关系 数据在内存中的映像(存储结构)数据有关操作的算法的总称。,1.1 什么是数据结构,注意:数据结构三方面的关系 数据的逻辑结构、数据的存储结构及数据
5、的运算这三方面是一个整体。孤立地去理解一个方面,而不注意它们之间的联系是不可取的。(1)存储结构是数据结构不可缺少的一个方面:同一逻辑结构的不同存储结构可冠以不同的数据结构名称来标识。例:线性表是一种逻辑结构,若采用顺序方法的存储表示,可称其为顺序表;若采用链式存储方法,则可称其为链表;若采用散列存储方法,则可称为散列表。,1.1 什么是数据结构,注意:数据结构三方面的关系 数据的逻辑结构、数据的存储结构及数据的运算这三方面是一个整体。(2)数据的运算也是数据结构不可分割的一个方面。在给定了数据的逻辑结构和存储结构之后,按定义的运算集合及其运算的性质不同,也可能导致完全不同的数据结构。例:若对
6、线性表上的插入、删除运算限制在表的一端进行,则该线性表称之为栈;若对插入限制在表的一端进行,而删除限制在表的另一端进行,则该线性表称之为队列。更进一步,若线性表采用顺序表或链表作为存储结构,则对插入和删除运算做了上述限制之后,可分别得到顺序栈或链栈,顺序队列或链队列。,1.1 什么是数据结构,注意:数据结构三方面的关系 数据的逻辑结构、数据的存储结构及数据的运算这三方面是一个整体。(3)逻辑结构与存储结构的关系数据的逻辑结构属于用户视图,是面向问题的,反映了数据内部的构成方式;数据的存储结构属于具体实现的视图,是面向计算机的。一种数据的逻辑结构可以用多种存储结构来存储,而采用不同的存储结构,其
7、数据处理的效率往往是不同的。,返回,1.2 基本概念和术语,一、基本术语数据:计算机处理的信息的全体。数据是信息的载体。它能够被计算机识别、存储和加工处理,是计算机程序加工的“原料”。数据元素(Data Element):是数据的基本单位。数据元素也称元素、结点、顶点、记录。一个数据元素可以由若干个数据项(也可称为字段、域、属性)组成。数据项是具有独立含义的最小标识单位。,1.2 基本概念和术语,二、四种基本结构 根据数据元素之间的关系,可以分成以下几种结构:(1)集合(2)线性结构(3)树形结构(4)图状结构,1.2 基本概念和术语,三、描述数据逻辑结构的方法(1)抽象定义法 Data_St
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据结构 PPT

链接地址:https://www.31ppt.com/p-3787974.html