数据结构与算法学习笔记之线性表五---循环链表的表示和实现(C++)

目录

前言

1.双向链表的定义

2.双向链表的表示和实现

1.定义

2.初始化

3.销毁

4.清空

5.表长

6.获取数据元素

7.前驱节点

8.后继节点

9.插入

10.删除

11.遍历

12.完整代码

---

前言

        记录下双向链表的表示和实现。

1.循环链表的定义

        循环链表(circular linked list)是另一种形式的链式存储结构。它的特点是表中最后一个结点的指针域指向头结点,整个链表形成一个环。由此,从表中任一结点出发均可找到表中其他结点,如图 2.12所示为单链的循环链表。类似地,还可以有多重链的循环链表。。

2.循环链表的表示和实现

1.定义

typedef int Status;
typedef int ElemType;
// 定义循环链表
typedef struct CircularNode {ElemType data; // 数据域struct CircularNode * next; // 直接后继
}CircularNode,*CircularLinkedList;

2.初始化

        初始化双向链表，next指针指向自己。

// 初始化循环链表
Status initCircularLinkedList(CircularLinkedList &circularLinkedList){circularLinkedList = new CircularNode;if (!circularLinkedList) {//内存分配失败return 0;}circularLinkedList->next = circularLinkedList; // 将头节点的指针指向自身，形成循环return 1;
}

3.销毁

// 循环链表销毁
void destroyCircularLinkedList(CircularLinkedList &circularLinkedList) {if (!circularLinkedList) {return; // 链表为空，无需销毁}CircularLinkedList current = circularLinkedList->next; // 从第一个节点开始while (current != circularLinkedList) { // 遍历至头节点CircularLinkedList temp = current; // 暂存当前节点current = current->next; // 移动到下一个节点delete temp; // 释放当前节点内存}delete circularLinkedList; // 释放头节点内存circularLinkedList = nullptr; // 头指针置为空
}

4.清空

// 循环链表清空
void clearCircularLinkedList(CircularLinkedList &circularLinkedList) {if (!circularLinkedList) {return; // 链表为空，无需清空}CircularLinkedList current = circularLinkedList->next; // 从第一个节点开始while (current != circularLinkedList) { // 遍历至头节点CircularLinkedList temp = current; // 暂存当前节点current = current->next; // 移动到下一个节点delete temp; // 释放当前节点内存}circularLinkedList->next = circularLinkedList; // 头节点的 next 指针指向自身，链表置为空链表
}

5.表长

// 循环链表表长
int getCircularLinkedListLength(CircularLinkedList &circularLinkedList) {int length = 0;CircularNode *p = circularLinkedList->next; // 从第一个节点开始计数while (p != circularLinkedList) { // 当指针指向头节点时结束循环++length;p = p->next;}return length;
}

6.获取数据元素

// 获取循环链表中的元素
Status getCircularLinkedListElement(CircularLinkedList &circularLinkedList, int position, int *element) {if (position < 1 || position > getCircularLinkedListLength(circularLinkedList)) { // 非法位置return 0;}CircularNode *p = circularLinkedList->next; // 从第一个节点开始遍历int index = 1;while (index < position) { // 定位到指定位置p = p->next;index++;}*element = p->data; // 将节点的数据域值赋给 elementreturn 1;
}

7.前驱节点

// 获取循环链表中的第一个与element相同的元素的直接前驱
Status priorCircularLinkedListElement(CircularLinkedList &circularLinkedList, int element, int *priorElement) {if (isCircularLinkedListEmpty(circularLinkedList)) { // 空链表return 0;}CircularNode *p = circularLinkedList->next;CircularNode *pre = circularLinkedList; // 前驱节点do {if (p->data == element) { // 找到要查找的节点*priorElement = pre->data;return 1;}pre = p;p = p->next;} while (p != circularLinkedList->next); // 循环直到回到起始节点return 0; // 未找到相同元素
}

8.后继节点

        先判断循环链表是否是空链表，然后遍历删除节点。

// 获取循环链表中的第一个与element相同的元素的后继节点
Status nextCircularLinkedListElement(CircularLinkedList &circularLinkedList, int element, int *nextElement) {if (isCircularLinkedListEmpty(circularLinkedList)) { // 空链表return 0;}CircularNode *p = circularLinkedList->next;do {if (p->data == element) { // 找到要查找的节点*nextElement = p->next->data;return 1;}p = p->next;} while (p != circularLinkedList->next); // 循环直到回到起始节点return 0; // 未找到相同元素
}

9.插入

         首先判断插入位置是否合法，然后分别处理头结点和非头结点的情况。

// 循环链表插入
Status insertCircularLinkedList(CircularLinkedList &circularLinkedList, int i, int element) {if (i < 1) { // 插入位置非法return 0;}CircularNode *newNode = new CircularNode; // 新节点if (!newNode) { // 内存分配失败return 0;}newNode->data = element;if (i == 1) { // 插入到表头if (circularLinkedList == nullptr) { // 空链表newNode->next = newNode; // 自己指向自己circularLinkedList = newNode;} else {CircularNode *last = circularLinkedList;while (last->next != circularLinkedList) { // 找到最后一个节点last = last->next;}newNode->next = circularLinkedList; // 新节点指向表头last->next = newNode; // 最后一个节点指向新节点circularLinkedList = newNode; // 更新表头指针}} else { // 插入到非表头位置CircularNode *p = circularLinkedList;int j = 1;while (p->next != circularLinkedList && j < i - 1) { // 找到插入位置的前一个节点p = p->next;++j;}if (j < i - 1) { // 插入位置超出链表长度delete newNode;return 0;}newNode->next = p->next; // 新节点指向原来位置节点p->next = newNode; // 前一个节点指向新节点}return 1;
}

10.删除

        首先判断删除位置是否合法，然后分别处理头结点和非头结点的情况。

// 循环链表删除
Status deleteCircularLinkedList(CircularLinkedList &circularLinkedList, int position, ElemType *deletedElement) {if (position < 1 || circularLinkedList == nullptr) { // 删除位置非法或链表为空return 0;}if (position == 1) { // 删除表头节点CircularNode *temp = circularLinkedList;*deletedElement = temp->data; // 存储被删除节点的数据if (circularLinkedList->next == circularLinkedList) { // 链表只有一个节点delete temp;circularLinkedList = nullptr;} else {CircularNode *last = circularLinkedList;while (last->next != circularLinkedList) { // 找到最后一个节点last = last->next;}last->next = circularLinkedList->next; // 最后一个节点指向第二个节点circularLinkedList = circularLinkedList->next; // 更新表头指针delete temp; // 释放被删除节点的内存}} else { // 删除非表头节点CircularNode *p = circularLinkedList;int j = 1;while (p->next != circularLinkedList && j < position - 1) { // 找到要删除节点的前一个节点p = p->next;++j;}if (j < position - 1 || p->next == circularLinkedList) { // 删除位置超出范围return 0;}CircularNode *temp = p->next; // 要删除的节点*deletedElement = temp->data; // 存储被删除节点的数据p->next = temp->next; // 前一个节点指向后一个节点delete temp; // 释放被删除节点的内存}return 1;
}

11.遍历

        遍历循环链表

// 遍历循环链表
void traverseCircularLinkedList(CircularLinkedList &circularLinkedList) {if (circularLinkedList == nullptr) { // 空链表return;}CircularNode *p = circularLinkedList;do {cout << p->data << "\t"; // 输出当前节点的数据p = p->next; // 移动到下一个节点} while (p != circularLinkedList); // 循环直到回到起始节点cout << endl;
}

12.测试代码

void  testCircularLinkedList(void) {CircularLinkedList circularLinkedList;cout<<"\n**********\t循环链表初始化\t**********"<<endl;if (initCircularLinkedList(circularLinkedList)) {cout<<"顺序表初始化成功"<<endl;}cout<<"\n**********\t循环链表判空和长度计算\t**********"<<endl;if (isCircularLinkedListEmpty(circularLinkedList)) {cout<<"循环链表为空,长度为"<<getCircularLinkedListLength(circularLinkedList)<<endl;}cout<<"\n**********\t循环链表插入测试\t**********"<<endl;for (int i = 1; i <=11 ; i++) {if (insertCircularLinkedList(circularLinkedList,i, i)) {cout<<"数据元素"<<i<<"插入成功"<<endl;}else{cout<<"数据元素"<<i<<"插入失败"<<endl;}}traverseCircularLinkedList(circularLinkedList);cout<<"\n**********\t循环链表根据下标获取数据元素测试\t**********"<<endl;for (int i = 0; i <= 12 ; i++) {int element;if (getCircularLinkedListElement(circularLinkedList,i, &element)) {cout<<"第"<<i<<"个数据元素为"<<element<<endl;}else{cout<<"第"<<i<<"个数据元素不存在"<<endl;}}cout<<"插入之后的循环链表"<<endl;traverseCircularLinkedList(circularLinkedList);cout<<"\n**********\t循环链表删除测试\t**********"<<endl;ElemType element;if (deleteCircularLinkedList(circularLinkedList, 11, &element)){cout<<"数据元素"<<element<<"删除成功"<<endl;}cout<<"删除之后的循环链表"<<endl;traverseCircularLinkedList(circularLinkedList);cout<<"\n**********\t循环链表后继节点测试\t**********"<<endl;int nextArr[3] = {1,8,11};for (int i = 0; i < 3; i++) {ElemType nextElement;if (nextCircularLinkedListElement(circularLinkedList, nextArr[i], &nextElement)) {cout<<"数据元素"<<nextArr[i]<<"后继节点为："<<nextElement<<endl;}else{cout<<"数据元素"<<nextArr[i]<<"后继节点不存在"<<endl;}}cout<<"\n**********\t循环链表前驱节点测试\t**********"<<endl;int priorArr[3] = {8,11,1};for (int i = 0; i < 3; i++) {ElemType priorElement;if (priorCircularLinkedListElement(circularLinkedList, priorArr[i], &priorElement)) {cout<<"数据元素"<<priorArr[i]<<"前驱节点为"<<priorElement<<endl;}else{cout<<"数据元素"<<priorArr[i]<<"前驱节点不存在"<<endl;}}cout<<"\n**********\t循环链表销毁\t**********"<<endl;destroyCircularLinkedList(circularLinkedList);cout<<"循环链表销毁"<<endl;}