前言

上一節,博主講解了單鏈表,并且具體的實作了單鏈表的增刪改查,而這次博主要講解的是雙向回圈鏈表,簡稱雙鏈表.

為何要雙鏈表?

既然有了單鏈表,為何還搞一個雙鏈表呢? 答案就是解決了單鏈表的一些缺點. 這個和上一節博主講解的為何需要單鏈表,而答案是單鏈表可以解決順序表空間浪費嚴重的問題一樣. 所以他們三者構成了一個簡單關系,如下圖:

補充:,大家如果對單鏈表的增刪查改比較熟悉,就知道單鏈表有一個致命的缺陷:

• 如果要動尾結點,就必須挨個遍歷,找到倒數第二個結點.
• 如果要動中間結點,往往也是需要先找到中間結點的前一個結點.

也就是說,如果想要修改一些東西,就必須得遍歷一下鏈表,這就導致很憋屈,特別是尾插和尾刪,明明只需要修改最后一個,卻必須全部遍歷,而這也就是雙鏈表的誕生原因.他完美的解決了單鏈表的問題.

雙鏈表的結構圖示

既然知道了雙鏈表解決的是單鏈表的哪些問題,我們不妨猜猜雙鏈表到底什么結構呢?

• 解決了想要動尾結點不需要遍歷的問題— --- — --- 那尾結點一定有被指向,被誰指向呢?兩種可能:

  • 被尾結點前一個指向
  • 被頭結點指向

• 解決了修改中間結點不需要遍歷的問題— --- — --- 那說明該結點的前一個結點一定有被指向,被誰指向呢?兩種可能:

  • 被所需要動結點的前兩個結點指向
  • 被所需要動結點指向

所以,他的結構大致應該是下面這樣,注意哦~~~,博主說的是大致,因為有一些小細節需要單獨拎出來說的:

嗯~~~,這樣完全符合我們的要求,但實際上 雙向回圈鏈表的真正結構,也是這樣,只是比起這個結構多了一個無效資料頭結點,這是為了方便頭插頭刪.

真正的雙向鏈表結構:

專案的建造

還是老規矩,博主用的vs2019,就仍然用它進行演示.

我們的目的是要實作雙鏈表,那我們現在就需要3個檔案,分別是List.h ,List.c, test.c

作用分別是: 結構體的定義,頭檔案的參考,函式宣告, 函式定義,函式測驗

如圖:

雙鏈表結點的定義

上圖中,雙鏈表的結構圖示我們已經非常清楚了,現在我們就需要按照圖示用代碼進行實作了.

圖示中,一個結點的內容有哪些?

• 一個指向前面結點的指標
• 一個存盤資料的空間
• 一個指向后面結點的指標

在List.h檔案中定義雙鏈表結構

typedef int LTDataType; //我們并不知道要存盤什么資料,便以int為例.   之所以用typedef改名是為了以后不用int,修改更方便

typedef struct ListNode
{
    struct ListNode* prev;
    LTDataType data;
    struct ListNode* next;
}LTNode; //修改個更短的名字

雙鏈表的各種方法實作

順序表有順序表的各種操作函式,單鏈表有單鏈表的各種操作,而我們的雙鏈表同理,也是有自己的各種操作.

那有什么樣子的操作呢? 博主全部列舉在下面,后面將會一一進行實作.

在List.h檔案中宣告各種方法

LTNode* BuyListNode(LTDataType elem);                     //創建一個新鏈表結點
void ListInit(LTNode** pphead);   						  //初始化
bool ListEmpty(LTNode* phead);    						  //判斷鏈表是否為空
size_t ListSize(LTNode* phead);   						  //回傳鏈表元素數量
void ListPrint(LTNode* phead);    						  //列印鏈表內容

void ListPushBack(LTNode* phead, LTDataType* elem);       //尾插
void ListPushFront(LTNode* phead, LTDataType* elem);      //頭插
void ListPopBack(LTNode* phead);                          //尾刪
void ListPopFront(LTNode* phead);                         //頭刪

LTNode* ListFind(LTNode* phead,LTDataType elem);          //查找元素elem,并回傳elem所在結點
void ListInsert(LTNode* pos,LTDataType elem);             //在結點pos之前插入elem,一般配合ListFind使用
void ListErease(LTNode* pos);                             //洗掉pos結點,一般配合ListFind使用
void ListDestroy(LTNode* phead);  						  //銷毀雙鏈表

雙鏈表之新建結點

結點的作用是干什么呢? 沒錯, 那就是存盤資料,所以新建結點首要目的就是把資料存盤

LTNode* BuyListNode(LTDataType elem)
{
    LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));
    if(newnode == NULL)
    {
        perror("錯誤原因:");
        exit(-1);
    }
    newnode->data = elem;
    newnode->prev = NULL;
    newnode->next = NULL;
    return newnode;
}

雙鏈表之初始化

既然是初始化,那我們要初始化什么呢? 我們知道雙鏈表是具有一個無效資料頭結點的,所以我們初始化要做的事情就是

給無效資料頭結點創立一個空間,并隨機給個值,然后讓其前后指標都指向著自己,這樣就符合 雙向回圈鏈表的結構

//大家注意哦~,博主這里用的是二級指標,為什么呢?
//因為實參是一個一級指標
//而如果形參是一級指標,這就屬于值傳遞了,函式內pphead的值改變并不會影響外面的實參,而初始化是需要修改實參的.
void ListInit(LTNode** pphead)
{
    assert(pphead); //pphead一定不能是空指標
    
    (*pphead) = BuyListNode(-1); //隨機給一個值用來創建結點
    
    (*pphead)->prev = *pphead;
    (*pphead)->next = *pphead;
}

測驗是否成功:

通過除錯可以發現,plist存盤的資料是-1,前指標指向了plist自己,后指標plist也指向了自己.成功!!!

雙鏈表之判空

雙鏈表判空,判斷的是哪一部分呢? 沒錯,判斷的是頭結點的后面部分,即排除了無效資料頭結點的部分,如圖:

所以我們只需要判斷就是頭結點之后(phead->next)的結點值是不是phead,原因:

• 當鏈表為空時候,就只剩下一個無效頭結點.— --- —即phead->next 等于 phead
• 當鏈表不為空時候,就有有效結點— --- —即phead->next 不等于 phead

bool ListEmpty(LTNode* phead)
{
    assert(phead); //phead不能為空
    
    return phead->next == phead; 
}

測驗是否成功:

1代表空,正確,因為這個時候除了頭結點自己,就沒有任何結點

雙鏈表之求具體元素數量

同樣,我們求取元素數量求取的還是頭結點之后.

size_t ListSize(LTNode* phead)
{
    assert(phead);
    size_t sum = 0;
    LTNode* cur = phead->next; //從頭結點之后開始遍歷
    
    while(cur != phead) //當cur再次為phead時候,說明鏈表已經遍歷完畢.
    {
        sum++;
        cur = cur->next;
    }
    
    return sum;
}

測驗是否成功:

成功!!!

雙鏈表之列印鏈表內容

一樣,我們列印的還是有效資料,即頭結點之后的資料

void ListPrint(LTNode* phead)
{
	assert(phead);
	LTNode* cur = phead->next;

	while (cur != phead)
	{
		printf("%d--->", cur->data);
		cur = cur->next;
	}
	printf("|完畢|\n");
}

雙鏈表之尾插

終于到這里了,這就是我們的重頭戲部分了.

還記得我們為什么有雙鏈表嗎?那就是尾插時候不需要從頭遍歷到尾,才能找到尾結點.

我們定義的這個雙向鏈表的尾結點怎么找到呢? 沒錯 , phead->prev

那么我們尾插的步驟是什么呢? 請看圖:

• 第一步,創建新結點存盤資料
• 第二步,原尾結點和現在新結點互相鏈接
• 第三步,新結點和頭結點互相鏈接

void ListPushBack(LTNode* phead, LTDataType* elem)
{
    assert(phead);
    
    LTNode* tail = phead->prev;  //找到尾結點
    LTNode* newnode  = BuyListNode(elem); //創建新結點
    
    //原來尾結點和現在新結點鏈接
    tail->next = newnode;
    newnode->prev = tail;
    
    //新結點和頭結點鏈接
    phead->prev = newnode;
    newnode->next = phead;
}

測驗是否成功

成功!!!

雙鏈表之尾刪

老規矩,到底怎樣操作呢?,先上圖!

• 第一步,找到尾結點和倒數第二個結點
• 第二步,釋放尾結點
• 第三步,頭結點和倒數第二個結點連接

void ListPopBack(LTNode* phead)
{
    assert(phead);
    assert(ListEmpty(phead)); //如果鏈表為空就不能洗掉.
    
    LTNode* tail = phead->prev;//尾結點
    LTNode* tail_prev = tail->prev;//倒數第二個結點
    
    free(tail);//釋放尾結點
    tail = NULL;
    
    tail_prev -> next = phead; //頭結點和倒數第二個結點連接
    phead->prev = tail_prev;
}

測驗是否成功

成功!!

雙鏈表之頭插

頭插怎樣操作?? 還是老規矩,先上圖?

• 第一步,創建新結點存盤資料
• 第二步,新結點與頭結點后的首結點鏈接
• 第三步,新結點與頭結點鏈接

void ListPushFront(LTNode* phead, LTDataType* elem)
{
    assert(phead);
    
    LTNode* newnode  = BuyListNode(elem); //創建新結點存盤資料
    LTNode* Second_first = phead->next; //頭結點后的首結點.
    
    //新結點 與 頭結點后的首結點 鏈接
    Second_first ->prev = newnode;
    newnode->next = Second_first;
    
    //新結點與頭結點鏈接
    phead->next = newnode;
    newnode->prev = phead;
}

測驗是否成功:

成功!!!

雙鏈表之頭刪

怎樣頭刪? 還是老規矩,先畫圖看清楚步驟!

• 第一步,頭結點與頭刪結點后的結點連接
• 第二步,釋放頭刪結點

void ListPopFront(LTNode* phead)
{
    assert(phead);
    assert(!ListEmpty(phead)); //如果為空就無法洗掉
    LTNode* Front_second = phead->next->next;//頭刪結點后的結點
    LTNode* front = phead->next; //頭刪結點
    
    //連接
    phead->next = Front_second;
    Front_second->prev = phead;
    
    //釋放頭刪結點
    free(front);
    front = NULL;
}

測驗是否成功

成功!!

雙鏈表之查找值

這個題比較簡單,直接遍歷查找就行,然后回傳該結點值

LTNode* ListFind(LTNode* phead,LTDataType elem)
{
    assert(phead);
    LTNode* cur = phead->next;
    while(cur != phead)
    {
        if(cur->data == elem)
        {
            return cur;
        }
        cur = cur->next;
    }
    return NULL;
}

雙鏈表之任意位置插入值

任意位置插入值的步驟和其實和頭插的步驟一模一樣,只是頭插是在頭結點后面的首結點前插入.

而任意位置前插入是在給定的pos結點之前插入,所以這里博主就不畫圖了,大家可以看著頭插的圖進行理解.

void ListInsert(LTNode* pos,LTDataType elem) //還記得我們最開始宣告時候說的,這個函式需要和ListFind配合嗎?請看:
{
    assert(pos);
    
    LTNode* pos_prev = pos->prev;  //保存pos結點之前的結點
    
    LTNode* newnode = BuyListNode(elem); //創建新結點
    
    //新結點與pos鏈接
    newnode->next = pos;
    pos->prev = newnode;
    
    //新結點與原來pos之前的結點連接
    pos_prev->next= newnode;
    newnode->prev = pos_prev;
    
}

測驗是否成功

成功!!!

雙鏈表之任意位置洗掉

任意位置洗掉和尾刪的步驟一模一樣,只是尾刪洗掉的是尾結點,連接的是原來尾結點前面結點和頭結點

而任意位置洗掉的是我們給的結點pos,連接的是pos前后的結點,一樣,大家可以去看尾刪的動圖,博主就不再畫了

void ListErease(LTNode* pos)
{
    assert(pos);
    
    LTNode* prev = pos-> prev; //pos 之前結點
    LTNode* next = pos->next;  //pos 之后結點
    
    free(pos);
    pos = NULL;
    
    prev->next = next;
    next->prev = prev;
}

測驗是否成功:

成功!!!

雙鏈表之銷毀空間

挨個釋放即可

void ListDestroy(LTNode* phead)
{
    assert(phead);
    
    LTNode* cur = phead->next;
    while(cur != phead)
    {
        LTNode* next = cur->next;
        free(cur);
        cur = next;
    }
    
    free(cur);
    cur = NULL;
}

測驗:

成功~~~