基本概念:

  • 数据(data):客观事物的符号表示,在计算机科学中指一切能够输入到计算机中并被计算机程序处理的符号的总称。
  • 数据元素(data element):数据的基本单位,在程序中通常作为一个整体进行考虑和处理。一个数据元素可以由若干个数据项组成。
  • 数据项(data item):数据结构中讨论的最小单位,是数据记录中最基本的、不可分的有名数据单位。
  • 数据对象(data object)性质相同的数据元素的集合,是数据的一个子集。
  • 数据结构(data structure):相互之间存在一种或多种特定关系的数据元素的集合
  • 数据类型(data type):一个值的集合和定义在这个值集上的一组操作的总称。
  • 抽象数据类型(abstract data type):一个数学模型以及定义在该模型上的一组操作。是对一般数据类型的扩展。

数据的逻辑结构:

数据的逻辑结构:数据元素与数据元素之间的逻辑关系。可以分为四类基本结构:

  • 线形结构:数据结构中的元素存在一对一的相互关系;
  • 树形结构:数据结构中的元素存在一对多的相互关系;
  • 图形结构:数据结构中的元素存在多对的的相互关系,也叫网状结构;
  • 集合:数据结构中的元素除了“同属一个集合”外,在无其他相互关系;

 

以下内容引用自LarryZeal的博客

逻辑结构可以采用两种方法来描述:二元组、图形。
    --二元组表示形式: DS = ( D, S )   【Data Structure】
        其中 D 是数据元素的集合; S 是 D 中数据元素之间的关系集合并且数据元素之间的关系是使用序偶来表示的。序偶是由两个元素 x 和 y 按一定顺序排列而成的二元组,记作<x , y>, x 是它的第一元素, y 是它的第二元素。
        
    --当使用图形来表示数据结构时,是用图形中的点来表示数据元素,用图形中的弧来表示数据元素之间的关系。如果数据元素 x 与 y 之间有关系<x , y>,则在图形中有从表示 x 的点出发到达表示 y 的点的一条弧。


二元组表示:

    令数据结构的二元组形式为:DS = (D, S),则:

  1. 如果 D != null,而S == null,则该数据结构为集合结构。
  2. 如果 D = {01, 02, 03, 04, 05},S = {<02,04>, <03,05>, <05,02>, <01,03>},则该数据结构是线性结构。
    在这些数据元素中有一个可以被称为“第一个”的数据元素;还有一个可以被称为“最后一个”的数据元素;除第一个元素以外每个数据元素有且仅有一个直接前驱元素,除最后一个元素以外每个数据元素有且仅有一个直接后续元素。这种数据结构的特点是数据元素之间是 1对 1 的联系,即线性关系。
  3. D = {01, 02, 03, 04, 05, 06}
    S = {<01,02>, <01,03>, <02,04>, <02,05>, <03,06>}
    除了一个数据元素(元素 01)以外每个数据元素有且仅有一个直接前驱元素,但是可以有多个直接后续元素。这种数据结构的特点是数据元素之间是 1 对 N 的联系,即树结构。
  4. D = {01, 02, 03, 04, 05}
    S = {<01,02>, <01,05>, <02,01>, <02,03>, <02,04>, <03,02>,<04,02>, <04,05>, <05,01>, <05,04>}:
    每个数据元素可以有多个直接前驱元素,也可以有多个直接后续元素。这种数据结构的特点是数据元素之间是 M 对 N 的联系,即图结构。

图形表示:  

 

 

 常见逻辑结构:线性表、栈、队列、树、图
        --其中线性表、栈、队列为线性结构,树和图都是非线性结构。

数据结构的存储结构:

数据在计算机中的存储表示称为数据的存储结构,又称物理结构。数据存储到计算机中即要求存储各节点的数值,又要存储结点与结点之间的逻辑关系。

  • 顺序存储:顺序存储结构是把逻辑上相邻的元素存储在一组连续的存储单元中,逻辑相邻的元素在物理存储单元也相邻。

        优点:节省存储空间,只需要存储数据结点,并不需要存储结点的逻辑关系。
        缺点:不便于修改,插入和删除某个结点需要修改一系列的结点。

  • 链式存储:链式存储结构,给每个结点增加指针字段,用于存放临近结点的存储地址,每个结点都由两部分存储单元组成,一个存放数据,一个存放临近结点(前驱/后继结点)的地址。

        优点:便于修改,插入和删除某个结点时只需要修改结点的指针字段,不需要移动其他结点
        缺点:浪费存储空间;查找慢,不能对结点进行随机访问。

  • 索引存储:索引存储结构即在存储结点的同时,增加索引表,索引表的索引项为:(关键字,地址),关键字标识结点,地址为结点的指针。各结点的地址在索引表中是依次排列的。

        优点:可以快速查找,可以随机访问,方便修改。
        缺点:建立索引表增加了时间和空间的开销。

  • 散列存储:散列存储结构是根据结点的值确定结点的存储地址。以结点作为自变量,通过散列函数算出结果i,再把i作为结点的存储地址。

        优点:查找速度快,适用于快速查找和插入的场景。
        缺点:只存结点数据,不存结点之间的关系。

最后修改于 2019-09-09 17:30:51
如果觉得我的文章对你有用,请随意赞赏
扫一扫支付
上一篇