主题:明天要交C++作业,可我不知道程序哪里出问题了
ritashenminyan
[专家分:0] 发布于 2010-07-15 21:43:00
设计一个环链表类模板,提供必要的环链表操作,最后用于解决约瑟夫(Josephus)问题。
这是题目
问题应该是 头文件最后那个CirclrLink那里
谢谢好心人帮我看看啊!
我QQ263119035
最后更新于:2010-07-15 21:50:00
回复列表 (共3个回复)
沙发
cgl_lgs [专家分:21040] 发布于 2010-07-16 05:55:00
问题挺多,首先语法上就有问题,然后编译通过了之后发现您写的链表类竟然很多地方都不支持环形链~~~~
板凳
cgl_lgs [专家分:21040] 发布于 2010-07-16 06:04:00
[code=c]
// hxx修改的部分:)
template <typename T> LinkList<T>::LinkList()
{
num = 0;
head = cur_node = NULL;
}
template <typename T> LinkList<T>::LinkList(const T*t,int n)
{
Node<T> *p;
head = NULL;
for(int i=n-1; i>=0; i--)
{
p = new Node<T>(t[i]);
p->next = head;
head = p;
}
num = n;
cur_node = head;
}
template <typename T>
LinkList<T>::LinkList(const LinkList<T> &list)
{
Node<T> *p, *pTail, *temp=list.head;
if((num=list.num)==0)
{
head = cur_node = NULL;
return;
}
head = pTail = new Node<T>(list.head->data);
if(list.head == list.cur_node) cur_node = head;
for(int i=1; i<num; i++)
{
temp = temp->next;
p = new Node<T>(temp->data);
if(temp == list.cur_node) cur_node = p;
pTail->next = p;
pTail = p;
}
pTail->next = NULL;
}
template <typename T> LinkList<T>::~LinkList()
{
FreeList();
cout << "析构一条链表。" << endl;
}
template <typename T>
typename LinkList<T>::Node<T> *LinkList<T>::GoTop()
{
return cur_node = head;
}
template <typename T>
typename LinkList<T>::Node<T> *LinkList<T>::Go(int n)
{
if((cur_node=head) == NULL) return cur_node;
for(int i=0; i<n && cur_node!=NULL; i++)
cur_node = cur_node->next;
return cur_node;
}
template <typename T>
typename LinkList<T>::Node<T> *LinkList<T>::GoBottom()
{
if((cur_node=head) == NULL) return cur_node;
while(cur_node->next!=NULL)
cur_node = cur_node->next;
return cur_node;
}
template <typename T>
typename LinkList<T>::Node<T> *LinkList<T>::Skip(int n)
{
int i;
if(n > 0)
{
for(i=0; i<n && cur_node!=NULL; i++)
cur_node = cur_node->next;
}
else if(n < 0)
{
int m = CurPos() + n;
cur_node = (m < 0) ? NULL : Go(m);
}
return cur_node;
}
template <typename T> typename LinkList<T>::Node<T> *
LinkList<T>::Locate(const T &t, bool restart)
{
static Node<T> *p = head; // 局部静态指针变量
if(head==NULL) return cur_node=NULL;
if(restart) p = head;
while(p!=NULL && p->data != t)
p = p->next;
cur_node = p;
if(p!=NULL) p = p->next;
return cur_node;
}
template <typename T>
typename LinkList<T>::Node<T> *LinkList<T>::CurNode() const
{
return cur_node;
}
template <typename T> void LinkList<T>::DeleteCurNode()
{
if(cur_node==NULL) return;
Node<T> *pGuard = head;
while(pGuard->next!=NULL && pGuard->next!=cur_node)
pGuard = pGuard->next;
if(cur_node==head)
{
num--;
head = head->next;
if (head==cur_node) head = NULL;
delete cur_node;
cur_node = head;
if (pGuard != NULL && head != NULL) pGuard->next = head;
return;
}
if(pGuard->next != NULL)
{
num--;
pGuard->next = cur_node->next;
delete cur_node;
cur_node = pGuard->next;
}
}
template <typename T> void LinkList<T>::FreeList()
{
Node<T> *p;
while(head!=NULL)
{
p = head;
head = head->next;
if (head==p)head=NULL;
delete p;
}
cur_node = NULL;
num = 0;
}
template <typename T>
void LinkList<T>::ShowList(int LinePerNode) const
{
if(LinePerNode==0) cout << "head";
Node<T> *p=head;
while ( p!=NULL )
{
if(LinePerNode==0)
cout << (p==cur_node ? " ★ " : " → ")
<< p->data;
else
cout << (p==cur_node ? "★" : " ")
<< p->data << endl;
p=p->next;
if (p==head)break; // 防止出现环状数据
}
if(LinePerNode==0) cout << " → NULL" << endl;
}
[/code]
3 楼
cgl_lgs [专家分:21040] 发布于 2010-07-16 06:06:00
[code=c]//cpp部分
int Josephus(int num , int interval)
{
LinkList<int> Jose;
int i,j,win;
for(i=1;i<=num;i++)
Jose.Append(i);
cout<<" 初始状态 ";
Jose.CircleLink(); // 之前版本还没数据就生成环形链~~~~
for(Jose.GoTop();Jose.NumNodes()>1; )
{
Jose.ShowList();
getch();
for(j=1;j<interval;j++)
{
Jose.Skip();
}
Jose.ShowCurData();
cout<<" 号出圈.";
Jose.DeleteCurNode();
}
Jose.ShowList();
win=Jose.CurData();
return win;
}
[/code]
我来回复