你好赵伟

这个屌丝很懒，什么也没留下！

热门标签

【数据结构】——顺序表的插入、扩容、删除、性能分析基础详解

作者：你好赵伟 | 2024-05-19 10:27:42

踩

顺序表的插入

1.1线性表的定义

线性表：是由n个数据元素组成的有限序列，记为（a1，a2，……，ai，……，an）

eg：英文字母表（a，b，c……z）是一个长度为26的线性表

问题1：线性表是否允许长度n=0?

答：是！（从实际出发，为什么要有数据结构？为什么要有线性表?——让我们存储元素的呀！当我们的元素还没有进入线性表的时候，n=0）

问题2：什么叫前驱/后继？每个元素都有前驱/后继吗？

答：前驱——此元素前面的一个元素就是它的前驱。

后继——此元素后面的一个元素就是它的后继。

每个元素可能有一个前驱和后继。最后一个元素没有后继，前面的元素都有唯一的后继，eg：a1的后继是a2。第一个元素没有前驱，其他元素都有前驱

1.2 线性表的顺序存储结构

顺序表：用连续存储空间顺序存储数据元素的线性表

元素地址要满足的关系：

（1） Loc（ai）=Loc（a1）+（i-1）*m

（2） Loc（ai+1）=Loc（ai）+m

其中m是一个元素占用的存储单元个数，Loc（ai）是线性表的第i个元素的地址，第一个元素的地址也叫基地址

顺序表的特点：

逻辑上相邻的元素，物理地址也相邻
高性能的随机存取，低性能的插入删除，高性能的顺序访问

为了插入元素的方便，我们还会开辟一段备用空间。表的容量是capacity。在实际的写代码时，会用一个数组来记录基地址


template < typename ElemType >
struct SeqList{
    ElemType * items;  //基地址指针
    int  length;       //顺序表长度
    int  capacity;     //顺序表容量
};
 
//定义好啦以后，要申请才可以真的使用
 
items = new ElemType [capacity];
//申请成功，会返回一个非空的指针，失败返回空指针

1.3 顺序表的插入元素

接口： void insertBefore （int index， ElemType e）

语义：将元素e插入到顺序表第index个元素之前插


void insertBefore(int index,ElemType e){
    if（index <0|| index > length）    //在插入之前应该检查要插入的位置是否符合实际情况
        throw "out of range";          //如果插入位置小于0或大于表长，抛出异常
    for(int i=length; i>index; i--)    //从最后一个元素开始移动一个
        items[i] = items[i-1];
    items[index] = e;                  //插入元素e
    length++;                          //插入后长度+1
}

为了避免覆盖，从最后一个元素开始移动。直到移动叭ai的位置空出，插入元素e。

1.4 顺序表插入的性能分析

假设Pi是在第i个元素之前插入一个元素的概率，则在长度为n的线性表中插入一个元素时，移动元素的次数的平均次数为：

$E=\sum_{i=1}^{n+1}Pi(n-i+1)$

E是期望，如何知道概率P?——在不知道其分布的情况下，可以假设其为均匀分布, $P=\frac{1}{n+1}$ （长度为n，+1的1是可以在最后一个元素的后面插入元素）

$E=\frac{1}{n+1}\sum_{i=1}^{n+1}(n-i+1)=\frac{n}{2}$

时间复杂度 $T\left ( n \right )=O\left ( n \right )$ ,由计算得，表长为n的顺序表平均要移动n/2次

1.5 顺序表的扩容

新建顺序表的时候，我们预留啦备用空间，当我们不断插入元素后，顺序表的备用空间被用完，将会导致不能再继续插入元素。此时要将顺序表扩容

1.就近扩容法

free那段空间是操作系统知道是空闲的，但是用户并看不见。此时就要像操作系统递交申请新的空间。


新地址 = realloc（旧地址，新容量）;           //申请新的容量以扩充顺序表
if (新地址 == NULL ) throw "申请空间失败";   //申请失败返空指针，则抛出异常
if (新地址 != 旧地址 ){
    memcpy (新地址, 旧地址, 旧容量);         //把原来的表的内容复制到新表
    free (旧地址);                          //释放旧表的空间
}

时间复杂度 $T\left ( n \right )=\theta \left ( 1 \right )$

补补课：

realloc函数的使用

函数原型：void ＊realloc（void ＊p，size＿t size）

功能：realloc函数将p指向的对象的长度修改为size个字节，如果新分配的内存比原来的大，则原来的数据保持不变，增加的空间不进行初始化。

memcpy函数的使用

函数原型：extern void *memcpy( void *dest, void *src, unsigned int count );

用法：#include <string.h>

功能：由src所指内存区域复制count个字节到dest所指内存区域。

说明：src和dest所指内存区域不能重叠，函数返回指向dest的指针。

但是很不幸的是绝大多数情况都不能做到就近扩容，所以有下面的这个方法。

2.整体挪动法

后面的内存空间已经被别的占用啦，所以就不能就近扩容，只能整体的挪动。使用循环memcpy来把原有元素搬家到新的顺序表中，所以时间复杂度是 $T\left ( n \right )=\theta \left ( n \right )$

这里都讨论啦扩容的方法，但是并没有讨论扩多大，又1.6来详解。

1.6 扩容的策略

等量扩容

从1个元素依次扩容到n个元素，每次扩容固定增加x个元素存储空间，因此需要扩容 $\frac{n}{x}$ 次。例如，一次扩容8个存储空间，用完后又会再继续扩容8个存储空间……

假设x = 1，分摊到每个元素插入时间复杂度为：（分摊也是一种平均，所以式子里有 $\frac{1}{n}$ ）

$T\left ( n \right )= \frac{1}{n}\left ( 1+2+3+ \cdot \cdot \cdot +n\right )= \frac{1}{n}\cdot \frac{n\left ( n+1 \right )}{2}=\theta \left ( n \right )$

（解释：分摊到每次到插入，分摊到n次到扩容，x=1，每次都会导致一个扩容，因为用了刚扩的这个就没多的空间啦，就要扩容。第一个元素来了，放进去。第二个元素来了，要申请两个存储空间，把第一个元素复制放进去，第二个再写进去，做两次操作。第三个元素来了，要把前面两个元素写到新到空间，再把新插入的元素写进去。随着不断的扩容，消耗逐渐扩大，式子约掉以后发现是线性的复杂度 $\theta \left ( n \right )$ ——为了插入一个元素，平均扩容要移动n个元素，可以看出代价很大）

由刚刚的方式可以看出，等量扩容是个消耗很大的方式，因此提出了新的改进如下。

等比扩容

比例是2，每次扩容改为翻倍扩容。例如，第一次扩容1个存储空间，第2次扩容2个，第三次扩容8个，等比来扩容。

$T\left ( n \right )= \frac{1}{n}\left ( 1+2+4+8+\cdot \cdot \cdot +n \right )= \frac{1}{n}\cdot \frac{1-2^{\log n }}{1-2}=\theta \left ( 1 \right )$

和等量扩容的区别就是要加的项变少了，（1+2+4+…+n）是 $\log n$ 项。复杂度变成常数复杂度，性能提高

1.7 删除元素

接口： void deleteAt（int index）

语义: 删除顺序表的第index个元素


void deleteAt (int index){
     if( index < 0 || index >= length )        //判断要删除的元素的位置
        throw "out of range";                  //不符合实际则抛出异常
     for( int i = index; i < length - 1; i++ ) //从index后面一个元素开始移动
        items[i] = items[i + 1];
    length--;                                  //删除元素，长度减1
}

1.8 顺序表删除的性能分析

假设Pi是删除第i个元素的概率，则在长度为 n 的顺序表中删除一个元素所需移动的元素次数的平均次数是：

$E=\sum_{i=1}^{n} Pi\left ( n-i \right )$

E是期望，有n个可以删除的位置，每个位置的概率是Pi，每次删除都会导致后面的 n - i 个元素发生移动（代价）。同样假设Pi服从均匀分布,所以 $Pi=\frac{1}{n}$ ，计算得：

$E=\frac{1}{n}\sum_{i=1}^{n}\left ( n-1 \right )= \frac{n-1}{2}$

所以时间复杂度 $T\left ( n \right )=O\left ( n \right )$ 。由此看出，在顺序表中插入或删除一个元素时，平均移动表的一半元素，当n很大时，消耗很大，效率低。

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/你好赵伟/article/detail/592451