一起talk C栗子吧（第十二回：C語(yǔ)言實(shí)例--單鏈表一）

各位看官們，大家好，從今天開始，我們講大型章回體科技小說 ：C栗子，也就是C語(yǔ)言實(shí)例。閑話休提， 言歸正轉(zhuǎn)。讓我們一起talk C栗子吧！

看官們，上一回中咱們沒有說具體的例子，而且是說了例子中的文件組織結(jié)構(gòu)。這一回咱們繼續(xù)說C例子， 說的例子是鏈表，更準(zhǔn)確的說法叫作單鏈表。咱們不但要說C例子，而且會(huì)在例子中使用上一回中說過的 文件組織結(jié)構(gòu)，就當(dāng)作是舉例說明文件組織結(jié)構(gòu)的使用方法。 有點(diǎn)一石二鳥的感覺，哈哈。

鏈表定義：看官們，所謂的鏈表其實(shí)就是一組元素通過一定的方式鏈接在一起。比如我們坐的火車和地鐵， 就是把一節(jié)節(jié)的車廂鏈接在一起才形成了一個(gè)火車或者地鐵。在軟件開發(fā)中常用的鏈表有單鏈表，雙向鏈 表和循環(huán)鏈表。今天，我們主要說的是單鏈表，其它類型的鏈表在后面的章回中依次介紹。

鏈表實(shí)現(xiàn)：?jiǎn)捂湵碛袃煞N實(shí)現(xiàn)方法，一種是線性存儲(chǔ)，一種是鏈?zhǔn)酱鎯?chǔ)。這么說，大家可能可能覺得有點(diǎn) 抽象，不容易理解。沒關(guān)系，咱們用舉個(gè)生活中的例子說明。線性存儲(chǔ)可以看作元素一個(gè)接一個(gè)的排列在 一起，我們?nèi)粘Ｉ钪械呐抨?duì)就可以看作是線性存儲(chǔ)，隊(duì)列中的每個(gè)人看作是鏈表中的元素，排隊(duì)時(shí)每個(gè) 人都是一個(gè)跟著一個(gè)，生怕中間有個(gè)空間被其它人插隊(duì)，這種一個(gè)跟著一個(gè)的方式可以看作是線性存儲(chǔ)。 在寫程序的時(shí)候，使用數(shù)組來表示單鏈表的線性存儲(chǔ)。數(shù)組中的元素大小相同，而且各個(gè)元素依次排列在 一起，通過數(shù)組下標(biāo)可以訪問數(shù)組中的元素。鏈?zhǔn)酱鎯?chǔ)可以看作元素通過一條鏈連接在一起，我們?nèi)粘Ｉ?活中馬路上的車隊(duì)可以看作是鏈?zhǔn)酱鎯?chǔ)。每當(dāng)上下班高峰的時(shí)候，馬路上的車輛都是一個(gè)接一個(gè)地在馬路 上緩慢行走，遠(yuǎn)遠(yuǎn)望去就是一條汽車鏈。每輛汽車可以看作鏈表中的元素，而這條汽車鏈就是通過馬路連 接在一起的。當(dāng)然了，這些汽車?yán)镉幸恍┕卉?，它們?huì)在路邊公交車站臨時(shí)停車，供乘客上下車。但是 不會(huì)影響其它汽車在馬路上行走。我們把公交車停在公交車站的當(dāng)作從汽車鏈中刪除一個(gè)元素。當(dāng)公交車 離開公交車站回到馬路上時(shí)，可以看作是向汽車鏈中插入一個(gè)元素?？垂賯兡芨杏X到公交車在公交車站的 ?？浚瑢?duì)汽車鏈的影響非常小。這也體現(xiàn)了單鏈表的好處，刪除或者插入元素很方便。哈哈，把日常生活 中的東西和鏈表這個(gè)抽象的概念結(jié)合起來，是不是感覺理解容易了呢？

看官們，關(guān)于的單鏈表的例子，詳細(xì)的代碼如下，大家可以參考。在例子中能看到：通過數(shù)組來實(shí)現(xiàn)單鏈 表的順序儲(chǔ)存方式，同時(shí)提供了單鏈表常用的功能：遍歷鏈表，插入和刪除元素，查找元素。

     1  /* **************************
     2   * Head file of Single List
     3   * *************************/
     4  #ifndef SINGLE_LIST_H
     5  #define SINGLE_LIST_H
     6  
     7  #include<stdio.h>
     8  
     9  #define SIZE 10
    10  
    11  typedef int LIST; //把int當(dāng)作List類型，實(shí)際中可以使用其它的類型或者自己定義一個(gè)List類型，不過不能是使用struct復(fù)合類型
    12  
    13  int ListSize = 0;  //定義List的實(shí)際長(zhǎng)度，它不能比SIZE大，因?yàn)閷?shí)際只有SIZE個(gè)空間
    14  
    15  //聲明函數(shù)原型，這里有插入，刪除，查找鏈表元素的函數(shù)，以及遍歷鏈表的函數(shù)
    16  int ListInsert(LIST *list,LIST a);
    17  int ListDelete(LIST *list,LIST a);
    18  int ListTravel(LIST *list);
    19  int ListFindElement(LIST *list,LIST a);
    20  
    21  #endif /*SINGLE_LIST_H*/

     1  /* **************************
     2   * Source file of Single List
     3   * *************************/
     4  #include"Ex010_SingleList.h"
     5  
     6  //函數(shù)的實(shí)現(xiàn)，和主函數(shù)放到了一個(gè)源文件中，實(shí)際中最好不要放在一起
     7  int ListTravel(LIST *list)
     8  {
     9      int index =0;
    10  
    11      if(NULL == list)
    12          return 1;
    13  
    14      for(index=0; index<ListSize && index < SIZE; ++index)
    15          printf("%d ",list[index]);
    16  
    17      printf("\n");
    18  
    19      return 0;
    20  }
    21  
    22  //查找到元素后返回?zé)o數(shù)在鏈表中的位置，即數(shù)組的下標(biāo)，否則返回-1
    23  int ListFindElement(LIST *list,LIST a)
    24  {
    25      int index = 0;
    26  
    27      if(NULL == list)
    28          return -1;
    29  
    30      for(index=0; index<ListSize && index < SIZE; ++index)
    31      {
    32          if(list[index] == a )
    33              return index;
    34      }
    35  
    36      return -1;
    37  }
    38  
    39  int ListInsert(LIST *list,LIST a)
    40  {
    41      if(NULL == list)
    42          return 1;
    43  
    44      if( ListSize >= SIZE)
    45      {
    46          printf("The list is full \n");
    47          return 1;
    48      }
    49  
    50      list[ListSize++] = a; //從List尾部插入元素
    51  
    52      return 0;
    53  }
    54  
    55  int ListDelete(LIST *list,LIST a)
    56  {
    57      int index = 0;
    58  
    59      if(NULL == list)
    60          return 1;
    61  
    62      if( ListSize < 0 )
    63      {
    64          printf("The list is empty\n");
    65          return 1;
    66      }
    67  
    68      index = ListFindElement(list,a);
    69  
    70      if(-1 != index )
    71      {
    72          if(index == SIZE-1) //鏈表中最后一個(gè)元素的時(shí)候這樣刪除
    73          {
    74              list[index] = 0;
    75              ListSize -= 1;
    76              return 0;
    77          }
    78          
    79          index += 1;
    80          while(index <= ListSize )
    81          {
    82              list[index-1] = list[index];
    83              index++;
    84          }
    85          list[index-1] = 0;
    86          ListSize -= 1;
    87      }
    88  
    89      return 0;
    90  }
    91  
    92  //程序主要邏輯部分
    93  int main()
    94  {
    95      int i = 0;
    96      LIST List[SIZE] = {0}; //定義了一個(gè)SIZE大小的鏈表，通過數(shù)組實(shí)現(xiàn)順序存儲(chǔ)
    97  
    98      for(i=0; i<SIZE; ++i)
    99          ListInsert(List,i+1);
   100  
   101      ListTravel(List);
   102      ListInsert(List,23); 
            //注意插入的元素類型需要是LIST類型，因?yàn)楫?dāng)前的LIST是int類型，所以插入一個(gè)數(shù)字23
   103      ListDelete(List,10); //刪除元素的類型和插入的一樣，不多說了
   104      ListTravel(List);
   105      ListDelete(List,5);
   106      ListTravel(List);
   107      ListDelete(List,1);
   108      ListTravel(List);
   109  
   110  
   111      return 0;
   112  }

各位看官，關(guān)于單鏈表的例子咱們就說到這里。欲知后面還有什么例子，且聽下回分解。