uva 10152 - ShellSort

时间：2011-06-01 来源：加速！！！！！！！！！！

/*
从大到小寻找下标，若该下表的乌龟上方有任意一个乌龟比它的下标大，就移动该乌龟。
*/

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
typedef struct _turtle
{
        char s[100];
        int order;
        struct _turtle *last;
        struct _turtle *next;
}turtle;
char requirted[100];
int main()
{
        int i,K,n,local;
        turtle *p,*pp,*_pp,*head,*now,*end;
        scanf("%d",&K);
        while(K-->0)
        {
                scanf("%d",&n);
                getchar();
                head=NULL;
                p=head;
                for(i=0;i<n;i++)
                {
                        now=(turtle *)malloc(sizeof(turtle));
                        gets(now->s);
                        if(i==0)
                        {
                                head=now;
                                p=now;
                                p->last=NULL;
                        }
                        else
                        {
                                now->last=p;
                                p->next=now;
                                p=p->next;
                        }
                }
                p->next=NULL;
                end=p;
                for(i=0;i<n;i++)
                {
                        gets(requirted);
                        p=head;
                        while(strcmp(p->s,requirted)!=0)
                                p=p->next;
                        p->order=i;
                }
                for(i=n-1;i>=0;i--)
                {
                        
                        p=end;
                        local=n-1;
                        while(p->order!=i)
                        {
                                p=p->last;
                                local--;
                        }
                        pp=p->last;
                        while(pp!=NULL)
                                if(pp->order>i)
                                        break;
                                else
                                        pp=pp->last;
                        if(pp!=NULL)
                        {
                                printf("%s\n",p->s);
                                if(local==n-1)
                                {
                                        end=end->last;
                                        end->next=NULL;
                                        head->last=p;
                                        p->next=head;
                                        head=p;
                                        head->last=NULL;
                                }
                                else
                                {
                                        pp=p->last;
                                        _pp=p->next;
                                        pp->next=_pp;
                                        _pp->last=pp;
                                        p->next=head;
                                        head->last=p;
                                        head=p;
                                        head->last=NULL;
                                }
                        }
                }
                printf("\n");
        }
        return 0;
}