/* 双向链表的基本操作
 * 创建链表、遍历（打印）、求长度、排序、插入、删除、查找
 */

#include <stdio.h> 
#include <stdlib.h> 
 
typedef struct Node 
{ 
    int data; 
    struct Node * next; 
    struct Node * prior; 
}NODE, *PNODE; 
 
PNODE create_list(void);    //创建节点 
void traverse_list(PNODE pHead);    //遍历链表（打印） 
int length_list(PNODE pHead);        //求链表长度 
void sort_list(PNODE pHead);        //排序 
void insert_list(PNODE pHead, int pos, int val);        //插入节点 
void delect_list(PNODE pHead, int pos, int *val);    //删除节点 
int find_list(PNODE pHead, int val,int *pos);        //查找元素 
 
int main(int argc, char* argv[]) 
{ 
    int pos_insert; 
    int val_insert; 
    int pos_delect; 
    int val_delect; 
    int pos_find; 
    int val_find; 
 
    PNODE pHead = NULL; 
 
    pHead = create_list(); 
    printf("/n原来链表：/n"); 
    traverse_list(pHead); 
    printf("链表的长度是：%d/n",length_list(pHead)); 
    printf("/n"); 
 
    printf("请输入您要插入的元素位置：pos = "); 
    scanf("%d",&pos_insert); 
    printf("请输入您要插入的元素值：val = "); 
    scanf("%d",&val_insert); 
    printf("插入元素后：/n"); 
    insert_list(pHead, pos_insert, val_insert); 
    traverse_list(pHead); 
    printf("链表的长度是：%d/n",length_list(pHead)); 
    printf("/n"); 
 
    printf("请输入您要删除的元素位置：pos = "); 
    scanf("%d",&pos_delect); 
    printf("删除元素后：/n"); 
    delect_list(pHead, pos_delect, &val_delect); 
    traverse_list(pHead); 
    printf("链表的长度是：%d/n",length_list(pHead)); 
    printf("您删除的节点元素是：%d/n",val_delect); 
    printf("/n"); 
 
    printf("请输入您要查找的元素的值：val = "); 
    scanf("%d",&val_find); 
    printf("查找元素：/n"); 
    if(find_list(pHead, val_find, &pos_find) == 0) 
    { 
        traverse_list(pHead); 
        printf("您要查找的元素位置是：%d/n", pos_find); 
        printf("/n"); 
    } 
    else 
        printf("您要查找的元素不存在！/n"); 
    printf("/n"); 
 
    printf("排序后：/n"); 
    sort_list(pHead); 
    traverse_list(pHead); 
    printf("链表的长度是：%d/n",length_list(pHead)); 
    printf("/n"); 
 
    return 0; 
} 
 
PNODE create_list(void) 
{ 
    int len; 
    int i, val; 
    PNODE pTail; 
 
    PNODE pHead = (PNODE)malloc(sizeof(NODE)); 
    if(NULL == pHead) 
    { 
        printf("动态内存分配失败，程序终止！/n"); 
        exit(-1); 
    } 
    pTail = pHead; 
    pTail->next = NULL; 
 
    printf("请输入您要创建链表的长度：/nlen = "); 
    scanf("%d",&len); 
 
    for(i = 0; i < len; i++) 
    { 
        printf("请输入第%d个节点的值：val = ", i+1); 
        scanf("%d",&val); 
 
        PNODE pNew = (PNODE)malloc(sizeof(NODE)); 
        if(NULL == pNew) 
        { 
            printf("新节点动态内存分配失败，程序终止！/n"); 
            exit(-1); 
        } 
        pNew->data = val; 
        pTail->next = pNew; 
        pTail = pNew->prior; 
        pNew->next = NULL; 
        pTail = pNew; 
    } 
    return pHead; 
} 
 
void traverse_list(PNODE pHead) 
{ 
    PNODE p; 
    p = pHead->next; 
    if(NULL == p) 
    { 
        printf("链表为空！/n"); 
    } 
    while(NULL != p) 
    { 
        printf("%d  ",p->data); 
        p = p->next; 
    } 
    printf("/n"); 
 
    return; 
} 
 
int length_list(PNODE pHead) 
{ 
    int len = 0; 
    PNODE p; 
    p = pHead; 
 
    while(NULL != p) 
    { 
        len++; 
        p = p->next; 
    } 
    return len-1; 
 
} 
 
void sort_list(PNODE pHead) 
{ 
    int len, i, j, temp; 
    PNODE p, q; 
 
    len = length_list(pHead); 
 
    for(i = 0,p = pHead->next; i < len; i++,p = p->next) 
    { 
        for(j = i+1, q = p->next; j < len; j++, q = q->next) 
        { 
            if(p->data > q->data) 
            { 
                temp = p->data; 
                p->data = q->data; 
                q->data = temp; 
            } 
        } 
    } 
    return; 
} 
 
void insert_list(PNODE pHead, int pos, int val) 
{ 
    int i; 
    PNODE pNew, p; 
    p = pHead; 
 
    pNew = (PNODE)malloc(sizeof(NODE)); 
    if(NULL == pNew) 
    { 
        printf("新节点动态内存分配失败，程序终止！/n"); 
        exit(-1); 
    } 
    pNew->data = val; 
 
    if((pos > (length_list(pHead)+1)) || (pos <= 0)) 
    { 
        printf("插入失败，插入位置不正确！/n"); 
        exit(-1); 
    } 
    for(i = 0; i < pos-1; i++) 
    { 
        p = p->next; 
    } 
    pNew->next = p->next; 
    p->next = pNew; 
    p = pNew->prior; 
 
    return; 
} 
 
void delect_list(PNODE pHead, int pos, int *val) 
{ 
    int i; 
    PNODE p = pHead; 
 
    if(length_list(pHead) == 0) 
    { 
        printf("链表为空，没有内容可以删除！/n"); 
        exit(-1); 
    } 
    if((pos > length_list(pHead)) || (pos <= 0)) 
    { 
        printf("删除元素的位置不是合法位置，删除失败！/n"); 
        exit(-1); 
    } 
    for(i = 0; i < pos-1; i++) 
    { 
        p = p->next; 
    } 
    if(NULL == p->next->next) 
    { 
        *val = p->next->data; 
        p->next = NULL; 
    } 
    else if(NULL == p->next->next->next) 
    { 
        *val = p->next->data; 
        p->next->next = NULL; 
        
    } 
    else 
    { 
        *val = p->next->data; 
        p->next = p->next->next; 
        p->next->next->prior = p; 
    } 
 
    return; 
} 
 
int find_list(PNODE pHead, int val,int *pos) 
{ 
    PNODE p = pHead; 
    int i = 0; 
 
    while(p != NULL) 
    { 
        i++; 
        if(p->data == val) 
        { 
            *pos = i-1; 
            return 0; 
        } 
        p = p->next; 
    } 
    return 1; 
}