数据结构-三大结构

计算机程序设计 = 数据结构 + 算法

数据结构研究变量的管理方式，算法研究解决特定问题的方法。

数据结构分三个层次：逻辑结构（抽象层）、物理结构（结构层）、运算结构（实现层）。

数据结构的逻辑结构

逻辑结构指人对数据之间关系的理解和看法，逻辑结构和计算机无关。 逻辑结构： 1、集合结构：这种结构表示数据可以合并成一个整体。 这是数据之间关系最弱的一种，就仅比那个一点关系都没有的强一点。 2、线性结构：这种结构中数据之间有一对一的关系（如排队）。 3、树型结构：这种结构中数据之间有一对多的关系，这个关系称为父子关系（典型的如细胞分裂）。 4、网状结构：这种结构中数据之间有多对多的交叉映射关系。 （我们主要研究线性结构和树型结构。）

数据结构的物理结构

物理结构描述计算机内部数据之间实际的关系。 物理结构： 1、顺序结构：结构中的数据元素存放在一段连续的内存空间中，典型代表就是数组。随机访问方便，插入删除复杂。 2、链式结构：这种结构中不同的数据被存储在计算机里不同的地方，他们的物理位置之间完全没有关系。链式结构由多个节点构成，每个节点中包括有效数据和至少一个指针变量。 对链式结构进行操作时，如果不会修改结构则使用一级指针变量就可以了，如果会修改结构则需要使用二级指针变量,其实，一级指针变量也可以修改链式结构。 链式结构适合进行插入删除操作，不适合进行随机访问。

  /链式结构练习/

#include

typedef struct node{
 int num;
 struct node \*p\_next;//void \*p\_next;
 }node;
 node node1 = {1,NULL};

int main(){
 node *p_head = NULL;//头指针
 node node2 = {2,NULL};
 static node node3 = {3,NULL};
 node node5 = {5,NULL};//新添一个节点，把它加入链表中

p_head = &node1;
 node1.p_next = &node2;
 node2.p_next = &node3;
 //用二级指针把新增节点5挂上去
 /\*node \*\*pp\_tmp = &p\_head;
 while (*pp_tmp){
 pp\_tmp = &((*pp\_tmp)->p_next);
 }
 \*pp_tmp = &node5;\*/

//第二种把新增节点5加进去的方法
 node *p_tmp = NULL;
 if (p_head){
 p\_tmp = p\_head;
 while (p\_tmp->p\_next){
 p\_tmp = p\_tmp->p_next;
 }
 p\_tmp->p\_next = &node5;
 }
 else {
 p_head = &node5;
 }
 //显示所有节点数据
 p\_tmp = p\_head;
 while (p_tmp){
 printf("%-3d",p_tmp->num);
 p\_tmp = p\_tmp->p_next;
 }
 printf("\\n");
 return 0;
 }

逻辑结构可以采用多种物理结构实现，它们之间没有明确的一对一的关系。

数据结构的运算结构

数据结构的基本操作（运算结构）： 1、创建/销毁 分配资源、建立结构、释放资源 2、插入/删除 增加、减少数据元素 3、获取/修改 遍历、迭代、随机访问 （增删改查） 4、排序/查找 算法应用