数据结构——用C语言描述(一)

数据结构绪论

数据结构基础概念

• 数据（Data）：描述客观事物的数值、字符，能被机器输入且处理的的各种符号的集合。

• 数据元素（Data Element）：组成数据的基本单位，是数据集合的个体。一条记录就是一个数据元素。

• 数据对象（Data Object）：性质相同的数据元素的集合，是数据的一个子集。

• 数据结构（Data Structure）：指相互之间存在一种或多种特定关系的数据元素集合。即数据元素之间的相互关系，即数据的组织形式。一句话总结：带有结构的数据元素的集合。

• 数据类型（Data Type）：一组性质相同的值集合以及定义在这个值集合上的一组操作的总称。即值域、定义域及运算集合。

• 抽象数据类型（Abstract Data Type）：定义了一个数据对象，数据对象中各元素之间的结构关系，以及一组处理数据的操作。包括定义和实现两方面，其中定义是独立于实现的。

  ADT 三要素：

  • 数据元素
  • 数据关系
  • 数据操作

数据结构内容

• 逻辑结构：数据元素之间逻辑关系描述。

  四种基本数据逻辑结构表现为四种数据元素关系：

  • 集合结构：属于关系
  • 线性结构：一对一的线性关系
  • 树形结构：一对多的层次关系
  • 图形结构：多对多的任意关系

• 存储结构（物理结构）：逻辑结构在计算机中存储映像，是逻辑结构在计算机中的实现。包括数据元素的表示和关系的表示。

  数据元素之间关系在计算机中表示方法：

  • 顺序映像，一组连续单元，如数组。
  • 非顺序映像，一组任意存储单元，如链表。

• 运算集合

算法与算法描述

• 算法（algorithm）定义：规则的有限集合，是为解决特定问题而规定一系列操作。
• 算法特性：
  • 有限性：有限步骤
  • 确定性：无二义性
  • 输入：有多个或0个输入
  • 输出：至少有一个输出
  • 可行性：原则上能精确进行，操作可通过已实现的基本运算执行有限次而完成
• 算法设计要求：
  • 正确性
  • 可读性
  • 健壮性（鲁棒性）：对非法输入的抵抗能力
  • 高效率与低存储量
• 算法描述：自然语言、框图、高级语言

算法性能评价

• 性能评价：问题规模 N 的函数

• 数量关系评价：时间和空间

  • 算法执行时间：本质是语句执行次数的比较

  • 语句频度：该语句在一个算法中的重复执行的次数

  • 算法的时间复杂度: $$ T(n)=O(f(n)) $$ 例如：

    1 2 3

    for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) x++;

    这样的一段代码其时间复杂度为 $$ o(n^2) $$ 再例如，下方有一个算法的执行时间 $$ f(n)=2n^3+2n^2+n $$ 其时间复杂度为 $$ o(n^3) $$ 但这样一个算法只是理论上可行，但实际上不可行，因为其执行次数上升太快，程序无法实现。

  • 最坏时间复杂度：算法在最坏情况下基本操作执行时间的上界。

    例如，冒泡排序算法最坏时间复杂度为 $$ o(n^2) $$ 而其最好时间复杂度为 $$ o(n) $$

  • 算法空间复杂度：以存储单元个数刻画随问题规模增加的函数 f(n)，是考虑程序运行时占用内存的大小，记作 $$ S(n)=O(f(n)) $$