【C语言】数据结构

小灰灰 2022-06-10 00:46 246阅读 0赞

1、数据结构研究如何使用存储区

2、算法研究常见问题的通用解决方法

3、数字间的关系可以从两个不同的角度描述

> a、逻辑关系（逻辑结构）：描述数字和计算机之间无关的关系  
> b、物理关系（物理结构）：描述存放数字的存储区之间的关系

4、逻辑结构分一下四种：

> a、集合结构：所有数字可以被看作一个整体（最弱的一种关系，再弱就是没有关系）  
> b、线性结构：可以用一条有顺序的线把所有数字串起来  
> c、树状结构：所有数据都是从一个数据向某个方向扩展出来的，任何一个数据均可扩展出多个其他数据  
> d、网状结构：任何两个数字之间都可以有直接的联系，所有数据之间的联系没有统一的方向

5、物理结构有如下两种:  
a、顺序结构：

> ● 所有存储区在内存中是连续排列的。  
> ● 数组和动态分配内存都是顺序物理结构的例子。  
> ●顺序存储结构里每个存储区都有一个编号，可以通过编号直接找到对应的存储区  
> ●顺序存储结构不太适合调整存储区的个数  
> ● 容易造成存储区的浪费  
> ● 顺序物理结构难以进行插入和删除操作

b、链式物理结构：

> ● 由多个相互独立的存储区构成，任何两个存储区之间可以用指针链接  
> ● 链式物理结构里每个存储区都是一个结构体类型的存储区，他们叫做节点。  
> ● 单向线性链式物理结构里面任何两个节点之间都有前后顺序（每个节点里面只需包含一个指针就可以了）  
> ● 单向线性链式物理结构里面最后一个节点里面的指针必须为空  
> ●可以在单向线性链式物理结构前面增加一个节点，叫做头节点，在后面加一个节点叫做尾节点  
> ● 头和尾节点不用来记录数字，只是为了占位置  
> ●链式物理结构不直接支持随机访问能力，但是可以模拟随机访问能力(也就是制定对某个数据进行处理)

eg:      
    int cnt = 0;
    for(p_node = &head; p_node != &tail; p_node = p_node->p_next) {
    node *p_first = p_node;         //p_first 和p_node捆绑 最多移动到最后一个有效节点，不和最后一个捆绑,p_node随着循环在变化,所以后面的也在变化
    node *p_mid = p_first->p_next;    //p_mid 和p_first下一个捆绑
    node *p_last = p_mid->p_next;        //p_last 和 p_mid 下一个捆绑
    if(p_mid != &tail && cnt == 2) {
            printf("%d\n", p_mid->num);
            break;
      }
      cnt++;
    }

6、链式物理结，栈

1、链式物理结构适合进行插入和删除操作
    2、处理单一节点的时候只需处理p_mid即可，处理某个位置的时候处理p_first和p_mid中间的位置 3、链式物理结构中的有效节点通常是动态分配的，这样可以根据实际情况随时调整链式物理结构的节点个数 4、数据结构由一组存储区和相关函数构成 5、这些函数提供了对这组存储区的使用方法 6、程序里不可以直接操作存储区，而应该通过数据结构里发函数来操作 -------------------------------------------------------------------------------- 7、栈是一种数据结构 8、栈是用来存放数字的，这写数字是有前后顺序的 9、先进入栈的数字在前，后进入的在后 10、每次从栈里获得的数字一定是最后一个放进去的数字 11、这种使用数字的方式叫做后进先出 12、实现栈的时候需要提供一个叫做push的函数它负责向栈里添加一个函数 13、实现栈的时候还需要提供一个叫做pop的函数，负责从栈里取出一个数字 --------------------------------------------------------------------------------
    14、队列也是一种数据结构
    15、队列也可以存放一组数字，这些数字间也有顺序，先进入的在前，后进入的在后
    16、从队列获得的数字一定是从最先进去的数字
    17、这种使用数字的方式是先进先出
    18、实现队列的时候也需要push函数，负责向队列里加入一个数字
    19、实现队列的时候也需要pop函数，负责从队列里取出一个数字

/* * 链式物理结构演示 * */
    typedef struct node{
        int num;
        struct node *p_next;
    }node;
    #include <stdio.h>
    int main() {
        node node1 = {
       10}, node2 = {
       20}, node3 = {
       30}, head = {
       0}, tail = {
       0};
        node *p_node = NULL;//相当于num做一个循环变量
        int cnt = 0;
        head.p_next = &node1;
        node1.p_next = &node2;//将各变量连接起来
        node2.p_next = &node3;//
        node3.p_next = &tail;
    
        for(p_node = &head; p_node != &tail; p_node = p_node->p_next) {
       //
            node *p_first = p_node; //p_first 和p_node捆绑 最多移动到最后一个有效节点，不和最后一个捆绑
            node *p_mid = p_first->p_next;//p_mid 和p_first下一个捆绑
            node *p_last = p_mid->p_next;//p_last 和 p_mid 下一个捆绑
            if(p_mid != &tail) { //p_mid不指向最后一个，即不显示最后的尾节点
                printf("%d ", p_mid->num);
            }
        }
        for(p_node = &head; p_node != &tail; p_node = p_node->p_next) {
            node *p_first = p_node; //p_first 和p_node捆绑 最多移动到最后一个有效节点，不和最后一个捆绑,p_node随着循环在变化,所以后面的也在变化
            node *p_mid = p_first->p_next;//p_mid 和p_first下一个捆绑
            node *p_last = p_mid->p_next;//p_last 和 p_mid 下一个捆绑
            if(p_mid != &tail && cnt == 2) {
                printf("%d\n", p_mid->num);
                break;
            }
            cnt++;
        }
        return 0;
    }