#include <stdio.h>
#include <stdlib.h>
#include <string.h>
struct Node
{
int content; //存放节点的数字,就是砖块的编号
struct Node *next; //指向堆在自己上面的砖块
int location; //记录自己在第几堆位置上
};
typedef struct Node NODE;
void Clear(int obj,NODE* nodelist[],NODE* location[]) //用于清除上面的砖块,放回原位
{
NODE *temp1;
NODE *temp2;
temp1 = nodelist[obj];
temp2 = temp1;
temp1 = temp1->next;
temp2->next = NULL;
while(temp1 != NULL)
{
int tag;
tag = temp1->content;
location[tag]->next = temp1;
temp2 = temp1;
temp1->location = tag;
temp1 = temp1->next;
temp2->next = NULL;
}
}
void Moveonto(int obj,int objonto,NODE* nodelist[],NODE* location[]) //moveonto
{
NODE* temp;
temp = location[nodelist[obj]->location];
while(temp->next->content != obj)
{
temp = temp->next;
}
temp->next = NULL;
Clear(obj,nodelist,location);
Clear(objonto,nodelist,location);
nodelist[objonto]->next = nodelist[obj];
nodelist[obj]->next = NULL;
nodelist[obj]->location = nodelist[objonto]->location;
}
void Moveover(int obj,int objover,NODE* nodelist[],NODE* location[])
{
NODE* temp;
temp = location[nodelist[obj]->location];
while(temp->next->content != obj)
{
temp = temp->next;
}
temp->next = NULL;
Clear(obj,nodelist,location);
temp = nodelist[objover];
while(temp->next != NULL)
{
temp = temp->next;
}
temp->next = nodelist[obj];
nodelist[obj]->location = nodelist[objover]->location;
}
void Pileonto(int obj,int objonto,NODE* nodelist[],NODE* location[])
{
NODE* temp;
temp = location[nodelist[obj]->location];
while(temp->next->content != obj)
{
temp = temp->next;
}
temp->next = NULL;
Clear(objonto,nodelist,location);
nodelist[objonto]->next = nodelist[obj];
nodelist[obj]->location = nodelist[objonto]->location;
}
void Pileover(int obj,int objover,NODE* nodelist[],NODE* location[])
{
NODE* temp;
temp = location[nodelist[obj]->location];
while(temp->next->content != obj)
{
temp = temp->next;
}
temp->next = NULL;
temp = nodelist[objover];
while(temp->next != NULL)
{
temp = temp->next;
}
temp->next = nodelist[obj];
nodelist[obj]->location = nodelist[objover]->location;
}
void Print(NODE* location[],int size)
{
int i;
NODE* temp;
for(i = 0;i < size;i++)
{
printf("%d:",i);
temp = location[i];
temp = location[i]->next;
while(temp != NULL)
{
printf(" %d",temp->content);
temp = temp->next;
}
printf("\n");
}
}
int main (void)
{
int amount;
char quit[5] = "quit";
char move[5] = "move";
char pile[5] = "pile";
char onto[5] = "onto";
char over[5] = "over";
char string1[5];
char string2[5];
scanf("%d",&amount);
NODE *nodelist[25];
NODE *location[10];
int i;
for(i = 0;i < amount;i++) //每个位置设置个头结点 ,仅用来标记位置
{
location[i] = (NODE*)malloc(sizeof(NODE));
location[i]->next = NULL;
}
for(i = 0;i < amount;i++) //砖块节点集 用于搜索到每个砖块节点
{
nodelist[i] =(NODE*)malloc(sizeof(NODE));
nodelist[i]->content = i;
nodelist[i]->next = NULL;
}
for(i = 0;i < amount;i++)
{
location[i]->next = nodelist[i];
nodelist[i]->location = i;
}
while(scanf("%s",&string1)&&strcmp(string1,quit))//不是quit就继续读
{
int lag;
int op1;
int op2;
scanf("%d %s %d",&op1,&string2,&op2);
if(op1 == op2|| nodelist[op1]->location == nodelist[op2]->location)
{
continue;
}else
{
if(!strcmp(string1,move))
{
lag = 1;
}else
if(!strcmp(string1,pile))
{
lag = 2;
}
switch (lag) //加深switch注意点
{
case 1:
if(!strcmp(string2,onto))
{
Moveonto(op1,op2,nodelist,location);
}else
if(!strcmp(string2,over))
{
Moveover(op1,op2,nodelist,location);
}
break;
case 2:
if(!strcmp(string2,onto))
{
Pileonto(op1,op2,nodelist,location);
}else
if(!strcmp(string2,over))
{
Pileover(op1,op2,nodelist,location);
}
break;
}
}
Print(location,amount); //这是每轮测试用的PRINT提交时删掉
//scanf("%s",&string1); //注意这是错误的
}
Print(location,amount);
return 0 ;
}
我的思想是每个砖块就是一个节点,每个位置有固定的节点代表一个个位置,用了动态链表。自己在测试数据的时候没发现错误,但是出现的TLE,究竟是不是因为错在用动态链表上,导致超时啊,望各位帮忙!