【王道数据结构】线性表的链式存储——循环单、双链表
作者:
Skuy
,
2023-03-20 23:26:46
,
所有人可见
,
阅读 195
#include <cstdio>
#include <stdlib.h>
typedef struct LNode {
int data;
struct LNode *next;
} LNode, *LinkList;
typedef struct DNode {
int data;
struct DNode *prior, *next;
} DNode, *DLinkList;
// 单链表从一个结点出发只能找到后续的各个结点,但是循环单链表从一个结点出发可以找到其他任何一个结点
// 初始化一个循环单链表
bool InitCirLinkList(LinkList &L)
{
L = (LNode *) malloc(sizeof(LNode));
if(L == NULL) return false;
L->next = L;
return true;
}
// 初始化一个循环双链表
bool InitCirDLinkList(DLinkList &L)
{
L = (DNode *) malloc(sizeof(DNode));
if (L == NULL) return false;
L->next = L;
L->prior = L;
return true;
}
// 循环单链表判空
bool isEmpty1(LinkList L)
{
if (L->next == L) return true;
else return false;
}
// 循环双链表判空
bool isEmpty2(DLinkList L)
{
if (L->next == L) return true;
else return false;
}
// 判断循环单链表的结点p是否为表尾结点
bool isTail1(LinkList L, LNode *p)
{
if (p->next == L) return true;
else return false;
}
// 判断循环双链表的结点p是否为表尾结点
bool isTail2(DLinkList L, DNode *p)
{
if (p->next == L) return true;
else return false;
}
// 在循环双链表的结点p后插入一个结点s 此时不要考虑表尾的特殊情况
bool InsertNextDNode(DLinkList L, DNode *p, DNode *s)
{
s->next = p->next;
s->prior = p;
p->next->prior = s;
p->next = s;
}
// 在循环双链表中删除结点p的后继结点 同样不需要考虑特殊情况
bool DeleteNextDNode(DLinkList L, DNode *p)
{
DNode *q = p->next;
p->next = q->next;
q->next->prior = p;
free(q);
return true;
}
void test()
{
LinkList L1;
InitCirLinkList(L1);
DLinkList L2;
InitCirDLinkList(L2);
}
int main()
{
test();
return 0;
}