基本概念
鏈?zhǔn)酱鎯?chǔ)定義：
為了表示每個(gè)數(shù)據(jù)元素與其直接后繼元素之間的邏輯關(guān)系，每個(gè)元素除了存儲(chǔ)本身的信息外，還需要存儲(chǔ)指示其直接后繼的信息。
表頭結(jié)點(diǎn)：
鏈表中的第一個(gè)結(jié)點(diǎn)，包含指向第一個(gè)數(shù)據(jù)元素的指針以及鏈表自身的一些信息。
數(shù)據(jù)結(jié)點(diǎn)：
鏈表中代表數(shù)據(jù)元素的結(jié)點(diǎn)，包含指向下一個(gè)數(shù)據(jù)元素的指針和數(shù)據(jù)元素的信息。
尾結(jié)點(diǎn)：
鏈表中的最后一個(gè)數(shù)據(jù)結(jié)點(diǎn)，其下一元素指針為空，表示無后繼。
鏈表技術(shù)領(lǐng)域推演
鏈表鏈?zhǔn)酱鎯?chǔ)_api實(shí)現(xiàn)分析：
在C語(yǔ)言中可以用結(jié)構(gòu)體來定義鏈表中的指針域，鏈表中的表頭結(jié)點(diǎn)也可以用結(jié)構(gòu)體實(shí)現(xiàn)；
帶頭結(jié)點(diǎn)、位置從0的單鏈表；
返回鏈表中第3個(gè)位置處，元素的值。
LinkListNode* LinkList_Get(LinkList* list, int pos) { if (list == NULL || pos < 0 || pos >= LinkList_Length(list)) { return NULL; } TLinkList *tList = NULL; tList = (TLinkList *)list; LinkListNode *cur = NULL; cur = &(tList->header); for (int i = 0; i < pos; ++i) { cur = cur->next; } return cur->next; } 返回第三個(gè)位置的。
移動(dòng)pos次以后，當(dāng)前指針指向哪里？
答案：指向位置2，所以需要返回 ret = current->next。
備注：循環(huán)遍歷時(shí)
遍歷第1次，指向位置0；
遍歷第2次，指向位置1；
遍歷第3次，指向位置2；
遍歷第n次，指向位置n-1。
刪除元素：
代碼實(shí)例：
linklist.h
#ifndef _MYLINKLIST_H_ #define _MYLINKLIST_H_ typedef void LinkList; typedef struct _tag_LinkListNode { struct _tag_LinkListNode* next; }LinkListNode; LinkList* LinkList_Create(); void LinkList_Destroy(LinkList* list); void LinkList_Clear(LinkList* list); int LinkList_Length(LinkList* list); int LinkList_Insert(LinkList* list, LinkListNode* node, int pos); LinkListNode* LinkList_Get(LinkList* list, int pos); LinkListNode* LinkList_Delete(LinkList* list, int pos); #endif
linklist.cpp
#include <iostream> #include <cstdio> #include "linklist.h" using namespace std; typedef void LinkList; typedef struct _tag_LinkList { LinkListNode header; int length; }TLinkList; LinkList* LinkList_Create() { TLinkList *tmp = NULL; tmp = (TLinkList *)malloc(sizeof(TLinkList)); if (tmp == NULL) { printf("function LinkList_Create() err./n"); return NULL; } memset(tmp, 0, sizeof(TLinkList)); // 初始化為空鏈表 return tmp; } void LinkList_Destroy(LinkList* list) { if (list == NULL) { return; } free(list); return; } void LinkList_Clear(LinkList* list) { if (list == NULL) { return; } TLinkList *tList = NULL; tList = (TLinkList *)list; tList->header.next = NULL; tList->length = 0; return; } int LinkList_Length(LinkList* list) { if (list == NULL) { return -1; } TLinkList *tList = NULL; tList = (TLinkList *)list; return tList->length; } int LinkList_Insert(LinkList* list, LinkListNode* node, int pos) { if (list == NULL || node == NULL || pos < 0) { return -1; } TLinkList *tList = NULL; tList = (TLinkList *)list; LinkListNode *cur = NULL; cur = &(tList->header); // 對(duì)pos的容錯(cuò)處理，如果pos過大，改為最后面 if (pos > LinkList_Length(list)) { pos = LinkList_Length(list); } // 移動(dòng)到需要插入的位置 for (int i = 0; i < pos; ++i) { cur = cur->next; } // 插入 node->next = cur->next; cur->next = node; ++tList->length; return 0; } LinkListNode* LinkList_Get(LinkList* list, int pos) { if (list == NULL || pos < 0 || pos >= LinkList_Length(list)) { return NULL; } TLinkList *tList = NULL; tList = (TLinkList *)list; LinkListNode *cur = NULL; cur = &(tList->header); for (int i = 0; i < pos; ++i) { cur = cur->next; } return cur->next; } LinkListNode* LinkList_Delete(LinkList* list, int pos) { if (list == NULL || pos < 0 || pos >= LinkList_Length(list)) { return NULL; } TLinkList *tList = NULL; tList = (TLinkList *)list; LinkListNode *cur = NULL; cur = &(tList->header); for (int i = 0; i < pos; ++i) { cur = cur->next; } LinkListNode *ret = NULL; ret = cur->next; // 刪除結(jié)點(diǎn) cur->next = ret->next; --tList->length; return ret; }
main.cpp
#include <iostream> #include <cstdio> #include "linklist.h" using namespace std; typedef struct _Student { LinkListNode node; char name[32]; int age; }Student; int main() { Student s1, s2, s3, s4, s5, s6; s1.age = 21; s2.age = 22; s3.age = 23; s4.age = 24; s5.age = 25; s6.age = 26; // 創(chuàng)建鏈表 Student *list = (Student *)LinkList_Create(); // 插入結(jié)點(diǎn) LinkList_Insert(list, (LinkListNode *)&s1, 0); LinkList_Insert(list, (LinkListNode *)&s2, 0); LinkList_Insert(list, (LinkListNode *)&s3, 0); LinkList_Insert(list, (LinkListNode *)&s4, 0); LinkList_Insert(list, (LinkListNode *)&s5, 0); LinkList_Insert(list, (LinkListNode *)&s6, 3); // 遍歷鏈表 for (int i = 0; i < LinkList_Length(list); ++i) { Student *tmp = (Student *)LinkList_Get(list, i); if (tmp == NULL) { return 0; } printf("age: %d/n", tmp->age); } // 刪除鏈表結(jié)點(diǎn) while (LinkList_Length(list)) { Student *tmp = (Student *)LinkList_Delete(list, 0); if (tmp == NULL) { return 0; } printf("age: %d/n", tmp->age); } LinkList_Destroy(list); return 0; } 優(yōu)點(diǎn)：
- 無需一次性定制鏈表的容量；
- 插入和刪除操作無需移動(dòng)數(shù)據(jù)元素。
缺點(diǎn)：
- 數(shù)據(jù)元素必須保存后繼元素的位置信息；
- 獲取指定數(shù)據(jù)的元素操作需要順序訪問之前的元素。
工程詳情：Github
