網(wǎng)站首頁(yè) 編程語(yǔ)言 正文
一、概念與結(jié)構(gòu)
無(wú)頭單向非循環(huán)鏈表結(jié)構(gòu)簡(jiǎn)單，一般不會(huì)單獨(dú)用來(lái)存數(shù)據(jù)。實(shí)際中更多的是作為其他數(shù)據(jù)結(jié)構(gòu)的子結(jié)構(gòu)，如哈希桶、圖的鄰接表等等。而帶頭雙向循環(huán)鏈表的結(jié)構(gòu)較為復(fù)雜，一般用在單獨(dú)存儲(chǔ)數(shù)據(jù)。實(shí)際中使用的鏈表數(shù)據(jù)結(jié)構(gòu)，都是帶頭雙向循環(huán)鏈表，雖然它的結(jié)構(gòu)復(fù)雜但是因?yàn)榻Y(jié)構(gòu)優(yōu)勢(shì)用代碼實(shí)現(xiàn)起來(lái)會(huì)變得簡(jiǎn)單。
二、基本操作的實(shí)現(xiàn)
1.創(chuàng)建結(jié)點(diǎn)
LTNode* BuyListNode(ListDataType x)
{
LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));
if (newnode == NULL)
{
perror("malloc");
exit(-1);
}
newnode->val = x;
newnode->prev = NULL;
newnode->next = NULL;
return newnode;
}
2.初始化鏈表
void ListInit(LTNode** pphead)//初始化
{
*pphead = (LTNode*)malloc(sizeof(LTNode));
*pphead = BuyListNode(-1);
(*pphead)->next = *pphead;
(*pphead)->prev = *pphead;
}
//LTNode* ListInit()//初始化
//{
// LTNode* phead = BuyListNode(-1);//初始化時(shí)將頭結(jié)點(diǎn)置為-1;
// phead->next = phead;
// phead->prev = phead;
// return phead;
//}
初始化鏈表有兩種方式，一種是有返回類型（注釋部分），另一種是在初始化函數(shù)中給結(jié)構(gòu)體開辟空間（不過注意參數(shù)要為二級(jí)指針）。因?yàn)槭菐ь^結(jié)點(diǎn)的循環(huán)鏈表，所以prev和next指針都指向自己。
3.打印鏈表
void ListPrint(LTNode* phead)//打印
{
assert(phead);
LTNode* cur = phead->next;
while (cur != phead)
{
printf("%d ", cur->val);
cur = cur->next;
}
printf("\n");
}
注意while循環(huán)的結(jié)束條件，保證能夠打印鏈表中的所有有效值。要對(duì)頭結(jié)點(diǎn)進(jìn)行assert判斷，不能為空。
4.尾插
void ListPushBack(LTNode* phead, ListDataType x)//尾插
{
assert(phead);
LTNode* newnode = BuyListNode(x);
LTNode* tail = phead->prev;
newnode->next = tail->next;
phead->prev = newnode;
newnode->prev = tail;
tail->next = newnode;
//ListInsert(phead, x);
}
5.尾刪
void ListPopBack(LTNode* phead)//尾刪
{
assert(phead);
assert(phead->next != phead);
LTNode* prevnode = phead->prev;
prevnode->prev->next = phead;
phead->prev = prevnode->prev;
free(prevnode);
//ListErase(phead->prev);
}
尾刪時(shí)要注意判斷phead->next != phead，不能刪除頭結(jié)點(diǎn)，同時(shí)記得要free(prevnode)釋放刪除后的空間。
6.頭插
void ListPushFront(LTNode* phead, ListDataType x)//頭插
{
assert(phead);
LTNode* tail = phead->next;
LTNode* newnode = BuyListNode(x);
tail->prev = newnode;
newnode->next = tail;
newnode->prev = phead;
phead->next = newnode;
//ListInsert(phead->next,x);
}
7.頭刪
void ListPopFront(LTNode* phead)//頭刪
{
assert(phead);
assert(phead->next != phead);
LTNode* tail = phead->next;
phead->next = tail->next;
tail->next->prev = phead;
//ListErase(phead->next);
}
8.查找某個(gè)數(shù)并返回其指針
LTNode* ListFind(LTNode* phead, ListDataType x)//找某個(gè)數(shù)返回其指針
{
assert(phead);
LTNode* cur = phead->next;
while (cur != phead)
{
if (cur->val == x)
{
return cur;
}
cur = cur->next;
}
return NULL;
}
9.在某個(gè)位置之前插入
void ListInsert(LTNode* pos, ListDataType x)//在pos之前插入
{
assert(pos);
LTNode* newnode = BuyListNode(x);
LTNode* tail = pos->prev;
tail->next = newnode;
newnode->prev = tail;
newnode->next = pos;
pos->prev = newnode;
}
10.刪除某個(gè)位置
void ListErase(LTNode* pos)//刪除pos位置
{
assert(pos);
LTNode* prevnode = pos->prev;
LTNode* nextnode = pos->next;
free(pos);
prevnode->next = nextnode;
nextnode->prev = prevnode;
/*pos->next->prev = pos->prev;
pos->prev->next = pos->next;
free(pos);*/
}
11.判斷鏈表是否為空
bool ListEmpty(LTNode* phead)//判斷是否為空,如果是空，返回true
{
assert(phead);
return phead->next == phead;
}
12.計(jì)算鏈表中有效值的個(gè)數(shù)
size_t ListSize(LTNode* phead)//計(jì)算鏈表中有效值的個(gè)數(shù)
{
assert(phead);
size_t size = 0;
LTNode* tail = phead->next;
while (tail != phead)
{
size++;
tail = tail->next;
}
return size;
}
13.銷毀鏈表
void ListDestroy(LTNode* phead)//銷毀鏈表
{
assert(phead);
LTNode* tail = phead->next;
while (tail != phead)
{
LTNode* nextnode = tail->next;
free(tail);
tail = nextnode;
}
free(phead);
}
銷毀鏈表時(shí)要注意要保證每個(gè)結(jié)點(diǎn)都釋放，同時(shí)最后也要將頭結(jié)點(diǎn)釋放free(phead)。
三、測(cè)試代碼
#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <assert.h>
typedef int ListDataType;
typedef struct ListNode {
ListDataType val;
struct ListNode* prev;
struct ListNode* next;
}LTNode;
LTNode* BuyListNode(ListDataType x)
{
LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));
if (newnode == NULL)
{
perror("malloc");
exit(-1);
}
newnode->val = x;
newnode->prev = NULL;
newnode->next = NULL;
return newnode;
}
void ListInit(LTNode** pphead)//初始化
{
*pphead = (LTNode*)malloc(sizeof(LTNode));
*pphead = BuyListNode(-1);
(*pphead)->next = *pphead;
(*pphead)->prev = *pphead;
}
//LTNode* ListInit()//初始化
//{
// LTNode* phead = BuyListNode(-1);//初始化時(shí)將頭結(jié)點(diǎn)置為-1;
// phead->next = phead;
// phead->prev = phead;
// return phead;
//}
void ListPrint(LTNode* phead)//打印
{
assert(phead);
LTNode* cur = phead->next;
while (cur != phead)
{
printf("%d ", cur->val);
cur = cur->next;
}
printf("\n");
}
void ListPushBack(LTNode* phead, ListDataType x)//尾插
{
assert(phead);
LTNode* newnode = BuyListNode(x);
LTNode* tail = phead->prev;
newnode->next = tail->next;
phead->prev = newnode;
newnode->prev = tail;
tail->next = newnode;
//ListInsert(phead, x);
}
void ListPopBack(LTNode* phead)//尾刪
{
assert(phead);
assert(phead->next != phead);
LTNode* prevnode = phead->prev;
prevnode->prev->next = phead;
phead->prev = prevnode->prev;
free(prevnode);
//ListErase(phead->prev);
}
void ListPushFront(LTNode* phead, ListDataType x)//頭插
{
assert(phead);
LTNode* tail = phead->next;
LTNode* newnode = BuyListNode(x);
tail->prev = newnode;
newnode->next = tail;
newnode->prev = phead;
phead->next = newnode;
//ListInsert(phead->next,x);
}
void ListPopFront(LTNode* phead)//頭刪
{
assert(phead);
assert(phead->next != phead);
LTNode* tail = phead->next;
phead->next = tail->next;
tail->next->prev = phead;
//ListErase(phead->next);
}
LTNode* ListFind(LTNode* phead, ListDataType x)//找某個(gè)數(shù)返回其指針
{
assert(phead);
LTNode* cur = phead->next;
while (cur != phead)
{
if (cur->val == x)
{
return cur;
}
cur = cur->next;
}
return NULL;
}
void ListInsert(LTNode* pos, ListDataType x)//在pos之前插入
{
assert(pos);
LTNode* newnode = BuyListNode(x);
LTNode* tail = pos->prev;
tail->next = newnode;
newnode->prev = tail;
newnode->next = pos;
pos->prev = newnode;
}
void ListErase(LTNode* pos)//刪除pos位置
{
assert(pos);
LTNode* prevnode = pos->prev;
LTNode* nextnode = pos->next;
free(pos);
prevnode->next = nextnode;
nextnode->prev = prevnode;
/*pos->next->prev = pos->prev;
pos->prev->next = pos->next;
free(pos);*/
}
bool ListEmpty(LTNode* phead)//判斷是否為空,如果是空，返回true
{
assert(phead);
return phead->next == phead;
}
size_t ListSize(LTNode* phead)//計(jì)算鏈表中有效值的個(gè)數(shù)
{
assert(phead);
size_t size = 0;
LTNode* tail = phead->next;
while (tail != phead)
{
size++;
tail = tail->next;
}
return size;
}
void ListDestroy(LTNode* phead)//銷毀鏈表
{
assert(phead);
LTNode* tail = phead->next;
while (tail != phead)
{
LTNode* nextnode = tail->next;
free(tail);
tail = nextnode;
}
free(phead);
}
void TestList()
{
//LTNode* plist = ListInit(&plist);
LTNode* plist = NULL;
ListInit(&plist);
ListPushBack(plist, 100);
ListPushBack(plist, 200);
ListPushBack(plist, 300);
ListPushBack(plist, 400);
ListPushBack(plist, 500);
ListPopBack(plist);
ListPopBack(plist);
ListPopBack(plist);
ListPrint(plist);
ListPushFront(plist, 1000);
ListPushFront(plist, 2000);
ListPushFront(plist, 3000);
ListPopFront(plist);
ListPopFront(plist);
ListPrint(plist);
LTNode* pos = ListFind(plist, 1000);
if (pos != NULL)
{
ListInsert(pos, 500);
ListErase(pos);
}
ListPrint(plist);
if (!ListEmpty(plist))
printf("%d\n", ListSize(plist));
}
int main()
{
TestList();
return 0;
}
原文鏈接：https://blog.csdn.net/weixin_53943591/article/details/127825693
相關(guān)推薦
- 2022-10-29 python使用正則表達(dá)式匹配反斜杠\遇到的問題_python
- 2022-11-23 詳解Android消息機(jī)制完整的執(zhí)行流程_Android
- 2022-07-11 Python利用xlrd?與?xlwt?模塊操作?Excel_python
- 2022-07-30 C語(yǔ)言數(shù)組長(zhǎng)度的計(jì)算方法實(shí)例總結(jié)(sizeof與strlen)_C 語(yǔ)言
- 2021-11-06 C/C++?Qt?StringListModel?字符串列表映射組件詳解_C 語(yǔ)言
- 2022-04-12 iOS?block的值捕獲與指針捕獲詳解_IOS
- 2022-10-19 python用opencv將標(biāo)注提取畫框到對(duì)應(yīng)的圖像中_python
- 2023-01-08 Android?Application的使用全面解析_Android
- 最近更新
-
- window11 系統(tǒng)安裝 yarn
- 超詳細(xì)win安裝深度學(xué)習(xí)環(huán)境2025年最新版（
- Linux 中運(yùn)行的top命令 怎么退出？
- MySQL 中decimal 的用法？ 存儲(chǔ)小
- get 、set 、toString 方法的使
- @Resource和 @Autowired注解
- Java基礎(chǔ)操作-- 運(yùn)算符，流程控制 Flo
- 1. Int 和Integer 的區(qū)別，Jav
- spring @retryable不生效的一種
- Spring Security之認(rèn)證信息的處理
- Spring Security之認(rèn)證過濾器
- Spring Security概述快速入門
- Spring Security之配置體系
- 【SpringBoot】SpringCache
- Spring Security之基于方法配置權(quán)
- redisson分布式鎖中waittime的設(shè)
- maven:解決release錯(cuò)誤：Artif
- restTemplate使用總結(jié)
- Spring Security之安全異常處理
- MybatisPlus優(yōu)雅實(shí)現(xiàn)加密？
- Spring ioc容器與Bean的生命周期。
- 【探索SpringCloud】服務(wù)發(fā)現(xiàn)-Nac
- Spring Security之基于HttpR
- Redis 底層數(shù)據(jù)結(jié)構(gòu)-簡(jiǎn)單動(dòng)態(tài)字符串（SD
- arthas操作spring被代理目標(biāo)對(duì)象命令
- Spring中的單例模式應(yīng)用詳解
- 聊聊消息隊(duì)列，發(fā)送消息的4種方式
- bootspring第三方資源配置管理
- GIT同步修改后的遠(yuǎn)程分支
提供CDN加速