赞
踩
链表的结构非常多样,以下情况组合起来就有八种(2×2×2)链表结构:
虽然有这么多的链表的结构,但我们实际中最常用的还是两种结构:单链表和双向带头循环链表.
- 1、无头单向非循环链表:结构简单,一般不会单独用来存数据。实际中更多是作为其他数据结构的子结构,如哈希桶、图的邻接表等等。
- 2、带头双向循环链表:结构复杂,一般用在单独存储数据。实际中使用的链表数据结构,都是带头双向循环链表。另外这个结构虽然结构复杂,但是使用代码实现以后会发现结构会带来很多优势,实现反而简单,后面我们代码实现了就知道了。
- 注意:这⾥的“带头”跟前⾯我们说的“头结点”是两个概念,实际前⾯的在单链表阶段称呼不严谨.
带头链表中的头结点,实际为“哨兵位”,哨兵位结点补存储任何有效元素,只是站在这里“放哨的”
List.h文件中:
#pragma once #include<stdio.h> #include<stdlib.h> #include<assert.h> #include<stdbool.h> typedef int LTDateType; typedef struct ListNode { LTDateType date; struct ListNode* next;//存放下个节点的地址 struct ListNode* prev;//存放上一个结点的地址 }LT; //初始化哨兵位 void LTInit(LT** pphead); //初始化哨兵位,串一级指针更方便 LT* LTInit02(); //头插 void LTPushFornt(LT* phead,LTDateType x); //尾插 void LTPushBack(LT* phead,LTDateType x); //打印数据 void LTPrint(LT* phead); //头删 void LTPopFront(LT* phead); //尾删 void LTPopBack(LT* phead); //判断链表是否为空 bool LTEmpty(LT* phead); //返回数据所在结点 LT* LTFind(LT* phead, LTDateType x); //在pos结点之后插入数据 void LTInsert(LT* pos, LTDateType x); //删除pos结点的数据 void LTErase(LT* pos); //销毁结点 void LTDesTroy(LT** pphead); //穿一级指针销毁,需要手动置空 void LTDeaTroy02(LT* phead);
//开辟结点空间 LT* LTBuyNode(LTDateType x) { LT* newnode = (LT*)malloc(sizeof(LT)); if (newnode == NULL) { perror("malloc fail"); exit(1); } newnode->date = x; newnode->next = newnode; newnode->prev = newnode; } //初始化哨兵位 void LTInit(LT** pphead) { assert(pphead != NULL); *pphead = LTBuyNode(-1); } //初始化哨兵位,串一级指针更方便 LT* LTInit02() { LT* newnode = LTBuyNode(-1); return newnode; }
//头插
void LTPushFornt(LT* phead, LTDateType x)
{
assert(phead != NULL);
LT* newnode = LTBuyNode(x);
newnode->next = phead->next;
newnode->prev = phead;
phead->next->prev = newnode;
phead->next = newnode;
}
//判断链表是否为空
bool LTEmpty(LT* phead)
{
assert(phead != NULL);
return phead->prev == phead;
}
//打印数据
void LTPrint(LT* phead)
{
assert(phead != NULL);
LT* pcur = phead->next;
while (pcur != phead)
{
printf("%d->", pcur->date);
pcur = pcur->next;
}
printf("\n");
}
//尾插
void LTPushBack(LT* phead, LTDateType x)
{
assert(phead != NULL);
LT* newnode = LTBuyNode(x);
newnode->prev = phead->prev;
newnode->next = phead;
phead->prev->next = newnode;
phead->prev = newnode;
}
//头删
void LTPopFront(LT* phead)
{
assert(phead);
assert(!LTEmpty(phead));
LT* del = phead->next;
phead->next = del->next;
del->next->prev = phead;
free(del);
del = NULL;
}
//尾删
void LTPopBack(LT* phead)
{
assert(phead);
assert(!LTEmpty(phead));
LT* del = phead->prev;
phead->prev = del->prev;
del->prev->next = phead;
free(del);
del = NULL;
}
//返回数据所在结点
LT* LTFind(LT* phead, LTDateType x)
{
assert(phead);
LT* pcur = phead->next;
while (pcur != phead)
{
if (pcur->date == x)
{
return pcur;
}
pcur = pcur->next;
}
return NULL;
}
//在pos结点之后插入数据
void LTInsert(LT* pos, LTDateType x)
{
assert(pos != NULL);
LT* newnode = LTBuyNode(x);
newnode->next = pos->next;
newnode->prev = pos;
pos->next->prev = newnode;
pos->next = newnode;
}
//删除pos结点的数据
void LTErase(LT* pos)
{
assert(pos);
pos->next->prev = pos->prev;
pos->prev->next = pos->next;
free(pos);
pos = NULL;
}
//销毁结点 void LTDesTroy(LT** pphead) { assert(pphead); LT* pcur = (*pphead)->next; while (pcur != *pphead) { LT* next = pcur->next; free(pcur); pcur = next; } free(*pphead); *pphead = pcur = NULL; } //穿一级指针销毁,需要手动置空 void LTDeaTroy02(LT* phead) { assert(phead); LT* pcur = phead->next; while (pcur != phead) { LT* next = pcur->next; free(pcur); pcur = next; } free(phead); phead = pcur =NULL; }
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。