computer science

data structure

数据结构是一门研究非数值计算的程序设计问题中计算机的操作对象以及他们之间的关系和操作等的科学。

  1. 数据

    是信息的载体,是描述客观事物的数、字符、以及所有能输入到计算机中,被计算机程序识别和处理的符号的集合。

    数值性数据:如整型、实型等。

    非数值性数据:如字符及声音、图像、视频等

  2. 数据元素

    数据的基本单位。在计算机程序中常作为一个整体进行考虑和处理。

    有时一个数据元素可以由若干数据项(Data Item)组成(此时数据元素被称为记录)。数据元素又称为元素、结点、记录(数据库概念)。

  3. 数据对象

    具有相同性质的数据元素的集合,是数据的一个子集。例如整数集,字母集。

  4. 结构

    结构是元素之间的关系。数据结构就是相互之间存在一种或多种特定关系的数据元素的集合。结构分为逻辑结构和存储结构。

  5. 逻辑结构

    数据对象中数据元素之间的相互关系。有集合结构、线性结构、树型结构和图形结构。

  6. 存储结构(物理结构)

    数据结构在物理中的表示称为物理结构(Physical Structure),又称为存储结构(Storage Structure)。

    顺序结构:数据元素存放在地址连续的存储单元里。

    链式存储:把数据元素存放在任意的存储单元里,这组存储单元可以是连续的,也可以是不连续的。

常用的数据结构

  1. 线性表

    元素呈线性,有前继和后继。主要操作有插入和删除。

  2. 栈和队列

    栈和队列的逻辑结构均为线性结构,是两种特殊的线性表。限定仅在表的两端进行插入或删除操作的线性表。栈是先进后出,队列是先进先出。

  3. 数组

    从逻辑结构上,数组可以看成是一般线性表的扩充。一维数组即为线性表。二维数组也可以看作为线性表,只不过线性表的数据元素亦是线性表。矩阵一般利用数组存储。

  4. 树有个节点是根,除了根其他节点都有唯一的前继,但是所有节点都可能有多个后继,没有后继的节点称为叶子节点,非叶子节点称为分支节点。

    可以将树看成一个族谱,根是祖先,后继就是二代,一直下去,后继称为孩子,前继称为父节点,同辈称为兄弟。

    根节点称为第一层,其孩子为第二层,以此类推。

    树可以分为有序树和无序树。计算机常用二叉树。

  5. 存在多个顶点,点与点之间都有可能有边相连。顶点集合称为点集,边的集合称为边集。

    图的边具有与它相关的数值称为权。有权的图又称为网。