24小时热门版块排行榜

返回列表

冰雨hust

铁虫 (小有名气)

应助: 0 (幼儿园)
金币: 796.3
红花: 1
帖子: 106
在线: 23.8小时
虫号: 1651706
注册: 2012-02-29
专业: 半导体材料

[求助] C++数据结构循环链表约瑟夫问题

#include <iostream>
using namespace std;

template <class T>
struct Node
{
T data;
Node<T> *next;
};

template <class T>
class CLinkList
{
public:
CLinkList(){rear=new Node<T>;rear->next=rear;}
CLinkList(T a[],int n);
int Josephus(int m,int n);
private:
Node <T> *rear;
};

template <class T>
CLinkList<T>::CLinkList(T a[],int n)
{
rear=new Node<T>;
rear->next=rear;
for (int i=0;i<n;i++)
{
Node <T>*s=new Node <T>;
s->data = a;
s->next = rear->next;
rear->next = s;
rear = s;
}
Node <T>*p = rear->next;
rear->next = p->next;
delete p;
}

template <class T>
int CLinkList<T>::Josephus(int m,int n)
{
int x,i;
Node <T>*p=rear->next;
if (n==1||m==1)
{
x=n;
}
else
{
while(n!=1)
{
i=1;
while (p&&i!=(m-1))
{
p=p->next;
i++;
}
Node <T> *q = p->next;
p->next = q->next;
delete q;
p = p->next;
n--;
}
rear=p;
x=p->data;
}
return x;
}

int main()
{
int M,N,a[1024];
cout<<"the number of people:";
cin>>N;
if (N>=1024)
{
cout<<"Error!Please put in a smaller number.";
return 0;
}
cout<<"the number they count:";
cin>>M;
if (M<=0)
{
cout<<"Error!Please put in a positive number:";
return 0;
}
for (int i=0;i<N;i++)
{
a = i+1;
}
CLinkList<int> A(a,N);
cout<<"the last number is:"<<A.Josephus(M,N)<<endl;
return 0;
}

我不知道在template <class T>
CLinkList<T>::CLinkList(T a[],int n)的最后为啥要加上：
Node <T>*p = rear->next;
rear->next = p->next;
delete p;
这一段代码，请高人指点，谢谢~~~

回复此楼

» 猜你喜欢

为什么nbs上溴没有产物点出现呢已经有6人回复
拟解决的关键科学问题还要不要写已经有8人回复
求推荐博导已经有4人回复
存款400万可以在学校里躺平吗已经有34人回复
求助一下有机合成大神已经有4人回复
最失望的一年已经有16人回复
求推荐英文EI期刊已经有5人回复
26申博已经有3人回复
基金委咋了？2026年的指南还没有出来？已经有10人回复
疑惑？已经有5人回复

1楼 2013-06-14 22:06:33

已阅回复此楼关注TA 给TA发消息送TA红花 TA的回帖

libralibra

至尊木虫 (著名写手)

骠骑将军

程序强帖: 40
应助: 817 (博后)
金币: 12914.1
红花: 64
帖子: 2238
在线: 287.3小时
虫号: 696514
注册: 2009-02-05
专业: 计算机软件

【答案】应助回帖

感谢参与，应助指数 +1

有2个问题,CLinkList<T>::CLinkList(T a[],int n)中这一句

CODE:

 s->data = a; 

少了[],应是a
int main()里面也一样,a = i+1;应该是a

然后看你问的那段代码:
CODE:
CLinkList<T>::CLinkList(T a[],int n)
{
      rear=new Node<T>;
      rear->next=rear;

生成一个哑节点(也就是多余的),没有任何数据,用来表示链表结尾.其next指向自身(添加数据后会被删除).
CODE:
      for (int i=0;i<n;i++)
      {
            Node <T>*s=new Node <T>;
            s->data = a;
            s->next = rear->next;
            rear->next = s;
            rear = s;
      }

循环添加数据,添加顺序为:生成新节点s,给s数据赋值,s指向next哑节点rear,哑节点next指向s,然后移动rear指针到新节点s(这时候所谓的rear其实变成了最后一个非空结点),画图就是:
添加前只有rear:
[rear][null][next]
↑___________|
添加后(只加一个),有2个元素,s1和rear:
[s1(循环最后一句赋值后变成rear)][data][next] ----→ [原rear(复制后没有指针指向这里,只能通过新的rear的next访问)][null][next]
↑_______________________________________________________________________________________________________|
添加2个后变成s1和s2和rear
[s1][data][next]  ---→  [s2(新的rear)][data][next]  ---→ [原rear][null][next]
↑___________________________________________________________|
循环下去可以看到,rear永远指向最后一个非空节点,也就是新添加的那个s.
CODE:
      Node <T>*p = rear->next;
      rear->next = p->next;
      delete p;
}

创建一个指针,指向空节点(rear的下一个),让最后一个非空节点指向头结点.删除空节点.循环链表生成完成.