文章目录
总结归纳
- 在 DeleteNode 函数中（删除指定结点），如果删除的是最后一个结点，则要特殊处理，需要通过遍历找到该结点的前驱结点，再进行删除操作。
- 循环链表比起单链表，它的优势在于：知道一个结点，就可以知道该结点的前驱结点，以致于所有结点；而单链表必须通过头结点才能得到所有结点，否则无法通过已知结点得到前驱结点。
- 如果你需要频繁的对表头或者表尾操作，那么循环链表很适合，你只需要在表尾置一个尾指针，或者使用循环双链表。
代码实现
/*
循环单链表(带头结点)
*/
#include <iostream>
#include <string>
using namespace std;
struct LNode {
int data; // 数据域
LNode *next; // 指针域
};
typedef LNode LNode; // LNode是一个循环单链表的结点
typedef LNode *LinkList; // LinkList是一个循环单链表
// 初始化循环单链表
void InitList(LinkList &L) {
L = new LNode;
L->next = L;
}
// 判断循环单链表是否为空
bool Empty(LinkList &L) {
if (L->next == L) {
return true;
} else {
return false;
}
}
// 获取循环单链表长度
int GetLength(LinkList &L) {
LNode *p = L->next;
int length = 0;
while (p != L) {
p = p->next;
length++;
}
return length;
}
// 头插法建立循环单链表
LinkList List_HeadInsert(LinkList &L) {
int e;
cin >> e;
while (e != 9999) {
LNode *s = new LNode;
s->data = e;
s->next = L->next;
L->next = s;
cin >> e;
}
return L;
}
// 尾插法建立循环单链表
LinkList List_TailInsert(LinkList &L) {
LNode *r = L; // r为尾指针
int e;
cin >> e;
while (e != 9999) {
LNode *s = new LNode;
s->next = r->next;
s->data = e;
r->next = s;
r = s; // 将r置为新的尾指针
cin >> e;
}
r->next = L; // 尾指针的next置为L
return L;
}
// 按位查找：查找第i个结点
LNode *GetElem(LinkList &L, int i) {
if (i < 0) {
return NULL; // i值不合法
}
LNode *p = L;
int j = 0;
while (p->next != L && j < i) {
p = p->next;
j++;
}
return p;
}
// 按值查找：查找数据域为e的结点
LNode *GetLNode(LinkList &L, int e) {
LNode *p = L->next;
while (p != L && p->data != e) {
p = p->next;
}
return p;
}
// 查找指定结点的前一个结点
LNode *GetPriorNode(LinkList &L, LNode *p) {
LNode *s = L;
while (s->next != p) {
s = s->next;
}
return s;
}
// 查找最后一个结点
LNode *GetLastNode(LinkList &L) {
LNode *p = L->next;
while (p->next != L) {
p = p->next;
}
return p;
}
// 前插操作：在p结点之前插入数据e
bool InsertPriorNode(LNode *p, int e) {
LNode *s = new LNode;
s->next = p->next;
s->data = p->data; // 数据后移，模拟结点后移
p->next = s;
p->data = e; // 将前结点置为新插入的结点
return true;
}
// 后插操作：在p结点之后插入数据e
bool InsertNextNode(LNode *p, int e) {
LNode *q = new LNode;
q->data = e;
q->next = p->next;
p->next = q;
return true;
}
// 按位序插入
bool InserstList(LinkList &L, int i, int e) {
if (i < 1) { // i值不合法
return false;
}
// LNode *p = GetElem(L, i - 1); // 遍历查找i-1个结点
// InsertNextNode(p, 5244); // 使用后插法
// 使用前插法，达到同样效果
LNode *p = GetElem(L, i);
InsertPriorNode(p, 5244);
return true;
}
// 删除指定结点
bool DeleteNode(LinkList &L, LNode *p) {
if (p == L) {
return false;
}
if (p->next == L) { // 要删除最后一个结点
LNode *s = GetPriorNode(L, p); // s为p的前驱结点
s->next = p->next;
delete p;
} else {
LNode *s = new LNode;
s = p->next; // 指向被删除结点的后继节点
p->data = s->data; // 数据前移，模拟结点前移
p->next = s->next; // 断开与被删除结点的联系
delete s;
}
return true;
}
// 删除p结点的后继结点
bool DeleteNextLNode(LinkList &L, LNode *p) {
if (p == NULL || p->next == L) {
return false;
}
LNode *s = new LNode;
s = p->next;
p->next = s->next;
delete s;
return true;
}
// 按位序删除
bool ListDelte(LinkList &L, int i, int &e) {
if (i < 1) {
return false;
}
/* // 按结点删除，实现同样效果
LNode *p = GetElem(L, i); // 被删除结点
e = p->data;
DeleteNode(L, p);
*/
LNode *p = GetElem(L, i - 1);
e = p->next->data;
DeleteNextLNode(L, p);
return true;
}
// 遍历循环单链表
void TraverseList(LinkList &L) {
if (L->next == L) {
return;
}
LNode *p = L->next; // 指向头指针
while (p != L) {
cout << p->data << " ";
p = p->next;
}
cout << endl;
}
int main() {
LinkList L;
InitList(L);
cout << Empty(L) << endl;
// List_HeadInsert(L); // 头插法
List_TailInsert(L); // 尾插法
TraverseList(L);
InserstList(L, 3, 5244);
TraverseList(L);
cout << "长度：" << GetLength << endl;
int e = -1;
ListDelte(L, 6, e);
cout << "被删除的值：" << e << endl;
TraverseList(L);
cout << GetElem(L, 5)->next->next->data << endl; // 验证循环链表的效果
}