第一章 绪论

数据的定义:信息的载体。

数据元素、数据项:数据元素是数据的基本单位,通常作为一个整体进行考虑和处理。一个数据元素可由若干数据项组成,数据项是构成数据元素的不可分割的最小单位。

数据结构的定义:相互之间存在一种或多种特定关系的数据元素的集合。

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

数据结构的三要素

逻辑结构

  1. 集合<不讨论>
  2. 线性结构<第二,三章>
  3. 树形结构<第四章>
  4. 图状结构(网状结构)<第五章>

存储结构

  1. 顺序存储
  2. 链式存储
  3. 索引存储
  4. 散列存储<第六章(散列表有讲)>

数据的运算

数据类型、抽象数据类型

数据类型

定义:一个值的集合和定义在此集合上的一组操作的总称。

  1. 原子类型(其值不可再分的数据类型)

  2. 结构类型(其值可以再分解为若干成分<分量>的数据类型)

抽象数据类型(ADT)

定义:抽象数据组织及与之相关的操作。

算法的基本概念

算法的五大特性

  1. 有穷性:一个算法必须总在执行有穷步之后结束,且每一步都可在有穷时间内完成。

    注:算法必须是有穷的,而程序可以是无穷的。

  2. 确定性:算法中每条指令必须有确切的含义,对于相同的输入只能得出相同的结果

  3. 可行性:算法中描述的操作都可以通过已经实现的基本运算执行有限次来实现。

  4. 输入:一个算法有零个或多个输入,这些输入取自于某个特定的对象的集合。

  5. 输出:一个算法有一个或多个输出,这些输出是与输入有着某种特定关系的量。