大纲

数据结构第一章

基本概念

• 数据：数据（Data）是客观事物的符号表示，是所有能输入到计算机中并被计算机程序处理的符号的总称。
• 数据元素：是数据的基本单位，在计算机中通常作为一个整体进行考虑和处理。
• 数据项：是组成数据元素的、有独立含义的、不可分割的最小单位。
• 数据对象：是性质相同的数据元素的集合，是数据的一个子集。

数据结构

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

逻辑结构

数据的逻辑结构有两个要素：一是数据元素；二是关系。

• 集合结构：数据元素之间除了“属于同一集合”的关系外，别无其他关系。
• 线性结构：数据元素之间存在一对一的关系。
• 树结构：数据元素之间存在一对多的关系。
• 图结构或网状结构：数据元素之间存在多对多的关系。
  线性结构包括线性表，栈和队列，字符串，数组，广义表。非线性结构包括树，二叉树，有向图和无向图。

存储结构

把数据对象存储到计算机时，通常要求既要存储各数据元素的数据，又要存储数据元素之间的逻辑关系，数据元素在计算机内用一个结点来表示。

• 顺序存储结构：顺序存储结构要求所有的元素依次存放在一片连续的存储空间中。
• 链式存储结构：无需占用一整块存储空间。但为了表示结点之间的关系，需要给每个结点附加指针字段，用于存放后继元素的存储地址。

数据类型

数据类型是一个值的集合和定义在这个值集上的一组操作的总称。

数据类型

C语言除了提供整型、实型、字符型等基本类型数据外，还允许用户自定义各种类型数据，例如数组、结构体和指针等。

抽象数据类型

一般指由用户定义的、表示应用问题的数学模型，以及定义在这个模型上的一组操作的总称，具体包括三部分：数据对象、数据对象上关系的集合以及对数据对象的基本操作的集合。

算法分析

算法的特性

• 有穷性
• 确定性
• 可行性
• 输入
• 输出

算法的优劣

• 正确性
• 可读性
• 健壮性

时间复杂度

• 顺序执行的代码只会影响常数项，可以忽略。
• 只需挑循环中的一个基本操作分析它的执行次数与n的关系即可。
• 如果有多层嵌套循环，只需关注最深层循环循环了几次即可。
  O（1）<O（log2n）<O（n）<O（nlog2n）<O（n^2)< O (n^3)< O (2^n)< O(n!)

空间复杂度

只需关注存储空间的大小与问题规模相关的变量。
如果内存空间大小是kn个字节，k是常数的话，那么用大O表示法S(n)=O(n)