数据结构与算法——线性表的链式储存结构_数据结构链表插入算法p和s怎么理解-程序员宅基地

技术标签: 链表  数据结构与算法  数据结构  

目录

前言

一、链式储存结构的定义

二、单链表的读取操作

三、单链表的插入与删除

3.1   单链表的插入

 3.2   单链表的删除

总结


 

前言

上一篇我们讲的线性表的顺序储存结构,实际上它是有缺陷的。其中最大的缺陷就在于插入和删除的时候需要移动大量元素,这显然就需要耗费大量的时间。所以,我们需要考虑用什么办法来解决这个问题。

要解决这个问题,在这里我们就要引入线性表的链式储存结构的概念。简单来说,就是不需要将所有的数据元素按照顺序连续的进行排列,只需要将数据元素安排的到有空位的地方,然后让每个元素知道下一个元素的位置。这样一来,我们就能通过遍历来找到所有元素的位置。

下面我们就来系统的认识一下什么是线性表的数据储存结构吧。


一、链式储存结构的定义

在阐述定义前,我们得先了解几个概念:

  • 我们把存储数据元素信息的域称为数据域
  • 把存储直接后继位置的域称为指针域
  • 这两部分信息组成数据元素的存储映像,称为结点

链式储存结构:n个结点链组成一个链表,即为线性表的链式存储结构。因为此链表的每个结点中只包含一个指针域,所以叫做单链表。我们把链表中第一个结点的存储位置叫做头指针。在单链表中第一个结点前附设一个结点,称为头结点。(头结点的数据域可以不储存任何信息)

下面我们就来看看,线性表的单链表储存结构的代码描述:

typedef struct node{
	
	int data;       //用于储存数据,这里暂定为int类型的数据 
	
	struct node *next;      //这里用于储存下一个元素的位置 

}node,*linklist;      //定义linklist 

 这里稍作解释,假设说 p 是第 i 个元素的指针,那么该元素的数据域我们可以用p.data来表示,指针域就可以用 p.next 来表示,表示指向下一个结点的指针。

二、单链表的读取操作

在顺序储存结构中,要获取一个元素的位置是比较容易的。但对于链式储存结构,由于我们没办法在一开始就知道第 i 个元素在什么位置,所以我们必须从头开始遍历整个单链表。因此,在算法上要相对麻烦些。算法思路为:

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

 实现代码算法如下:

int get(linklist a,int i,int *e)
{
	int j=1;        //j为计数器 
	p=a.next;       //让p指向链表a的第一个结点 
	while(p&&j<i)    //当p不为空并且j<i时,循环继续 
	{
		p=p.next;    //让p指向下一个结点 
		j++;
	}
	if(!p||j>i)    //第i个元素不存在的时候,返回wrong 
	{
		return wrong;
	}
	*e=p.data;      //取得第i个元素的数据 
	
	return right;
}

说白了,就是从头开始找。其算法的时间复杂度取决于 i 的位置,如果 i 的位置在第一个,则不需要遍历;如果是最坏的情况,当i=n时,需要遍历n-1次才能找到,时间复杂度为O(n)。其工作的核心思想就是“工作指针后移”,这也是很多算法常用的技术。

三、单链表的插入与删除

3.1   单链表的插入

简单来说,就是要将一个新的结点 s 插入到结点 p 与 p.next 之间即可。代码实现结果如下:


s.next=p.next;   //让p的后继结点赋值给s的后继 
p.next=s;        //将s赋值给p的后继 

这两句的顺序切记不能交换。具体原因留给读者自行思考。

下面给出第 i 个数据插入结点的算法思路:

  1. 利用上面的查找算法,将第 i 个元素的位置找出来;
  2. 若查找成功,在系统中建立一个新的结点;
  3. 将数据元素e赋值给 s.data;
  4. 单链表的插入标准语句 s.next=p.next , p.next=s;
  5. 返回正确。

实现代码算法如下:

int listinsert(linklist *a,int i,int e)
{
	int j=1;
	linklist p,s;
	p=*a;
	while(p&&j<i)       //寻找第i个结点的位置 
	{
		p=p.next
		j++
	}
	if(!p||j>i)
	{
		return wrong;
	}
	s=(linklist)malloc(sizeof(node));   //生成一个新的结点 
	s.data=e;           //将数据e赋值给s 
	s.next=p.next;      //将s进行插入操作 
	p.next=s;
	
	return ok;
	
}

 3.2   单链表的删除

对于单链表的删除操作,就更加简单啦。只需要将结点p的前继节点的指针绕过,直接指向p的后继结点即可,最后再把结点p释放掉。

算法思路如下:

  1. 利用上述的查找算法找出第 i 个元素的位置;
  2. 若查找成功,将欲删除的结点p.next赋值给q;
  3. 单链表的删除标准语句 p.next=q,next;
  4. 将q结点中的数据赋值给e,作为返回;
  5. 释放q结点;
  6. 返回正确。

实现代码算法如下:

int listinsert(linklist *a,int i,int *e)
{
	int j=1;
	linklist p,q;
    p=*a;
    while(p.next&&j<i)        //查找第i个元素 
    {
    	p=p.next;
    	j++;
	}
	if(!(p.next)||j>i)
	{
		return wrong;
	}
	q=p.next;         //标准删除语句 
	p.next=q.next;
	*e=q.data;         //将q的数据由e返回 
	free(q);           //释放q结点 
	
	return right
	
}

总结

相比于顺序储存结构,单链表储存结构在查找数据元素方面要逊于前者。但对于数据元素的插入和删除操作,就会有一定的优势,我们可以来简单分析一下。

单链表的插入和删除操作其实都是有两部分组成:一是遍历查找第 i 个结点;二是插入和删除结点。显然,其时间复杂度为O(n),假设说对于不知道第i个结点的位置,在单链表上进行插入和删除操作,与顺序储存结构没有太大的优势。但是,如果我们希望从第 i 个位置插入10个结点,对于顺序存储结构每一次都需要移动n-i个结点,每次的时间复杂度都是O(n)。对于单链表,当找到了第i个元素的位置,时间复杂度为O(n),但之后无论插入或删除多少个结点,其时间复杂度永远是O(1)。

显然,对于插入或删除数据越频繁的操作,单链表的优势就越明显。

版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/xzt12138/article/details/125944404

智能推荐

字符串大小写互换(函数)_把字符串下标从小到大交换成从大到小-程序员宅基地

文章浏览阅读837次。#include#includechar a(char b){ int i; if(b>='a'&&b { b-=32; } else if(b>='A'&&b { b+=32; } return b;}int main(){ int l,n_把字符串下标从小到大交换成从大到小

数据结构与算法-8数组的分割_多组数据,每组数据两行。第一行为一个整数n,代表数组中有n个元素。第二行为数组中-程序员宅基地

文章浏览阅读4.9k次,点赞15次,收藏42次。Description已知由n(n≥2)个正整数构成的集合A={ak}(0≤k<n),将其划分为两个不相交的子集A1和A2,元素个数分别是n1和n2,A1和A2中元素之和分别为S1和S2。设计一个尽可能高效的划分算法,满足|n1-n2|最小且|S1-S2|最大。Input多组数据,每组数据两行。第一行为一个整数n,代表数组中有n个元素。第二行为数组中的n个元素(元素之间用空格分隔)。当..._多组数据,每组数据两行。第一行为一个整数n,代表数组中有n个元素。第二行为数组中

You have an error in your SQL syntax; check the manual that corresponds to your MySQL server version_you have an error in your sql syntax; check the ma-程序员宅基地

文章浏览阅读734次。这种错,除了sql语法错误,还有可能是用了mysql关键字导致的,比如这次就是表名用了mysql关键字order,改下表名即可。_you have an error in your sql syntax; check the manual that corresponds to your mysql server version for the right syntax to use near 'the manual that corresponds to your mysql server version for the right syntax to' at line 1

android paint style,android绘图之Paint(1)-程序员宅基地

文章浏览阅读226次。Android 绘图学习Paint 讲解开篇android Paint,Canvasandroid中绘制特定图案类似显示中的绘画需要画笔和画纸,为此android提供了Paint和Canvas。Paint和Canvas分别代表画笔和画布。The Paint class holds the style and color information about how to draw geometrie..._android cap round butt square

USB产品(FX3、CCG3PA)的调试方法_ez-usb cx3-程序员宅基地

文章浏览阅读1.1k次。英飞凌的USB产品线,主要来自过去Cypress的FX3和CCG3PA产品,在此基础上进行了扩展和产品系列的细分,比如以FX3为基础又分出了CX3、HX3、SD3等,这个系列主要是实现接口,比如USB2.0、USB3.2Gen1、USB3.2Gen2等,同样的CCG3之后又有了CCG4、CCG5、CCG6、CCG7以及PMG1等,有些是整合DC-DC有些则是新增主控MCU功能,主要实现的是PD3.0、PD3.1的充电接口,这也是目前的热点,就是C口+PD充电。..._ez-usb cx3

R语言之多重共线性的判别以及解决方法_r语言共线性分析-程序员宅基地

文章浏览阅读3.6w次,点赞17次,收藏106次。多重共线性(Multicollinearity)是指线性回归模型中的解释变量之间由于存在精确相关关系或高度相关关系而使模型估计失真或难以估计准确。 1.可以计算X矩阵的秩qr(X)$rank,如果不是满秩的,说明其中有Xi可以用其他的X的线性组合表示;(完全的线性表示,此方法不能作为判别是否有共线性的标准,因为有可能存在共线性但不是完全线性相关)2.也可以计算条件数kapp_r语言共线性分析

随便推点

ASP.NET—002:GridView手动增加一行_asp.net的gridview增加一行-程序员宅基地

文章浏览阅读1.5w次,点赞3次,收藏7次。ASP.NET中的gridview如何增加一行呢,下面介绍一种最简单的方式。只使用后台的数据,在后台的datatable或者list增加一项,然后重新绑定gridview。直接看代码效果:实体类public class PersonModel { private int personIndex; public int PersonIndex_asp.net的gridview增加一行

unity3d接入有米广告SDK----android_ubity 接有米广告-程序员宅基地

文章浏览阅读8.1k次。个人开发者发布开发应用想接入广告SDK,个人jie'c_ubity 接有米广告

python hasattr函数_Python3 hasattr()、getattr()、setattr()函数简介-程序员宅基地

文章浏览阅读509次。Python3 hasattr()、getattr()、setattr()函数简介一、hasattr(object, name)判断object对象中是否存在name属性,当然对于python的对象而言,属性包含变量和方法;有则返回True,没有则返回False;需要注意的是name参数是string类型,所以不管是要判断变量还是方法,其名称都以字符串形式传参;getattr和setattr也同样..._python3 hasattr

阶乘求和(高精)_阶乘分母的级数求和-程序员宅基地

文章浏览阅读1.8k次。用高精度计算出S=1!+2!+3!+…+n!(n ≤ 50)其中“!”表示阶乘,例如:5!=54321。输入描述:输入正整数N输出描述:输出计算结果S示例1输入3输出9思路:高精度的加法和乘法,还是利用n!=n*(n-1)!,然后就是高精加和高精乘的模板#include<bits/stdc++.h>using namespace std;#define ios ios::sync_with_stdio(0)typedef long long ll;const int_阶乘分母的级数求和

「建议收藏」我想进阿里,我该怎么做?_想进阿里巴巴当软件工程师该怎么做-程序员宅基地

文章浏览阅读464次。阿里巴巴,作为一家知名的互联网公司,是我们程序员心仪公司之一,想得到一份阿里的offer,得通过层层关卡在这里我想分享一些我的经验,送给那些跟我一样,没大厂背景,但是想进阿里(或其他大厂,比如我面过的字节跳过),又有点迷茫不知该如何前进的人。之前没有去过,我一直很迷茫,内心有一些谜团一直困扰着我,比如阿里招人标准是什么?,自己距离这个标准有多少差距?那时候一直不知道,就好像置身于沙漠之中,却..._想进阿里巴巴当软件工程师该怎么做

推荐文章

热门文章

相关标签