国产成人精品三级麻豆,色综合天天综合高清网,亚洲精品夜夜夜,国产成人综合在线女婷五月99播放,色婷婷色综合激情国产日韩

    在嵌入式linux內(nèi)核中，鏈表是一種常見的重要數(shù)據(jù)結(jié)構(gòu)，它可以動(dòng)態(tài)地進(jìn)行存儲(chǔ)分配，根據(jù)需要開辟內(nèi)存單元，還可以方便地實(shí)現(xiàn)數(shù)據(jù)的增加和刪除。鏈表中的每個(gè)元素都由兩部分組成：數(shù)據(jù)域和指針域。

    其中，數(shù)據(jù)域用于存儲(chǔ)數(shù)據(jù)元素的信息，指針域用于存儲(chǔ)該元素的直接后繼元素的位置。其整體結(jié)構(gòu)就是用指針相鏈接起來的線性表，如圖1.1所示。

圖1.1 鏈表結(jié)構(gòu)

    由圖中，大家可以清楚地看到，每個(gè)鏈表都有一個(gè)頭指針Head，其用于指示鏈表中第一個(gè)節(jié)點(diǎn)的存儲(chǔ)位置。之后，鏈表由第一個(gè)節(jié)點(diǎn)指向第二個(gè)節(jié)點(diǎn)，依此類推。鏈表的后一個(gè)數(shù)據(jù)元素由于沒有直接后繼節(jié)點(diǎn)，因此其節(jié)點(diǎn)的指針為空（NULL）。本文主要介紹的是單項(xiàng)鏈表！

    1、 單鏈表的組織與存儲(chǔ)

    單向鏈表的每個(gè)節(jié)點(diǎn)中除信息域以外還有一個(gè)指針域，用來指向其后續(xù)節(jié)點(diǎn)，其后一個(gè)節(jié)點(diǎn)的指針域?yàn)榭眨∟ULL）。

    單向鏈表由頭指針惟一確定，因此單向鏈表可以用頭指針的名字來命名，頭指針指向單向鏈表的第一個(gè)節(jié)點(diǎn)。

    在用C語言實(shí)現(xiàn)時(shí)，首先說明一個(gè)結(jié)構(gòu)類型，在這個(gè)結(jié)構(gòu)類型中包含一個(gè)（或多個(gè)）信息成員以及一個(gè)指針成員如下所示：

    typedef struct _link_node
    {
      element_type data; /* element_type為有效數(shù)據(jù)類型*/
      struct _link_node *next;
    } link_node;
    typedef link_node *link_list;

    鏈表結(jié)構(gòu)中包含指針型的結(jié)構(gòu)成員，類型為指向相同結(jié)構(gòu)類型的指針。根據(jù)C語言的語法要求，結(jié)構(gòu)的成員不能是結(jié)構(gòu)自身類型，即結(jié)構(gòu)不能自己定義自己，因?yàn)檫@樣將導(dǎo)致一個(gè)無窮的遞歸定義，但結(jié)構(gòu)的成員可以是結(jié)構(gòu)自身的指針類型，通過指針引用自身這種類型的結(jié)構(gòu)。

    2、 單鏈表常見操作

    （1）節(jié)點(diǎn)初始化

    由于鏈表是一種動(dòng)態(tài)分配數(shù)據(jù)的數(shù)據(jù)結(jié)構(gòu)，因此單鏈表中各個(gè)節(jié)點(diǎn)的初始化通常使用malloc()函數(shù)，把節(jié)點(diǎn)中的next指針賦為NULL，同時(shí)再把數(shù)據(jù)域的部分初始化為需要的數(shù)值，通常使用memset()函數(shù)。

    int init_link(link_list *list)
    {
      /*用malloc分配函數(shù)分配節(jié)點(diǎn)*/
      *list = (link_list)malloc(sizeof(link_node));
      /*若分配失敗，返回*/
      if (!list)
      {
        return -1;
      }
      /*初始化鏈表節(jié)點(diǎn)的數(shù)據(jù)域*/
      memset(&((*list)->data), 0, sizeof(element_type));
      /*初始化鏈表節(jié)點(diǎn)的指針域*/
      (*list)->next = NULL;
      return 0;
    }

    （2）數(shù)據(jù)查詢

    在操作鏈表時(shí)，通常需要檢查在鏈表中是否存在某種數(shù)據(jù)，這時(shí)，可以通過順序遍歷鏈表來取得所需要的元素。

    int get_element(link_list list, int i, element_type *elem)
    {
      /* list為帶頭節(jié)點(diǎn)的單鏈表的頭指針 */
      /*當(dāng)?shù)趇個(gè)元素存在時(shí)，其值賦給elem并返回*/
      link_list p = NULL;
      int j = 0;

      /*初始化，指向鏈表的第一個(gè)節(jié)點(diǎn)，j為計(jì)數(shù)器*/
      p = list->next;
      /* 為防止i過大，通過判斷p是否為空來確定是否到達(dá)鏈表的尾部 */
      while ((j++ < i) && (p = p->next));
      /* 若第i個(gè)元素不存在，返回 */
      if (!p || (j <= i))
      {
        return -1;
      }
      /*取得第i個(gè)元素*/
      *elem = p->data;
      return 0;
    }

    （3）鏈表的插入與刪除

    鏈表的插入與刪除是鏈表中常見的操作，也是能體現(xiàn)鏈表靈活性的操作。

    在單向鏈表中插入一個(gè)節(jié)點(diǎn)要引起插入位置前面節(jié)點(diǎn)的指針的變化，如圖1.2所示。

圖1.2 鏈表的節(jié)點(diǎn)插入過程

    由圖中可以看出，在鏈表中增加一個(gè)節(jié)點(diǎn)會(huì)依次完成如下操作。
    ●創(chuàng)建新節(jié)點(diǎn)C
    ●使C指向B：C→next = A→next。
    ●使A指向C：A→next = C。

    int link_insert(link_list list, int i, element_type elem)
    {
      /* list為帶頭節(jié)點(diǎn)的單鏈表的頭指針 */
      /* i為要插入的元素位置，elem為要插入的元素*/
      link_list p = list, new_node;
      int j = 0;

      /* 找到第i位 */
      while ((j++ < i) && (p = p->next));
      if (!p || (j <= i))
      {
        return 0;
      }
      /* 初始化鏈表節(jié)點(diǎn) */
      new_node = (link_list)malloc(sizeof(link_node));
      new_node->data = elem;
      /* 將s插入鏈表，并修改原先的指針 */
      new_node->next = p->next;
      p->next = new_node;
      return 1;
    }

    刪除的過程也類似，如圖1.3所示。

圖1.3 鏈表的節(jié)點(diǎn)刪除過程

    同樣，鏈表中元素的指針會(huì)依次有以下變化。
    ●使A指向C：A→next = B->next。

    （4）其他操作

    將幾個(gè)單鏈表合并也是鏈表操作中的一個(gè)常見的操作之一。

    下面將兩個(gè)單鏈表根據(jù)標(biāo)識(shí)符ID順序合并成一個(gè)單鏈表。在合并的過程中，實(shí)際上新建了一個(gè)鏈表，然后將兩個(gè)鏈表的元素依次進(jìn)行比較，并且將ID較小的節(jié)點(diǎn)插入到新的鏈表中。如果其中一個(gè)鏈表的元素已經(jīng)全部插入，則另一個(gè)鏈表的剩余操作只需順序?qū)⑹Ｓ嘣�素插入即可�?/p>

    該過程如圖1.4所示：

圖1.4 鏈表的合并過程

    void merge_list(link_list list_a, link_list list_b, link_list *list_c)
    {
      /* 合并單鏈表list_a和list_b到list_c中 */
      link_list pa, pb, pc;

      /* 初始化pa、pb，指向鏈表的第一個(gè)元素 */
      pa = list_a->next;
      pb = list_b->next;
      *list_c = pc = list_a;
      /* 判斷兩個(gè)鏈表是否到達(dá)末尾 */
      while (pa && pb)
      {
        /*若鏈表list_a的元素小于鏈表list_b的元素，
        則把鏈表list_a的元素插入到list_c中*/
        if (less_equal_list(&pa->data, &pb->data))
        {
          pc->next = pa;
          pc = pa;
          pa = pa->next;
        }
        /* 若鏈表list_a的元素大于鏈表list_b的元素，
        則把鏈表list_b的元素插入到list_c中*/
        else
        {
          pc->next = pb;
          pc = pb;
          pb = pb->next;
        }
      }
      /* 將還未到達(dá)末尾的鏈表連入list_c中，若兩個(gè)鏈表都到達(dá)末尾，pc->next為NULL*/
      pc->next = pa?pa:pb;
    }

   熱點(diǎn)鏈接：

   1、Linux內(nèi)核模塊程序結(jié)構(gòu)
   2、嵌入式Linux內(nèi)核如何編譯
   3、典型嵌入式Linux系統(tǒng)設(shè)置

更多新聞>>