网站设计尺寸规范,深圳做网站便宜,wordpress通知插件,惠州谷歌优化目录
前言
1.双向链表的定义
2.双向链表的表示和实现
1.定义
2.初始化
3.销毁
4.清空
5.表长
6.获取数据元素
7.前驱节点
8.后继节点
9.插入
10.删除
11.遍历
12.完整代码 前言 记录下双向链表的表示和实现。
1.循环链表的定义 循环链表(circular linked list)…目录
前言
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个数据元素为elementendl;}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]后继节点为nextElementendl;}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]前驱节点为priorElementendl;}else{cout数据元素priorArr[i]前驱节点不存在endl;}}cout\n**********\t循环链表销毁\t**********endl;destroyCircularLinkedList(circularLinkedList);cout循环链表销毁endl;}
