一、观看PPT教程
【01】双向链表
二、练习题（不清楚回头查看有关PPT）
【01】下面是有关双向链表的定义的描述，如果有错误，请改正：双向链表的每个节点包含两个指针域，一个指向前一个节点，一个指向后一个节点。
如果存在头节点，头指针head指向它，否则指向第一个节点。
如果存在头节点，那它的向前指针一般指向NULL，即不指向任何节点；向前指针指向第一个节点（非空链表）或NULL（空链表）。如果不存在头节点，那第一个节点充当头节点的功能，只不过数据域中有数据。尾节点的向后指针一般指向NULL，即不储存任何节点信息。
【02】下面是使用三静态数组模拟双向链表（有头节点）的代码，请补全缺失的注释：
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
#include<iostream>using namespace std;const int max_size = 1001; //int head; //int val[max_size]; //int pre[max_size]; //int nxt[max_size]; //int idx; //int size; ////初始化void init(){ head = 0; // pre[0] = -1, nxt[0] = -1; // idx = 1; // size = 0; //} //空链表：当链表中仅有头指针和头节点或仅有头指针时，此时链表为空 。//模拟指针从头节点开始查找节点int find(int pos) //传入pos { if(pos > size || pos < 0) // { cout << "查找位置不存在" << endl; return -1; } else { int fd = head; // for(int i = 1; i <= pos; i++) // { fd = nxt[fd]; } return fd; // }}/**双向链表的插入1. 头插法2. 中间插入法3. 尾插法插入位置的前后节点和新节点之间的指向关系需要重新构建。1．新节点的 pre 指向前一个节点；2．新节点的 nxt 指向后一个节点；3．前一个节点的 nxt 指向新节点；4．后一个节点的 pre 指向新节点。想一想，这4步的顺序哪些步骤不能改变？答：先建立新节点的指向关系，再建立它的前后节点指向关系。即1、2的步骤放在3、4之前。**//**插入第一个节点 双向链表初始为空时，由于头节点的前后指向为—1，为避免数组访问越界。特别地，当空链表插入第一个元素时，做出特殊处理，直接构建头节点和第一个节点的指向关系。**/ void push_first(int x) //传入一个节点值{ val[idx] = x; //保存节点值 pre[idx] = head; //向前指针指向头节点 nxt[idx] = -1; //向后指针指向NULL nxt[head] = idx; //头节点向后指针指向第一个节点 idx++; //新节点储存位置增加1 size++; //链表长度增加1 } //头插法：将新节点插入到头部void push_front(int x) //待插入的值x{ if(idx > max_size - 1) //检查数组是否已满 cout << "储存位置已超过范围" << endl; else if (size == 0){ //检查链表中是否还没有节点（空链表） push_first(x); //插入第一个节点 return; }else { val[idx] = x; // pre[idx] = head; // nxt[idx] = nxt[head]; // nxt[head] = idx; // pre[nxt[idx]] = idx; // idx++; // size++; //单链表长度增加1 } }//中间插入法：将新节点插入知道位置前。void insert(int pos, int x) //pos插入位置 { if(pos > size || pos <= 0) // cout << "插入位置不存在" << endl; else if(idx > max_size - 1) cout << "储存位置已超过范围" << endl; else { val[idx] = x; // int temp = find(pos); // pre[idx] = pre[temp]; // nxt[idx] = temp; // nxt[pre[temp]] = idx; // pre[temp] = idx; // idx++; // size++; //单链表长度增加1 } }//尾插法：将新节点插入末尾void push_back(int x) //传入待插入的值x { if(idx > max_size -1) // cout << "储存位置已超过范围" << endl; else if (size == 0) //检查链表中是否还没有节点（空链表） return push_first(x); //插入第一个节点 else { val[idx] = x; // int temp = head; while(nxt[temp] != -1) // temp = nxt[temp]; pre[idx] = temp; nxt[idx] = nxt[temp]; // nxt[temp] = idx; // idx++; // size++; //单链表长度增加1 }}/**双向链表的删除删除节点，前节点直接指向后节点。1. 删除第一个节点 注：这里第一个节点不是头节点 2. 删除最后一个节点3. 删除中间的某个节点。注：数组模拟的链表很难物理移除数据，故模拟代码中不含数据移除算法，模拟删除过程不是实际的删除过程，节点删除后就成了垃圾。**///删除第一个节点void pop_front(){ if(size == 0) // cout << "链表为空" << endl; else if (size == 1){ // nxt[head] = -1; size--; //链表长度减1 }else{ // nxt[head] = nxt[nxt[head]]; //头节点的向后指针指向第二个节点 pre[nxt[head]] = head; //原第二个节点的向前指针指向头节点 size--; //链表长度减1 }}//删除最后一个节点void pop_back(){ if(size == 0) // cout << "链表为空" << endl; else // { int temp = head; //从头指针开始查找 while(nxt[temp] != -1) //temp定位为尾节点 temp = nxt[temp]; nxt[pre[temp]] = -1; // size--; //链表长度减1 } }//删除中间节点void erase(int pos) //传入删除位置 { if(pos > size || pos <= 0) // cout << "删除位置不存在" << endl; else if (pos == size) // pop_back(); else // { int temp = find(pos); // nxt[pre[temp]] = nxt[temp]; // pre[nxt[temp]] = pre[temp]; // size--; //链表长度减1 }}/**双向链表的修改 **/void modify(int pos, int x) //传入位置pos和新值x{ if(pos > size || pos <= 0) // cout << "修改位置不存在" << endl; else val[find(pos)] = x; // } /**双向链表的遍历（双向） **/void print_list(){ int temp = nxt[head]; // int tail = temp; //尾节点 while(temp != -1) // { cout << val[temp] << " "; // tail = temp; //更新尾节点 temp = nxt[temp]; //沿向后指针前进1节点 } cout << " | " ; //从尾节点开始遍历 while(tail > head) //不是头节点 { cout << val[tail] << " "; //输出节点值 tail = pre[tail]; //沿向前指针前进1节点 } cout << endl;}/**双向链表测试**/ int main(){ //初始化 init(); int tvs[] = {1,20,300,4000,50000,600000}; //push_front测试 for(int i = 0; i < 6; i++){ push_front(tvs[i]); print_list(); } //push_back测试 push_back(0); print_list(); //insert测试 insert(4, 250); print_list(); //find测试 int temp = find(4); cout << "第4个节点的位置是" << temp << "，值是" << val[temp] << "。" << endl; //modify测试 modify(4, 350); print_list(); //erase测试 erase(4); print_list(); //pop_back测试 pop_back(); print_list(); //pop_front测试 pop_front(); print_list(); return 0;}
【03】循环双向链表与双向链表不同的地方是，头尾节点的指针的指针会互相指向，即头节点的前指针会指向尾节点，尾节点的后指针指向头节点，形成双向循环结构。把上面的程序改造成适用于循环双向链表的程序。
【04】下面是双向链表的总结，如果有错误，请改正。
时间复杂度——删除操作：若只知道待删除节点的序号，则依然要按序查找，时间复杂度仍为O(n)；插入操作：若给定前驱节点，则时间复杂度均为O(1)。否则只能按序或按值查找前驱节点，时间复杂度为 O(n)；查找：时间复杂度均为O(n)。双向链表本身的结构优势在于，可以O(n)地找到前驱节点，若算法需要对待操作节点的前驱节点做处理，则双向链表相比单链表有更加便捷的优势。双向链表缺点在于浪费空间来存储指针域，（若从工程角度考量，则其维护性和可读性都更低），所以常规情况下，使用单链表的较多。【05】编程题：双向约瑟夫环
