| 查看: 353 | 回复: 2 | |||
[求助]
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; 这一段代码，请高人指点，谢谢~~~ |
回复此楼» 猜你喜欢
体制内长辈说体制内绝大部分一辈子在底层，如同你们一样大部分普通教师忙且收入低
已经有13人回复
-
为什么中国大学工科教授们水了那么多所谓的顶会顶刊，但还是做不出宇树机器人？
已经有8人回复
-
版面费该交吗
已经有8人回复
-
面上可以超过30页吧？
已经有4人回复
-
“人文社科而论，许多学术研究还没有达到民国时期的水平”
已经有5人回复
-
什么是人一生最重要的？
已经有4人回复
-
今年春晚有几个节目很不错，点赞！
已经有12人回复
libralibra
至尊木虫 (著名写手)
骠骑将军
- 程序强帖: 40
- 应助: 817 (博后)
- 金币: 12914.1
- 红花: 64
- 帖子: 2238
- 在线: 287.3小时
- 虫号: 696514
- 注册: 2009-02-05
- 专业: 计算机软件
【答案】应助回帖
感谢参与，应助指数 +1
|
有2个问题,CLinkList<T>::CLinkList(T a[],int n)中这一句 少了[],应是a int main()里面也一样,a = i+1;应该是a 然后看你问的那段代码: 生成一个哑节点(也就是多余的),没有任何数据,用来表示链表结尾.其next指向自身(添加数据后会被删除). 循环添加数据,添加顺序为:生成新节点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. 创建一个指针,指向空节点(rear的下一个),让最后一个非空节点指向头结点.删除空节点.循环链表生成完成. |
2楼2013-06-17 16:41:00
libralibra
至尊木虫 (著名写手)
骠骑将军
- 程序强帖: 40
- 应助: 817 (博后)
- 金币: 12914.1
- 红花: 64
- 帖子: 2238
- 在线: 287.3小时
- 虫号: 696514
- 注册: 2009-02-05
- 专业: 计算机软件
3楼2013-06-17 16:42:26