《数据结构》—— 双链表逻辑思考与代码解析

太过爱你忘了你带给我的痛 2022-08-28 15:54 129阅读 0赞

### 链表 ###

*   *  一、双链表
     *   *  1.1 双链表的存储定义：
         *  1.2 双链表的初始化：
         *  1.3 双链表的判空：
         *  1.4 双链表的查找操作：
         *  1.5 双链表的插入操作：
         *  1.6 双链表的删除操作：

## 一、双链表 ##

单链表结点中只有一个指向其后继的指针，使得单链表只能从头结点依次顺序地向后遍历。

要访问某个结点的前驱结点(插入、删除操作时)，只能从头开始遍历，访问后继结点的时间复杂度为0(1)，访问前驱结点的时间复杂度为O(n)。

为了克服单链表的上述缺点，引入了双链表，双链表结点中有两个指针prior和next，分别指向其前驱结点和后继结点。  
![在这里插入图片描述][84a180446c204d239fc5c912b2569d46.png]

### 1.1 双链表的存储定义： ###

typedef struct DuLNode{
        
    	ElemType data;	// 数据域
    	struct DuLNode *prior,*next;  // 前驱和后继指针
    }DNode,*DlinkList

双链表在单链表的结点中增加了一个指向其前驱的prior指针，因此双链表中的按值查找和按位查找的操作与单链表的相同。但双链表在插入和删除操作的实现上,与单链表有着较大的不同。

### 1.2 双链表的初始化： ###

bool InitDLinklist(DlinkList l&){
        
        L = (DNode *)malloc(sizeof(DNode)); // 分配头结点
        if(L==NULL)     // 内存不足，分配失败
            return false;
        L->prior = NULL;  // 头结点的prior永远指向NULL
        L->next = NULL;   // 头结点之后暂时还没有节点
        return true;
    }

### 1.3 双链表的判空： ###

bool Empty(DlinkList L){
        
        if(L->next==NULL)
            return true;
        else
            return false;
    }

--------------------

### 1.4 双链表的查找操作： ###

在带头结点的双向链表L中查找第i个元素，返回结点的地址。

DNode *GetElemP_DuL(DlinkList L, int i) {
        	
    //在带头结点的双向链表L中查找第i个元素，返回结点的地址
    	int j;
    	DlinkList p;
    	p = L->next;
    	j = 1; //初始化，p指向第一个结点，j为计数器
    	while (j<i&&p) {
         // 循环直到p指向第i个元素或p为空
    		p = p->next;
    		++j;
    	}
    	if (!p||j>i)
    		return NULL; // 第i个元素不存在
    	return p;
    }

--------------------

### 1.5 双链表的插入操作： ###

![在这里插入图片描述][996a4b7a44274e31a7f3031ff5473805.png]  
**在L中确定第i个元素的位置指针p，进行前插或者后插。**  
**【分析】**：循环操作：在L中确定第i个元素的合法位置指针p；再创建s结点，把e赋给s的数据域。

*  **在第i位置后插：** 充分条件：1、p的下一个结点是s的下一个结点；2、p的下一个结点的前驱是s结点；因此 **–>** 3、s的(前驱)前一个结点是p，p的(后继)下一个结点是s。
 *  **在第i位置前插：** 充分条件：1、p的上一个结点是s的上一个结点；2、p的上一个结点的后继是s结点；因此 **–>** 3、s的(后继)后一个结点是p，p的(前驱)上一个结点是s。

1、后插核心代码：
    s = new DNode; // 生成新结点*s
    s->data = e; // 将结点*s数据域置为e
    s->next = p->next;
    p->next->prior = s;
    s->prior = p;
    p->next = s;
    ++length;
    ----
    2、前插核心代码：
    s = new DNode; // 生成新结点*s
    s->data = e; // 将结点*s数据域置为e
    s->prior = p->prior;
    p->prior->next = s;
    s->next = p;
    p->prior = s;
    ++length;
    ----
    3、在双向链表的第一个元素上插入
    if(i==1){
        
        s = new DNode;
        s->data = e;
        DlinkList p = L->next;
        L->next = s;
        s->prior = L;
        s->next = p;//将结点*s插入L中
    	p->prior = s;    
        ++length;
    }
    ----
    4、在双向链表的最后一个元素上插入
    else if (i == length) {
         //在双向链表的最后一个元素上插入
    	s = new DNode; //生成新结点s
    	s->data = e; //将结点s数据置为e
    	DlinkList p = L;
    	while (p->next)
    		p = p->next; // 将LinkList p指向双向链表结尾
    	p->next = s;
    	s->prior = p; // 将结点*s插入到p的后面，插入到L中
    	s->next = NULL;
    	++length;

--------------------

**算法双向链表的插入：** 在带头结点的双向链表L中第i个位置之前插入元素e，i的合法值为1<=i<=表长+1。

Status ListInsert_DuL(DlinkList &L, int i, ElenType e) {
         //算法双向链表的插入
    	DlinkList s, p;
    	if (!(p = GetElemP_DuL(L, i))) //在L中确定第i个元素的位置指针p
    		return ERROR; //p为NULL时，第i个元素不存在
    	if (i == 1) {
        //在双向链表的第一个元素上插入
    		s = new DNode; //生成新结点s
    		s->data = e; //将结点s数据置为e
    		DlinkList p = L->next;
    		L->next = s;
    		s->prior = L;
    		s->next = p;//将结点*s插入L中
    		p->prior = s;
    		++length;
    	} else if (i == length) {
        //在双向链表的最后一个元素上插入
    		s = new DNode; //生成新结点s
    		s->data = e; //将结点s数据置为e
    		DlinkList p = L;
    		while (p->next)
    			p = p->next;//将LinkList p指向双向链表结尾
    		p->next = s;
    		s->prior = p;//将结点*s插入到p的后面，插入到L中
    		s->next = NULL;
    		++length;
    	} else {
         // 前插
    		s = new DNode; //生成新结点*s
    		s->data = e; //将结点*s数据域置为e
    		s->prior = p->prior; //将结点*s插入L中，
    		p->prior->next = s;
    		s->next = p;
    		p->prior = s;
    		++length;
    	}
    	return true;
    }

### 1.6 双链表的删除操作： ###

**删除带头结点的双向链表L中第i个位置之前插入的元素e，i的合法值为1<=i<=表长。**  
**【分析】**：删除p结点，要解决p的前驱与后继指向问题！！

*  1、在L中确定元素e的位置i，指针p指向第i个位置；
 *  2、满足：p的前驱的后继 == p的后继；
 *  3、满足：p的后继的前驱 == p的前驱 。

p->prior->next = p->next; // 修改被删结点的前驱结点的后继指针
    p->next->prior = p->prior; //修改被删结点的后继结点的前驱指针
    delete p; //释放被删结点的空间 
    --length;

--------------------

**删除带头结点的双向链表L中第i个位置之后插入的元素e，i的合法值为1<=i<=表长。**  
**【分析】**：删除p结点的后一个结点q，要解决q的前驱与后继指向问题！！

*  1、在L中确定元素e的位置i，指针p指向第i个位置；
 *  2、满足：p下一个结点是q的下一个结点；
 *  3、满足：q下一个结点的前驱是p结点。

// 删除p结点的后继结点
    bool DeleteNextDNode (DNode *p){
        
        if (!(p = GetElemP_DuL(L, i))) //在L中确定第i个元素的位置指针p
    		return ERROR; 	// p为NULL时，第i个元素不存在
        DNode *q = p->next; // 找到p的后继结点q
        if (q==NULL)
            return false;   // p没有后继
        p->next=q->next;
        if (q->next!=NULL)  // q结点不是最后一个结点
            q->next->prior=p;
        free(q);    //释放结点空间
        return true;
    }

--------------------

[84a180446c204d239fc5c912b2569d46.png]: /images/20220828/09357426407247f9ae00e3a845ac2cf9.png
[996a4b7a44274e31a7f3031ff5473805.png]: /images/20220828/a3e181a29c1a4484a06da1e35334df27.png