#pragma once
#define OK ?? ??? ?1
#define ERROR ?? ?0
#define TRUE ?? ?1
#define FALSE ?? ?0

typedef int Status;
typedef int ElemType;

typedef struct DNode
{
?? ?struct DNode *prior;?? ??? ?//前結(jié)點(diǎn)指針域
?? ?ElemType data;?? ??? ??? ??? ?//數(shù)據(jù)域
?? ?struct DNode *next;?? ??? ??? ?//后結(jié)點(diǎn)指針域
}DNode, *DLinkList;?? ??? ??? ??? ?//結(jié)點(diǎn)和指向結(jié)點(diǎn)的指針

bool InitDLinkList(DLinkList &L);?? ??? ??? ??? ??? ??? ?//雙鏈表初始化
Status CreatDLinkList(DLinkList &L);?? ??? ??? ??? ??? ?//尾插法創(chuàng)建鏈表，包含初始化功能
bool InsertNextDNode(DNode *p, DNode *s);?? ??? ??? ??? ?//結(jié)點(diǎn)s插入在結(jié)點(diǎn)p之后
Status DeleteNextDNode(DNode *p, ElemType &e);?? ??? ??? ?//刪除結(jié)點(diǎn)p的后繼節(jié)點(diǎn)?? ??? ??? ??? ?
void ListTraverse(const DLinkList L);?? ??? ??? ??? ??? ?//雙鏈表的遍歷
Status ListInsert(DLinkList &L, int i, ElemType e);?? ??? ?//指定位置插入元素
Status ListDelete(DLinkList &L, int i, ElemType &e);?? ?//指定位置刪除元素
DNode* GetElem(DLinkList L, int i);?? ??? ??? ??? ??? ??? ?//查找鏈表指定位置節(jié)點(diǎn)，返回的是結(jié)點(diǎn)
void DestoryList(DLinkList &L);?? ??? ??? ??? ??? ??? ??? ?//銷(xiāo)毀雙鏈表,需要釋放頭結(jié)點(diǎn)

#include <iostream>
#include"list.h"

bool InitDLinkList(DLinkList &L)
{
?? ?//構(gòu)建空的雙鏈表，作為雙鏈表的頭結(jié)點(diǎn)，數(shù)據(jù)域?yàn)榭?
?? ?L = new DNode;
?? ?if (L == NULL)?? ??? ??? ??? ?//內(nèi)存分配失敗
?? ??? ?return FALSE;
?? ?L->prior = NULL;?? ??? ??? ?//頭結(jié)點(diǎn)的前驅(qū)指針始終指向NULL?? ?
?? ?L->next = NULL;?? ??? ??? ??? ?//暫時(shí)指向NULL
?? ?return TRUE;
}

Status CreatDLinkList(DLinkList &L)
{
?? ?//利用InsertNextDNode函數(shù)來(lái)創(chuàng)建

?? ?using std::cin;
?? ?using std::cout;
?? ?using std::endl;
?? ?if (InitDLinkList(L))
?? ?{
?? ??? ?DNode *s,*r = L;?? ??? ??? ??? ?//s為新建的新結(jié)點(diǎn)，用來(lái)存儲(chǔ)數(shù)據(jù)，而r為尾指針，始終指向尾部節(jié)點(diǎn)
?? ??? ?int num;
?? ??? ?cout << "輸入你需要?jiǎng)?chuàng)建的雙鏈表的個(gè)數(shù)：";
?? ??? ?cin >> num;
?? ??? ?for (int i = 1; i <= num; i++)
?? ??? ?{
?? ??? ??? ?s = new DNode;?? ??? ??? ??? ?//創(chuàng)建的新結(jié)點(diǎn)
?? ??? ??? ?cout << "輸入第" << i << "個(gè)元素：";
?? ??? ??? ?cin >> s->data;?? ??? ??? ??? ?//輸入數(shù)據(jù)
?? ??? ??? ?s->next = NULL;
?? ??? ??? ?InsertNextDNode(r,s);?? ??? ?//結(jié)點(diǎn)s插在尾部節(jié)點(diǎn)之后
?? ??? ??? ?r = s;?? ??? ??? ??? ??? ??? ?//尾指針指向新的尾結(jié)點(diǎn)
?? ??? ?}
?? ??? ?return OK;
?? ?}
?? ?else
?? ?{
?? ??? ?cout << "內(nèi)存不夠，單鏈表創(chuàng)建失??！" << endl;
?? ??? ?return ERROR;
?? ?}
}

//結(jié)點(diǎn)s插入在結(jié)點(diǎn)p之后
bool InsertNextDNode(DNode *p, DNode *s)
{
?? ?if (p == NULL || s == NULL)
?? ??? ?return FALSE;?? ??? ??? ?//非法參數(shù)
?? ?s->next = p->next;
?? ?if (p->next != NULL)?? ??? ?//如果p不是最后一個(gè)結(jié)點(diǎn)
?? ?{
?? ??? ?p->next->prior = s;
?? ?}
?? ?s->prior = p;
?? ?p->next = s;
?? ?return TRUE;
}

Status DeleteNextDNode(DNode *p, ElemType &e)
{
?? ?if(p == NULL)
?? ??? ?return FALSE;?? ??? ??? ?//非法參數(shù)
?? ?DNode *q = p->next;?? ??? ??? ?//找到p節(jié)點(diǎn)的后繼節(jié)點(diǎn)
?? ?if (q == NULL)?? ??? ??? ??? ?//節(jié)點(diǎn)p沒(méi)有后繼節(jié)點(diǎn)
?? ?{
?? ??? ?return ERROR;
?? ?}
?? ?else
?? ?{
?? ??? ?//有后繼節(jié)點(diǎn)，但是p的后繼節(jié)點(diǎn)為空
?? ??? ?p->next = q->next;
?? ??? ?e = q->data;
?? ??? ?if (q->next != NULL)
?? ??? ?{
?? ??? ??? ?q->next->prior = p;
?? ??? ?}
?? ??? ?delete q;
?? ??? ?return OK;
?? ?}
}

void ListTraverse(const DLinkList L)
{
?? ?using std::cout;
?? ?using std::endl;
?? ?int i = 1;
?? ?DNode *p = L->next;?? ??? ??? ??? ??? ?//指向第一個(gè)元素
?? ?if (p == NULL)
?? ?{
?? ??? ?cout << "雙鏈表為空，無(wú)法輸出元素！" << endl;
?? ??? ?return;
?? ?}
?? ?while (p)
?? ?{
?? ??? ?cout << "第" << i++ << "個(gè)元素為：" << p->data << endl;
?? ??? ?p = p->next;
?? ?}
}

Status ListDelete(DLinkList &L, int i, ElemType &e)
{
?? ?if (i < 1)?? ??? ? ?? ??? ?//位置不合理
?? ??? ?return ERROR;
?? ?//尋找第i-1個(gè)結(jié)點(diǎn)
?? ?DNode *p = GetElem(L, i - 1);
?? ?//刪除i-1結(jié)點(diǎn)的后面結(jié)點(diǎn)
?? ?return DeleteNextDNode(p,e);
}

DNode* GetElem(DLinkList L, int i)
{
?? ?DNode *p = L;
?? ?int j = 0;?? ??? ??? ??? ?//表示p指向的當(dāng)前結(jié)點(diǎn)的位置，此時(shí)為頭結(jié)點(diǎn)
?? ?while (p != NULL && j < i)
?? ?{
?? ??? ?p = p->next;?? ??? ?//指向下一個(gè)結(jié)點(diǎn)
?? ??? ?j++;
?? ?}
?? ?return p;
}

void DestoryList(DLinkList &L)
{
?? ?using std::cout;
?? ?using std::endl;
?? ?ElemType temp;
?? ?int i = 1;
?? ?while (L->next != NULL)
?? ?{
?? ??? ?DeleteNextDNode(L,temp);
?? ??? ?cout << "第" << i++ << "個(gè)刪除的元素為：" << temp << endl;
?? ?}
?? ?cout << "雙鏈表全部數(shù)據(jù)銷(xiāo)毀成功！" << endl;
?? ?delete L;
?? ?cout << "頭結(jié)點(diǎn)銷(xiāo)毀，整個(gè)雙鏈表銷(xiāo)毀成功！" << endl;
?? ?L = NULL;?? ??? ??? ??? ?//頭指針指向NULL
}

Status ListInsert(DLinkList &L, int i, ElemType e)
{
?? ?if (i < 1)
?? ??? ?return FALSE;
?? ?//尋找第i-1個(gè)結(jié)點(diǎn)
?? ?DNode *p = GetElem(L, i - 1);
?? ?//直接在i-1結(jié)點(diǎn)的后面插入元素即可
?? ?DNode *s = new DNode;?? ??? ?//新建節(jié)點(diǎn)
?? ?s->data = e;
?? ?s->next = NULL;
?? ?s->prior = NULL;
?? ?return InsertNextDNode(p,s);
}

/* 雙向鏈表：帶頭結(jié)點(diǎn)，且頭結(jié)點(diǎn)的prior指針時(shí)鐘指向?yàn)镹ULL

1、雙鏈表的初始化
2、雙鏈表的創(chuàng)建
3、雙鏈表的結(jié)點(diǎn)插入（相當(dāng)于后插操作）：（結(jié)點(diǎn)s插入結(jié)點(diǎn)p之后）需要考慮p結(jié)點(diǎn)是不是最后一個(gè)結(jié)點(diǎn)
?? ?如果想前插操作，則找到該節(jié)點(diǎn)的i-1節(jié)點(diǎn)，然后實(shí)行后插操作也是一樣
4、雙鏈表的結(jié)點(diǎn)刪除（相當(dāng)于后刪操作）：（刪除p節(jié)點(diǎn)的后序節(jié)點(diǎn)q）需要考慮p結(jié)點(diǎn)是不是最后一個(gè)結(jié)點(diǎn)
?? ?也要考慮q節(jié)點(diǎn)是不是最后一個(gè)結(jié)點(diǎn)
5、雙鏈表的刪除：
6、雙鏈表的遍歷：
7、雙鏈表的銷(xiāo)毀：需要回收頭結(jié)點(diǎn)

*/

#include <iostream>
#include"list.h"

void showMenu()
{
?? ?using std::cout;
?? ?using std::cin;
?? ?using std::endl;
?? ?cout << "*********************************************************" << endl;
?? ?cout << "*** 1.指定位置插入元素?? ??? ??? ?2.刪除指定位置元素 ***" << endl;
?? ?cout << "*** 3.遍歷單鏈表?? ??? ??? ?0.銷(xiāo)毀雙鏈表并退出 ***" << endl;
?? ?cout << "*********************************************************" << endl;
}

int main()
{
?? ?using std::cout;
?? ?using std::cin;
?? ?using std::endl;
?? ?int select = 0, flag = -1;?? ??? ??? ?//輸入的選擇

?? ?DLinkList L;?? ??? ??? ??? ?//L表示頭指針，始終指向表頭

?? ?if (CreatDLinkList(L))?? ??? ?//尾插法創(chuàng)建單鏈表
?? ?{
?? ??? ?cout << "雙鏈表創(chuàng)建成功！" << endl;
?? ?}
?? ?else
?? ??? ?cout << "雙鏈表創(chuàng)建失敗！" << endl;

?? ?while (true)
?? ?{
?? ??? ?showMenu();
?? ??? ?cout << "輸入你的選擇：";
?? ??? ?cin >> select;
?? ??? ?switch (select)
?? ??? ?{
?? ??? ?case 1: {?? ??? ?//指定位置插入元素
?? ??? ??? ?int position = 0, elem = 0;
?? ??? ??? ?cout << "輸入插入的位置和元素:";
?? ??? ??? ?cin >> position >> elem;
?? ??? ??? ?if (ListInsert(L, position, elem))
?? ??? ??? ??? ?cout << "指定位置插入元素成功！" << endl;
?? ??? ??? ?else
?? ??? ??? ??? ?cout << "內(nèi)存分配失敗或者插入位置越界，插入失敗！" << endl;
?? ??? ?}
?? ??? ??? ??? ?break;
?? ??? ?case 2: {?? ??? ?//刪除指定位置節(jié)點(diǎn)
?? ??? ??? ?int position = 0, elem = 0;
?? ??? ??? ?cout << "輸入指定位置:";
?? ??? ??? ?cin >> position;
?? ??? ??? ?if (ListDelete(L, position, elem))
?? ??? ??? ?{
?? ??? ??? ??? ?cout << "刪除指定位置元素成功！元素為：" << elem << endl;
?? ??? ??? ?}
?? ??? ??? ?else
?? ??? ??? ?{
?? ??? ??? ??? ?cout << "單鏈表為空或者刪除位置不合理！" << endl;
?? ??? ??? ?}
?? ??? ?}
?? ??? ??? ??? ?break;
?? ??? ?case 3: {
?? ??? ??? ?ListTraverse(L);
?? ??? ?}
?? ??? ??? ??? ?break;
?? ??? ?case 0: {
?? ??? ??? ?DestoryList(L);
?? ??? ??? ?system("pause");
?? ??? ??? ?return 0;
?? ??? ?}
?? ??? ?break;
?? ??? ?}
?? ?}
?? ?return 0;
}