第二章：线性表（顺序表VS链表）

前面分别讲了顺序表和链表的存储特点以及基本的操作，下面讲解顺序表和链表的一些区别和在解决实际问题的时候我们应该做出怎样的选择，以及线性表的常用操作。

1.顺序表和链表的差异性

在单链表中每一个数据的存储不一定是连续的，所以我们无法实现随机存取，只能通过指针连接各个结点，所以我们只能实现顺序存取。而在顺序表中每一个数据源的存放是连续的，我们只需要通过LOC(A)+(n-1)*sizeof(ElemType)这个式子，只要我们知道第一个元素的地址，我们就可以通过计算得到每一个元素的地址，这样就可以实现随机存取和顺序存取。故：

单链表：只能实现顺序存取。顺序表：可以实现顺序存储和随机存取。

2.逻辑结构和物理结构差异性

单链表中数据元素的存储位置是任意的，可能相邻也可能不相邻，而顺序表元素的存储位置一定是相邻的。链表是通过指向下一个元素的指针来维持逻辑结构的，每一个元素不仅存放了数据元素还存放了下一个数据元素的地址，通过指针将所有的元素穿成一个链。而顺序表是通过数据元素的相邻性来维持逻辑结构的，在逻辑上相邻的数据元素，在物理上也是相邻的。

在这里插入图片描述

顺序表：逻辑相邻物理上也相邻,通过相邻表示逻辑关系。单链表：逻辑相邻物理上不一定相邻，通过指针表示逻辑关系。

3.线性表的基本操作

3.1插入

顺序表中：元素向后移动->将新元素赋值 单链表中：新结点S的next指针指向p结点的后一个结点->修改p结点的next指针指向新的结点S。

在这里插入图片描述

3.2删除

顺序表中：将要删除的元素开始，将后面的元素依次向前移动。单链表中：首先一个新的指针指向将要删除的结点q--->接着修改q的前面一个结点的next指针指向q后面的的结点--->接着释放q结点的空间。

在这里插入图片描述

插入&删除

• 单链表为O(1)(节点指针已知);O(n)(节点指针未知),但操作时只需修改指针
• 顺序表为O(n)且需要大量移动元素

3.3查找

按值查找

顺序表中：遍历整个顺序表对比值。O(n) 单链表中：遍历整个单链表对比值。O(n)

按序号查找

顺序表中：按照序号，我们通过数组的下标既可以直接找到对应序号的数组元素的位置。O(1) 单链表中：需要遍历整个链表。O(n)

在这里插入图片描述

查找

• 按值查找中单链表和顺序表(无序)都为O(n)；
• 按序查找中单链表为O(n),顺序表为O(1)；

3.内存空间的差异性

顺序存储 无论静态分配还是非静态都需要预先分配合适的内存空间静态分配时预分配空间太大会造成浪费，太小会造成溢出；动态分配时虽不会溢出但是扩充需要大量移动元素，操作效率低链式存储 在需要时分配结点空间即可,高效方便,但指针要使用额外空间。

4.怎样选择线性表的存储结构？

在这里插入图片描述

5.线性表的常用操作

在这里插入图片描述

5.1求最值

顺序表

首先使用两个变量标记数组的第一个元素为最大值和最小值，接着遍历顺序表，如果该元素大于最大值，则修改最大值的变量，如果小于最小值，则修改最小值变量。遍历结束即可得到最大值和最小值。

时间复杂度：O(n)

int min=L[0];int max=L[0];for(int i=0;i<n;i++){   if(min>L[i]){      min=L[i];   }   if(max<L[i]){      max=L[i];   }}

单链表

同理和顺序表。

在这里插入图片描述

时间复杂度：O(n)

5.2求逆置

顺序表

思路一，我们申请一个辅助空间，然后从尾部到头遍历整个顺序表，然后将每一个元素插入到新的空间中即可，但是这样的时间和空间复杂度是O(n)。下面讲解另一种方法：

我们可以使用两个标记分别指向头部元素i和尾部元素j的值，接着交换两个标记的数据元素的值，然后将i标记向后移动一位，j标记向前移动一位，继续交换元素的值.....直到i<j的时候结束。这种方法的时间复杂度为O(n)，空间复杂度为O(1)

单链表

在单链表中我们有一个头指针(p)和尾指针(r)，我们将第一个数据元素结点移动到(r)指针后面，接着继续将第一个数据元素结点移动到(r)指针后面....持续操作，直到p指针的下一个结点为(r)结点结束。

在这里插入图片描述

代码讲解：p->next!=r 就是移动结束的判断条件，移动到r结点作为第一个结点的时候结束。temp=p->next是保存p结点的下一个结点。p->next=temp->next就是直接将p结点和temp后面的结点相连接。【前两个语句是将要移动的结点拿出去并保存】temp->next=r->next修改要插入的结点的next指针指向r结点的后一个结点，r->next=temp;就是连接起来。【后两个语句是连接操作】

时间复杂度：O(n).

5.3合并

顺序表

需要新申请一个空间，大小为两个顺序表空间的和，然后需要找到两个顺序表中元素值最小的那个，然后插入的新的表中。这时需要借助三个标记，一个(i)指向L1的第一个位置，一个(j)指向L2的第一个位置，一个(k)指向新数组，注意这里的顺序表的元素都是从小到大排列的，我们只需要保证合并后的元素值也是从小到大排列。 然后我们需要一次比较两个数组的元素的值，如果L1[i]<L2[i]，这时将L1[i]添加到新的的数组中，同时标记k++，然后让i++，j不变，然后继续比较，如果L1数组的元素比较完了，此时L2数组还有剩余，此时不需要比较了，直接将L2数组元素依次添加到新数组中即可。

在这里插入图片描述

其中i<L1_Size&&j<L2_Size就是判断两个数组是否全部移除。下面的两个while判断就是判断两个数组是否全部移除完毕，因为不知道那个数组没移除完毕。

时间复杂度：O(n)

单链表

基本同理顺序表。

关于数据结构的知识，持续更新中，欢迎关注公众号理木客