【玩转408数据结构】线性表——定义和基本操作

这篇具有很好参考价值的文章主要介绍了【玩转408数据结构】线性表——定义和基本操作。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

考点剖析

        线性表是算法题命题的重点,该类题目实现相对容易且代码量不高,但需要最优的性能(也就是其时间复杂度以及空间复杂度最优),这样才可以获得满分。所以在考研复习中,我们需要掌握线性表的基本操作,在平时多进行代码练习。当然在考场上,我们并不一定要求代码具有实际的可执行性,但我们需要去清晰的表达出算法的思路步骤,且算法题目只允许使用 C/C++ 语言进行实现

线性表知识点

        关于线性表这章内容其实并不多,我们将其分为两大部分:顺序存储(也就是我们常说的顺序表)和链式存储(链表),其中对于链表部分我们需要掌握其中的 单链表、双链表、循环链表、静态链表等部分链表。

        关于线性表的内容并不是太难,我将用3-4篇文章带着大家一起了解线性表以及其实现,当我们可以自己去实现其功能的时候,我们对于该部分内容的知识掌握也就十分的熟练了,那么废话不多说,我们下面开始正式的进入线性表的学习。

线性表的定义

        线性表是具有相同数据类型的 n ( n   0) 个数据元素的有限序列,其中n为表长;当n=0时,线性表为空表。在这里我们以L命名线性表,可以将其表示为:

site:csdn.net,考研408之数据结构,数据结构,考研,算法

        其中: 是线性表的第一个元素,我们也称其为表头元素;是线性表的最后一个元素,我们称其为表尾元素。

        除了第一个元素外,每个元素有且仅有一个直接前驱(前一个元素);除了最后一个元素外,每个元素有且仅有一个直接后续(后一个元素)。当然我们也可以将“直接前驱”称为“前驱”,将“直接后续”称为“后续”。

site:csdn.net,考研408之数据结构,数据结构,考研,算法

        通过已上知识我们总结出线性表的特点如下所示:

  • 线性表元素个数有限
  • 线性表元素都是数据元素,每个元素都是单个元素
  • 线性表的元素具有逻辑上的顺序性,表中的元素有其先后次序
  • 线性表的数据类型都相同,所以其每个元素所占空间大小相同
  • 线性表的元素具有抽象性,我们讨论元素间的逻辑关系,不考虑元素究竟表示什么内容

 注:线性表是逻辑结构,表示元素一对一的相邻关系,而我们前面所了解的链表以及顺序表指的是存储结构。(也就是说线性表的顺序存储是顺序表,线性表的链式存储是链表;这两个只是在存储结构上存在差异,而其逻辑结构归根结底都是线性表)。

线性表的基本操作

        对于线性表,有一些基本操作是需要我们去学习的,至于为什么要学习这些基本操作,当然408大纲要求是要学习的,但在这里我们还是可以了解一下原因的。我们去对一些数据结构的基本操作进行封装实现,这样我们在进行复杂的操作时,可以去调用相关基本操作进行实现,并且这样进行封装也有利于减少错误的产生。

        线性表的基本操作如下所示:

InitList(&L);    //线性表的初始化
DestroyList(&L);    //销毁线性表

ListInsert(&L,i,e);    //线性表的插入
ListDelete(&L,i,&e);    //线性表的删除

LocateElem(L,e);    //按值查找
GetElem(L,i);    //按位查找

Length(L);    //求线性表长
PrintList(L);    //按顺序输出线性表的所有值
Empty(L);    //判断线性表是否为空

(如果不懂为什么要加“&”的同学可以去学习一下,简单来说加“&”的元素我们可以修改其值,它会将其值带回来,而不加的我们在函数中修改其值是在主函数中无效的)。        

注:在这里线性表只是一种逻辑结构,我们对于其基本操作的实现是要基于存储结构的,不同的存储结构实现其功能的方法是不同的,所以对于这些基本操作的实现,我会在后面顺序表和链表的讲解中进行代码的实现,在这里我们仅对其基本操作有一个了解即可。 

小测试

  1.  线性表是一个可以存不同数据类型的n ( n   0) 个数据元素的有限序列吗?
  2. 在线性表中每一个元素都有自己的前驱和后续元素吗?
  3. 不同的线性表的逻辑结构必然存在一些差异性。对吗?

答案

  1. 错,线性表需要存储相同的数据类型。

  2. 错,第一个元素不存在前驱,最后一个元素不存在后续。

  3. 错,线性表的逻辑结构是相同的。 文章来源地址https://www.toymoban.com/news/detail-825153.html

到了这里,关于【玩转408数据结构】线性表——定义和基本操作的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包