這篇文章主要介紹“數(shù)據(jù)結(jié)構(gòu)的鏈表有那幾種類型”，在日常操作中，相信很多人在數(shù)據(jù)結(jié)構(gòu)的鏈表有那幾種類型問題上存在疑惑，小編查閱了各式資料，整理出簡單好用的操作方法，希望對大家解答”數(shù)據(jù)結(jié)構(gòu)的鏈表有那幾種類型”的疑惑有所幫助！接下來，請跟著小編一起來學(xué)習(xí)吧！
善左網(wǎng)站制作公司哪家好，找成都創(chuàng)新互聯(lián)！從網(wǎng)頁設(shè)計(jì)、網(wǎng)站建設(shè)、微信開發(fā)、APP開發(fā)、自適應(yīng)網(wǎng)站建設(shè)等網(wǎng)站項(xiàng)目制作，到程序開發(fā)，運(yùn)營維護(hù)。成都創(chuàng)新互聯(lián)2013年至今到現(xiàn)在10年的時(shí)間，我們擁有了豐富的建站經(jīng)驗(yàn)和運(yùn)維經(jīng)驗(yàn)，來保證我們的工作的順利進(jìn)行。專注于網(wǎng)站建設(shè)就選成都創(chuàng)新互聯(lián)。
單鏈表的尾結(jié)點(diǎn)的指針域是 NULL，所以單鏈表到此終止。如果我們使用單鏈表的尾結(jié)點(diǎn)的指針域存儲(chǔ)頭結(jié)點(diǎn)的地址，即尾結(jié)點(diǎn)的直接后繼結(jié)點(diǎn)為頭結(jié)點(diǎn)，如此一來，單鏈表就構(gòu)成了一個(gè)環(huán)(循環(huán))，稱之為單項(xiàng)循環(huán)鏈表。
單向循環(huán)鏈表是由單鏈表進(jìn)化而來的，算是單鏈表的“兒子”，所以單鏈表的那一套結(jié)構(gòu)對于單向循環(huán)鏈表來說完全適用，從上圖你也可以看出，結(jié)構(gòu)并無較大改變，二者所不同只在尾結(jié)點(diǎn)，所以我們只需要在尾結(jié)點(diǎn)和與尾結(jié)點(diǎn)相關(guān)的操作上下功夫就行了。
因此，單向循環(huán)鏈表的結(jié)構(gòu)體和單鏈表的結(jié)構(gòu)體相同。
重慶分公司
重慶分公司
/*單向循環(huán)鏈表的結(jié)點(diǎn)的結(jié)構(gòu)體*/ typedef struct _Node { int data; //數(shù)據(jù)域：存儲(chǔ)數(shù)據(jù) struct _Node *next; //指針域：存儲(chǔ)直接后繼結(jié)點(diǎn)的地址 } Node;為了統(tǒng)一對空鏈表和非空鏈表的操作，我們使用帶頭結(jié)點(diǎn)的鏈表來實(shí)現(xiàn)它。
一個(gè)空鏈表如圖所示，只有一個(gè)頭指針和頭結(jié)點(diǎn)：
空鏈表
頭結(jié)點(diǎn)的指針域指向其本身構(gòu)成一個(gè)循環(huán)，我們可以借此來判斷鏈表是否為空。
if (head->next == head) { printf("空鏈表。\n"); }想要初始化一個(gè)空鏈表很簡單，創(chuàng)造頭結(jié)點(diǎn)，使頭結(jié)點(diǎn)的 next 指針指向其自身即可：
Node *create_node(int elem) { Node *new = (Node *) malloc(sizeof(Node)); new->data = elem; new->next = NULL; return new; } /** * 初始化鏈表 * p_head: 指向頭指針的指針 */ void init(Node **p_head) { //創(chuàng)建頭結(jié)點(diǎn) Node *head_node = create_node(0); //頭指針指向頭結(jié)點(diǎn) *p_head = head_node; //頭結(jié)點(diǎn)的next指針指向其本身，構(gòu)成環(huán) head_node->next = head_node; }這里只演示頭插法和尾插法
因?yàn)閹ь^結(jié)點(diǎn)，所以不需要考慮是否為空鏈表。下圖是向空鏈表中頭插兩個(gè)元素的過程：
單向循環(huán)鏈表頭插法過程
/** * 頭插法，新結(jié)點(diǎn)為頭結(jié)點(diǎn)的直接后繼 * p_head: 指向頭指針的指針 * elem: 新結(jié)點(diǎn)的數(shù)據(jù) */ void insert_at_head(Node **p_head, int elem) { Node *new = create_node(elem); Node *head_node = *p_head; //頭結(jié)點(diǎn) //新結(jié)點(diǎn)插入頭結(jié)點(diǎn)之后 new->next = head_node->next; head_node->next = new; }因?yàn)闉榱吮M量簡單，所以我們并沒有設(shè)置指向尾結(jié)點(diǎn)的尾指針，所以在尾插之前，需要先借助某個(gè)指針，遍歷至尾結(jié)點(diǎn)，然后再插入。
/** * 尾插法：新插入的結(jié)點(diǎn)始終在鏈表尾 * p_head: 指向頭指針的指針 * elem: 新結(jié)點(diǎn)的數(shù)據(jù) */ void insert_at_tail(Node **p_head, int elem) { Node *new = create_node(elem); Node *head_node = *p_head; //頭結(jié)點(diǎn) Node *tail = head_node; //tail指針指向頭結(jié)點(diǎn) while (tail->next != head_node) { //tail遍歷至鏈表尾 tail = tail->next; } //尾插 new->next = tail->next; tail->next = new; }刪除的本質(zhì)是“跳過”待刪除的結(jié)點(diǎn)，所以我們要找到待刪除結(jié)點(diǎn)的直接前驅(qū)結(jié)點(diǎn)，然后讓其直接前驅(qū)結(jié)點(diǎn)的 next 指針指向其直接后繼結(jié)點(diǎn)，以此來“跳過”待刪除結(jié)點(diǎn)，最后保存其數(shù)據(jù)域，釋放結(jié)點(diǎn)，即完成刪除。
這里只演示頭刪法。
因?yàn)閯h除的是頭結(jié)點(diǎn)的直接后繼結(jié)點(diǎn)，所以我們不必再費(fèi)力尋找待刪除結(jié)點(diǎn)的直接前驅(qū)結(jié)點(diǎn)了。
單向循環(huán)鏈表頭刪法過程
/** * 頭刪法：刪除頭結(jié)點(diǎn)之后的結(jié)點(diǎn) * p_head: 指向頭指針的指針 * elem: 指向保存數(shù)據(jù)變量的指針 */ void delete_from_head(Node **p_head, int *elem) { Node *head_node = *p_head; //頭結(jié)點(diǎn) if (head_node->next == head_node) { printf("空鏈表，無元素可刪。\n"); return; } Node *first_node = head_node->next; //首結(jié)點(diǎn)：頭結(jié)點(diǎn)的下一個(gè)結(jié)點(diǎn) *elem = first_node->data; //保存被刪除結(jié)點(diǎn)的數(shù)據(jù) head_node->next = first_node->next; //刪除結(jié)點(diǎn) free(first_node); //釋放 }我們可以一圈又一圈地循環(huán)遍歷鏈表，下面是循環(huán)打印 20 次結(jié)點(diǎn)地代碼：
/** * 循環(huán)打印20次結(jié)點(diǎn) */ void output_20(Node *head) { if (head->next == head) { printf("空鏈表。\n"); return; } Node *p = head->next; for (int i = 0; i <= 20; i++) { if (p != head) { //不打印頭結(jié)點(diǎn) printf("%d ", p->data); } p = p->next; } printf("\n"); }顧名思義，雙向鏈表，就是有兩個(gè)方向，一個(gè)指向前，一個(gè)指向后。這樣我們就彌補(bǔ)了單鏈表的某個(gè)結(jié)點(diǎn)只能找到其直接后繼的缺陷。如圖所示：
雙向鏈表
為了實(shí)現(xiàn)能指前和指后的效果，只靠 next 指針肯定是不夠的，所以我們需要再添加一個(gè)指針 —— prev，該指針指向某結(jié)點(diǎn)的直接前驅(qū)結(jié)點(diǎn)。
/*雙向鏈表的結(jié)點(diǎn)結(jié)構(gòu)體*/ typedef struct _Node { int data; //數(shù)據(jù)域 struct _Node *prev; //指向直接前驅(qū)結(jié)點(diǎn)的指針 struct _Node *next; //指向直接后繼結(jié)點(diǎn)的指針 } Node;雙向鏈表的空鏈表如圖所示：
要初始化一個(gè)這樣的空鏈表，需要?jiǎng)?chuàng)造出頭結(jié)點(diǎn)，然后將兩個(gè)指針域置空即可：
Node *create_node(int elem) { Node *new = (Node *)malloc(sizeof(Node)); new->data = elem; new->prev = NULL; new->next = NULL; return new; } void init(Node **p_head) { //創(chuàng)建頭結(jié)點(diǎn) Node *head_node = create_node(0); //頭指針指向頭結(jié)點(diǎn) *p_head = head_node; }這里只演示頭插法，過程如下：
雙向鏈表頭插法過程
代碼如下：
/** * 頭插法，新結(jié)點(diǎn)為頭結(jié)點(diǎn)的直接后繼 * p_head: 指向頭指針的指針 * elem: 新結(jié)點(diǎn)的數(shù)據(jù) */ void insert_at_head(Node **p_head, int elem) { Node *new = create_node(elem); Node *head_node = *p_head; //頭結(jié)點(diǎn) if (head_node->next != NULL) { //不為空鏈表 Node *first_node = head_node->next; //首結(jié)點(diǎn)：頭結(jié)點(diǎn)的下一個(gè)結(jié)點(diǎn) //首結(jié)點(diǎn)的prev指針指向new結(jié)點(diǎn) first_node->prev = new; //new結(jié)點(diǎn)的next指針指向首結(jié)點(diǎn) new->next = first_node; } //new結(jié)點(diǎn)的prev指針指向頭結(jié)點(diǎn) new->prev = head_node; //頭結(jié)點(diǎn)的next指針指向new結(jié)點(diǎn) head_node->next = new; }這里只演示頭刪法。下圖是將一個(gè)有兩個(gè)元素結(jié)點(diǎn)的雙向鏈表頭刪為空鏈表的過程：
雙向鏈表頭刪法過程
代碼如下：
/** * 頭刪法 * p_head: 指向頭指針的指針 * elem: 指向保存變量的指針 */ void delete_from_head(Node **p_head, int *elem) { Node *head_node = *p_head; //頭結(jié)點(diǎn) Node *first_node = head_node->next; //待刪除的首結(jié)點(diǎn)：頭結(jié)點(diǎn)的下一個(gè)結(jié)點(diǎn) if (head_node->next == NULL) { //判空 printf("空鏈表，無元素可刪。\n"); return; } *elem = first_node->data; //保存數(shù)據(jù) if (first_node->next != NULL) { first_node->next->prev = first_node->prev; } first_node->prev->next = first_node->next; free(first_node); }有了 next 指針域，我們可以一路向后遍歷;有了 prev 指針域，我們可以一路向前遍歷。
這里不再展示代碼了。
到此，關(guān)于“數(shù)據(jù)結(jié)構(gòu)的鏈表有那幾種類型”的學(xué)習(xí)就結(jié)束了，希望能夠解決大家的疑惑。理論與實(shí)踐的搭配能更好的幫助大家學(xué)習(xí)，快去試試吧！若想繼續(xù)學(xué)習(xí)更多相關(guān)知識(shí)，請繼續(xù)關(guān)注創(chuàng)新互聯(lián)網(wǎng)站，小編會(huì)繼續(xù)努力為大家?guī)砀鄬?shí)用的文章！
