《数据结构》—— 单链表的插、删、查操作

ゞ浴缸里的玫瑰 2022-09-10 13:26 142阅读 0赞

### 单链表 ###

*   *  一、链表介绍
     *   *  1.1 顺序表与链表优缺点比较
         *  1.2 单链表定义
     *  二、单链表基本操作
     *   *  2.1 按位序插入（带头结点后插）
         *  2.2 指定结点的后插操作
         *  2.3 指定结点的前插操作
         *  2.4 按位序删除（带头结点）
         *  2.5 指定结点p的删除操作
         *  2.6 按位置查找值
         *  2.7 按值查找表结点

## 一、链表介绍 ##

### 1.1 顺序表与链表优缺点比较 ###

**顺序表**  
优点：可以随时存取表中的任意一个元素；  
缺点：插入和删除操作需要移动大量元素。

**链式存储线性表**  
优点：不需要使用地址连续的存储单元，插入和删除操作不需要移动元素，而只需修改指针；  
缺点：失去顺序表可随机存取的优点。

**单链表**  
优点：解决顺序表需要大量连续存储单元的缺点；  
缺点：单链表附加指针域，浪费存储空间，查找某个特定的结点时，需要从表头开始遍历，依次查找。

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

### 1.2 单链表定义 ###

线性表的链式存储称**单链表**，单链表结构由数据域(data)与指针域(next)组成。数据域存储数据元素；指针域存放其后继结点的地址。

**单链表实现方式：**  
不带头结点 --> 空表判断: L= =NULL。代码书写不便  
带头结点 --> 空表判断: L-> next==NULL。写代码更方便(基本提倡写这种)

**单链表结点类型代码描述：**

typedef struct LNode {
        
    	int data; // 结点的数据域
    	struct LNode *next; // 结点的指针域
    } LNode, *LinkList; // LinkList为指向结构体LNode的指针类型

“LinkList"等价于"LNode”。前者强调这是链表，后者强调这是结点，合适的地方使用合适的名字，代码可读性更高。

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

## 二、单链表基本操作 ##

### 2.1 按位序插入（带头结点后插） ###

ListInsert(&L,i,e)：插入操作。在表L中的第i个位置上插入指定元素e。平均时间复杂度O(n)  
![在这里插入图片描述][7988269caec5411caca2d6ef1a7fcfaa.png]  
**【分析】:** 1、先定义链表结构；2、在算法中，判断是否i位置<1，创建指针\*p指向头结点，在循环中 \*p找到第 i-1个节点，进行插入；3、创建一个节点s存储元素e，p的next位置是s的next位置，即把p赋值给s：**s->next=p->next**；接着变成p的next是s，即p->next=s。

typedef struct LNode {
        
    	ElemType data; // 结点的数据域
    	struct LNode *next; // 结点的指针域
    } LNode, *LinkList; // LinkList为指向结构体LNode的指针类型
    
    //第i个位置上插入指定元素e
    bool ListInsert(LinkList &L, int i, ElemType e){
        
        if(i<1)
            return false;
        LNode *p; // 指针p指向当前扫描到的结点
        int j=0;  // 当前p指向的是第几个结点
        p =L;     // L指向头结点，头结点是第0个结点(不存数据)
        while (p!=NULL && j<i-1) {
         //循环找到第 1-1个结点
            p=p->next;
            j++;
        }
        if(p==NULL) 	// i值不合法
            return false;
        LNode *s = (LNode*)malloc(sizeof(LNode));
        s->data = e;
        s->next=p->next;
        p->next=s;     // 将结点s连到p之后
        return true;   // 插入成功
    }

![在这里插入图片描述][fc91b3b65dbc456eb8b7b535bb45e579.png]  
若不带头结点的后插法，在第一个结点的操作与其他结点不同！  
【分析】: 1、创建新节点 \*s，2、s的数据域为元素e，s的next为L本身；3、那么s会变成原本的L。

if(i==1){
         // 插入第1个结点的操作与其他结点操作不同
    	LNode *s = (LNode*)malloc(sizeof(LNode));
    	s->data = e;
    	S->next=L ;
    	L=s;	//头指针指向新结点
    	return true;
    }

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

### 2.2 指定结点的后插操作 ###

//后插操作:在p结点之后插入元素e
    bool InsertNextNode (LNode *p, ElemType e){
        
        if (p==NULL)
            return false;
        LNode *s = (LNode *)malloc(sizeof(LNode));
        if (s==NULL) //内存分配失败
            return false;
        s->data = e;    //用结点s保存数据元素e
        s->next=p->next;
        p->next=s;     //将结点s连到p之后
        return true;
    }
    调用:return InsertNextNode(p,e)

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

### 2.3 指定结点的前插操作 ###

前插操作:在p结点之前插入元素e。  
**如何找到 p 结点的前驱结点？**  
【分析1】：已知p结点，可以传入头指针L，循环查找p的前驱q，再对q后插，则可以完成算法操作。时间复杂度O(n)。

【分析2】：已知p结点，创建s结点，我们思考当p的元素值是e，而s的元素值是p，那么可以就是前插操作！！

1.  s的next=p的next；
2.  p的next=s；
3.  s的data=p的data；
4.  p的data是e。

// 前插操作:在p结点之前插入元素e。
    bool InsertPriorNode (LNode *p, ElemType e){
        
        if (p==NULL)
            return false;
        LNode *s = (LNode *)malloc(sizeof(LNode));
        if (s==NULL) //内存分配失败
            return false;
        s->next=p->next;
        p->next=s;     //将结点s连到p之后
        s->data=p->data
        p->data=e;     // p中元素覆盖为e
        return true;
    }

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

### 2.4 按位序删除（带头结点） ###

ListDelete(&L,i,&e)：删除操作。删除表L中第i个结点的元素，并用e返回删除元素的值。时间复杂度O(n)  
![在这里插入图片描述][3116dcb2a5b246629e6fcc5f7651eeca.png]  
【分析】：跟2.1的插入操作类似，只是核心代码不一样。检查删除结点的位置合法性，查找出第i-1个结点 \*p，然后讲 \*p的指针域指向被删除结点 \*q的下一结点，最后释放 \*q。

if(p==NULL) 	// i值不合法
            return false;
        if(p->next == NULL) // 第i个结点没有
        	return false;
        LNode *q=p->next;   // 令q指向被删除结点
        e = q->data;        // 用e返回元素的值
        p->next=q->next;   // 将*q结点从链中“断开”
        free(q);        // 释放结点的存储空间
        return true;    // 删除成功

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

### 2.5 指定结点p的删除操作 ###

【分析】：要删除p结点。p的前驱未知，后继q可求。那么p与p的next交换数据域，再把q的next赋值给p的next即可，最后释放q。时间复杂度O(1)

//删除指定结点p
    bool DeleteNode (LNode *p){
        
        if (p==NULL)
            return false;
        LNode *q=p->next;    // 令q指向*p的后继结点
        p->data=p->next->data; // 和后继结点交换数据域
        p->next=q->next;       // 将*q结点从链中“断开”
        free(q);        // 释放后继结点的存储空间
            return true;
    }
    【注意】当指定结点是最后一个结点时，需要特殊处理

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

### 2.6 按位置查找值 ###

按位查找，返回第i个元素(带头结点)  
【分析】：1、判断i的合法位置，创建结点 \*p指向头结点L；2、while循环找到第i个结点，最后return p。时间复杂度O(n)

在单链表中从第一个结点出发，顺指针next域逐个往下搜索，直到找到第i个结点为止，否则返回最后一个结点指针域NULL。

// 按位查找，返回第i个元素(带头结点)
    LNode *GetElem(LinkList L, int i){
        
        if(i<0 )
            return NULL;
        LNode *p;   //指针p指向当前扫描到的结点
        int j=0;    //当前p指向的是第几个结点
        p=L;       //L指向头结点，头结点是第0个结点(不存数据)
        while (p!=NULL && j<i) {
         //循环找到第i个结点
            p=p->next;
            j++;
        }
        return p;
    }

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

### 2.7 按值查找表结点 ###

从单链表的第一个结点开始，由前往后依次比较表中各结点数据域的值，若某结点数据域的值等于给定值e,则返回该结点的指针:若整个单链表中没有这样的结点，则返回NULL，时间复杂度O(n)。

LNode *LocateElem (LinkList L, ElemType e) {
        
        LNode *p=L->next;
        while (p!=NULL&&p->data!=e) // 从第1个结点开始查找data域为e的结点
            p-p->next; 
        return P;    // 找到后返回该结点指针，否则返回NULL
    }

[7988269caec5411caca2d6ef1a7fcfaa.png]: /images/20220829/f6d8e69e0c944b4cbd69d51cd638808a.png
[fc91b3b65dbc456eb8b7b535bb45e579.png]: /images/20220829/21090f3ed52b4678b677f27ca4b1c085.png
[3116dcb2a5b246629e6fcc5f7651eeca.png]: /images/20220829/ef3c9e2bfe764bd4aa84dbcf15a73c92.png