数据存储，链表还是数组？

2023-02-14 371

引言

链表和数组是两种不同的数据存储方式。链表是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。数组是把具有相同类型的若干元素按有序的形式组织起来的一种形式，数组中的各元素的存储是有先后顺序的，它们在内存中按照这个先后顺序连续存放在一起。本文将对这两种存储方式的优缺点做一个大致的介绍，并详细介绍链表在操作系统中定义和使用的方式。

一、链表和数组

链表是链式的存储结构，数组是顺序的存储结构，其在内存存储上的不同形式决定了其各自的特点。

链表通过指针来链接元素，链表中的结点顺序关系由指针来体现；数组将元素按次序依次存储，元素顺序关系由元素在数组中的位置（下标）确定。
链表节点的存储单元在程序执行时动态向系统申请，链表的结点个数可按需要增减；数组元素的存储单元在数组定义时分配，其元素个数是固定的，对于不是固定长度的列表，用可能最大长度的数组来描述。
链表插入删除元素不需要移动元素，且较为容易实现长度扩充，但是寻找某个元素较为困难；数组寻找某个元素较为简单，但插入与删除比较复杂。

总体来说，链表使用指针将一系列数据节点链接成数据链，相对于数组，它具有良好的动态性，建立链表时不需要提前知道数据量，可以随时分配空间，可以高效地在链表中的任意位置插入或者删除数据。操作系统中存在着大量的基础数据结构链表和链表项，理解链表对理解操作系统至关重要。

二、单向链表和双向链表

通常链表数据结构包含两部分，一部分是数据域，用于存储数据；另外一部分是指针域，用于建立与其它节点的关系。链表项中可以包含一个指向下一个链表项的指针而不包含指向上一个链表的指针，也可以两者都包含，前者称为单向链表，后者为双向链表。

OneOS物联网操作系统中提供的链表不包含数据域，使用时不是在链表结构中包含数据，而是在用户的数据结构中包含链表节点，操作系统中提供了双向链表及单向链表的一些比较通用的操作接口。

2.1 单向链表

OneOS操作系统中的单向链表包含一个节点指针，这个节点指针指向下一个节点。OneOS操作系统中的单向链表是一个非循环链表，单向链表本身首尾并非相连，单向链表中的最后一个节点指向OS_NULL（循环链表单向链表中的最后一个节点指向单向链表中的第一个节点），其示意图如下所示。

OneOS操作系统中单向链表节点的结构体如下所示。

struct os_slist_node
{
    struct os_slist_node *next;     /* Point to next node */
};

2.2 双向链表

OneOS操作系统中的双向链表包含了两个结点指针，一个节点指针指向下一个节点，另一个节点指针指向上一个节点。OneOS操作系统中的双向链表是一个循环链表，双向链表本身首尾相连，双向链表最后一个节点的指向下一个节点的节点指针指向第一个节点，第一个节点的指向上一个节点的节点指针指向最后一个节点，其示意图如下所示。

OneOS操作系统中双向链表节点的结构体如下所示。

struct os_list_node
{
    struct os_list_node *next;      /* Point to next node */
    struct os_list_node *prev;      /* point to previous node */
};

三、应用示例

单向链表应用示例

#include <oneos_config.h>#include <dlog.h>#include <os_errno.h>#include <shell.h>#include <string.h>#include <os_memory.h>#include <os_list.h>
#define TEST_TAG        "TEST"
#define STUDENT_NUM     10#define TEST_NAME_MAX   16
char *name[STUDENT_NUM] = {"xiaoming", "xiaohua", "xiaoqiang", "xiaoli", "xiaofang", "zhangsan", "lisi", "wangwu", "zhaoliu", "qianqi"};uint32_t score[STUDENT_NUM] = {70, 83, 68, 80, 88, 86, 78, 92, 55, 82};
struct student_score
{
    os_slist_node_t list_node;
    char name[TEST_NAME_MAX];
    uint32_t id;
    uint32_t score;
};typedef struct student_score student_score_t;
void single_list_sample(void)
{
    uint32_t i = 0;
    os_slist_node_t list_head = OS_SLIST_INIT(list_head);
    student_score_t *data;
    os_slist_node_t *node_temp;
    os_slist_node_t *node;

    LOG_W(TEST_TAG, "single_list_sample insert data");
    for (i = 0; i < STUDENT_NUM; i++)
    {
        data = os_malloc(sizeof(student_score_t));
        data->id = i;
        memset(data->name, 0, TEST_NAME_MAX);
        strncpy(data->name, name[i], TEST_NAME_MAX);
        data->score = score[i];
        if (i < STUDENT_NUM/2)
        {
            LOG_W(TEST_TAG, "insert tail -- id:%d score:%d name:%s", data->id, data->score, data->name);
            os_slist_add_tail(&list_head, &data->list_node);
        }
        else
        {
            LOG_W(TEST_TAG, "insert front-- id:%d score:%d name:%s", data->id, data->score, data->name);
            os_slist_add(&list_head, &data->list_node);
        }
    }

    LOG_W(TEST_TAG, "single_list_sample show result");
    os_slist_for_each(node, &list_head)
    {
        data = os_slist_entry(node, student_score_t, list_node);
        LOG_W(TEST_TAG, "id:%d score:%d name:%s", data->id, data->score, data->name);
    }

    LOG_W(TEST_TAG, "single_list_sample list_len is:%d", os_slist_len(&list_head));
    LOG_W(TEST_TAG, "single_list_sample delete the score less than 60");
    os_slist_for_each_safe(node, node_temp, &list_head)
    {
        data = os_slist_entry(node, student_score_t, list_node);
        if (data->score < 60)
        {
            LOG_W(TEST_TAG, "delete -- id:%d score:%d name:%s", data->id, data->score, data->name);
            os_slist_del(&list_head, &data->list_node);
            os_free(data);
        }
    }

    LOG_W(TEST_TAG, "single_list_sample list_len is:%d", os_slist_len(&list_head));
    LOG_W(TEST_TAG, "single_list_sample show result, and then delete");
    os_slist_for_each_safe(node, node_temp, &list_head)
    {
        data = os_slist_entry(node, student_score_t, list_node);
        LOG_W(TEST_TAG, "delete -- id:%d score:%d name:%s", data->id, data->score, data->name);
        os_slist_del(&list_head, &data->list_node);
        os_free(data);
    }

    LOG_W(TEST_TAG, "single_list_sample list_len is:%d", os_slist_len(&list_head));
}

SH_CMD_EXPORT(test_single_list, single_list_sample, "test single list");

运行结果

sh>test_single_list
W/TEST: single_list_sample insert data
W/TEST: insert tail -- id:0 score:70 name:xiaoming
W/TEST: insert tail -- id:1 score:83 name:xiaohua
W/TEST: insert tail -- id:2 score:68 name:xiaoqiang
W/TEST: insert tail -- id:3 score:80 name:xiaoli
W/TEST: insert tail -- id:4 score:88 name:xiaofang
W/TEST: insert front-- id:5 score:86 name:zhangsan
W/TEST: insert front-- id:6 score:78 name:lisi
W/TEST: insert front-- id:7 score:92 name:wangwu
W/TEST: insert front-- id:8 score:55 name:zhaoliu
W/TEST: insert front-- id:9 score:82 name:qianqi
W/TEST: single_list_sample show result
W/TEST: id:9 score:82 name:qianqi
W/TEST: id:8 score:55 name:zhaoliu
W/TEST: id:7 score:92 name:wangwu
W/TEST: id:6 score:78 name:lisi
W/TEST: id:5 score:86 name:zhangsan
W/TEST: id:0 score:70 name:xiaoming
W/TEST: id:1 score:83 name:xiaohua
W/TEST: id:2 score:68 name:xiaoqiang
W/TEST: id:3 score:80 name:xiaoli
W/TEST: id:4 score:88 name:xiaofang
W/TEST: single_list_sample list_len is:10
W/TEST: single_list_sample delete the score less than 60
W/TEST: delete -- id:8 score:55 name:zhaoliu
W/TEST: single_list_sample list_len is:9
W/TEST: single_list_sample show result, and then delete
W/TEST: delete -- id:9 score:82 name:qianqi
W/TEST: delete -- id:7 score:92 name:wangwu
W/TEST: delete -- id:6 score:78 name:lisi
W/TEST: delete -- id:5 score:86 name:zhangsan
W/TEST: delete -- id:0 score:70 name:xiaoming
W/TEST: delete -- id:1 score:83 name:xiaohua
W/TEST: delete -- id:2 score:68 name:xiaoqiang
W/TEST: delete -- id:3 score:80 name:xiaoli
W/TEST: delete -- id:4 score:88 name:xiaofang
W/TEST: single_list_sample list_len is:0

双向链表应用示例

#include <oneos_config.h>#include <dlog.h>#include <os_errno.h>#include <shell.h>#include <string.h>#include <os_memory.h>#include <os_list.h>
#define TEST_TAG        "TEST"
#define STUDENT_NUM     10#define TEST_NAME_MAX   16
char *name[STUDENT_NUM] = {"xiaoming", "xiaohua", "xiaoqiang", "xiaoli", "xiaofang", "zhangsan", "lisi", "wangwu", "zhaoliu", "qianqi"};uint32_t score[STUDENT_NUM] = {70, 83, 68, 80, 88, 86, 78, 92, 55, 82};
struct student_score
{
    os_list_node_t list_node;
    char name[TEST_NAME_MAX];
    uint32_t id;
    uint32_t score;
};typedef struct student_score student_score_t;
void list_sample(void)
{
    uint32_t i = 0;
    os_list_node_t list_head = OS_LIST_INIT(list_head);
    student_score_t *data;
    student_score_t *data_temp;
    os_list_node_t *node;
    os_list_node_t *node_temp;

    LOG_W(TEST_TAG, "list_sample insert data");
    for (i = 0; i < STUDENT_NUM; i++)
    {
        data = os_malloc(sizeof(student_score_t));
        data->id = i;
        memset(data->name, 0, TEST_NAME_MAX);
        strncpy(data->name, name[i], TEST_NAME_MAX);
        data->score = score[i];
        if (i < STUDENT_NUM/2)
        {
            LOG_W(TEST_TAG, "insert tail -- id:%d score:%d name:%s", data->id, data->score, data->name);
            os_list_add_tail(&list_head, &data->list_node);
        }
        else
        {
            LOG_W(TEST_TAG, "insert front-- id:%d score:%d name:%s", data->id, data->score, data->name);
            os_list_add(&list_head, &data->list_node);
        }
    }

    LOG_W(TEST_TAG, "list_sample show result");
    os_list_for_each_entry(data, &list_head, student_score_t, list_node)
    {
        LOG_W(TEST_TAG, "id:%d score:%d name:%s", data->id, data->score, data->name);
    }

    LOG_W(TEST_TAG, "list_sample list_len is:%d", os_list_len(&list_head));
    LOG_W(TEST_TAG, "list_sample delete the score less than 60");
    os_list_for_each_entry_safe(data, data_temp, &list_head, student_score_t, list_node)
    {
        if (data->score < 60)
        {
            LOG_W(TEST_TAG, "delete -- id:%d score:%d name:%s", data->id, data->score, data->name);
            os_list_del(&data->list_node);
            os_free(data);
        }
    }

    LOG_W(TEST_TAG, "list_sample list_len is:%d", os_list_len(&list_head));
    LOG_W(TEST_TAG, "list_sample show result, and then delete");
    os_list_for_each_safe(node, node_temp, &list_head)
    {
        data = os_list_entry(node, student_score_t, list_node);
        LOG_W(TEST_TAG, "delete -- id:%d score:%d name:%s", data->id, data->score, data->name);
        os_list_del(&data->list_node);
        os_free(data);
    }

    LOG_W(TEST_TAG, "list_sample list_len is:%d", os_list_len(&list_head));
}

SH_CMD_EXPORT(test_list, list_sample, "test list");

运行结果

sh>test_list
W/TEST: list_sample insert data
W/TEST: insert tail -- id:0 score:70 name:xiaoming
W/TEST: insert tail -- id:1 score:83 name:xiaohua
W/TEST: insert tail -- id:2 score:68 name:xiaoqiang
W/TEST: insert tail -- id:3 score:80 name:xiaoli
W/TEST: insert tail -- id:4 score:88 name:xiaofang
W/TEST: insert front-- id:5 score:86 name:zhangsan
W/TEST: insert front-- id:6 score:78 name:lisi
W/TEST: insert front-- id:7 score:92 name:wangwu
W/TEST: insert front-- id:8 score:55 name:zhaoliu
W/TEST: insert front-- id:9 score:82 name:qianqi
W/TEST: list_sample show result
W/TEST: id:9 score:82 name:qianqi
W/TEST: id:8 score:55 name:zhaoliu
W/TEST: id:7 score:92 name:wangwu
W/TEST: id:6 score:78 name:lisi
W/TEST: id:5 score:86 name:zhangsan
W/TEST: id:0 score:70 name:xiaoming
W/TEST: id:1 score:83 name:xiaohua
W/TEST: id:2 score:68 name:xiaoqiang
W/TEST: id:3 score:80 name:xiaoli
W/TEST: id:4 score:88 name:xiaofang
W/TEST: list_sample list_len is:10
W/TEST: list_sample delete the score less than 60
W/TEST: delete -- id:8 score:55 name:zhaoliu
W/TEST: list_sample list_len is:9
W/TEST: list_sample show result, and then delete
W/TEST: delete -- id:9 score:82 name:qianqi
W/TEST: delete -- id:7 score:92 name:wangwu
W/TEST: delete -- id:6 score:78 name:lisi
W/TEST: delete -- id:5 score:86 name:zhangsan
W/TEST: delete -- id:0 score:70 name:xiaoming
W/TEST: delete -- id:1 score:83 name:xiaohua
W/TEST: delete -- id:2 score:68 name:xiaoqiang
W/TEST: delete -- id:3 score:80 name:xiaoli
W/TEST: delete -- id:4 score:88 name:xiaofang
W/TEST: list_sample list_len is:0

更详细的API介绍欢迎前往OneOS官网文档中心查看。

文档中心 (10086.cn)

OneOS源码仓库：https://gitee.com/cmcc-oneos/OneOS

微信关注我们

原文链接：https://my.oschina.net/u/5443273/blog/7782411

转载内容版权归作者及来源网站所有！

低调大师中文资讯倾力打造互联网数据资讯、行业资源、电子商务、移动互联网、网络营销平台。持续更新报道IT业界、互联网、市场资讯、驱动更新,是最及时权威的产业资讯及硬件资讯报道平台。

深度学习调参小册

作者：京东零售彭馨谷歌大脑的五位深度学习大佬在 “Chinese New Year” 期间合作推出了《深度学习调参手册》，来为各位深度学习爱好者恭贺新年（我猜的），一时间好评如潮，获星过万，看来大家都是苦调参久已。难道依靠经验的调参变得“可解释”了？显然不是，而是大佬们分享自己的调参经验，内容还是挺多的，下面咱们去粗取精，希望能够获得飞升。一、新项目指南调参并不是开始项目的第一步，在此之前，我们要完成一些必要的基本工作，如问题制定、数据清洗、pipeline 设置、评估指标等确定后，花时间在模型架构和训练配置上才有意义。 1.选择模型架构 • 在进行一个新项目时，首先要尝试重用已经经过验证并有效的模型。如果要新开发，也应该选择一个完善、常用的模型架构先来开展工作，之后再去慢慢构建自己的自定义模型。 • 模型架构具有一系列的超参数，如层数、层宽度、激活函数等，选择架构实际上是选择具有不同超参数的模型，后面的选择初始配置和提高模型性能的科学方法主要是讲选择模型超参数的问题。 • 如果能找到一篇接近解决手头问题的论文，并将其中模型进行复现，是个很好的选择。 2.选择优...

2023-02-14

387

开源项目 OpenHarmony 是每个人的 OpenHarmony 技术构筑万物智联创新使能行业发展 2月25日第一届开放原子开源基金会OpenHarmony技术峰会即将启幕众多行业大咖齐聚深圳开启一场“技术硬核”探索盛宴亮点拉满，我们共同期待

2023-02-14

434

资源下载

更多资源

Mario

马里奥是站在游戏界顶峰的超人气多面角色。马里奥靠吃蘑菇成长，特征是大鼻子、头戴帽子、身穿背带裤，还留着胡子。与他的双胞胎兄弟路易基一起，长年担任任天堂的招牌角色。

腾讯云软件源

为解决软件依赖安装时官方源访问速度慢的问题，腾讯云为一些软件搭建了缓存服务。您可以通过使用腾讯云软件源站来提升依赖包的安装速度。为了方便用户自由搭建服务架构，目前腾讯云软件源站支持公网访问和内网访问。

Sublime Text

Sublime Text具有漂亮的用户界面和强大的功能，例如代码缩略图，Python的插件，代码段等。还可自定义键绑定，菜单和工具栏。Sublime Text 的主要功能包括：拼写检查，书签，完整的 Python API ， Goto 功能，即时项目切换，多选择，多窗口等等。Sublime Text 是一个跨平台的编辑器，同时支持Windows、Linux、Mac OS X等操作系统。

WebStorm

WebStorm 是jetbrains公司旗下一款JavaScript 开发工具。目前已经被广大中国JS开发者誉为“Web前端开发神器”、“最强大的HTML5编辑器”、“最智能的JavaScript IDE”等。与IntelliJ IDEA同源，继承了IntelliJ IDEA强大的JS部分的功能。