数据结构研究如何使用存储区解决问题

算法研究解决常见问题的方法

数字之间的关系可以从两个完全不同的角度

进行描述

逻辑关系（逻辑结构）描述数字之间和计算机

无关的关系

物理关系（物理结构）描述存放数字的存储区

之间的关系

逻辑结构分为如下几种

1.集合结构：所有数字可以看作一个整体

2.线性结构：可以用一条有顺序的线把所有

数字连起来

3.树状结构：所有数据都是从一个数据开始

向一个方向扩展出来的，任何数据

可以扩展出多个其他数据

4.网状结构：任何两个数字之间可以有直接的

联系，所有数字之间的联系没有统一

方向

物理结构有以下两种

1.顺序结构：所有存储区在内存里连续排列

数组和动态分配内存都是顺序结构的例子

顺序结构中每个存储区有一个编号，

可以根据编号直接找到对应的存储区

根据编号找到存储区的方法叫随机访问，

顺序结构支持随机访问能力

顺序结构中存储区个数很难调整，这

有可能造成内存的浪费

顺序结构不适合进行插入或删除操作

/*    顺序结构演示*/#include 
     
      void remove_num(int *p_num, int size, int num) {    int num1 = 0;    for (num1 = 0;num1 <= size - 1;num1++) {        if (num < *(p_num + num1)) {            *(p_num + num1 - 1) = *(p_num + num1);        }        else if (num1 && *(p_num + num1) < *(p_num + num1 - 1)) {            *(p_num + num1 - 1) = *(p_num + num1);            break;        }    }}void insert(int *p_num, int size, int num) {    int tmp = num, num1 = 0, tmp1 = 0;    for (num1 = 0;num1 <= size - 1;num1++) {        if (tmp < *(p_num + num1)) {            tmp1 = tmp;            tmp = *(p_num + num1);            *(p_num + num1) = tmp1;        }        else if (num1 && *(p_num + num1) < *(p_num + num1 - 1)) {            tmp1 = tmp;            tmp = *(p_num + num1);            *(p_num + num1) = tmp1;            break;        }    }}int main() {    int arr[20] = {
   2, 6, 12, 14, 17, 21, 23,        31, 35, 37};    int num = 0;    insert(arr, 20, 27);    for (num = 0;num <= 19;num++) {        printf("%d ", arr[num]);    }    printf("\n");    remove_num(arr, 20, 14);    for (num = 0;num <= 19;num++) {        printf("%d ", arr[num]);    }    printf("\n");    return 0;}
     

 

2.链式物理结构：由多个无关的存储区构成，

任何两个存储区之间可以用指针连接

链式物理结构中每个存储区叫做一个

结点

单向线性链式物理结构中任何两个结点

之间都有前后关系（每个结点里只

需要包含一个指针）

单向线性链式物理结构中最后一个结点

里的指针必须是空指针

链式物理结构不直接支持随机访问能力

可以在所有结点前增加一个无效头结点，

在所有结点后增加一个无效尾结点，这样

可以简化程序的编写　　

/*    链式物理结构演示*/#include 
     
      typedef struct node {    int num;    struct node *p_next;} node;int main() {    node node1 = {
   1}, node2 = {
   5}, node3 = {
   12}, head = {
   0}, tail = {
   0}, node4 = {
   7};    int cnt = 0;    node *p_node = NULL;    node1.p_next = &node2;    node2.p_next = &node3;    head.p_next = &node1;    node3.p_next = &tail;    for (p_node = &head;p_node != &tail;p_node = p_node->p_next) {        node *p_first = p_node;        node *p_mid = p_first->p_next;        node *p_last = p_mid->p_next;        if (p_mid != &tail) {            printf("%d ", p_mid->num);        }    }    printf("\n");    for (p_node = &head;p_node != &tail;p_node= p_node->p_next) {        node *p_first = p_node;        node *p_mid = p_first->p_next;        node *p_last = p_mid->p_next;        if (p_mid != &tail && cnt == 2) {            printf("数字是%d\n", p_mid->num);        }        cnt++;    }    for (p_node = &head;p_node != &tail;p_node = p_node->p_next) {        node *p_first = p_node;        node *p_mid = p_first->p_next;        node *p_last = p_mid->p_next;        if (p_mid == &tail || p_mid->num > node4.num) {            p_first->p_next = &node4;            node4.p_next = p_mid;            break;        }    }    for (p_node = &head;p_node != &tail;p_node = p_node->p_next) {        node *p_first = p_node;        node *p_mid = p_first->p_next;        node *p_last = p_mid->p_next;        if (p_mid != &tail) {            printf("%d ", p_mid->num);        }    }    printf("\n");    for (p_node = &head;p_node != &tail;p_node = p_node->p_next) {        node *p_first = p_node;        node *p_mid = p_first->p_next;        node *p_last = p_mid->p_next;        if (p_mid != &tail && p_mid->num == 5) {            p_first->p_next = p_last;            break;        }    }    for (p_node = &head;p_node != &tail;p_node = p_node->p_next) {        node *p_first = p_node;        node *p_mid = p_first->p_next;        node *p_last = p_mid->p_next;        if (p_mid != &tail) {            printf("%d ", p_mid->num);        }    }    printf("\n");    return 0;}
     

 

链式物理结构中每个有效结点都应该是动态

分配的

链式物理结构中能容纳的数字数量可以灵活

变化

数据结构由一组存储区和一组相关的函数构成

这些函数提供了对存储区的使用方法

程序中的其他语句只能通过这组函数使用这些

存储区

/*    动态分配链式物理结构演示*/#include 
     
      #include 
      
       typedef struct node {    int num;    struct node *p_next;} node;int main() {    int num = 0;    node head = {
   0}, tail = {
   0}, *p_tmp = NULL, *p_node = NULL;    head.p_next = &tail;    while (1) {        printf("请输入一个数字：");        scanf("%d", &num);        if (num < 0) {            break;        }        p_tmp = (node *)malloc(sizeof(node));        if (!p_tmp) {            continue;        }        p_tmp->num = num;        p_tmp->p_next = NULL;        for (p_node = &head;p_node != &tail;p_node = p_node->p_next) {            node *p_first = p_node;            node *p_mid = p_first->p_next;            node *p_last = p_mid->p_next;            if (p_mid == &tail) {                p_first->p_next = p_tmp;                p_tmp->p_next = p_mid;                break;            }        }    }    printf("请输入要删除的数字：");    scanf("%d", &num);    for (p_node = &head;p_node != &tail;p_node = p_node->p_next) {        node *p_first = p_node;        node *p_mid = p_first->p_next;        node *p_last = p_mid->p_next;        if (p_mid != &tail && p_mid->num == num) {            p_first->p_next = p_last;            free(p_mid);            p_mid = NULL;            break;        }    }    for (p_node = &head;p_node != &tail;p_node = p_node->p_next) {        node *p_first = p_node;        node *p_mid = p_first->p_next;        node *p_last = p_mid->p_next;        if (p_mid != &tail) {            printf("%d ", p_mid->num);        }    }    printf("\n");    while (head.p_next != &tail) {        node *p_first = &head;        node *p_mid = p_first->p_next;        node *p_last = p_mid->p_next;        p_first->p_next = p_last;        free(p_mid);        p_mid = NULL;    }    return 0;}