单链表上基本操作的实现

2024-07-13 14:27| 来源: 网络整理| 查看: 265

单链表的基本操作单链表的建立头插法建立单链表基本思路代码实现尾插法建立单链表方法原理：代码实现尾插法建立单链表最优代码如下：单链表的插入与删除单链表的插入按位序的插入操作带头结点的按位序插入操作代码实现不带头节点的按位序插入操作代码实现按指定结点的插入操作在指定结点之后插入（后插）代码实现后插操作与按位序插入操作的联系在指定结点之前插入（前插）代码实现单链表的删除按位序的删除操作带头节点的单链表的删除操作代码实现不带头节点的单链表的删除操作代码实现按指定结点的删除操作代码实现单链表的查找按位查找代码实现代码封装按值查找求单链表的表的长度代码实现总结提示，可以根据目录，可以从单链表的插入删除——单链表的查找——单链表的建立这样的顺序进行学习！！！

单链表的建立

单链表的建立主要包括两种建立方法：头插法与尾插法。基本步骤如下：

初始化一个单链表每次取一个数据元素，*插入到表尾/表头 *（导致于头插法，尾插法）头插法建立单链表

（带头结点的的单链表）该方法从一个空表开始，生成新结点，并将读取到的数据存放在新结点的数据域中，然后将新结点插入到当前链表的表头，即头结点之后。本质————是对头结点的后插操作

基本思路初始化一个单链表利用while循环{每次取一个数据元素e；调用一次后插法——InsertNextNode(L,e)} 代码实现 typedf struct LNode{ //定义单链表结构类型 ElemType data; //每个节点存放一个数据元素 struct LNode *next; //指针指向下一个节点 }LNode,*LinkList; //函数功能——头插法建立单链表 LinkList List_HeadInsert(LinkList &L){ //逆向建立单链表 LNode *s; int x; L = (LinkList)malloc(sizeof(LNode)) //创建头结点 L->next=NUll; //保证头指针是不会指向脏数据的，初始化为空链表 scanf("%d",&x); //输入结点的值 while(x!=99999){//只有当输入x为99999时，循环无法进行，否则可以进行————即输入99999代表着结束 s=（LNode*)malloc(sizeof(LNode)); //申请新结点 s->data=x; //新结点的数据域被x覆盖 s-next=L->next; //将新结点链接在头指针的后继结点 L->next=s; //新结点插入表中，L为头指针 scanf("d",&x); } return L; }

效果：在这里插入图片描述

问题：若没有头结点，该如何理解头插法的修改？答：没有了头指针，每次插入新结点后，需要将其指针指向单链表指针L 提示：链表的逆置可以考虑头插法的方法！

尾插法建立单链表

（带头结点的单链表）法一：

初始化一个单链表；利用按位序插入算法；设置变量length来记录链表长度每次都要循环，每取一个元素，按位序插入算法用一次，length++，时间复杂度为O( n 2 n^{2} n2）。

法二：利用后插操作，设置一个表尾指针，每次更新，使得这个指针指向单链表的最后一个结点。

方法原理：

将新结点插入到当前链表的表尾，为此必须增加一个指针，使其始终指向当前链表的尾结点。

代码实现 typedf 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 = MULL; //头节点之后暂时还没有节点 return true； } //函数：按位序插入，在第i个位置插入元素 e bool ListInsert(LinkList &L,int i,ElemType e){ if(i if(p==NULL) //结点p不合法 return false; LNode *s=(LNode*),malloc(sizeof(LNode));//申请新结点 if(s==NULL)// 内存分配失败。某些情况有可能分配不足，也可以不考虑这一点 return false; s->data=e; //在新结点中存入数据元素e s->next =p->next; //结点p的下一个结点由新结点s来链接； p->next=s; //将结点s链接到p之后； return ture; //插入成功！ } void test (){ LinkList L; //声明一个指向单链表的指针 //注意到此处并没有创建一个节点 //初始化一个空表 InitList(L); //....后续代码。。。。 }

思路效果：在这里插入图片描述

尾插法建立单链表最优代码如下： typedf struct LNode{ //定义单链表结构类型 ElemType data; //每个节点存放一个数据元素 struct LNode *next; //指针指向下一个节点 }LNode,*LinkList; //函数功能——尾插法建立单链表 LinkList List_Tailinsert(LinkList &L){//正向建立单链表 int x; //假设建立链表插入的类型ElemType为整型； L=(LinkList)malloc(sizeof(LNode)); //建立头结点 ——本质初始化空表 LNode *s,*r=L; //设置两个指针，最开始二者都为头指针，r本质是表尾指针； scanf("%d",&x) ; //要插入结点的数据域的值 while(x!=99999){//只有当输入x为99999时，循环无法进行，否则可以进行————即输入99999代表着结束 s=（LNode*)malloc(sizeof(LNode)); //申请新结点 s->data=x; //新结点的数据域被x覆盖 r-next=s; //将新结点链接在上一个表尾结点之后————本质是尾插法，在r结点之后插入元素x； r=s; //r指向新的表尾结点————永远保证r指向最后一个结点。 scanf("d",&x); } r-next->NULL; //尾结点指针置空 return L; } //该算法的时间复杂度为O(n). 单链表的插入与删除单链表的插入

单链表的插入分为按位序插入和按指定结点插入两大类。

按位序的插入操作

按位序插入操作也分为带头结点的单链表插入和不带头结点的单链表插入

带头结点的按位序插入操作

ListInsert(&L,i,e):插入操作。在表L中的第i个位置上插入指定元素e。分析：要在第i个位置上插入指定元素，那就应该要找到第i-1个结点，并将新结点插入其后。未进行插入前的但链表结构在这里插入图片描述我们假设：i=2 主要步骤过程：

要找到第i-1个结点；(若i=2,就需要找到i=1的第一个结点)然后需要用malloc函数申请一个新的结点s;将数据元素e存入到这个结点;假设第i-1的结点为*p;新结点s的指针域指向p的后继结点；令p的指针域指向新插入结点s; (5与6的顺序不能颠倒)按位序插入成功；在这里插入图片描述

进行思考:若在i=1的位置进行插入，即在头结点之后进行插入怎么办？答：考虑到因为是带头结点的单链表的插入，我们可以考虑把头节点看作第0个结点。代码实现 typedf struct LNode{ //定义单链表结构类型 ElemType data; //每个节点存放一个数据元素 struct LNode *next; //指针指向下一个节点 }LNode,*LinkList; //函数功能：在第i个位置插入元素e（带头结点） bool ListInsert(LinkList &L,int i,ElemType e){ if(i //定义单链表结构类型 ElemType data; //每个节点存放一个数据元素 struct LNode *next; //指针指向下一个节点 }LNode,*LinkList; //函数功能：在第i个位置插入元素e（带头结点） bool ListInsert(LinkList &L,int i,ElemType e){ if(i // 通过循环找到第i-1个结点，这也是本算法的主要的时间开销：为O(n) p=p->next; j++; } if(p==NULL) //i值不合法，超出链表长度，说明第i-1个结点不存在 return false; LNode *s=(LNode*),malloc(sizeof(LNode));//申请新结点 s->data=e; //在新结点中存入数据元素e s->next =p->next; //将新结点的指针域发挥与*p的指针 p->next=s; //将结点连接到p之后，我们假设的是第i-1个结点为*p； return ture; //插入成功！ } //函数功能：在第i个位置插入元素e（带头结点） bool ListInsert(LinkList &L,int i,ElemType e){ if(i //定义单链表结构类型 ElemType data; //每个节点存放一个数据元素 struct LNode *next; //指针指向下一个节点 }LNode,*LinkList; //函数功能:后插操作，在p结点之后插入元素e. bool InsertNextNode(LNode *p,ElemType e){ if(p==NULL) //结点p不合法 return false; LNode *s=(LNode*),malloc(sizeof(LNode));//申请新结点 if(s==NULL)// 内存分配失败。某些情况有可能分配不足，也可以不考虑这一点 return false; s->data=e; //在新结点中存入数据元素e s->next =p->next; //结点p的下一个结点由新结点s来链接； p->next=s; //将结点s链接到p之后； return ture; //插入成功！ }

实现效果如下：在这里插入图片描述

后插操作与按位序插入操作的联系

不难发现：

后插操作的代码的时间复杂度为O(1)按位序插入操作的代码的平均时间复杂度为O(n) 那是因为相比于按位序插入操作而言，后插操作省去了循环查找i-1结点的情况，一旦按位序插入操作实现目的结点的查找之后，后面的操作二者及其相似。

代码：

typedf struct LNode{ //定义单链表结构类型 ElemType data; //每个节点存放一个数据元素 struct LNode *next; //指针指向下一个节点 }LNode,*LinkList; //函数功能:后插操作，在p结点之后插入元素e. bool InsertNextNode(LNode *p,ElemType e){ if(p==NULL) //结点p不合法 return false; LNode *s=(LNode*),malloc(sizeof(LNode));//申请新结点 if(s==NULL)// 内存分配失败。某些情况有可能分配不足，也可以不考虑这一点 return false; s->data=e; //在新结点中存入数据元素e s->next =p->next; //结点p的下一个结点由新结点s来链接； p->next=s; //将结点s链接到p之后； return ture; //插入成功！ } //函数功能：在第i个位置插入元素e（带头结点） bool ListInsert(LinkList &L,int i,ElemType e){ if(i //定义单链表结构类型 ElemType data; //每个节点存放一个数据元素 struct LNode *next; //指针指向下一个节点 }LNode,*LinkList; //函数功能:前插操作，在p结点之前插入元素e. bool InsertPriorNode(LNode *p,ElemType e){ if(p==NULL) //结点p不合法 return false; LNode *s=(LNode*),malloc(sizeof(LNode));//申请新结点 if(s==NULL)// 内存分配失败。某些情况有可能分配不足，也可以不考虑这一点 return false; s->next=p->next; ; p->next=s; //将新结点连接到p之后 s->data=p->data; //将p中元素复制到s中 p->data=e; //将p中元素被覆盖为e return ture; //插入成功！ } /*倘若交换的数据不是一个简单的元素e呢*/ //我们用 temp变量来作为中间的数据桥梁 s->next=p->next; ; p->next=s; //将新结点连接到p之后 temp=p->data; //交换数据域部分 p->data=s->data; s->data=temp; 单链表的删除

单链表的删除操作与插入操作类似，也分为：按位序删除和指定结点的删除。

按位序的删除操作

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

带头节点的单链表的删除操作

找到第i-1个结点，将其指针指向第i+1个结点，并释放第i个结点基本步骤：

检查删除位置的合法性；查找表中的第i-1个结点——被删结点的前驱结点(最浪费时间)修改指针域和返回被删数据域的元素删除成功! 最坏、最好时间复杂度：O(n) 最好时间复杂度：O(1)——不用循环查找结点，被删结点是第一个结点。代码实现 typedf struct LNode{ //定义单链表结构类型 ElemType data; //每个节点存放一个数据元素 struct LNode *next; //指针指向下一个节点 }LNode,*LinkList; //函数功能：在第i个位置插入元素e（带头结点） //头节点被看作第0个结点 bool ListDelete(LinkList &L,int i,ElemType &e){ if(i //定义单链表结构类型 ElemType data; //每个节点存放一个数据元素 struct LNode *next; //指针指向下一个节点 }LNode,*LinkList; //函数功能：在第i个位置删除结点，并用e返回被删结点的数据 bool ListDelete(LinkList &L,int i,ElemType &e){ if(i // 通过循环找到第i-1个结点，这也是本算法的主要的时间开销：为O(n) p=p->next; j++; } if(p==NULL) //i值不合法，超出链表长度，说明第i-1个结点不存在 return false; /*比插入操作多一个判断*/ if(p->next==NULL) //说明第i-1个结点之后已无其他结点，不存在删除的必要 return false; LNode *q=p->next; //找到被删结点q e=q->data //得到被删结点q的数据域,用e返回元素的值 p->next=q->next; //将第i-1个结点指针指向第i+1个结点，*q从链中断开 free(q); //释放结点q的存储空间; return temp; //按位序删除成功！ } 按指定结点的删除操作

删除指定结点*p，一般有两个方法：方法一：我们要删除指定结点，就行按位序删除操作一样，要先找到自己的前驱结点。

从链表的头指针开始，顺序找到被删结点*p的前驱指针；执行删除操作；时间复杂度：O(n)

方法二：删除结点p的操作也可用删除p的后继结操作实现

将被删结点的后继结点的数据域赋予自身；删除自己的后继结点；（让后继节点替自己死亡的过程）时间复杂度：O(1) 由于方法二的时间复杂度低，我们一般采用方法二。效果过程：在这里插入图片描述

代码实现 //函数功能：删除指定结点p //被删结点p不是最后一个结点 bool DeleteNode(LNode *p){ if(p==NULL) return false; LNode *q=p->next;//令q指向*p的后继结点 p->data=q->data; //得到后继节点的数据域 p-next=q->next; // 将后继节点*q从链中断开 free(q); // 释放后继节点q的存储空间 return true; } 时间复杂度：O(1)

图片！！！

然而，如果被删结点p的后继结点为NULL（被删结点是尾结点），成为了没有替身的情况，上述代码的*q也是一个空指针！那么就不能使用方法二，只能使用方法一，从表头开始依次寻找p的前驱，时间复杂度就为O(n)。从中也能体现单链表的局限性，无法逆向检索。

单链表的查找

我们默认讨论——带头单链表的查找单链表的查找方法有两种：按序号查找结点值(也称按位查找)，按值查找表结点（也称按值查找）

按位查找

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

平均时间复杂度：O(n)

代码实现 //函数功能：返回第i个元素（带头结点） LNode *GetElem(LinkList L,int i){ if(i LNode *p=L->next;//从链表的第一个结点 while(p!MULL&&p->data!=e){ p=p->next; } return p;//找到后，返回该结点指针，否则返回NULL }

平均时间复杂度：O(n) 应该注意到，倘若数据元素e的数据类型不是简单的int，或者char类型，不能像上述代码那样进行比较。比如struct类型的数据元素，只有定义相同的结构体才能进行比较，不同定义的结构体之间比较无意义。

求单链表的表的长度

我们要知道单链表的长度是不包括头结点的！求表长操作就是计算单链表中数据结点（不含头结点）的个数。基本步骤：

需要从第一个结点开始顺序依次访问表中的每个结点；为此需要设置一个计数器变量，每访问一个结点，计数器加1；知道访问到空结点为止；算法时间复杂度O(n) 代码实现 int Length(LinkList L){ int len =0;//初始访问结点数为0 LNode *p=L; while(p->next !=NULL){ p=p->next; len++; } return len; } 总结单链表是学习链表的基础，应该要熟练掌握。这些整理大多借鉴于数据结构严蔚敏版本以及王道考研网课的学习。第一次发布这么多字的博客，我自己对单链表的理解和掌握也精进了许多，希望大家加油呀！如有错误多多指正！希望下次能有更好的博客发布！

【本文地址】

公司简介

联系我们