酷播亮新聞
非常人販3.jpg
順序表必須佔用一塊事先分配好的、大小固定的儲存空間，不便於儲存空間的管理，為此有人提出可以實現儲存空間的動態管理，即鏈式儲存方式——連結串列。
本篇文章將學習下什麼是連結串列，以及連結串列的實現。
和順序儲存不同，在鏈式儲存中，結點之間的儲存單元地址可能是不連續的。鏈式儲存中每個結點都包含了兩個部分：
儲存元素本身的資料域
儲存結點地址的指標域
我們在前邊講解連式儲存時，提到了一些鏈式儲存的原理，結點中的指標指向的是下一個結點，如果結點中只有指向後繼結點的指標，那麼這些結點組成的連結串列成為單向連結串列。
還是來張圖複習一下撒
單向連結串列.png
一般在連結串列中也會有一個頭結點來儲存連結串列資訊，然後有一個指標指向下一個結點，下一個結點又指向他後邊的一個結點，如果這個指標沒有後繼結點，那麼他就指向NULL。
在連結串列中，這些儲存單元可以是不連續的，因此他可以提高空間利用率。當需要儲存元素時，哪裏有空閒的空間就在哪裏分配，只要將分配的空間地址儲存到上一個結點就可以。這樣通過訪問上一個元素就能找到後一個元素。
擋在連結串列中某一個位置插入元素時，從空閒空間中為該元素分配一個儲存單元，然後將兩個結點之間的指標斷開，上一個結點的指標指向新分配的儲存單元，新分配的結點中指標指向下一個結點。這樣不需要移動原來元素的位置，效率比較高。同樣，當刪除連結串列中的某個元素時，就斷開它與前後兩個結點的指標，然後他的前後兩個結點連線起來，同樣也不需要移動原來元素的位置。與順序表相比，在插入、刪除元素方面，連結串列的效率要比順序表高許多。
但是，隨機查詢元素時，由於連結串列沒有像順序表的索引標註，儲存單元的空間並不連續，如果要查詢某一個元素，必須先得經過他的上一個結點中的地址才能找到他，因此不管遍歷哪一個元素，都必須要把他前面的那個元素都遍歷後才能找到他，效率就不如順序表的高了。
總結一句話，連結串列增刪元素的效率比較高，但是查詢元素的效率就比順序表低了。
連結串列的幾種操作與順序表差不多，也是增刪改查等操作，接下來我們實現一個連結串列。
在建立連結串列時，頭結點中儲存連結串列的資訊，則需要建立一個結構體struct，在其中定義連結串列的資訊與指向下一結點的指標。程式碼如下：
struct Header{ //頭結點 int length;//記錄連結串列的長度 struct Node * next;//指向第一個結點的指標 }
儲存元素結點包含兩部分內容：資料域和指標域，則也需要再定義一個struct,程式碼如下：
struct Node{//結點int data;//資料域struct Node * next;//指向下一個結點的指標}
這樣頭結點與資料結點均已定義，爲了使用方便，將兩個struct用typedef重新定義新的名稱，程式碼如下
typedef struct Node List;//把struct Node重新命名為List typedef struct Header pHead;//把struct Header 重新命名為pHead
建立連結串列要比建立順序表簡單一些。
順序表中需要先為頭結點分配空間，其次為陣列分配一段連續空間，將這段連續空間地址儲存在頭結點中，然後往其中儲存資料。
而建立連結串列時，只需要建立一個頭結點，每儲存一個元素就分配一個儲存單元，然後將儲存單元的地址儲存在上一個結點的指標中即可，不需要再建立時把所有空間都分配好。
ok，我們把兩個結構體定義好之後，就可以建立連結串列了，建立連結串列的程式碼如下：
pHead * createList(){//pHead 是struct Header的別名，是頭結點型別 pHead * ph=(pHead *)malloc(sizeof(pHead));//為頭結點分配記憶體 ph->lenght=0;//為頭結點初始化 ph->next=NULL; return ph;//將頭結點地址返回 }
連結串列大小等資訊也儲存在頭結點中，因此需要從頭結點中獲取即可，也是很簡單的：
int Size(pHead * ph){ if(ph==NULL){ printf(「引數傳入有誤」)； return 0; } return ph->length;}
在連結串列中插入元素要比在順序表中快，只需要將插入位置前後指標斷開，然後讓前元素指標指向新元素，新元素指標指向後元素即可。
插入元素示意圖
插入元素步驟1.png
插入元素步驟2.png
插入元素步驟3.png
插入元素bingo.png
程式碼如下：
int insert(pHead *ph,int pos,int val){ if(ph==NULL||pos<0||pos>ph->length){ printf("引數傳入有誤")； return 0； } //在向連結串列中插入元素時，先要找到這個位置 //先分配一塊記憶體給要插入的資料 List * pval=(List *)malloc(sizeof(List)); pval->data=val; //當前指標指向頭結點後的第一個節點 List * pCur=ph->next; //如果要插入的位置是0 if(pos==0){ ph->next=pval; pval->next=pCur; } else{ //通過for迴圈找到要插入的位置 for(int i=1;inext; } //指標重指 pval->next=pCur->next; pCur->next=pval; } //由於增加了一個元素，所以長度加一 ph->length++; return 1; }
查詢連結串列中的某個元素，其效率沒有順序表高，因為不管查詢的元素在哪個位置，都需要將她前邊的那個元素都完全遍歷才能找到。查詢元素的程式碼如下：
List * find(pHead * ph,int val){ if(ph==NULL){ printf("傳入引數有誤n"); return NULL; } //遍歷連結串列來查詢元素,從第一個元素開始遍歷 LIst * pTmp=ph->next; do{ if(pTmp->data==val){ //一旦發現有符合條件的值，直接返回 return pTmp; } //讓迴圈動起來 pTmp=pTmp->next; } //如果到最後都沒找到符合條件的結點，說明沒有 while(pTmp->next!=NULL); printf("沒有職位%d的元素「,val); return NULL; }
再刪除元素時，首相將被刪除元素與上下結點之間的連線斷開，然後將這兩個上下結點重新連線，這樣元素就從連結串列中成功刪除了。示意圖如下
刪除元素步驟1.png
刪除元素步驟2.png
刪除元素bingo.png
我們看到，從連結串列中刪除元素，也不需要移動其他元素，效率也比較高，我們看下程式碼吧
LIst * Delete(pHead * ph,int val){ if(ph==NULL){ printf("連結串列傳入錯誤！"); return NULL; } //找到val值所在的結點,這裏呼叫了上方查詢的方法 List * pval=find(ph,val); if(pval==NULL){ printf("沒有值為%d的元素！",val); return NULL; } //遍歷連結串列找到要刪除的結點，並找出其前驅和後繼結點 List * pRe=ph-next; List * pCur=NULL; //判斷特殊情況:如果要刪除的元素是第一個結點 if(pRe->data==val){ ph->next=pRe->next; ph->length--; return pRe; } //排查特殊情況之後 else{ for(int i=0;ilength;i++){ pCur=pRe->next; if(pCur->data==val){ //執行上方圖例操作 pRe->next=pCur->next; ph->length--; return pCur; } //延續迴圈遍歷 pRe=pRe->next; } } }
銷燬連結串列時，將連結串列的每個結點元素釋放。頭結點可以釋放，也可以保留，並將其置為初始化狀態。程式碼如下：
void Destory(pHead * ph){ List * pCur=ph->next; List * pTmp; if(ph==NULL){ printf("引數傳遞有誤！」)： } while(pCur->next!=NULL){ pTmp=pCur->next; //將結點釋放 free(pCur); pCur=pTmp; } //將頭結點置為初始化狀態 ph->length=0; ph->next=NULL; }
在本例中，沒有釋放頭結點，只是將頭結點中的資訊置為初始化狀態了。
實現出連結串列的遍歷列印函式，程式碼如下：
void print(pHead * ph){ if(ph==NULL){ printf(「引數傳遞有誤!」); } List * pTmp=ph->next; while(pTmp!=NULL){ printf("%d",pTmp->data); pTmp=pTmp->next; } printf("n"); }
至此，連結串列基本的操作都已實現。
現在我們對於線性表的一些相關知識：原理及實現方式，應該有了一定的認識了，其實只要瞭解了其中的儲存原理，思路清晰，程式碼實現並不難。
掌握了這兩個最基本的線性表，對接下來我們學習其他數據結構會有很大幫助。
謝謝關注~~