数据结构与算法学习笔记（三）

1. 线性表（List）：由0个或多个元素组成的有限序列。
   1. 首先它是一个序列，也就是说元素之间是有个先来后到的顺序
   2. 若元素存在多个，则第一个元素无前驱，而最后一个元素无后继，其他元素都有且只有一个前驱和后继
   3. 线性表是有限的，事实上无论计算机发展到多强大，它所处理的元素都是有限的
2. 线性表用数学语言来定义：若将线性表记为(a₁,a₂,……,a_i-1,a_i,a_i+1,……,a_n-1,a_n)，则表中a_i-1领先于a_i，a_i领先于a_i+1，称a_i-1是a_i的直接前驱元素，a_i+1是a_i的直接后继元素
3. 线性表元素的个数n(n>=0)定义为线性表的长度，当n=0时，称为空表。
4. 数据类型：指一组性质相同的值得集合及定义在此集合上的一些操作的总称，例如，整型，浮点型，字符型。
5. 在C语言中，按照取值的不同，数据类型可以分为两类：
   1. 原子类型：不可以再分解的基本类型，例如整型、浮点型、字符型等。
   2. 结构类型：由若干个类型组合而成，是可以再分解的，例如整型数组是由若干个整型数据组成的
6. 抽象：是指抽取出事物具有的普遍性的本质。它要求抽出问题的特征而忽略非本质的细节，是对具体事务的一个概括。抽象是一种思考问题的方式，它隐藏了繁杂的细节。
7. 我们对已有的数据类型进行抽象，就有了抽象数据类型。
8. 抽象数据类型（Abstract Data Type，ADT）是指一个数学模型及定义在该模型上的一组操作。
9. 抽象数据类型的定义仅取决于它的一组逻辑特性，而与其在计算机内部如何表示和实现无关。比如1+1=2这样一个操作，在不同CPU的处理上可能不一样，但由于其定义的数学特性相同，所以在计算机编程者看来，他们都是相同的。
10. 描述抽象数据类型的标准格式：

　　　　　　　　ADT　　抽象数据类型名

　　　　　　　　Data　　

　　　　　　　　　　　　数据元素之间逻辑关系的定义

　　　　　　　　Operation

　　　　　　　　　　　　操作

　　　　　　　　endADT

　 11. 线性表的抽象数据类型定义：

　　　　　　　　ADT　　线性表（List）

　　　　　　　　Data　　

　　　　　　　　　　　　线性表的数据对象集合为{a₁,a₂,……,a_n}，每个元素的类型均为DataType。

　　　　　　　　　　　　其中，除第一个元素a1外，每一个元素有且只有一个直接前驱元素，除了最后一个元素an外，每一个元素有且只有一个直接后继元素。

　　　　　　　　　　　　数据元素之间的关系是一对一的关系。

　　　　　　　　Operation

　　　　　　　　　　　　操作

　　　　　　　　endADT

数据结构与算法学习笔记（三）

原文：http://www.cnblogs.com/czq1989/p/5235888.html