408数据结构-其他

1. 数据结构

数据元素：数据元素是数据的基本单位。一个数据元素可由若干数据项组成。例如，学生记录就是一个数据元素，它由学号、姓名、性别等数据项组成。

数据对象：数据对象是具有相同性质的数据元素的集合，是数据的一个子集。

数据结构：三要素：逻辑结构、存储结构、数据的运算。

• 逻辑结构

  逻辑结构与数据的存储无关，是独立于计算机的。

  逻辑结构大致上分成两种：线性结构和非线性结构。

  再细分有：

  • 集合：结构中数据元素之间除了“同属于一个集合”外，无其他关系。
  • 线性结构：结构中的数据元素之间只存在一对一的关系。
  • 树形结构：结构中的数据元素之间存在一对多的关系。
  • 图状结构/网状结构：结构中的数据元素之间存在多对多关系。

• 存储结构/物理结构

  指数据元素在计算机中的表示。包括数据元素的表示和关系的表示。

  • 顺序存储：逻辑上相邻的元素在物理位置上也相邻的存储单元。
  • 链式存储：不要求逻辑上相邻的元素在物理位置上也相邻。
  • 索引存储：存储元素信息的同时还建立附加的索引表，索引表中每项称为索引项，索引项的一般形式是（关键字，地址）。
  • 散列存储：根据元素的关键字直接计算出该元素的存储地址。

• 数据的运算

  施加在数据上的运算包括运算的定义和实现。

  运算的定义是针对逻辑结构的，指出运算的功能。

  运算的实现是针对存储结构的，指出运算的具体步骤。

有序表指关键字有序的线性表，仅描述元素之间的逻辑关系。

2. 算法

算法

算法是对特定问题求解的一种描述。有如下五个特性：

• 有穷性：一个算法必须在有穷步之后结束。
• 确定性：算法中每条指令必须有确切的含义，对于相同输入只能得到相同的输出。
• 可行性：算法中描述的操作都可以通过已经实现的基本运算执行有限次来实现。
• 输入：一个算法有零个或者多个输入。
• 输出：一个算法有一个或者多个输出。

A：程序不一定满足有穷性，比如死循环、操作系统。

C：只是算法的必要条件，不是算法的定义。