普歌-毅雁-线型表

2024-02-02 09:50
文章标签 线型 普歌 毅雁

本文主要是介绍普歌-毅雁-线型表,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

线型表

  • 前言
  • 一、线型表是什么?
  • 二、常用概念
      • 结点
      • 前驱
      • 后继
      • 第一元素,最后元素
  • 三、分类
    • 1.顺序表
      • 创建
      • 常见操作
      • 特点
    • 2.链表
      • 定义
      • 分类
      • 常见操作
      • 特点
  • 四、两表的比较
    • 跳跃表(skiplist)
  • 五、线型表的特点分析


前言

在看完数据结构基础入门篇后,再来讲解一下数据结构中常用的工具线型表。

基本模型


一、线型表是什么?

这里我们引入一下百度百科的概念:

将具有线性关系的数据存储到计算机中所使用的存储结构称为线型表。

因为线性表的逻辑结构简单,便于实现和操作。

二、常用概念

结点

结点又包含了两部分
数据域:存放的存储数据
指针域:存放的其它结点的地址

前驱

在逻辑上的前一个结点

后继

同理,后继就是在逻辑上的后一个结点

第一元素,最后元素

最简单的概念,他就是在分配地址时的一个元素。同理如果在创建时是静态创建时最后一个元素。

三、分类

我们都知道,在逻辑上相邻的数据在实际的物理存储中有两种形式:分散存储集中存储,那么我们就分析一下他们各自的优缺点吧。

被划分为以下两种表:

1.顺序表

创建

在创建时会在物理地址上分配一块地方
顺序表存储示意图

常见操作

  • 顺序表的初始化

在创建后就需要对表进行初始化操作,以避免一些脏数据会影响结果

  • 创建
  • 查找
  1. 顺序表的优点就是查询速度快(随机存取特点)当按位查找时他的时间复杂度就是常量级:O(1)
  2. 按值查找的时间复杂度:O(n)
  • 插入
    时间复杂度:(On)

需要注意的是:

因为他的底层实际就是数组,如果在分配地址时分配地址有剩余,那么就会将新加入的数据添加到后面。
但是添加的数据超过最大分配地址时,就需要重新创建一个更大的表来存储。

  • 删除

时间复杂度:O(n)

  • 清空
  • 判空

特点

  1. 随机访问

可以在时间复杂度为O(1)中可以找到第i个元素

  1. 存储密度高

在一片连续空间中就可以存储数据,因为本身就连续,不需要索引。

  1. 扩展不方便

因为在创建时就已经指定了大小,所以如果在扩展就需要重新分配地址。
同样的插,删数据也是相同的道理。

  1. 插,删数据难

2.链表

链表是一种常见的重要的数据结构。接下来让我们进一步了解他吧。

定义

什么是链表?

在这里我们引入一下百度百科的概念

链表是一种在物理结构上不连续存储结构,它是动态地进行存储分配的一种结构,由一系列结点组成。

具体的分类图解请看下文。

分类

  • 单向链表

    因为他是由一串结点组成的最后一个指针指向null,所以他又叫结点列表。
    它又可以分为 - 带头结点 和 - 不带头结点。

    在不带头结点中,它的下一结点是用于存放数据的。
    而头结点头指针指向的下一位是不存放数据元素的。
    显然带头结点写代码更方便。

单链表示意图

  • 双向链表

    同理双向链表就是一个节点中存储着前驱的地址和后继的地址。
    双链表示意图

  • 循环链表

    循环链表就是头尾相连的链表
    循环链表示意图

  • 静态链表

    静态链表就是用数组表示的链表,在物理地址上也是连续的。

常见操作

这里只针对单链表进行的操作

  • 判空
  • 插入
    因为插入时需要对每一个结点进行判断是否是指定位置。
    时间复杂度为O(n)
  • 前插
    可以遍历一遍寻找到对应结点进行操作。

但是也可以创建一个新的链表,将插入的数据与后面的结相连,组成一个新的链表。最后将前面的链表连接上。

那么它的时间复杂度就是:O(1)
  • 删除
    时间复杂度为:O(n)

  • 查找
    相比于顺序表,链表中的查找就显得比较忙了
    简单理解就是你需要从头开始找到下一个引路人,告诉你下一条路这么走。
    所以他的时间复杂度为:O(n)

  • 求长度
    实际上在增,删操作时就已经引入了求长度的方法,这里就不在多赘述。
    时间复杂度:O(n)

特点

  1. 高效的插入和删除
  2. 低效的随机访问

四、两表的比较

比较内容顺序表链表
存储存储密度高改容方便
分为自动回收和手动回收每个结点依次回收
增删改后面的元素都要移动只需要改变指针即可
有序时可用二分查找法:O(log2n)按位和按值都是O(n)

跳跃表(skiplist)

当我们遇到数据量很大时,要进行增删查操作时,在使用如上两表会很不方便,于是跳跃表就出现了

他是一种基于链表和二分查找法思想的实现

如图:跳跃表
当数据过多时就可以为一些结点来添加索引

跳跃表实质上是一种空间换时间的操作。

五、线型表的特点分析

  1. 均匀性:

    虽然数据元素可以是多种多样的,但是对于同一线型表中的各个元素他的类型长度必须是相同的。

  2. 有序性:

    因为他的存储是相对线型的,所以各数据元素在线性表中的位置只取决于它们的序号

注意:其它元素前面均只有一个数据元素(直接前驱)和后面均只有一个数据元素(直接后继)

这篇关于普歌-毅雁-线型表的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/670319

相关文章

设置图表的线型、属性和格式化字符串

from matplotlib import pyplot as pltx = [1, 3, 5, 7, 9]y = [2, 4, 6, 8, 10]'''# 改变线的属性# 第一种方式,向方法传入关键字参数来指定线型plt.plot(x, y, linewidth=15)''''''# 第二种方式,对plot()方法调用返回的线条实例(matplotlib.lines.Line2

36、线型光束感烟探测器的设置规范

一、图例: 二、设置规范: 1、探测器的光束轴线至顶棚的垂直距离宜为0.3m-1.0m,距地高度不宜超过20m; 2、相邻两组探测器的水平距离不应大于14m,探测器至侧墙水平距离不应大于7m,且不应小于0.5m,探测器的发射器和接收器之间的距离不宜超过100m; 3、探测器应设置在固定结构上; 4、探测器的设置应保证其接收端避开日光和人工光源直接照射; 5、选择反射式探测器时,应保证在反射板与

R语言学习case12:ggplot 置信区间(多线型)

接上文:多条曲线 R语言学习case11:ggplot 置信区间(包含多子图) 在ggplot2中,每个geom函数都接受一个映射参数。然而,并非每个美学属性都适用于每个geom。你可以设置点的形状,但不能设置线的“形状”。另一方面,你可以设置线的线型。geom_smooth()将为您映射到线型的每个唯一值绘制不同的线,具有不同的线型。 单一曲线 ggplot(data = mpg) + g

OpenGL在窗口显示多种线型

OpenGL初学 实现功能 1.画点、画线函数使用 2.新建一个窗口显示画的点、线 3.几种线型在窗口显示 //#include <iostream>#include<stdio.h>#include<math.h>#include<gl\glut.h>void init(void)//初始化相关的{//将显示窗口的背景颜色设置为白色,前三个参数分别为RGB,glClearColor(

tensorflow example 入门例子(线型回归与逻辑回归)

1. 前言–线性回归与逻辑回归介绍 tensorflow一般入门都至少会讲两种例子,一个是线型回归,一个是逻辑回归。(或者也可以说,回归算法 & 分类算法) 线性回归用来做回归预测,逻辑回归用于做二分类,一个是解决回归问题,一个用于解决分类问题。两者区别: 拟合函数不同: 线性回归: f(x)=θTX=θ1x1+θ2x2+⋯+θnxn f ( x ) = θ T X = θ 1 x 1

tensorflow example 入门例子(线型回归与逻辑回归)

1. 前言–线性回归与逻辑回归介绍 tensorflow一般入门都至少会讲两种例子,一个是线型回归,一个是逻辑回归。(或者也可以说,回归算法 & 分类算法) 线性回归用来做回归预测,逻辑回归用于做二分类,一个是解决回归问题,一个用于解决分类问题。两者区别: 拟合函数不同: 线性回归: f(x)=θTX=θ1x1+θ2x2+⋯+θnxn f ( x ) = θ T X = θ 1 x 1

利用matlab实现线型卡尔曼滤波(LKF)

LKF算法模型 例题 实现 观测只有位置 clc;clear;%测量值模拟N=100;%观测次数t=0:1:N-1;%假定输出周期T=1;x=zeros(6,N);z=zeros(3,N);x0=[0;0;50;0;5*cos(pi/6);5*sin(pi/6)];%真值初始值mu1=[0;0;0;0;0;0];mu2=[0;0;0];Q=diag(0.

flutter圆形或线型进度条

前言 Flutter是谷歌的移动UI框架,可以快速在iOS和Android上构建高质量的原生用户界面。 IT界著名的尼古拉斯·高尔包曾说:轮子是IT进步的阶梯!热门的框架千篇一律,好用轮子万里挑一!Flutter作为这两年开始崛起的跨平台开发框架,其第三方生态相比其他成熟框架还略有不足,但轮子的数量也已经很多了。本系列文章挑选日常app开发常用的轮子分享出来,给大家提高搬砖效率,同时也希望fl

hdu 4358 Boring counting(树型结构转线型结构,线段树)

题意:给你一棵树,树上的每个节点都有树值,给m个查询,问以每个点u为根的子树下有多少种权值恰好出现k次。 方法跟 Codeforces Round #136 (Div. 2) D. Little Elephant and Array很类似,只不过要将树型结构转化成线型结构。 #include <iostream>#include <cstdio>#include <cstring>#

Linear Regression及各种线型回归在正则化中的应用

Linear Regression 线性回归: from sklearn.linear_model import LinearRegressionlr = LinearRegression(fit_intercept=True)lr.fit(x, y)p = map(lr.predict, x)e = p - ytotal_error = np.sum(e*e)rmse_train