嘮嗑

時隔兩周再來寫這篇筆記诱告，是因為對于我這種大學本著及格就好的學神來說這一章節(jié)還是有點難度和思考恒削，有些東西知道羡藐，但是具體細節(jié)已經(jīng)沒有概念了，所以需要認真思考和總結(jié)一下落萎，所以在此還是想跟各位學生黨朋友說一句，學習要有目標炭剪，有些東西你覺得沒什么用可能是你還沒接觸到练链，等到真的需要你的這一些知識的時候就悔之晚矣了。

好了奴拦，話不多說媒鼓，展開這次的筆記，第三章-線性表。

第三章 線性表

線性表（list）：零個或多個數(shù)據(jù)元素的有限序列绿鸣。

這里有幾個需要注意的關(guān)鍵點：

• 序列：顧名思義是有順序的數(shù)列疚沐，數(shù)據(jù)元素之間是有順序的。就是說潮模，一列隊伍在排隊亮蛔，第一個前面沒有人，最后一個后面沒有人擎厢，其他中間的人有且只有一個前驅(qū)和后繼究流。
• 有限：線性表強調(diào)是有限的，事實上动遭，在計算機中處理的對象都是有限的芬探，那種無限的數(shù)列，只存在于數(shù)學的概念中厘惦。
• 數(shù)據(jù)元素的類型需要相同：這就相當于占座偷仿，書包和人能一樣嗎？能算一個數(shù)列嗎宵蕉？

數(shù)學語言定義

若將線性表記為（a1,...,a(i-1),a(i),a(i+1),...,a(n)）酝静，則表中a(i-1)領(lǐng)先于a(i)，a(i)領(lǐng)先于a(i+1)国裳，稱a(i-1)是a(i)的直接前驅(qū)元素形入，a(i)是a(i+1)的直接后繼元素。并且各元素有且只有一個直接前驅(qū)和直接后繼缝左。

所以線性表元素的個數(shù)n(n>=0)定義為線性表的長度亿遂，當n=0時，稱為空表渺杉。

在非空表中的每個數(shù)據(jù)元素都有一個確定的位置蛇数，稱i為數(shù)據(jù)元素a(i)在線性表中的位序。

線性表的抽象數(shù)據(jù)類型

現(xiàn)在我們思考一下是越，線性表會有一些什么操作耳舅？

拿一個現(xiàn)實中的例子來說明吧：

我想大家都有學生時代排隊的經(jīng)歷，那么一個班的學生該怎么排隊呢倚评？按身高從矮到高還是按照名字拼音還是按照姓氏筆畫呢浦徊？這個過程就是線性表的創(chuàng)建和初始化。

一開始可能沒有經(jīng)驗按照姓氏筆畫來排隊天梧，然后發(fā)現(xiàn)有高有矮盔性，隊伍很難看，這個時候就需要重新排隊呢岗，這就是線性表重置為空表的操作冕香。

那么隊伍排好了蛹尝，會有什么操作呢？會不會有說隊伍第幾個人出來一下的操作悉尾？會不會有說隊伍報數(shù)看看有多少人的操作突那？會不會有其他班的老師來問xxx是不是你們班的學生這樣的操作？更或者會不會來個插班生构眯，按照身高直接排在隊伍中呢愕难？

以上的集中情況都是比較常見的線性表操作，分別是根據(jù)位序得到數(shù)據(jù)元素鸵赖，查找某個數(shù)據(jù)元素是否存在务漩，獲得線性表長度，插入和刪除數(shù)據(jù)它褪。

所以饵骨，線性表的抽象數(shù)據(jù)類型定義如下：

ADT 線性表 (List)
Data
      線性表的數(shù)據(jù)對象集合為（a1,a2,...,a(n)），每個元素的類型均為DataType茫打。其中居触，除第一個
元素a1外，每一個元素有且只有一個直接前驅(qū)元素老赤，除了最后一個元素a(n)外轮洋，每一個元素有且只有一個直接
后繼元素。數(shù)據(jù)元素之間的關(guān)系是一對一關(guān)系抬旺。
Operation
      InitList(*L);                 初始化操作弊予，建立一個空的線性表L。
      ListEmpty(L);                 判斷線性表是否為空开财。
      ClearList(*L);                將線性表清空汉柒。
      GetElem(L,i,*e);              將線性表中的第i個元素值返回給e。
      LocateElem(L,e);              在線性表L中查找與給定值e相等的元素责鳍，如果查到返回
該元素在表中的位序碾褂；否則返回0表示失敗。
      ListInsert(*L,i,e);           在線性表L中的第i個位置插入新元素e历葛。
      ListDelete(*L,i,*e);          刪除線性表L中第i個位置元素正塌，并用e返回其值。
      ListLength(L);                返回線性表L的長度恤溶。
endADT

以上就是線性表的最基本操作乓诽，對于更復雜的操作，完全可以通過基本操作的組合來實現(xiàn)咒程。

線性表的順序存儲結(jié)構(gòu)

前面說過问裕，計算機的物理存儲分為兩種，一種是順序存儲孵坚，一種是鏈式存儲粮宛。先來說說比較簡單的線性表的順序存儲結(jié)構(gòu)。

線性表的順序存儲結(jié)構(gòu)卖宠，指的是用一段地址連續(xù)的存儲單元一次存儲線性表的數(shù)據(jù)元素巍杈。

順序存儲結(jié)構(gòu)，說白了扛伍，其實就是在內(nèi)存中找了塊地方筷畦，通過占位的方式，把一段連續(xù)的內(nèi)存給占了刺洒，然后把相同數(shù)據(jù)類型的數(shù)據(jù)元素依次放入這塊內(nèi)存中鳖宾。同時，數(shù)據(jù)類型相同逆航，就直接可以使用一維數(shù)組來實現(xiàn)順序存儲結(jié)構(gòu)鼎文，即把第一個數(shù)據(jù)元素存在數(shù)組下標為0的位置中，依次把線性表相鄰的元素存儲在數(shù)組中相鄰的位置因俐。

那么拇惋，我們可以思考一下，這里的關(guān)鍵點：

1. 第一個是首位置抹剩，也就是這一塊內(nèi)存的起始位置撑帖。
2. 第二個是我們需要多大的內(nèi)存，這是需要預估的澳眷，多了浪費胡嘿，少了容易溢出，所以數(shù)組的長度就是這個最大存儲容量钳踊。

接下來衷敌，我們看看線性表的順序存儲的結(jié)構(gòu)代碼

#define MAXSIZE 20                     /*存儲空間初始分配量*/
typedef int ElemType;                  /*ElemType類型根據(jù)實際情況而定，這里假設為int*/
typedef struct
{
    ElemType data[MAXSIZE];            /*數(shù)組存儲數(shù)據(jù)元素箍土，最大值為MAXSIZE*/
    int length逢享；                       /*線性表當前長度*/
}SqList；

這里吴藻，我們發(fā)現(xiàn)描述順序存儲結(jié)構(gòu)需要三個屬性：
- 存儲空間的起始位置：數(shù)組data瞒爬，它的存儲位置就是存儲空間的存儲位置。
- 線性表的最大存儲容量：數(shù)組長度MAXSIZE沟堡。
- 線性表的當前長度：length侧但。

注意：需要區(qū)別一下數(shù)組長度和線性表長度。數(shù)組長度是存放線性表的存儲空間的長度航罗，內(nèi)存分配后這個量一般是不變的（當然排除動態(tài)分配數(shù)組禀横，比如OC中可變數(shù)組，這會帶來性能上的一定損耗）粥血。線性表的長度是線性表中數(shù)據(jù)元素的個數(shù)柏锄，隨著線性表的插入刪除酿箭，這個量是變化的。所以趾娃，在任何時刻缭嫡，線性表的長度應該小于等于數(shù)組的長度，也就是我們需要估算數(shù)組長度多少比較合適抬闷。

線性表順序結(jié)構(gòu)的存取時間復雜度

已經(jīng)知道了順序結(jié)構(gòu)是連續(xù)的妇蛀，那么我們想想如果要計算存取的時間復雜度，只需要了解一下內(nèi)存中的地址的計算方法笤成，就可以很輕松的得出時間復雜度评架。

線性表的起始是1，數(shù)組的起始下標是0炕泳，所以線性表的第i個元素是要存儲在數(shù)組下標為i-1的位置纵诞，即數(shù)據(jù)元素和數(shù)組下標有如下對應關(guān)系：

對應關(guān)系.png

存儲器中的每個存儲單元都有自己的編號，這個編號稱為地址喊崖。當我們開辟內(nèi)存后挣磨，第一個位置已經(jīng)確定，那么后面的位置是不是荤懂，只要首地址+長度*間距數(shù)茁裙，就可以計算出來呢？公式如下：

LOC(a(i)) = LOC(a1)+(i-1)*c                 /*c表示數(shù)據(jù)類型的長度*/

通過這個公式就可以隨時計算出線性表中任意位置的地址节仿，那么我們對每個線性表位置的存入或者取出數(shù)據(jù)晤锥，對于計算機來說都是相等的時間，也就是一個常熟廊宪，所以它的存取時間性能為O(1)矾瘾。

也因此，我們?nèi)绻玫骄€性表中的第i個位置的數(shù)據(jù)元素箭启，其實也是很簡單的壕翩，只要取得數(shù)組的i-1下標的值，用代碼來寫的話傅寡，如下：

#define OK 1
#define ERROR 0
typedef int Status;
/*
   Status是函數(shù)的類型放妈，其值是函數(shù)結(jié)果狀態(tài)代碼
   初始條件：順序線性表已經(jīng)存在，1<=i<=ListLength(L)
   操作結(jié)果：用e返回L中第i個數(shù)據(jù)元素的值
*/
Status GetElem(SqList L, int i,ElemType *e)
{
   if(L.length == 0 || i<1 || i>L.length)
          return ERROR;
   *e = L.data[i-1];
   return OK;
}

線性表順序結(jié)構(gòu)的插入與刪除

我們來想一下荐操，如果一個隊伍排在那芜抒，有人插隊，會有什么情況發(fā)生托启，肯定是后面的人每個人都要往后退一個位置宅倒。順序結(jié)構(gòu)的線性表插入數(shù)據(jù)的實現(xiàn)過程也就是這樣。

插入算法的思路：
1.如果插入位置不合理屯耸，拋出異常拐迁；
2.如果線性表長度大于等于數(shù)組長度蹭劈，則拋出異常或動態(tài)增加容量唠亚；
3.從最后一個元素開始向前遍歷到第i個位置链方，分別將它們都向后移動一個位置；
4.將要插入數(shù)據(jù)填入位置i處灶搜；
5.表長加1；
代碼：
Status ListInsert(SqList *L,int i,ElemType e)
{
   int k;
   if (L->length == MAXSIZE)     /*順序線性表已經(jīng)滿了*/
       return ERROR;
   if (i<1 || i>L->length+1)     /*當i不在范圍內(nèi)時*/
       return ERROR;
   if (i<=L->length)             /*若插入數(shù)據(jù)位置不在表尾*/
   {
      for(k=L->length-1;k>=i-1;k--)    /*將要插入位置后數(shù)據(jù)元素向后移動一位*/
      {
           L->data[k+1] = L->data[k];
      }
   }
   L->data[i-1] = e;           /*新元素插入i*/
   L->length++;                /*表長加1*/
   return OK;
}

同樣的道理工窍，如果一個隊伍中有一個走了割卖，那是不是后面的人都可以上前一位呢，這也就是順序線性表的刪除實現(xiàn)過程患雏。

刪除算法的思路：
1.如果刪除位置不合理鹏溯，拋出異常；
2.取出刪除元素淹仑；
3.從刪除元素位置開始遍歷到最后一個元素位置丙挽，分別將它們都向前移動一個位置；
4.表長減1.
代碼：
Status ListDelete(SqList *L,int i,ElemType *e)
{
     int k;
     if (L->length == 0)            /*線性表為空*/
         return ERROR;
     if (i < 1 || i > L->length)        /*刪除位置不正確*/
         return ERROR;
     *e = L->data[i-1];
     if (i < L->length)
     {
            for (k = i; k < L->length;k++)
            {
                  L->data[k-1] = L->data[k];
            }
     }
     L->length--;
     return OK;
}

在這里的話就是注意線性表的下標和數(shù)組的下標匀借，別搞混了應該是挺簡單的颜阐。

現(xiàn)在，來分析一下插入刪除的時間復雜度吓肋，最好的情況時間復雜度是O(1)凳怨，最壞的情況時間復雜度是O(n)，至于平均的情況為（n-1）/2是鬼，時間復雜度還是O(n)肤舞。

這樣的話，我們就可以總結(jié)一下順序結(jié)構(gòu)存儲線性表的優(yōu)缺點了：

• 優(yōu)點：無須為表示表中元素之間的邏輯關(guān)系而增加額外的存儲空間均蜜；
  可以快速的存取表中任一位置的元素李剖。
• 缺點：插入和刪除操作需要移動大量位置（可以想想如果插入的不是一個元素而是多個連續(xù)的元素）；當線性表長度變化較大時囤耳，難以確定存儲空間的容量篙顺；容易造成存儲空間的“碎片”。

接下來紫皇，我們就來分析一下線性表的鏈式存儲結(jié)構(gòu)慰安，又有什么不同和優(yōu)缺點。

線性表的鏈式存儲結(jié)構(gòu)

既然知道順序結(jié)構(gòu)的插入和刪除這么麻煩聪铺，那有沒有什么方法可以解決呢化焕？首先我們思考一下為什么順序結(jié)構(gòu)會有這種問題，原因在于相鄰兩元素的存儲位置也具有鄰里關(guān)系铃剔，在內(nèi)存中的位置也是挨著的撒桨，中間沒有空隙查刻，這就導致插入的時候，需要移動n-i個元素凤类，刪除也一樣穗泵。

那么解決辦法也就可以思考得出，就是那不然大家都不要挨著了谜疤，全部散開佃延，這樣的話，插入和刪除就不需要移動這么多元素夷磕，那么數(shù)據(jù)元素就不單單存數(shù)據(jù)元素的信息履肃，也需要存它的后繼元素的存儲地址。這種形式也就是單鏈表坐桩。

為了表示每個數(shù)據(jù)元素a(i)與其直接后繼數(shù)據(jù)元素a(i+1)之間的邏輯關(guān)系尺棋，對數(shù)據(jù)元素a(i)來說，除了存儲
其本身的信息之外绵跷，還需存儲一個指示其直接后繼的信息（即直接后繼的存儲位置）膘螟。我們把存儲數(shù)據(jù)元素信
息的域稱為數(shù)據(jù)域，把存儲直接后繼位置的域稱為指針域碾局。指針域中存儲的信息稱作指針或連荆残。這兩部分信息
組成數(shù)據(jù)元素a(i)的存儲映像，稱為結(jié)點（Node）擦俐。
n個結(jié)點（a(i)的存儲映像）鏈結(jié)成一個鏈表脊阴，即為線性表的鏈式存儲結(jié)構(gòu)，因為此鏈表的每個結(jié)點只包含一
個指針域蚯瞧，所以叫做單鏈表嘿期。

我們把鏈表中第一個結(jié)點的存儲位置叫做頭指針。整個鏈表的存取就必須是從頭指針開始進行了埋合，之后的每一個結(jié)點备徐，就是上一個結(jié)點的后繼指針指向的位置，如此甚颂，最后一個結(jié)點的后繼指針就為空（NULL或^符號表示）蜜猾。

有時，我們習慣在單鏈表的第一個結(jié)點前附設一個結(jié)點振诬，稱為頭結(jié)點蹭睡。頭結(jié)點的數(shù)據(jù)域可以不存儲任何信息，或者存儲如線性表的長度等附加信息赶么，頭結(jié)點的指針域指向第一個結(jié)點的指針肩豁。

頭指針：頭指針是指鏈表指向第一個結(jié)點的指針，若鏈表有頭結(jié)點，則是指向頭結(jié)點的指針清钥；頭指針具有標識
作用琼锋，所以常用頭指針冠以鏈表的名字；無論鏈表是否為空祟昭，頭指針均不為空缕坎。頭指針是鏈表的必須要素。
頭結(jié)點：頭結(jié)點是為了操作的統(tǒng)一和方便而設立的篡悟，放在第一元素的結(jié)點之前谜叹，其數(shù)據(jù)域一般無意義（也可存
放鏈表的長度）；有了頭結(jié)點恰力，對在第一元素結(jié)點前插入結(jié)點和刪除第一結(jié)點叉谜，其操作和其他結(jié)點的操作就統(tǒng)一
了；頭結(jié)點不一定是鏈表必須要素踩萎。

單鏈表

帶頭結(jié)點的單鏈表

空聯(lián)表

/*線性表的單鏈表存儲結(jié)構(gòu)*/
typedef struct Node
{
      ElemType data;
      struct Node *next;
} Node;
typedef struct Node *LinkList;   /*定義LinkList*/

從定義可以看出來，結(jié)點由存放數(shù)據(jù)元素的數(shù)據(jù)域和存放后繼結(jié)點地址的指針域組成很钓。

總結(jié)

這篇就寫到這吧香府，寫的是真累，回到老家码倦，發(fā)現(xiàn)書桌沒了企孩，一直是坐在床沿邊寫，太累了袁稽，這一章節(jié)的后一半單鏈表的讀取勿璃，插入刪除，以及靜態(tài)鏈表推汽，雙向鏈表补疑，循環(huán)鏈表，就下一篇再寫吧歹撒，初步預估后天會寫好發(fā)出來莲组，希望各位大佬多多諒解。

最后祝祖國母親68周歲快樂暖夭，祝大家國慶锹杈，中秋雙節(jié)快樂！有時間的話可以多陪陪爸媽迈着，反正我是打算在家宅8天竭望，哈哈！裕菠！

Better Late Than Never!
努力是為了當機會來臨時不會錯失機會咬清。
共勉！