5、数据结构——简单的线性表——循环链表（四）

一、循环单链表

定义

image-20240215164126690

结构体定义 + 循环单链表初始化……

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
typedef struct LNode{
	ElemType data;
	struct LNode *next;
}LNode,*LinkList;

bool InitList (LinkList &L) {
    L = (LNode *)malloc (sizeof LNode);
    if (L == NULL) return false;
    L -> next = L; // 头结点指向头结点
    return false;	
}

bool Empty(LinkList &L) {
    return L->next == L;
}

bool isTail(LinkList L, LNode *p) {
    return p -> next == L;
}

与单链表的不同

​ 循环单链表从一个结点触发可以找到其他任何一个结点

其他操作就不废话了……

二、循环双链表

定义

image-20240215165409956

结构体定义 + 循环双链表的初始化……

1
2
3
4
5
6
7
8
9
10
11
12
typedef struct DNode {
    ElemType data;
    struct LNode *prior, *next;
}DNode, *DNodeList;

bool InitDLinkList (DLinkList &L) {
    L = (DNode *)malloc (sizeof DNode);
    if (L == NULL) return false;
    L -> prior = L;
    L -> next = L;
    return true;
}
image-20240215165757019

循环双链表的插入

1
2
3
4
5
6
bool InsertNextNode (DNode *p, DNode *s) {
    s -> next = p -> next;
    p -> next -> prior = s;
    s -> prior = p;
    p -> next = s;
}

循环双链表的删除

1
2
3
4
5
6
7
bool DeleteNextNode (DNode *p) {
    q = p -> next;
	p -> next = q -> next;    
    q -> next-prior = p;
    free(p);
}

image-20240215171503983

下一节内容是：6、简单的线性表——静态链表！！！

一定要把本节内容看懂再往下看，不然会非常痛苦的哦o(╥﹏╥)oo(╥﹏╥)oo(╥﹏╥)o……..