• / 35
  • 下载费用:10 金币  

实用数据结构基础(中国铁道出版社 第三版)第1章 绪论.ppt

关 键 词:
实用数据结构基础(中国铁道出版社 第三版)第1章 绪论.ppt
资源描述:
第1章 绪论,2011年5月11日星期三,1,第1章 绪论,知 识 点数据结构中常用的基本概念和术语 算法描述和分析方法 难 点 算法时间复杂度 要 求 了解数据的逻辑结构和物理结构;了解算法对于程序设计的重要性 ;掌握算法时间复杂度的分析方法 。,目 录,1-1 什么是数据结构 1-2 数据的逻辑结构 1-3 数据的存储结构1-4 算法和算法分析 小 结 实验1习题1,1-1 什么是数据结构1-1-1 从数据结构实验演示认识数据结构《数据结构实验演示》1-1-2 数据结构研究的内容用计算机解决具体问题需要经过的步骤: (1)从具体问题抽象出适当的数学模型; (2)设计解数学模型的算法; (3)编制程序、运行并调试程序,直到解决实际问 题。,【例1-1】学生入学情况登记问题表1-1 学生入学情况简表,【例1-2】井字棋对奕问题,,【例1-3】七桥问题,,图1-2 七桥问题,图1-3 欧拉回路,1-2 数据的逻辑结构,1-2-1 基本概念 1.数据(Data)数据是信息的载体,是对客观事物的符号表示。通俗的说,凡是能被计算机识别、存取和加工处理的符号、字符、图形、图象、声音、视频信号等一切信息都可以称为数据。 2. 数据元素(Data Element)数据元素是对现实世界中某独立个体的数据描述,是数据的基本单位。数据元素也称为结点(Node),在计算机中,常作为一个整体来处理。,3.数据项(Data Item)数据项是数据不可分割的、具有独立意义的最小数据单位,是对数据元素属性的描述。数据项也称为域,或字段(Field)。 4.数据对象(Data Object) 数据对象是性质相同的数据元素的集合,是数据的一个子集。例如在“学生入学情况表”中,数据对象就是全体学生记录的集合。 5.数据逻辑结构(Data Structure)数据的逻辑结构是相互之间存在的一种或多种特定关系的数据元素的集合。,(1)集合——结构中数据元素之间,除了“同属于一个集合”关系之外,别无其它关系。 (2)线性结构——结构中的数据元素之间存在着“一对一”的关系。 (3)树形结构——结构中的数据元素之间存在着“一对多”的关系。 (4)图形结构——结构中的数据元素之间存在着“多对多”的关系。,图1-4所示为四类基本数据结构的示意图,,,,,,,,,,,,,,,,,(b)线性结构,,,,,,,,,,,,,(c)树形结构,(d)图形结构,图1- 4 四类基本数据结构的示意图,,,,,,,,,,(a)集合结构,,,1-2-2 逻辑结构的描述,数据元素之间的逻辑关系,称为数据的逻辑结构。一个数据的逻辑结构可以用二元组来表示:G=(D,R)其中:D是数据元素的集合;R是D上所有数据元素之间关系的有限集合。 【例1-4】一种数据结构Line=(D,R),其中:D={01,02,03,04,05,06,07,08,09,10}R={r}r={,,,,,,,,},【例1-5】一种数据结构Tree=(D,R),其中:D={01,02,03,04,05,06,07,08,09,10}R={r}r={,,,,,,,,},,图1- 6 树形结构,【例1-6】一种数据结构 graph=(D,R),其中:D= {a,b,c,d,e}R={r}r={(a,b),(a,d),(b,d),(b,c),(b,e),(c,d),(d,e)},图1- 7 图形结构,圆括号表示的关系集合是无方向的,如(a,b)表示从a到b之间的边是双向的。其特点是各个结点之间都存在着多对多(M:N)的关系,即每个结点都可以有多个直接前驱或多个直接后继,如图1-7所示,我们把具有这种特点的数据结构叫做图形结,简称图。,1-3 数据的存储结构,数据元素及其关系在计算机存储器内的表示,称为数据的存储结构。四种不同的存储结构: 1. 顺序存储顺序存储结构的特点是借助元素在存储器中的相对位置来表示数据元素之间的逻辑关系。例如,一个字母占一个字节,输入A、B、C、D、E,并存储在2000起始的连续的存储单元,如图1-8为顺序存储结构。,2000,2001,2002,2003,2004,图1-8 顺序存储结构,……,2. 链式存储借助指示元素存储地址的指针(Pointer)来表示数据元素之间的逻辑关系。例如,图1-9为表示复数z=2.0+4.8i的链式存储结构。其中地址2000存放实部,地址2100存放虚部,实部与虚部的关系用值为”2100”的指针来表示。,3. 索引存储索引存储是在原有存储数据结构的基础上,附加建立一个索引表,索引表中的每一项都由关键字和地址组成。索引表反映了按某一个关键字递增或递减排列的逻辑次序,主要作用是为了提高数据的检索速度。 4. 散列存储散列存储是通过构造散列函数来确定数据存储地址或查找地址的。例如:某一
展开阅读全文
  微传网所有资源均是用户自行上传分享,仅供网友学习交流,未经上传用户书面授权,请勿作他用。
0条评论

还可以输入200字符

暂无评论,赶快抢占沙发吧。

关于本文
本文标题:实用数据结构基础(中国铁道出版社 第三版)第1章 绪论.ppt
链接地址:https://www.weizhuannet.com/p-10054327.html
微传网是一个办公文档、学习资料下载的在线文档分享平台!

微传网博客

网站资源均来自网络,如有侵权,请联系客服删除!

 网站客服QQ:80879498  会员QQ群:727456886

copyright@ 2018-2028 微传网络工作室版权所有

     经营许可证编号:冀ICP备18006529号-1 ,公安局备案号:13028102000124

收起
展开