c語言單鏈表尾添加的深入講解

更新時(shí)間：2020年12月22日 10:11:00 作者：24mamba

這篇文章主要給大家介紹了關(guān)于c語言單項(xiàng)鏈表尾添加的相關(guān)資料，文中通過示例代碼介紹的非常詳細(xì)，對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧

前言

猶豫了幾天，看了很多大牛寫的關(guān)于c語言鏈表，感觸很多，終于下定決心，把自己對于鏈表的理解隨之附上，可用與否，自行裁奪。由于作者水平有限也是第一次寫，不足之處，竭誠希望得到各位大神的批評指正。制作不易，不喜勿噴，謝謝?。?！

在正文開始之前，我先對數(shù)組和鏈表進(jìn)行簡單的對比分析。

鏈表也是一種很常見的數(shù)據(jù)結(jié)構(gòu)，不同于數(shù)組的是它是動態(tài)進(jìn)行存儲分配的一種結(jié)構(gòu)。數(shù)組存放數(shù)據(jù)時(shí)，必須要事先知道元素的個(gè)數(shù)。舉個(gè)例子，比如一個(gè)班有40個(gè)人，另一個(gè)班有100個(gè)人，如果要用同一個(gè)數(shù)組先后來存放這兩個(gè)班的學(xué)生數(shù)據(jù)，那么必須得定義長度為100的數(shù)組。如果事先不確定一個(gè)班的人數(shù)，只能把數(shù)組定義的足夠大，以能存放任何班級的學(xué)生數(shù)據(jù)。這樣就很浪費(fèi)內(nèi)存，而且數(shù)組對于內(nèi)存的要求必須是是連續(xù)的，數(shù)據(jù)小的話還好說，數(shù)據(jù)大的話內(nèi)存分配就會失敗，數(shù)組定義當(dāng)然也就失敗。還有數(shù)組對于插入以及刪除元素的效率也很低這就不一一介紹了。然而鏈表就相對于比較完美，它很好的解決了數(shù)組存在的那些問題。它儲存數(shù)據(jù)時(shí)就不需要分配連續(xù)的空間，對于元素的插入以及刪除效率就很高?？梢哉f鏈表對于內(nèi)存就是隨用隨拿，不像數(shù)組要事先申請。當(dāng)然，有優(yōu)點(diǎn)就必然有缺點(diǎn)，就比如說鏈表里每一個(gè)元素里面都多包含一個(gè)地址，或者說多包含一個(gè)存放地址的指針變量，所以內(nèi)存開銷就很大。還有因?yàn)殒湵淼膬?nèi)存空間不是連續(xù)的，所以想找到其中的某一個(gè)數(shù)據(jù)就沒有數(shù)組那么方便，必須先得到該元素的上一個(gè)元素，根據(jù)上一個(gè)元素提供的下一元素地址去找到該元素。所以不提供“頭指針”（下文中“頭指針”為“PHead”），那么整個(gè)鏈表將無法訪問。鏈表就相當(dāng)于一條鐵鏈一環(huán)扣一環(huán)（這個(gè)稍后會詳細(xì)的說）。

鏈表

上面我提到過鏈表是動態(tài)進(jìn)行存儲分配的一種結(jié)構(gòu)。鏈表中的每一個(gè)元素稱為“結(jié)點(diǎn)”，每個(gè)結(jié)點(diǎn)都包括兩部分：一部分為用戶需要的實(shí)際數(shù)據(jù)，另一部分為下一結(jié)點(diǎn)的地址。鏈表有一個(gè)“頭指針(PHead)”變量，存放著一個(gè)地址，該地址指向第一個(gè)結(jié)點(diǎn)，第一個(gè)結(jié)點(diǎn)里面存放著第二個(gè)結(jié)點(diǎn)的地址，第二個(gè)結(jié)點(diǎn)又存放著第三個(gè)結(jié)點(diǎn)地址。就這樣頭指針指向第一個(gè)結(jié)點(diǎn)，第一個(gè)結(jié)點(diǎn)又指向第二個(gè)......直到最后一個(gè)結(jié)點(diǎn)。最后一個(gè)結(jié)點(diǎn)不再指向其他結(jié)點(diǎn)，地址部分存放一個(gè)“NULL”。見下圖：（表中有一個(gè)尾指針（PEnd）其作用后面會解釋）

c語言單項(xiàng)鏈表尾添加整體代碼如下：（詳解附后）

#include <stdio.h>
#include <stdlib.h>
#include <malloc.h>


//函數(shù)聲明
//尾添加
void wei_tian_jia(struct NODE** PHEAD, struct NODE** PEND, int shu_ju);
//尾添加(沒有尾指針)
void wei_tian_jia_(struct NODE** PHEAD, int shu_ju);
//釋放鏈表
void shi_fang_lian_biao(struct NODE* PHEAD);
//釋放鏈表(并是頭指針(PHead)尾指針(PEnd)指向空)
void shi_fang_lian_biao_free(struct NODE** PHEAD, struct NODE** PEnd);
//輸出鏈表
void shu_chu(struct NODE* PHEAD);


//定義一個(gè)鏈表結(jié)構(gòu)體
struct NODE
{
  int shu_ju;      //用戶需要的實(shí)際數(shù)據(jù)
  struct NODE* PNext;  //下一結(jié)點(diǎn)的地址

};


int main(void)
{
  //創(chuàng)建頭尾指針
  struct NODE* PHead = NULL;
  struct NODE* PEnd = NULL;


  //尾添加
  wei_tian_jia(&PHead, &PEnd, 17);
  wei_tian_jia(&PHead, &PEnd, 21);
  wei_tian_jia(&PHead, &PEnd, 34);
  wei_tian_jia(&PHead, &PEnd, 8);
  wei_tian_jia(&PHead, &PEnd, 24);

  //尾添加(沒有尾指針)
  //wei_tian_jia_(&PHead, 23);
  //wei_tian_jia_(&PHead, 17);
  //wei_tian_jia_(&PHead, 11);

  //輸出鏈表
  shu_chu(PHead);

  //釋放鏈表
  //shi_fang_lian_biao(PHead);

  //釋放鏈表(并是頭指針(PHead)尾指針(PEnd)指向空)
  shi_fang_lian_biao_free(&PHead, &PEnd);


  system("pause");
  return 0;
}

//尾添加
void wei_tian_jia(struct NODE** PHEAD, struct NODE** PEND, int SHU_JU)
{
  //創(chuàng)建結(jié)點(diǎn)
  struct NODE* PTEMP = (struct NODE*)malloc(sizeof(struct NODE));
  if (PTEMP != NULL)
  {
    //節(jié)點(diǎn)賦值
    PTEMP->shu_ju = SHU_JU;
    PTEMP->PNext = NULL;

    //把結(jié)點(diǎn)連起來
    if (NULL == *PHEAD) // 因?yàn)镻HEAD如果是NULL的話 PEND也就是NULL 所以條件里面不必要寫
    {
      *PHEAD = PTEMP;
      *PEND = PTEMP;
    }
    else
    {
      (*PEND)->PNext = PTEMP;
      *PEND = PTEMP;

    }
  }  
}

//尾添加(沒有尾指針)
void wei_tian_jia_(struct NODE** PHEAD1, int SHU_JU)
{
  //創(chuàng)建結(jié)點(diǎn)
  struct NODE* PTEMP = (struct NODE*)malloc(sizeof(struct NODE));

  if (PTEMP != NULL)
  {
      //結(jié)點(diǎn)成員賦值
    PTEMP->shu_ju = SHU_JU;
    PTEMP->PNext = NULL;

    //把結(jié)點(diǎn)連一起
    if (NULL == *PHEAD1)
    {
      *PHEAD1 = PTEMP;
    }
    else 
    {
      struct NODE* PTEMP2 = *PHEAD1;
      while (PTEMP2->PNext != NULL)
      {
        PTEMP2 = PTEMP2->PNext;
      }
      PTEMP2->PNext = PTEMP;
    }

  }

}

//輸出鏈表
void shu_chu(struct NODE* PHEAD)
{
  while (PHEAD != NULL)
  {
    printf("%d\n", PHEAD->shu_ju);
    PHEAD = PHEAD->PNext;

  }

}

//釋放鏈表
void shi_fang_lian_biao(struct NODE* PHEAD)
{
  struct NODE* P = PHEAD;
  while (PHEAD != NULL)
  {
    struct NODE* PTEMP = P;
    P = P->PNext;
    free(PTEMP);
  }
  free(PHEAD);

}
//釋放鏈表(并是頭指針(PHead)尾指針(PEnd)指向空)
void shi_fang_lian_biao_free(struct NODE** PHEAD, struct NODE** PEnd)
{
  
    while (*PHEAD != NULL)
    {
      struct NODE* PTEMP = *PHEAD;
       *PHEAD = (*PHEAD)->PNext;
      free(PTEMP);
    }
    *PHEAD = NULL;
    *PHEAD = NULL;


}

部分代碼詳解：(再次申明：由于作者水平有限，所以有的變量名用的拼音。見笑，莫怪?。?！為了簡單明了，方便起見，我定義了一個(gè)實(shí)際數(shù)據(jù)。)

“頭指針”(PHead)以及“尾指針”(PEnd)：

頭指針很好理解指向首結(jié)點(diǎn)用于遍歷整個(gè)數(shù)組，而尾指針呢？我們先看下面兩段代碼一段是有尾指針的一段是沒有尾指針的：

//尾添加
void wei_tian_jia(struct NODE** PHEAD, struct NODE** PEND, int SHU_JU)
{
  //創(chuàng)建一個(gè)結(jié)點(diǎn)
  struct NODE* PTEMP = (struct NODE*)malloc(sizeof(struct NODE));
  if (PTEMP != NULL)
  {
    //節(jié)點(diǎn)成員賦值（一定要每個(gè)成員都要賦值）
    PTEMP->shu_ju = SHU_JU;
    PTEMP->PNext = NULL;

    //把結(jié)點(diǎn)連起來
    if (NULL == *PHEAD) // 因?yàn)镻HEAD如果是NULL的話 PEND也就是NULL 所以條件里面不必要寫
    {
      *PHEAD = PTEMP;
      *PEND = PTEMP;
    }
    else
    {
      //把尾指針向后移
      (*PEND)->PNext = PTEMP;
      *PEND = PTEMP;

    }

  }
  
}

那么下面這段代碼是沒有尾指針的。它的思想就是頭指針一直指向第一個(gè)結(jié)點(diǎn)，然后通過遍歷來找到最后一個(gè)結(jié)點(diǎn)，從而使最后一個(gè)結(jié)點(diǎn)里面的指針指向所要插入的元素。

//尾添加(沒有尾指針)
void wei_tian_jia_(struct NODE** PHEAD1, int SHU_JU)
{
  //創(chuàng)建結(jié)點(diǎn)
  struct NODE* PTEMP = (struct NODE*)malloc(sizeof(struct NODE));

  if (PTEMP != NULL)
  {
    //結(jié)點(diǎn)成員賦值
    PTEMP->shu_ju = SHU_JU;
    PTEMP->PNext = NULL;

    //把結(jié)點(diǎn)連一起  
    if (NULL == *PHEAD1)
    {
      *PHEAD1 = PTEMP;

    }
    else 
    {
      struct NODE* PTEMP2 = *PHEAD1;
      while (PTEMP2->PNext != NULL)
      {
        PTEMP2 = PTEMP2->PNext;
      }
      PTEMP2->PNext = PTEMP;
    }

  }

}

我把上面代碼里面的一段摘出來說明一下。

這段代碼里面可以看到我又定義了一個(gè)PTEMP2指針變量，為什么呢？前面我提到過沒有尾指針的時(shí)候添加結(jié)點(diǎn)的思想就是要遍歷數(shù)組，從而找到最后一個(gè)結(jié)點(diǎn)然后讓它指向我們要插入的結(jié)點(diǎn)，如果沒有這個(gè)PHEAD2，我們遍歷完鏈表以后我們的頭指針PHEAD1就已經(jīng)指向了最后一個(gè)結(jié)點(diǎn)了，單項(xiàng)鏈表如果頭指針移動了，數(shù)據(jù)就會找不到了。所以我定義了一個(gè)中間變量裝著頭指針然后去遍歷鏈表，讓頭指針永遠(yuǎn)指向鏈表的頭。

else 
    {
      struct NODE* PTEMP2 = *PHEAD1;
      while (PTEMP2->PNext != NULL)
      {
        PTEMP2 = PTEMP2->PNext;
      }
      PTEMP2->PNext = PTEMP;
    }

可以看到有尾指針的代碼和沒有尾指針的代碼里面，有尾指針的鏈表里面我每次添加完數(shù)據(jù)都讓尾指針指向最后一個(gè)結(jié)點(diǎn)，然后通過尾指針來添加數(shù)據(jù)。而沒有尾指針的鏈表里面每次添加數(shù)據(jù)都要通過循環(huán)來遍歷鏈表找到最后一個(gè)結(jié)點(diǎn)然后指向所添加的結(jié)點(diǎn)。如果一個(gè)鏈表里面有幾萬個(gè)結(jié)點(diǎn)，每次都通過循環(huán)遍歷鏈表來添加數(shù)據(jù)，那么速度就相對于有尾指針的鏈表慢很多。總而言之，還是看個(gè)人愛好吧。不管黑貓還是白貓能抓到耗子都是好貓。