[数据结构与算法] 链表的定义及增删查算法的实现

开发: C++知识库 Java知识库 JavaScript Python PHP知识库人工智能区块链大数据移动开发嵌入式开发工具数据结构与算法开发测试游戏开发网络协议系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑笔记本显卡显示器固态硬盘硬盘耳机手机 iphone vivo oppo 小米华为单反装机图拉丁

-> 数据结构与算法 -> 链表的定义及增删查算法的实现 -> 正文阅读

[数据结构与算法]链表的定义及增删查算法的实现

文章目录

1 存在的意义

? 线性表的顺序存储结构最大的缺点就是插入和删除时需要移动大量元素，这显然是需要耗费大量的时间，链式存储结构就是为了解决这个问题而存在。

为什么当插入和删除时，就要移动大量元素。仔细分析后，发现原因就在于响铃元素的存储位置具有邻居关系。它们编号是1，2，3，·····，n，它们在内容中的位置也是挨着的，中间没有空隙，当然就无法快速插入，而删除后，当中就会留出空隙，问题就出在这里。

2 链表的定义

2.1 文字定义

?在顺序结构中，每个数据元素只需要存储数据元素信息就可以了。现在链式结构中，除了要存储数据元素外，还要存储它的后继元素的存储地址。

在这里插入图片描述

?为了表示每个数据元素 $a_i$ 与其直接后继数据元素 $a_{i+1}$ 之间的逻辑关系，对数据元素 $a_i$ 来说，除了存储其本身的信息之外，还需存储一个指示其直接后继的信息（即直接后继的存储位置）。把存储数据元素信息的域称为数据域，把存储直接后继位置的域称为指针域，指针域中存储的信息称作指针或链。这两部分信息组成数据元素 $a_i$ 的存储映像称为结点。

?线性表的链式存储结构： $n$ 个结点( $a_j$ 的存储映像)链结成一个链表，因为此链表的每个结点中只包含一个指针域，所以叫做单链表。单链表正是通过每个结点的指针域将线性表的数据元素按其逻辑次序链接在一起。

在这里插入图片描述

头指针：链表中第一个结点的存储位置。

尾指针：线性链表的最后一个结点指针为“空”（通常用NULL或“^”符号表示）

头结点：在单链表的第一个结点前附设一个结点，称为头结点。（头结点的数据域可以不存储任何信息，也可以存储如线性表长度等附加信息，头结点的指针指向第一个结点的指针。）

头指针与头结点的异同：

头指针
头指针是指链表指向第一个结点的指针，若链表有头结点，则是指向头结点的指针。
头指针具有标志作用，所以常用头指针冠以链表的名字。
无论链表是否为空，头指针均不为空。头指针是链表的必要元素。

头结点
头结点是为了操作的统一和方便而设立的，放在第一元素的结点之前，其数据域一般无意义（也可存放链表的长度）。
有了头结点对在第一元素结点前插入结点和删除第一结点，其操作与其他结点的操作就统一了。
头结点不一定是链表必需要素。

2.2 代码定义

?用存储示意图表示单链表如图所示：

在这里插入图片描述

?C语言描述：

typedef struct Node{
    ElemType data;
    struct Node *next;
}Node;
typedef struct Node *LinkList; // 定义LinkList

结点由存放数据元素的数据域和存放后继结点地址的指针域组成。

3 单链表的读取、插入与删除

3.1 单链表的读取

获取链表第i个数据的算法思路：

声明一个指针p指向链表第一个结点，初始化j从1开始。
当j<i时，就遍历链表，让p的指针向后移动，不断指向下一结点，j累加1。
若到链表末尾p为空，则说明第i个结点不存在。
否则查找成功，返回结点p的数据。

实现代码如下：

/* 初始条件：链式线性表L已存在，1≤i≤ListLength(L) */
/* 操作结果：用e返回L中第i个数据元素的值 */
Status GetElem(LinkList L,int i,ElemType *e){
    int j;
    LinkList p; /* 声明一结点p */
    p = L->next; /* 让p指向链表L的第一个结点 */
    j = 1; /*  j为计数器 */
    while (p && j<i){ /* p不为空或者计数器j还没有等于i时，循环继续 */
        p = p-> next; /* 让p指向下一个结点 */
        ++j;
    }
    if (!p || j>i){ /*  第i个元素不存在 */
        return ERROR;
    }
    *e = p->data; /*  取第i个元素的数据 */
    return OK;
}

3.2 插入算法

设存储元素e的结点为s,要实现结点p、p-＞next和s之间逻辑关系的变化，只需将结点s插入到结点p和p-＞next之间即可。

在这里插入图片描述

根本用不着惊动其他结点，只需要让s-＞next和p-＞next的指针做一点改变即可。

s->next = p->next; // 将p的后继结点复制给s的后继
p->next = s; // 将s复制给p的后继

也就是说让p的后继结点改成S的后继结点，再把结点S变成p的后继结点。

单链表第i个数据插入结点的算法思路：

声明一指针p指向链表头结点，初始化j从1开始；
当j<i时，就遍历链表，让p的指针向后移动，不断指向下一结点，j累加1；
若到链表末尾p为空，则说明第i个结点不存在；
否则查找成功，在系统中生成一个空节点s；
将数据元素e复制给s->data；
单链表的插入标准语句 s->next = p->next; p->next=s;
返回成功。

C实现代码算法如下：

/* 初始条件：链式线性表L已存在,1≤i≤ListLength(L)， */
/* 操作结果：在L中第i个位置之前插入新的数据元素e，L的长度加1 */
Status ListInsert(LinkList *L,int i,ElemType e){
    int j;
    LinkList p,s;
    p = *L;
    j = 1;
    while(p && j<i){  /* 寻找第i个结点 */
        p = p->next;
        ++j;
    }
    if(!p || j>i){  /* 第i个元素不存在 */
        return ERROR;
    }
    
    S = (LinkList)malloc(sizeof(Node));   /*  生成新结点(C语言标准函数) */
    s->data = e;
    s->next = p->next;  /* 将p的后继结点赋值给s的后继  */
    p->next = s;  /* 将s赋值给p的后继 */
    return OK;
}

malloc函数的作用就是生成一个新的结点，其类型与Node是一样的，其实质就是再内存中找了一小块空地，准备用来存放数据e的s结点。

3.3 单链表的删除

设存储元素 $a_{i}$ 的结点为q，要实现将结点q删除单链表的操作，其实就是将它的前继结点的指针绕过，指向它的后继结点即可。

在这里插入图片描述

我们所要做的，实际上就是—步，p-＞next＝p-＞next-＞next，用q来取代p-＞next，即是

q = p->next;
p->next = q->next; //将q的后继复制给p的后继

单链表第j个数据删除结点的算法思路：

声明—指针p指向链表头结点，初始化j从1开始;
当j＜i时，就遍历链表，让p的指针向后移动，不断指向下一个结点，j累加1;
若到链表末尾p为空，则说明第i个结点不存在；
否则查找成功，将预删除的结点p->next赋值给q；
单链表的删除标准语句p->next=q->next;
将q结点中的数据赋值给e，作为返回；
释放q结点；
返回成功。

/* 初始条件：链式线性表L已存在，1≤i≤ListLength(L) */
/* 操作结果：删除L的第i个数据元素，并用e返回其值，L的长度减1 */
Status ListDelete(LinkList *L,int i,ElemType *e){
    int j;
    LinkList p,q;
    p = *L;
    j = 1;
    while(p->next && j<i){  /* 遍历寻找第i个元素 */
        p = p-> next;
        ++j;
    }
    if(!(p->next) || j>i){  /* 第i个元素不存在 */
        return ERROR;
    }
    q = p->next;
    p->next = q->next;  /* 将q的后继赋值给p的后继 */
    *e = q->data;  /* 将q结点中的数据给e */
    free(q);  /* 让系统回收此结点，释放内存 */
    return OK;
}

free函数的作用是让系统回收一个Node结点，释放内容。

4 单链表的整表创建与删除

4.1 单链表的整表创建

创建单链表的过程就是—个动态生成链表的过程。即从“空表”的初始状态起，依次建立各元素结点，并逐个插入链表。

单链表整表创建的算法思路：

声明一指针p和计数器变量i；
初始化一空链表L；
让L的头结点的指针指向NULL，即建立一个带头结点的单链表；
循环：
1. 生成一新结点赋值给p；
2. 随机生成一数字赋值给p的数据域p->data;
3. 将p插入到头结点与前一新结点之间。

头插法：始终让新结点在第一的位置。

在这里插入图片描述

/*  随机产生n个元素的值，建立带表头结点的单链线性表L（头插法） */
void CreateListHead(LinkList *L,int n){
    LinkList p;
    int i;
    srand(time(0));  /* 初始化随机数种子 */
    *L = (LinkList)malloc(sizeof(Node));
    (*L)->next = NULL;  /*  先建立一个带头结点的单链表 */
    for(int i=0; i<n; i++){
        p = (LinkList)malloc(sizeof(Node));  /*  生成新结点 */
        p->data = rand()%100 + 1;   /*  随机生成100以内的数字 */
        p->next = (*L) -> next;
        (*L)->next = p;  /*  插入到表头 */
    }
}

尾插法：每次新结点都插在终端结点的后面。

/*  随机产生n个元素的值，建立带表头结点的单链线性表L（尾插法） */
void CreateListTail(LinkList *L, int n) 
{
	LinkList p,r;
	int i;
	srand(time(0));                      /* 初始化随机数种子 */
	*L = (LinkList)malloc(sizeof(Node)); /* L为整个线性表 */
	r=*L;                                /* r为指向尾部的结点 */
	for (i=0; i<n; i++) 
	{
		p = (Node *)malloc(sizeof(Node)); /*  生成新结点 */
		p->data = rand()%100+1;           /*  随机生成100以内的数字 */
		r->next=p;                        /* 将表尾终端结点的指针指向新结点 */
		r = p;                            /* 将当前的新结点定义为表尾终端结点 */
	}
	r->next = NULL;                       /* 表示当前链表结束 */
}

L与r的关系，L是指整个单链表，而r是指向尾结点的变量，r会随着循环不4断地变化结点，而L则是随着循环增长为—个多结点的链表。

4.2 单链表的整表删除

当我们不打算使用这个单链表时我们需要把它销毁，其实也就是在内存中将它释放掉，以便于留出空间给其他程序或软件使用。

单链表整表删除的算法思路如下:

声明一指针p和q；
将第一个结点赋值给p；
循环：
1. 将下一结点复制给q；
2. 释放p；
3. 将q复制给p。

/* 初始条件：链式线性表L已存在。操作结果：将L重置为空表 */
Status ClearList(LinkList *L){
    LinkList p,q;
    p = (*L)->next;   /*  p指向第一个结点 */
    while(p){  /*  没到表尾 */
        q = p->next;
        free(p);
        p=q;
    }
    (*L)->next = NULL;  /* 头结点指针域为空 */
    return OK;
}