帶頭雙向循環(huán)鏈表
- 帶頭雙向循環(huán)鏈表的優(yōu)點
1.支持任意位置時間復雜度為O(1)的插入和刪除。
2.按照需求申請釋放空間，無需擔心空間不夠用，無需擔心浪費。
3.帶頭可以省去鏈表為空時的判斷，可以使代碼更加簡約
- 帶頭雙向循環(huán)鏈表的缺點
1.不可以進行下標隨機訪問。
2.緩存利用率低
帶頭雙向循環(huán)鏈表是線性表的一種，帶頭雙向循環(huán)鏈表是鏈式存儲的線性表，不同于順序表，鏈表在內(nèi)存空間中不連續(xù)。
帶頭：帶頭就是帶哨兵位，可以省鏈表為空時進行的判斷。
雙向：由結構體內(nèi)的next指針下一條數(shù)據(jù)進行鏈接，由prev對前一條數(shù)據(jù)進行鏈接??。
循環(huán)：以循環(huán)方式進行鏈接，頭的（前一個）prev是尾，尾的next（后一個）是頭。
PS:需要源碼直接通過目錄跳轉到最后
帶頭雙向循環(huán)鏈表主體結構
默認大小與擴容大小還有類型都可以是任意大小或類型
typedef int DListDataType; //數(shù)據(jù)類型
typedef struct ListNode
{
DListDataType data;
struct ListNode* prev; //指針指向前一個結點
struct ListNode* next; //指針指向后一個結點
}LTNode;
帶頭雙向循環(huán)鏈表操作函數(shù)介紹
- LTNode* InitLTNode(); //鏈表初始化
- void ListInsert(LTNode* pos, DListDataType x); //任意位置插入
- void ListPushBack(LTNode* phead, DListDataType x); //尾插
- void ListPushFront(LTNode* phead, DListDataType x); //頭插
- void print(LTNode* phead); //輸出鏈表
- void ListErase(LTNode* pos); //任意位置刪除
- void ListPopBack(LTNode* phead); //尾刪
- void ListPopFront(LTNode* phead); //頭刪
- LTNode* LTModify(LTNode* phead, DListDataType x); //修改指定結點
- LTNode* LTFind(LTNode* phead, DListDataType x); //查找指定結點
- void LTDestory(LTNode* phead); //銷毀鏈表
為了代碼方便閱讀，將帶頭雙向循環(huán)鏈表操作函數(shù)全部放在LinkedList.c文件中，將頭文件放在LinkedList.h，測試文件test.c ??
帶頭雙向循環(huán)鏈表操作函數(shù)實現(xiàn)
為了方便調(diào)試，建議每寫完1-2個函數(shù)就進行測試，初始化之后，首先實現(xiàn)print函數(shù)可以方便我們進行調(diào)試。
帶頭雙向循環(huán)鏈表的初始化函數(shù)：
LTNode* Phead = InitLTNode(); //初始化哨兵位
LTNode* BuyNewNode(DListDataType x) //開辟一個新結點
{
LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));
if (newnode == NULL)
{
perror("malloc");
return NULL;
}
newnode->next = NULL;
newnode->prev = NULL;
newnode->data = x;
return newnode;
}
LTNode* InitLTNode()
{
LTNode* phead = BuyNewNode(-1);
phead->next = phead;
phead->prev = phead;
return phead;
}
必須先進行初始化哨兵位，將哨兵位指向自己形成循環(huán)
打印函數(shù)
先寫出打印函數(shù)，方便進行調(diào)試
void print(LTNode* phead)
{
assert(phead);
LTNode* cur = phead->next;
printf("head");
while (cur!=phead)
{
printf("->%d", cur->data);
cur = cur->next;
}
printf("\n");
}
帶頭雙向循環(huán)鏈表插入函數(shù)：
指定結點后插入和查找函數(shù)
兩個函數(shù)可以配合使用，使用LTFind查找到需要插入的位置，然后使用ListInsert進行更改
LTNode* LTFind(LTNode* phead, DListDataType x)
{
assert(phead);
LTNode* cur = phead->next;
while (cur)
{
if (cur->data == x)
{
return cur;
}
cur = cur->next;
}
return NULL;
}
LTNode* BuyNewNode(DListDataType x)
{
LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));
if (newnode == NULL)
{
perror("malloc");
return NULL;
}
newnode->next = NULL;
newnode->prev = NULL;
newnode->data = x;
return newnode;
}
void ListInsert(LTNode* pos,DListDataType x)
{
assert(pos);
LTNode* newnode = BuyNewNode(x);
LTNode* prev = pos->prev;
prev->next = newnode;
newnode->prev = prev;
newnode->next = pos;
pos->prev = newnode;
}
頭插
頭插將新結點插入到哨兵位后面的結點
這里面有一種簡單的寫法，就是直接復用ListInsert，將哨兵位后面的結點傳過去，也是頭插的效果
void ListPushFront(LTNode* phead, DListDataType x)
{
assert(phead);
//第一種方法
//ListInsert(phead->next,x);
//第二種方法
LTNode* newnode = BuyNewNode(x);
LTNode* secound = phead->next;
newnode->next = secound;
secound->prev = newnode;
phead->next = newnode;
newnode->prev = phead;
}
尾插
從最后一個結點后面插入新結點
尾插也可以復用ListInsert函數(shù)
- 尾插也會用到申請新結點的函數(shù)，這里不重復了
void ListPushBack(LTNode* phead, DListDataType x)
{
assert(phead);
//第一種辦法
//ListInsert(phead,x);
//第二種辦法
LTNode* newnode = BuyNewNode(x);
LTNode* tail = phead->prev;
tail->next = newnode;
newnode->prev = tail;
newnode->next = phead;
phead->prev = newnode;
}
帶頭雙向循環(huán)鏈表刪除函數(shù)
指定結點刪除
刪除指定結點，配合STFInd使用，將指定節(jié)點前一個結點的next連接到指定結點后一個結點，再將指定結點后面結點的prev連接到指定指定結點前一個結點。
void ListErase(LTNode* pos)
{
assert(pos);
LTNode* prev = pos->prev;
LTNode* next = pos->next;
prev->next = next;
next->prev = prev;
free(pos);
}
頭刪
記得進行斷言，當只有一個哨兵位時與頭結點為空都無法進行刪除
可以對STErase進行復用
void ListPopFront(LTNode* phead)
{
assert(phead);
assert(phead != phead->next);
//第一種方法
//ListErase(phead->next);
//第二種
LTNode* secound = phead->next;
phead->next = secound->next;
secound->next->prev = phead;
free(secound);
}
尾刪
void ListPopBack(LTNode* phead)
{
assert(phead);
assert(phead != phead->next);
//第一種方法
//ListErase(phead->prev);
//第二種方法
LTNode* tail = phead->prev;
phead->prev = tail->prev;
tail->prev->next = phead;
free(tail);
}
帶頭雙向循環(huán)鏈表修改函數(shù)
配合LTFind函數(shù)使用
LTNode* LTFind(LTNode* phead, DListDataType x)
{
assert(phead);
LTNode* cur = phead->next;
while (cur)
{
if (cur->data == x)
{
return cur;
}
cur = cur->next;
}
return NULL;
}
LTNode* LTModify(LTNode* phead, DListDataType x)
{
LTNode* pos = LTFind(phead, x);
int y;
scanf("%d", &y);
pos->data = y;
}
銷毀帶頭雙向循環(huán)鏈表
將每個結點依次釋放。最后將哨兵位釋放。
void LTDestory(LTNode* phead)
{
assert(phead);
LTNode* cur = phead->next;
while (cur!=phead)
{
LTNode* next = cur->next;
free(cur);
cur = next;
}
free(phead);
}
源代碼文件
????為了使代碼更有閱讀性，我們不建議把所有函數(shù)寫在一個文件里，所以這里分成三個文件，模塊化管理
test.c
測試文件
#include "DList.h"
void test1()
{
LTNode* Phead = InitLTNode();
ListPushBack(Phead, 666);
ListPushBack(Phead, 777);
ListPushBack(Phead, 9999);
ListPushBack(Phead, 888);
print(Phead);
ListPopBack(Phead);
print(Phead);
ListPopFront(Phead);
print(Phead);
ListPopFront(Phead);
ListPopFront(Phead);
print(Phead);
ListPushFront(Phead,111);
print(Phead);
ListPushFront(Phead, 112);
print(Phead);
LTDestory(Phead);
Phead = NULL;
}
int main()
{
test1();
}
DList.c
i將所有函數(shù)封裝在此文件下
#include "DList.h"
LTNode* BuyNewNode(DListDataType x)
{
LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));
if (newnode == NULL)
{
perror("malloc");
return NULL;
}
newnode->next = NULL;
newnode->prev = NULL;
newnode->data = x;
return newnode;
}
LTNode* InitLTNode()
{
LTNode* phead = BuyNewNode(-1);
phead->next = phead;
phead->prev = phead;
return phead;
}
void ListInsert(LTNode* pos,DListDataType x)
{
assert(pos);
LTNode* newnode = BuyNewNode(x);
LTNode* prev = pos->prev;
prev->next = newnode;
newnode->prev = prev;
newnode->next = pos;
pos->prev = newnode;
}
void ListPushBack(LTNode* phead, DListDataType x)
{
//ListInsert(phead,x);
assert(phead);
LTNode* newnode = BuyNewNode(x);
LTNode* tail = phead->prev;
tail->next = newnode;
newnode->prev = tail;
newnode->next = phead;
phead->prev = newnode;
}
void ListPushFront(LTNode* phead, DListDataType x)
{
//ListInsert(phead->next,x);
assert(phead);
LTNode* newnode = BuyNewNode(x);
LTNode* secound = phead->next;
newnode->next = secound;
secound->prev = newnode;
phead->next = newnode;
newnode->prev = phead;
}
void ListErase(LTNode* pos)
{
assert(pos);
LTNode* prev = pos->prev;
LTNode* next = pos->next;
prev->next = next;
next->prev = prev;
free(pos);
}
void ListPopBack(LTNode* phead)
{
//ListErase(phead->prev);
assert(phead);
assert(phead != phead->next);
LTNode* tail = phead->prev;
phead->prev = tail->prev;
tail->prev->next = phead;
free(tail);
}
void ListPopFront(LTNode* phead)
{
assert(phead);
assert(phead != phead->next);
//ListErase(phead->next);
LTNode* secound = phead->next;
phead->next = secound->next;
secound->next->prev = phead;
free(secound);
}
void print(LTNode* phead)
{
assert(phead);
LTNode* cur = phead->next;
printf("head");
while (cur!=phead)
{
printf("->%d", cur->data);
cur = cur->next;
}
printf("\n");
}
LTNode* LTFind(LTNode* phead, DListDataType x)
{
assert(phead);
LTNode* cur = phead->next;
while (cur)
{
if (cur->data == x)
{
return cur;
}
cur = cur->next;
}
return NULL;
}
LTNode* LTModify(LTNode* phead, DListDataType x)
{
LTNode* pos = LTFind(phead, x);
int y;
scanf("%d", &y);
pos->data = y;
}
void LTDestory(LTNode* phead)
{
assert(phead);
LTNode* cur = phead->next;
while (cur!=phead)
{
LTNode* next = cur->next;
free(cur);
cur = next;
}
free(phead);
}
DLlist.h
將主程序所需要的函數(shù)全部在頭文件中聲明，增加代碼閱讀性文章來源：http://www.zghlxwxcb.cn/news/detail-438244.html
#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
#include <malloc.h>
#include <assert.h>
typedef int DListDataType;
typedef struct ListNode
{
DListDataType data;
struct ListNode* prev;
struct ListNode* next;
}LTNode;
LTNode* InitLTNode();
void ListInsert(LTNode* pos, DListDataType x);
void ListPushBack(LTNode* phead, DListDataType x);
void ListPushFront(LTNode* phead, DListDataType x);
void print(LTNode* phead);
void ListErase(LTNode* pos);
void ListPopBack(LTNode* phead);
void ListPopFront(LTNode* phead);
LTNode* LTModify(LTNode* phead, DListDataType x);
LTNode* LTFind(LTNode* phead, DListDataType x);
void LTDestory(LTNode* phead);
撒花
這就是實現(xiàn)帶頭雙向循環(huán)鏈表的全部內(nèi)容了，創(chuàng)作不易，還請各位小伙伴多多點贊??關注收藏?，以后也會更新各種關于c語言，數(shù)據(jù)結構的博客，撒花！文章來源地址http://www.zghlxwxcb.cn/news/detail-438244.html
到了這里，關于【數(shù)據(jù)結構】線性表——帶頭雙向循環(huán)鏈表的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關文章，希望大家以后多多支持TOY模板網(wǎng)！
