数据结构与算法 双向链表

双向链表

对于双向链表来说，它无非就是在单链表的基础上，在链表中多增加了一个指针域，用来存储上一个节点的地址。 单链表没有上一个节点的地址，所以无法访问它，只能访问它下一个节点，而双向链表因其比单链表多一个指针域用来存储上一个节点的地址，所以可以访问，这就是双向链表。

1.初始化双向链表

双向链表初始化只是在单链表的基础上多增加了一个指针域，所以变化不大，初始化这个指针就可以了。

//结构体定义链表 typedef struct _DoubleLinkNode { int data; //数据域(存储数据) struct _DoubleLinkNode* next; //指针节点，指向(存储)下个链表节点的地址 struct _DoubleLinkNode* prev; //指向上一个节点地址 }DLinkNode, DLinkList; //链表节点、链表 //初始化链表,定义头节点 bool DInitList(DLinkList*& L) { //构造一个空的单链表 L L = new DLinkNode; //创建新结点作为头结点，用头指针L指向头结点 if (!L) { cout << "初始化链表失败！" << endl; return false;//生成结点失败 } L->next = NULL; //头结点的指针域置空(指向下一个节点) L->prev = NULL; //头结点的指针域置空(指向上一个节点) L->data = -1; //链表数据设置为-1 cout << "初始化链表成功！" << endl; return true; }

2.前插法

（在不是空链表的情况下L为头节点）L->next为头节点的下一个节点的地址，L->next->prev为头(本)节点的地址，在单链表的基础上，多了一个逆指向。

//前插法 bool DbListInsert_front(DbLinkList* &L, DbLinkNode *node){ if(!L || !node) return false; //判断是否为空 if(L->next==NULL){ //判断是否为头节点 node->next = NULL; //将新节点next(指向下个节点指针)指针设为空 node->prev = L; //将新节点prev指针指向头节点 L->next=node; //头节点next指针指向新节点 }else { //不是头节点的情况 L->next->prev=node; //第二个节点的 prev 指向新节点 node->next = L->next; //新节点 next 指针指向第二个节点 node->prev=L; //新节点 prev 指针指向头节点 L->next=node; //头节点 next 指针指向新节点，完成插入 } return true; }

3.尾插法

与单链表大体相同

//尾插法 bool DbListInsert_back(DbLinkList* &L, DbLinkNode *node){ DbLinkNode *last = NULL; if(!L || !node) return false; //合法性检查 last = L; //last指针指向头节点 while(last->next) last = last->next; //找出最后一个节点 node->next = NULL; //将新节点next指针设置为空 last->next = node; //将最后一个节点的next指向新节点地址 node->prev = last; //将新节点prev指针指向最后一个节点的地址 return true; }

4.任意位置插入

//指定位置插入 bool DbLink_Insert(DbLinkList* &L, int i, int &e){ if(!L||!L->next) return false; //链表不能为空 if(i<1) return false; //i不能小于0 int j =0; DbLinkList *p, *s; p = L; //指针p指向头节点 while(p && j<i){//查找位置为 i 的结点，p 指向该结点 p = p->next; //找出该位置(位置为i)节点 j++; } if(!p || j!=i){ cout<<"不存在节点："<<i<<endl; return false; } s = new DbLinkNode; //生成新节点 s->data = e; //插入数据赋值给新节点数据域 s->next = p; //将新节点next指针指向i位置节点地址 s->prev = p->prev; //将新节点prev指针指向i节点的上一个节点 p->prev->next = s; //将i节点的上一个节点next指针指向新节点 p->prev = s; //将i节点prev指针指向新节点地址 return true; }

5.双向链表按位置取值

//双向链表的取值 bool DbLink_GetElem(DbLinkList*& L, int i, int& e) { //在带头结点的双向链表 L 中查找第 i 个元素 //用 e 记录 L 中第 i 个数据元素的值 int index; DbLinkList *p; if(!L || !L->next) return false; //合法性检查 p = L->next; //将p指针指向第一个节点 index = 1; while(p && index<i){//顺链表向后扫描，直到 p 指向第 i 个元素或 p 为空 p = p->next; //p 指向下一个结点 index++; //计数器 index 相应加 1 } if(!p || index>i){ return false; //i 值不合法,i＞n 或 i<=0 } e=p->data; //数据赋值 return true; }

6.任意位置删除

//任意位置删除 bool DbLink_Delete(DbLinkList*& L, int i) {//双向链表的删除 DbLinkList* p; int index = 0; if (!L || !L->next) { cout << "双向链表为空!" << endl; return false; } if (i < 1) return false; //不能删除头节点 p = L; //指针p指向头节点 while (p && index < i) {//循环查找i节点 p = p->next; index++; } if (!p) { //当节点不存在时，返回失败 return false; } p->prev->next = p->next; //将i节点前节点的next指针指向i节点下一个节点地址 if (p->next) { p->next->prev = p->prev; //改变删除节点后节点的 prev 指针域 } delete p; //释放被删除结点的空间 return true; }

7.销毁链表

//双向链表的销毁 void DbLink_Destroy(DbLinkList*& L) { //定义临时节点 p 指向头节点 DbLinkList *p = L; while(p){ L=L->next;//L 指向下一个节点 cout<<"删除元素: "<<p->data<<endl; delete p; //删除当前节点 p = L; //p 移向下一个节点 } cout << "链表已销毁!" << endl; }

8.打印链表

//双向链表的遍历输出 void DbLink_Print(DbLinkList* &L ){ DbLinkNode *p = NULL; if(!L){ cout<<"链表为空."<<endl; return ; } p = L; //指针p指向头节点 while(p->next){ //循环打印数据 cout<<p->next->data<<"\t"; p = p->next; } //逆向打印 cout<<endl<<"逆向打印"<<endl; while(p){ cout<<p->data<<"\t"; p = p->prev; } cout<<endl; }

完整代码

#include <iostream> #include <string> #include <stdlib.h> using namespace std; //结构体定义链表 typedef struct _DoubleLinkNode { int data; //数据域(存储数据) struct _DoubleLinkNode* next; //指针节点，指向(存储)下个链表节点的地址 struct _DoubleLinkNode* prev; //指向上一个节点地址 }DbLinkNode, DbLinkList; //链表节点、链表 //初始化链表,定义头节点 bool DbInitList(DbLinkList*& L) { //构造一个空的单链表 L L = new DbLinkNode; //创建新结点作为头结点，用头指针L指向头结点 if (!L) { cout << "初始化链表失败！" << endl; return false;//生成结点失败 } L->next = NULL; //头结点的指针域置空(指向下一个节点) L->prev = NULL; //头结点的指针域置空(指向上一个节点) L->data = -1; //链表数据设置为-1 cout << "初始化链表成功！" << endl; return true; } //前插法 bool DbListInsert_front(DbLinkList* &L, DbLinkNode *node){ if(!L || !node) return false; //判断是否为空 if(L->next==NULL){ //判断是否为头节点 node->next = NULL; //将新节点next(指向下个节点指针)指针设为空 node->prev = L; //将新节点prev指针指向头节点 L->next=node; //头节点next指针指向新节点 }else { //不是头节点的情况 L->next->prev=node; //第二个节点的 prev 指向新节点 node->next = L->next; //新节点 next 指针指向第二个节点 node->prev=L; //新节点 prev 指针指向头节点 L->next=node; //头节点 next 指针指向新节点，完成插入 } return true; } //尾插法 bool DbListInsert_back(DbLinkList* &L, DbLinkNode *node){ DbLinkNode *last = NULL; if(!L || !node) return false; //合法性检查 last = L; //last指针指向头节点 while(last->next) last = last->next; //找出最后一个节点 node->next = NULL; //将新节点next指针设置为空 last->next = node; //将最后一个节点的next指向新节点地址 node->prev = last; //将新节点prev指针指向最后一个节点的地址 return true; } //指定位置插入 bool DbLink_Insert(DbLinkList* &L, int i, int &e){ if(!L||!L->next) return false; //链表不能为空 if(i<1) return false; //i不能小于0 int j =0; DbLinkList *p, *s; p = L; //指针p指向头节点 while(p && j<i){//查找位置为 i 的结点，p 指向该结点 p = p->next; //找出该位置(位置为i)节点 j++; } if(!p || j!=i){ cout<<"不存在节点："<<i<<endl; return false; } s = new DbLinkNode; //生成新节点 s->data = e; //插入数据赋值给新节点数据域 s->next = p; //将新节点next指针指向i位置节点地址 s->prev = p->prev; //将新节点prev指针指向i节点的上一个节点 p->prev->next = s; //将i节点的上一个节点next指针指向新节点 p->prev = s; //将i节点prev指针指向新节点地址 return true; } //双向链表的取值 bool DbLink_GetElem(DbLinkList*& L, int i, int& e) { //在带头结点的双向链表 L 中查找第 i 个元素 //用 e 记录 L 中第 i 个数据元素的值 int index; DbLinkList *p; if(!L || !L->next) return false; //合法性检查 p = L->next; //将p指针指向第一个节点 index = 1; while(p && index<i){//顺链表向后扫描，直到 p 指向第 i 个元素或 p 为空 p = p->next; //p 指向下一个结点 index++; //计数器 index 相应加 1 } if(!p || index>i){ return false; //i 值不合法,i＞n 或 i<=0 } e=p->data; //数据赋值 return true; } //任意位置删除 bool DbLink_Delete(DbLinkList*& L, int i) {//双向链表的删除 DbLinkList* p; int index = 0; if (!L || !L->next) { cout << "双向链表为空!" << endl; return false; } if (i < 1) return false; //不能删除头节点 p = L; //指针p指向头节点 while (p && index < i) {//循环查找i节点 p = p->next; index++; } if (!p) { //当节点不存在时，返回失败 return false; } p->prev->next = p->next; //将i节点前节点的next指针指向i节点下一个节点地址 if (p->next) { p->next->prev = p->prev; //改变删除节点后节点的 prev 指针域 } delete p; //释放被删除结点的空间 return true; } //双向链表的销毁 void DbLink_Destroy(DbLinkList*& L) { //定义临时节点 p 指向头节点 DbLinkList *p = L; while(p){ L=L->next;//L 指向下一个节点 cout<<"删除元素: "<<p->data<<endl; delete p; //删除当前节点 p = L; //p 移向下一个节点 } cout << "链表已销毁!" << endl; } //双向链表的遍历输出 void DbLink_Print(DbLinkList* &L ){ DbLinkNode *p = NULL; if(!L){ cout<<"链表为空."<<endl; return ; } p = L; //指针p指向头节点 while(p->next){ //循环打印数据 cout<<p->next->data<<"\t"; p = p->next; } //逆向打印 cout<<endl<<"逆向打印"<<endl; while(p){ cout<<p->data<<"\t"; p = p->prev; } cout<<endl; } int main(void) { DbLinkList* L = NULL; DbLinkNode* s = NULL; //1. 初始化一个空的双向链表 DbInitList(L); //2. 使用前插法插入数据 int n; cout<<"前插法创建双向链表"<<endl; std::cout<<"请输入元素个数 n："; cin>>n; cout << "\n 请依次输入 n 个元素：" << endl; while (n > 0) { s = new DbLinkNode; //生成新节点 s cin>>s->data; DbListInsert_front(L, s); n--; } //3. 使用尾插法插入数据 cout<<"尾插法创建双向链表"<<endl; std::cout<<"请输入元素个数 n："; cin>>n; cout<<"\n 请依次输入 n 个元素：" <<endl; while(n>0){ s = new DbLinkNode; //生成新节点 s cin>>s->data; DbListInsert_back(L, s); n--; } //4. 双向链表的输出 DbLink_Print(L); //5. 任意位置插入元素 for(int j=0; j<3; j++){ int i, x; cout << "请输入插入的位置和元素（用空格隔开）:"; cin >> i; cin >> x; if(DbLink_Insert(L, i, x)){ cout << "插入成功.\n\n"; }else{ cout << "插入失败!\n\n"; }DbLink_Print(L); } //6. 双向链表根据位置获取元素 int element = 0; if(DbLink_GetElem(L, 2, element)){ cout<<"获取第二个元素成功, 值："<<element<<endl; }else { cout << "获取第二个元素失败!" << endl; } //7. 双向链表删除元素 if(DbLink_Delete(L, 2)){ cout<<"删除第 2 个元素成功!"<<endl; DbLink_Print(L); }else { cout<<"删除第 2 个元素失败!"<<endl; }if(DbLink_Delete(L, 1)){ cout<<"删除第 1 个元素成功!"<<endl; DbLink_Print(L); }else { cout<<"删除第 1 个元素失败!"<<endl; } //8. 销毁双向链表 DbLink_Destroy(L); system("pause"); return 0; }