数据结构基础1——概念
## 1、数据结构研究内容
这是一门研究==非数值计算程序设计中的操作对象==，及这些对象之间的==关系==和==操作==的学科。
==程序设计的实质==：为所处理的问题选择一种好的数据结构，并在此结构的基础上施加一种好的算法。
## 2、基本概念
### （1）数据
一切能输入计算机并被计算机程序处理的符号的总称。
### （2）数据元素
组成数据的基本单位，在计算机中通常被当作一个整体进行考虑和处理。
### （3）数据项
组成数据的，局有独立含义的，不可分割的最小单位。
### （4）数据对象
性质相同的数据元素的集合。
是数据的子集。
## 3、数据结构
互相之间存在一种或多种特性关系的数据元素的集合。
结构指的是数据元素之间的关系
### （1）逻辑结构
从逻辑关系上描述数据，与数据的存储无关，独立于计算机
两要素：数据元素，关系
#### 集合结构：
数据元素之间除了“同属于一个集合”之外，再无其他关系。
#### 线性结构：
数据元素之间存在一对一的关系。例如，数组、字符串、线性表、栈、队列等
#### 树形结构：
数据元素之间存在一对多的关系。例如，二叉树（两个分支），树（多个分支）
#### 图形结构或网状结构
数据元素之间存在多对多的关系。例如，有向图、无向图
### （2）存储结构
数据对象在计算机中的存储表示，也被称为物理结构。
将数据存入计算机时，通常要求既要存储数据元素，又要存储数据元素之间的关系。
#### 顺序存储：
将数据元素存入一片连续的存储空间中，借助数据元素在存储器中的相对位置表示数据元素之间的逻辑关系，通常借助程序设计语言中的数组描述
#### 链式存储
链式存储无需占用连续的存储空间，为了表示元素之间的关系，需要给每个元素附加一个节点，保存下一个元素的地址，通常借助指针来描述
## 4、数据类型
是高级程序设计语言中的一个基本概念，是一个值集以及定义在这个值集上的一组操作的总称
体现了程序设计语言的数据描述和处理能力
## 5、抽象数据类型（abstract data type，缩写为：ADT）
是由用户定义的、表示应用问题的数学模型，以及定义在这个模型上的一组操作的总称
包括：数据对象，数据关系，对数据对象的基本操作
定义格式如下：
```C
ADT 抽象数据类型名{
数据对象：（数据对象的定义）
数据关系：（数据关系的定义）
基本操作名1（参数列表）
初始条件：条件描述
操作结果：结果描述
基本操作名2（参数列表）
初始条件：条件描述
操作结果：结果描述
...
}ADT 抽象数据类型名
```
基本操作有两种参数
赋值参数：只为操作提供输入
引用参数：以&符号打头，除了提供输入外，还将返回操作结果
初始条件：描述了操作之前数据结构和参数列表应满足的条件，若为空，则省略。
操作结果：描述了操作正常结束之后，数据结构的变化状况和应返回的结果
```C
//复数的抽象数据的定义
ADT Complex{
数据对象：D = {e1, e2 | e1, e2∈R，R是实数集}；
数据关系：S = {<e1, e2> | e1是复数的实部， e2是复数的虚部}
基本操作：
Create(&C, x, y)
操作结果：构造复数C，实部与虚部的值分别为x和y
GetReal(C)
初始条件：复数C已存在
操作结果：返回复数C实部的值
GetImag(C)
初始条件：复数C已存在
操作结果：返回复数C虚部的值
Add(C1, C2)
初始条件：C1，C2是复数
操作结果：返回C1、C2的和
Sub(C1, C2)
初始条件：C1，C2是复数
操作结果：返回C1、C2的差
Delete(C)
初始条件：复数C已存在
操作结果：删除复数C
}ADT Complex
//复数的抽象数据类型的实现
typedef struct
{
float real;
float imag;
}Complex;
void Creat(Complex ** C, float x, float y)
{
*C = malloc(sizeof(Complex));
*C->real = x;
*C->imag = y;
}
float GetReal(Complex C)
{
return C.real;
}
float GetImag(Complex C)
{
return C.imag;
}
Complex Add(Complex C1, Complex C2)
{
Complex sum;
sum.real = C1.real + C2.real;
sum.imag = C1.imag + C2.imag;
return sum;
}
Complex Sub(Complex C1, Complex C2)
{
Complex dif;
dif.real = C1.real - C2.real;
dif.imag = C1.imag - C2.imag;
return dif;
}
viod Delete(Complex * C)
{
free(C);
}
```