数学和计算机科学板块_辛酸网

数据结构与算法2

线性表

  前面已经说过，顺序表是线性表中最简单的一种。至于什么是线性表，其实就是结点和结点之间的关系是线性的，有一个严格的先后顺序。一个结点前面最多只有一个结点是和它直接相联系的，也就是说前驱结点是唯一的。而且，一个结点的后面，与之直接向关联的结点也是最多就那么一个，那就是说它的后继结点是唯一的。这里说的之间相关联是啥呢？比如说，在一个数据结构中，我说有a,b,c三个玩意被当成结点了，a在b的前面，b在c的前面，那我就可以说a在c的前面。但是，放眼整个数据结构中，是否有这样一个结点x，使得a在x前面而且x在b的前面呢？如果有这么一个x，那a和b就不是我说的那个，直接相关联了，毕竟中间隔了个x。但是如果没有呢？我说a在b的前面，但是中间没有什么别的结点，那就是逻辑上的挨着啊。

  这种逻辑上的挨着，有人称之为邻接。于是我可以说，什么是线性表呢？线性表就是：每一个结点，前面就一个和它邻接的结点，甚至没有（首），后面就一个跟它邻接的结点，甚至还没有（尾）。每一个结点内部，有一些需要存储和处理的数据。线性表的概念是一个逻辑的概念，但是这个概念如果有用，就应该转化为物理的概念。毕竟一个纯粹的逻辑的概念的存在，如果没有物理的存在与之对应，那真没什么用。由此我们就要搞清楚一个问题——线性表怎么存储？（这里的存储一般是指在内存里而非磁盘中，要不然涉及到文件系统那就恶心了）

什么是顺序表和链表

  之前我说过，什么是邻接，就是逻辑上挨着的情况。那么，凡是逻辑上挨着的东西，物理上是不是一定挨着的呢？也就是说，在内存里这些东西是不是真的就放在一起的呢？还真不一定。如果这些东西是物理上就都挨着的，那就叫顺序表。顺序表是线性表的一种特定的物理的存在，与之相反的存在是链表，链表中的结点并没有在物理上真的挨着，而是隔开的，但是利用指针一步一步可以寻址过去。总之，在物理上,要是线性表里面的东西是一个一个挨着的，进行顺序存储，那就是顺序表；要是一个一个都隔开了，进行链式存储，那就叫链表。

对顺序表做点事情

  凡是涉及数据结构的，包括数据库原理那门课的内容，你会发现人的最基本的行为无非不过四个：增删改查。其中进行只读的查找操作对于顺序表而言就比较容易，要是想看某一结点的一些细节的内容，你可以直接看。学过C语言的同志们都知道，顺序表这个东西的最简单的实现方式就是纯粹的一个数组。（之所以说是纯粹，是因为在其它语言尤其是Python中，数组的概念并不纯粹，其中列表不是直接放东西，而是放地址）那么数组这片连续的空间，只要你获取了首地址，然后告诉我要访问的元素的下标，我就能直接定位把这个东西给你拿出来。因为这个东西的地址很容易获取，不就是首地址加上元素大小乘以下标么？所以顺序表可以随机查找，想要哪个东西，直接给你，时间复杂度就是O(1).

  当然，直接修改某一结点内的值也是很快的，反正能直接找到，然后直接写。

  然而，麻烦的是，如果你要插入一个元素，为了保证这个顺序表中的元素是挨着的，你就必须让后面的元素移动来腾出空间来（除非是在结尾处，那不用）。那么后面的元素要如何移动呢？既然是后面的给前面的腾出空间来，那后面的就该向后移动。但是，就移动的顺序而言，却是从后往前的。也就是说，每一个元素都要从前往后移动一个位置，但整体而言这些元素的移动是从后往前的。假设我们要在第i个元素前面插入一个元素，那么插入的元素占据了原来i第i元素的位置，第i元素就需要占据原来第(i+1)个元素的位置，以此类推，第j个元素需要占据原来第(j+1)个元素的位置，最后一个元素需要额外占据一个原本空的位置。

  不过，若是我们对一个数组A先搞A[i]=x再搞A[i+1]=A[i]的话，那么x就直接覆盖了A[i]的值，之后A[i+1]就会把x的值复制过来，失去A[i]的信息。所以我们必须先把后面的元素转移一下，腾出空间为x的赋值做准备。同理，在向后转移时若先搞A[i+1]=A[i],再做A[i+2]=A[i+1]的话，那么原本第i个元素的值就把第(i+1)个元素的值直接覆盖了，接着再让这个覆盖了的值，去覆盖第(i+2)个元素的值，造成后面都是第i个元素的值。因此我们必须先执行A[i+2]=A[i+1]，再执行A[i+1]=A[i]。一般地，要先弄A[j+2]=A[j+1]，再搞A[j+1]=A[j]，当后面的值提前转移到更后面的位置保存下来，前面的覆盖才不会造成信息损失。显然，在要插入的地方后面，每一个元素都要为前一个元素腾出空间。而最后一个元素要到一片空的地方去，那就是下标加1后的新地方，为倒数第二个元素腾出空间。

  如上图，插入x，需要先让j后移，再让i后移，随后是h后移，直到c后移，才能把x赋值过去。

  删除元素与之类似，只不过是后方的每一个元素都在从后往前，占据空出来的位置，而就顺序而言整体的移动是从前往后的。

顺序表中插入和删除的时间复杂度

  插入和删除的时间复杂度，占大头的就是元素的移动。设顺序表原本有n个元素.最坏的情况下，如果在最前面插入一个，那么原来那n个都要向后移动，次数为n；如果把最前面的删了，那么后面(n-1)个元素都要向前移动，次数n-1。最好的情况下，如果在最后面放一个元素或是删掉最后面的那个，那就不移动了。现在考虑平均情况，假设在每一个元素前面插入的可能性相等，都是$\frac{1}{\mathrm{n}}$,其中如果在第i个元素（从0开始）前面插入，后面(n-i)个都要后移，于是平均移动次数为

${\mathrm{移动次数}}_{\mathrm{插入}}=\frac{1}{\mathrm{n}}{\mathrm{\sum }}_{\mathrm{i=0}}^{\mathrm{n}}\mathrm{(n-i)}=\frac{\mathrm{n}}{2}$

  即插入时的平均移动次数为$\frac{\mathrm{n}}{2}$类似地，若每一个元素被删除的可能性都相等，那么平均移动次数为$\frac{\mathrm{n-1}}{2}$。取数量级，我们会发现这两种操作最坏和平均时都是O(n)。整体上，顺序表的查找和修改很方便，是O(1)的时间复杂度，而插入和删除则是O(n)。这与链表恰恰相反。

辛酸网 ©版权所有