实验五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)-创新互联
文章地址：http://wjwzjz.com/article/igghs.html