数据结构与算法线性表(二)

柔情只为你懂 2022-09-13 05:26 240阅读 0赞

# ✍、目录总览 #

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA55Sf5ZG95piv5pyJ5YWJ55qE_size_20_color_FFFFFF_t_70_g_se_x_16_pic_center]

# 1、线性表 #

**定义**：线性表是具有**相同**数据类型的n(n≥0)个数据元素的有限序列，其中n为**表长**，当n = 0 时线性表是一个空表。若用L命名线性表，则其一般表示为：

L = (a1,a2,....,ai,ai+1,.....,an)

**线性表的特点**：

*  线性表中的元素的个数是有限的
 *  线性表中的元素有先后次序
 *  线性表中的数据类型都相同，这意味着每个元素占有相同大小的存储空间
 *  ai 是线性表中的 “第i个” 元素线性表中的位序（位序是从1开始，数组下标从0开始）
 *  a1是表头元素，an是表尾元素
 *  除第一个元素外，每个元素有且仅有一个直接前驱；除最后一个元素外，每个元素有且仅有一个直接后继

# 2、顺序表 #

**定义**：把用顺序存储的方式实现的线性表叫做顺序表

**顺序存储**：把逻辑上相邻的元素存储在物理位置上也相邻的存储单元中，元素之间的关系由存储单元的邻接关系来体现。

**顺序表有两种实现方式**：静态分配实现和动态分配实现

## 2.1、静态分配实现 ##

#define MaxSize 10; //定义最大长度
    typedef struct{ 
        ElemType data[MaxSize];		//用静态的"数组"存放数据元素
        int length;					//顺序表的当前长度
    }SqList;						//顺序表的类型定义(静态分配方式)

### 2.2.1、初始化顺序表 ###

#include<stdio.h>
    #define MaxSize 10; //定义最大长度
    typedef struct{ 
        ElemType data[MaxSize];		//用静态的"数组"存放数据元素
        int length;					//顺序表的当前长度
    }SqList;						//顺序表的类型定义
    
    // 基本操作-初始化一个顺序表
    void InitList(SqList &L){ 
        for(int i=0;i<MaxSize;i++)
        { 
            L.data[i] = 0;			//将所有数据元素设置为默认初始值
        }
        L.length = 0;				//顺序表初始长度为0
    }
    
    
    int main(){ 
        SqList L; 					//声明一个顺序表
        InitList(L);				//初始化顺序表
        
        return 0;
    }

## 2.2、动态分配实现 ##

#define MaxSize 10; //定义最大长度
    typedef struct{ 
        ElemType *data;				//指针指向第一个数据元素
        int MaxSize;				//顺序表的最大容量
        int length;					//顺序表的当前长度
    }SeqList;						//顺序表的类型定义(动态分配方式)

### 2.2.1、初始化顺序表 ###

#define MaxSize 10; //定义最大长度
    #include<stdio.h>
    #include<stdlib.h>
    typedef struct{ 
        ElemType *data;				//指针指向第一个数据元素
        int MaxSize;				//顺序表的最大容量
        int length;					//顺序表的当前长度
    }SeqList;						//顺序表的类型定义
    
    // 基本操作-初始化一个顺序表
    void InitList(SeqList &L){ 
        //用malloc函数申请一片连续的存储空间
        L.data=(ElemType *)malloc(sizeof(ElemType)*InitSize);
        L.length = 0;			//顺序表初始长度为0
        L.MaxSize = InitSize;	//顺序表的最大长度
    }
    
    // 增加动态数组的长度
    void IncreaseSize(SeqList &L,int len){ 
        int *p = L.data;		//让指针p指向顺序表中的第一个数据元素
        L.data=(ElemType *)malloc(sizeof(ElemType)*(L.MaxSize+len));
        for(int i=0; i<L.length; i++){ 
            L.data[i] = p[i];	//将数据复制到新区域
        }
        L.MaxSize = L.MaxSize + len;	//顺序表最大长度增加 len
        free(p);						//释放原来的内存空间
    }
    
    
    int main(){ 
        SeqList L;	//声明一个顺序表
        InitList(L);//初始化顺序表
        // 往顺序表中随便插入几个元素
        IncreaseSize(L,5);
        return 0;
    }

## 2.3、顺序表的特点 ##

1.  **随机访问**：即可以在O(1)时间内中找到第i个元素
2.  **存储密度高**，每个节点只存储数据元素
3.  扩展容量不方便
4.  **插入、删除操作不方便，需要移动大量元素**

## 2.4、顺序表的插入 ##

`ListInsert(&L,i,e)` ：插入操作，在表L中的第 i 个位置上插入指定元素e

#define MaxSize 10; //定义最大长度
    
    typedef struct{ 
        ElemType data[MaxSize];		//用静态的"数组"存放数据元素
        int length;					//顺序表的当前长度
    }SqList;						//顺序表的类型定义(静态分配方式)
    
    // 插入操作:在L的位序 i 处插入元素e
    bool ListInsert(SqList &L,int i,int e){ 
        if(i<1 || i>L.length+1)		//判断i的范围是否有效
            return false;
        if(L.length >= MaxSize)		//当前存储空间已满,不能插入
            return false;
        //将第i个元素及之后的元素后移
        for(int j=L.length;j>=i;j--)
        { 
            L.data[j] = L.data[j-1];
        }
        L.data[i-1]=e;				//在位置i处放入e,注意位序、数组下标的关系
        L.length++;					//长度加1
        return true;
    }
    
    
    
    int main(){ 
        SqList L;	//声明一个顺序表 
        InitList(L);//初始化顺序表
        //...此处省略一些代码,插入几个元素
        ListInsert(L,3,3);
        return 0;
    }

![在这里插入图片描述][b595381811c24583abd4f2d4406e4b6e.png_pic_center]

### 2.4.1、插入操作时间复杂度 ###

只需关注最深层循环语句的执行次数与问题规模n的关系

//将第i个元素及之后的元素后移
    for(int j=L.length;j>=i;j--)
    { 
        L.data[j] = L.data[j-1];
    }

*  最好情况：新元素插入到表尾，不需要移动元素，时间复杂度O(1)
 *  最坏情况：新元素插入到表头，需要将原有的n个元素全都向后移动，循环n次，时间复杂度O(n)
 *  平均情况：假设新元素插入到任何一个位置的概率相同，时间复杂度O(n)

## 2.5、顺序表的删除 ##

`ListDelete(&L,i,&e)`：删除操作。删除表L中第i个位置的元素，并用e返回删除元素的值

bool ListDelete(SqList &L,int i,int &e){ 
        if(i<1 || i>L.length+1)		//判断i的范围是否有效
            return false;
        e = L.data[i-1];			//将被删除的元素赋值给e
        //将第i个位置后的元素前移
        for(int j=i;j<length;j++)
        { 
            L.data[j-1] = L.data[j];
        }
        
        L.length--;					//线性表长度减1
        return true;
    }
    
    
    
    int main(){ 
        SqList L;	//声明一个顺序表 
        InitList(L);//初始化顺序表
        //...此处省略一些代码,插入几个元素
        int e = -1;	//用变量e把删除的元素"带回来"
       	if(ListDelete(L,3,e)){ 
            print("已删除第3个元素,删除元素值为=%d\n",e);
        }else{ 
            print("位序i不合法,删除失败\n");
        }
        return 0;
    }

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA55Sf5ZG95piv5pyJ5YWJ55qE_size_8_color_FFFFFF_t_70_g_se_x_16_pic_center]

*  这里函数定义中的参数e加了引用符号，目的是使得在此时声明的变量e和main函数中声明的变量e是同一片内存空间

### 2.5.1、删除操作时间复杂度 ###

只需关注最深层循环语句的执行次数与问题规模n的关系

//将第i个位置后的元素前移
    for(int j=i;j<length;j++)
    { 
        L.data[j-1] = L.data[j];
    }

*  最好情况：删除表尾元素，不需要移动其他元素，最好时间复杂度O(1)
 *  最坏情况：删除表头元素，需要将后续的 n-1 个元素全都向前移动。循环n-1 次，最坏时间复杂度O(n)
 *  平均情况：平均时间复杂度O(n)

### 2.5.2、总结 ###

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA55Sf5ZG95piv5pyJ5YWJ55qE_size_20_color_FFFFFF_t_70_g_se_x_16_pic_center 1]

## 2.6、顺序表的查找 ##

### 2.6.1、静态分配按位查找 ###

`GetElem(L,i)`：按位查找操作。获取表L中第i个位置的元素的值

typedef struct{ 
        ElemType data[MaxSize];		//用静态的"数组"存放数据元素
        int length;					//顺序表的当前长度
    }SqList;						//顺序表的类型定义(静态分配方式)
    
    
    
    ElemType GetElem(SqList L,int i){ 
        return L.data[i-1];
    }

### 2.6.2、动态分配按位查找 ###

#define InitSize 10; //顺序表的初始长度
    typedef struct{ 
        ElemType *data;				//指针指向第一个数据元素
        int MaxSize;				//顺序表的最大容量
        int length;					//顺序表的当前长度
    }SeqList;						//顺序表的类型定义(动态分配方式)
    
    
    ElemType GetElem(SqList L,int i){ 
        return L.data[i-1];			//和访问普通数组的方法一样
    }

### 2.6.3、按位查找时间复杂度 ###

由于顺序表的各个数据元素在内存中连续存放，因此可以根据起始地址和数据元素大小立即找到第i个元素➡"随机存取"特性，按位查找的时间复杂度为O(1)

### 2.6.4、按值查找 ###

`LocateElem(L,e)`：按值查找操作。在表L中查找值为e的元素

#define InitSize 10; //顺序表的初始长度
    typedef struct{ 
        ElemType *data;				//指针指向第一个数据元素
        int MaxSize;				//顺序表的最大容量
        int length;					//顺序表的当前长度
    }SeqList;						//顺序表的类型定义(动态分配方式)
    
    //在顺序表L中查找第一个元素值等于e的元素，并返回其位序
    int LocateElem(SeqList L,ElemType e){ 
    	for(int i=0;i<L.length;i++)
        { 
            if(L.data[i]==e)
            { 
                return i+1;		//数组小标为i的元素值等于e,返回其位序i+1
            }
            return 0;			//退出循环,说明查找失败
        }
    }

### 2.6.5、按值查找时间复杂度 ###

关注最深层循环语句的执行次数与问题规模n的关系，问题规模`n=L.length（表长）`

int LocateElem(SeqList L,ElemType e){ 
    	for(int i=0;i<L.length;i++)
        { 
            if(L.data[i]==e)
            { 
                return i+1;		//数组小标为i的元素值等于e,返回其位序i+1
            }
            return 0;			//退出循环,说明查找失败
        }
    }

*  最好情况：目标元素在表头，只需要循环1次，最好的时间复杂度为O(1)
 *  最坏情况：目标元素在表尾，需要循环n次，最坏时间复杂度为O(n)
 *  平均情况：O(n)

### 2.6.6、总结 ###

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA55Sf5ZG95piv5pyJ5YWJ55qE_size_20_color_FFFFFF_t_70_g_se_x_16_pic_center 2]

# 3、单链表 #

顺序表：用顺序存储结构实现的线性表叫做顺序表

*  顺序表优点：可随机存取，存储密度高
 *  顺序表缺点：要求大片连续空间，改变容量不方便

链表：用链式存储结构实现的线性表叫做链表，链表分为：

*  单链表
 *  双链表
 *  循环链表
 *  静态链表

单链表优点：不要求大片连续空间，改变容量方便

单链表缺点：不可随机存取，要耗费一定空间存放指针

## 3.1、单链表的定义 ##

typedef struct LNode{ 				//定义单链表结点类型
        ElemType data;					//定义单链表结点类型(数据域)
        struct LNode * next;			//每个节点存放一个数据元素(指针域)
    }LNode,*LinkList;					//LinkList为指向结构体LNode的指针类型
    //增加一个新的结点:在内存中申请一个结点所需空间,并用指针p指向这个结点
    LNode *p =(LNode *)malloc(sizeof(LNode));
    
    // 上述定义代码等价于
    struct LNode{ 
        ElemType data;
        struct LNode *next;
    };
    typedef struct LNode LNode;			//struct LNode = LNode
    typedef struct LNode * LinkList;	//struct LNode *= LinkList 
    
    //增加一个新的结点:在内存中申请一个结点所需空间,并用指针p指向这个结点
    struct LNode *p =(struct LNode *)malloc(sizeof(struct LNode))

要表示一个单链表时，只需声明一个头指针L，指向单链表的第一个结点

LNode *L;		//声明一个指向单链表的第一个结点的指针
    LinkList L;		//声明一个指向单链表的第一个结点的指针

上述两种声明方式有什么区别呢？

*  `LNode *` ： 强调这是一个结点
 *  `LinkList`：强调这是一个单链表

## 3.2、初始化不带头结点的单链表 ##

typedef struct LNode{ 				//定义单链表结点类型
        ElemType data;					//定义单链表结点类型(数据域)
        struct LNode * next;			//每个节点存放一个数据元素(指针域)
    }LNode,*LinkList;					//LinkList为指向结构体LNode的指针类型
    
    // 初始化一个空的单链表
    bool InitList(LinkList &L){ 
        L = NULL;						//空表,暂时还没有任何结点
        return true;					
    }
    
    void test(){ 
        LinkList L;						//声明一个指向单链表的指针
        //初始化一个空表
        InitList(L);
    }

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA55Sf5ZG95piv5pyJ5YWJ55qE_size_9_color_FFFFFF_t_70_g_se_x_16_pic_center]

## 3.3、不带头结点的单链表是否为空 ##

//判断单链表是否为空
    bool Empty(LinkList L){ 
        return (L==NULL);
    }

## 3.4、初始化带头结点的单链表 ##

typedef struct LNode{ 				//定义单链表结点类型
        ElemType data;					//定义单链表结点类型(数据域)
        struct LNode * next;			//每个节点存放一个数据元素(指针域)
    }LNode,*LinkList;					//LinkList为指向结构体LNode的指针类型
    
    
    //初始化一个单链表(带头结点)
    bool InitList(LinkList &L){ 
        //用malloc申请一片空间存一个结点
        //并且把malloc返回的地址赋给头指针L,也就是说头指针L是指向了这个结点
        L =(LNode *)malloc(sizeof(LNode));	
        if(L==NULL)							//分配不足,分配失败
        { 
           return false; 
        }
        L->next = NULL;						//头节点之后暂时还没有结点
        return true;
    }
    
    void test(){ 
        LinkList L;							//声明一个指向单链表的指针
        //初始化一个空表
        InitList(L);
    }

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA55Sf5ZG95piv5pyJ5YWJ55qE_size_8_color_FFFFFF_t_70_g_se_x_16_pic_center 1]

## 3.5、带头结点的单链表是否为空 ##

//判断单链表是否为空(带头结点)
    bool Empty(LinkList L){ 
        if(L->next == NULL){ 
            return true;
        }else{ 
            return false;
        }
    }

## 3.6、单链表的插入 ##

### 3.6.1、带头结点按位序插入 ###

`ListInsert(&L,i,e)`：插入操作。**在表L中的第i个位置上插入指定元素e**

(找到第i-1个结点，将新结点插入其后)

![在这里插入图片描述][afabed3c83144344b58e15fd59ba9971.png_pic_center]

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){ 	//循环找到第 i-1 个结点
            p=p->next;
            j++;
        }
        if(p==NULL)		//i值不合法
        { 
            return false;
        }
        LNode *s = (LNode *)malloc(sizeof(LNode));
        s->data=e;
        //将s指向结点的next指针指向p指向结点的next指针
        s->next = p->next;	
        p->next = s;	//将p指向结点的next指针指向s
        return true;	//插入成功
    }

分析：

1.  如果 i=1(也就是在表头插入元素)：时间复杂度O(1)

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA55Sf5ZG95piv5pyJ5YWJ55qE_size_20_color_FFFFFF_t_70_g_se_x_16_pic_center 3]

1.  如果 i = 3(也就是在表中插入元素)

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA55Sf5ZG95piv5pyJ5YWJ55qE_size_20_color_FFFFFF_t_70_g_se_x_16_pic_center 4]

1.  如果 i = 5(也就是在表尾插入元素)：时间复杂度O(n)

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA55Sf5ZG95piv5pyJ5YWJ55qE_size_20_color_FFFFFF_t_70_g_se_x_16_pic_center 5]

### 3.6.2、不带头结点按位序插入 ###

`ListInsert(&L,i,e)`：插入操作。**在表L中的第i个位置上插入指定元素e**

(找到第i-1个结点，将新结点插入其后)

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA55Sf5ZG95piv5pyJ5YWJ55qE_size_20_color_FFFFFF_t_70_g_se_x_16_pic_center 6]

bool ListInsert(LinkList &L,int i,ElemType e){ 
        if(i<1)
        { 
            return false;
        }
        if(i==1)		//插入第1个结点的操作与其他结点操作不同
        { 
            LNode *s =(LNode *)malloc(sizeof(LNode));
            s->data = e;
            s->next = L;
            L = s;		//头指针指向新结点
            return true;
        }
        
        
        LNode *p;		//指针p指向当前扫描到的结点
        int j=1;		//当前p指向的是第几个结点
        p = L;			//p指向第1个结点(注意:不是头结点)
        
        while(P!=NULL && j<i-1){ 	//循环找到第 i-1 个结点
            p=p->next;
            j++;
        }
        if(p==NULL)		//i值不合法
        { 
            return false;
        }
        LNode *s = (LNode *)malloc(sizeof(LNode));
        s->data=e;
        //将s指向结点的next指针指向p指向结点的next指针
        s->next = p->next;	
        p->next = s;	//将p指向结点的next指针指向s
        return true;	//插入成功
    }
        
    }

*  结论：不带头结点写代码不方便，推荐用带头结点
 *  注意：考试中带头、不带头都有可能考察，注意审题

## 3.7、指定结点的后插操作 ##

后插操作：在结点之后插入元素

![在这里插入图片描述][109ba68f152d40e3baf37fcf200f493c.png_pic_center]

//后插操作:在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->next = p->next;
        p->next = s;
        return true;
    }

## 3.8、指定结点的前插操作 ##

前插操作：在结点之前插入元素

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA55Sf5ZG95piv5pyJ5YWJ55qE_size_20_color_FFFFFF_t_70_g_se_x_16_pic_center 7]

//前插操作:在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中元素复制到s中
        p->data = e;		//p中元素覆盖为e
        return true;
    }

王道书中的版本：

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA55Sf5ZG95piv5pyJ5YWJ55qE_size_20_color_FFFFFF_t_70_g_se_x_16_pic_center 8]

//前插操作:在p结点之前插入结点s
    bool InsertPriorNode(LNode *p,LNode *s){ 
        if(p==NULL || s==NULL)
        { 
            return false;
        }
        s->next = p->next;
        p->next = s;				//s连到p之后
        ElemType temp = p->data;	//交换数据域部分
        p->data = s->data;
        s->data = temp;
        return true;
    }

## 3.9、单链表的删除 ##

### 3.9.1、带头结点按位序删除 ###

`ListDelete(&L,i,&e)`：删除操作。删除表L中第i个位置的元素，并用e返回删除元素的值(找到第i-1个结点，将其指针指向第i+1个结点，并释放第i个结点)

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA55Sf5ZG95piv5pyJ5YWJ55qE_size_20_color_FFFFFF_t_70_g_se_x_16_pic_center 9]

bool ListDelete(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)	//循环找到第 i-1 个结点
        { 
            p = p->next;
            j++
        }
        if(p==NULL)  			// i值不合法
        { 
            return false;
        }
        if(p->next == NULL)		//第 i-1 个结点之后已无其他结点
        { 
            return false;
        }
        LNode *q = p->next;		//令q指向被删除结点
        e = q->data;			//用e返回元素的值
        p->next = q->next;		//将*q结点从链中断开
        free(q);				//释放结点的存储空间
        return true;			//删除成功
    }

### 3.9.2、指定结点的删除 ###

`bool DeleteNode(LNode *p)`：删除结点p

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA55Sf5ZG95piv5pyJ5YWJ55qE_size_20_color_FFFFFF_t_70_g_se_x_16_pic_center 10]

//删除指定结点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;
    }

## 3.10、单链表的查找 ##

### 3.10.1、按位查找 ###

`GetElem(L,i)`：按位查找操作。获取表L中第i个位置的元素的值。

//按位查找,返回第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;		//让p指针依次向后移
            j++;
        }
        return p;
    }

1.  如果i=0

![在这里插入图片描述][fb2792d54480402698c820f290cdbd22.png_pic_center]

1.  如果 i = 8(i大于链表长度)

![在这里插入图片描述][60b6bf7372334494ad65b61bb08c2e3c.png_pic_center]

王道书版本：

![在这里插入图片描述][e6a63d1c78174d62adcab1254d40ac3b.png_pic_center]

LNode *GetElem(LinkList L,int i){ 
        int j=1;
        LNode *p = L->next;
        if(i==0)
        { 
            return L;
        }
        if(i<1)
        { 
            return NULL;
        }
        while(p!=NULL && j<i)
        { 
        	p = p->next;
            j++;
        }
        return p;
    }

### 3.10.2、按值查找 ###

`LocateElem(L,e)`：按值查找操作。在表L中查找具有给定关键字值的元素

![在这里插入图片描述][3e6dd00405fc4e8e90f5346424a9834e.png_pic_center]

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

### 3.10.3、求单链表长度 ###

![在这里插入图片描述][26892c30ab564b3da11362e4d0f215a7.png_pic_center]

//求表的长度
    int Length(LinkList L)
    { 
        int len = 0;			//统计表长
        LNode *p = L;		
        while(p->next !=NULL)
        { 
            p = p->next;
            len++;
        }
        return len;
    }

### 3.10.4、总结 ###

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA55Sf5ZG95piv5pyJ5YWJ55qE_size_20_color_FFFFFF_t_70_g_se_x_16_pic_center 11]

## 3.11、单链表的建立 ##

如果给你很多个数据元素，要把它们存到一个单链表里边，咋弄呢？

1.  初始化一个单链表
2.  每次取一个数据元素，插入到表尾/表头

### 3.11.1、尾插法建立单链表 ###

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA55Sf5ZG95piv5pyJ5YWJ55qE_size_19_color_FFFFFF_t_70_g_se_x_16_pic_center]

LinkList List_TailInsert(LinkList &L)		//正向建立单链表
    { 
        int x;									//设ElemType为整型
        L = (LinkList)malloc(sizeof(LNode));	//建立头结点
        LNode *s,*r=L;							//r为表尾指针
        scanf("%d",&x);							//输入结点的值
        while(x!=9999)
        { 
            s=(LNode *)malloc(sizeof(LNode));	
            s->data = x;
            r->next = s;
            r = s;								//r指向新的表尾结点
            scanf("%d",&x);				
        }
        r->next = NULL;							//尾结点指针置空
        return L;
    }

尾插法的时间复杂度：O(n)

### 3.11.2、头插法 ###

头插法:对头结点进行后插操作

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA55Sf5ZG95piv5pyJ5YWJ55qE_size_19_color_FFFFFF_t_70_g_se_x_16_pic_center 1]

LinkList List_HeadInsert(LinkList &L){ 
        LNode *s;
        int x;
       	L = (LinkList)malloc(sizeof(LNode));	//创建头结点
        L->next = NULL;							//初始化为空链表(初始化单链表,都先把头指针指向NULL)
        scanf("%d",&x);							//输入结点的值
        while(x!=9999)							//输入9999表示结束
        { 
            s = (LNode *)malloc(sizeof(LNode));	//创建新结点
            s->data = x;
            s->next = L->next;
            L->next = s;						//将新结点插入表中,L为头指针
            scanf("%d",&x);
        }
        return L;
    }

### 3.11.3、总结 ###

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA55Sf5ZG95piv5pyJ5YWJ55qE_size_20_color_FFFFFF_t_70_g_se_x_16_pic_center 12]

# 4、双链表 #

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA55Sf5ZG95piv5pyJ5YWJ55qE_size_20_color_FFFFFF_t_70_g_se_x_16_pic_center 13]

## 4.1、双链表的定义 ##

typedef struct DNode{ 				//定义双链表结点类型
        ElemType data;					//数据域
        struct DNode *prior,*next;		//前驱和后继指针
    }DNode,*DLinklist;

## 4.2、双链表的初始化 ##

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA55Sf5ZG95piv5pyJ5YWJ55qE_size_13_color_FFFFFF_t_70_g_se_x_16_pic_center]

//初始化双链表(带头结点)
    bool InitDLinkList(DLinklist &L){ 
        L = (DNode *)malloc(sizeof(DNode));			//分配一个头结点
        if(L==NULL)									//内存不足,分配失败
        { 
            return false;
        }
        L->prior = NULL;							//头结点的prior永远指向NULL
        L->next = NULL;								//头结点之后暂时还没有结点
        return true;
    }
    
    
    viod testDLinkList(){ 
        //初始化双链表
        DLinklist L;
        InitDLinkList(L);
    }

*  `DLinklist` 等价于`DNode *`
 *  `DLinklist` 强调这是一个链表
 *  `DNode *` 强调这是一个结点

## 4.3、判断双链表是否为空 ##

判断双链表是否为空：判断头结点的下一个是否为空

//判断双链表是否为空(带头结点)
    bool Empty(DLinklist L){ 
        if(L->next == NULL)
        { 
            return true;
        }else{ 
            return false;
        }
    
    }

## 4.4、双链表的插入 ##

### 4.4.1、后插操作 ###

如果p结点是最后一个结点(特殊情况)：

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA55Sf5ZG95piv5pyJ5YWJ55qE_size_20_color_FFFFFF_t_70_g_se_x_16_pic_center 14]

//在p结点之后插入s结点
    bool InsertNextDNode(DNode *p,DNode *s){ 
        if(p=NULL || s=NULL)							//非法参数
        { 
            return false;
        }
        s->next = p->next;
        if(p->next != NULL)
        { 												//如果p结点有后继结点
            p->next->prior = s;
        }
        s->prior = p;
        p->next = s;	
        return true;
    }

如果p是中间一个结点：

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA55Sf5ZG95piv5pyJ5YWJ55qE_size_20_color_FFFFFF_t_70_g_se_x_16_pic_center 15]

### 4.4.2、按位序插入 ###

按位序插入：只需从头结点开始，找到某一个位序的前驱结点，然后对这个前驱结点执行后插操作

### 4.4.3、前插操作 ###

前插操作：只需找到此结点的前驱结点，然后对其前驱结点进行后插操作，即为前插操作

## 4.5、双链表的删除 ##

当q结点不是最后一个结点时：

![在这里插入图片描述][1bf0fe62dcc24b39a535162ec23d882f.png_pic_center]

//删除p结点的后继结点
    bool DeleteNextDNode(DNode *p){ 
        if(p==NULL)
        { 
            return false;
        }
        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;
    }

当q结点是最后一个结点时：

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA55Sf5ZG95piv5pyJ5YWJ55qE_size_20_color_FFFFFF_t_70_g_se_x_16_pic_center 16]

## 4.6、双链表的销毁 ##

void DestoryList(DLinklist &L){ 
        //循环释放各个数据结点
        while(L->next !=NULL)
        { 
            DeleteNextDNode(L);
        }
        free(L);		//释放头结点
        L=NULL;			//头指针指向NULL
    }

## 4.7、双链表的遍历 ##

后向遍历：

while(p != NULL){ 
        //对结点p做相应处理
        p = p->next;
    }

前向遍历：

while(p != NULL){ 
        //对结点p做相应处理
        p = p->prior;
    }

前向遍历(跳过头结点)：

while(p->prior!=NULL){ 
        //对结点p做相应处理
        p = p->prior;
    }

## 4.8、总结 ##

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA55Sf5ZG95piv5pyJ5YWJ55qE_size_20_color_FFFFFF_t_70_g_se_x_16_pic_center 17]

# 5、循环链表 #

*  单链表：表尾结点的next指针指向NULL

![在这里插入图片描述][b20be6d0f4204019bf912f6082858b48.png_pic_center]

*  循环单链表：表尾结点的next指针指向头结点

![在这里插入图片描述][a17301cb73224cf29f24794cb17d5261.png_pic_center]

## 5.1、循环单链表 ##

头结点next指针指向头结点：

![在这里插入图片描述][69a4b7aa0dc64249bf93c82ab72209a3.png_pic_center]

### 5.1.1、初始化循环单链表 ###

typedef struct LNode{ 		//定义单链表结点类型
        ElemType data;			//每个结点存放一个数据元素
        struct LNode *next;		//指针指向下一个结点
    }LNode,*LinkList;
    
    //初始化一个循环单链表
    bool InitList(LinkList &L){ 
        L = (LNode *)malloc(sizeof(LNode));		//分配一个头结点
        if(L == NULL)
        { 
            return false;
        }
        L->next = L;							//头结点next指向头结点
        return true;
    }

### 5.1.2、判断循环单链表是否为空 ###

判断循环单链表是否为空：判断头结点的next指针是否指向它自己

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

### 5.1.3、判断循环单链表表尾结点 ###

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA55Sf5ZG95piv5pyJ5YWJ55qE_size_18_color_FFFFFF_t_70_g_se_x_16_pic_center]

//判断结点p是否是循环单链表的表尾结点
    bool isTail(LinkList L,LNode *p){ 
        if(p->next == L)
        { 
            return true;
        }else{ 
            return false;
        }
    }

## 5.2、循环双链表 ##

*  双链表：表头结点的prior指向NULL，表尾结点的next指向NULL

![在这里插入图片描述][1e26f7ae661d4351a68b00f601a56440.png_pic_center]

*  循环双链表：表头结点的prior指向表尾结点，表尾结点的next指向头结点

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA55Sf5ZG95piv5pyJ5YWJ55qE_size_20_color_FFFFFF_t_70_g_se_x_16_pic_center 18]

### 5.2.1、初始化循环双链表 ###

初始化循环双链表：让头结点的prior和next指针都指向头结点

![在这里插入图片描述][c6acec76f4f14711b8a17c624cb4bd88.png_pic_center]

bool InitDLinkList(DLinklist &L){ 
        L = (DNode *)malloc(sizeof(DNode));				//分配一个头结点
        if(L == NULL)									//内存不足,分配失败
        { 
            return false;
        }
        L->prior = L;									//头结点的prior指向头结点
        L->next = L;									//头结点的next指向头结点
        return true;
    }
    
    void testDLinkList(){ 
        //初始化循环双链表
        DLinklist L;
        InitDLinkList(L);
    }

### 5.2.2、判断循环双链表是否为空 ###

判断循环双链表是否为空：头结点的next指针是否指向了它自身

//判断循环双链表是否为空
    bool Empty(DLinkList L){ 
        if(L->next == L)
        { 
            return true;
        }else{ 
            return false;
        }
    }

### 5.2.3、判断循环双链表表尾结点 ###

判断循环双链表表尾结点:这个结点的next指针是否指向了头结点

//判断结点p是否是循环双链表的表尾结点
    bool isTail(DLinkList L,DNode *p){ 
        if(p->next == L)
        { 
            return true;
        }else{ 
            return false;
        }
    }

## 5.3、循环双链表的插入 ##

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA55Sf5ZG95piv5pyJ5YWJ55qE_size_20_color_FFFFFF_t_70_g_se_x_16_pic_center 19]

//在p结点之后插入s结点
    bool InsertNextDNode(DNode *p,DNode *s){ 
        s->next = p->next;							//将结点*s插入到结点*p之后
        p->next->prior = s;		
        s->prior = p;
        p->next = s;
    }

## 5.4、循环双链表的删除 ##

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA55Sf5ZG95piv5pyJ5YWJ55qE_size_20_color_FFFFFF_t_70_g_se_x_16_pic_center 20]

//删除p的后继结点q
    p->next = q->next;
    q->next->prior = p;
    free(q);

## 5.5、总结 ##

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA55Sf5ZG95piv5pyJ5YWJ55qE_size_20_color_FFFFFF_t_70_g_se_x_16_pic_center 21]

# 6、静态链表 #

**单链表**：各个结点在内存中星罗棋布、散落天涯。

**静态链表**：分配一整片连续的内存空间，各个结点集中安置。**静态链表中的每个结点包含数据元素和下一个结点的数组下标。**

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA55Sf5ZG95piv5pyJ5YWJ55qE_size_17_color_FFFFFF_t_70_g_se_x_16_pic_center]

我们看上图：

*  静态链表中数组下标为 0 的结点充当头结点的角色，而头结点的下一个结点是存储在数组下标为 2 的位置，数组下标为 2 的位置结点数据元素为 e1，下一个结点为数组下标为 1 的结点，也就是数据元素为 e2 的结点。
 *  单链表中表尾指针是指向NULL，静态链表中游标为 -1 表示已经到达表尾。
 *  假如每个数据元素 4B，每个游标 4B(每个结点共8B)，设起始地址为 addr，则 e1 的存放地址为 addr + 8 \* 2

## 6.1、代码定义静态链表 ##

#define MaxSize 10 // 静态链表的最大长度
    typedef struct{ 						// 静态链表结构类型的定义
        ElemType data;					// 存储数据元素
        int next;						// 下一个元素的数组下标
    }SLinkList[MaxSize];

上述代码其实等价于下面代码：

#define MaxSize 10 // 静态链表的最大长度
    struct Node{ 						// 静态链表结构类型的定义
        ElemType data;					// 存储数据元素
        int next;						// 下一个元素的数组下标
    };
    
    typedef struct Node SLinkList[MaxSize];	// 给 struct Node 起别名为 SLinkList[MaxSize]

// 可以用 SLinkList 定义 "一个长度为MaxSize的Node型数组"
    SlinkList a;
    // 这个数组元素有 MaxSize 这么多,每个数组元素类型都是 struct Node
    // 等价于 struct Node a[MaxSize]

# 7、第一章总结 #

1.  顺序表和链表都是线性结构，都属于线性表

<table> 
 <thead> 
  <tr> 
   <th>线性表</th> 
   <th>优点</th> 
   <th>缺点</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>顺序表(顺序存储)</td> 
   <td>支持随机存取、存储密度高</td> 
   <td>大片连续空间分配不方便，改变容量不方便</td> 
  </tr> 
  <tr> 
   <td>链表(链式存储)</td> 
   <td>离散的小空间分配方便，改变容量方便</td> 
   <td>不可随机存取，存储密度低</td> 
  </tr> 
 </tbody> 
</table>

1.  创建

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA55Sf5ZG95piv5pyJ5YWJ55qE_size_20_color_FFFFFF_t_70_g_se_x_16_pic_center 22]

1.  销毁

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA55Sf5ZG95piv5pyJ5YWJ55qE_size_20_color_FFFFFF_t_70_g_se_x_16_pic_center 23]

1.  增删

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA55Sf5ZG95piv5pyJ5YWJ55qE_size_20_color_FFFFFF_t_70_g_se_x_16_pic_center 24]

1.  查找

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA55Sf5ZG95piv5pyJ5YWJ55qE_size_20_color_FFFFFF_t_70_g_se_x_16_pic_center 25]

*  表长难以预估、经常要增加/删除元素——链表
 *  表长可预估、查询（搜索）操作较多——顺序表

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA55Sf5ZG95piv5pyJ5YWJ55qE_size_20_color_FFFFFF_t_70_g_se_x_16_pic_center 26]

[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA55Sf5ZG95piv5pyJ5YWJ55qE_size_20_color_FFFFFF_t_70_g_se_x_16_pic_center]: /images/20220828/4c61a8554b54452e8c054e3581411384.png
[b595381811c24583abd4f2d4406e4b6e.png_pic_center]: /images/20220828/d1d2fee18a054bf5ab6cdb9d1ec568ea.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA55Sf5ZG95piv5pyJ5YWJ55qE_size_8_color_FFFFFF_t_70_g_se_x_16_pic_center]: /images/20220828/69b14b1ac236488d9210495fb32a2b2c.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA55Sf5ZG95piv5pyJ5YWJ55qE_size_20_color_FFFFFF_t_70_g_se_x_16_pic_center 1]: /images/20220828/8230d5605be446659250ce0df880ea40.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA55Sf5ZG95piv5pyJ5YWJ55qE_size_20_color_FFFFFF_t_70_g_se_x_16_pic_center 2]: /images/20220828/08a24b73d0464e2fa2eb39c33b70588b.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA55Sf5ZG95piv5pyJ5YWJ55qE_size_9_color_FFFFFF_t_70_g_se_x_16_pic_center]: /images/20220828/86e1bbc04251452f8aa03d13fe7bdf5c.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA55Sf5ZG95piv5pyJ5YWJ55qE_size_8_color_FFFFFF_t_70_g_se_x_16_pic_center 1]: /images/20220828/041c394498614be7ae744576de736030.png
[afabed3c83144344b58e15fd59ba9971.png_pic_center]: /images/20220828/d7688eccf1fb472f89a7864a4aa14d2e.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA55Sf5ZG95piv5pyJ5YWJ55qE_size_20_color_FFFFFF_t_70_g_se_x_16_pic_center 3]: /images/20220828/c59bf370a07e4c7ab3918df293892745.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA55Sf5ZG95piv5pyJ5YWJ55qE_size_20_color_FFFFFF_t_70_g_se_x_16_pic_center 4]: /images/20220828/192bd51769634be99adbc5477a361aaf.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA55Sf5ZG95piv5pyJ5YWJ55qE_size_20_color_FFFFFF_t_70_g_se_x_16_pic_center 5]: /images/20220828/fb0bcec5fc2f42aa9668af537b3be58f.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA55Sf5ZG95piv5pyJ5YWJ55qE_size_20_color_FFFFFF_t_70_g_se_x_16_pic_center 6]: /images/20220828/b4d69eb7114f4df299aa4ac078305136.png
[109ba68f152d40e3baf37fcf200f493c.png_pic_center]: /images/20220828/705bc9078bbf4c728dac8ce02dd0ab70.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA55Sf5ZG95piv5pyJ5YWJ55qE_size_20_color_FFFFFF_t_70_g_se_x_16_pic_center 7]: /images/20220828/b699d7df810d429a99a53cfa98564da3.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA55Sf5ZG95piv5pyJ5YWJ55qE_size_20_color_FFFFFF_t_70_g_se_x_16_pic_center 8]: /images/20220828/354fc4612cd64f6da38c319671b7347c.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA55Sf5ZG95piv5pyJ5YWJ55qE_size_20_color_FFFFFF_t_70_g_se_x_16_pic_center 9]: /images/20220828/0b515ed255ba49428e347a7b81f42f86.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA55Sf5ZG95piv5pyJ5YWJ55qE_size_20_color_FFFFFF_t_70_g_se_x_16_pic_center 10]: /images/20220828/a06831d9126e405db145daa9b902f21c.png
[fb2792d54480402698c820f290cdbd22.png_pic_center]: /images/20220828/9157ce0e819841cb93af2e3eb9d9b3f9.png
[60b6bf7372334494ad65b61bb08c2e3c.png_pic_center]: /images/20220828/2eb3c3539e83499ba54a71a48b6acd28.png
[e6a63d1c78174d62adcab1254d40ac3b.png_pic_center]: /images/20220828/731545f855c541acb0a35d42f83ee265.png
[3e6dd00405fc4e8e90f5346424a9834e.png_pic_center]: /images/20220828/3950671bf2bf4a57a2682c0c19999a66.png
[26892c30ab564b3da11362e4d0f215a7.png_pic_center]: /images/20220828/e5284c03d184440291f5c62b5ce8c7c5.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA55Sf5ZG95piv5pyJ5YWJ55qE_size_20_color_FFFFFF_t_70_g_se_x_16_pic_center 11]: /images/20220828/b5f7023fafcb4acfa3d846d2bb5f69ca.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA55Sf5ZG95piv5pyJ5YWJ55qE_size_19_color_FFFFFF_t_70_g_se_x_16_pic_center]: /images/20220828/0ed6f4b05b0448eab82961143c1d20ea.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA55Sf5ZG95piv5pyJ5YWJ55qE_size_19_color_FFFFFF_t_70_g_se_x_16_pic_center 1]: /images/20220828/3556a5c2700246dc9ef106a547ee8cb9.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA55Sf5ZG95piv5pyJ5YWJ55qE_size_20_color_FFFFFF_t_70_g_se_x_16_pic_center 12]: /images/20220828/ca4725d1750940eb8387dcf89edf5b82.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA55Sf5ZG95piv5pyJ5YWJ55qE_size_20_color_FFFFFF_t_70_g_se_x_16_pic_center 13]: /images/20220828/654ad23d8e41414b97daf14edaf2b0b5.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA55Sf5ZG95piv5pyJ5YWJ55qE_size_13_color_FFFFFF_t_70_g_se_x_16_pic_center]: /images/20220828/8b112e8fa2264480910647b611ffd72d.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA55Sf5ZG95piv5pyJ5YWJ55qE_size_20_color_FFFFFF_t_70_g_se_x_16_pic_center 14]: /images/20220828/3512464394b548bf8ab60e4022477a99.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA55Sf5ZG95piv5pyJ5YWJ55qE_size_20_color_FFFFFF_t_70_g_se_x_16_pic_center 15]: /images/20220828/ea9c71ae16704780b0c2d0d3633fbc6e.png
[1bf0fe62dcc24b39a535162ec23d882f.png_pic_center]: /images/20220828/df3a874b91fe44878eee6c0629b52adb.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA55Sf5ZG95piv5pyJ5YWJ55qE_size_20_color_FFFFFF_t_70_g_se_x_16_pic_center 16]: /images/20220828/3384a70d3e6b44efa04159fe712cf6da.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA55Sf5ZG95piv5pyJ5YWJ55qE_size_20_color_FFFFFF_t_70_g_se_x_16_pic_center 17]: /images/20220828/f49d71986dfd4eee8cfa1ddca1c15a7e.png
[b20be6d0f4204019bf912f6082858b48.png_pic_center]: /images/20220828/45cda6787db24910aeeacc27889cbec7.png
[a17301cb73224cf29f24794cb17d5261.png_pic_center]: /images/20220828/b43224860ca54d50883f514cd2dd68fc.png
[69a4b7aa0dc64249bf93c82ab72209a3.png_pic_center]: /images/20220828/4dd09bed2b294847a6be892949a645d0.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA55Sf5ZG95piv5pyJ5YWJ55qE_size_18_color_FFFFFF_t_70_g_se_x_16_pic_center]: /images/20220828/8266292b5ce0466882ee0009294eb5b4.png
[1e26f7ae661d4351a68b00f601a56440.png_pic_center]: /images/20220828/a54de101c7fe4e70ad51af5479988094.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA55Sf5ZG95piv5pyJ5YWJ55qE_size_20_color_FFFFFF_t_70_g_se_x_16_pic_center 18]: /images/20220828/a950f58c1b504fcaa7a513088e549ea3.png
[c6acec76f4f14711b8a17c624cb4bd88.png_pic_center]: /images/20220828/26a63d6d82bc4fa58e565be291cf2292.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA55Sf5ZG95piv5pyJ5YWJ55qE_size_20_color_FFFFFF_t_70_g_se_x_16_pic_center 19]: /images/20220828/e085a6109af448bfa494982351691086.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA55Sf5ZG95piv5pyJ5YWJ55qE_size_20_color_FFFFFF_t_70_g_se_x_16_pic_center 20]: /images/20220828/f90d2b3d5a3a4e29b8445b9d5d2ed1f6.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA55Sf5ZG95piv5pyJ5YWJ55qE_size_20_color_FFFFFF_t_70_g_se_x_16_pic_center 21]: /images/20220828/6e6b2d56cff641beb8fdd614b34b09ef.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA55Sf5ZG95piv5pyJ5YWJ55qE_size_17_color_FFFFFF_t_70_g_se_x_16_pic_center]: /images/20220828/70a5f6c429f14b09a801261fba507760.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA55Sf5ZG95piv5pyJ5YWJ55qE_size_20_color_FFFFFF_t_70_g_se_x_16_pic_center 22]: /images/20220828/317b36113d7142d28079e730603aa03f.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA55Sf5ZG95piv5pyJ5YWJ55qE_size_20_color_FFFFFF_t_70_g_se_x_16_pic_center 23]: /images/20220828/55818795209a43e9b0dd2ec20a998f09.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA55Sf5ZG95piv5pyJ5YWJ55qE_size_20_color_FFFFFF_t_70_g_se_x_16_pic_center 24]: /images/20220828/fb2868438a544fb58a17bf4797bd7315.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA55Sf5ZG95piv5pyJ5YWJ55qE_size_20_color_FFFFFF_t_70_g_se_x_16_pic_center 25]: /images/20220828/4e372c94dc36446e833dd40de6f5399a.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA55Sf5ZG95piv5pyJ5YWJ55qE_size_20_color_FFFFFF_t_70_g_se_x_16_pic_center 26]: /images/20220828/e24c920162f843ae8bae76fb531c7d91.png