数据结构与算法－循环链表

作者: 风云永杰 | 来源:发表于2020-04-02 18:10 被阅读0次

镇楼图

今天我们来实现一个单向循环链表，在实现之前先让我们看看什么叫循环链表，它又是长什么样的呢？

什么是循环链表

循环链表：循环链表是另一种形式的链式存储结构。它的特点是表中最后一个结点的指针域指向首元节点，整个链表形成一个环。如图：

单向循环链表

循环链表的创建

在创建循环链表之前我们先看看单链表是什么样的？如图：

截屏2020-04-0216.27.20.png

单链表的创建代码

///创建单链表
Status CreateList(LinkList *L){
    int value;
    Node *temp;
    Node *last = NULL;
    printf("请输入数字,输入0结束\n");
    while (1) {
        scanf("%d",&value);
        if (value==0) break;
        temp=(Node *)malloc(sizeof(Node));
        if (temp==NULL) return ERROR;
        temp->data=value;
        if ((*L)==NULL) {
            *L=temp;
            last=temp;
        }else{
            last->next=temp;
            last=temp;
        }
    }
    return OK;
}

看到了单链表的创建，那循环链表要怎么做呢？很简单，就是让最后一个节点的指针域指向首元节点嘛。只需要加一句代码:

last->next=*L;

完整创建方法:

Status CreateList(LinkList *L){
    int value;
    Node *temp;
    Node *last = NULL;
    printf("请输入数字,输入0结束\n");
    while (1) {
        scanf("%d",&value);
        if (value==0) break;
        temp=(Node *)malloc(sizeof(Node));
        if (temp==NULL) return ERROR;
        temp->data=value;
        if ((*L)==NULL) {
            *L=temp;
            last=temp;
        }else{
            last->next=temp;
            last=temp;
        }
        last->next=*L;
    }
    return OK;
}

循环链表打印

在实现其它功能前先来实现输出打印功能吧。毕竟有了输出打印方法，我们才能看到它的内部状态嘛，这部分没啥说的直接上代码。

/// 打印循环链表
Status TraverseList(LinkList L){
    if (L==NULL) {
        printf("打印的是空链表!");
        return ERROR;
    };
    Node *temp=L;
    do {
        printf("%5d",temp->data);
        temp=temp->next;;
    } while (temp!=L);
    printf("\n");
    return OK;
}

注意！注意！注意！再做任何操作之前先对 L==NULL 进行判断，不要对 NULL 做任何操作！不要对 NULL 做任何操作！不要对 NULL 做任何操作！重要的事情一定要说３遍。

循环链表插入

在做循环链表插入的时候有两种情况。第一种是插入位置是首元节点，第二种就是其它节点了。

我们先看插入位置是首元节点的话要怎么做。如图：

在首元节点插入

简单讲一下步骤：

创建新节点，
找到尾节点，
尾节点指针域指向新节点，
新节点指针域指向首元节点，
链表指针指向新节点，

小二上代码：

/// 插入节点
Status ListInsert(LinkList *L,int place,int value){
    Node *temp;
    Node *newNode=(Node *)malloc(sizeof(Node));
    if (newNode==NULL) return ERROR;
    newNode->data=value;
    
    if (place == 1) {
        for (temp=(*L); temp->next != (*L); temp=temp->next){}
        newNode->next=*L;
        temp->next=newNode;
        (*L)=newNode;
    }
    return OK;
}

再来看一下第二种，插入位置不是首元节点的情况

其它位置插入

步骤：

创建新节点，
找到插入位置前一个节点，
新节点指针域指向前一个节点的指针域指向的节点，
前一个节点的指针域指向新节点，

小二再来一段代码：

/// 插入节点
Status ListInsert(LinkList *L,int place,int value){
    Node *temp;
    Node *newNode=(Node *)malloc(sizeof(Node));
    if (newNode==NULL) return ERROR;
    newNode->data=value;
    
    if (place == 1) {
        for (temp=(*L); temp->next != (*L); temp=temp->next){}
        newNode->next=*L;
        temp->next=newNode;
        (*L)=newNode;
    }else{
        int i;
        for (i=1,temp=(*L); (temp->next!=(*L))&&(i<place-1); i++,temp=temp->next){}
        newNode->next=temp->next;
        temp->next=newNode;
    }
    return OK;
}

当然再插入之前先做插入位置合法性校验，这里就不贴代码了。

循环链表删除

同样删除也有两种情况，删除首元节点和删除其它节点，我们先来看删除首元节点的步骤：

找到尾节点，
尾节点指针域指向首元节点指针域指向的节点，
新建一个节点指针，指向首元节点，
链表指针指向首元节点指针域指向的节点，
释放新建的指针指向的内存，

来代码：

/// 删除节点
Status ListDelete(LinkList *L,int place){
    printf("方法内变量地址:%p\n",&L);
    Node *temp;
    Node *old;
    
    if (*L==NULL) return ERROR;
    
    if (place == 1) {
        for (temp=(*L); temp->next != (*L); temp=temp->next){}
        temp->next=(*L)->next;
        old=*L;
        //如果删除的是最后一个元素,让链表指针为NULL
        if ((*L)->next==*L) {
            *L=NULL;
            free(old);
            return OK;
        }else{
            *L=temp->next;
        }
        free(old);
    }
    return OK;
}

另外一种情况，删除的不是首元节点，这种情况的步骤：

找到要删除位置的前一个节点，
新建一个节点指针，指向前一个节点指针域指向的节点，也就是要删除的节点，
前一个节点的指针域指向它原来指向节点指针域指向的节点,也就是:
temp->next=temp->next->next;
释放要删除的节点,

/// 删除节点
Status ListDelete(LinkList *L,int place){
    printf("方法内变量地址:%p\n",&L);
    Node *temp;
    Node *old;
    
    if (*L==NULL) return ERROR;
    
    if (place == 1) {
        for (temp=(*L); temp->next != (*L); temp=temp->next){}
        temp->next=(*L)->next;
        old=*L;
        //如果删除的是最后一个元素,让链表指针为NULL
        if ((*L)->next==*L) {
            *L=NULL;
            free(old);
            return OK;
        }else{
            *L=temp->next;
        }
        free(old);
    }else{
        int i;
        for (i=1,temp=(*L); (temp->next!=(*L))&&(i<place-1); i++,temp=temp->next){}
        old=temp->next;
        temp->next=temp->next->next;
        free(old);
    }
    return OK;
}

这里有一个地方要注意一下，如果链表中只剩最后一个节点时，删除后要额外做一个判断，使链表指针指向NULL，否则链表指针仍然指向已经释放的内存。

//如果删除的是最后一个元素,让链表指针为NULL
if ((*L)->next==*L) {
        *L=NULL;
        free(old);
        return OK;
}

同样的，删除前先做删除位置合法性校验！

约瑟夫杀人问题

什么是约瑟夫杀人问题?

据说著名犹太历史学家 Josephus有过以下的故事：在罗马人占领乔塔帕特后，39 个犹太人与Josephus及他的朋友躲到一个洞中，39个犹太人决定宁愿死也不要被敌人抓到，于是决定了一个自杀方式，41个人排成一个圆圈，由第1个人开始报数，每报数到第3人该人就必须自杀，然后再由下一个重新报数，直到所有人都自杀身亡为止。然而Josephus 和他的朋友并不想遵从。首先从一个人开始，越过k-2个人（因为第一个人已经被越过），并杀掉第k个人。接着，再越过k-1个人，并杀掉第k个人。这个过程沿着圆圈一直进行，直到最终只剩下一个人留下，这个人就可以继续活着。问题是，给定了和，一开始要站在什么地方才能避免被处决？Josephus要他的朋友先假装遵从，他将朋友与自己安排在第16个与第31个位置，于是逃过了这场死亡游戏。

简单来说就是:N个人围成一圈，从第一个开始报数，第M个将被杀掉，最后剩下一个，其余人都将被杀掉。例如N=6，M=5，被杀掉的顺序是：5，4，6，2，3，1。

我们用循环链表来试着解决一下这个问题:

先创建链表

/// 创建循环链表
/// @param L 链表指针
/// @param sum 总人数
Status CreateList(LinkList *L,int sum){
    int value;
    Node *temp;
    Node *last = NULL;
    for (int i=1; i<=sum; i++) {
        value=i;
        temp=(Node *)malloc(sizeof(Node));
        if (temp==NULL) return ERROR;
        temp->data=value;
        if ((*L)==NULL) {
            *L=temp;
            last=temp;
        }else{
            last->next=temp;
            last=temp;
        }
        last->next=*L;
    }
    return OK;
}

杀人游戏代码:

/// 开始游戏
/// @param L 要操作链表指针
/// @param m 报m数的人杀掉,
Status startKill(LinkList *L,int m){
    if (*L==NULL) return ERROR;
    int i=1;
    Node *temp=*L;
    Node *willKill;
    printf("开始杀人,\n");
    while (temp->next!=temp) {
        //找到要杀的人前一个人
        if (i==m-1) {
            willKill=temp->next;
            printf("%d,",willKill->data);
            temp->next=willKill->next;
            temp=willKill->next;
            free(willKill);
            i=1;
        }else{
            i++;
            temp=temp->next;
        }
    }
    printf("\n");
    printf("游戏结束,最后活下来的人是:%d\n",temp->data);
    *L=temp;
    return OK;
}

最后我们在main()方法中调用代码

int main(int argc, const char * argv[]) {
    // insert code here...
    LinkList head;
    //n个人
    int n;
    //第m个人杀掉
    int m;
    printf("请输入总人数和要杀的数,用空格格开\n");
    scanf("%d %d",&n,&m);
    CreateList(&head,n);
    TraverseList(head);
    //开始游戏
    startKill(&head, m);
    return 0;
}

运行程序

请输入总人数和要杀的数,用空格格开
6 5
1,2,3,4,5,6,
开始杀人,
5,4,6,2,3,
游戏结束,最后活下来的人是:1

再来一次,回归到问题本身,当时是41个人,报3的杀掉,试一下:

请输入总人数和要杀的数,用空格格开
41 3
1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40,41,
开始杀人,
3,6,9,12,15,18,21,24,27,30,33,36,39,1,5,10,14,19,23,28,32,37,41,7,13,20,26,34,40,8,17,29,38,11,25,2,22,4,35,16,
游戏结束,最后活下来的人是:31

最后再提醒一下自己，删除时需要记住的两点！１记得释放已经删除的节点。２链表为空是链表指针指向NULL。

数据结构与算法－循环链表

什么是循环链表

循环链表的创建

循环链表打印

循环链表插入

循环链表删除

约瑟夫杀人问题

相关文章

网友评论

延伸阅读

深度阅读

栏目导航

热点阅读