#include<stdio.h>
#include<stdlib.h>
struct Node
{
    int value;
    struct Node *prior;
    struct Node *next;
 } ;
 typedef struct Node node;
 void menu(void)
 {
     printf("you must initialize first!!!\n");
     printf("menu:\n");
     printf("1.initialization\n");
     printf("2.inserting\n");
     printf("3.deleting\n");
     printf("4.searching\n");
     printf("5.sorting\n");
     printf("6.printlist\n");
     printf("7.addathead\n");//头插
     printf("8.addattail\n");//尾插
     printf("9.addinnumbers\n");//批量添加节点
 }
 int Choice(void)
 {
     int choice=0;
     printf("please input your choice\n");
     scanf("%d",&choice);
     return choice;
 }
 node* initialization(void)
{
    int data;
    node* head=(node*)malloc(sizeof(node));
    printf("please input value\n");
    scanf("%d",&data);
    head->next=NULL;
    head->prior=NULL;
    head->value=data;
    printf("OK!!!\n");
    return head;
}
void printlist(node* head)
{
    node* temp=head;
    if(!head)
        {printf("please initialize first!!!\n");return;}
    printf("your list is:\n");
    while(temp)
    {
        printf("%d ",temp->value);
        temp=temp->next;
    }
    printf("\n");
}
void addathead(node** head)
{
    int data;
    node* newnode=(node*)malloc(sizeof(node));
    printf("please input value:\n");
    scanf("%d",&data);
    newnode->value=data;
    (*head)->prior=newnode;
    newnode->next=*head;
    newnode->prior=NULL;
    *head=newnode;
    printf("adding\n");
}
void addattail(node** head)
{
    int data;
    node* newnode=(node*)malloc(sizeof(node));
    node* temp=*head;
    printf("please input value:\n");
    scanf("%d",&data);
    newnode->value=data;
    newnode->next=NULL;
    while(temp->next)
        temp=temp->next;
    temp->next=newnode;
    newnode->prior=temp;
    printf("adding\n");
}
void add(node** head,int data)
{
    node* newnode=(node*)malloc(sizeof(node));
    newnode->value=data;
    newnode->prior=NULL;
    newnode->next=*head;
    (*head)->prior=newnode;
    *head=newnode;
}
void addinnumbers(node**head)
{
    int number=0,i,*p;
    printf("how many?\n");
    scanf("%d",&number);
    printf("input:");
    p=(int*)malloc(sizeof(int)*number);
    for(i=0;i<number;i++)
    {
        scanf("%d",&p[i]);
        add(head,p[i]);
    }
    printf("please print the list to see\n");
}
int count(node* head)
{
    int cnt=0;
    node* temp=head;
    while(temp)
    {
        cnt++;
        temp=temp->next;
    }
    return cnt;
}
void inserting(node**head)
{
    int location=0,cnt=1;
    int choice=0;
    node *temp=*head,*newnode=(node*)malloc(sizeof(node));
    newnode->prior=NULL;newnode->next=NULL;
    printf("where do you want to insert?");
    scanf("%d",&location);
    if(location<=0||location>count(*head))
        printf("location is not valid\n");
    else
    {
        while(cnt++<location)
            temp=temp->next;
        printf("please input value:");
        scanf("%d",&newnode->value);
        printf("before or after? 1.before 2.after\n");
        scanf("%d",&choice);
        switch(choice)
         {
             case 1:if(location==1)
                     {
                         newnode->next=temp;
                         temp->prior=newnode;
                         *head=newnode;
                     }else
                    {
                        newnode->next=temp;
                        newnode->prior=temp->prior;
                        temp->prior->next=newnode;
                        temp->prior=newnode;
                    }     
                     break;
             case 2:if(location==count(*head))
                     {
                         temp->next=newnode;
                         newnode->prior=temp;
                     }else
                     {
                         newnode->prior=temp;
                         newnode->next=temp->next;
                         temp->next->prior=newnode;
                         temp->next=newnode;
                     }
                     break;
         }
    }
}
void print(node* code)
{
    printf("%d\n",code->value);
}
void searching(node* head)
{
    int choice=0,target,cnt=1;
    node* temp=head;
    printf("search by value or location? 1.value 2.location\n");
    scanf("%d",&choice);
    switch(choice){
        case 1:{
            printf("please input value:\n");
            scanf("%d",&target);
            while(temp)
            {
                if(temp->value==target)
                {
                    printf("here is the result:");
                    print(temp);
                    break;
                }else
                temp=temp->next;
            }
            if(!temp)
                printf("not found such value\n");
            break;
        }
        case 2:{
            printf("please input location\n");
            scanf("%d",&target);
            if(target<0||target>count(head))
                printf("not found such location\n");
            else
            {
                while(cnt++<target)
                    temp=temp->next;
                printf("here is the result:");
                print(temp);
            }
            break;
        }
    }
}
void deleteing(node** head)
{
    int choice=0,target,cnt=1;
    node* temp=*head,*prev;
    printf("how to delete?\n1.delete the whole 2.delete by value 3.delete by location\n");
    printf("if you delete the whole,then you may need to create new list!!!\n");
    scanf("%d",&choice);
    switch(choice)
    {
        case 1:{
            while(temp)
            {
                prev=temp;
                prev->prior=NULL;
                prev->next=NULL;
                free(prev);
                temp=temp->next;
            }
            *head=NULL;
            printf("if you want to go on,initialize first");
            break;
        }
        case 2:{
            printf("please input value\n");
            scanf("%d",&target);
            while(temp)
            {
                printf("deleting.....\n");
                if(temp->value==target)
                {
                    if(!temp->next&&!temp->prior)
                    {
                        *head=NULL;
                        free(temp);
                        temp=*head;
                    }
                    else if(temp->prior==NULL)
                    {
                        *head=temp->next;
                        temp->next->prior=NULL;
                        temp->next=NULL;
                        temp=*head;
                    }else if(temp->next==NULL)
                    {
                        temp->prior->next=NULL;
                        temp->prior=NULL;
                        temp->next=NULL;
                        free(temp);
                        temp=NULL;
                    }
                    else
                    {
                        prev=temp->next;
                        temp->prior->next=temp->next;
                        temp->next->prior=temp->prior;
                        temp->next=NULL;
                        temp->prior=NULL;
                        free(temp);
                        temp=prev;
                    }
                }else
                    temp=temp->next;
            }
            printf("OK!!!\n");
            break;
        }
        case 3:{
            printf("where do you want to delete?");
            scanf("%d",&target);
            if(target<0||target>count(*head))
                printf("not found");
            else if(target==1)
            {
                *head=temp->next;
                temp->next->prior=NULL;
                temp->next=NULL;
                free(temp);
                printf("OK!!!\n");
            }else if(target==count(*head))
            {
                while(temp->next)
                temp=temp->next;
                temp->prior->next=NULL;
                temp->prior=NULL;
                free(temp);
                printf("OK!!!\n");
            }else
            {
                while(cnt++<target)
                    temp=temp->next;
                temp->prior->next=temp->next;
                temp->next->prior=temp->prior;
                temp->next=NULL;
                temp->prior=NULL;
                free(temp);
                printf("OK!!!\n");
            }
            break;
        }
    }
}
void insertinorder(node** head,node* temp)
{
    node* prev=*head;
    if((*head)==NULL)
        *head=temp;
    else if(count(*head)==1)
    {
        if(temp->value<prev->value)
        {
            temp->next=prev;
            prev->prior=temp;
            *head=temp;
        }else
        {
            prev->next=temp;
            temp->prior=prev;
        }
    }else
    {
        while(temp->value>prev->value)
            prev=prev->next;
        if(prev==*head)
        {
            temp->next=prev;
            prev->prior=temp;
            *head=temp;
        }
        else    
        {
            temp->next=prev;
            temp->prior=prev->prior;
            prev->prior->next=temp;
            prev->prior=temp;    
        }    
    }
}
void sorting(node** head)
{
    node* newhead=NULL;
    node *prev=*head,*temp;
    printf("sorting....\n");
    while(prev)
    {
        temp=prev;
        prev=prev->next;
        temp->next=NULL;
        temp->prior=NULL;
        insertinorder(&newhead,temp);
    }
    *head=newhead;
}
 int main()
 {
     menu();
     node* head;
     int flag=1;
     while(flag)
     {
         switch(Choice())
         {
             case 1:head=initialization();break;
             case 2:inserting(&head);break;
             case 3:deleteing(&head);break;
             case 4:searching(head);break;
             case 5:sorting(&head);break;
             case 6:printlist(head);break;
             case 7:addathead(&head);break;
             case 8:addattail(&head);break;
             case 9:addinnumbers(&head);break;
             default:flag=0;break;
         }
     }
     return 0;
 }