【数据结构初阶】双向带头循环链表原来是纸老虎,结构复杂,操作简单
2023-02-25 18:20:14 时间
目录
双向带头循环链表:结构复杂,操作简单
0.结构体定义
这里方便浏览,特地没有将int类型重命名为TLDateType
#define _CRT_SECURE_NO_WARNINGS 1
#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>
struct ListNode
{
int val;
struct ListNode* prev;
struct ListNode* next;
};
1.初始化
- 带头需要初始化一个哨兵位头结点
- 传二级指针
- 初始化自己的prev和next都指向自己
void ListInit(struct ListNode** pphead)
{
struct ListNode* Guard = (struct ListNode*)malloc(sizeof(struct ListNode));
if (Guard == NULL)
{
perror("ListInit");
return;
}
*pphead = Guard;
Guard->next = Guard;
Guard->prev = Guard;
}
2.尾插
- 一级指针
- 直接prev找尾
- 即是无首元结点,也可(头结点自环)
struct ListNode* BuyListNode(int x)
{
struct ListNode* newnode = (struct ListNode*)malloc(sizeof(struct ListNode));
if (newnode == NULL)
{
perror("BuySListNode");
return NULL;
}
newnode->val = x;
newnode->prev = NULL;
newnode->next = NULL;
return newnode;
}
void ListPushBack(struct ListNode* phead,int x)
{
assert(phead);
struct ListNode* newnode = BuyListNode(x);
struct ListNode* tail = phead->prev;
newnode->next = phead;
phead->prev = newnode;
tail->next = newnode;
newnode->prev = tail;
}
3.打印
- 可assert断言(建议单链表不用断言)---头结点
- 起始条件cur=phead->next;
- 循环终止条件cur==phead
void ListPrint(struct ListNode* phead)
{
assert(phead);
struct ListNode* cur = phead->next;
while (cur != phead)
{
printf("%d->", cur->val);
cur = cur->next;
}
printf("NULL\n");
}
4.头插
- 一级指针
- 即是无首元结点,也可(头结点自环)
void ListPushFront(struct ListNode* phead,int x)
{
assert(phead);
struct ListNode* newnode = BuyListNode(x);
struct ListNode* next = phead->next;
newnode->next = next;
next->prev = newnode;
phead->next = newnode;
newnode->prev = phead;
}
5.任意位置插入前面位置
- 因为有prev,前插不同phead
- 尾插,头插就用ListInsert传不同pos参数
- 如果pos传phead,就相当于于是尾插
- 如果pos传phead->next,就相当于于是头插
void ListInsert(struct ListNode* pos, int x)
{
assert(pos);
struct ListNode* newnode = BuyListNode(x);
struct ListNode* prev = pos->prev;
prev->next = newnode;
newnode->prev = prev;
newnode->next = pos;
pos->prev = newnode;
}
头插:ListNode(phead->next,x);
尾插:ListNode(phead,x);
6.尾删
- 不为空,!ListEmpty(plhead)
- prev,tail,phead
bool ListEmpty(struct ListNode* phead)
{
return phead->next == phead;
}
void ListPopBack(struct ListNode* phead)
{
assert(phead);
assert(!ListEmpty(phead));
struct ListNode* tail = phead->prev;
struct ListNode* prev = tail->prev;
prev->next = phead;
phead->prev = prev;
free(tail);
tail = NULL;
}
7.头删
- 不为空,!ListEmpty(plhead)
- phead,first,second
void ListPopFront(struct ListNode* phead)
{
assert(phead);
assert(!ListEmpty(phead));
struct ListNode* first = phead->next;
struct ListNode* second = first->next;
phead->next = second;
second->prev = phead;
free(first);
first = NULL;
}
8.链表长度
- 起始条件:cur=phead->next
- 终止条件:cur!=phead;
size_t ListSize(struct ListNode* phead)
{
size_t size = 0;
struct ListNode* cur = phead->next;
while (cur != phead)
{
++size;
cur = cur->next;
}
return size;
}
9.任意位置删除当前位置
- 不为空,!ListEmpty(plhead)
- 尾删,头删就用ListErase传不同pos参数
- 如果pos传phead->prev,就是尾删
- 如果pos传phead->next,就是头删
void ListErase(struct ListNode* pos)
{
assert(pos);
struct ListNode* prev = pos->prev;
struct ListNode* next = pos->next;
prev->next = next;
next->prev = prev;
free(pos);
pos = NULL;
}
10. 销毁
- 看是否保留哨兵头,来传一级或二级指针
- 先保留哨兵头作为判断循环条件,最后决定是否释放哨兵头
void ListDestory(struct ListNode** pphead)
{
assert(pphead);
struct ListNode* cur = (*pphead)->next;
while (cur != *pphead)
{
struct ListNode* next = cur->next;
free(cur);
cur = next;
}
free(*pphead);
*pphead = NULL;
}
制作不易,敬请三连
相关文章
- 叹息!GitHub Trending 即将成为历史!
- 微软软了?开源社区讨论炸锅,GitHub CEO 亲自来答
- GitHub Trending 列表频现重复项,前后端都没去重?
- Photoshop Elements 2021版本软件安装教程(mac+windows全版本都有)
- (ps全版本)Photoshop 2020的安装与破解教程(mac+windows全版本都有)
- (ps全版本)Photoshop cc2018的安装与破解教程(mac+windows全版本,包括2023
- 环境搭建:Oracle GoldenGate 大数据迁移到 Redshift/Flat file/Flume/Kafka测试流程
- 每个开发人员都要掌握的:最小 Linux 基础课
- 来撸羊毛了!Windows 环境下 Hexo 博客搭建,并部署到 GitHub Pages
- 超实用!手把手入门 MongoDB:这些坑点请一定远离
- 【GitHub日报】22-10-09 zustand、neovim、webtorrent、express 等4款App今日上新
- 【GitHub日报】22-10-10 brew、minio、vite、seaweedfs、dbeaver 等8款App今日上新
- 【GitHub日报】22-10-11 cobra、grafana、vue、ToolJet、redwood 等13款App今日上新
- Photoshop 2018 下载及安装教程(mac+windows全版本都有,包括最新的2023)
- Photoshop 2017 下载及安装教程(mac+windows全版本都有,包括最新的2023)
- Photoshop 2020 下载及安装教程(mac+windows全版本都有,包括最新的2023)
- Photoshop 2023 资源免费下载(mac+windows全版本都有,包括最新的2023)
- 最新版本Photoshop CC2018软件安装教程(mac+windows全版本都有,包括2023
- Mac OSX 安装 MongoDB
- Kali Linux 在VMware Workstation Pro上的安装