单向循环链表与单向链表的结点结构相同，每个结点都有一个数据域、一个指针域。
数据域用来存储结点的数据，指针域用来存储下一个结点所在的内存空间地址。
两者不同的是，单向链表末结点的指针域为NULL，而单向循环链表末结点的指针域存储了头结点所在的内存空间地址。
这里实现了单向循环链表的六个基本功能，初始化链表、添加结点(头插法、尾插法)、删除结点、反转链表、遍历链表。
一、代码结构
1.1单向循环链表的数据结构
typedef struct node
{
int data;//数据域
struct node * next;//指针域
}Node;
1.2单向循环链表的六个方法
1.2.1 Node * initialize()
初始化单向循环链表，返回头结点的指针
1.2.2 void headInsert(Node * head,int data)
添加结点(头插法)，每次插入的新结点都会作为第一个结点存在
1.2.3 void tailInsert(Node * head,int data)
添加结点(尾插法)，每次插入的新结点都会作为末结点存在
1.2.4 int delete(Node * head,int data)
删除结点，将指定数据的结点删除，删除成功返回1，删除失败返回0
1.2.5 void reverse(Node * head)
反转链表，将链表结点的原有顺序首尾颠倒过来，其实现方法的核心还是头插法
1.2.6 void reveal(Node * head)
遍历链表，将链表的每个结点依次展出
二、主要代码
/*
单向循环链表
初始化链表
增加结点(头插法、尾插法)
删除结点
反转链表
遍历链表
*/
//定义循环链表的数据结构
#include
#include
typedef struct node
{
int data;//数据域
struct node * next;//指针域
}Node;
//初始化链表
Node * initialize()
{
Node * head=(Node*)(malloc(sizeof(Node)));
head->data=0;//头结点的数据域用来存储链表的结点个数
head->next=head;//头结点的指针域用来存储后继结点所在的内存空间地址，初始化时存储自身所在的内存空间地址
return head;
}
// 增加结点(头插法)
void headInsert(Node * head,int data)
{
Node * newborn=(Node*)(malloc(sizeof(Node)));//创建新结点
newborn->data=data;//给新结点的数据域赋值
newborn->next=head->next;//新结点的指针域指向头结点的指针域所指向的内存空间地址
head->next=newborn;//头结点的指针域指向新结点
head->data++;//头结点的数据域自增，说明链表的结点个数增加
}
// 增加结点(尾插法)
void tailInsert(Node * head,int data)
{
Node * newborn=(Node*)(malloc(sizeof(Node)));//创建新结点
newborn->data=data;//给新结点的数据域赋值
Node * start=head->next;//定义循环指针变量start，其初始值为链表中首元素的内存空间地址
for(;start->next!=head;start=start->next);//通过循环遍历链表，将start定位到末结点
newborn->next=start->next;//新结点的指针域指向末结点的指针域所指向的内存空间，即头结点的内存空间
start->next=newborn;//末结点的指针域指向新结点
head->data++;//头指针的数据域自增，说明链表的结点个数增加
}
//删除结点
int delete(Node * head,int data)
{
Node * previousNode=head;
//变量previousNode用来存储当前结点的前驱结点内存空间地址，初始化值为头结点的内存空间地址
Node * start=head->next;//变量start用来存储首结点的内存空间地址，作循环变量使用
while(start!=head)//循环变量start与变量head的值不相等时，循环继续运行
{
if(start->data==data)//找到指定的数据时
{
previousNode->next=start->next;//当前结点的前驱结点指针域就指向当前结点的后继结点
free(start);//释放当前结点
head->data--;//头结点的数据域自减，说明链表的结点个数减少
return 1;
}
previousNode=start;//previousNode存储本次循环的结点，在下一次循环中就变当前结点的前驱结点
start=start->next;//当前结点向后遍历
}
return 0;
}
//反转链表(核心还是头插法)
void reverse(Node * head)
{
Node * start=head->next;//变量start存储首结点的内存空间，作循环变量使用
Node * temporary;//变量temporary用来临时存储当前结点
head->next=head;//让头结点的指针域指向自身,表明链表中无结点
while(start!=head)//当循环变量start不等于头结点指针变量head时
{
temporary=start;//变量temporary存储循环变量start的值，也就是存储了当前结点的内存空间地址
start=start->next;//而循环变量start向后遍历一个结点
temporary->next=head->next;//此时，把头结点指针域的值赋给temporary的指针域
head->next=temporary; //让头结点的指针域指向temporary
}
}
//遍历链表
void reveal(Node * head)
{
for(Node * start=head->next;start!=head;start=start->next)
{
if(start->next!=head)
{
printf("%d , ",start->data);
}else
{
printf("%d\n",start->data);
}
}
}
int main(int argc,char * argv[])
{
puts("--------------初始化链表--------------");
Node * head=initialize();
printf("head=\t%p\n\n",head);
puts("-------------- 增加结点(头插法)--------------");
headInsert(head,13);
headInsert(head,14);
headInsert(head,15);
reveal(head);
printf("length:\t%d\n\n",head->data);
puts("-------------- 增加结点(尾插法)--------------");
tailInsert(head,21);
tailInsert(head,22);
tailInsert(head,23);
reveal(head);
printf("length:\t%d\n\n",head->data);
puts("--------------删除结点--------------");
puts("删除数据为5120的结点");
puts("删除前:");
reveal(head);
printf("%s\n",delete(head,5120)==1?"--------删除成功":"--------删除失败");
reveal(head);
printf("length:\t%d\n\n",head->data);
puts("删除数据为13的结点");
puts("删除前:");
reveal(head);
printf("%s\n",delete(head,13)==1?"--------删除成功":"--------删除失败");
reveal(head);
printf("length:\t%d\n\n",head->data);
puts("删除数据为23的结点");
puts("删除前:");
reveal(head);
printf("%s\n",delete(head,23)==1?"--------删除成功":"--------删除失败");
reveal(head);
printf("length:\t%d\n\n",head->data);
puts("--------------反转链表--------------");
puts("-------反转前");
reveal(head);
reverse(head);
puts("-------反转后");
reveal(head);
}
三、运行展示
四、感受
玩单向循环链表，很容易陷入思维惯性，把单向链表的实现方法带进来，导致一些逻辑错误。在写代码前先画画图，让自己的脑子进入单向循环链表，这样就能一次性完美实现单向循环链表。
推荐阅读
发表评论