[其它应用]

嵌入式实时性可以考虑静态链表~

[复制链接]
1749|8
手机看帖
扫描二维码
随时随地手机跟帖
两只袜子|  楼主 | 2024-4-27 10:00 | 显示全部楼层 |阅读模式
大家好,我是bug菌~



首先跟大家聊聊什么是静态链表,静态链表是一种使用数组来实现的链​表结构。在静态链表中,数组的每个元素称为一个节点,节点中包含两部分信息:数据和指向下一个节点的“指针”,这里的指针并不是C语言里语法上的指针,它主要是标记节点在数组中的位置,也就是数组的下标索引,其实广义上也是一种指针吧。



再来看下静态链表怎么玩的吧~



所以与动态链表的差异点,主要是静态链表的节点在内存中是连续存储的,而且节点的数量是固定的。



有代码有真相:



#include <stdio.h>

#define MAX_SIZE 100

// 静态链表的节点结构
typedef struct Node {
    int data; // 数据域
    int next; // 指针域,指向下一个节点的索引
} Node;

// 初始化静态链表
void init(Node list[]) {
    // 将所有节点的 next 域初始化为 -1,表示空闲状态
    for (int i = 0; i < MAX_SIZE; i++) {
        list.next = -1;
    }
}

// 释放节点
void release(Node list[], int index) {
    // 将节点标记为可用状态
    list[index].next = -1;
}

// 获取可用的空闲节点索引
int getFreeNode(Node list[]) {
    for (int i = 0; i < MAX_SIZE; i++) {
        if (list.next == -1) {
            return i;
        }
    }
    return -1; // 没有可用节点
}

// 在链表末尾插入新节点
void insert(Node list[], int *head, int data) {
    int freeIndex = getFreeNode(list);
    if (freeIndex != -1) {
        // 在空闲节点处插入新节点
        list[freeIndex].data = data;
        list[freeIndex].next = -1;
        int i = *head;
        while (list.next != -1) {
            i = list.next;
        }
        list.next = freeIndex;
    } else {
        printf("No free node available.\n");
    }
}

// 删除节点
void deleteNode(Node list[], int *head, int data) {
    int prevIndex = -1;
    int currIndex = *head;
    while (currIndex != -1) {
        if (list[currIndex].data == data) {
            if (prevIndex != -1) {
                list[prevIndex].next = list[currIndex].next;
            } else {
                *head = list[currIndex].next;
            }
            release(list, currIndex);
            printf("Node with data %d deleted.\n", data);
            return;
        }
        prevIndex = currIndex;
        currIndex = list[currIndex].next;
    }
    printf("Node with data %d not found.\n", data);
}

// 打印链表中的所有节点
void printList(Node list[], int head) {
    int i = head;
    while (i != -1) {
        printf("%d ", list.data);
        i = list.next;
    }
    printf("\n");
}

int main() {
    Node list[MAX_SIZE]; // 定义静态链表
    int head = 0; // 头指针

    // 初始化链表
    init(list);

    // 插入节点
    insert(list, &head, 10);
    insert(list, &head, 20);
    insert(list, &head, 30);

    // 打印链表
    printf("Static Linked List: ");
    printList(list, head);

    // 删除节点
    deleteNode(list, &head, 20);

    // 打印删除节点后的链表
    printf("Static Linked List after deletion: ");
    printList(list, head);

    return 0;
}


这样看静态链表代码上的两个特点,采用固定内存区域上数组,指向下一个元素存储的是数组索引。



顺便整理下动态数组静态数组的差异,两者也如前面说的,主要是在内存管理和节点分配两个方面有比较大的差异点:



1、内存管理方式:



动态链表: 在动态链表中,节点通常是通过动态内存分配函数(如 malloc 或 new)在堆内存中分配的。这意味着节点在代码运行时动态地分配和释放内存。节点的数量可以根据需要进行动态调整,只要你的动态内存空间足够,因此在插入和删除节点时相对更加灵活。



静态链表: 静态链表使用数组实现,节点的数量在编译时就被确定,并且存储空间是静态分配的,话说回来,你可以在使用前动态分配一片内存供静态链表使用,但在静态链表在使用过程中没法动态地增加或减少总的节点的数量,当然你说完全没法改变吧,也不是不行,就是相对来说性价比不高。



2、节点的分配和释放:



动态链表: 节点在堆内存中动态分配,因此可以根据需要创建新节点,并且可以在不需要时释放节点的内存,给其他任务去使用。节点的生命周期由bug工程师自己管理,可以根据需要进行内存管理,如果没管理好,就会出现内存泄漏或者野指针等问题。



讲了这么多,到底静态链表有啥只用?有什么优势?



主要是用在内存受限的嵌入式系统,比如说单片机,在内存受限的这样的嵌入式系统中,动态内存分配可能会导致碎片化问题,而静态链表通过预分配数组空间,避免了频繁的内存分配和释放。



需要实时性有要求的系统:对于需要保证实时性能的系统,静态链表的实现更加可靠,因为它避免了动态内存分配和释放的不确定性,从而减少了系统出现延迟的可能性,这一点很重要。



固定大小的数据结构,相对动态链表的话内存问题更加容易受管控。



小型数据集:当数据集较小,不需要频繁进行节点插入和删除操作时,静态链表可以提供较好的性能和简洁的实现。

使用特权

评论回复
tpgf| | 2024-5-8 08:29 | 显示全部楼层
静态链表和动态链表的差别都体现在什么方面上啊

使用特权

评论回复
tpgf| | 2024-5-8 09:34 | 显示全部楼层
我们操作链表的时候是不是必须使用指针才能实现呢

使用特权

评论回复
keaibukelian| | 2024-5-8 10:36 | 显示全部楼层
静态链表的长度是固定的还是变化的呢

使用特权

评论回复
renzheshengui| | 2024-5-8 22:51 | 显示全部楼层
在C语言中,静态链表的表现形式即为结构体数组,结构体变量包括数据域data和游标CUR

使用特权

评论回复
paotangsan| | 2024-5-8 23:24 | 显示全部楼层
静态链表的实质是不是就是数组呢

使用特权

评论回复
guanjiaer| | 2024-5-8 23:57 | 显示全部楼层
静态链表对单片机的存储空间占用的是不是比较多呢

使用特权

评论回复
亚瑟| | 2024-5-24 22:20 | 显示全部楼层
都静态了,应该是固定大小的吧

使用特权

评论回复
yangjiaxu| | 2024-5-27 22:12 | 显示全部楼层
这种链表是不是适合做UI界面操作啊?

使用特权

评论回复
发新帖 我要提问
您需要登录后才可以回帖 登录 | 注册

本版积分规则

1923

主题

6679

帖子

8

粉丝