(1)--第1章 绪论-基本概念数据结构.ppt

《(1)--第1章 绪论-基本概念数据结构.ppt》由会员分享，可在线阅读，更多相关《(1)--第1章 绪论-基本概念数据结构.ppt（27页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、-基本概念第1章 绪论教学目标教学目标1.了解数据结构研究的主要内容2.掌握数据结构中涉及的基本概念3.掌握算法的时间、空间复杂度及其分析的简易方法 1.1数据结构的研究内容1.2基本概念和术语1.3抽象数据类型的表示与实现1.4算法与算法分析教学内容教学内容&N.沃思（NiklausWirth)教授提出：程序=算法+数据结构&电子计算机的主要用途：早期：主要用于数值计算后来：处理逐渐扩大到非数值计算领域，能处理多种复杂的具有一定结构关系的数据 1.1 1.1 数据结构数据结构的研究内容的研究内容书目自动检索系统书目自动检索系统登录号：书名：作者名：分类号：出版单位：出版时间：价格：书目卡片书

2、目文件按书名按作者名按分类号索引表线性表人机对奕问题人机对奕问题树.22:25 多叉路口交通灯管理问题多叉路口交通灯管理问题CEDABABACADBABCBDDADBDCEAEBECED图顶点：顶点：一条通路连线：连线：不能同时通行染色：染色：有连线的两个顶点不能具有相同颜色设计出合适的数据结构及相应的算法即：首先要考虑对相关的各种信息如何表示、组织和存储？非数值计算的问题非数值计算的问题 研究非数值计算的程序设计问题中计算机的研究非数值计算的程序设计问题中计算机的操作对操作对象象以及它们之间的以及它们之间的关系和操作关系和操作。数据结构的研究内容数据结构的研究内容数据结构数据结构所处的地位所

3、处的地位介于数学、计算机硬件和计算机软件三者之间的一门核心课程1.2 1.2 基本基本概念和术语概念和术语1、数据（data)所有能输入到计算机中去的描述客观事物的符号u数值性数据u非数值性数据（多媒体信息处理）2、数据元素（dataelement）数据的基本单位，也称结点（node）或记录（record）3、数据项（dataitem）有独立含义的数据最小单位，也称域(field)u整数数据对象N=0,1,2,u学生数据对象学生记录的集合4、数据对象(DataObject)：相同特性数据元素的集合，是数据的一个子集1.2 1.2 基本基本概念和术语概念和术语5、数据结构（DataStructu

4、re）是相互之间存在一种或多种特定关系的数据元素的集合。数据结构是带“结构”的数据元素的集合，“结构”就是指数据元素之间存在的关系。1.2 1.2 基本基本概念和术语概念和术语&数据结构的两个层次：&逻辑结构-数据元素间抽象化的相互关系，与数据的存储无关，独立于计算机，它是从具体问题抽象出来的数学模型。&存储结构（物理结构）-数据元素及其关系在计算机存储器中的存储方式。22:25 通常要求同一逻辑结构中的所有数据元素具有相同的特性，这意味着（）。数据具有同一特点不仅数据元素所包含的数据项的个数要相同，而且对应数据项的类型要一致每个数据元素都一样数据元素所包含的数据项的个数要相等ABCD提交单选

5、题单选题单选题1分划分方法一划分方法一（1）线性结构-有且仅有一个开始和一个终端结点，并且所有结点都最多只有一个直接前趋和一个后继。例如：线性表、栈、队列、串（2）非线性结构-一个结点可能有多个直接前趋和直接后继。例如：树、图逻辑结构逻辑结构线性结构线性结构一个对一个，如线性表、栈、队列树形结构树形结构一个对多个，如树集合集合数据元素间除“同属于一个集合”外，无其它关系图形结构图形结构多个对多个，如图划分方法二划分方法二在数据结构中，从逻辑上可以把数据结构分成（）.动态结构和静态结构紧凑结构和非紧凑结构线性结构和非线性结构内部结构和外部结构ABCD提交单选题单选题1分存储结构分为：存储结构分为

6、：顺序存储结构借助元素在存储器中的相对位置来表示数据元素间的逻辑关系链式存储结构借助指示元素存储地址的指针表示数据元素间的逻辑关系存储结构存储结构数据的存储结构是指（）。数据所占的存储空间量数据的逻辑结构在计算机中的表示数据在计算机中的顺序存储方式存储在外存中的数据ABCD提交单选题1分元素元素n n.元素元素i i.元素元素2 2元素元素1 1LoLo+mLo+(i-1)*mLo+（n-1)*m存储地址存储地址存储内容存储内容Loc(元素元素i)=Lo+（i-1)*m顺序存储顺序存储1536元素元素2 21400元素元素1 11346元素元素3 3 元素元素4 41345h存储地址存储地址

7、存储内容存储内容 指针指针 1345 1345 元素元素1 1 14001400 1346 1346 元素元素4 4 .14001400 元素元素2 2 1536 1536 .1536 1536 元素元素3 3 1346 1346 链式存储链式存储 hp逻辑结构和存储结构都相同逻辑结构和存储结构都相同,但运算不同但运算不同,则数据结则数据结构不同构不同.例如例如,栈与队列栈与队列p对于一种数据结构对于一种数据结构,常见的运算常见的运算插入插入删除删除修改修改查找查找排序排序数据的运算数据的运算 数据的逻辑结构 数据的存储结构数据的运算：插入、删除、修改、查找、排序 线性结构 非线性结构 顺序存储 链式存储线性表 栈、队列 串、数组树形结构图形结构数据结构三要素数据类型数据类型是一组性质相同的值的集合,以及定义于这个集合上的一组运算的总称1.2 1.2 基本基本概念和术语概念和术语(ADT:Abstract Data Types)u更高层次的数据抽象u由用户定义，用以表示应用问题的数据模型u由基本的数据类型组成,并包括一组相关的操作1.31.3抽象数据类型抽象数据类型抽象数据类型可以用以下的三元组来表示：ADT=（D，S，P）数据对象D上的关系集D上的操作集ADT抽象数据类型名数据对象：数据关系：基本操作：ADT抽象数据类型名ADT常用定义格式