赞
踩
单链表中每个结点除了存储自身数据之后,还存储了下一个结点的地址,因此可以轻松访问下一个结点,以及后面的后继结点,但是如果想访问前面的结点就不行了,再也回不去了。例如删除结点 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; | |
} | 11 |
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;
- }
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。