Question

C++ 单向循环链表

循环依次删除第3个数，例如n=6，显示结果为：
123456 列出列表
12456 删除第三个数，即删除数字3，继续读数
1245 删除第三个数，即删除数字6，继续读数
125 删除第三个数，即删除数字5，继续读数
15 删除第三个数，即删除数字2，继续读数
1 删除第三个数，即删除数字5，cout<<"1为最后结果"；

出学者，求过程。

Answer 1

我实在不知道你们这个题目是什么意思，竟然继承链表来实现队列，帮你实现了，VC6.0通过
//list.h
#ifndef LIST_H
#define LIST_H
#include<iostream>
using namespace std;
struct Node
{
int data;
Node *next;
};
class List
{
public:
List();
~List();
List(List&rhs);
List &operator=(List&);
int operator >>(int x);//让>>从尾部输入x
int operator <<(int x);//让<<删除x
virtual void push(int x);
void push(int x,int idx);
void deletex (int x);
virtual void pop();
virtual int top();
bool empty();
int get_num()
{
return m_nNum;
}
Node *get_head()
{
return m_pHead;
}
protected:
int m_nNum;
Node *m_pHead;
};
List::List()
{
m_nNum=0;
m_pHead=new Node;
m_pHead->data=NULL;
m_pHead->next=NULL;
}
List::List(List&rhs)
{

if(this->get_num!=rhs.get_num)
{
cout<<"链变大小不同，不能复制"<<endl;
}
else
{
Node*tmp1=m_pHead->next ;
Node*tmp2=rhs.m_pHead->next;
while(tmp1!=m_pHead)
{
tmp1->data=tmp2->data;
tmp1=tmp1->next;
tmp2=tmp2->next;

}

}
}
List&List::operator=(List&rhs)
{
if(this->get_num()!=rhs.get_num())
{
cout<<"链变大小不同，不能复制"<<endl;
}
else
{
Node*tmp1=m_pHead->next ;
Node*tmp2=rhs.m_pHead->next;
while(tmp1!=m_pHead)
{
tmp1->data=tmp2->data;
tmp1=tmp1->next;
tmp2=tmp2->next;

}

}
return *this;

}
List::~List()//释放所有的内存
{
Node *i=m_pHead->next;
while(i!=m_pHead)
{
Node *j=i->next;
delete i;
i=j;
}
delete m_pHead;
}
void List::pop()
{
if(empty())
{
cout<<"链表为空"<<endl;
return ;
}
else
{
Node*tmp=m_pHead->next->next ;
delete m_pHead->next ;
m_pHead->next=tmp;
--m_nNum;
return;

}

}
void List::push(const int x,const int idx)//在idx位置后插入x
{

if(m_nNum==0)
{
Node *idx_node=new Node;
m_pHead->next=idx_node;
idx_node->data=x;
idx_node->next=m_pHead;

}
else
{
Node *tmp=m_pHead;
for(int i=0;i<idx;++i)
{
tmp=tmp->next;

}
Node *tmpnext=tmp->next;
Node *idx_node=new Node;
tmp->next=idx_node;
idx_node->data=x;
idx_node->next=tmpnext;
}
++m_nNum;
}
void List::push(const int x)
{
push(x,m_nNum);
}
void List::deletex (int x)//删除值为x的所有点
{
Node *tmp=m_pHead;
int idx=0;
while(idx<m_nNum)
{
Node *preNode=tmp;
tmp=tmp->next;
if(tmp->data==x)
{
Node*tmpNext=tmp->next;
tmp->next=tmpNext;
delete tmp;
tmp=tmpNext;
++idx;
}
tmp=tmp->next;
++idx;

}

}
inline int List::top ()
{
if(empty())
{
cout<<"空链表"<<endl;
return false;
}
return m_pHead->next->data ;

}
inline bool List::empty()
{
return m_nNum==0;
}
int List::operator <<(int x)
{
deletex(x);
return 0;
}
int List::operator >>(int x)
{
push(x);
return 0;
}
#endif
////deque.h
#ifndef QUEUE_H
#define QUEUE_H
#include "list.h"
class Queue:public List
{
public:
Queue(){}
Queue(Queue&);

virtual void pop();
virtual void push(int x);
virtual int top();

};
Queue::Queue(Queue&rhs)
{
if(this->get_num!=rhs.get_num)
{
cout<<"队列大小不同，不能复制"<<endl;
}
else
{
Node*tmp1=m_pHead->next ;
Node*tmp2=rhs.m_pHead->next;
while(tmp1!=m_pHead)
{
tmp1->data=tmp2->data;
tmp1=tmp1->next;
tmp2=tmp2->next;
}
}
}
void Queue::pop()
{
if(empty())
{
cout<<"队列为空"<<endl;
return ;
}
else
{
Node*tmp=m_pHead->next->next ;
delete m_pHead->next ;
m_pHead->next=tmp;
return;
--m_nNum;
}

}
int Queue::top()
{
if(empty())
{
cout<<"队列为空"<<endl;
return false;
}
return m_pHead->next->data ;

}
void Queue::push(int x)
{
Node *new_node=new Node;
Node *tmp=m_pHead;
for(int i=0;i<m_nNum;++i)
{
tmp=tmp->next;
}
tmp->next=new_node;
new_node->next =m_pHead;
new_node->data =x;
++m_nNum;
}
#endif
///main.cpp
/*--------------------------
这个主函数用于测试list
#include"list.h"
#include<iostream>
using namespace std;
int main()
{
List xx;
if(xx.empty())
cout<<"空"<<endl;
for(int i=0;i<3;++i)
xx.push(i);
cout<<xx.top()<<endl;
xx.pop();
cout<<xx.top()<<endl;

return 0;

}
-----------------------------------*/

#include "queue.h"
#include<iostream>
using namespace std;
int main()
{
List *xx=new Queue;//检验多态
xx->pop();
for(int i=0;i<3;++i)
xx->push(i);
cout<<xx->top()<<endl;
xx->pop();
cout<<xx->top()<<endl;
return 0;

}

Answer 2

123456 列出列表
12456 删除第三个数，即删除数字3，继续读数
1245 删除第三个数，即删除数字6，继续读数，，应该删除4而不是6，乘下1256
125 删除第三个数，即删除数字5，继续读数，，上次的1256，应该删除5，乘126
15 删除第三个数，即删除数字2，继续读数，，上次的126，应该删除6，乘12，此时已经不够3个数了，无法符合删除条件，所以最后的结果应为：12，而不是1
1 删除第三个数，即删除数字5，cout<<"1为最后结果"；

追问

....完全不对路子！循环列表！
123456
12456
1245
125
15
1
这6个数字只是占位。你可以把这6个数字看成6个人，做游戏！从第一人开始数到第三个人，把第三个人踢出队伍，然后从他后面一个人开始再数三个人，这第三个人再踢出队伍，数到队伍尾端了再回到第一个人继续，成为一个循环链，最后剩下的一个人就是赢家！用C++的循环列表实现！

Answer 3

按照我的理解，你要求过程，所以我只写了删除的过程
print(link *point)
{cout<<point->data;//这是根据你的语言环境的输出
}
void delete(link *head,int n)
{link *p,*q; int i=0;
p=head;
while (p!=p->next && i<n)
{q=p;p=p->next;i++;
if (i==n)
{print(p);
q->next=p->next;
p=q->next;
i=0;}
}
head=p;
print(head);
}

Answer 4

使用全局变量会使程序的可读性下降。你可以操作指针来实现你说的数据传送。就是你在任务中把要给子函数处理的数据用指针传给子函数。用数据的指针去当形参就行了，在子函数中修改数据。。。

Answer 5

这是个约瑟夫环问题，在百度知道里搜索“约瑟夫环”，答案一大堆。