C++U3-第11课-单、双链表

小虾同学 / 2024-01-21 / 原文

学习目标

链表概念

计算机存储结构

单链表

实现单链表

删除

插入节点

双向链表

实现双链表

[【数据结构-链表】猴子选大王]

【题意分析】
通过循环报数的方式每一次剔除报到4数字的猴子，最后剩下的猴子就为大王

【思路分析】
通过链表的方式连接每一只猴子，将上一只猴子的尾指针指向下一只猴子，将猴子储存成为链式的结构，然后进行报数，每一次报数将指针向后进行移动。当报数为m-1的时候删除当前节点的下一个节点，也就是通过将当前位置的尾指针指向的位置变成下一个猴子的尾指针位置

定义结构体储存猴子的id和他的下一只猴子的位置

创建结构体表示当前的第一只猴子

通过while循环的方式将所有的猴子通过链表的方式连接在一起，前一只猴子的尾指向后一只猴子

将最后一只猴子的尾指针指向第一只猴子

定义一个指针表示当前报数的是哪一只猴子

通过for循环报数m-2只猴子每一次报数将指针往后移动一个，最后停留在m-1只猴子的位置

当前这个猴子的后一只需要出圈，将当前尾指针变成指向后一只猴子的尾指针

向后移动一只猴子

输出最后的猴子

【参考代码】
#include<iostream>
using namespace std;
//定义结构体储存猴子的id和他的下一只猴子的位置 
struct node{
    int data;
    node *next;
};
int n,m;
node *head,*p,*r;
int main(){
    cin>>n>>m;
    //创建结构体表示当前的第一只猴子 
    head=new node;
    head->data=1,head->next=NULL;
    r=head;
    //通过while循环的方式将所有的猴子通过链表的方式连接在一起，前一只猴子的尾指向后一只猴子
    for(int i=2;i<=n;i++){
        p=new node;
        p->data=i;
        p->next=NULL;
        r->next=p;
        r=p;
    }
    //将最后一只猴子的尾指针指向第一只猴子
    r->next=head;
    //定义一个指针表示当前报数的是哪一只猴子
    node *q=head;
    for(int i=1;i<n;i++){
        //通过for循环报数m-2只猴子每一次报数将指针往后移动一个，最后停留在m-1只猴子的位置 
        for(int j=1;j<m-1;j++){
            q=q->next;
        }
        //当前这个猴子的后一只需要出圈，将当前尾指针变成指向后一只猴子的尾指针
        q->next=q->next->next;
        //向后移动一只猴子 
        q=q->next;
    }
    //输出最后的猴子 
    cout<<q->data;
    return 0;
}