本期帶大家一起用C語言實現(xiàn)雙向鏈表??????
一、鏈表的概念??
鏈表是一種物理存儲單元上非連續(xù)、非順序的存儲結(jié)構(gòu)，數(shù)據(jù)元素的邏輯順序是通過鏈表中的指針鏈接次序?qū)崿F(xiàn)的；簡單來說，線性表的鏈式存儲結(jié)構(gòu)生成的表，稱作“鏈表”。
二、鏈表中數(shù)據(jù)元素的構(gòu)成?? ??
每個元素本身由兩部分組成：
1、本身的信息，稱為“數(shù)據(jù)域”
2、指向直接后繼的指針，稱為“指針域”
三、鏈表的結(jié)構(gòu)?? ?? ??
1、帶哨兵位或者不帶哨兵位 ??
3、單向或者雙向 ?? ?? ??
四、 雙向帶哨兵位循環(huán)鏈表的實現(xiàn)?? ?? ?? ??
這里先建立三個文件：
1?? ：SeqList.h文件，用于函數(shù)聲明
2?? ：SeqList.c文件，用于函數(shù)的定義
3?? ：Test.c文件，用于測試函數(shù)
建立三個文件的目的： 將順序表作為一個項目來進行書寫，方便我們的學習與觀察。
一、定義雙向鏈表的結(jié)構(gòu)體?
雙向鏈表的結(jié)構(gòu)為
存儲的有效數(shù)據(jù)data
指向后一個數(shù)據(jù)地址的指針next
指向前一個數(shù)據(jù)指針的數(shù)據(jù)prev
typedef int LTDataType;
typedef struct ListNode
{
LTDataType data;
struct ListNode* next;
struct ListNode* prev;
}LTNode;
這里我們使用typedef對我們所存儲的數(shù)據(jù)，以及雙向鏈表結(jié)構(gòu)體重命名，方便我們后續(xù)修改 ?? ?? ??
二、接口的實現(xiàn)??
1.雙向鏈表的創(chuàng)建以及初始化
LTNode* CreatNode(LTDataType x)
{
LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));
if (newnode == NULL)
{
perror("malloc fail");
return NULL;
}
newnode->data = x;
newnode->next = NULL;
newnode->prev = NULL;
return newnode;
}
LTNode* LTInit()
{
LTNode* phead = CreatNode(-1);
phead->next = phead;
phead->prev = phead;
}
創(chuàng)建哨兵位節(jié)點
2、尾插
對鏈表進行尾插操作，添加數(shù)據(jù)到鏈表的尾部?? ?? ??
void LTPushBack(LTNode* phead,LTDataType x)
{
assert(phead);
LTNode* newnode = CreatNode(x);
LTNode* tail = phead->prev;
tail->next = newnode;
newnode->prev = tail;
phead->prev = newnode;
newnode->next = phead;
}
首先我們需要創(chuàng)建一個新的節(jié)點，然后將我們的雙向鏈表和我們創(chuàng)建的新節(jié)點進行鏈接起來?? ??
3、頭插
對鏈表進行頭插操作，添加數(shù)據(jù)到鏈表的頭部
但注意的是：不是添加到哨兵位的前面?? ??
而是添加到哨兵位下一個節(jié)點的前面
void LTPushFront(LTNode* phead, LTDataType x)
{
assert(phead);
LTNode* node = CreatNode(x);
node->next = phead->next;
phead->next->prev = node;
phead->next = node;
node->prev = phead;
}
4、檢查鏈表當中是否只有哨兵位
bool LTEmpty(LTNode* phead)
{
return phead == phead->next;
}
5、尾刪
對于 雙向鏈表 的尾刪，只要找到尾結(jié)點的前一個節(jié)點改變它和哨兵位的連接關(guān)系即可?? ??
如果要找到尾結(jié)點的前一個節(jié)點，那么我只需要通過
哨兵位 的 prev 找到 尾，在通過 尾 的 prev 就可以找到 尾結(jié)點的前一個節(jié)點。然后調(diào)整這個節(jié)點和哨兵位的鏈接關(guān)系，然后 釋放尾結(jié)點 就可以了
但是要注意，當鏈表只有哨兵位的時候不能進行刪除操作?。。??
如圖所示
void LTPopBack(LTNode* phead)
{
assert(phead);
if (LTEmpty(phead))
{
printf("鏈表為空\n");
return;
}
LTNode* tail = phead->prev;
LTNode* tailPrev = tail->prev;
free(tail);
tailPrev->next = phead;
phead->prev = tailPrev;
}
上面說過，如果當鏈表只有哨兵位的時候不能進行刪除操作?。。?br> 所以我們通過了一個函數(shù)來檢查當前鏈表是否只有一個哨兵位?? ??
bool LTEmpty(LTNode* phead)
{
return phead == phead->next;
}
6、頭刪
對于頭刪來說，我需要刪除 哨兵位的 next 節(jié)點 ，我們
需要連接哨兵位和哨兵位next的next，然后釋放哨兵位的next??
但是同樣需要注意的是：鏈表當中只有哨兵位的時候我們不能對其刪除！?。?/p>
如圖所示：??
void LTPopFront(LTNode* phead)
{
assert(phead);
if (LTEmpty(phead))
{
printf("鏈表為空\n");
return;
}
LTNode* next = phead->next->next;
phead->next = next;
phead->next->prev = phead;
}
7、查找鏈表當中元素
當我們需要查找鏈表當中是否存在某個元素的時候，我們需要鏈表，看是否存在該個元素????
但是帶頭雙向循環(huán)鏈表當中不存在NULL
所以停止遍歷的時候我們的終止條件為！=·phead
如果找到，返回該節(jié)點的地址；如果找不到返回 NULL
LTNode* LTFind(LTNode* phead, LTDataType x)
{
assert(phead);
LTNode* cur = phead->next;
while (cur != phead)
{
if (cur->data == x)
return cur;
cur = cur->next;
}
return NULL;
}
8、在pos位置之前插入數(shù)據(jù)
在 pos 位置之前插入，那么 通過 pos 的 prev 找到 pos 位置的上一個節(jié)點 posPrev ，然后改變 posPrev 和 新節(jié)點 newnode 之間的鏈接和 newnode 和 pos 之間的鏈接
需要同LTFind一起使用
void LTInsert(LTNode* pos, LTDataType x)
{
LTNode* node = CreatNode(x);
LTNode* posPrev = pos->prev;
posPrev->next = node;
node->next = pos;
node->prev = posPrev;
pos->prev = node;
}
代碼實現(xiàn)邏輯圖如下所示
那么很好，有了這個接口之后，可以把它 復(fù)用 于 尾插 和 頭插。
對于 尾插 來說， pos 位置就是 phead ，因為 phead 的前面就是
鏈表的尾，在 phead 位置前插入，就是尾插：
void LTPushBack(LTNode* phead,LTDataType x)
{
assert(phead);
LTInsert(phead, x);
}
對于 頭插 來說， pos 位置就是 phead->next
為第一個節(jié)點的前面，在 phead->next 位置前插入，就是頭插：
void LTPushFront(LTNode* phead, LTDataType x)
{
assert(phead);
LTInsert(phead->next, x);
}
9、刪除pos位置的數(shù)據(jù)
在 pos 位置刪除， 只要找到 pos 的前一個節(jié)點 posPrev
然后找到 pos 的后一個節(jié)點 posNext ，然后將這兩個節(jié)點的 prev 和 next 建立正確的鏈接關(guān)系。然后釋放 pos 節(jié)點，pos 節(jié)點置空。??????
void LTErase(LTNode* pos)
{
assert(pos);
pos->prev->next = pos->next;
pos->next->prev = pos->prev;
free(pos);
}
同樣的，這個接口也能復(fù)用于 尾刪 和 頭刪 。
對于 尾刪 來說，， pos 位置就是 phead->prev
為鏈表的尾，刪除 phead->prev 位置，就是尾刪：
為了避免空指針異常，我們需要進行判斷
void LTPopBack(LTNode* phead)
{
assert(phead);
if (LTEmpty(phead))
{
printf("鏈表為空\n");
return;
}
LTErase(phead->prev);
}
對于 頭刪 來說， pos 位置就是 phead->next
為鏈表的頭，刪除 phead->next 位置，就是頭刪：
為了避免空指針異常，我們需要進行判斷
void LTPopFront(LTNode* phead)
{
assert(phead);
if (LTEmpty(phead))
{
printf("鏈表為空\n");
return;
}
LTErase(phead->next);
}
10、打印雙向鏈表
打印整個鏈表，就只需要遍歷鏈表，控制好循環(huán)的停止條件：
循環(huán)終止條件設(shè)置為！=phead
void LTPrint(LTNode* phead)
{
assert(phead);
LTNode* cur = phead->next;
printf("哨兵位->");
while (cur != phead)
{
printf("%d ", cur->data);
cur = cur->next;
}
printf("\n");
}
11、銷毀雙向鏈表
我需要把 哨兵位 ，鏈表的節(jié)點 全部刪除，那么我就要使用循環(huán)來刪除。
循環(huán)的結(jié)束條件為 != phead。在銷毀的過程中，每次記住我當前節(jié)點的下一個節(jié)點，以便迭代????
但是由于我們的 形參是一級指針
所以不能夠?qū)⑸诒徽ｄN毀，我們需要在主函數(shù)當中手動將哨兵位置為NULL
void LTDestroy(LTNode* phead)
{
assert(phead);
LTNode* cur = phead->next;
while (cur != phead)
{
LTNode* next = cur->next;
free(cur);
cur = next;
}
free(cur);
}
12、雙向鏈表的測試
五、源代碼??????
1、LIst.h
#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<stdbool.h>
#include<assert.h>
typedef int LTDataType;
typedef struct ListNode
{
LTDataType data;
struct ListNode* next;
struct ListNode* prev;
}LTNode;
//初始化
LTNode* LTInit();
//打印鏈表
void LTPrint(LTNode* phead);
//尾插
void LTPushBack(LTNode* phead,LTDataType x);
//頭插
void LTPushFront(LTNode* phead, LTDataType x);
//尾刪
void LTPopBack(LTNode* phead);
//頭刪
void LTPopFront(LTNode* phead);
//查找
LTNode* LTFind(LTNode* phead,LTDataType x);
//pos之前插入
void LTInsert(LTNode* pos, LTDataType x);
//刪除pos位置的值
void LTErase(LTNode* pos);
//銷毀
void LTDestroy(LTNode* phead);
2、List.c
#define _CRT_SECURE_NO_WARNINGS
#include"List.h"
LTNode* CreatNode(LTDataType x)
{
LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));
if (newnode == NULL)
{
perror("malloc fail");
return NULL;
}
newnode->data = x;
newnode->next = NULL;
newnode->prev = NULL;
return newnode;
}
LTNode* LTInit()
{
LTNode* phead = CreatNode(-1);
phead->next = phead;
phead->prev = phead;
}
bool LTEmpty(LTNode* phead)
{
return phead == phead->next;
}
void LTPrint(LTNode* phead)
{
assert(phead);
LTNode* cur = phead->next;
printf("哨兵位->");
while (cur != phead)
{
printf("%d ", cur->data);
cur = cur->next;
}
printf("\n");
}
void LTPushBack(LTNode* phead,LTDataType x)
{
assert(phead);
//LTNode* newnode = CreatNode(x);
//LTNode* tail = phead->prev;
//tail->next = newnode;
//newnode->prev = tail;
//phead->prev = newnode;
//newnode->next = phead;
LTInsert(phead, x);
}
void LTPushFront(LTNode* phead, LTDataType x)
{
assert(phead);
//LTNode* node = CreatNode(x);
//node->next = phead->next;
//phead->next->prev = node;
//phead->next = node;
//node->prev = phead;
LTInsert(phead->next, x);
}
void LTPopBack(LTNode* phead)
{
assert(phead);
/*if (LTEmpty(phead))
{
printf("鏈表為空\n");
return;
}
LTNode* tail = phead->prev;
LTNode* tailPrev = tail->prev;
free(tail);
tailPrev->next = phead;
phead->prev = tailPrev;*/
if (LTEmpty(phead))
{
printf("鏈表為空\n");
return;
}
LTErase(phead->prev);
}
void LTPopFront(LTNode* phead)
{
assert(phead);
/*if (LTEmpty(phead))
{
printf("鏈表為空\n");
return;
}
LTNode* next = phead->next->next;
phead->next = next;
phead->next->prev = phead;*/
if (LTEmpty(phead))
{
printf("鏈表為空\n");
return;
}
LTErase(phead->next);
}
LTNode* LTFind(LTNode* phead, LTDataType x)
{
assert(phead);
LTNode* cur = phead->next;
while (cur != phead)
{
if (cur->data == x)
return cur;
cur = cur->next;
}
return NULL;
}
void LTInsert(LTNode* pos, LTDataType x)
{
LTNode* node = CreatNode(x);
LTNode* posPrev = pos->prev;
posPrev->next = node;
node->next = pos;
node->prev = posPrev;
pos->prev = node;
}
void LTErase(LTNode* pos)
{
assert(pos);
pos->prev->next = pos->next;
pos->next->prev = pos->prev;
free(pos);
}
void LTDestroy(LTNode* phead)
{
assert(phead);
LTNode* cur = phead->next;
while (cur != phead)
{
LTNode* next = cur->next;
free(cur);
cur = next;
}
free(cur);
}
3、test.c
#define _CRT_SECURE_NO_WARNINGS
#include"List.h"
void test1()
{
printf("尾插：");
LTNode* plist = LTInit();
LTPushBack(plist, 1);
LTPushBack(plist, 2);
LTPushBack(plist, 3);
LTPushBack(plist, 4);
LTPrint(plist);
LTDestroy(plist);
printf("\n");
}
void test2()
{
printf("頭插：");
LTNode* plist = LTInit();
LTPushFront(plist, 1);
LTPushFront(plist, 2);
LTPushFront(plist, 3);
LTPushFront(plist, 4);
LTPushFront(plist, 5);
LTPrint(plist);
LTDestroy(plist);
plist = NULL;
printf("\n");
}
void test3()
{
printf("尾刪：");
LTNode* plist = LTInit();
LTPushFront(plist, 1);
LTPushFront(plist, 2);
LTPopBack(plist);
LTPopBack(plist);
LTPopBack(plist);
LTPopBack(plist);
LTPrint(plist);
LTDestroy(plist);
printf("\n");
}
void test4()
{
printf("頭刪：");
LTNode* plist = LTInit();
LTPushFront(plist, 1);
LTPushFront(plist, 2);
LTPopFront(plist);
LTPopFront(plist);
LTPopFront(plist);
LTPopFront(plist);
LTPrint(plist);
LTDestroy(plist);
printf("\n");
}
void test5()
{
printf("pos之前插入");
LTNode* plist = LTInit();
LTPushFront(plist, 1);
LTPushFront(plist, 2);
LTPushFront(plist, 3);
LTPushFront(plist, 4);
LTPushFront(plist, 5);
LTNode* pos = LTFind(plist,5);
if (pos != NULL)
{
LTInsert(pos, 9);
}
LTPrint(plist);
LTDestroy(plist);
printf("\n");
}
void test6()
{
printf("刪除pos的值：");
LTNode* plist = LTInit();
LTPushFront(plist, 1);
LTPushFront(plist, 2);
LTPushFront(plist, 3);
LTPushFront(plist, 4);
LTPushFront(plist, 5);
LTNode* pos = LTFind(plist, 3);
if (pos != NULL)
{
LTErase(pos);
}
LTPrint(plist);
LTDestroy(plist);
printf("\n");
}
int main()
{
test1();
test2();
test3();
test4();
test5();
test6();
return 0;
}
六、感謝與交流?
??????如果大家通過本篇博客收獲了,對順序表有了新的了解的話
那么希望支持一下哦如果還有不明白的，疑惑的話，或者什么比較好的建議的話，可以發(fā)到評論區(qū)，
我們一起解決，共同進步 ??????
最后謝謝大家????????????文章來源：http://www.zghlxwxcb.cn/news/detail-445102.html
文章來源地址http://www.zghlxwxcb.cn/news/detail-445102.html
到了這里，關(guān)于雙向鏈表--C語言實現(xiàn)數(shù)據(jù)結(jié)構(gòu)的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
