#include <stdio.h>
#include <stdlib.h>

/**
* 含头节点双向链表定义及有关操作
*/

//操作函数用到的状态码 
#define TRUE 1;
#define FALSE 0;
#define OK 1;
#define ERROR 0;

//Status是新定义的一种函数返回值类型，其值为int型，意义为函数结果 状态码 
typedef int Status;
//定义一种 数据元素 类型,为表示方便，定义为char型 
typedef char ElemType;

//双向链表的定义
typedef struct DuLnode {
    ElemType data;
    struct DuLnode *next,*prior;
} DuLnode, *DuLinkList;

//操作1：双向链表初始化
Status InitList(DuLinkList *list){
    (*list)=(DuLinkList)malloc(sizeof(DuLnode));
    (*list)->prior=NULL;
    (*list)->next=NULL;
    return OK;
}

//操作2：头插法建立双向链表，数据保存在ElemType类型的数组中
Status CreateList_H(DuLinkList *list,ElemType arrData[],int length){
    int j;
    for(j=length-1;j>=0;j--){
        //新建结点并分配空间
        DuLnode *node;
        node=(DuLnode*)malloc(sizeof(DuLnode));
        node->data=arrData[j];
        node->prior=NULL;
        node->next=NULL;
        
        //插入为1号结点
        node->next=(*list)->next;
        node->prior=(*list);
        if((*list)->next){  //第一个结点已存在
            (*list)->next->prior=node;
        }
        (*list)->next=node;
    }
    return OK;
}

//操作3：尾插法建立双向链表
Status CreateList_R(DuLinkList *list,ElemType arrData[],int length) {
    int j;
    DuLnode *r;    //尾指针
    r=*list;
    for(j=0;j<length;j++) {
        DuLnode *node;
        node=(DuLnode*)malloc(sizeof(DuLnode));
        node->data=arrData[j];
        node->prior=NULL;
        node->next=NULL;
        
        //插入表尾
        r->next=node;
        node->prior=r;
        r=node;  //r指向尾结点
    }
    return OK; 
} 

//操作4：双向链表元素遍历输出
Status ListTraverse(DuLinkList list) {
    DuLnode *p;
    p=list;
    int j=0;
    printf("逻辑索引：    结点数据：\n");
    while(p->next){
        j++;
        p=p->next;
        printf(" %d          %c\n",j,p->data);
    }
    return OK;
}

//操作5：插入新元素数据到指定位置。(i为逻辑位置) 
Status ListInsert(DuLinkList *list,int i,ElemType elem){
    if(i<1) return ERROR; //插入位置序号小于1 
    DuLnode *p;
    int j=0;  //计数器
    p=*list;
    //先找到第i-1个结点 
    while(p&&j<i-1){ 
        j++;
        p=p->next;
    }
    if(!p) return ERROR;
    
    //构造新结点 
    DuLnode *new_node;
    new_node=(DuLnode*)malloc(sizeof(DuLnode));
    new_node->data=elem;
    
    //插入到链表
    if(p->next){   //当i!=length+1时，即非插入尾结点之后时。
        new_node->next=p->next;
        p->next->prior=new_node;
    }
    new_node->prior=p;
    p->next=new_node;
    
    return OK;    
} 

//操作6:删除链表第i个结点，被删除的数据保存在elem
Status ListDelete(DuLinkList *list,int i,ElemType *elem){
    if(i<1) return ERROR;
    DuLnode *p;  //工作指针指向待删结点
    int j=1;  //计数器
    p=(*list)->next;  //指向首元
    while(p&&j<i) {
        p=p->next;
        j++;
    }
    if(!p) return ERROR; //i>length 
    
    //删除结点
    p->prior->next=p->next;
    if(p->next){
        p->next->prior=p->prior;  //若删除的不是尾结点
    }
    
    free(p);
    return OK;
} 

//其他操作(如：判空、销毁、清空、求表长、按值查找、遍历输出、索引到数据等)由于不涉及或只涉及一个方向，故与单链表的操作无异。

int main(void){
    //定义一个双向链表(用指针list1表示) 
    DuLinkList list1;
    
    //链表初始化 
    Status initResultCode=InitList(&list1);
    printf("list1初始化结果：%d\n",initResultCode); 
    
    //产生数据并保存到数组 
    ElemType data1='A',data2='B',data3='C',data4='D',data5='E',data6='F';
    ElemType waitInserted[]={
        data1,
        data2,
        data3,
        data4,
        data5,
        data6,
    };
    //获得数组长度 
    int arrLength=sizeof(waitInserted)/sizeof(waitInserted[0]);
    
    //头插法建立链表list1
    Status createListResult1 = CreateList_H(&list1,waitInserted,arrLength); 
    printf("建表结果状态码：%d\n",createListResult1);
    ListTraverse(list1);  //遍历测试 
    
    //定义表2
    DuLinkList list2;
    InitList(&list2);
    //尾插法建立链表list2
    CreateList_R(&list2,waitInserted,arrLength);
    ListTraverse(list2);  //遍历测试
    
    //插入结点
    ElemType elemInserted='T';
    Status insertResultCode = ListInsert(&list1,1,elemInserted);
    printf("插入结果状态码：%d\n",insertResultCode);
    ListTraverse(list1);  //遍历测试 
    
    //删除结点，并保存删除的数据
    ElemType deletedElem;
    Status deleteResultCode=ListDelete(&list1,2,&deletedElem);
    printf("删除结果状态码:%d\n",deleteResultCode);
    printf("被删除结点数据:%c\n",deletedElem);
    ListTraverse(list1);  //遍历测试 
    
    printf("\nEND!");
    return 0;
}