大主宰,我欲封天耳根小说,将夜猫腻小说

引言

鏈表和數組是兩種不同的數據存儲方式。鏈表是一種物理存儲單元上非連續、非順序的存儲結構，數據元素的邏輯順序是通過鏈表中的指針鏈接次序實現的。數組是把具有相同類型的若干元素按有序的形式組織起來的一種形式，數組中的各元素的存儲是有先后順序的，它們在內存中按照這個先后順序連續存放在一起。本文將對這兩種存儲方式的優缺點做一個大致的介紹，并詳細介紹鏈表在操作系統中定義和使用的方式。

一、鏈表和數組

鏈表是鏈式的存儲結構，數組是順序的存儲結構，其在內存存儲上的不同形式決定了其各自的特點。

鏈表通過指針來鏈接元素，鏈表中的結點順序關系由指針來體現；數組將元素按次序依次存儲，元素順序關系由元素在數組中的位置（下標）確定。

鏈表節點的存儲單元在程序執行時動態向系統申請，鏈表的結點個數可按需要增減；數組元素的存儲單元在數組定義時分配，其元素個數是固定的，對于不是固定長度的列表，用可能最大長度的數組來描述。

鏈表插入刪除元素不需要移動元素，且較為容易實現長度擴充，但是尋找某個元素較為困難；數組尋找某個元素較為簡單，但插入與刪除比較復雜。

總體來說，鏈表使用指針將一系列數據節點鏈接成數據鏈，相對于數組，它具有良好的動態性，建立鏈表時不需要提前知道數據量，可以隨時分配空間，可以高效地在鏈表中的任意位置插入或者刪除數據。操作系統中存在著大量的基礎數據結構鏈表和鏈表項，理解鏈表對理解操作系統至關重要。

二、單向鏈表和雙向鏈表

通常鏈表數據結構包含兩部分，一部分是數據域，用于存儲數據；另外一部分是指針域，用于建立與其它節點的關系。鏈表項中可以包含一個指向下一個鏈表項的指針而不包含指向上一個鏈表的指針，也可以兩者都包含，前者稱為單向鏈表，后者為雙向鏈表。

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 #include #include #include #include #include #include 
#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 #include #include #include #include #include #include 
#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

審核編輯：劉清

聲明：本文內容及配圖由入駐作者撰寫或者入駐合作網站授權轉載。文章觀點僅代表作者本人，不代表電子發燒友網立場。文章及其配圖僅供工程師學習之用，如有內容侵權或者其他違規問題，請聯系本站處理。舉報投訴

物聯網

物聯網

+關注

關注
2912

文章
44889

瀏覽量
375769
操作系統

操作系統

+關注

關注
37

文章
6877

瀏覽量
123580

原文標題：數據存儲，鏈表還是數組？

文章出處：【微信號：OSC開源社區，微信公眾號：OSC開源社區】歡迎添加關注！文章轉載請注明出處。

各種嵌入式操作系統詳細介紹

的所有成員及廣大第三方廠商的廣泛支持。目前 Motif 已作為軟件產品在 OS/2、Unix、Sys V、OSF/1、VMS、Macintosh OS、Ultrix 等48中操作系統平臺上實現，并可

發表于 06-17 00:49

【安富萊】【RTX操作系統教程】第2章嵌入式實時操作系統介紹

教程中有對基于時間觸合作式調度和混合式調度的講解。2.3總結本章節是一些入門性質的介紹，從下一章節開始講解RTX操作系統。此外，在2.1小節中推薦的兩個實時

發表于 01-15 15:35

【安富萊】【RTX操作系統教程】第4章 RTX操作系統介紹

本帖最后由硬漢Eric2013 于 2016-1-18 14:33 編輯第4章RTX操作系統介紹本章節介紹一下RTX操作系統，讓大家對RTX有一個整體的了解，Keil RT

發表于 01-18 14:31

關于操作系統的結構體指針使用方式

地址（也就是說在這個結構體中存在著一個鏈表結構體變量沒那么就可以通過這個鏈表結構體變量去得知結構體變量的地址）。假設typedefstructalist //這個是一個鏈表結構體，

發表于 10-06 23:44

Linux內核的鏈表操作

的list_head沒有數據域。在Linux內核鏈表中，不是在鏈表結構中包含數據，而是在數據結構

發表于 08-29 11:13

嵌入式操作系統FreeRTOS 的原理與實現

分配策略的實現原理，并指出FreeRTOS在應用中的優缺點。在嵌入式領域中，嵌入式實時操作系統正得到越來越廣泛的應用。采用嵌入式實時操作系統

發表于 06-23 08:00

介紹ThreadX操作系統

第3章 ThreadX操作系統介紹本章節介紹 ThreadX 操作系統，讓大家對 ThreadX 有一個整體的了解。目錄第3章 ThreadX操作系

發表于 08-24 07:13

ThreadX操作系統介紹

第3章 ThreadX操作系統介紹本章節介紹 ThreadX 操作系統，讓大家對 ThreadX 有一個整體的了解。目錄第3章 ThreadX操作系

發表于 08-24 07:37

數據結構鏈表的基本操作

嵌入式學習基礎-數據結構鏈表的基本操作鏈表節點采用結構體的方式進行定義，下面是最基礎的定義只有一

發表于 12-22 08:05

LwIP|無操作系統

LwIP無操作系統下的實驗本文詳細講述了LwIP在無操作系統支持環境下的API函數介紹及編程應用。首先，

發表于 04-07 16:39 ?110次下載

智能手機操作系統的詳細介紹

智能手機操作系統的詳細介紹 SymbianWindows CEPalm OSLinux1998年愛立信、諾基亞、摩托羅拉和Psion共同投資成立的Sy

發表于 12-28 08:18 ?3200次閱讀

操作系統實驗

操作系統實驗。詳細的實驗介紹。正宗的實驗源代碼。

發表于 03-18 16:59 ?3次下載

機器人操作系統ROS詳細介紹

機器人操作系統ROS詳細介紹 ROS（機器人 操作系統，RobotOperatingSystem），是專為機器人軟件開發所設計出來的一套電腦操作系

發表于 11-18 18:09 ?2424次閱讀

嵌入式實時操作系統的應用詳細教程說明

本文檔的主要內容詳細介紹的是嵌入式實時操作系統的應用詳細教程說明包括了：1 嵌入式系統與嵌入式操作系統

發表于 12-05 08:00 ?2次下載

鏈表的基本操作

回看了一下以前寫的鏈表操作，確實有點復雜不利于初學，這篇文章就換個寫法，簡單明了的介紹鏈表的操作。

發表于 12-13 10:11 ?1386次閱讀

在线观看www成人影院-在线观看www日本免费网站-在线观看www视频-在线观看操-欧美18在线-欧美1级

搜索歷史

詳細介紹鏈表在操作系統中定義和使用的方式

評論

各種嵌入式操作系統詳細介紹

【安富萊】【RTX操作系統教程】第2章嵌入式實時操作系統介紹

【安富萊】【RTX操作系統教程】第4章 RTX操作系統介紹

關于操作系統的結構體指針使用方式

Linux內核的鏈表操作

嵌入式操作系統FreeRTOS 的原理與實現

介紹ThreadX操作系統

ThreadX操作系統介紹

數據結構鏈表的基本操作

LwIP|無操作系統

智能手機操作系統的詳細介紹

操作系統實驗

機器人操作系統ROS詳細介紹

嵌入式實時操作系統的應用詳細教程說明

鏈表的基本操作