cpp learning

在计算机领域中,数据结构就是计算机存储组织数据的方式。数据结构是指相互之间存在一种或多种特定关系的数据元素的集合。由于对于特定的算法,需要特定的数据结构支撑,因此数据结构成为一门独立的学科供我们学习。

计算机的运行离不开两样:程序和数据。而数据的存储方式对我们以后的处理至关重要。数据结构分两方面理解。一种是逻辑,一种是物理实现。

逻辑结构(理论)

逻辑关系是指数据元素之间的关系,而与他们在计算机中的存储位置无关。主要有

  1. 集合

    数据结构中的元素之间除了 “同属一个集合” 的相互关系外,别无其他关系。

  2. 线性结构

    数据结构中的元素存在一对一的相互关系。

  3. 树形结构

    数据结构中的元素存在一对多的相互关系。

  4. 图形结构

    数据结构中的元素存在多对多的相互关系。

物理结构(实现)

数据的物理结构是数据结构在计算机中的表示(又称映像)。具体实现有顺序、链接、索引、散列等多种,所以,一种数据结构可表示成一种或多种存储结构。

  1. 顺序存储

    逻辑上相邻的结点存储在物理位置相邻的存储单元里。

  2. 链接存储

    不要求逻辑上相邻的结点在物理位置上亦相邻,结点间的逻辑关系是由附加的指针字段表示的。

  3. 索引存储

    除建立存储结点信息外,还建立附加的索引表来标识结点的地址。(相当于偏移地址,要与 2 区别开来)

  4. 散列存储

    根据结点的关键字直接计算出该结点的存储地址,也就是程序员口中常说的哈希表。

研究内容

计算机解决一个具体问题时,需要经过以下几个步骤

  1. 提出问题
  2. 抽出数学模型
  3. 设计此数学模型的算法
  4. 编程测试得到解决方案

在第二步中,我们需要建立数学模型,而很多数学模型是数学方程来描述的,计算机无法用数学方程来描述,因此需要数据结构来描述。

客观事物例如数值、字符、声音、图形等等都不是数据,只有通过编码编程能被计算机识别、存储和处理的符号形式后才是数据。才能被数据结构所利用。

数据元素是数据的基本单位,在计算机程序中通常作为一个整体考虑。例如学生信息整体为一个基本单位。

数据处理是指对数据进行查找、插入、删除、合并、排序、统计以及简单计算等的操作过程。

结构算法

一个软件系统框架应建立在数据之上,而不是建立在操作之上(抽象思想)。一个含抽象数据类型的软件模块应包含定义、表示、实现三个部分。

对每一个数据结构而言,必定存在与它密切相关的一组操作。若操作的种类和数目不同,即使逻辑结构相同,数据结构能起的作用也不同。

不同的数据结构其操作集不同,但下列操作必不可缺

  1. 结构的生成;

  2. 结构的销毁;

  3. 在结构中查找满足规定条件的数据元素;

  4. 在结构中插入新的数据元素;

  5. 删除结构中已经存在的数据元素;

  6. 遍历。

常用结构

  1. 数组

    在程序设计中,为了处理方便, 把具有相同类型的若干变量按有序的形式组织起来。这些按序排列的同类数据元素的集合称为数组。

  2. 先进后出的线性表

  3. 队列

    先进先出的线性表

  4. 链表

    是一种物理存储单元上非连续、非顺序的存储结构,它既可以表示线性结构,也可以用于表示非线性结构,数据元素的逻辑顺序是通过链表中的指针链接次序实现的。

  5. 一个前继,多个后继,根没有前继,叶子没有后继。

  6. 一个节点可与多个节点存在关系。

  7. 在计算机科学中,堆是一种特殊的树形数据结构,每个结点都有一个值。通常我们所说的堆的数据结构,是指二叉堆。堆的特点是根结点的值最小(或最大),且根结点的两个子树也是一个堆。

  8. 散列表

    若结构中存在关键字和K相等的记录,则必定在f(K)的存储位置上。由此,不需比较便可直接取得所查记录。称这个对应关系f为散列函数(Hash function),按这个思想建立的表为散列表。