線性結(jié)構(gòu)：有且只有一個根節(jié)點，且每個節(jié)點最多有一個直接前驅(qū)和一個直接后繼的非空數(shù)據(jù)結(jié)構(gòu)

非線性結(jié)構(gòu)：不滿足線性結(jié)構(gòu)的數(shù)據(jù)結(jié)構(gòu)

鏈表（單向鏈表的建立、刪除、插入、打?。?/p>

1、鏈表一般分為：　

　　單向鏈表

    雙向鏈表

    環(huán)形鏈表

2、基本概念

鏈表實際上是線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)，與數(shù)組不同的是，它是用一組任意的存儲單元來存儲線性表中的數(shù)據(jù)，存儲單元不一定是連續(xù)的，

且鏈表的長度不是固定的，鏈表數(shù)據(jù)的這一特點使其可以非常的方便地實現(xiàn)節(jié)點的插入和刪除操作

鏈表的每個元素稱為一個節(jié)點，每個節(jié)點都可以存儲在內(nèi)存中的不同的位置，為了表示每個元素與后繼元素的邏輯關(guān)系，以便構(gòu)成 “一個節(jié)點鏈著一個節(jié)點” 的鏈?zhǔn)酱鎯Y(jié)構(gòu)，

除了存儲元素本身的信息外，還要存儲其直接后繼信息，因此，每個節(jié)點都包含兩個部分，第一部分稱為鏈表的數(shù)據(jù)區(qū)域，用于存儲元素本身的數(shù)據(jù)信息，這里用 data 表示，

它不局限于一個成員數(shù)據(jù)，也可是多個成員數(shù)據(jù)，第二部分是一個結(jié)構(gòu)體指針，稱為鏈表的指針域，用于存儲其直接后繼的節(jié)點信息，這里用 next 表示，

next 的值實際上就是下一個節(jié)點的地址，當(dāng)前節(jié)點為末節(jié)點時，next 的值設(shè)為空指針

1 struct link2 {3     int data;4     struct link *next;5 };

像上面這種只包含一個指針域、由 n 個節(jié)點鏈接形成的鏈表，就稱為線型鏈表或者單向鏈表，鏈表只能順序訪問，不能隨機訪問，鏈表這種存儲方式最大缺點就是容易出現(xiàn)斷鏈，

一旦鏈表中某個節(jié)點的指針域數(shù)據(jù)丟失，那么意味著將無法找到下一個節(jié)點，該節(jié)點后面的數(shù)據(jù)將全部丟失

3、鏈表與數(shù)組比較

數(shù)組（包括結(jié)構(gòu)體數(shù)組）的實質(zhì)是一種線性表的順序表示方式，它的優(yōu)點是使用直觀，便于快速、隨機地存取線性表中的任一元素，但缺點是對其進行 插入和刪除操作時需要移動大量的數(shù)組元素，同時由于數(shù)組屬于靜態(tài)內(nèi)存分配，定義數(shù)組時必須指定數(shù)組的長度，程序一旦運行，其長度就不能再改變，實際使用個數(shù)不能超過數(shù)組元素最大長度的限制，否則就會發(fā)生下標(biāo)越界的錯誤，低于最大長度時又會造成系統(tǒng)資源的浪費，因此空間效率差

4、單向鏈表的建立

1 #include

上面的代碼使用了三個函數(shù) AppendNode、DisplyNode、DeletMemory

struct link *AppendNode (struct link *head);（函數(shù)作用：新建一個節(jié)點并添加到鏈表末尾，返回添加節(jié)點后的鏈表的頭指針）

void DisplyNode (struct link *head);（函數(shù)功能：顯示鏈表中所有節(jié)點的節(jié)點號和該節(jié)點中的數(shù)據(jù)項的內(nèi)容）

void DeletMemory (struct link *head);（函數(shù)功能：釋放 head 所指向的鏈表中所有節(jié)點占用的內(nèi)存）

（還使用了 malloc 函數(shù)和 free 函數(shù)）

5、malloc 函數(shù)

作用：用于分配若干字節(jié)的內(nèi)存空間，返回一個指向該內(nèi)存首地址的指針，若系統(tǒng)不能提供足夠的內(nèi)存單元，函數(shù)將返回空指針 NULL，函數(shù)原型為 void *malloc (unsigned int size)

其中 size 是表示向系統(tǒng)申請空間的大小，函數(shù)調(diào)用成功將返回一個指向 void 的指針（void * 指針是 ANSIC 新標(biāo)準(zhǔn)中增加的一種指針類型，

具有一般性，通常稱為通用指針或者無類型的指針）常用來說明其基類型未知的指針，即聲明了一個指針變量，但未指定它可以指向哪一種基類型的數(shù)據(jù)，

因此，若要將函數(shù)調(diào)用的返回值賦予某個指針，則應(yīng)先根據(jù)該指針的基類型，用強轉(zhuǎn)的方法將返回的指針值強轉(zhuǎn)為所需的類型，然后再進行賦值

 1 int *pi; 2 pi = (int *)malloc(4); 

其中 malloc（4）表示申請一個大小為 4 字節(jié)的內(nèi)存，將 malloc（4）返回值的 void * 類型強轉(zhuǎn)為 int * 類型后再賦值給 int 型指針變量 pi，即用 int 型指針變量 pi 指向這段存儲空間的首地址

若不能確定某種類型所占內(nèi)存的字節(jié)數(shù)，則需使用 sizeof（）計算本系統(tǒng)中該類型所占的內(nèi)存字節(jié)數(shù)，然后再用 malloc（）向系統(tǒng)申請相應(yīng)字節(jié)數(shù)的存儲空間

pi = (int *)malloc(sizeof(int));

6、free 函數(shù)

釋放向系統(tǒng)動態(tài)申請的由指針 p 指向的內(nèi)存存儲空間，其原型為：Void free (void *p); 該函數(shù)無返回值，唯一的形參 p 給出的地址只能由 malloc（）和 calloc（）申請內(nèi)存時返回的地址，

該函數(shù)執(zhí)行后，將以前分配的指針 p 指向的內(nèi)存返還給系統(tǒng)，以便系統(tǒng)重新分配

 為什么要用 free 釋放內(nèi)存

（在程序運行期間，用動態(tài)內(nèi)存分配函數(shù)來申請的內(nèi)存都是從堆上分配的，動態(tài)內(nèi)存的生存期有程序員自己來決定，使用非常靈活，但也易出現(xiàn)內(nèi)存泄漏的問題，

為了防止內(nèi)存泄漏的發(fā)生，程序員必須及時調(diào)用 free（）釋放已不再使用的內(nèi)存）

7、單向鏈表的刪除操作

刪除操作就是將一個待刪除的節(jié)點從鏈表中斷開，不再與鏈表的其他節(jié)點有任何聯(lián)系

需考慮四種情況：

　　1. 若原鏈表為空表，則無需刪除節(jié)點，直接退出程序

　　2. 若找到的待刪除節(jié)點 p 是頭節(jié)點，則將 head 指向當(dāng)前節(jié)點的下一個節(jié)點（p->next），即可刪除當(dāng)前節(jié)點

 　 3. 若找到的待刪除節(jié)點不是頭節(jié)點，則將前一節(jié)點的指針域指向當(dāng)前節(jié)點的下一節(jié)點（pr->next = p->next），即可刪除當(dāng)前節(jié)點，當(dāng)待刪除節(jié)點是末節(jié)點時，

由于 p->next 值為 NULL，因此執(zhí)行 pr->next = p->next 后，pr->next 的值也變成 NULL，從而使 pr 所指向的節(jié)點由倒數(shù)第 2 個節(jié)點變成了末節(jié)點

　　4. 若已搜索到表尾（p->next == NULL），仍未找到待刪除節(jié)點，則顯示 “未找到”，注意：節(jié)點被刪除后，只是將它從鏈表中斷開而已，它仍占用著內(nèi)存，必須釋放其所占的內(nèi)存，否則將出現(xiàn)內(nèi)存泄漏

（頭結(jié)點不是頭指針，注意兩者區(qū)別）

8、頭節(jié)點和頭指針

頭指針存儲的是頭節(jié)點內(nèi)存的首地址，頭結(jié)點的數(shù)據(jù)域可以存儲如鏈表長度等附加信息，也可以不存儲任何信息

　　　　參考鏈接 --- 頭指針和頭節(jié)點：https://www.cnblogs.com/didi520/p/4165486.html

　　　　　　　　　　　　　　　 　　https://blog.csdn.net/qq_37037492/article/details/78453333

　　　　　　　　　　　　　　　   　https://www.cnblogs.com/marsggbo/p/6622962.html

　　　　　　　　　　　　　　　 　　https://blog.csdn.net/hunjiancuo5340/article/details/80671298

（圖片出處：https://blog.csdn.net/hunjiancuo5340/article/details/80671298）

值得注意的是：

　　1. 無論鏈表是否為空，頭指針均不為空。頭指針是鏈表的必要元素

　　2. 鏈表可以沒有頭節(jié)點，但不能沒有頭指針，頭指針是鏈表的必要元素

 　　3. 記得使用 free 釋放內(nèi)存

單向鏈表的刪除操作實現(xiàn)

1 struct link *DeleteNode (struct link *head, int nodeData) 2 { 3     struct link *p = head, *pr = head; 4  5     if (head == NULL) 6     { 7         printf("Linked table is empty!\n"); 8         return 0; 9     }10     while (nodeData != p->data && p->next != NULL)11     {12         pr = p;            /* pr保存當(dāng)前節(jié)點 */13         p = p->next;    /* p指向當(dāng)前節(jié)點的下一節(jié)點 */14     }15     if (nodeData == p->data)16     {17         if (p == head)    /* 如果待刪除為頭節(jié)點 （注意頭指針和頭結(jié)點的區(qū)別）*/18         {19             head = p->next;20         }21         else            /* 如果待刪除不是頭節(jié)點 */22         {23             pr->next = p->next;24         }25         free(p);        /* 釋放已刪除節(jié)點的內(nèi)存 */26     }27     else            /* 未發(fā)現(xiàn)節(jié)點值為nodeData的節(jié)點 */28     {29         printf("This Node has not been found");30     }31 32     return head;33 }

9、單向鏈表的插入

向鏈表中插入一個新的節(jié)點時，首先由新建一個節(jié)點，將其指針域賦值為空指針（p->next = NULL），然后在鏈表中尋找適當(dāng)?shù)奈恢脠?zhí)行節(jié)點的插入操作，

此時需要考慮以下四種情況：

　　　　1. 若原鏈表為空，則將新節(jié)點 p 作為頭節(jié)點，讓 head 指向新節(jié)點 p（head = p）

   　　 2. 若原鏈表為非空，則按節(jié)點值的大?。僭O(shè)節(jié)點值已按升序排序）確定插入新節(jié)點的位置，若在頭節(jié)點前插入新節(jié)點，則將新節(jié)點的指針域指向原鏈表的頭節(jié)點（p->next = head），且讓 head 指向新節(jié)點（head =p）

　　　　3. 若在鏈表中間插入新節(jié)點，則將新節(jié)點的指針域之下一節(jié)點（p->next = pr -> next），且讓前一節(jié)點的指針域指向新節(jié)點（pr->next = p）

　　　　4. 若在表尾插入新節(jié)點，則末節(jié)點指針域指向新節(jié)點（p->next = p）

單向鏈表的插入操作實現(xiàn)

1 /* 函數(shù)功能：向單向鏈表中插入數(shù)據(jù) 按升序排列*/ 2 struct link *InsertNode(struct link *head, int nodeData) 3 { 4     struct link *p = head, *pr = head, *temp = NULL; 5  6     p = (struct link *)malloc(sizeof(struct link)); 7     if (p == NULL) 8     { 9         printf("No enough meomory!\n");10         exit(0);11     }12     p->next = NULL;        /* 待插入節(jié)點指針域賦值為空指針 */13     p->data = nodeData;14 15     if (head == NULL)    /* 若原鏈表為空 */16     {17         head = p;        /* 插入節(jié)點作頭結(jié)點 */18     }19     else        /* 原鏈表不為空 */20     {21         while (pr->data < nodeData && pr->next != NULL)22         {23             temp = pr;        /* 保存當(dāng)前節(jié)點的指針 */24             pr = pr->next;    /* pr指向當(dāng)前節(jié)點的下一節(jié)點 */25         }26         if (pr->data >= nodeData)27         {28             if (pr == head)        /* 在頭節(jié)點前插入新節(jié)點 */29             {30                 p->next = head;    /* 新節(jié)點指針域指向原鏈表頭結(jié)點 */31                 head = p;        /* 頭指針指向新節(jié)點 */32             }33             else34             {35                 pr = temp;36                 p->next = pr->next;        /* 新節(jié)點指針域指向下一節(jié)點 */37                 pr->next = p;            /* 讓前一節(jié)點指針域指向新節(jié)點 */38             }39         }40         else        /* 若在表尾插入新節(jié)點 */41         {42             pr->next = p;    /* 末節(jié)點指針域指向新節(jié)點*/43         }44     }45 46     return head;47 }

 （編譯器：Microsoft Visual C++ 2010 Express）

（tips：上面的代碼中將頭節(jié)點中的數(shù)據(jù)當(dāng)作第一個元素，大多數(shù)情況頭節(jié)點是不存儲數(shù)據(jù)的（當(dāng)時沒注意???），讀者可自行嘗試修改代碼讓頭結(jié)點不存儲數(shù)據(jù)，頭節(jié)點的后一個節(jié)點作為第一個元素）

下面附上頭結(jié)點不存儲數(shù)據(jù)的代碼（區(qū)別不是很大，就是多用了一個子函數(shù)來初始化頭結(jié)點）