线性表的一二三事

欢迎点击「算法与编程之美」关注我们！

本文首发于微信公众号："算法与编程之美"，欢迎关注，及时了解更多此系列文章。

《数据结构与算法（python语言描述）》第二节课总结

算法的高效性

一道编程题的算法设计多种多样，不是唯一而定的，程序顺利运行只是算法几个要求中最基础的要求。而代码是否简洁清晰、通俗易懂也是很重要的因素，“最美代码奖”就是依据这个原理来设定的。在教学中，常常会由“如何评价AB同学的算法高效性”这样的问题来引出线性表。很多同学都会强调所用时间，因为大家都会觉得时间短表明运行快，就说明代码好。但其实不然，如果只考虑时间，那就要考虑到其他条件，硬件差别很大也会导致运行时间的差异。明明A同学的代码更好，但B同学的电脑配置更高，运行速度更快，那这样就会有失公正。有人可能想，把两种算法放到同一台电脑中运行不就可以公正参考了吗？但是我们要考虑的是实际问题，代码量大且繁琐，需要用的时间很多，所以我们要用一个全球统一的标准来评价算法的高效性。那就是评价算法的时间代价和空间代价。

线性表

本章的重点是线性表，而线性表是数据结构中最基本的数据结构之一，也可以来理解计算机对数据的储存和查找的原理。而在线性表的操作中删除元素是基本操作，这需要动态改变表的内容。而删除元素有三种，一是定位删除，删掉某个特定位置的元素。二是删掉0元素。三是删掉不满足条件的元素。而涉及到删除就要考虑到数据位置的表示。

如下图，这是按照顺序放置的线性表。

如下图，这也是按照顺序放置的线性表，但不是从开头开始放置的。

如下图，这是随便放置的线性表。

而随便放置数据后，再想找到相邻的数据就有些困难了，所以我们就可以采用放置地址的方式找到某一个数后面的数据。

比如在1后面应该是2，但这个时候2并不在1后面，所以我们就可以把2的地址找到，也就是14，这样我们就还是可以实现1.2的顺序了。同理，在3后面应该是4，但是真正的4在表里的其他地方，所以也把他的地址找到就是9。

同理，我们可以通过输入地址的这样的方法找到数据的后一个数，也可以找到前一个数。而这里有一个容易混淆的知识点就是，我们输入的前一个数的地址时，不能把它直接放到数的前面。而是要利用数组的顺序，依次放到原本我们就知道的数的后面，而此时有三个数，也是要按照数的顺序来填写地址的顺序。

总结

线性表虽然只是数据结构中比较简单的结构，但是他的重要性也是不言而喻的。在将数据放置进表中的时候，我们也要考虑数据结构与python之间的关系。而这样的表在python中就是list的意思。

上述公式是地址的计算公式，而在实际的计算中，还要添加上时间这个变量哦！掌握好线性表这个知识，使非常重要的，对以后的学习能够打下很坚实的基础！