单向循环链表

是在单向链表的基础上，将最后一个数据结点的指针域指向头结点，头尾相连。

可解决约瑟夫环问题。

单向循环链表结构体声明

typedef struct looplinklist{
    data_t data;
    struct looplinklist *next;
}LOOPL;

单向循环链表的操作

和单向链表的操作类似：创建、插入（头插/尾插）、删除、遍历（打印）、查找、修改等。

不同的地方在于一些判断条件的变化：例如遍历结束的条件变成了node->next!=h

创建头结点

LOOPL *creatLNode(void)
{
    LOOPL *h = (LOOPL*)malloc(sizeof(LOOPL));
    h->next = h;
    return h;
}

创建数据结点

LOOPL *creatDataLNode(data_t val)
{
    LOOPL *node = (LOOPL*)malloc(sizeof(LOOPL));
    node->data = val;
    node->next = NULL;
    return node;
}

头插法插入一个数据结点

void insertLNode(LOOPL *h,data_t val)
{
    LOOPL *node = creatDataLNode(val);
    node->next = h->next;
    h->next = node;
}

带头结点遍历（打印）

void printLOOPL(LOOPL *h)
{
    LOOPL *temp = h;
    while(h->next!=temp)
    {
        h=h->next;
        printf("%d ",h->data);
    }
    putchar(10);
}

删除头结点

LOOPL *delHeadLOOPL(LOOPL *h)
{
    LOOPL *temp = h;
    while(h->next!=temp)
    {
        h = h->next;
    }
    h->next = temp->next;
    free(temp);
    return h->next;
}

遍历找到最后一个数据结点，修改该结点的指针指向第一个数据结点

不带头结点遍历（打印）

void printNoheadLOOPL(LOOPL *h)
{
    LOOPL *temp = h;
    while(h->next!=temp)
    {
        printf("%d ",h->data);
        h=h->next;
    }
    printf("%d \n",h->data);
}

示例

#include <stdio.h>
#include <stdlib.h>
typedef int data_t;
typedef struct looplinklist{
    data_t data;
    struct looplinklist *next;
}LOOPL;

LOOPL *creatLNode(void);
LOOPL *creatDataLNode(data_t val);
void insertLNode(LOOPL *h,data_t val);
void printLOOPL(LOOPL *h);
LOOPL *delHeadLOOPL(LOOPL *h);
void printNoheadLOOPL(LOOPL *h);

int main(int argc, const char *argv[])
{
    LOOPL *h = creatLNode();
    insertLNode(h,1);
    insertLNode(h,2);
    printLOOPL(h);
    h = delHeadLOOPL(h);//删除头节点
    printNoheadLOOPL(h);
    return 0;
}
//创建头节点
LOOPL *creatLNode(void)
{
    LOOPL *h = (LOOPL*)malloc(sizeof(LOOPL));
    h->next = h;
    return h;
}
//创建数据节点
LOOPL *creatDataLNode(data_t val)
{
    LOOPL *node = (LOOPL*)malloc(sizeof(LOOPL));
    node->data = val;
    node->next = NULL;
    return node;
}
//头插法插入一个数据节点
void insertLNode(LOOPL *h,data_t val)
{
    LOOPL *node = creatDataLNode(val);
    node->next = h->next;
    h->next = node;
}
//带头结点打印循环链表
void printLOOPL(LOOPL *h)
{
    LOOPL *temp = h;
    while(h->next!=temp)
    {
        h=h->next;
        printf("%d ",h->data);
    }
    putchar(10);
}
//删除头结点
LOOPL *delHeadLOOPL(LOOPL *h)
{
    LOOPL *temp = h;
    while(h->next!=temp)
    {
        h = h->next;
    }
    h->next = temp->next;
    free(temp);
    return h->next;
}
//不带头结点打印
void printNoheadLOOPL(LOOPL *h)
{
    LOOPL *temp = h;
    while(h->next!=temp)
    {
        printf("%d ",h->data);
        h=h->next;
    }
    printf("%d \n",h->data);
}

结果

2 1
2 1

本文链接：https://shengto.top/data_structure/143.html

转载时须注明出处及本声明