5.0、C语言数据结构——线性表 ( 2 )

5.0、C语言数据结构——线性表 ( 2 )

线性表的顺序存储结构：

        1. 我们可以想象，线性表有两种物理存储结构：顺序存储结构和链式存储结构；
        2. 线性表的顺序存储结构，指的是用一段连续的地址存储单元一次存储线性表的数据元素
        3. 线性表 （a1 , a2 , ... , an）的顺序存储如下:

        物理上的存储方式事实上就是在内存中找个初始地址，然后通过站位的形式，把一定的内存空间给占了，然后把相同的数据类型的数据元素依次放在这块空地中

        接下来看线性表顺序存储的结构代码：

#edfine MAXSIZE 20
typedef int ElemType;
typedef struct {
    ElemType data[MAXSIZE];
    int length;
} SqList;

        大家看到了，这类我们封装了一个结构，事实上就是对数组进行封装，增加了当前长度的变量罢了；

总结下，顺序存储结构封装需要三个属性：
        1. 存储空间的起始位置，数组data，它的存储位置就是线性表存储空间的存储位置；
        2. 线性表的最大存储容量：数组的长度MaxSize；
        3. 线性表的当前长度：length；

注意 ->
        数组的长度与线性表的当前长度需要区分一下：数组的长度是存放线性表的存储空间的总长度，一般初始化后不变。而线性表的当前长度是线性表中元素的个数，是会变化的；

        假设ElemType 占用的是 c 个存储单元（字节），那么线性表中第 i + 1 个数据元素和第 i 个数据元素的存储位置的关系是（LOC表示获得存储位置的函数） : LOC( ai + 1 ) = LOC( ai ) + c；

        所以对于第 i 个数据元素 ai 的存储位置可以由 a1 推算得出 ： LOC ( ai ) = LOC(a1) + ( i - 1 ) * c ;
        结合下图来理解：

         通过这个公式，我们可以随时计算出线性表中任意位置的地址，不管他是第一个还是最后一个，都是相同的时间。那么他的存储时间性能当然就为 0( 1 ) ，我们通常称为随机存储结构；

        实现 GetElem 的具体操作，即将线性表 L 中的第 i 个位置元素返回。就程序而言非常简单了，我们只需要把数组第 i -1 下标的值返回即可；
        实现代码，如下所示： 
 

Status GetElem (SqList L , int i , ElemType* e) {
    if( L.length == 0 || i < 1 || i > L.length ) {
        return ERROR;
    }
    *e = L.data(i - 1);
    return OK;
}

        注意这里返回值类型 Status 是一个整型，约定返回 1 代表 OK ， 返回 0 代表 ERROR。今后还会出现，也是使用同样的约定，不再详述；

        刚才我们也谈到，线性表的顺序存储结构具有随机存储结构的特点，时间复杂度为 O ( 1 )；
        大家现在来考虑下，如果我们要实现，ListInsert ( *L , i , e )，即在线性表 L 中的第 i 个位置插入新元素 e ，代码应该如何写？

所以插入算法的思路：
        1. 如果插入位置不合理，抛出异常；
        2. 如果线性表长度大于等于数组长度，则抛出异常或动态增阿基数组容量；
        3. 从最后一个元素开始向前遍历到第 i 个位置，分别将他们都向后移动一个位置；
        4. 将要插入元素填入位置 i 处；
        5. 线性表长 + 1

Status ListInsert(SqList* L , int i , ElemType e) {
    int k;
    if(L->length == MAXSIZE) {
        return ERROR;
    }
    if(i < 1 || i > L->length + 1) {
        return ERROR;
    }
    if(i<=L->length) {
        for(k = L->length-1;k >= i-1;k--) {
            L->data[k+1] = L->data[k];
        }
    }
    L->data[i-1] = e;
    L->length++;
    return OK;
}

        1. 现在我们分析一下，插入 和 删除 的时间复杂度;
        2. 最好的情况：插入和删除操作刚好要求在最后一个位置操作，因为不需要移动任何元素，所以此时的时间复杂度O ( 1 )；
        3. 最坏的情况：如果要插入和删除的位置是第一个元素，那就意味着要移动所有的元素向后或者向前，所以这个时间复杂度为 O ( n )；
        4. 至于平均情况，就去中间值 O( ( n - 1 ) / 2 );
        5. 按照前边游戏秘籍指导，平均情况复杂度简化后还是 O ( n );
        6. 线性表的顺序存储结构，再存、读数据时，不管哪个位置，时间复杂度都是O ( 1 )；而在插入或删除时，时间复杂度都是 O ( n )；
        7. 这就是说明，他比较合适元素个数比较稳定，不经常插入和删除元素，而个更多的操作时存取数据的应用；

那我们接下来给大家简单总结一下线性表的顺序存储结构的优缺点：

        优点：
                1. 无须为表示表中元素之间的漏记关系而增加额外的存储空间；
                2. 可以快速地存取表中任意位置的元素；
        缺点：
                1. 插入和删除操作需要移动大量元素；
                2. 当线性表长度变化较大时，难以确定存储空间的容量；
                3. 容易造成存储空间的 “ 碎片 ”；

        1. 前面我们讲的线性表的顺序存储结构，他最大的缺点就是插入和删除时需要移动大量元素，这显然就需要耗费时间；
        2. 那我们能不能针对这个缺陷或者说遗憾提出解决的方法呢？要解决这个问题，我们就得考虑一下导致整个问题的原因？
        3. 为什么当插入和删除时，就要移动大量的元素？
        原因就在于相邻两个元素的存储位置也具有邻居关系，他们在内存中的位置是紧挨着的，中间没有间隙，当然就无法快速插入和删除；