资讯

精准传达 • 有效沟通

从品牌网站建设到网络营销策划,从策略到执行的一站式服务

实验五A.DS循环链表—约瑟夫环(Ver.I-A)-创新互联

【题目描述】

N个人坐成一个圆环(编号为1 - N),从第S个人开始报数,数到K的人出列,后面的人重新从1开始报数。问最后剩下的人的编号。

创新互联坚信:善待客户,将会成为终身客户。我们能坚持多年,是因为我们一直可值得信赖。我们从不忽悠初访客户,我们用心做好本职工作,不忘初心,方得始终。十余年网站建设经验创新互联是成都老牌网站营销服务商,为您提供网站设计制作、成都网站制作、网站设计、HTML5建站、网站制作、高端网站设计小程序制作服务,给众多知名企业提供过好品质的建站服务。

例如:N = 3,K = 2,S = 1。2号先出列,然后是1号,最后剩下的是3号。

要求使用循环链表实现。

【输入】

测试数据有多组

每组包括3个数N、K、S,表示有N个人,从第S个人开始,数到K出列。(1<= N<= 10^6,1<= K<= 10,  1<= S<= N)

【输出】

出列的人的编号

【输入样 例】

13 3 1
3 2 1

【输出样例】

3 6 9 12 2 7 11 4 10 5 1 8 13
2 1 3

#includeusing namespace std;

class ListNode{
public:
    int data;
    ListNode* next;
    ListNode() {
        next = NULL;
    }
};

class LinkList{
    int len;
    ListNode* head;
public:
    int n, k, s;
    LinkList() {
        head = new ListNode();
    }
    ~LinkList() {
        delete head;
    }
    void CreateList();
    void Test();
};

void LinkList::CreateList()
{
    len = n;//传入len
    ListNode* p = head;//从头结点开始
    ListNode* q;
    for (int i = 1; i<= n; i++)//因为此时插入一个更新一个,所以不存在,之前的插入问题
    {
        q = new ListNode();
        q->data = i;//传入数据
        p->next = q;//指向q这个新结点
        p = p->next;//移动到当前最新的一位
    }
    p->next = head;//构成循环
}

void LinkList::Test()
{
    int i;
    ListNode* p = head;
    for (i = 1; i< s ; i++)//找到要开始的那一位,是index的作用
        p = p->next;
    while (len)//直到出列完成
    {
        if (p->next == head)//删除结点使得p->next为头节点,则p要多移一次。
            p = p->next;
        for (i = 1; i< k; i++)//从1开始报数,报到k-1位
        {
            p = p->next;
            if (p->next == head)//在p向后位移的时候如果遇到头结点,多移一次。
                p = p->next;
        }
        ListNode* q = p->next;//上一个for循环找到了要删除的节点的前一位,这时候用q代表要删除的结点
        cout<< q->data;
        p->next = q->next;//先变指针域,改为删去的节点的下一位
        delete q;
        len--;
        if (len != 0) {
            cout<< " ";
        }
    }
    cout<< endl;
}

int main()
{
    int N, K, S;
    while (cin>>N>>K>>S)
    {
        LinkList myList;
        myList.n = N;
        myList.k = K;
        myList.s = S;
        myList.CreateList();
        myList.Test();
    }
    return 0;
}

你是否还在寻找稳定的海外服务器提供商?创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源,准确流量调度确保服务器高可用性,企业级服务器适合批量采购,新人活动首月15元起,快前往官网查看详情吧


新闻名称:实验五A.DS循环链表—约瑟夫环(Ver.I-A)-创新互联
链接URL:http://cdkjz.cn/article/igghs.html
多年建站经验

多一份参考,总有益处

联系快上网,免费获得专属《策划方案》及报价

咨询相关问题或预约面谈,可以通过以下方式与我们联系

大客户专线   成都:13518219792   座机:028-86922220