双向链表

模板题Aizu - ALDS1_3_C

#include<cstdio>
#include<cstring>
#include<cstdlib>

typedef struct Node
{
    int num;
    Node *next,*prev;
}node;

node *head;
void Init()
{
    head=(node*)malloc(sizeof(node));
    head->next=head;
    head->prev=head;
}
void Insert(int num)
{
    node *x=(node *)malloc(sizeof(node));
    x->num=num;
    x->next=head->next;
    head->next->prev=x;
    head->next=x;
    x->prev=head;
}
node *Listsearch(int key)
{
    node *cur=head->next;
    while(cur!=head&&cur->num!=key)
    {
        cur=cur->next;
    }
    return cur;
}
void Deletenode(node *t)
{
    if(t==head) return ;
    t->prev->next=t->next;
    t->next->prev=t->prev;
    free(t);
}
void DeleteFirst()
{
    Deletenode(head->next);
}
void DeleteLast()
{
    Deletenode(head->prev);
}
void deleteKey(int key)
{
    Deletenode(Listsearch(key));
}
void printList()
{
    node *cur=head->next;
    int isf=0;
    while(1)
    {
        if(cur==head) break;
        if(isf++>0) printf(" ");
        printf("%d",cur->num);
        cur=cur->next;
    }
    printf("\n");

}
int main()
{
   int key,n,i;
   int cize=0;
   char com[20];
   int np=0,nd=0;
   scanf("%d",&n);
   Init();
   for(i=0;i<n;i++)
   {
       scanf("%s%d",com,&key);
       if(com[0]=='i') { Insert(key);  np++; cize++;}
       else if( com[0]=='d')
       {
           if(strlen(com)>6)
           {
               if(com[6]=='F') DeleteFirst();
               else if( com[6]=='L') DeleteLast();
           }
           else
           {
               deleteKey(key);
               nd++;
           }
           cize--;
       }
   }
   printList();

   return 0;
}