单向循环链表

单向循环链表

：将单向链表的最后一个结点指向头结点形成一个环，即成为单向循环链表，可以通过其中任意一个结点出发访问到其他结点。单向循环链表的操作方法与单向链表相似，只是在于循环条件存在差异。


特点

：

• 若链表为空，则头结点的next结点还是指向其本身，即head ->next=head；
• 尾节点的next指针指向head结点，即头尾相连；
• 通过判断当前结点的next结点是否与head结点相等，即可判断是否对单向循环链表遍历完成；
• 循环链表无须增加存储量，仅对单向链表的链接方式稍作改变，即可使得单向链表处理更加方便灵活。

单向循环链表结构如下图所示：




注

：单向循环链表不一定存在头结点

单向循环链表宏定义及数据类型

//定义处理的数据类型
typedef int ElemType;
#define bool int

//定义状态
typedef enum Status
{
    success, fail, fatal, rang_err
}Status;

//定义数据类型的结构
typedef struct Node
{
    ElemType data;
    struct Node *next;
}Node,*PtrList;

单向循环链表初始化

/************************************************************
 * 函数名称：InitList(PtrList list,int size)
 * 功能描述：初始化循环链表
 * 传入参数：PtrList lis       待初始化的循环链表
 *           int size          初始化的循环链表长度
 * 返回值：fail    失败
 *         success 成功
 ************************************************************/
Status InitList(PtrList list, int size)
{
    Status _outcome_ = fail;
    int i = 1;
    ElemType elem;
    list = (PtrList)malloc(sizeof(Node));
    PtrList Tail;
    PtrList Temp;
    if(list != NULL)
    {
        list -> data = 0;
        list -> next = list;/*第一个节点不保存数据*/
        Tail = list;
        for(; i< size+1;size++)
        {
            Temp = (PtrList)malloc(sizeof(Node));
            if(Temp == NULL)
            {
                return _outcome_;
            }
            printf("请输入第%d个节点的数据：",i)
            scanf("%d",&elem);

            Temp -> data = elem;
            Temp ->next = list;

            Tail ->next = Temp;
            Tail = Temp;
            _outcome_ = success;
        }
    }
    return _outcome_;
}

单向循环链表插入数据

/************************************************************
 * 函数名称：InitList(PtrList list,int size)
 * 功能描述：循环链表插入数据
 * 传入参数：PtrList lis       传入的循环链表
 *           int i             插入的位置
 *           ElemType elem     插入的数据
 * 返回值：fail    失败
 *         success 成功
 ************************************************************/
Status InsertList(PtrList list, int i,ElemType elem)
{
    Status _outcome_ = fail;
    PtrList Temp = NULL,Target = NULL;
    if(i == 1)/*循环链表头部插入结点*/
    {
        Temp = (PtrList)malloc(sizeof(Node));
        if(NULL == Temp)
        {
            return _outcome_;
        }
        Temp -> data = elem;
        for( Target = list; Target != list; Target = Target -> next);/*找到最后一个结点*/
        Temp -> next = list;
        Target ->next = Temp;
        list = Temp;/*新插入的结点作为头节点*/
        _outcome_ = success;
    }
    else
    {
        Target = list;
        for(int j = 1; j < (i-1); j++)
        {
            Target = Target -> next;/*找到第i-1个节点*/
        }
        Temp = (PtrList)malloc(sizeof(Node));
        if(Temp == NULL)
        {
            return _outcome_;
        }
        Temp ->next = Target ->next;
        Temp ->data = elem;
        Target -> next = Temp;
        _outcome_ = success;
    }
    return _outcome_;
}

单向循环链表删除结点

/************************************************************
 * 函数名称：DeleteList(PtrList list, int i)
 * 功能描述：循环链表删除数据
 * 传入参数：PtrList lis       传入的循环链表
 *           int i             删除的位置
 * 返回值：fail    失败
 *         success 成功
 ************************************************************/
Status DeleteList(PtrList list, int i)
{
    Status _outcome_ = fail;
    PtrList Target = NULL,Temp = NULL;
    if(i == 1)
    {
        for(Target = list;Target ->next != list;Target = Target -> next);/*找到尾结点*/
        Target ->next = list ->next;
        Temp = list;
        list = list ->next;
        free(Temp);
        if( NULL != Temp)
        {
            return _outcome_;
        }
        _outcome_ = success;
    }
    else
    {
        Target = list;
        for(int j = 1; j < i-1; j++)
        {
            Target = Target -> next;/*找到第i-1个结点*/
        }
        Temp = Target ->next;
        Target ->next = Temp ->next;
        free(Temp);
        if(NULL != Temp)
        {
            return _outcome_;
        }
        _outcome_ = success;
    }
    return _outcome_;
}

返回单向循环链表中结点位置

/************************************************************
 * 函数名称：SearchList(PtrList list, ElemType elem)
 * 功能描述：返回节点所在位置
 * 传入参数：PtrList lis       传入的循环链表
 *           ElemType  elem    结点数据        
 * 返回值：结点位置
 *         若返回0表示循环链表中不存在该结点
 ************************************************************/
int SearchList(PtrList list, ElemType elem)
{
    PtrList Target = list;
    PtrList listHead = list;
    int num = 0;
    
    while((Target -> data != elem) && (Target -> next != listHead))
    {
        ++num;
        Target = Target -> next;
    }
    
    if(Target -> next == listHead && Target -> data != elem)
    {
        return fail;
    }
    
    return num;
}