2 数据结构相关概念.ppt
![资源得分’ title=](/images/score_1.gif)
![资源得分’ title=](/images/score_1.gif)
![资源得分’ title=](/images/score_1.gif)
![资源得分’ title=](/images/score_1.gif)
![资源得分’ title=](/images/score_05.gif)
《2 数据结构相关概念.ppt》由会员分享,可在线阅读,更多相关《2 数据结构相关概念.ppt(50页珍藏版)》请在得力文库 - 分享文档赚钱的网站上搜索。
1、第第2 2章章线性数据结构线性数据结构在此幻灯片插入公司的徽标在此幻灯片插入公司的徽标从从“插入插入”菜单菜单选择图片选择图片找到徽标文件找到徽标文件单击单击“确定确定”重新设置徽标大小重新设置徽标大小单击徽标内任意位置。徽标外部单击徽标内任意位置。徽标外部出现的方框是出现的方框是“调整控点调整控点”使用这些重新设置对象大小使用这些重新设置对象大小如果在使用尺寸调整控点前按下如果在使用尺寸调整控点前按下 shift 键,则对象改变大小但维键,则对象改变大小但维持原比例。持原比例。1065865姓名姓名 学号学号 成绩成绩 班级班级李红李红 2001456 95 6 ABCDEFG第第2 2章章
2、线性数据结构线性数据结构数据结构数据结构的地位的地位综合性基础课;综合性基础课;介于数学、计算机硬件与计算机软件之间的核介于数学、计算机硬件与计算机软件之间的核心课程;心课程;不仅是一般程序设计的基础,而且是设计和实不仅是一般程序设计的基础,而且是设计和实现编译程序、操作系统、数据库系统及其他系现编译程序、操作系统、数据库系统及其他系统程序和大型应用程序的重要基础统程序和大型应用程序的重要基础算法算法+数据结构数据结构=程序程序第第2 2章章线性数据结构线性数据结构数据结构应用实例数据结构应用实例对弈(树)对弈(树)报童送信最短距离(图)报童送信最短距离(图)哈夫曼编码(哈夫曼树)哈夫曼编码(
3、哈夫曼树)调度(排序)调度(排序)搜索(查找)搜索(查找)第第2 2章章线性数据结构线性数据结构数据结构应用实例数据结构应用实例数字视频监控系统数字视频监控系统摄像机摄像机云台:上、下、左、右云台:上、下、左、右镜头:变焦、聚焦镜头:变焦、聚焦报警器报警器位置、类型、状态位置、类型、状态用户用户基本信息基本信息工作信息工作信息联系信息联系信息日志日志存储线性表树图查找排序第第2 2章章线性数据结构线性数据结构图像处理、分析与机器视觉图像处理、分析与机器视觉(第第3版版)Image Processing,Analysis,and Machine Vision第4章 图像分析的数据结构 69 4.
4、1 图像数据表示的层次 69 4.2 传统图像数据结构 70 4.2.1 矩阵 70 4.2.2 链 72 4.2.3 拓扑数据结构 73 4.2.4 关系结构 73 4.3 分层数据结构 74 4.3.1 金字塔 74 4.3.2 四叉树 75 4.3.3 其他金字塔结构 76 第第2 2章章线性数据结构线性数据结构第第2章章 线性数据结构线性数据结构 2.1 基本概念基本概念 2.1.1 数据和数据结构数据和数据结构2.1.2 算法的描述和评价算法的描述和评价2.2 线性表线性表 2.2.1 线性表的定义及操作线性表的定义及操作2.2.2 线性表的线性表的 顺序存储结构顺序存储结构2.2.
5、3 线性表的链式存储结构线性表的链式存储结构2.2.4 循环链表和双向链表循环链表和双向链表2.3 栈和队列栈和队列 2.3.1 栈栈2.3.2 队列队列2.4 串和数组串和数组 2.4.1 串串2.4.2 数组数组第第2 2章章线性数据结构线性数据结构2.1 基基 本本 概概 念念 2.1.1 数据和数据结构数据和数据结构现代数字计算机原是作为数值计算工具而发明的。随着计算机的发展,在计算机的绝大多数应用中,能够存取、处理大量信息的能力却被认为是计算机的首要特征,而它的计算能力在许多情况下已经几乎被人们忽略了。有位美国学者曾批评说:“计计算算机机”这个词只告诉我们以前能做的事,却未道出它的潜
6、能。有鉴于此,人们常常把计算机称作数据处理机数据处理机。第第2 2章章线性数据结构线性数据结构一.什么是数据?数数据据就是是信息的载体,它可以用计算机表示并加工。可以看出,数据这个概念本身是随着计算机的发展而不断扩展的概念。在计算机发展的初期,由于计算机主要用于数值计算,数据指的就是数值。计算机硬件和软件技术的不断发展,扩大了计算机的应用领域,诸如字符、文字、表格、图形、图像、声音等也属于数据的范畴。数数据据就就是是对对客客观观事事物物的的符符号号表表示示,是是可可以以被被计计算算机机处理的处理的“原料原料”。第第2 2章章线性数据结构线性数据结构二二.数数据据元元素素是数据集合中的一个个体,
7、它是数据的基基本本单单位位。例如:全部学生的学籍登记卡组成学生的学籍数据,每个学生的学籍登记卡就是学籍数据的一个数据元素。数据元素可以是一个数或字符串,也可以由若干数数据据项项组成(数据的最最小小单单位位)。在这种情况下,通常把数数据据元元素素称为记记录录。如表2-1所示的学生学籍登记表,在这个表中每一个学生的学籍登记卡作为一个数据元素,每一个元素由学号、姓名、性别、民族、籍贯、专业六个数据项组成。第第2 2章章线性数据结构线性数据结构表2-1 学生学籍登记表学 号姓 名性 别民 族籍 贯专 业1王 安男汉北京计算机通信2李 华男回河北软 件3张 莉女汉山西计算机应用4张 平女汉广东软 件第第
8、2 2章章线性数据结构线性数据结构三三.数据对象数据对象 性质相同的数据元素的集合,数据的子集。如上表中的学生学籍卡中的所有学生纪录。四四.什么是数据结构?什么是数据结构?在任何问题中,构成数据的数据元素并不是孤立存在的,它们之间存在着一定的关系以表达不同的事物及事物之间的联系。所以简单地说,数据结数据结构构就是指同一数据对象中各数据元素间存在的一种或多种特定关系。第第2 2章章线性数据结构线性数据结构五.数据结构数据结构的研究内容的研究内容?它不仅是一般程序设计的基础,而且是设计和实现编译程序、操作系统、数据库系统及其它系统程序和大型应用程序的重要基础。它包括三个方面的内容:计算机处理非数值
9、计算的问题中的数据元素间的结构关系(逻逻辑辑结结构构)、以及这样的关系在计算机内存中的存储形式(物物理理结结构构存存储储结结构构),和对数据元素及其关系的操作实现(算法)(算法)。第第2 2章章线性数据结构线性数据结构1.数据的逻辑结构数据的逻辑结构 2.数据的存储结构数据的存储结构 3.数据的运算:数据的运算:检索、排序、插入、删除、修改等。检索、排序、插入、删除、修改等。A.线性结构线性结构 B.非线性结构非线性结构A.顺序存储顺序存储 B.链式存储链式存储 线性表线性表栈栈队队树形结构树形结构图形结构图形结构数据结构的三个方面数据结构的三个方面反映数据元素反映数据元素之间的逻辑关之间的逻
10、辑关系系数据元素在计算机数据元素在计算机内部的组织方式内部的组织方式C.散列结构(散列表)散列结构(散列表)D.索引结构(索引表)索引结构(索引表)第第2 2章章线性数据结构线性数据结构 1.数据的逻辑结构数据的逻辑结构 数数据据的的逻逻辑辑结结构构就是数据元素之间的逻辑关系。可以用一个二元组,给出其形式定义为 Data Structure=(D,R)其中,D是组成数据的数据元素的有限集合,R是数据元素之间的关系集合。根据数据元素之间关系的不同特性,数据结构又可分为两大类分为两大类:线性数据结构线性数据结构和非线性数据结构非线性数据结构。第第2 2章章线性数据结构线性数据结构在自然界中,事物之
11、间的关系(逻辑结构)在自然界中,事物之间的关系(逻辑结构)主要有四种表现形式:主要有四种表现形式:集合:元素同属于一个集合集合:元素同属于一个集合线性关系:一个对一个,并非一一对应线性关系:一个对一个,并非一一对应树形关系:一个对多个树形关系:一个对多个图状关系(网状):多个对多个图状关系(网状):多个对多个第第2 2章章线性数据结构线性数据结构 2数据的存储结构数据的存储结构 数数据据的的逻逻辑辑结结构构是从逻辑上来描述数据元素之间的关系的,是独立于计算机的。然而讨论数据结构的目的是为了在计算机中实现对它的处理。因此还需要研究数据元素和数据元素之间的关系如何在计算机中表示,这就是数据的存储结
12、构数据的存储结构。计算机的存储器是由很多存储单元组成的,每个存储单元有惟一的地址。数数据据的的存存储储结结构构要讨论的就是数据结构在计算机存储器上的存储映像方法。第第2 2章章线性数据结构线性数据结构 实现数据的逻辑结构到计算机存储器的映像有多种不同的方式。一般来说,数据在存储器中的存储有四种基本的映像方法四种基本的映像方法。(1)顺顺序序存存储储结结构构。这种存储方式主要用于线性数据结构,就是把数据元素按某种顺序放在一块连续的存储单元中。其特特点点是逻辑上相邻的数据元素存储在物理上相邻的存储单元中,元素之间的关系由存储单元的邻接关系来体现。某些非线性数据结构也可以采用顺序方式存储,例如完全二
13、叉树、多维数组等,具体方法将在后面介绍。第第2 2章章线性数据结构线性数据结构 (2)链链式式存存储储结结构构。链式存储结构可可以以把把逻逻辑辑上上相相邻邻的的两两个个元元素素存存放放在在物物理理上上不不相相邻邻的的存存储储单单元元中中。即即可可用用一一组组任任意意的的存存储储单单元元来来存存储储数数据据元元素素,这这些些存存储储单单元元可可以以是是连连续续的的,也也可可以以是是不不连连续续的的。另外对于非线性数据结构,还可以在线性编址的计算机存储器中表示结点之间的非线性关系。链式存储结构的特特点点就是将将存存放放每每个个数数据据元元素素的的结结点点分分为为两两部部分分:一部分存放数据元素(称
14、为数数据据域域):另一部分存放指示存储地址的指针(称为指指针针域域),借助指针表示数据元素之间的关系。第第2 2章章线性数据结构线性数据结构 (3)索索引引存存储储结结构构。在线性表中,数据元素可以排成一个序列:R1、R2、R3、Rn,每个数据元素Ri在序列里都有对应的位置数据i,这就是元素的索索引引。索引存储结构就是通过数据元素的索引号i来确定数据元素Ri的存储地址。一般索引存储结构的实现方法是以若干数据元素为一组,建立特征索引,用索引号来确定存储地址。第第2 2章章线性数据结构线性数据结构 (4)散散列列存存储储结结构构。这种存储方法就是在数据元素与其在存储器上的存储位置之间建立一个映像关
15、系函数F。也就是说,数据元素的存放位置与其元素值呈函数关系。根据这个映像关系F,已知某数据元素就可以得到它的存储地址。即D=F(E),这里E是要存放的数据元素,D是该数据元素的存储位置。可见,这种存储结构的关关键键是设计这个函数F。但函数F不可能解决数据存储中的所有问题,还应有一套意外事件的处理方法,它们共同实现数据的散列存储结构。第第2 2章章线性数据结构线性数据结构 3.数据的运算数据的运算 数数据据的的运运算算是定定义义在在数数据据逻逻辑辑结结构构上上的的操操作作,每种数据结构都有一个运算的集合。常常用用的的运运算算有检检索索、插插入入、删删除除、更更新新、排排序序等等。运运算算的的具具
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据结构相关概念 数据结构 相关 概念
![提示](https://www.deliwenku.com/images/bang_tan.gif)
限制150内