数据结构链表约瑟夫（思考题）

Question

请大家帮我看一下问什么输出错误
题目一 joseph环（线性表应用）
　
【问题描述】
编号是1，2，……,n的n个人按照顺时针方向围坐一圈，每个人只有一个密码（正整数）。一开始选一个正整数作为报数上限值m,从第一个人开始顺时针方向自1开始顺序报数，报到m时停止报数。报m的人出列，将他的密码作为新的m值，从他在顺时针方向的下一个人开始重新从1报数，如此下去，直到所有人全部出列为止。设计一个程序来求出出列顺序。
【实现提示】
可以利用顺序结构或循环链表存储结构模拟此过程。顺序结构可以通过取模运算来完成循环报数。

测试数据：m的初值为4，n=7 ,7个人的密码依次为

3，1，7，2，4，7，4.

输出结果为:

4 6 1 5 7 3 2

以下我的代码

```c++

#include <iostream>
using namespace std;
typedef struct Lnode
{
    int code;
    int num;
    struct Lnode* next;
 } Lnode,*Linklist;
 void IntList (Linklist& L)
 {
     L=new Lnode;
     L->next=NULL;
 }
 void CreatList (Linklist& L,int n)
 {
     Lnode* p;
     for(int i=0;i<n;i++)
     {
         p=new Lnode;
         cin>>p->code;
         p->num=i+1;
         p->next=L->next;
         L->next=p;
     }
 }
 bool Listdelete(Linklist& L,int i,int e)
 {
     Linklist p=L;
     Lnode* q;
     int j=0;
     while (p->next&&j<i-1)
     {
         p=p->next;
         j++;
     }
     if(!(p->next)||i<1)
     {
         return false;
     }
     q=p->next;
     p->next=q->next;
     e=q->code;
     cout<<q->num<<" "; 
     delete q;
 }
void Listdelete(Linklist& L,int i,int n,int r)
 {
     bool flag;
     int e;
     flag=Listdelete(L,i,e);
     if(flag)
     {
         r= e;
         n--;//删除成功,e为下一次的前进数目 
     }
 }
 int main()
 {
     Linklist L;
     IntList ( L);
     int n;
     cin>>n;
     CreatList (L,n);
     int k;int e;cin>>k;
     while (L->next != L) {  // 当链表中只剩下一个节点时结束循环
        Listdelete(L, k, n, e);
        // 输出被淘汰的学生编号
        k = (e + k) % n;
        n--;  // 学生人数减一
    }
    cout << L->num;
     
     }

Answer 1

【以下回答由 GPT 生成】

这段代码中存在一些问题，导致输出结果不正确：

1. 在Listdelete函数中，形参e是按值传递的，无法修改实参的值。因此，在函数内部将e赋值给q->code之后，对e的修改不会反映到函数外部。
2. 在Listdelete函数中，需要将删除的节点的num值输出，但是输出的是q->num，实际上应该是p->num，即表示删除节点的上一个节点的num值。
3. 在Listdelete函数的第二个重载中，删除节点成功后，没有更新n的值，导致循环链表的长度没有被正确更新。

此外，代码中存在一些冗余的部分，可以进行简化。

下面是修正后的代码：

#include <iostream>
using namespace std;

typedef struct Lnode
{
    int code;
    int num;
    struct Lnode* next;
} Lnode, *Linklist;

void IntList (Linklist& L)
{
    L = new Lnode;
    L->next = NULL;
}

void CreatList (Linklist& L, int n)
{
    Linklist p = L;
    for(int i=0; i<n; i++)
    {
        Linklist q = new Lnode;
        cin >> q->code;
        q->num = i+1;
        q->next = NULL;
        p->next = q;
        p = q;
    }
    p->next = L->next;
}

bool Listdelete(Linklist& L, int i, int& e)
{
    Linklist p = L;
    int j=0;
    while (p->next && j<i-1)
    {
        p = p->next;
        j++;
    }
    if(!(p->next) || i<1)
    {
        return false;
    }
    Linklist q = p->next;
    p->next = q->next;
    e = q->code;
    cout << p->num << " ";
    delete q;
    return true;
}

void Joseph(Linklist& L, int k)
{
    int n = 0;  // 记录链表的长度
    Linklist p = L;
    while(p->next)
    {
        p = p->next;
        n++;
    }
    int e;
    while(n > 0)
    {
        Listdelete(L, k, e);
        n--;
        k = e;
    }
}

int main()
{
    Linklist L;
    IntList(L);
    int n;
    cin >> n;
    CreatList(L, n);
    int k;
    cin >> k;
    Joseph(L, k);
    return 0;
}

修正后的代码会正确输出删除节点的num值。

【相关推荐】

• 这有个类似的问题, 你可以参考下: https://ask.csdn.net/questions/7706963
• 除此之外, 这篇博客: 【面试题】【剑指offer】给定一个整数数组nums，其中恰好有两个元素只出现一次，其余所有元素均出现两次，请找出只出现一次的那两个元素。中的 显然，要想从ret中拆出独立的两个元素非常困难，我们可以换个思路，既然ret是那两个元素的异或，那么在ret的二进制一个位置上（如M位）为1，必然两个元素（假设为x1，x2）其中一个的M位为1，另一个为0（异或时，相同为0，相异为一，二进制仅有0和1两种表示方法）。想到这里，那我们可以将原先数组中M为1的分成一组，M位为0的分成一组，相同的元素，必然会分到同一组，再让为1的一组全部异或得到其中一个独立元素，M为0的一组全部异或，得到另一个独立元素。 部分也许能够解决你的问题。

如果你已经解决了该问题, 非常希望你能够分享一下解决方案, 写成博客, 将相关链接放在评论区, 以帮助更多的人 ^-^