首页 > 编程语言 >3.数据结构与算法复习--线性表

3.数据结构与算法复习--线性表

时间:2023-06-25 17:12:08浏览次数:41  
标签:线性表 -- 元素 初始条件 ai 操作 数据结构 顺序存储

线性表的定义和特点

线性表是具有相同特性的数据元素的一个有限序列
(a1,a2,..ai-1,ai,ai+1,...an)
a1:线性起点
ai-1为ai的直接前驱,ai+1为ai的直接后驱
an为线性终点,当n=0时称为空表

  • 线性表

同一线性表中的元素必定具有相同特性,数据元素间的关系时线性关系

  • 线性表的逻辑特征是:
    • 在非空的线性表,有且仅有一个开始节点a1,它没有直接前趋,而仅有一个直接后继a2
    • 有仅有一个终端结点an,它没有直接后继,而仅有一个直接前趋an-1
    • 其余的内部结点ai(2≤i≤n-1)都有且仅有一个直接前趋ai-1和一个直接后继ai+1
      线性表是一种典型的线性结构

线性表的类型定义

  • 抽象数据类型线性表的定义如下:

基本操作

  • InitList(&L)
    • 操作结果:构造一个空的线性表L
  • DestroyList(&L)
    • 初始条件:线性表L已经存在
    • 操作结果:销毁线性表L
  • ClearList(&L)
    • 初始条件:线性表L已经存在
    • 操作结果:将线性表L重置为空表
  • ListEmpty(L)
    • 初始条件:线性表L已经存在
    • 操作结果: 若线性表L为空表,则返回TURE,否则返回FALSE
  • ListLength(L)
    • 初始条件:线性表L已经存在
    • 操作结果:返回线性表L中的数据元素个数
  • GetElem(L,i.&e)
    • 初始条件:线性表L已经存在,1≤i≤ListLength(L)
    • 操作结果:用e返回线性表L中第i个数据元素的值
  • LocateElem(L,e,compare())
    • 初始条件:线性表L已经存在,compare()是数据元素判定函数
    • 操作结果:返回L中第1个与e满足compare()的数据元素的位序。若这样的数据元素不存在则返回值为0
  • PriorElem(L,cur_e,&pre_e)
    • 初始条件:线性表L已经存在
    • 操作结果:若cur_e是L的数据元素,且不是第一个,则用pre_e返回它的前驱,否则操作失败,pre_e无意义
  • NextElem(L,cur_e,&next_e)
    • 初始条件:线性表L已经存在
    • 操作结果:若cur_e是L的数据元素,且不是第最后一个,则用next_e返回它的后继,否则操作失败,next_e无意义
  • Listlnsert(&L,i,e)
    • 初始条件:线性表L已经存在,1≤i≤ListLength(L)+1
    • 操作结果:在L的第i个位置之前插入新的数据元素e,L的长度加一
  • ListDelete(&L,i,&e)
    • 初始条件:线性表L已经存在,1≤i≤ListLength(L)
    • 操作结果: 删除L的第i个数据元素,并用e返回其值,L的长度减一
  • ListTraverse(&L,visited())
    • 初始条件:线性表L已经存在
    • 操作结果:依次对线性表中每个元素调用visited()

线性表的存储结构

  • 在计算机内,线性表有两种基本的存储结构:
    顺序存储结构链式存储结构

线性表的顺序存储表示

线性表的顺序表又称为顺序存储结构顺序映像
顺序存储定义:把逻辑上相邻的数据元素存储在物理上相邻的存储单元中的存储结构。
线性表:(a1,a2,...,ai-1,ai,ai+1,...,an)
线形表顺序存储结构占用一片连续的存储空间。知道某个元素的存储位置就可以计算其他元素的存储位置

标签:线性表,--,元素,初始条件,ai,操作,数据结构,顺序存储
From: https://www.cnblogs.com/laocaigoul/p/17498769.html

相关文章

  • C++ 数据抽象
     数据抽象是指,只向外界提供关键信息,并隐藏其后台的实现细节,即只表现必要的信息而不呈现细节。数据抽象是一种依赖于接口和实现分离的编程(设计)技术。让我们举一个现实生活中的真实例子,比如一台电视机,您可以打开和关闭、切换频道、调整音量、添加外部组件(如喇叭、录像机、DVD播......
  • 运维想要不背锅,这7点了解一下!
    所谓的“不背锅”,我希望强调的是运维工程师应该避免因自身问题所带来的过度承担责任和不必要的风险,欢迎留言并留下你的看法。下面总结的几点:清晰的职责边界定期维护好运维文档临时修改配置文件也要做好备份定期备份重要数据发布变更到生产之前一定要发布到测试环境严格测......
  • 修改博客园代码块高亮主题
    博客园(默认编辑器设置为Markdowm)是使用heightlight.js进行代码块高亮的。因此可以通过下载heightlight.js官网的主题css修改博客园中的代码块高亮颜色。修改方法:进入heightlight.js官网,点击demo页面预览,查看主题效果在下载页面选择需要的语言并下载打开下载......
  • 线上非业务问题排查
     常见的线上问题基本都是业务代码导致的问题,例如某个空指针或者是代码编写存在漏洞。这里记录一下网上看到的容器服务线程数飙升导致的问题  一、监控数据首先看下监控公司采用Prometheus监控,有较为完善的监控指标,因运维同学说的是线程数过多,那就只列出和线程相关的监控......
  • [WP] 攻防世界 CSFJ0978 Check
    「附件」下载附件,一个图片「思路」推断图片隐写,使用Stegsolve打开图片,切换通道,未发现水印、二维码等异常。使用stegsolve的Analysis——DataExtract,Red、Green、Blue均设为0,BitOrder设为MSBFirst或LSBFirst(都行)发现开头部分编码比较有规律,Savebin。使用编辑器打开......
  • electron中调用node.js API
    主进程在node.js环境中运行,等同于它拥有调用require模块和使用所有node.jsAPI的能力。但是在渲染器进程中,渲染器是无法直接访问require和其他node.jsAPI的,想要访问有以下两种方法:Preload脚本预加载脚本运行在渲染器环境中,可以在BrowserWindow构造方法中的webPreferences选项里被......
  • 其他——25封装表单验证
    前言:在我们做vue项目,日常开发的时候,肯定会经常遇到正则表达式,例如手机号,邮箱,密码和数字,每次验证都需要去查询,浪费时间不说,也造成代码冗余,我也遇到过,那我就自己封装一个吧,方便大家使用查询。1.封装一个公共的js文件,命名rule.js://手机号验证telphone:(rule,value,callback......
  • elementplus vue 范围输入框
    <divclass="fv-rowmb-7"><labelclass="fs-6fw-semoboldmb-2">{{t("Numberofgroups")}}</label><el-form-itemprop="formInline.group"><el-inputcl......
  • C# .NET6结束UI线程
    在.NET6项目中,不再支持Thread.Abort:Thread.AbortisnotsupportedandthrowsPlatformNotSupportedException.原因是Thread.Abort可能导致资源泄漏,1.不正常的关闭,导致线程运行过程中待释放资源的业务代码,未能完成执行。2.异常捕获,业务模块未添加捕获、业务模块添加了捕获但......
  • "Failed to destroy network for sandbox" 错误处理分享
    问题说明:calicopod突然报错,如下截图最后排查到containerd的cni插件有问题,官方文档说的是:如果你使用containerdv1.6.0-v1.6.3并遇到"IncompatibleCNIversions"或者"Failedtodestroynetworkforsandbox"错误,考虑更新你的CNI插件并编辑CNI配置文件(如果版本......