gogo专业大尺度亚洲高清人体,美女张开双腿让男生桶,亚洲av无码一区二区三区鸳鸯影院,久久久久国产精品人妻

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

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

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

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

    1、 單鏈表的組織與存儲

    單向鏈表的每個節(jié)點中除信息域以外還有一個指針域，用來指向其后續(xù)節(jié)點，其后一個節(jié)點的指針域為空（NULL）。

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

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

    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)不能自己定義自己，因為這樣將導(dǎo)致一個無窮的遞歸定義，但結(jié)構(gòu)的成員可以是結(jié)構(gòu)自身的指針類型，通過指針引用自身這種類型的結(jié)構(gòu)。

    2、 單鏈表常見操作

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

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

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

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

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

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

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

    （3）鏈表的插入與刪除

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

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

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

    由圖中可以看出，在鏈表中增加一個節(jié)點會依次完成如下操作。
    ●創(chuàng)建新節(jié)點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é)點的單鏈表的頭指針 */
      /* 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é)點 */
      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é)點刪除過程

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

    （4）其他操作

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

    下面將兩個單鏈表根據(jù)標識符ID順序合并成一個單鏈表。在合并的過程中，實際上新建了一個鏈表，然后將兩個鏈表的元素依次進行比較，并且將ID較小的節(jié)點插入到新的鏈表中。如果其中一個鏈表的元素已經(jīng)全部插入，則另一個鏈表的剩余操作只需順序?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，指向鏈表的第一個元素 */
      pa = list_a->next;
      pb = list_b->next;
      *list_c = pc = list_a;
      /* 判斷兩個鏈表是否到達末尾 */
      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;
        }
      }
      /* 將還未到達末尾的鏈表連入list_c中，若兩個鏈表都到達末尾，pc->next為NULL*/
      pc->next = pa?pa:pb;
    }

   熱點鏈接：

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

更多新聞>>