1. 什么是数据结构

• 计算机解决一个具体的问题，大致需要以下三个步骤：
• 具体问题抽象出一个适当数据模型
• 设计一个解此数据模型的算法
• 编出程序

• 寻求数据模型的实质就是：==分析问题==，从中提取操作的对象，并找出这些操作对象之间含有的关系，然后用数学语言加以描述

2. 基本概念和术语

• 数据（data）是对客观事物的符号表示，在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号的总称（如：图像、声音都是可以通过编码而归之于数据的范畴）

• 数据元素（data element）是数据的基本单元，在计算机程序中，通常作为一个整体进行考虑和处理。

• 数据对象（data object）是性质相同的数据元素的集合，是数据的一个子集

• 数据结构 （data structure）是相互之间存在一种或多种特定的数据元素的集合。在任何问题中，数据元素都不是孤立存在的，而是在他们之间存在着某种关系，这种数据元素之间的关系称为结构（structure）

• 根据数据元素之间关系的不同特性，分为4种基本结构

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

• 数据结构的形式定义：数据结构是一个二元组Data_Structure=(D,S) 其中D是元素的有限集，S是D上关系的有限集。结构定义中的“关系”描述的是数据元素之间的逻辑结构，因此称为数据的逻辑结构。

• 数据结构在计算机中的表示（又称映像）称为数据的物理结构，即存储结构，它包括数据元素的表示和关系的表示。数据元素之间的关系在计算机中有两种不同的表示方法，分别为：顺序映像和非顺序映像，并由此得到两种不同的存储结构：顺序存储结构和链式存储结构。

  • 顺序映像的特点是：借助元素在存储器中相对位置来表示数据元素之间的逻辑关系
  • 非顺序映像特点是：借助指示元素存储的指针来表示数据元素之间的逻辑关系
  • 任何一个算法的设计取决于选定的选定的数据逻辑结构，而算法的实现却依赖于采用的存储结构

• 数据类型：是一个值的集合和定义在这个值集上的一组操作的总称。例如：c语言中的整型变量，其值集为某个区间上的整数，定义在其上的操作为加、减、乘、除和取模等算术运算

• 抽象数据类型（Abstract Data Type简称ADT）:是指一个数据模型以及定义在该模型上的一组操作

  • 抽象数据类型可用以下三元组表示（D，S，T）其中D是数据对象 S是D上的关系集，P是对D的基本操作。可采用一下格式定义抽象数据类型：

    ADT 抽象数据类型名 {
    数据对象:（数据对象的定义）
    数据关系:（数据关系的定义）
    基本操作:（基本操作的定义）
    }ADT 抽象数据类型名

3. 算法和算法分析

• 算法(algorithm)是对特定问题求解步骤的一种描述，它是指令的有限序列，其中每一条指令表示一个或多个操作。算法有5个重要特征

  • 有穷性：一个算法必须总是在执行有穷步之后结束，且每一步都可在有穷时间内完成
  • 确定性：算法中每一条指令必须有确切的含义，读者理解是不会产生二义，并且，在任何条件下，算法只有唯一的一条执行路径，即对于相同的输入只能得出相同的输出
  • 可行性：一个算法是可行的，即算法中描述的操作都是可以通过已经实现的基本运算执行有限此来实现。
  • 输入：一个算法有0个或多个的输入，这些输入取自于某个特定的对象集合
  • 输出：一个算法有1个或多个输出，这些输出是同输入有着某些特定关系的量

• 算法设计的要求：通常设计一个好的算法应考虑达到以下目标：

  • 正确性(correctness)：程序对于一切合法的输入数据都能产生满足规格说明要求的结果
  • 可读性(readability): 算法主要是为了人的阅读和交流，其次才是机器执行，可读性好有助于人对算法的理解，晦涩难懂的程序易于隐藏较多错误，难以调试和修改
  • 健壮性(robustness):当输入数据非法时，算法也能适当的作出反应或进行处理，而不会产生莫名其妙的输出结果
  • 效率与低存储量需求:存储量需求指算法执行过程中所需要的最大存储空间。效率指的的算法的执行时间。这两者都与问题的的规模有关。

• 算法效率的度量：时间复杂度

一般情况下，算法中基本操作重复执行的次数是问题规模n的某个函数f(n),算法的时间度量计作：T(n)=O(f(n))。它表示随问题规模n的增大，算法执行时间的增长率和f(n)的增长率相同，称做算法的渐进时间复杂度(asymptotic time complexiy)简称时间复杂度

• 算法的存储空间需求：类似与算法的时间复杂度，空间复杂度（space complexity）作为算法所需存储空间的量度，记作： S(n)=O(f(n))