// 该程序使用带头结点的双向循环链表// 交换节点进行排序//补充：locate & Insert#include 
     
      #include 
      
       typedef struct _Node{    int data;    struct _Node *next;    struct _Node *prior;}DNode;DNode *createList(){    DNode *head=(DNode *)malloc(sizeof(DNode));    head->next=head->prior=head;    return head;}//头是固定的使用头插法比较方便void insertList(DNode *head,int data){    DNode *p=(DNode *)malloc(sizeof(DNode));    p->data=data;    p->next=head->next;         //先改变p的指向，不影响原链表的指向关系    p->prior=head;    p->prior->next=p;              //利用已有的双向关系进行修改    p->next->prior=p;}void traverseDList(DNode *head){    DNode *p=head->next;    DNode *p2=NULL;    printf("Traverse:");    while(p!=head){        printf("%d ",p->data);        p2=p;        p=p->next;    }    printf("\n");    //Reverse#if 1    printf("Reverse:");    while(p2!=head){        printf("%d ",p2->data);        p2=p2->prior;    }    printf("\n");#endif}void searchElem(DNode *head,int n){    DNode *p=head->next;    int flag=0;    while(p!=head){        if(p->data==n){            flag=1;            printf("Find elem addr:%p\n",p);        }        p=p->next;    }    if(!flag){        printf("Can not find elem %d !",n);    }}int deleteElem(DNode *head,int n){    DNode *p1=head->next;    DNode *p2=head;    while(p1!=head){        if(p1->data==n){            //delete elem            p2->next=p1->next;            p1->next->prior=p2;            free(p1);            printf("delete %d !\n",n);            return 1;        }        p2=p1;        p1=p1->next;    }    return 0;}void swapNode(DNode *p2,DNode *p1){  //交换p2和它的下一个节点    p2->prior->next=p1;    p2->next=p1->next;    p1->next=p2;        p1->prior=p2->prior;    p2->next->prior=p2;    p2->prior=p1;}#if 1int listNESort(DNode *head){         //先按从大到小排。小的(上浮)至尾部    int flag;    DNode *p1,*p2;    p1=head->next;    for(p1=p1->next;p1!=head;){        flag=1;        for(p2=head->next;p2!=p1;p2=p2->next){            if((p2->data) > (p2->next->data)){                swapNode(p2,p2->next);                flag=0;                if(p1->next==p2)              //交换p2和p2->next后，p1位置可能也变了                    p1=p1->next;                //先把p1换回去，恢复p1在前p2在后                p2=p2->prior;                   //p2退回去                //traverseDList(head);               }        }        if(flag)p1=p1->next;                //printf("2.p2:%d ,p1:%d\n",p2->data,p1->data);     }}#endif//void listDESort(DNode *head){  //Excheange Data//}int main(){    DNode *head=createList();    int i;    for(i=1;i<=10;i++){        insertList(head,i);    }#if 0    insertList(head,1);    insertList(head,3);    insertList(head,5);    insertList(head,7);    insertList(head,2);    insertList(head,4);    insertList(head,6);    insertList(head,8);#endif#if 0    int find=7;    searchElem(head,find);    deleteElem(head,5);    traverseDList(head);#endif#if 0    DNode *p=head->next;    p=p->next;    p=p->next;    swapNode(p,p->next);#endif    listNESort(head);    traverseDList(head);    return 0;}