三十四、双链表
示例：
#include <iostream>
using namespace std;
typedef int ElemType; // 自定义链表的数据元素为整数。
struct LNode // 双链表的结点。
{
ElemType data; // 存放结点的数据元素。
struct LNode* prior,*next; // 前驱和后继结点的指针。
};
// 初始化链表，返回值：失败返回 nullptr，成功返回头结点的地址。
LNode* InitList()
{
LNode* head = new (std::nothrow) LNode; // 分配头结点。
if (head == nullptr) return nullptr; // 内存不足，返回失败。
head->prior = head->next = nullptr; // 前驱后继结点都置为空。
return head; // 返回头结点。
}
// 销毁链表。代码和单链表相同。
void DestroyList(LNode* head)
{
// 销毁链表是指释放链表全部的结点，包括头结点。
LNode* tmp;
while (head != nullptr)
{
tmp = head->next; // tmp 保存下一结点的地址。
delete head; // 释放当前结点。
head = tmp; // 指针移动到下一结点。
}
}
// 在链表的头部插入元素（头插法），返回值：false-失败；true-成功。
bool PushFront(LNode* head, const ElemType& ee)
{
if (head == nullptr) { cout << "链表不存在。\n"; return false; }
LNode* tmp = new (std::nothrow) LNode; // 分配一个新结点。
if (tmp == nullptr) return false;
tmp->data = ee; // 把元素的值存入新结点。
// 处理 prior 和 next 指针。
tmp->prior = head; // 当前结点的 prior 指针指向 head。
tmp->next = head->next; // 当前结点的 next 指针指向 head->next。
tmp->prior->next = tmp; // 让前驱结点的 next 指针指向自己。
// head->next = tmp;
// 让后继结点的 prior 指针指向自己。注意：如果当前结点是最后一个结点，tmp->next 根本
不存在。
if (tmp->next != nullptr) tmp->next->prior = tmp;
return true;
}
// 显示链表中全部的元素。代码和单链表相同。
void PrintList(const LNode* head)
{
if (head == nullptr) { cout << "链表不存在。\n"; return; }
LNode* pp = head->next; // 从第 1 个结点开始。
while (pp != nullptr)
{
cout << pp->data << " "; // 如果元素为结构体，这行代码要修改。
pp = pp->next; // 指针往后移动一个结点。
}
cout << endl;
}
// 在链表的尾部插入元素（尾插法），返回值：false-失败；true-成功。
bool PushBack(LNode* head, const ElemType& ee)
{
if (head == nullptr) { cout << "链表不存在。\n"; return false; }
LNode* pp = head; // 从头结点开始。
// 找到最后一个结点，pp 将指向尾结点（最后一个结点）。
while (pp->next != nullptr) pp = pp->next;
LNode* tmp = new (std::nothrow) LNode; // 分配一个新结点。
if (tmp == nullptr) return false;
tmp->data = ee; // 把元素的值存入新结点。
// 处理 prior 和 next 指针。
tmp->prior = pp; // 当前结点的 prior 指针指向 head。
tmp->next = nullptr; // 当前结点的 next 指针指向 head->next。
tmp->prior->next = tmp; // 让前驱结点的 next 指针指向自己。
// 既然是尾插法，那么就肯定没有后继结点，不需要处理它的 prior 指针。
return true;
}
// 求链表的表长，返回值：>=0-表 LL 结点的个数。代码和单链表相同。
size_t ListLength(LNode* head)
{
//if (head == nullptr) { cout << "链表不存在。\n"; return 0; }
//LNode* pp = head->next; // 头结点不算，从第 1 个结点开始。
//size_t length = 0;
//while (pp != nullptr) { pp = pp->next; length++; }
//return length;
// 不使用临时变量，如何计算链表（包括头结点）的长度？
if (head==nullptr) return 0;
return ListLength(head->next)+1;
}
// 删除链表第一个结点。
bool PopFront(LNode* head)
{
if (head == nullptr) { cout << "链表不存在。\n"; return false; }
if (head->next == nullptr) { cout << "链表为空，没有结点。\n"; return false; }
LNode* pp = head->next; // pp 指向第一个节点。
head->next = head->next->next; // 修改头结点的 next 指针。
// 让后继结点的 prior 指针指向头结点。
// 注意：需要特殊处理，如果待删除的结点是最后一个结点，head->next 根本不存在。
if (head->next != nullptr) head->next->prior = head;
delete pp; // 删除第一个节点。
return true;
}
// 删除链表最后一个结点。代码和单链表相同。
bool PopBack(LNode* head)
{
if (head == nullptr) { cout << "链表不存在。\n"; return false; }
// 必须加上这个判断，否则下面的循环 pp->next->next 不成立。
if (head->next == nullptr) { cout << "链表为空，没有结点。\n"; return false; }
LNode* pp = head; // 从头结点开始。
// 找到倒数第二个结点（包括头结点）。
while (pp->next->next != nullptr) pp = pp->next;
delete pp->next; // 释放最后一个结点。
pp->next = nullptr; // 倒数第二个结点成了最后一个结点。
return true;
}
// 清空链表，清空链表是指释放链表全部的结点，但是，不释放头结点。代码和单链表相同。
void ClearList(LNode* head)
{
if (head == nullptr) { cout << "链表不存在。\n"; return; } // 判断链表是否存在。
LNode* tmp1;
LNode* tmp2 = head->next; // 从头结点的下一个结点开始释放。
while (tmp2 != nullptr)
{
tmp1 = tmp2->next;
delete tmp2;
tmp2 = tmp1;
}
head->next = nullptr; // 这行代码一定不能少，否则会留下野指针。
}
// 查找元素 ee 在链表中的结点地址，如果没找到返回 nullptr，否则返回结点的地址。代码和单链
表相同。
LNode* LocateElem(const LNode* head, const ElemType& ee)
{
LNode* pp = head->next; // 从第 1 个存放数据结点开始。
while (pp != nullptr)
{
// 如果数据元素是结构体，以下代码要修改成比较关键字。
if (pp->data == ee) return pp;
pp = pp->next;
}
return pp;
}
// 获取链表中第 n 个结点，成功返回结点的地址，失败返回 nullptr。
// 注意，n 可以取值为 0，表示头结点。代码和单链表相同。
LNode* LocateNode(LNode* head, unsigned int n)
{
if (head == nullptr) { cout << "链表不存在。\n"; return nullptr; }
LNode* pp = head; // 指针 pp 指向头结点，逐步往后移动，如果为空，表示后面没结
点了。
unsigned int ii = 0; // ii 指向的是第几个结点，从头结点 0 开始，pp 每向后移动一次，
ii 就加 1。
while ((pp != nullptr) && (ii < n))
{
pp = pp->next; ii++;
}
if (pp == nullptr) { cout << "位置" << n << "不合法，超过了表长。\n"; return nullptr; }
return pp;
}
// 在指定结点 pp 之后插入元素 ee。
bool InsertNextNode(LNode* pp, const ElemType& ee)
{
if (pp == nullptr) { cout << "结点 pp 不存在。\n"; return false; }
LNode* tmp = new LNode;
tmp->data = ee;
tmp->next = pp->next;
tmp->prior = pp;
tmp->prior->next = tmp; // 让前驱结点的 next 指针指向自己。
// 让后继结点的 prior 指针指向自己。注意当前结点是最后一个结点，tmp->next 根本不存在。
if (tmp->next != nullptr) tmp->next->prior = tmp;
return true;
}
// 在指定结点 pp 之前插入元素 ee。
bool InsertPriorNode(LNode* pp, const ElemType& ee)
{
if (pp == nullptr) { cout << "结点 pp 不存在。\n"; return false; }
LNode* tmp = new LNode;
tmp->data = ee;
tmp->next = pp;
tmp->prior = pp->prior;
tmp->prior->next = tmp; // 让前驱结点的 next 指针指向自己。
tmp->next->prior = tmp; // 让后继结点的 prior 指针指向自己，不需要特别处理。
return true;
}
// 删除指定结点。
bool DeleteNode(LNode* pp)
{
if (pp == nullptr) { cout << "结点 pp 不存在。\n"; return false; }
pp->prior->next = pp->next; // 让前驱结点的 next 指针指向 pp 的后继结点。
// 让后继结点的 prior 指针指向前驱结点。注意，如果当前结点是最后一个结点，pp->next 根
本不存在。
if (pp->next != nullptr) pp->next->prior = pp->prior;
delete pp;
return true; // 可以在函数外面调用 PopBack()函数。
}
int main()
{
LNode* LL = InitList(); // 初始化链表 LL。
cout << "用头插法向链表中插入元素（1、2、3）。\n";
PushFront(LL, 1);
PushFront(LL, 2);
PushFront(LL, 3);
PrintList(LL); // 把链表中全部的元素显示出来。
cout << "用尾插法向链表中插入元素（4、5、6）。\n";
PushBack(LL, 4);
PushBack(LL, 5);
PushBack(LL, 6);
PrintList(LL); // 把链表中全部的元素显示出来。
cout << "链表的表长（包括头结点）：" << ListLength(LL) << endl;
//PopFront(LL); PopFront(LL); PopFront(LL); PopFront(LL); PopFront(LL); PopFront(LL);
PopFront(LL);
//PrintList(LL); // 把链表中全部的元素显示出来。
//PopBack(LL); PopBack(LL); PopBack(LL); PopBack(LL); PopBack(LL); PopBack(LL);
PopBack(LL);
//PrintList(LL); // 把链表中全部的元素显示出来。
//ClearList(LL);
//PrintList(LL); // 把链表中全部的元素显示出来。
LNode *p1=LocateElem(LL, 4);
cout << "元素为 4 的结点的地址是：" << p1 << "，值是：" << p1->data << endl;
LNode* p2 = LocateNode(LL, 3);
cout << "位序为 3 的结点的地址是：" << p2 << "，值是：" << p2->data << endl;
cout << "在" << p2->data << "之后插入元素 8。" << endl;
InsertNextNode(p2, 8);
PrintList(LL); // 把链表中全部的元素显示出来。
cout << "在" << p2->data << "之前插入元素 7。" << endl;
InsertPriorNode(p2, 7);
PrintList(LL); // 把链表中全部的元素显示出来。
cout << "删除元素" << p2->data << "。" << endl;
DeleteNode(p2);
PrintList(LL); // 把链表中全部的元素显示出来。
DestroyList(LL); // 销毁链表 LL。
}