Question

c++猴子选大王 找错

#include<iostream.h>
struct node
{
int num;
node *next;
};
node *createList(int);
void search(node *);
void main()
{
int n;
node *listHead=NULL;
cout<<"请输入猴子的个数："<<endl;
cin>>n;
listHead=createList(n);
search(listHead);
}

node *createList(int n)
{
int i;
node *head;
node *newNode=NULL;
node *tail=NULL;
head=new node;
if(head==NULL)
{
cout<<"内存分配失败！"<<endl;
return NULL;
}
else
{
head->num=1;
head->next=NULL;
tail=head;
}
for(i=2;i<=n;i++)
{
newNode=new node;
if(newNode==NULL)
{
cout<<"内存分配失败！"<<endl;
return NULL;
}
else
{
newNode->num=i;
newNode->next=NULL;
tail->next=newNode;
tail=newNode;
}
}
tail->next=head;
return head;
}

void search(node *head)
{
node *curNode=head;
node *preNode=NULL;
int i=1;
while(curNode->next!=curNode)
{
curNode=curNode->next;
preNode=curNode;
i++;
if(i==3)
{
cout<<"被淘汰的猴子为："<<curNode->num<<"号。"<<endl;
preNode->next=curNode->next;
curNode=preNode->next;
i=1;
}
}
cout<<"猴王是："<<preNode->num<<"号。"<<endl;
}

Answer 1

你的意图是建立一个单环链表，然后从链表头开始计数，删除计数为3的节点，重复此过程，直到剩余一个节点。整个过程，建立链表的环节正确，错误在search函数中，其中这两句有问题：
curNode=curNode->next;
preNode=curNode;

此时preNode，不是代表当前节点，而可能是要删除的节点，因为preNode = curNode->next；即下一个节点，正确的代码只需要调正顺序即可，改为：
preNode = curNode;
curNode=curNode->next;
就ok了

Answer 2

以下代码可以正确运行， 错误或者说明在注释中

#include <iostream> //此处不能加.h， iostream是标准库
using namespace std; //要直接使用cout和cin必须要使用名字空间，否则要用std::cin
和std::cout

typedef struct node{ //这儿要使用typedef关键字，以后才能直接用node声明变量，否则
int num; 只能使用 struct node *next这样的方式声明变量
node *next;
}node; //这儿配合 typedef使用，定义node为结构体

node *createList(int);
void search(node *);

void main()
{
int n;
node *listHead = NULL;
cout<<"请输入猴子的个数："<<endl;
cin>>n;
listHead=createList(n);
search(listHead);
}

node *createList(int n)
{
int i;
node *head;
node *newNode=NULL;
node *tail=NULL;
head=new node;
if(head==NULL)
{
cout<<"内存分配失败！"<<endl;
return NULL;
}
else
{
head->num=1;
head->next=NULL;
tail=head;
}

for(i=2;i<=n;i++)
{
newNode=new node;
if(newNode==NULL)
{
cout<<"内存分配失败！"<<endl;
return NULL;
}
else
{
newNode->num=i;
newNode->next=NULL;
tail->next=newNode;
tail=newNode;
}
}
tail->next=head;
return head;
}

void search(node *head)
{
node *curNode=head;
node *preNode=NULL;
int i=1;
while(curNode->next!=curNode)
{
preNode=curNode; //此处要首先给preNode赋值，否则curNode==
curNode=curNode->next; // preNode了，逻辑上是错的

i++;
if(i==3)
{
cout<<"淘汰的猴子为："<<curNode->num<<"号。"<<endl;
preNode->next=curNode->next;
delete curNode; //无用的内存记得释放
curNode=preNode->next;
i=1;
}
}
cout<<"猴王是："<<preNode->num<<"号。"<<endl;
}