美文网首页程序员
数据结构和算法之一——线性表_2_顺序结构存储

数据结构和算法之一——线性表_2_顺序结构存储

作者: Eric_Hunter | 来源:发表于2018-01-11 15:58 被阅读0次
    1. 线性表存储结构分类
      线性表有两种物理存储结构:1)顺序存储结构;2)链式存储结构

    2. 顺序存储结构
      2.1定义:线性表的顺序存储结构,指的是用一段地址连续的存储单元依次存储线性表的数据元素。(物理上的存储方式事实上就是在内存中找个初始地址,然后通过占位的形式,把一定的连续的内存空间给占了,然后把相同数据类型的数据元素依次放在这块内存空间中。)
      线性表( a1,a2,...,an )的顺序存储如下:


      顺序存储结构

    2.2 线性表顺序存储的结构代码,见例1.

    //例1,代码段
    /#define MAXSIZE 20
    typedef int ElemType;
    typedef struct
    {
    ElemType data[MAXSIZE];
    int length; // 线性表当前长度
    } SqList;
    (注:这里事实上就是对数组进行封装,增加了个当前长度的变量罢了)

    2.3 顺序存储结构封装需要三个属性:
    1)存储空间的起始位置,数组“data” ,它的存储位置就是线性表存储空间的存储位置。
    2)线性表的最大存储容量:数组的长度 MaxSize 。
    3)线性表的当前长度: length 。
    (注意,数组的长度与线性表的当前长度需要区分一下:数组的长度是存放线性表的存储空间的总长度,一般初始化后不变;而线性表的当前长度是线性表中元素的个数,是会变化的。)

    2.4 线性表顺序存储结构的地址计算方法
        假设 ElemType 占用的是 c 个存储单元(字节),那么线性表中第 i+1 个数据元素和第 i 个数据元素的存储位置的关系是( LOC 表示获得存储位置的函数):LOC(ai+1) = LOC(ai) + c。 所以对于第 i 个数据元素 ai 的存储位置可以由 a1推算得出: LOC(ai) = LOC(a1) + (i-1)*c
    

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

    2.5 线性表顺序存储结构的获得元素操作
        实现 GetElem 的具体操作,即将线性表 L 中的第i 个位置元素值返回。我们只需要把数组第 i-1 下标的值返回即可(因为在数组中,第i个元素的下标是i-1),其时间复杂度为O(1),见例2.
    

    //例2,代码段
    /#define OK 1
    /#define ERROR 0
    /#define TRUE 1
    /#define FALSE 0

    typedef int Status;
    // Status 是函数的类型,其值是函数结果状态代码,如OK等。
    // 初始条件:顺序线性表L已存在,1 <= i <= ListLength(L)
    // 操作结果:用e返回L中第i个数据元素的值。
    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;
    }

    2.6 线性表顺序存储结构的插入元素操作
    插入算法的思路:
    1)如果插入位置不合理,抛出异常;
    2)如果线性表长度大于等于数组长度,则抛出异常或动态增加数组容量;
    3) 从最后一个元素开始向前遍历到第 i 个位置,分别将它们都向后移动一个位置;
    4) 将要插入元素填入位置 i 处;
    5) 线性表长 +1 。
    (注:插入元素算法的时间复杂度为O(n),见例3.)

    //例3,代码段
    /* 初始条件:顺序线性表L已存在,1<=i<=ListLength(L)。 /
    /
    操作结果:在L中第i个位置之前插入新的数据元素e,L长度+1。*/
    Status ListInsert(SqList L, int i, ElemType e)
    {
    int k;
    if( L->length == MAXSIZE ) // 顺序线性表已经满了
    {
    return ERROR;
    }
    if( i<1 || i>L->length+1) // 当i不在范围内时
    {
    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;
    }

    2.7 线性表顺存储结构的删除操作
    

    删除算法的思路:
    1)如果删除位置不合理,抛出异常;
    2)取出删除元素;
    3)从删除元素位置开始遍历到最后一个元素位置,分别将它们都向前移动一个位置;
    4)表长 -1 。
    (注:删除算法的时间复杂度为O(n),见例4.)

    //例4,代码段
    /* 初始条件:顺序线性表L已存在,1<=i<=ListLength(L) /
    /
    操作结果:删除L的第i个数据元素,并用e返回其值,L的长度-1 */
    Status ListDelete(SqList *L, int i, ElemType *e)
    {
    int k;
    if( L->length == 0 )
    {
    return ERROR;
    }
    if( i<1 || i>L->length )
    {
    return ERROR;
    }
    *e = L->data[i-1];
    if( i < L->length )
    {
    for( k=i; k < L->length; k++ )
    {
    L->data[k-1] = L->data[k];
    }
    }
    L->length--;
    return OK;
    }

    2.8 线性表顺存储结构的分析
    插入和删除操作的时间复杂度分析:
    1)最好的情况:插入和删除操作刚好要求在最后一个位置操作,因为不需要移动任何元素,所以此时的时间复杂度为 O(1) 。
    2)最坏的情况:如果要插入和删除的位置是第一个元素,那就意味着要移动所有的元素向后或者向前,所以这个时间复杂度为 O(n) 。
    3)平均情况:就取中间值 O((n-1)/2) ,平均情况复杂度简化后还是O(n) 。

    线性表顺序存储结构的特点:
    线性表的顺序存储结构,在存、读数据时,不管是哪个位置,时间复杂度都是 O(1) 。而在插入或删除时,时间复杂度都是 O(n) 。这就说明,它比较适合元素个数比较稳定,不经常插入和删除元素,而更多的操作存取数据的应用。

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

    相关文章

      网友评论

        本文标题:数据结构和算法之一——线性表_2_顺序结构存储

        本文链接:https://www.haomeiwen.com/subject/fmqtoxtx.html