第一章绪论

前言：今天（2015年9月14日）去一家公司面试（还是霸面）C/C++开发工程师，没有经过系统地复习就一后果，被虐了。为了下次面试，所以现在趁着有时间重新学下数据结构（C语言版，严蔚敏著）。在这记录学习资料，一般都是书上写的。

1、什么是数据结构

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

1.2四种基本结构：集合结构，线性结构，树形结构，图状结构（网状）。（关系）

1.3数据结构的形式定义：数据结构是一个二元组， Data_Struct=(D,S)，其中D是数据元素的有限集，S是D上关系的有限集。

1.4数据的逻辑结构：数据结构中定义中的关系描述的是数据元素之间的逻辑关系；分两种：线性结构（线性表{是一种有限序列，如数组和链式等}，栈LIFO{限定仅在表尾进行插入或删除操作的线性表}，队列FIFO）和非线性结构（树，图）

　　数据的物理结构：数据结构在计算机的表示（映像）成为数据的物理结构（存储结构）；分两种：顺序存储结构，链式存储结构，索引存储，散列存储。

2、抽象数据类型ADT（Abstract Data Type）

2.1定义：是指一个数学模型及定义在该模型上的一组操作。定义仅取决于数据的逻辑特性。

2.2一个包含抽象数据类型的软件模块组成：定义，表示，实现三部分，三元组定义式如下：(D,S,P)，其中D是数据对象，S是D上的关系集，P是对D的基本操作集。

　　抽象数据类型的格式：

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

　　基本操作名格式

基本操作名（参数表）
    初始条件：描述
    操作结果：描述

3、算法及算法分析

3.1算法：有穷性，确定性，可行性，输入，输出。

3.2算法效率的度量

　　时间复杂度：T(n)=O(f(n))

　　空间复杂度：S(N)=O(f(n))

第一章 绪论