1.鏈表認知

?一場病，斷了好久。這幾天算是基本沒什么問題了。是時候繼續了。

鏈表我想可以認為是，點到線的過程。

一個個點就是一個個鏈表的節點，以特定的順序組合或鏈接后，行成了一條線，即鏈表。所以添加，刪除一個點是相對較容易的（因為可以動態的追加，刪除節點），但是查找某個點相對較麻煩（數組中只需要a[i]即可取得數據，鏈表則需要遍歷）。所以，對于未知大小長度的數據來說，具有相當的優勢。但已知數據量來說，數組可能更好一些。

單鏈表

單鏈表(通常簡稱為鏈表)由各個元素之間通過一個指針彼此鏈接起來而組成。每個元素包含兩部分:數據成員和一個稱為nexr的指針。通過采用這種二成員結構,將每個元素的next指針設置為指向其后面的元素。最后一個元素的next指針置為NUL,簡單地表示鏈表的尾端。鏈表開始處的元素是“頭”,鏈表末尾的元素稱為“尾。

簡單來說，火車是最好理解的鏈表了。車頭就是“頭”，每節車廂里面裝的人救贖數據，車廂后面連接下一個車廂的鐵栓就是next指針。

單鏈表代碼實現

#include<stdio.h> #include<stdlib.h> #include<string.h>typedef struct ListElmt //定義節點 {void *data;struct ListElmt *next; };typedef struct List //定義鏈表 {int size;int(*match)(const void *key1, const void *key2); //構造函數void(*destroy)(void *data); //析構函數ListElmt *head;ListElmt *tail; };void list_init(List *list, void(*destroy)(void *data)); //新建鏈表 void list_destroy(List *list); //移除鏈表中的元素 void list_size(List *list, void (*destroy)(void *data)); //鏈表長度 int list_ins_next(List *list, ListElmt *element, const void *data); //尾插 int list_rem_next(List *list, ListElmt *element, void **data); //移除#define list_is_head(list,element) ((element) == (list)->head ? 1:0) #define list_is_tail(element) ((element)->next == NULL ? 1:0)//新建鏈表 void list_init(List *list, void(*destroy)(void *data)) {list->size = 0;list->destroy = destroy;list->head = NULL;list->tail = NULL;return; }//銷毀鏈表 void list_destroy(List *list) {void *data;while (list->size > 0){if (list_rem_next(list, NULL, (void **)&data) == 0 && list->destroy != NULL){list->destroy(data); //循環刪除元素}}memset(list, 0, sizeof(List));return; }int list_ins_next(List *list, ListElmt *element, const void *data) {ListElmt *new_element;if ((new_element = (ListElmt *)malloc(sizeof(ListElmt))) == NULL)return -1;new_element->data = (void *)data;if (element == NULL){if (list->size == 0){list->tail = new_element;}new_element->next = list->head;list->head = new_element;}else{if (element->next == NULL){list->tail = new_element;}new_element->next = element->next;element->next = new_element;}list->size++;return 0; }//刪除element后的一個元素 int list_rem_next(List *list, ListElmt *element, void **data) {ListElmt *old_element;if (list->size == 0)return -1;if (element == NULL){*data = list->head->data;old_element = list->head->next;list->head = list->head->next;if (list->size == 1)list->tail = NULL;}else{if (element->next == NULL)return-1;*data = element->next->data;old_element = element->next;element->next = element->next->next;if (element->next == NULL){list->tail = element;}}free(old_element);list->size--;return 0; }

?雙鏈表

雙向鏈表,如同其名字所暗示的那樣,鏈表元秦之間由兩個指針鏈接。雙向鏈表中的每元素都由3部分組成:除了數據成員和nexr指針外,每個元素還包含一個指向共前驅元素的指針,稱為prev指針。雙向鏈表的組成是這樣的:將一些元素鏈接在一起使得每個元素的 next指針都指向其后繼的元素,而每個元素的rev指針都指向其前驅元素。為了標識鏈表的頭和尾,將第一個元素的prev指針和最后一個元素的nexr指針設置為NULL。要反向遍歷整個雙向鏈表,使用prev指針以從尾到頭的順序連續訪問各個元素。因此,為每個元素増加了一個指針的代價,換來的是雙向鏈表比單錐表提供了更為靈活的訪問方式。當我們知道某個元素存儲在鏈表中的某處時,我們可以明智地途擇按照何種方式訪問到它,這會非常有幫助。例如,雙向鏈表的一種靈活性在于它提供了一種比單鏈表更直觀的方式以移除一個元素

具體代碼實現

#include<stdlib.h> #include<string.h> typedef struct DListElmt //節點屬性 {void *data;struct DListElmt *prev;struct DListElmt *next; }DListElmt;typedef struct DList {int size;int(*match)(const void *key1, const void *key2);void(*destroy)(void *data);DListElmt *head;DListElmt *tail; }DList;#define dlist_is_head(element) ((element)->perv == NULL ? 1:0) //是否是頭 #define dlist_is_tail(element) ((element)->next == NULL ? 1:0) //是否是尾//創建鏈表 void dlist_init(DList *list, void(*destroy)(void *data)) {list->size = 0;list->destroy = destroy;list->head = NULL;list->tail = NULL;return; }//刪除節點 int dlist_remove(DList *list, DListElmt *element, void **data) {if (element == NULL || list->size == 0)return 1;*data = element->data;if (element == list->head) //如果是頭節點，則判空。{if (list->head == NULL) //為空則是最后一個節點，清空連接list->tail = NULL;elseelement->next->prev = NULL; //非空，則摘除節點，準備刪除}else //如果不是頭結點，摘除。刪除{element->prev->next = element->next; //刪除節點的前一個指向刪除節點的后一個if (element->next == NULL) //判斷是否為最后一個節點list->tail = element->prev;elseelement->next->prev = element->prev; //刪除節點的后一個指向刪除節點的前一個}free(element);list->size--;return 0; }//刪除鏈表 void dlist_destroy(DList *list) {void *data;while (list->size > 0){if (dlist_remove(list, list->tail, (void **)&data) == 0&& list->destroy != NULL)//如果節點刪除成功，則刪除節點對應存儲的數據list->destroy(data);} }//尾插法 int dlist_ins_next(DList *list, DListElmt *element, const void *data) {DListElmt *new_element;if (element == NULL && list->size != 0)return -1;if ((new_element = (DListElmt*)malloc(sizeof(DListElmt))) == NULL)return -1;new_element->data = (void *)data;if (list->size == 0) //如果為鏈表頭{list->head = new_element;list->head->prev = NULL;list->head->next = NULL;list->tail = new_element;}else{new_element->next = element->next;new_element->prev = element;if (element->next == NULL)list->tail = new_element;elseelement->next->prev = new_element;element->next = new_element;}list->size++;return 0; }//頭插法 int dlist_ins_prev(DList *list, DListElmt *element, const void *data) {DListElmt *new_element;if (element == NULL && list->size != 0)return -1;if ((new_element = (DListElmt*)malloc(sizeof(DListElmt))) == NULL)return -1;new_element->data = (void *)data;if (list->size == 0){list->head = new_element;list->head->prev = NULL;list->head->next = NULL;list->tail = new_element;}else{new_element->next = element;new_element->prev = element->prev;if (element->prev == NULL)list->head = new_element;elseelement->prev->next = new_element;element->prev = new_element;}list->size++;return 0; }

?

?

總結

以上是生活随笔為你收集整理的算法精解（一）：C语言描述（链表）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。