数据结构开篇及绪论（学习方向，基本概念和术语，抽象数据类型ADT，引用符&，抽象数据类型的表示，ADT小结）【DS】（a）
首先进行说明，我们这里所描述到的的数据结构的内容在之后的代码实现过程中都是用C语言实现，本篇博客是后面所有章节的基础，读者可以多次阅读本篇博客进行复习，也可以在之后的每章之前阅读本篇博客。
说明
程序设计中数据如果有关系，那么关系可以大概抽象为
线性关系，树形关系和图形关系。
数据结构的的研究内容包括：
逻辑结构 ：研究对象的特性及其相互之间的关系
存储结构：有效地组织计算机存贮
算法：有效地实现对象之间的 “运算” 关系
《数据结构》是一门研究非数值计算的程序设计问题中计算机的操作对象以及它们之间的关系和操作的一门学科。
基本概念和术语
数据（Data）
是对客观事物的符号表示，在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号的总称。
数据元素 （data element）
是数据的基本单位，在计算机程序中通常作为一个整体而考虑和处理。例如：学生管理系统，管理的是学生，那么就把数据元素作为一个数据元素。
数据对象 （data object）
性质相同的数据元素的集合，是数据的一个子集。
具体数据元素和数据对象要根据具体的情况而确定，比较灵活和具有针对性。并且数据元素的大小也是根据情况而定的。
数据项 （data item）
一个数据元素可由若干个数据项组成，数据项是数据不可分割的最小单位。
结构（Structure）
是组成整体的各部分的关系和关联。
数据结构（ Data Structure）
数据结构是相互之间存在一种或多种特定关系的数据元素的集合，也可称其为逻辑结构。
四类基本数据结构：
我们上面用圆圈表示元素。那么元素之间的连线表示元素之间的关系，如果是集合那么元素之间就没有关系。如果是线性，那么元素之间存在一对一的关系。如果是树形结构，那么就是一对多的关系。如果是图形关系，那么就是多对多的关系。
关系、关联的表示–用序偶表示【离散数学】
数据结构的形式定义：
Data_Structure = (D, R)
例如：复数数据结构Complex = (C, R)
C = {c1,c2|c1,c2属于任意实数}
R = {<c1,c2>|c1表示实部,c2表示虚部}
三种基本的关系
1:1 1:n n:m
物理结构(存储结构)
数据结构在计算机中的表示(映像)称为数据的物理结构。
顺序映像
顺序映像的特点是借助元素在存储器中的相对位置来表示数据元素之间的逻辑关系。
非顺序映像
非顺序映像的特点是借助指示元素存储地址的指针表示数据元素之间的逻辑关系。
数据类型：
一组性质相同的值的集合以及定义于这个值集合上的一组操作的总称。
值的集合+值集合上的一组操作
数据类型的作用：
约束变量的内存空间，
约束变量或常量的取值范围，
约束变量或常量的操作。
例如，C 语言中的 int 型变量，是指一定范围中的值构成的集合及一组操作（加、减、乘、除、乘方 等）的总称。
抽象数据类型（abstract data type ADT）
是指一个数学模型以及定义在该模型上的一组操作。抽象数据类型的定义仅取决于它的一组逻辑特性，而与其在计算机内部如何表示和实现无关。
我们自行认为抽象的数据类型只能团队内使用。
抽象数据类型 Abstract Data Type, ADT
含义：
一种数据类型，其数据对象和对象操作的规格说明独立于对象的存储表示和对象上操作的实现。
ADT的定义
定义：
和数据结构的形式定义相对应，抽象数据类型可以用三元组来刻画:(D,S,P)。其中D是数据对象，S是D上的关系集，P是对D的基本操作。
ADT 抽象数据类型名{
数据对象：<数据对象的定义>
数据关系：<数据关系的定义>
基本操作：<基本操作的定义>
} ADT 抽象数据类型名
其中，数据对象和数据关系的定义用伪码描述，基本操作的定义格式为：
基本操作名(参数表)
初始条件：<初始条件描述>
操作结果：<操作结果描述>
例：二元组的定义
ADT Compare{
数据对象：D={e1,e2| e1,e2为可比较的同类型的元素}
数据关系：R={< e1,e2 >}
基本操作：
InitCom(&C,ee1,ee2)
操作结果：构造一个二元组c，元素e1,e2分别被赋成ee1,ee2。
FirElemBig©
初始条件：二元组已经存在。
操作结果：如果首元素大，则返回1，否则返回0。
…
} ADT Compare
InitCom(&C,ee1,ee2)
上面的&并不是C语言中的取地址，而是C++中的引用类型，这里需要作以说明，因为之后需要用到。
例如：
#include <stdio.h>
#include<stdlib.h>
//&的常规应用
void swap(int x, int y)
{
int temp;
temp = x;
x = y;
y = temp;
}
int main()
{
int a = 4;
int b = 5;
swap(a, b);
printf("a = %d b = %d\n",a,b);
system("PAUSE");
return 0;
}
打印结果为：
无法实现交换
已经知道了值传递和指针传递的区别，不清楚的读者可以找到有专门的一篇博客进行说明。
#include <stdio.h>
#include<stdlib.h>
//&的常规应用
void swap(int * x, int * y)
{
int temp;
temp = *x;
*x = *y;
*y = temp;
}
int main()
{
int a = 4;
int b = 5;
swap(&a, &b);
printf("a = %d b = %d\n",a,b);
system("PAUSE");
return 0;
}
打印结果为：
这里交换成功
那么我们对于代码进行修改，使用引用
我们只改变
void swap(int * x, int * y)
为
void swap(int & x, int & y)
#include <stdio.h>
#include<stdlib.h>
//&的常规应用
void swap(int & x, int & y)
{
int temp;
temp = x;
x = y;
y = temp;
}
int main()
{
int a = 4;
int b = 5;
swap(a, b);
printf("a = %d b = %d\n",a,b);
system("PAUSE");
return 0;
}
打印结果为：
我们可以看出来这里的结果是正确的。
那么最后一次我们就使用了引用符号&
我们在这里对于引用加以说明：在主函数中调用的时候，将a的名称和swap参数x指向同一块内存空间，将5的名称b和swap函数中的y指向同一块内存空间，随着x，y函数调用结束被释放，由于x，y分别指向的是a，b变量的空间，那么a，b空间的值发生变化并且被保存下来。这样能方便的传值并且将才做的结果进行保留。是否加引用要看传递的值是是否被改变。
抽象数据类型的表示
抽象数据类型的表示就是要将该类型映射到计算机中，也就是确定抽象数据类型的存储结构以及给出基于该结构之上的基本操作的函数原型。
例如：
typedef int ElemType; //整形元组
typedef ElemType * Compare; //动态顺序存储结构
//初始化二元组
InitCom(Compare &C, ElemType ee1, ElemType ee2) //这里的&是一个引用
//判断二元组的首元素是否比次元素大
FirElemBig(Compare C) //这里不需要使用到引用，因为C看完之后没有任何变化
……
抽象数据类型的实现
抽象数据类型的实现就是基于特定存储结构之上的基本操作的实现。
例：
//初始化二元组
Status InitCom(Compare &C, ElemType ee1, ElemType ee2)
{
C = (ElemType *)malloc(2*sizeof(ElemType));
if(!C) exit (OVERFLOW);
C[0] = ee1; C[1] = ee2;
return OK;
}
//判断二元组的首元素是否大
Status FirElemBig(Compare C)
{
if(C[0] > C[1]) return TRUE;
else return FALSE;
}
ADT小结
抽象数据类型主要指用户在设计软件系统时自己定义的数据类型。
在构造软件系统的各个相对独立的模块时，定义一组数据和施与这些数据之上的一组操作，并在模块内部给出它们的表示和实现细节，在模块外部使用的只是抽象的数据和抽象的操作。