自学考试:数据结构导论课件.pdf
第一章概论
第零节概论
简单地说,数据结构是计算机组织数据和存储数据的方式。
更进一步地说,数据结构是指一组相互之间存在一种或多种特定关系的数据的组织方式和它
们在计算机内的存储方式,以及定义在该组数据上的一组操作。
第一节引言
1、计算机解决一个具体问题时,一般需要经过以下几个步骤:
(1)从具体的问题抽象出一个适当的数学模型;
(2 )设计一个求解该数学模型的算法;
(3)用某种计算机语言编写实现该算法的程序,调试和运行程序直至最终得到问题的解答。
在每个步骤中,数据的表现形式都不相同,实际问题中的数据称为原始数据。在数学模型中,
需要把原始数据按照某种方式组织起来,以便很好地体现数据之间的关系,数据及数据的组
1
织方式称为数据的逻辑结构。为了能用计算机加工处理,逻辑结构还必须转换为能被计算机
存储的存储结构。如下图:
2、1976年瑞士计算机科学家尼克劳斯•维尔特(NiklausWirth)曾提出一个著名公式:算
法+数据结构=程序。该公式简洁地描述了算法、数据结构和程序之间关系。
第二节基本概念和术语
一、数据、数据元素和数据项
(1)数据:所有被计算机存储、处理的对象。
(2 )数据元素:数据的基本单位,在程序中作为一个整体而加以考虑和处理。数据元素是
运算的基本单位,通常具有完整确定的实际意义。数据元素常常又简称为元素。
(3)数据项:一般情况下,数据元素由数据项组成。在数据库中数据项又称为字段或域。
它是数据的不可分割的最小标识单位。
从宏观上看,数据、数据元素和数据项实际上反映了数据组织的三个层次,数据可由若干个
数据元素组成,而数据元素又可由若干个数据项组成。
数据结构是相互之间存在一种或多种特定关系的数据元素的集合。它包括数据的逻辑结构、
数据的存储结构和数据的基本运算。
2
二、数据的逻辑结构
1、数据的逻辑结构是指数据元素之间的逻辑关系。所谓逻辑关系是指数据元素之间的关联
方式或 “邻接关系”。
2、根据数据元素之间的关系,有四类基本的逻辑结构:
(1)集合中任意两个结点之间都没有邻接关系,组织形式松散。
(2 )线性结构中结点按逻辑关系依次排列形成一条 “链”,结点之间一个一个依次相邻接。
(3)树形结构具有分支、层次特性,其形态像自然界中的树,上层的结点可以和下层多个
结点相邻接,但下层结点只能和上层的一个结点相邻接。
(4 )图结构最复杂,其中任何两个结点都可以相邻接。
三、数据的存储结构
1、数据的逻辑结构在计算机中的实现称为数据的存储结构(或物理结构)。一般情况下,
一个存储结构包括以下两个部分:
(1)存储数据元素;
3
(2 )数据元素之间的关联方式。
2、表示数据元素之间的关联方式主要有顺序存储方式和链式存储方式。
(1)顺序存储方式是指所有存储结点存放在一个连续的存储区里。利用结点在存储器中的
相对位置来表示数据元素之间的逻辑关系。
(2 )链式存储方式是指每个存储结点除了含有一个数据元素外,还包含指针,每个指针指
向一个与本结点有逻辑关系的结点,用指针表示数据元素之间的逻辑关系。
除了上述两种存储方式之外,还有索引存储方式和散列存储方式。
3、一种逻辑结构可以采用一种或几种存储方式来表达数据元素之间的逻辑关系,相应的存
储结构称为给定逻辑结构的存储实现或存储映像。如何来描述存储结构呢?可以分别在机器
级和语言级上讨论。
四、运算
1、运算是指在某种逻辑结构上施加的操作,即对逻辑结构的加工。这种加工以数据的逻辑
结构为对象。一般来说,在每个逻辑结构上,都定义了一组基本运算,这些运算包括:建立、
查找、读取、插入和删除等。
2、线性表、栈和队列中的元素具有相同的逻辑结构(即线性结构),但有不同的运算集,
它们是不同的数据结构。
第三节算法及描述
(一)算法的概念
运算的实现是指该运算的算法。算法是计算机科学的一个基本概念,也是程序设计的一个核
心概念。
4
2024最新激活全家桶教程,稳定运行到2099年,请移步至置顶文章:https://sigusoft.com/99576.html
版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请联系我们举报,一经查实,本站将立刻删除。 文章由激活谷谷主-小谷整理,转载请注明出处:https://sigusoft.com/92788.html