链表是线性表的链式存储方式，逻辑上相邻的数据在计算机内的存储位置不一定相邻，那么怎么表示逻辑上的相邻关系呢？
可以给每个元素附加一个指针域，指向下一个元素的存储位置。这种链表称为单向链表，简称单链表，如图1所示：
单链表中每个结点除了存储自身数据之后，还存储了下一个结点的地址，因此可以轻松访问下一个结点，以及后面的后继结点，但是如果想访问前面的结点就不行了，再也回不去了。例如删除结点p时，要先找到它的前一个结点q，然后才能删掉p结点，单向链表只能往后走，不能向前走。如果需要向前走，怎么办呢？
可以给每个元素附加两个指针域，一个存储前一个元素的地址，一个存储下一个元素的地址。这种链表称为双向链表，如图2所示：
从图2中可以看出，双向链表每个结点包含三个域：数据域和两个指针域，指针域分别存储前后两个元素结点的地址，即前驱和后继。因此指针指向的类型也是结点类型。
结点结构体的定义：
下面以带头结点的双链表为例，讲解双向链表的初始化、创建、取值、查找、插入、删除操作。
1.双向链表初始化
双向链表初始化是指构建一个空表：
bool InitList_L(DuLinkList &L)//构造一个空的双向链表L
{
L=new DuLNode; //生成新结点作为头结点，用头指针L指向头结点
if(!L)
return false; //生成结点失败
L->prior=L->next=NULL; //头结点的两个指针域置空
return true;
}
2.双向链表的创建
创建双向链表也可以用前插法和尾插法，前插法创建的链表和输入顺序正好相反，因此称为逆序建表，尾插法创建的链表和输入顺序一致，因此称为正序建表。
前插法建表如图：
(1)初始状态
(2)输入数据元素1，创建新结点，把元素1放入新结点数据域：
s=new DuLNode; //生成新结点s
cin>>s->data; //输入元素值赋给新结点的数据域
(3)前插操作，插入到头结点的后面：
(4)输入数据元素2，创建新结点，把元素2放入新结点数据域：
(5)前插操作，插入到头结点的后面：
解释：
注意：赋值语句的右侧是一个地址，左侧是一个结点的指针域。
为什么要先修改后面那个指针呢？
因为一旦修改了L结点的next指针域，那么原来L的后继结点就找不到了，要最后修改L->next指针。
注意：修改指针顺序的原则：先修改没有指针标记的那一端。
如果要插入结点的两端都有标记，例如再定义一个指针q指向第1个结点，那么先修改哪个指针都无所谓了。
拉直链表之后：
(6)继续依次输入数据元素3，4，5，前插法创建链表的结果：
void CreateDuList_H(DuLinkList &L)//前插法创建双向链表
{
//输入n个元素的值，建立到头结点的单链表L
int n;
DuLinkList s; //定义一个指针变量
L=new DuLNode;
L->prior=L->next=NULL; //先建立一个带头结点的空链表
cout <<"请输入元素个数n：" <
cin>>n;
cout <<"请依次输入n个元素：" <
cout <<"前插法创建单链表..." <
while(n--)
{
s=new DuLNode; //生成新结点s
cin>>s->data; //输入元素值赋给新结点的数据域
if(L->next)
{
L->next->prior=s;
}
s->next=L->next;
s->prior=L;
L->next=s; //将新结点s插入到头结点之后
}
}
尾插法建表同单链表的尾插法建表，需要有一个尾指针，不再赘述。
3.双向链表取值、查找如同单向链表，不再赘述。
4.双向链表插入
单链表只有一个指针域，是向后操作的，不可以向前处理，因此单链表如果要在第i个结点之前插入一个元素，则必须先找到第i-1个结点。第i个结点之前插入一个元素相当于把新结点放在第i-1个结点之后。而双向链表不需要，因为有两个指针，可以向前后操作，直接找到第i个结点，就可以把新结点插入到第i个结点之前。
解释：
因为p的前驱结点无标记，一旦修改了p结点的prior指针，p的前驱结点就找不到了，因此，最后修改这个指针。
bool ListInsert_L(DuLinkList &L, int i, int &e)//双向链表的插入
{
//在带头结点的单链表L中第i个位置之前插入值为e的新结点
int j;
DuLinkList p, s;
p=L;
j=0;
while (p&&j
{
p=p->next;
j++;
}
if (!p || j>i)//i＞n+1或者i＜1
return false;
s=new DuLNode; //生成新结点
s->data=e; //将新结点的数据域置为e
p->prior->next=s;
s->prior=p->prior;
s->next=p;
p->prior=s;
return true;
}
6.双向链表删除
删除一个结点，实际上是把这个结点跳过去。要想跳过第i个结点，可以先找到第i个结点。然后修改指针，如图：
p->prior->next=p->next；含义是将p的后继结点的地址赋值给p的前驱结点的next指针域。即p的前驱结点的next指针指向p的后继结点。在这些有关指针的赋值语句中，很多同学不理解，容易混淆，在此说明一下，等号的右侧是结点的地址，等号的左侧是结点的指针域。
p->next->prior =p->prior；含义是将p的前驱结点的地址赋值给p的后继结点的prior指针域。即p的后继结点的prior指针指向p的前驱结点。
这样，就把p结点跳过去了。然后用delete p释放被删除结点的空间。删除结点修改指针没有顺序，先修改那个都可以。
bool ListDelete_L(DuLinkList &L, int i) //双向链表的删除
{
//在带头结点的双向链表L中，删除第i个位置
DuLinkList p;
int j;
p=L;
j=0;
while((p->next)&&(j
{
p=p->next;
j++;
}
if (!(p->next)||(j>i))//当i>n或i<1时，删除位置不合理
return false;
p->prior->next=p->next;
p->next->prior=p->prior;
delete p; //释放被删除结点的空间
return true;
}
双向链表基本操作完整代码：
[cpp]view plaincopy
#include
#include
usingnamespacestd;
typedefstructDuLNode {
intdata;//结点的数据域
structDuLNode *prior,*next;//结点的指针域
}DuLNode, *DuLinkList;//LinkList为指向结构体LNode的指针类型
boolInitDuList_L(DuLinkList &L)//构造一个空的双向链表L
{
L=newDuLNode;//生成新结点作为头结点，用头指针L指向头结点
if(!L)
returnfalse;//生成结点失败
L->prior=L->next=NULL;//头结点的两个指针域置空
returntrue;
}
voidCreateDuList_H(DuLinkList &L)//前插法创建双向链表
{
//输入n个元素的值，建立到头结点的单链表L
intn;
DuLinkList s;//定义一个指针变量
L=newDuLNode;
L->prior=L->next=NULL;//先建立一个带头结点的空链表
cout <<"请输入元素个数n："<
cin>>n;
cout <<"请依次输入n个元素："<
cout <<"前插法创建单链表..."<
while(n--)
{
s=newDuLNode;//生成新结点s
cin>>s->data;//输入元素值赋给新结点的数据域
if(L->next)
{
L->next->prior=s;
}
s->next=L->next;
s->prior=L;
L->next=s;//将新结点s插入到头结点之后
}
}
boolGetElem_L(DuLinkList L,inti,int&e)//双向链表的取值
{
//在带头结点的双向链表L中查找第i个元素
//用e记录L中第i个数据元素的值
intj;
DuLinkList p;
p=L->next;//p指向第一个结点，
j=1;//j为计数器
while(j
{
p=p->next;//p指向下一个结点
j++;//计数器j相应加1
}
if(!p || j>i)
returnfalse;//i值不合法i＞n或i<=0
e=p->data;//取第i个结点的数据域
returntrue;
}
boolLocateElem_L(DuLinkList L,inte)//按值查找
{
//在带头结点的双向链表L中查找值为e的元素
DuLinkList p;
p=L->next;
while(p && p->data!=e)//顺链域向后扫描，直到p为空或p所指结点的数据域等于e
p=p->next;//p指向下一个结点
if(!p)
returnfalse;//查找失败p为NULL
returntrue;
}
boolListInsert_L(DuLinkList &L,inti,int&e)//双向链表的插入
{
//在带头结点的单链表L中第i个位置之前插入值为e的新结点
intj;
DuLinkList p, s;
p=L;
j=0;
while(p&&j
{
p=p->next;
j++;
}
if(!p || j>i)//i＞n+1或者i＜1
returnfalse;
s=newDuLNode;//生成新结点
s->data=e;//将新结点的数据域置为e
p->prior->next=s;
s->prior=p->prior;
s->next=p;
p->prior=s;
returntrue;
}
boolListDelete_L(DuLinkList &L,inti)//双向链表的删除
{
//在带头结点的双向链表L中，删除第i个位置
DuLinkList p;
intj;
p=L;
j=0;
while((p->next)&&(j
{
p=p->next;
j++;
}
if(!(p->next)||(j>i))//当i>n或i<1时，删除位置不合理
returnfalse;
p->prior->next=p->next;
p->next->prior=p->prior;
deletep;//释放被删除结点的空间
returntrue;
}
voidListprint_L(DuLinkList L)//双向链表的输出
{
DuLinkList p;
p=L->next;
while(p)
{
cout <data <<"\t";
p=p->next;
}
cout<
}
intmain()
{
inti,x,e,choose;
DuLinkList L;
choose=-1;
while(choose!=0)
{
cout <<"1. 初始化\n";
cout <<"2. 创建双向链表（前插法）\n";
cout <<"3. 取值\n";
cout <<"4. 查找\n";
cout <<"5. 插入\n";
cout <<"6. 删除\n";
cout <<"7. 输出\n";
cout <<"0. 退出\n";
cout<<"请输入数字选择:";
cin>>choose;
switch(choose)
{
case1://初始化一个空的双向链表
if(InitDuList_L(L))
cout <<"初始化一个空的双向链表!\n";
break;
case2://创建双向链表（前插法）
CreateDuList_H(L);
cout <<"前插法创建双向链表输出结果:\n";
Listprint_L(L);
break;
case3://双向链表的按序号取值
cout <<"请输入一个位置i用来取值:";
cin >> i;
if(GetElem_L(L,i,e))
{
cout <<"查找成功\n";
cout <<"第"<< i <<"个元素是："<
}
else
cout <<"查找失败\n\n";
break;
case4://双向链表的按值查找
cout<<"请输入所要查找元素x:";
cin>>x;
if(LocateElem_L(L,x))
cout <<"查找成功\n";
else
cout <<"查找失败! "<
break;
case5://双向链表的插入
cout <<"请输入插入的位置和元素（用空格隔开）:";
cin >> i;
cin >> x;
if(ListInsert_L(L, i, x))
cout <<"插入成功.\n\n";
else
cout <<"插入失败!\n\n";
break;
case6://双向链表的删除
cout<<"请输入所要删除的元素位置i:";
cin>>i;
if(ListDelete_L(L, i))
cout<<"删除成功!\n";
else
cout<<"删除失败!\n";
break;
case7://双向链表的输出
cout <<"当前双向链表的数据元素分别为:\n";
Listprint_L(L);
cout << endl;
break;
}
}
return0;
}
网友评论