学习贺老师数据结构
数据结构之自建算法库——循环单链表_循环单链表 csdn-CSDN博客
整理总结出的循环单链表算法库
v1.0 : 基本实现功能
v2.0(2024.4.6):
修复Delete_SpecificLocate_CyclicList()删除节点函数bug,添加验证删除节点是否超范围判断
目录
1.主要功能:
2. 循环链表头文件
3. 循环链表库函数
4. main.cpp测试函数
5. 运行展示:
V2.0
v1.0 bug复现
1.主要功能
2. 循环链表头文件
3. 循环链表库函数
4. main.cpp测试函数
5. 运行展示:
V1.0
1.主要功能:
//(1)头插法建立循环单链表 void Create_CyclicList_Head(singleLinkList_Cyclic *&L,ElemType Array_used[],int Array_number); //(2)尾插法建立单链表 void Create_CyclicList_Tail(singleLinkList_Cyclic *&L,ElemType Array_used[],int Array_number); //(3)输出循环单链表 void Display_CyclicList(singleLinkList_Cyclic *L); //(4)初始化循环单链表 void Init_CyclicList(singleLinkList_Cyclic *&L); //(5)销毁循环单链表 void Destroy_CyclicList(singleLinkList_Cyclic *&L); //(6)判断循环单链表是否为空 bool Empty_CyclicList(singleLinkList_Cyclic *L); //(7)求循环单链表数据元素个数(不包括头结点) int Length_CyclicList(singleLinkList_Cyclic *L); //(8) 查找特定元素值,在循环单链表中的位置 int SpecificValue_Location_CyclicList(singleLinkList_Cyclic *L, ElemType specific_value); //(9) 取出循环单链表中 特定位置的元素值 bool SpecificLocate_Value_CyclicList(singleLinkList_Cyclic *L, int specific_locate,ElemType &get_value); //(10) 把特定的节点值, 插入到循环单链表特定位置 bool InsertElement_CyclicList(singleLinkList_Cyclic *&L, int specific_locate, ElemType insert_value); //(11) 删除特定位置的节点值 bool Delete_SpecificLocate_CyclicList(singleLinkList_Cyclic *&L, int specific_locate, ElemType &delete_value);
2. 循环链表头文件
Cyclic_singleLinkList.h
#ifndef CYCLIC_SINGLELINKLIST_H_INCLUDE
#define CYCLIC_SINGLELINKLIST_H_INCLUDE
#include "stdio.h"
#include "malloc.h"
//循环单链表基本运算函数
typedef int ElemType;
typedef struct Cyclic_Node
{
ElemType data;
struct Cyclic_Node *next;
}singleLinkList_Cyclic;
//(1)头插法建立循环单链表
void Create_CyclicList_Head(singleLinkList_Cyclic *&L,ElemType Array_used[],int Array_number);
//(2)尾插法建立单链表
void Create_CyclicList_Tail(singleLinkList_Cyclic *&L,ElemType Array_used[],int Array_number);
//(3)输出循环单链表
void Display_CyclicList(singleLinkList_Cyclic *L);
//(4)初始化循环单链表
void Init_CyclicList(singleLinkList_Cyclic *&L);
//(5)销毁循环单链表
void Destroy_CyclicList(singleLinkList_Cyclic *&L);
//(6)判断循环单链表是否为空
bool Empty_CyclicList(singleLinkList_Cyclic *L);
//(7)求循环单链表数据元素个数(不包括头结点)
int Length_CyclicList(singleLinkList_Cyclic *L);
//(8) 查找特定元素值,在循环单链表中的位置
int SpecificValue_Location_CyclicList(singleLinkList_Cyclic *L, ElemType specific_value);
//(9) 取出循环单链表中 特定位置的元素值
bool SpecificLocate_Value_CyclicList(singleLinkList_Cyclic *L, int specific_locate,ElemType &get_value);
//(10) 把特定的节点值, 插入到循环单链表特定位置
bool InsertElement_CyclicList(singleLinkList_Cyclic *&L, int specific_locate, ElemType insert_value);
//(11) 删除特定位置的节点值
bool Delete_SpecificLocate_CyclicList(singleLinkList_Cyclic *&L, int specific_locate, ElemType &delete_value);
#endif //CYCLI_SINGLELINKLIST_H_INCLUDE
3. 循环链表库函数
Cyclic_singleLinkList.cpp
#include "Cyclic_singleLinkList.h"
/**************************************************
(1)函数名: Create_CyclicList_Head
功 能: 头插法建立循环单链表
参 数: (1)singleLinkList_Cyclic *&L: 要建立并传回去的循环单链表指针地址
(2)ElemType Array_used[]: 要使用的数组数据
(3)int Array_number: 数组的长度
注 意: ①我们是按照单链表方法建立,最后找到尾指针,再形成闭环
思 路: (1)创建头结点(2)头结点置空(3)根据数据创建新节点,并利用头插法插入(4)查找尾结点(5)形成闭环
返回值: 无
**************************************************/
void Create_CyclicList_Head(singleLinkList_Cyclic *&L,ElemType Array_used[],int Array_number)
{
int counter;
singleLinkList_Cyclic *newnode,*tailnode;
L = (singleLinkList_Cyclic*)malloc(sizeof(singleLinkList_Cyclic)); //创建头结点
L->next = NULL;
for(counter = 0; counter < Array_number; counter++)
{
newnode = (singleLinkList_Cyclic*)malloc(sizeof(singleLinkList_Cyclic)); //创建新节点
newnode->data = Array_used[counter];
newnode->next = L->next; //将newnode插在原开始结点之前,头结点之后
L->next = newnode;
}
tailnode = L;
while(tailnode->next != NULL) //①查找尾结点, 从而将其指向头结点
{
tailnode = tailnode->next;
}
tailnode->next = L; // 形成闭环
}
/**************************************************
(2)函数名: Create_CyclicList_Tail
功 能: 尾插法建立单链表
参 数: (1)singleLinkList_Cyclic *&L: 要建立并传回去的循环单链表指针地址
(2)ElemType Array_used[]: 要使用的数组数据
(3)int Array_number: 数组的长度
注 意: 我们是按照单链表建立的方法进行建立,最后尾指针指向头结点即可
思 路: (1)定义新节点,尾指针节点,数组遍历序号
(2)创建头结点,并置空后继指针
(3)按照数组顺序,新建节点,并利用尾插法插入链表尾部
(4)插入完成,尾指针指向头结点
返回值: 无
**************************************************/
void Create_CyclicList_Tail(singleLinkList_Cyclic *&L,ElemType Array_used[],int Array_number)
{
int counter;
singleLinkList_Cyclic *newNode,*tailNode;
L = (singleLinkList_Cyclic*)malloc(sizeof(singleLinkList_Cyclic));
L->next = NULL;
tailNode = L;
for(counter = 0; counter < Array_number; counter++)
{
newNode = (singleLinkList_Cyclic*)malloc(sizeof(singleLinkList_Cyclic));
newNode->data = Array_used[counter];
tailNode->next = newNode;
tailNode = newNode;
}
tailNode->next = L;
}
/**************************************************
(3)函数名: Display_CyclicList
功 能: 输出展示循环单链表
参 数:(1)singleLinkList_Cyclic *L:要展示的循环单链表
注 意:①因为是循环单链表,所以结束条件是, 指针指向头结点
思 路: (1)定义遍历节点(2)判断是否为空(L == L->next)(3)从数据节点开始遍历输出(4)不结束接着遍历输出
返回值: 无
**************************************************/
void Display_CyclicList(singleLinkList_Cyclic *L)
{
singleLinkList_Cyclic *showNode;
showNode = L->next;
if(showNode == L)
{
printf("hey, it is Empty!"); //为空,无法输出
}
while(showNode != L)//①
{
printf("%d",showNode->data);
printf(" ");
showNode = showNode->next;
}
printf("\n");
}
/**************************************************
(4)函数名: Init_CyclicList
功 能: 初始化循环单链表
参 数: singleLinkList_Cyclic *&L:要初始化的循环单链表指针地址
返回值: 无
**************************************************/
void Init_CyclicList(singleLinkList_Cyclic *&L)
{
L = (singleLinkList_Cyclic*)malloc(sizeof(singleLinkList_Cyclic));
L->next = L; //初始化头结点指向自己
}
/**************************************************
(5)函数名: Destroy_CyclicList
功 能: 释放循环单链表的节点空间,
参 数: singleLinkList_Cyclic *&L:要销毁的循环单链表
注 意: ①防止野指针被函数利用后, 飘飞
②防止遍历指针信息被删除后,找不到后继信息
③循环单链表,结束条件是 尾指针指向头结点
思 路: (1)定义遍历指针和后继指针(2)规划好nowNode和backNode关系
(3) nowNode遍历删除,backNode后移,直到backNode == L,退出
(4)接着释放nowNode,并且防止野指针飘飞,①
返回值: 无
**************************************************/
void Destroy_CyclicList(singleLinkList_Cyclic *&L)
{
singleLinkList_Cyclic *nowNode;
singleLinkList_Cyclic *backNode; //②
nowNode = L;
backNode = nowNode->next;
while(backNode != L) //③
{
free(nowNode);
nowNode = backNode;
backNode = backNode->next;
}
free(nowNode);
L->next = L; //①
}
/**************************************************
(6)函数名: Empty_CyclicList
功 能: 判断循环单链表是否为空
参 数: singleLinkList_Cyclic *L:要参与判断的循环单链表
返回值: bool:是否为空? true:false
**************************************************/
bool Empty_CyclicList(singleLinkList_Cyclic *L)
{
return (L->next == L);
}
/**************************************************
(7)函数名: Length_CyclicList
功 能: 求循环单链表数据元素个数(不包括头结点)
参 数: singleLinkList_Cyclic *L :要参与计算的循环单链表
注 意: ① 结束条件:尾指针指向头结点
返回值: int: 循环单链表数据元素个数
**************************************************/
int Length_CyclicList(singleLinkList_Cyclic *L)
{
int counter = 0;
singleLinkList_Cyclic *nowNode = L;
while(nowNode->next != L) //①
{
counter++;
nowNode = nowNode->next;
}
return counter;
}
/**************************************************
(8)函数名:SpecificValue_Location_CyclicList
功 能:找特定元素值,在循环单链表中的位置
参 数:(1)singleLinkList_Cyclic *L: 需要查找的循环单链表
(2)ElemType specific_value: 要查找的元素值
注 意: ① 从 L->next开始,即第一个数据元素开始查找,其位置counter伴随
②跳出有两种情况:1,找到 2,超范围指向头结点
返回值: int: 返回特定元素值的 位置(0:未找到 , 1~n: 找到)
**************************************************/
int SpecificValue_Location_CyclicList(singleLinkList_Cyclic *L, ElemType specific_value)
{
int counter = 1;
singleLinkList_Cyclic *nowNode = L->next; //①
while((nowNode != L) && (nowNode->data != specific_value))
{
counter++;
nowNode = nowNode->next;
}
if(nowNode == L) //②如果指向头结点,则未找到
{
return 0;
}
else
{
return counter;
}
}
/**************************************************
(9)函数名:SpecificLocate_Value_CyclicList
功 能:取出循环单链表中 特定位置的元素值
参 数:(1)singleLinkList_Cyclic *L: 要进行遍历查找的循环单链表
(2)int specific_locate: 要定位的特定位置
(3)ElemType &value: 传回对应的节点数据
注 意:①循环链表,超范围条件是nowNode = L,如果从头开始,nowNode = L,counter = 0,就会默认到头
所以从第 L->next开始算,
② 从① 开始算的前提是,L有后继节点,也就是L不是空表
③ L不是空表, 但是所给位置,超出循环链表长度,仍返回错误
④ ②和③其实可以归为一类,都是长度不足,但是为了做区分, 分开了
思 路:(1)定义当前节点和位置序号 (2)从第一个数据节点开始
(3) 空表直接跳出 (4)通过对比位置信息 和 检测 节点循环链表是否超范围
(5)传回特定位置信息 或者 超范围标志false
返回值: bool: 是否找到特定位置,并传回节点数据? true:false
**************************************************/
bool SpecificLocate_Value_CyclicList(singleLinkList_Cyclic *L, int specific_locate,ElemType &get_value)
{
int counter = 1;
bool result;
singleLinkList_Cyclic *nowNode;
nowNode = L->next; //①
if(nowNode == L) //②
{
result = false; //循环链表为空表,跳出
}
else
{
while(counter < specific_locate && nowNode != L)
{
counter++;
nowNode = nowNode->next;
}
if(nowNode == L) //③
{
result = false; //位置还未到,链表到头了,长度不足
}
else
{
get_value = nowNode->data;
result = true;
}
}
return result;
}
/**************************************************
(10)函数名: InsertElement_CyclicList
功 能:特定的节点值，插入到循环单链表特定位置
参 数:(1)singleLinkList_Cyclic *&L:要插入的循环单链表
(2)int specific_locate: 要插入的特定位置
(3)ElemType insert_value: 要插入的特定值
思 路: (1)定义遍历节点nowNode,新节点newNode (2)从头开始遍历,到特定位置
(3) 不管是否为空表,第一个位置都可以插入成功,单独摘出
(4) 后续遍历nowNode从 nowNode = L->next开始,只能插入到第2~n个位置
(5) 查找第(specific_locate-1 )个位置{是否超范围? true:false},将新节点插入其后
(6)返回成功
注 意: ①因为我们 判断nowNode是否结束, 是直接判断 nowNode ?= L, 所以初始不能 nowNode = L
返回值: bool:插入是否成功? true:false
**************************************************/
bool InsertElement_CyclicList(singleLinkList_Cyclic *&L, int specific_locate, ElemType insert_value)
{
int counter;
bool result;
singleLinkList_Cyclic *nowNode,*newNode;
nowNode = L;
//(3)
if(specific_locate == 1)//只插入到第一个节点(头插法)
{
newNode = (singleLinkList_Cyclic*)malloc(sizeof(singleLinkList_Cyclic));
newNode->data = insert_value;
newNode->next = L->next;
L->next = newNode;
result = true;
}
else
{
nowNode = L->next;
counter = 1; //因为nowNode最低指向 L->next,所以只能插如第2~n个位置
while(counter < (specific_locate-1) && nowNode != L)//①找到第(specific_locate-1)个元素
{
counter++;
nowNode = nowNode->next;
}
if(nowNode == L)
{
result = false;
printf("Position overrun!\n");
}
else
{
newNode = (singleLinkList_Cyclic*)malloc(sizeof(singleLinkList_Cyclic));
newNode->data = insert_value;
newNode->next = nowNode->next;
nowNode->next = newNode;
result = true;
}
}
return result;
}
/**************************************************
(11)函数名: Delete_SpecificLocate_CyclicList
功 能: 删除特定位置的节点值
参 数: (1)singleLinkList_Cyclic *&L: 要删除节点的循环单链表
(2)int specific_locate: 要删除的特定位置
(3)ElemType &delete_value: 删除节点的值
注 意: ① 删除节点,至少需要一个节点
②后面删除的是 2~n个节点
思 路: (1)范围控制(注意事项)
(2)找到要删除的节点的前一个位置,
(3)删除节点
返回值: 无
**************************************************/
bool Delete_SpecificLocate_CyclicList(singleLinkList_Cyclic *&L, int specific_locate, ElemType &delete_value)
{
int counter;
bool result;
singleLinkList_Cyclic *nowNode,*deleteNode;
nowNode = L;
if(L->next == L)
{
result = false;
}
else
if(specific_locate == 1)//①至少有一个节点
{
deleteNode = L->next; //存储要删除的节点
delete_value = deleteNode->data;
L->next = deleteNode->next;
free(deleteNode);
result = true;
}
else
{
//②后面就是删除第 2~n个节点
nowNode = L->next; //此时我们只能删除nowNode后面的节点,也就是第二个节点
counter = 1;
while(counter < (specific_locate-1) && nowNode != L) //还是要找到第 specific_locate-1 个节点
{
counter++;
nowNode = nowNode->next;
}
if(nowNode == L)
{
result = false;
}
else
{
deleteNode = nowNode->next;
delete_value = deleteNode->data;
nowNode->next = deleteNode->next;
free(deleteNode);
result = true;
}
}
return result;
}
4. main.cpp测试函数
#include <stdio.h> #include "Cyclic_singleLinkList.h" int main() { singleLinkList_Cyclic *L1,*L2; ElemType elem; ElemType A[] = {1,2,3,4,5,6,7,8}; ElemType B[] = {11,22,33,44,55,66,77,88}; Create_CyclicList_Head(L1,A,8); printf("头插法建立单链表 L1\n"); Display_CyclicList(L1); Create_CyclicList_Tail(L2,B,8); printf("\n尾插法建立单链表 L2\n"); Display_CyclicList(L2); printf("\n清空初始化L1\n"); Init_CyclicList(L1); printf("\n判断L1,是否为空:\n"); if(Empty_CyclicList(L1)) { printf("L1被清空弹夹了!\n"); } printf("\n求L2此时的长度: %d\n",Length_CyclicList(L2)); elem = 66; printf("\n%d在L2中是第%d个元素\n",elem,SpecificValue_Location_CyclicList(L2,elem)); elem = 88; if(SpecificLocate_Value_CyclicList(L2,8,elem)) { printf("\nL2中第8个元素是%d\n",elem); } elem = 99; if(InsertElement_CyclicList(L1,1,elem)) { printf("\n%d插入L1成功了\n",elem); } printf("\n%d在L1中是第%d个元素\n",elem,SpecificValue_Location_CyclicList(L1,elem)); return 0; }
5. 运行展示:
V2.0
v1.0 bug复现
调用函数(11)
运行错误结果:
原因分析:
由于我们删除的是链表节点,所以查找的是 删除节点的前一个节点, 这个节点我们已经做了 非法判断,
但是 当删除的前一个节点为链表的最后一个节点时, 我们就无法找到要删除的节点,
所以我们要再做一次 删除节点的存在判断
再次运行,即可解决卡极限bug:
1.主要功能
//(1)头插法建立循环单链表
void Create_CyclicList_Head(singleLinkList_Cyclic *&L,ElemType Array_used[],int Array_number);
//(2)尾插法建立单链表
void Create_CyclicList_Tail(singleLinkList_Cyclic *&L,ElemType Array_used[],int Array_number);
//(3)输出循环单链表
void Display_CyclicList(singleLinkList_Cyclic *L);
//(4)初始化循环单链表
void Init_CyclicList(singleLinkList_Cyclic *&L);
//(5)销毁循环单链表
void Destroy_CyclicList(singleLinkList_Cyclic *&L);
//(6)判断循环单链表是否为空
bool Empty_CyclicList(singleLinkList_Cyclic *L);
//(7)求循环单链表数据元素个数(不包括头结点)
int Length_CyclicList(singleLinkList_Cyclic *L);
//(8) 查找特定元素值,在循环单链表中的位置
int SpecificValue_Location_CyclicList(singleLinkList_Cyclic *L, ElemType specific_value);
//(9) 取出循环单链表中 特定位置的元素值
bool SpecificLocate_Value_CyclicList(singleLinkList_Cyclic *L, int specific_locate,ElemType &get_value);
//(10) 把特定的节点值, 插入到循环单链表特定位置
bool InsertElement_CyclicList(singleLinkList_Cyclic *&L, int specific_locate, ElemType insert_value);
//(11) 删除特定位置的节点值
bool Delete_SpecificLocate_CyclicList(singleLinkList_Cyclic *&L, int specific_locate, ElemType &delete_value);2. 循环链表头文件
Cyclic_singleLinkList.h
#ifndef CYCLIC_SINGLELINKLIST_H_INCLUDE
#define CYCLIC_SINGLELINKLIST_H_INCLUDE
#include "stdio.h"
#include "malloc.h"
//循环单链表基本运算函数
typedef int ElemType;
typedef struct Cyclic_Node
{
ElemType data;
struct Cyclic_Node *next;
}singleLinkList_Cyclic;
//(1)头插法建立循环单链表
void Create_CyclicList_Head(singleLinkList_Cyclic *&L,ElemType Array_used[],int Array_number);
//(2)尾插法建立单链表
void Create_CyclicList_Tail(singleLinkList_Cyclic *&L,ElemType Array_used[],int Array_number);
//(3)输出循环单链表
void Display_CyclicList(singleLinkList_Cyclic *L);
//(4)初始化循环单链表
void Init_CyclicList(singleLinkList_Cyclic *&L);
//(5)销毁循环单链表
void Destroy_CyclicList(singleLinkList_Cyclic *&L);
//(6)判断循环单链表是否为空
bool Empty_CyclicList(singleLinkList_Cyclic *L);
//(7)求循环单链表数据元素个数(不包括头结点)
int Length_CyclicList(singleLinkList_Cyclic *L);
//(8) 查找特定元素值,在循环单链表中的位置
int SpecificValue_Location_CyclicList(singleLinkList_Cyclic *L, ElemType specific_value);
//(9) 取出循环单链表中 特定位置的元素值
bool SpecificLocate_Value_CyclicList(singleLinkList_Cyclic *L, int specific_locate,ElemType &get_value);
//(10) 把特定的节点值, 插入到循环单链表特定位置
bool InsertElement_CyclicList(singleLinkList_Cyclic *&L, int specific_locate, ElemType insert_value);
//(11) 删除特定位置的节点值
bool Delete_SpecificLocate_CyclicList(singleLinkList_Cyclic *&L, int specific_locate, ElemType &delete_value);
#endif //CYCLI_SINGLELINKLIST_H_INCLUDE
3. 循环链表库函数
Cyclic_singleLinkList.cpp
#include "Cyclic_singleLinkList.h"
/**************************************************
(1)函数名: Create_CyclicList_Head
功 能: 头插法建立循环单链表
参 数: (1)singleLinkList_Cyclic *&L: 要建立并传回去的循环单链表指针地址
(2)ElemType Array_used[]: 要使用的数组数据
(3)int Array_number: 数组的长度
注 意: ①我们是按照单链表方法建立,最后找到尾指针,再形成闭环
思 路: (1)创建头结点(2)头结点置空(3)根据数据创建新节点,并利用头插法插入(4)查找尾结点(5)形成闭环
返回值: 无
**************************************************/
void Create_CyclicList_Head(singleLinkList_Cyclic *&L,ElemType Array_used[],int Array_number)
{
int counter;
singleLinkList_Cyclic *newnode,*tailnode;
L = (singleLinkList_Cyclic*)malloc(sizeof(singleLinkList_Cyclic)); //创建头结点
L->next = NULL;
for(counter = 0; counter < Array_number; counter++)
{
newnode = (singleLinkList_Cyclic*)malloc(sizeof(singleLinkList_Cyclic)); //创建新节点
newnode->data = Array_used[counter];
newnode->next = L->next; //将newnode插在原开始结点之前,头结点之后
L->next = newnode;
}
tailnode = L;
while(tailnode->next != NULL) //①查找尾结点, 从而将其指向头结点
{
tailnode = tailnode->next;
}
tailnode->next = L; // 形成闭环
}
/**************************************************
(2)函数名: Create_CyclicList_Tail
功 能: 尾插法建立单链表
参 数: (1)singleLinkList_Cyclic *&L: 要建立并传回去的循环单链表指针地址
(2)ElemType Array_used[]: 要使用的数组数据
(3)int Array_number: 数组的长度
注 意: 我们是按照单链表建立的方法进行建立,最后尾指针指向头结点即可
思 路: (1)定义新节点,尾指针节点,数组遍历序号
(2)创建头结点,并置空后继指针
(3)按照数组顺序,新建节点,并利用尾插法插入链表尾部
(4)插入完成,尾指针指向头结点
返回值: 无
**************************************************/
void Create_CyclicList_Tail(singleLinkList_Cyclic *&L,ElemType Array_used[],int Array_number)
{
int counter;
singleLinkList_Cyclic *newNode,*tailNode;
L = (singleLinkList_Cyclic*)malloc(sizeof(singleLinkList_Cyclic));
L->next = NULL;
tailNode = L;
for(counter = 0; counter < Array_number; counter++)
{
newNode = (singleLinkList_Cyclic*)malloc(sizeof(singleLinkList_Cyclic));
newNode->data = Array_used[counter];
tailNode->next = newNode;
tailNode = newNode;
}
tailNode->next = L;
}
/**************************************************
(3)函数名: Display_CyclicList
功 能: 输出展示循环单链表
参 数:(1)singleLinkList_Cyclic *L:要展示的循环单链表
注 意:①因为是循环单链表,所以结束条件是, 指针指向头结点
思 路: (1)定义遍历节点(2)判断是否为空(L == L->next)(3)从数据节点开始遍历输出(4)不结束接着遍历输出
返回值: 无
**************************************************/
void Display_CyclicList(singleLinkList_Cyclic *L)
{
singleLinkList_Cyclic *showNode;
showNode = L->next;
if(showNode == L)
{
printf("hey, it is Empty!"); //为空,无法输出
}
while(showNode != L)//①
{
printf("%d",showNode->data);
printf(" ");
showNode = showNode->next;
}
printf("\n");
}
/**************************************************
(4)函数名: Init_CyclicList
功 能: 初始化循环单链表
参 数: singleLinkList_Cyclic *&L:要初始化的循环单链表指针地址
返回值: 无
**************************************************/
void Init_CyclicList(singleLinkList_Cyclic *&L)
{
L = (singleLinkList_Cyclic*)malloc(sizeof(singleLinkList_Cyclic));
L->next = L; //初始化头结点指向自己
}
/**************************************************
(5)函数名: Destroy_CyclicList
功 能: 释放循环单链表的节点空间,
参 数: singleLinkList_Cyclic *&L:要销毁的循环单链表
注 意: ①防止野指针被函数利用后, 飘飞
②防止遍历指针信息被删除后,找不到后继信息
③循环单链表,结束条件是 尾指针指向头结点
思 路: (1)定义遍历指针和后继指针(2)规划好nowNode和backNode关系
(3) nowNode遍历删除,backNode后移,直到backNode == L,退出
(4)接着释放nowNode,并且防止野指针飘飞,①
返回值: 无
**************************************************/
void Destroy_CyclicList(singleLinkList_Cyclic *&L)
{
singleLinkList_Cyclic *nowNode;
singleLinkList_Cyclic *backNode; //②
nowNode = L;
backNode = nowNode->next;
while(backNode != L) //③
{
free(nowNode);
nowNode = backNode;
backNode = backNode->next;
}
free(nowNode);
L->next = L; //①
}
/**************************************************
(6)函数名: Empty_CyclicList
功 能: 判断循环单链表是否为空
参 数: singleLinkList_Cyclic *L:要参与判断的循环单链表
返回值: bool:是否为空? true:false
**************************************************/
bool Empty_CyclicList(singleLinkList_Cyclic *L)
{
return (L->next == L);
}
/**************************************************
(7)函数名: Length_CyclicList
功 能: 求循环单链表数据元素个数(不包括头结点)
参 数: singleLinkList_Cyclic *L :要参与计算的循环单链表
注 意: ① 结束条件:尾指针指向头结点
返回值: int: 循环单链表数据元素个数
**************************************************/
int Length_CyclicList(singleLinkList_Cyclic *L)
{
int counter = 0;
singleLinkList_Cyclic *nowNode = L;
while(nowNode->next != L) //①
{
counter++;
nowNode = nowNode->next;
}
return counter;
}
/**************************************************
(8)函数名:SpecificValue_Location_CyclicList
功 能:找特定元素值,在循环单链表中的位置
参 数:(1)singleLinkList_Cyclic *L: 需要查找的循环单链表
(2)ElemType specific_value: 要查找的元素值
注 意: ① 从 L->next开始,即第一个数据元素开始查找,其位置counter伴随
②跳出有两种情况:1,找到 2,超范围指向头结点
返回值: int: 返回特定元素值的 位置(0:未找到 , 1~n: 找到)
**************************************************/
int SpecificValue_Location_CyclicList(singleLinkList_Cyclic *L, ElemType specific_value)
{
int counter = 1;
singleLinkList_Cyclic *nowNode = L->next; //①
while((nowNode != L) && (nowNode->data != specific_value))
{
counter++;
nowNode = nowNode->next;
}
if(nowNode == L) //②如果指向头结点,则未找到
{
return 0;
}
else
{
return counter;
}
}
/**************************************************
(9)函数名:SpecificLocate_Value_CyclicList
功 能:取出循环单链表中 特定位置的元素值
参 数:(1)singleLinkList_Cyclic *L: 要进行遍历查找的循环单链表
(2)int specific_locate: 要定位的特定位置
(3)ElemType &value: 传回对应的节点数据
注 意:①循环链表,超范围条件是nowNode = L,如果从头开始,nowNode = L,counter = 0,就会默认到头
所以从第 L->next开始算,
② 从① 开始算的前提是,L有后继节点,也就是L不是空表
③ L不是空表, 但是所给位置,超出循环链表长度,仍返回错误
④ ②和③其实可以归为一类,都是长度不足,但是为了做区分, 分开了
思 路:(1)定义当前节点和位置序号 (2)从第一个数据节点开始
(3) 空表直接跳出 (4)通过对比位置信息 和 检测 节点循环链表是否超范围
(5)传回特定位置信息 或者 超范围标志false
返回值: bool: 是否找到特定位置,并传回节点数据? true:false
**************************************************/
bool SpecificLocate_Value_CyclicList(singleLinkList_Cyclic *L, int specific_locate,ElemType &get_value)
{
int counter = 1;
bool result;
singleLinkList_Cyclic *nowNode;
nowNode = L->next; //①
if(nowNode == L) //②
{
result = false; //循环链表为空表,跳出
}
else
{
while(counter < specific_locate && nowNode != L)
{
counter++;
nowNode = nowNode->next;
}
if(nowNode == L) //③
{
result = false; //位置还未到,链表到头了,长度不足
}
else
{
get_value = nowNode->data;
result = true;
}
}
return result;
}
/**************************************************
(10)函数名: InsertElement_CyclicList
功 能:特定的节点值，插入到循环单链表特定位置
参 数:(1)singleLinkList_Cyclic *&L:要插入的循环单链表
(2)int specific_locate: 要插入的特定位置
(3)ElemType insert_value: 要插入的特定值
思 路: (1)定义遍历节点nowNode,新节点newNode (2)从头开始遍历,到特定位置
(3) 不管是否为空表,第一个位置都可以插入成功,单独摘出
(4) 后续遍历nowNode从 nowNode = L->next开始,只能插入到第2~n个位置
(5) 查找第(specific_locate-1 )个位置{是否超范围? true:false},将新节点插入其后
(6)返回成功
注 意: ①因为我们 判断nowNode是否结束, 是直接判断 nowNode ?= L, 所以初始不能 nowNode = L
返回值: bool:插入是否成功? true:false
**************************************************/
bool InsertElement_CyclicList(singleLinkList_Cyclic *&L, int specific_locate, ElemType insert_value)
{
int counter;
bool result;
singleLinkList_Cyclic *nowNode,*newNode;
nowNode = L;
//(3)
if(specific_locate == 1)//只插入到第一个节点(头插法)
{
newNode = (singleLinkList_Cyclic*)malloc(sizeof(singleLinkList_Cyclic));
newNode->data = insert_value;
newNode->next = L->next;
L->next = newNode;
result = true;
}
else
{
nowNode = L->next;
counter = 1; //因为nowNode最低指向 L->next,所以只能插如第2~n个位置
while(counter < (specific_locate-1) && nowNode != L)//①找到第(specific_locate-1)个元素
{
counter++;
nowNode = nowNode->next;
}
if(nowNode == L)
{
result = false;
printf("Position overrun!\n");
}
else
{
newNode = (singleLinkList_Cyclic*)malloc(sizeof(singleLinkList_Cyclic));
newNode->data = insert_value;
newNode->next = nowNode->next;
nowNode->next = newNode;
result = true;
}
}
return result;
}
/**************************************************
(11)函数名: Delete_SpecificLocate_CyclicList
功 能: 删除特定位置的节点值
参 数: (1)singleLinkList_Cyclic *&L: 要删除节点的循环单链表
(2)int specific_locate: 要删除的特定位置
(3)ElemType &delete_value: 删除节点的值
注 意: ① 删除节点,至少需要一个节点
②后面删除的是 2~n个节点
③由于找到删除节点的前一个节点(specific_locate-1),前一个在范围内,但删除节点不一定
思 路: (1)范围控制(注意事项)
(2)找到要删除的节点的前一个位置,
(3)删除节点
返回值: 无
**************************************************/
bool Delete_SpecificLocate_CyclicList(singleLinkList_Cyclic *&L, int specific_locate, ElemType &delete_value)
{
int counter;
bool result;
singleLinkList_Cyclic *nowNode,*deleteNode;
nowNode = L;
if(L->next == L)
{
printf("The single linked list is empty and cannot be deleted!\n");
result = false;
}
else
if(specific_locate == 1)//①至少有一个节点
{
deleteNode = L->next; //存储要删除的节点
delete_value = deleteNode->data;
L->next = deleteNode->next;
free(deleteNode);
result = true;
}
else
{
//②后面就是删除第 2~n个节点
nowNode = L->next; //此时我们只能删除nowNode后面的节点,也就是第二个节点
counter = 1;
while(counter < (specific_locate-1) && nowNode != L) //还是要找到第 specific_locate-1 个节点
{
counter++;
nowNode = nowNode->next;
}
if(nowNode == L)
{
printf("(1)Single linked list deletion out of range!\n");
result = false;
}
else
{
deleteNode = nowNode->next;
if(deleteNode == L) //
{
printf("(2)Single linked list deletion out of range!\n");
result = false;
}
else
{
delete_value = deleteNode->data;
nowNode->next = deleteNode->next;
free(deleteNode);
result = true;
}
}
}
return result;
}
4. main.cpp测试函数
#include <stdio.h>
#include "Cyclic_singleLinkList.h"
int main()
{
singleLinkList_Cyclic *L1,*L2;
ElemType elem;
ElemType A[] = {1,2,3,4,5,6,7,8};
ElemType B[] = {11,22,33,44,55,66,77,88};
Create_CyclicList_Head(L1,A,8);
printf("头插法建立单链表 L1\n");
Display_CyclicList(L1);
Create_CyclicList_Tail(L2,B,8);
printf("\n尾插法建立单链表 L2\n");
Display_CyclicList(L2);
if(Delete_SpecificLocate_CyclicList(L2,9,elem))
{
//v2.0 bug验证并修复
printf("成功删除了%d\n",elem);
}
printf("\n清空初始化L1\n");
Init_CyclicList(L1);
printf("\n判断L1,是否为空:\n");
if(Empty_CyclicList(L1))
{
printf("L1被清空弹夹了!\n");
}
printf("\n求L2此时的长度: %d\n",Length_CyclicList(L2));
elem = 66;
printf("\n%d在L2中是第%d个元素\n",elem,SpecificValue_Location_CyclicList(L2,elem));
elem = 88;
if(SpecificLocate_Value_CyclicList(L2,8,elem))
{
printf("\nL2中第8个元素是%d\n",elem);
}
elem = 99;
if(InsertElement_CyclicList(L1,1,elem))
{
printf("\n%d插入L1成功了\n",elem);
}
printf("\n%d在L1中是第%d个元素\n",elem,SpecificValue_Location_CyclicList(L1,elem));
return 0;
}
5. 运行展示:
