#include <iostream> 
using namespace std;
#define ElemType int
#define maxSize 100
typedef struct dNode {
    ElemType data;
    struct dNode *next, *prior;
}dNode, *doubleLinkList;

// 初始化双链表
bool initDoubleLinkList(doubleLinkList &L) {
    L = new dNode;
    L->next = NULL;
    L->prior = NULL;
}

// 头插法创建双链表
void inputDoubleLinkListHead(doubleLinkList &L) {
    ElemType data;
    cin >> data;
    while(data != -1) {
        dNode *newp;
        newp = new dNode;
        newp->data = data;
        newp->next = L->next;
        newp->prior = L;
        L->next = newp;
        cin >> data;
    }
}

// 尾插法创建双链表
void inputDoubleLinkListTail(doubleLinkList &L) {
    dNode *tail = L;
    ElemType data;
    cin >> data;
    while(data != -1) {
        dNode *p;
        p = new dNode;
        p->data = data;
        p->prior = tail;
        tail->next = p;
        tail = p;
        cin >> data;
    }
    tail->next = NULL;
}

// 获取双链表的表长
int getLengthDoubleLinkList(doubleLinkList L) {
    int res = 0;
    dNode *p;
    p = L->next;
    while(p != NULL) {
        res ++;
        p = p->next;
    }
    return res;
}

// 输出双链表
void outputDoubleLinkList(doubleLinkList L) {
    dNode *p;
    p = L->next;
    while(p) {
        cout << p->data << " ";
        p = p->next;
    }
    cout << endl;
}

// 双链表的插入操作，在第i个结点之前插入结点值为e的新结点
bool insertDoubleLinkListBefore(doubleLinkList &L, ElemType e, int i) {
    if(i > getLengthDoubleLinkList(L)) return false;
    else {
        dNode *p;
        p = L;
        while(i --) {
            p = p->next;
        }
        dNode *newp = new dNode;
        newp->data = e;
        newp->prior = p->prior;
        newp->next = p;
        p->prior->next = newp;
        p->prior = newp;
        return true;
    }
}

// 双链表的插入操作，在第i个结点之后插入结点值为e的新结点
bool insertDoubleLinkListAfter(doubleLinkList &L, ElemType e, int i) {
    if(i > getLengthDoubleLinkList(L)) return false;
    else {
        dNode *p;
        p = L;
        i ++;
        while(i --) {
            p = p->next;
        }
        dNode *newp = new dNode;
        newp->data = e;
        newp->prior = p->prior;
        newp->next = p;
        p->prior->next = newp;
        p->prior = newp;
        return true;
    }
}

// 查找到双链表中第一个值为e的结点返回其下标
int searchDoubleLinkList(doubleLinkList L, ElemType e) {
    dNode *p;
    p = L->next;
    int res = 1;
    while(p) {
        if(p->data == e) break;
        p = p->next;
        res ++;
    }
    if(p != NULL) {
        return res;
    }
    else return -1;
}

// 删除第i个结点
bool deleteDoubleLinkListIndex_i(doubleLinkList &L, int i) {
    if(i > getLengthDoubleLinkList(L)) return false;
    else {
        dNode *p;
        p = L;
        while(i --) {
            p = p->next;
        }
        dNode *pprior, *pnext;
        pprior = p->prior;
        pnext = p->next;
        pprior->next = pnext;
        pnext->prior = pprior;
        delete p;
        return true;
    }
}

// 删除第一个值为e的结点
bool deleteDoubleLinkListValue_e(doubleLinkList &L, ElemType e) {
    int i = searchDoubleLinkList(L, e);
    deleteDoubleLinkListIndex_i(L, i);
}

int main() {
    doubleLinkList L;
    initDoubleLinkList(L);
    inputDoubleLinkListTail(L);
    outputDoubleLinkList(L);
    // int res = getLengthDoubleLinkList(L);
    // cout << res << endl;
    insertDoubleLinkListBefore(L, 15, 4);
    outputDoubleLinkList(L);
    int res = searchDoubleLinkList(L, 15);
    cout << res << endl;
    deleteDoubleLinkListIndex_i(L, 3);
    outputDoubleLinkList(L);
    return 0;
}