2 qq 33825615 qq_33825615 于 2016.09.21 15:50 提问

POJ 1208 砖块问题。超时了

图片说明

 #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,究竟是不是因为错在用动态链表上,导致超时啊,望各位帮忙!

1个回答

zqbnqsdsmd
zqbnqsdsmd   2016.09.28 01:03
Csdn user default icon
上传中...
上传图片
插入图片
准确详细的回答,更有利于被提问者采纳,从而获得C币。复制、灌水、广告等回答会被删除,是时候展现真正的技术了!