#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;?? ??? ?//前結點指針域
?? ?ElemType data;?? ??? ??? ??? ?//數(shù)據(jù)域
?? ?struct DNode *next;?? ??? ??? ?//后結點指針域
}DNode, *DLinkList;?? ??? ??? ??? ?//結點和指向結點的指針

bool InitDLinkList(DLinkList &L);?? ??? ??? ??? ??? ??? ?//雙鏈表初始化
Status CreatDLinkList(DLinkList &L);?? ??? ??? ??? ??? ?//尾插法創(chuàng)建鏈表，包含初始化功能
bool InsertNextDNode(DNode *p, DNode *s);?? ??? ??? ??? ?//結點s插入在結點p之后
Status DeleteNextDNode(DNode *p, ElemType &e);?? ??? ??? ?//刪除結點p的后繼節(jié)點?? ??? ??? ??? ?
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é)點，返回的是結點
void DestoryList(DLinkList &L);?? ??? ??? ??? ??? ??? ??? ?//銷毀雙鏈表,需要釋放頭結點

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

bool InitDLinkList(DLinkList &L)
{
?? ?//構建空的雙鏈表，作為雙鏈表的頭結點，數(shù)據(jù)域為空
?? ?L = new DNode;
?? ?if (L == NULL)?? ??? ??? ??? ?//內存分配失敗
?? ??? ?return FALSE;
?? ?L->prior = NULL;?? ??? ??? ?//頭結點的前驅指針始終指向NULL?? ?
?? ?L->next = NULL;?? ??? ??? ??? ?//暫時指向NULL
?? ?return TRUE;
}

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

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

//結點s插入在結點p之后
bool InsertNextDNode(DNode *p, DNode *s)
{
?? ?if (p == NULL || s == NULL)
?? ??? ?return FALSE;?? ??? ??? ?//非法參數(shù)
?? ?s->next = p->next;
?? ?if (p->next != NULL)?? ??? ?//如果p不是最后一個結點
?? ?{
?? ??? ?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é)點的后繼節(jié)點
?? ?if (q == NULL)?? ??? ??? ??? ?//節(jié)點p沒有后繼節(jié)點
?? ?{
?? ??? ?return ERROR;
?? ?}
?? ?else
?? ?{
?? ??? ?//有后繼節(jié)點，但是p的后繼節(jié)點為空
?? ??? ?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;?? ??? ??? ??? ??? ?//指向第一個元素
?? ?if (p == NULL)
?? ?{
?? ??? ?cout << "雙鏈表為空，無法輸出元素！" << endl;
?? ??? ?return;
?? ?}
?? ?while (p)
?? ?{
?? ??? ?cout << "第" << i++ << "個元素為：" << p->data << endl;
?? ??? ?p = p->next;
?? ?}
}

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

DNode* GetElem(DLinkList L, int i)
{
?? ?DNode *p = L;
?? ?int j = 0;?? ??? ??? ??? ?//表示p指向的當前結點的位置，此時為頭結點
?? ?while (p != NULL && j < i)
?? ?{
?? ??? ?p = p->next;?? ??? ?//指向下一個結點
?? ??? ?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++ << "個刪除的元素為：" << temp << endl;
?? ?}
?? ?cout << "雙鏈表全部數(shù)據(jù)銷毀成功！" << endl;
?? ?delete L;
?? ?cout << "頭結點銷毀，整個雙鏈表銷毀成功！" << endl;
?? ?L = NULL;?? ??? ??? ??? ?//頭指針指向NULL
}

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

/* 雙向鏈表：帶頭結點，且頭結點的prior指針時鐘指向為NULL

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

*/

#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.銷毀雙鏈表并退出 ***" << 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 << "內存分配失敗或者插入位置越界，插入失敗！" << endl;
?? ??? ?}
?? ??? ??? ??? ?break;
?? ??? ?case 2: {?? ??? ?//刪除指定位置節(jié)點
?? ??? ??? ?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;
}