#include<stdio.h>
#include<time.h>
typedef struct _DNode
{
    int data;
    struct _DNode* prev;
    struct _DNode* next;
}DNode;

DNode* CreateDNodeList()
{
    DNode* head=(DNode*)malloc(sizeof(DNode));
    if(NULL==head)
        exit(-1);
    head->next=head->prev=head;
    return head;
}

void InsertDNode(DNode* head,int data)
{
   DNode* cur=(DNode*)malloc(sizeof(DNode));
   if(NULL==cur)
       exit(-1);
   cur->data=data;
   cur->next=head->next;
   cur->prev=head;
   cur->prev->next=cur;
   cur->next->prev=cur;
}

int GetLen(DNode* head)
{
    DNode* tmp=head->next;
    int count=0;
    while(tmp->next!=head)
    {
        count++;
        tmp=tmp->next;
    }
    return count;
}

void TraverseDNodeList(DNode* head)
{
    DNode* cur=head;
    while(cur->next!=head)
    {
        printf("%d\t",cur->next->data);
        cur=cur->next;
    }
    printf("\n");
}

void DeleteDNode(DNode* pfind)
{
    pfind->prev->next=pfind->next;
    pfind->next->prev=pfind->prev;
    free(pfind);
}

void DestroyDNodeList(DNode* head)
{
    DNode* cur;
    while(head)
    {
        cur  = head;
        head = head->next;
        free(cur);
    }
}

void popSortDNodeList(DNode *head)
{
    DNode* p,*q,*cur;
    int    len = GetLen(head);
    for(int i=0;i<len-1;i++)
    {
        p=head->next;
        q=p->next;
        for(int j=0;j<len-1-i;j++)
        {
            if(p->data>q->data)
            {
                p->prev->next=q;
                p->next->prev=p->prev;
                p->next=q->next;
                p->prev=q;
                p->next->prev=p;
                p->prev->next=p;
                q=p->next;
                continue;
            }
            p=p->next;
            q=q->next;
        }
    }
}

DNode* SearchDNodeList(DNode *head,int data)
{
    DNode* clock=head->next,*unclock=head->prev;
    while(unclock!=clock->prev)
    {
        if(clock->data==data)
        return clock;
        if(unclock->data==data)
        return unclock;
        if(clock==unclock)
           break;
        clock=clock->next;
        unclock=unclock->prev;
    }
}

int main()
{
    DNode* head=CreateDNodeList();
    srand(time(NULL));
    //printf("随机插入十个元素:");
    for(int i=0;i<10;i++)
    {
        InsertDNode(head,rand()%10);
    }

    TraverseDNodeList(head);
    printf("操作说明:\n1.增加元素\n2.查找元素\n3.删除元素\n4.遍历双向链表\n5.销毁链表\n6.链表排序\n");

    int temp;
    while(1)
    {
        int num;
        printf("请输入操作\n");
        scanf("%d",&num);

    switch (num)
    {
    case 1:
        printf("请输入要添加的元素\n");
        scanf("%d",&temp);
        InsertDNode(head,temp);
        break;
    case 2:
        printf("请输入要查找的元素\n");
        scanf("%d",&temp);
        DNode* cur=SearchDNodeList(head,temp);
        if(cur)
        {
            printf("找到\n");
        }
        break;
    case 3:
        printf("请输入要删除的元素\n");
        scanf("%d",&temp);
        DNode* cur1=SearchDNodeList(head,temp);
        if(cur1)
        {
            DeleteDNode(cur1);
        }
        break;
    case 4:
        TraverseDNodeList(head);
        break;
    case 5:
        DestroyDNodeList(head);
        break;
    case 6:
        popSortDNodeList(head);
        break;
    }
    }



    return 0;
}