[数据结构与算法]数据结构之单向循环链表

单向循环链表与单向链表的结点结构相同，每个结点都有一个数据域、一个指针域。

数据域用来存储结点的数据，指针域用来存储下一个结点所在的内存空间地址。

两者不同的是，单向链表末结点的指针域为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<stdio.h>
#include<stdlib.h>
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);

   
}

三、运行展示

?四、感受

? ? ? ? 玩单向循环链表，很容易陷入思维惯性，把单向链表的实现方法带进来，导致一些逻辑错误。在写代码前先画画图，让自己的脑子进入单向循环链表，这样就能一次性完美实现单向循环链表。