数据结构（二）——数据结构与算法基础

第二章 数据结构与算法基础

• 基本概念
  数据 ：描述客观事物的数值、字符以及能输入机器且能被处理的各种符号集合
  数据元素： 数据的基本单位，是数据集合的个体
  数据对象 ：性质相同的数据元素的集合，是数据的子集
  数据结构：是指相互之间存在一种或多种特定关系的数据元素的集合。是组织并存储数据以便能够有效使用的一种专门格式，它用来反映一个数据的内部构成，即一个数据由哪些成分数据构成，以什么方式构成，呈什么结构。分为逻辑结构和存储结构。逻辑结构是指数据结构的逻辑层面；存储结构是指存在于计算机世界的物理层面。
  逻辑结构——按照数据元素之间相互关系的特性来分，分为以下四种结构：集合、线性结构（线性表，栈，队列）、树形结构和图状结构；数据的逻辑结构采用两种方法来描述：二元组、图形；二元组的表示形式为：
  数据结构={D,S}
  其中 D 是数据元素的集合；S 是 D 中数据元素之间的关系集合，并且数据元素之间的
  关系是使用序偶来表示的。序偶是由两个元素 x 和 y 按一定顺序排列而成的二元组，记作
  <x , y>，x 是它的第一元素，y 是它的第二元素。
  
  依次对应数据结构的二元组

• set = (K, R)
  K={01,02,03,04,05}
  R={ }

• linearity=(K, R)
  K={01,02,03,04,05}
  R={<02,04>,<03,05>,<05,02>,<01,03>}

• tree= (K, R)
  K={01,02,03,04,05,06}
  R={<01,02>,<01,03,><02,04>,<02,05>,<03,06>}

• graph=(K,R)
  K={01,02,03,04,05}
  R={}
  存储结构：数据的存储结构主要包括数据元素本身的存储以及数据元素之间关系表示。两种存储结构：顺序存储结构和链式存储结构。顺序存储结构的特点：数据元素的存储对应于一块连续的存储空间，数据元素之间的前驱和后驱关系通过数据元素在存储器中的相对位置来反映。**链式存储结构特点：**数据元素的存储对应不连续的存储空间，每个存储节点对应需要存储的数据单元。元素的逻辑关系，通过存储节点之间的连接关系反应。

• 抽象数据类型
  数据类型：一组性质相同的数据元素的集合以及加在这个集合上的一组操作
  抽象数据类型ADT:由数据模型和在该数据模型上的一组操作组成
  抽象数据类型可以使用一个三元组来表示：
  ADT = (D, S, P)
  其中 D 是数据对象，S 是 D 上的关系集，P 是加在 D 上的一组操作。
  在定义抽象数据类型时，我们使用以下格式：

  ADT 抽象数据类型名 {
  数据对象： < 数据对象的定义 >
  数据关系： < 数据关系的定义 >
  基本操作： < 基本操作的定义
  }

• 算法
  算法是指令的集合，是一个明确定义的可计算的过程，以一个数据集合作为输入，并产生一个数据集合作为输出，通常具有五个特性：

• 时间复杂性：算法运行时间的确定问题
  如何分析算法的运行时间？？以简单选择排序为例
  
  算法的执行次数为
  **算法的规模T(n)：**此处指针对排序的数组大小
  常用的作为问题规模的例子：

• 几个符号定义

  1. O符号（提供运行时间的上限）：对简单快速排序算法分析，
     
  2. Ω符号（算法事件复杂度的下界）：Ω符号可以解释为：如果输入大于等于某个阈值 N，算法的运行时间下限是 f(n)的 c 倍，
     其中 c 是一个正常数，则称算法的时间复杂度是Ω(f(n))的。Ω的形式定义与Ο符号对称。
  3. θ符号（算法事件复杂度的精确阶）
     Θ符号可以解释为：如果输入大于等于某个阈值N，算法的运行时间在下限c 1 f(n)和上限
     c 2 f(n)之间（0<c 1 ≤c 2 ），则称算法的时间复杂度是Θ(f(n))阶的。该符号的形式定义如下。

• 空间复杂性（存储空间的数目）：
  用S(n)表示,如果使用 S(n)与 T(n)分别表示算法的空间复杂度和时间复杂度，则有S(n)=O(T(n))

• 算法的时间复杂度分析

  1. 计算循环次数
     
     n在这里这的是循环次数吗？？
  2. 分析最高频度的基本操作——针对统计循环次数非常复杂的时间复杂度情况
     例子：将两个有序的数组a[0,m-1]，b[0,n-1]合并为一个更大的有序数组。