1.1? 数据结构的学科定义
? ? ?是一门研究非数值计算的程序设计问题中计算机的操作对象以及它们之间的关系和操作等的学科。
数值计算：数值的加减乘除等计算。
非数值计算：除了数值计算外的数据，如字符、图形、图像、声音等。
?例1中a1是a2的前驱，a2是a1的后继。对于中间的元素只有一个前驱和后继（一一对应）
1.2? ?基本概念和术语
数据：是客观事物的符号表示。在计算机科学中指的是所有能输入到计算机中并被计算机程序处理的符号总称。如：数字、字符、图形、图像、声音等。
数据元素：是数据的基本单位，在程序中通常作为一个整体来进行考虑和处理。
一个数据元素可以由若干个数据项组成。
数据项：是数据不可分割的最小单位，数据项是对客观事物某一方面特性的数据描述。
例：
姓名??? 性别?? 年龄?? 班级?? 健康情况
?王小林???? 男????? 18??? 13A???? 良好
在这个表中 “王小林 男 18 13A 良好”是数据元素，其单个项是数据项。
链表中：
?
?a1在数据域（代表一个数据元素），地址在指针域。箭头指示下一个元素地址（又叫指针)
?单个链表有两个数据项。
?数据结构：是指相互之间存在一种或多种特定关系的数据元素的集合。
元素之间的关系称为结构。
数据结构指带结构的数据元素的集合。
数据元素之间的逻辑关系有四种基本类型：集合、线性结构、树型结构、网状结构（图状结构）。
?数据结构的形式定义
是一个二元组：Data-Structure=(D,S） 其中D是数据元素的有限集，S是D上关系的有限集即结构。
逻辑结构与存储结构
逻辑结构：Data-Structure=(D,S)强调数据元素之间的逻辑关系，即数据之间的逻辑结构。
存储结构：数据结构在计算机中的表示称为数据的物理结构，有称为存储结构。也叫逻辑结构在存储器中的映像。
算法的设计取决于逻辑结构。
算法的实现取决于存储结构。
数据类型指的是一个值的集合和定义在该值集上的一组操作的总称。如C语言中的整型变量。
值的集合：某区间上的整数
操作：加减乘除取模等算术运算。
按照值得不同特性，高级语言得数据类型分为：原子类型（非结构的，值不可分解）、结构类型（值是由若干成分按某种结构组成的，可分解）。
1.3? 抽象数据类型
抽象数据类型（ADT）是指一个数学模型以及定义在该模型上的一组操作。（仅取决于他的一组逻辑特性，而与其在计算机内部如何表示和实现无关）
ADT是形式化定义是三元组：ADT=（D,S,P）? ? ?D 是数据结构；S 是在D上的关系；P 是对D的基本操作集。
ADT的一般定义：
ADT抽象数据类型名{
数据对象D:<数据对象的定义>
数据关系S：<数据关系的定义>
基本操作P：<基本操作的定义>
} ADT抽象数据类型名。
基本操作名（参数表）
初始条件：<初始条件的描述>
操作结果：<操作结果的描述>
参数：（1）赋值参数：只提供输入值
? ? ? ? ? （2）引用参数：以&开头提供输入值并返回操作结果。
?