前言
1.概念
單向鏈表：一塊內(nèi)存指向下一個(gè)內(nèi)存。
單鏈表存在一些缺陷：
1.查找速度慢。
2.不能從后往前找。
3.找不到前驅(qū)。
鏈表的結(jié)構(gòu)分為8種：
1.單向和雙向
2.帶頭和不帶頭
帶頭的鏈表有一個(gè)帶哨兵位的頭結(jié)點(diǎn)，這個(gè)節(jié)點(diǎn)不存儲(chǔ)有效數(shù)據(jù)。
好處：尾插更方便，不需要二級(jí)指針了，帶頭結(jié)點(diǎn)不需要改變傳過來的指針，，也就意味著不需要傳二級(jí)指針
3.循環(huán)和不循環(huán)
不循環(huán)：尾是指向空的
循環(huán)：尾是指針頭的
一、無頭單向肺循環(huán)鏈表：結(jié)構(gòu)簡(jiǎn)單，一般不會(huì)單獨(dú)用來存數(shù)據(jù)。實(shí)際中更多是作為其他數(shù)據(jù)結(jié)構(gòu)的子結(jié)構(gòu)，如哈希桶、圖的領(lǐng)接表等等。
另外這種結(jié)構(gòu)在筆試面試中出現(xiàn)很多。
二、帶頭雙向循環(huán)鏈表：結(jié)構(gòu)復(fù)雜，一般用在單獨(dú)存儲(chǔ)數(shù)據(jù)。實(shí)際中使用的鏈表數(shù)據(jù)結(jié)構(gòu)，都是帶頭雙向循環(huán)鏈表，另外這個(gè)結(jié)構(gòu)雖然結(jié)構(gòu)復(fù)雜，
但是使用代碼實(shí)現(xiàn)以后會(huì)發(fā)現(xiàn)帶來很多優(yōu)勢(shì)，實(shí)現(xiàn)反而簡(jiǎn)單了。
2.初始化
typedef struct ListNode
{
struct ListNode* next;
struct ListNode* prev;
LTDataType data;
}ListNode;
next表示指向下一個(gè)節(jié)點(diǎn)
prev表示前驅(qū)指針，指向上一個(gè)節(jié)點(diǎn)
一、雙向鏈表的應(yīng)用
1.打印鏈表和創(chuàng)建新的節(jié)點(diǎn)
//創(chuàng)建新的節(jié)點(diǎn)
ListNode* BuyListNode(LTDataType x)
{
ListNode* newnode = (ListNode*)malloc(sizeof(ListNode));
newnode->data = x;
newnode->next = NULL;
newnode->prev = NULL;
return newnode;
}
//打印鏈表
void ListPrint(ListNode* phead)
{
ListNode* cur = phead->next;
while (cur!= phead)
{
printf("%d ", cur->data);
cur = cur->next;
}
printf("\n");
}
2.鏈表的初始化和銷毀
//初始化
ListNode* ListInit()
{
ListNode* phead = BuyListNode(0);
phead->next = phead;
phead->prev = phead;
return phead;
}
//銷毀
void ListDestory(ListNode* phead)
{
assert(phead);
ListNode* cur = phead->next;
while (cur != phead)
{
ListNode* next = cur->next;
free(cur);
cur = next;
}
free(phead);
phead = NULL;
}
3.鏈表的首插和尾插
//尾插
void ListPushBack(ListNode* phead, LTDataType x)
{
assert(phead);
ListNode* tail = phead->prev;
ListNode* newnode = BuyListNode(x);
tail->next = newnode;
newnode->prev = tail;
newnode->next = phead;
phead->prev = newnode;
}
//上面的尾插針對(duì)空鏈表也是成立的，可以畫個(gè)圖理解一下
//雙向帶頭循環(huán)鏈表結(jié)構(gòu)雖然復(fù)雜了，但是操作反而簡(jiǎn)單了。
//結(jié)構(gòu)設(shè)計(jì)的優(yōu)勢(shì)
//內(nèi)存占用增加，每個(gè)節(jié)點(diǎn)多了一個(gè)前驅(qū)指針
//STL中的List原碼就是這個(gè)結(jié)構(gòu)
//頭插
void ListPushfront(ListNode* phead, LTDataType x)
{
assert(phead);
ListNode* newnode = BuyListNode(x);
ListNode* first = phead->next;
phead->next = newnode;
newnode->prev = phead;
newnode->next = first;
first->prev = newnode;
}
4.鏈表的尾刪和頭刪
//尾刪
void ListPopBack(ListNode* phead)
{
assert(phead);
assert(phead->next != phead);
ListNode* tail = phead->prev;
ListNode* last = tail->prev;
free(tail);
last->next = phead;
phead->prev = last;
tail = NULL;
}
//頭刪
void ListPopFront(ListNode* phead)
{
assert(phead);
assert(phead->next != phead);
ListNode* first = phead->next;
ListNode* second = first->next;
free(first);
phead->next = second;
second->prev = phead;
first = NULL;
}
5.鏈表的查找和指定位置的插入刪除
//查找
ListNode* ListFind(ListNode* phead, LTDataType x)
{
assert(phead);
ListNode* cur = phead->next;
while (cur!=phead)
{
if (cur->data == x)
{
return cur;
}
cur = cur->next;
}
return NULL;
}
//插入
void ListInsert(ListNode* phead, ListNode* pos, LTDataType x)
{
assert(pos);
ListNode* last = pos->prev;
ListNode* newnode = BuyListNode(x);
last->next = newnode;
newnode->prev = last;
newnode->next = pos;
pos->prev = newnode;
}
//刪除pos位置的數(shù)
void ListErase(ListNode* plist, ListNode* pos)
{
assert(pos);
ListNode* last = pos->prev;
ListNode* following = pos->next;
free(pos);
last->next = following;
following->prev = last;
pos = NULL;
}
二、封裝文件
注：以上函數(shù)封裝在List.c中
1. List.h文件
#pragma once
//雙向鏈表定義
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
typedef int LTDataType;
typedef struct ListNode
{
struct ListNode* next;
struct ListNode* prev;
LTDataType data;
}ListNode;
ListNode* ListInit();
void ListPrint(ListNode* plist);
void ListDestory(ListNode* plist);
void ListPushBack(ListNode* plist, LTDataType x);
void ListPushfront(ListNode* plist, LTDataType x);
void ListPopBack(ListNode* plist);
void ListPopFront(ListNode* plist);
ListNode* ListFind(ListNode* plist, LTDataType x);
//在pos位置之前插入一個(gè)值
void ListInsert(ListNode* plist, ListNode* pos, LTDataType x);
//刪除pos位置的值
void ListErase(ListNode* plist, ListNode* pos);
2.測(cè)試函數(shù)
#include "List.h"
void TestList1()
{
ListNode* plist = ListInit();
ListPushBack(plist, 1);
ListPushBack(plist, 2);
ListPushBack(plist, 3);
ListPushBack(plist, 4);
ListPrint(plist);
ListDestory(plist);
}
void TestList2()
{
ListNode* plist = ListInit();
ListPushfront(plist, 1);
ListPushfront(plist, 2);
ListPushfront(plist, 3);
ListPushfront(plist, 4);
ListPrint(plist);
ListDestory(plist);
}
void TestList3()
{
ListNode* plist = ListInit();
ListPushfront(plist, 1);
ListPushfront(plist, 2);
ListPushfront(plist, 3);
ListPushfront(plist, 4);
ListPrint(plist);
printf("\n");
ListPopBack(plist);
ListPrint(plist);
ListDestory(plist);
}
void TestList4()
{
ListNode* plist = ListInit();
ListPushfront(plist, 1);
ListPushfront(plist, 2);
ListPushfront(plist, 3);
ListPushfront(plist, 4);
ListPrint(plist);
printf("\n");
ListPopFront(plist);
ListPrint(plist);
ListDestory(plist);
}
void TestList5()
{
ListNode* plist = ListInit();
ListPushfront(plist, 1);
ListPushfront(plist, 2);
ListPushfront(plist, 3);
ListPushfront(plist, 4);
ListPrint(plist);
ListNode* pos = ListFind(plist, 3);
if (pos)
{
//查找同時(shí)可以附帶修改
printf("找到了");
pos->data = pos->data * 10;
}
else
{
printf("沒有找到");
}
}
void TestList6()
{
ListNode* plist = ListInit();
ListPushfront(plist, 1);
ListPushfront(plist, 2);
ListPushfront(plist, 3);
ListPushfront(plist, 4);
ListPrint(plist);
printf("\n");
ListNode* pos = ListFind(plist, 3);
if (pos)
{
ListInsert(plist, pos, 100);
ListErase(plist, pos->prev);
}
ListPrint(plist);
}
int main()
{
TestList6();
return 0;
}
用以上函數(shù)進(jìn)行測(cè)試文章來源：http://www.zghlxwxcb.cn/news/detail-783662.html
總結(jié)
雖然雙向鏈表結(jié)構(gòu)付咱，但是理解其結(jié)構(gòu)可發(fā)現(xiàn)各個(gè)接口比單向鏈表的接口寫起來更加簡(jiǎn)單，更加容易上手文章來源地址http://www.zghlxwxcb.cn/news/detail-783662.html
到了這里，關(guān)于數(shù)據(jù)結(jié)構(gòu)---雙向鏈表的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
