数据结构（1）—— 数据结构的三大结构

计算机程序设计 = 数据结构 + 算法
数据结构研究变量的管理方式，算法研究解决特定问题的方法。
数据结构分三个层次：逻辑结构（抽象层）、物理结构（结构层）、运算结构（实现层）。

1.1 数据结构的逻辑结构

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

（我们主要研究线性结构和树型结构。）

1.2 数据结构的物理结构

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

/*链式结构练习*/
#include <stdio.h>

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
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46

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

1.3 数据结构的运算结构

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