数据结构 概述

一  数据

1. 数据（Date）：能被计算机处理的各种符号集合，信息的载体，对客观事物符号化的表示，能够被计算机识别、存储和加工，包括数值型的数据（能进行运算的），非数值型
2. 数据元素（Date Element）：是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。也简称元素，或称之为记录、节点或顶点。一个数据元素可以由若干个数据项组成
3. 数据项（Date Item）：构成数据元素不可分割的最小单位
4. 数据对象（Date Object）：是性质相同的数据元素的集合，是数据的一个子集
5. 数据 >  数据项 > 数据元素 > 数据项

二 数据结构

1. 数据结构就是把数据元素按照一定的关系组织起来的集合，用来组织和存储数据
2. 分类：逻辑结构与物理结构（存储结构）
3. 逻辑结构：划分方法一

1. 线性结构：有且仅有一个开始和一个终端节点，并且所有节点都最多只有一个直接。（一对一） 例如：线性表、栈、队列串    
2. 非线性结构：一个节点可能有多个直接前趋和直接后继（一对多或者多对多）例如：树、图

4. 逻辑结构：划分方法二                                                                                                                a. 集合结构：数据元素处了属性同一个集合外，他们之间没有任何关系：
   
   b. 线性结构：数据元素之间存在一对一的关系：
   
   c. 树形结构：元素存在一对多的层次关系：
   
   d. 图形结构：数据元素是多对多的关系：
5. 物理结构：是逻辑结构在计算机中真正的表示方式（又称之为映射）即数据元素之间的逻辑关系由元素的存储位置来表示

1. 顺序存储结构：把数据元素放到地址连续的存储单元中，常用的数组就是顺序存储结构
   
   优点：可以通过索引来访问元素，查找效率高；缺点：存储结构内部难操作，例如在原存储结构中插入新的元素，则需要将插入点以后的元素索引全部发生变化
2. 链式存储结构：把数据元素存放在任意的存储单元里面，这组存储空间可以是连续的，也可以是不连续的。此时，数据元素之间并不能反应元素的逻辑关系，因此在链式存储的数据结构中引进了一个指针存储数据元素的地址，这样通过地址就可以找到相关联数据元素的位置，在存储一个元素的同时，存储下一个元素的地址（指针）。存在头指针，与最后一个空指针。
   
   优点：存储内部容易操作，易插入，缺点：因为元素相互关联，难以查找                
3. 索引存储结构：在存储结点信息的同时，还建立附加的索引表（方便查找数据）。索引表中的每一项称为一个索引项，索引项的一般形式是：（关键字，地址），关键字是唯一标识一个结点的那些数据项。若每一个结点都有对应的索引项，则称之为稠密索引，若一组节点对应一个索引项，则称之为稀疏索引。                                                    
   
4. 散列存储结构：根据结点的关键字直接计算出该结点的存储地址
   

三  数据类型（Data Type,DT）

1. 在使用高级程序设计语言时，必须对程序中出现的每个变量、常量或表达式，明确说明它们的数据类型。
2. 一些最基础的数据结构可以用数据类型来实现，如数组、字符串等。而另一些常用的数据结构，如栈、队列、树、图等，不能直接用数据类型来表示。
3. 用处：明显或者隐含的规定了在执行程序期间变量和表达式的所有可能的取值范围，以及在这些数值范围上允许进行的操作。即：约束变量或者常量的取值范围与操作。
4. 定义：数据类型是一组性质相同的值的集合以及定义于这个值集合上的一组操作的总称。
5. 数据类型 = 值的集合 + 值集合上的一组操作

四  抽象数据类型（Abstract Data Type，ADT）

1. 是指一个数据模型以及定义在此数据模型上的一组操作。由用户定义，从问题抽象出数据模型（逻辑结构），还包括定义在数据模型上的一组抽象运算（相关操作）。
2. 抽象数据类型：不考虑计算机内的具体存储结构与运算的具体实现算法。
3. 形式定义：三元组表示（D，S，P；D 是数据对象；S 是D上的关系集；P 是对D的基本操作集）。
4. 定义格式：数据对象、数据关系的定义用伪代码描述
   
   参数表：赋值参数：只为操作提供初始值；引用参数：以&打头，除可以提供输入值外，还将返回操作结果。  初始条件：描述操作执行之前数据结构和参数应满足的条件，若不满足，则操作失败，并返回相应出错信息。若初始条件为空，则省略之。 操作结果：说明操作正常完成之后，数据结构的变化状况和应返回的结果。
5. 定义举例：伪代码

ADT Circle {
  数据对象：D = {r, x, y| r, x, y均为实数} 
  数据关系：S = {<r, x, y>| r是半径, <x, y>是圆心坐标} 
  基本操作：
  Circle(&C, r, x, y)  //使用&号，表示将返回操作结果，一个圆 C 
    操作结果：构造一个圆
  double Area(C)
    初始条件：圆已存在。
    操作结果：计算面积。
  double Circumference(C)
    初始条件：圆已存在。
    操作结果：计算周长。
  ...
} ADT Circle

ADT Complex{
    D = {r1, r2| r1, r2都是实数}
    S = {<r1, r2>| r1是实部, r2是虚部}
    assign(&C, v1, v2)
        初始条件：空的复数C已存在。
        操作结果：构造复数C，r1，r2分别被赋值以参数v1，v2的值。
    destory(&C)
        初始条件：复数C已存在。
        操作结果：复数C被销毁。
...
}ADP Complex

1.  概念小结
   
2. 实现抽象数据类型：抽象数据类型可以通过固有的数据类型（如整型、实型、字符型等）来表示和实现。即利用处理器中已经存在的数据类型来说明新的结构，用已经实现的操作来组合新的操作。
   
3. 实例演示：

#include<stdio.h>
typedef struct{
  float realpart;
  float imagpart;
}Complex;
//->表示指针类型的变量获取成员变量；.表示普通变量获取成员变量 
void assign(Complex* A, float real, float imag){ 
  A->realpart = real;  
  A->imagpart = imag; 
}
void add(Complex* c, Complex A, Complex B){
  c->realpart = A.realpart + B.realpart;
  c->imagpart = A.imagpart + B.imagpart;
}
int main(){
  Complex z1, z2, z3;
  assign(&z1, 8.0, 4.0);
  assign(&z2, 4.0, 3.0);
  add(&z3, z1, z2);
  printf("%f, %f", z3.imagpart, z3.realpart);
}