数据结构第4-2讲双向链表

曾经终败给现在 2022-06-05 07:37 382阅读 0赞

**数据结构第4-2讲双向链表**

链表是线性表的链式存储方式，逻辑上相邻的数据在计算机内的存储位置不一定相邻，那么怎么表示逻辑上的相邻关系呢？

可以给每个元素附加一个指针域，指向下一个元素的存储位置。这种链表称为单向链表，简称单链表，如图1所示：

![Center][]

单链表中每个结点除了存储自身数据之后，还存储了下一个结点的地址，因此可以轻松访问下一个结点，以及后面的后继结点，但是如果想访问前面的结点就不行了，再也回不去了。例如删除结点*p*时，要先找到它的前一个结点*q*，然后才能删掉*p*结点，单向链表只能往后走，不能向前走。如果需要向前走，怎么办呢？

可以给每个元素附加两个指针域，一个存储前一个元素的地址，一个存储下一个元素的地址。这种链表称为双向链表，如图2所示：

![Center 1][]

从图2中可以看出，双向链表每个结点包含三个域：数据域和两个指针域，指针域分别存储前后两个元素结点的地址，即前驱和后继。因此指针指向的类型也是结点类型。

**结点结构体的定义：**

![Center 2][]

下面以带头结点的双链表为例，讲解双向链表的初始化、创建、取值、查找、插入、删除操作。

1. 双向链表初始化

双向链表初始化是指构建一个空表：

![Center 3][]

bool InitList\_L(DuLinkList &L)//构造一个空的双向链表L

L=new DuLNode; //生成新结点作为头结点，用头指针L指向头结点

if(!L)

return false; //生成结点失败

L->prior=L->next=NULL; //头结点的两个指针域置空

return true;

2. 双向链表的创建

创建双向链表也可以用**前插法**和**尾插法**，前插法创建的链表和输入顺序正好相反，因此称为逆序建表，尾插法创建的链表和输入顺序一致，因此称为正序建表。

前插法建表如图：

(1) 初始状态

![Center 3][]

(2) 输入数据元素1，创建新结点，把元素1放入新结点数据域：

![Center 4][]

s=new DuLNode; //生成新结点s

cin>>s->data; //输入元素值赋给新结点的数据域

(3) 前插操作，插入到头结点的后面：

![Center 5][]

(4) 输入数据元素2，创建新结点，把元素2放入新结点数据域：

![Center 6][]

(5) 前插操作，插入到头结点的后面：

![Center 7][]

解释：

![Center 8][]

**注意：赋值语句的右侧是一个地址，左侧是一个结点的指针域。**

**为什么要先修改后面那个指针呢？**

因为一旦修改了L结点的next指针域，那么原来L的后继结点就找不到了，要最后修改L->next指针。

**注意：**修改指针顺序的**原则：先修改没有指针标记的那一端。**

![Center 9][]

如果要插入结点的两端都有标记，例如再定义一个指针*q*指向第1个结点，那么先修改哪个指针都无所谓了。

拉直链表之后：

![Center 10][]

(6) 继续依次输入数据元素3，4，5，前插法创建链表的结果：

![Center 11][]

void CreateDuList\_H(DuLinkList &L)//前插法创建双向链表

//输入n个元素的值，建立到头结点的单链表L

int n;

DuLinkList s; //定义一个指针变量

L=new DuLNode;

L->prior=L->next=NULL; //先建立一个带头结点的空链表

cout <<"请输入元素个数n：" <<endl;

cin>>n;

cout <<"请依次输入n个元素：" <<endl;

cout <<"前插法创建单链表..." <<endl;

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*个结点之前。

![Center 12][]

解释：

![Center 13][]

因为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<i) //查找第i个结点，p指向该结点

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*个结点。然后修改指针，如图：

![Center 14][]

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<i)) //查找第i个结点，p指向该结点

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;

双向链表基本操作完整代码：

#include<iostream>
    #include<string>
    using namespace std;
    
    typedef struct DuLNode {
    	int data; //结点的数据域
    	struct DuLNode *prior,*next; //结点的指针域
    }DuLNode, *DuLinkList; //LinkList为指向结构体LNode的指针类型
    
    bool InitDuList_L(DuLinkList &L)//构造一个空的双向链表L
    {
        L=new DuLNode;     //生成新结点作为头结点，用头指针L指向头结点
    	if(!L)
          return false;     //生成结点失败
    	L->prior=L->next=NULL;   //头结点的两个指针域置空
    	return true;
    }
    
    void CreateDuList_H(DuLinkList &L)//前插法创建双向链表
    {
    	//输入n个元素的值，建立到头结点的单链表L
    	int n;
    	DuLinkList s; //定义一个指针变量
    	L=new DuLNode;
    	L->prior=L->next=NULL; //先建立一个带头结点的空链表
    	cout <<"请输入元素个数n：" <<endl;
    	cin>>n;
    	cout <<"请依次输入n个元素：" <<endl;
    	cout <<"前插法创建单链表..." <<endl;
    	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插入到头结点之后
    	}
    }
    
    bool GetElem_L(DuLinkList L, int i, int &e)//双向链表的取值
    {
    	//在带头结点的双向链表L中查找第i个元素
    	//用e记录L中第i个数据元素的值
    	int j;
    	DuLinkList p;
    	p=L->next;//p指向第一个结点，
    	j=1; //j为计数器
    	while (j<i && p) //顺链域向后扫描，直到p指向第i个元素或p为空
        {
    		p=p->next; //p指向下一个结点
    		j++; //计数器j相应加1
    	}
    	if (!p || j>i)
    		return false; //i值不合法i＞n或i<=0
    	e=p->data; //取第i个结点的数据域
    	return true;
    }
    
    bool LocateElem_L(DuLinkList L, int e) //按值查找
    {
    	//在带头结点的双向链表L中查找值为e的元素
    	DuLinkList p;
    	p=L->next;
    	while (p && p->data!=e)//顺链域向后扫描，直到p为空或p所指结点的数据域等于e
    		p=p->next; //p指向下一个结点
    	if(!p)
            return false; //查找失败p为NULL
        return true;
    }
    
    bool ListInsert_L(DuLinkList &L, int i, int &e)//双向链表的插入
    {
    	//在带头结点的单链表L中第i个位置之前插入值为e的新结点
    	int j;
    	DuLinkList p, s;
    	p=L;
    	j=0;
    	while (p&&j<i) //查找第i个结点，p指向该结点
        {
    		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;
    }
    
    bool ListDelete_L(DuLinkList &L, int i) //双向链表的删除
    {
    	//在带头结点的双向链表L中，删除第i个位置
    	DuLinkList p;
    	int j;
    	p=L;
    	j=0;
    	while((p->next)&&(j<i)) //查找第i个结点，p指向该结点
    	{
    		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;
    }
    
    void Listprint_L(DuLinkList L) //双向链表的输出
    {
        DuLinkList p;
        p=L->next;
        while(p)
        {
            cout <<p->data <<"\t";
    		p=p->next;
        }
        cout<<endl;
    }
    
    int main()
    {
    	int i,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)
    		{
    		case 1: //初始化一个空的双向链表
    			if (InitDuList_L(L))
    				cout << "初始化一个空的双向链表!\n";
    			break;
    		case 2: //创建双向链表（前插法）
    			CreateDuList_H(L);
                cout << "前插法创建双向链表输出结果:\n";
                Listprint_L(L);
    			break;
    		case 3: //双向链表的按序号取值
    			cout << "请输入一个位置i用来取值:";
    			cin >> i;
    			if (GetElem_L(L,i,e))
                {
    				cout << "查找成功\n";
    				cout << "第" << i << "个元素是："<<e<< endl;
    			}
    			else
    				cout << "查找失败\n\n";
    			break;
    		case 4: //双向链表的按值查找
    			cout<<"请输入所要查找元素x:";
    			cin>>x;
    			if (LocateElem_L(L,x))
    				cout << "查找成功\n";
    			else
    				cout << "查找失败! " <<endl;
    			break;
    		case 5: //双向链表的插入
    			cout << "请输入插入的位置和元素（用空格隔开）:";
    			cin >> i;
    			cin >> x;
    			if (ListInsert_L(L, i, x))
    				cout << "插入成功.\n\n";
    			else
    				cout << "插入失败!\n\n";
    			break;
    		case 6: //双向链表的删除
    			cout<<"请输入所要删除的元素位置i:";
    			cin>>i;
    			if (ListDelete_L(L, i))
    				cout<<"删除成功!\n";
    			else
    				cout<<"删除失败!\n";
    			break;
    		case 7: //双向链表的输出
    			cout << "当前双向链表的数据元素分别为:\n";
    			Listprint_L(L);
    			cout << endl;
    			break;
    		}
    	}
    	return 0;
    }

本文来自《趣学数据结构》，让数据结构变得简单有趣。

[Center]: /images/20220605/518f8fa6af34452b8299203c97b265db.png
[Center 1]: /images/20220605/6c2d1c16a6b04d29805513a234715e91.png
[Center 2]: /images/20220605/ddfb262776284e7088e99d645cac1e69.png
[Center 3]: /images/20220605/ace3dcffd60449ba96b7c6e156152307.png
[Center 4]: /images/20220605/7d5406ce4aaa4723b04c55b92c4f971f.png
[Center 5]: /images/20220605/22d471ec03024e0aa6b345e4a3caa6c0.png
[Center 6]: /images/20220605/c3ba6e02fea64bd7adfe3077c681a076.png
[Center 7]: /images/20220605/dc161fcd89bc4c74b103b72cf9250eae.png
[Center 8]: /images/20220605/5b6bb71c1cfa44578ab0bf71ab1d037e.png
[Center 9]: /images/20220605/52a39f22e9d54ea4871b23fe15c2a4ca.png
[Center 10]: /images/20220605/6a95681a2fdb400f8f55b21c31002dd2.png
[Center 11]: /images/20220605/b1eb8ef078034d918ca3258216911f20.png
[Center 12]: /images/20220605/6d01dcc48cf347a7979096b46153ea80.png
[Center 13]: /images/20220605/6ff9816240984260bb26635acd5617a7.png
[Center 14]: /images/20220605/e33a0c174b774067aad08d5233c61043.png