数据结构— —双向链表
双向链表的算法实现
单链表中每个结点除了存储自身数据之后，还存储了下一个结点的地址，因此可以轻松访问下一个结点，以及后面的后继结点，但是如果想访问前面的结点就不行了，再也回不去了。例如删除结点 p 时，要先找到它的前一个结点 q，然后才能删掉 p 结点，单向链表只能往后走，不能向前走。如果需要向前走，怎么办呢？
可以在单链表的基础上给每个元素附加两个指针域，一个存储前一个元素的地址，一个存储下一个元素的地址。这种链表称为双向链表.
其结构体定义：
typedef struct _LinkNode {
int data; //结点的数据域 struct _LinkNode *next; //下一个节点的指针域
struct _LinkNode *prev; //上一个结点的指针域
}LinkNode, LinkList; //LinkList 为指向结构体 LNode 的指针类型
双向链表的初始
//前插法 bool DbListInsert_front(DbLinkList* &L, DbLinkNode *node){ if(!L || !node) return false; //1.只有头节点 if(L->next==NULL){ typedef struct _DoubleLinkNode { int data; //结点的数据域 struct _DoubleLinkNode *next; //下一个节点的指针域 struct _DoubleLinkNode *prev; //上一个结点的指针域 }DbLinkNode, DbLinkList; //LinkList为指向结构体LNode的指针类型 bool DbInit_List(DbLinkList* &L)//构造一个空的双向链表L { L=new DbLinkNode; //生成新结点作为头结点，用头指针L指向头结点 if(!L)return false; //生成结点失败 L->next=NULL; //头结点的next指针域置空 L->prev=NULL; //头结点的指针域置空 L->data = -1; return true; }
双向链表增加元素前插法
node->next=NULL; 11 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; while(last->next) last = last->next; node->next = NULL; last->next = node; node->prev = last; return true; }
任意位置插入
//指定位置插入 bool DbLink_Insert(DbLinkList* &L, int i, int &e){ if(!L||!L->next) return false; if(i<1) return false; int j =0; DbLinkList *p, *s; p = L; while(p && j<i){//查找位置为i的结点，p指向该结点 p = p->next; j++; } if(!p || j!=i){ cout<<"不存在节点："<<i<<endl; return false; } cout<<"p: "<<p<<endl; s=new DbLinkNode;//生成新节点 s->data = e; s->next = p; s->prev = p->prev; p->prev->next = s; p->prev = s; return true; }
双向链表的遍历
//双向链表的遍历输出 void DbLink_Print(DbLinkList* &L ){ DbLinkNode *p = NULL; if(!L){ cout<<"链表为空."<<endl; return ; } p = L; 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; }
双向链表获取元素
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; index = 1; while(p && index<i){//顺链表向后扫描，直到p指向第i个元素或p为空 p = p->next; index++; } if(!p || index>i){ return false; //i值不合法,i＞n或i<=0 } e=p->data; return true; }
11 |
||
双向链表删除元素
//任意位置删除 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; while(p && index<i){ p = p->next; index++; } if(!p){ //当节点不存在时，返回失败 return false; } p->prev->next=p->next; //改变删除结点前驱结点的next 指针域 if(p->next){ p->next->prev = p->prev; //改变删除节点后继节点的prev 指针域 } delete p; //释放被删除结点的空间 return true; }
双向链表销毁
void DbLink_Destroy(DbLinkList* &L) //双向链表的销毁 { //定义临时节点p指向头节点 DbLinkList *p = L; cout<<"销毁链表!"<<endl; while(p){ L=L->next;//L指向下一个节点 cout<<"删除元素: "<<p->data<<endl; delete p; //删除当前节点 p = L; //p 移向下一个节点 } }
完整代码实现：
#include <iostream> #include <Windows.h> using namespace std; typedef struct _DbLinkList { int data;//数据域 struct _DbLinkList* prev;//前驱结点 struct _DbLinkList* next;//后继结点 }DbLinkList, DbLinkNode; bool DbLinkList_Init(DbLinkList*& L) { //分配头结点 L = new DbLinkNode; if (!L) { return false; } L->next = NULL; L->prev = NULL; L->data = -1; return true; } //头插 bool InsertDbLink_front(DbLinkList*& L, DbLinkList* node) { if (!L || !node) { return false; } if (L->next == NULL) { node->next = NULL; node->prev = L; L->next = node; } else { L->next->prev = node; node->next = L->next; node->prev = L; L->next = node; //L->next->prev = node; //第二个节点的 prev 指向新节点 //node->next = L->next; //新节点 next 指针指向第二个节点 //node->prev = L; //新节点 prev 指针指向头节点 //L->next = node; } return true; } //尾插 bool InsertDbLink_back(DbLinkList* &L, DbLinkNode* node) { if (!L || !node) { return false; } DbLinkList* q; q = L; while (q->next) { q = q->next; } q->next = node; node->prev = node; return true; } //任意位置插入 bool DbLink_Insert(DbLinkList*& L,int i,int &e) { DbLinkList* q, * s; int j = 1; q = L->next; if (!L || !L->next) { return false; } while (!q || j < i) { q = q->next; j++; } if (!q || i != j) { return false; } s = new DbLinkNode; s->data = e; q->prev->next = s; s->prev = q->prev; s->next = q; q->prev = s; return true; } //按指定位置查找元素 bool seekElem(DbLinkList*& L, int i, int& e) { DbLinkList* p; int j = 1; p = L->next; if (!L || !L->next) { return false; } while (p && j < i) { p = p->next; j++; } if (!p || j > i) { return false; } e = p->data; return true; } bool DbLink_Delete(DbLinkList*& L, int i) { DbLinkNode* pos; int j = 1; pos = L->next; if (!L || !L->next) { return false; } if (i < 1) { return false; } while (!pos ||j<i) { pos = pos->next; j++; } if (!pos) { return false; } pos->prev->next = pos->next; pos->next->prev = pos->prev; delete pos; return true; } //链表的销毁 void DestroyLink(DbLinkList* &L) { DbLinkNode* q = L; if (!L) { cout << "链表为空" << endl; } while (q) { L = L->next; delete q; q = L; } cout << "链表销毁了" << endl; } void DbLink_Print(DbLinkList*& L) { DbLinkNode* s = NULL; s = L; if (!L) { cout << "链表为空." << endl; return; } while (s->next) { s = s->next; cout << s->data << "\t"; } cout << endl; while (s!=L) { cout << s->data << "\t"; s = s->prev; } cout << endl; } int main(void) { DbLinkList* L, * s, * a; //双向链表初始化 if (DbLinkList_Init(L)) { cout << "初始化循环链表成功" << endl; } else { cout << "初始化循环链表失败" << endl; } //前插 int j; cout << "请输入你要插入的个数："; cin >> j; for (int i = 0; i < j; i++) { s = new DbLinkNode; cin >> s->data; InsertDbLink_front(L, s); } DbLink_Print(L); //尾插 int z; cout << "请输入你要插入的个数："; cin >> z; for (int i = 0; i < z; i++) { a = new DbLinkNode; cin >> a->data; InsertDbLink_front(L, a); } DbLink_Print(L); //任意位置插入 int element, w; cout << "请输入你要插入的数："; cin >> w; cout << "请输入你要插入的位置："; cin >> element; DbLink_Insert(L, element, w); DbLink_Print(L); //查找元素 int b; cout << "请输入你要查找元素的位置："; cin >> b; seekElem(L, b, element); cout << element << endl; //删除指定位置的元素 DbLink_Delete(L, 3); DbLink_Print(L); //销毁链表 DestroyLink(L); DbLink_Print(L); system("pause"); return 0; }
