数据结构与算法-线性表的顺序存储结构

680 阅读9分钟

1、顺序存储结构

1.1、顺序存储的定义

说这么多的线性表,我们来看看线性表的两种物理结构的第一种——顺序存储结构。

线性表的顺序存储结构,指的是用一段地址连续的存储单元依次存储线性表的数据元素。

线性表(a1,a2,......,an)的顺序存储示意图如下:

image-20200405195000254

1.2、顺序存储方式

线性表的顺序存储结构,说白了,和刚才的例子一样,就是在内存中找了块地儿,通过占位的形式,把一定内存空间给占了,然后把相同数据类型的数据元素依次存放在这块空地中。既然线性表的每个数据元素的类型都相同,所以可以用C语言(其他语言也相同)的一维数组来实现顺序存储结构,即把第一个数据元素存到数组下标为0的位置中,接着把线性表相邻的元素存储在数组中相邻的位置。

线性表的顺序存储的结构代码。

// 存储空间初始分配量
#define MAXSIZE 20
// ElemtType类型根据实际情况而定,这里假设为int
typedef int ElemtType;

typedef struct {
    // 数组存储数据的元素,最多为MAXSIZE个
    ElemtType data[MAXSIZE];
    // 线性表当前的长度
    int length;
} Sqlit;

这里,我们就发现描述顺序存储结构需要三个属性:

  • 存储空间的起始位置:数组data,它的存储位置就是存储空间的存储位置。
  • 线性表的最大存储容量:数组长度MaxSize。
  • 线性表的当前长度:length。

1.3、数组长度与线性表长度区别

注意哦,这里有两个概念“数组的长度”和“线性表的长度”需要区分一下。

数组的长度是存放线性表的存储空间的长度,存储分配后这个量一般是不变的。

数组的大小一定不可以变吗?我怎么看到有书中谈到可以动态分配的一维数组。是的,一般高级语言,比如C、VB、C++都可以用编程手段实现动态分配数组,不过这会带来性能上的损耗。

线性表的长度是线性表中数据元素的个数,随着线性表插入和删除操作的进行,这个量是变化的。在任意时刻,线性表的长度应该小于等于数组的长度。

1.4、地址计算方法

由于我们数数都是从1开始数的,线性表的定义也不能免俗,起始也是1,可C语言中的数组却是从0开始第一个下标的,于是线性表的第i个元素是要存储在数组下标为i-1的位置,即数据元素的序号和存放它的数组下标之间存在对应关系(如图3-4-3所示)。

image-20200405200611248

用数组存储顺序表意味着要分配固定长度的数组空间,由于线性表中可以进行插入和删除操作,因此分配的数组空间要大于等于当前线性表的长度。

由于每个数据元素,不管它是整型、实型还是字符型,它都是需要占用一定的存储单元空间的。假设占用的是c个存储单元,那么线性表中第i+1个数据元素的存储位置和第i个数据元素的存储位置满足下列关系(LOC表示获得存储位置的函数)。

LOC(ai+1)=LOC(ai)+c

所以对于第i个数据元素ai的存储位置可以由a1推算得出:

LOC(ai)=LOC(a1)+(i-1)*c

从下图来理解

image-20200405201227287

通过这个公式,你可以随时算出线性表中任意位置的地址,不管它是第一个还是最后一个,都是相同的时间。那么我们对每个线性表位置的存入或者取出数据,对于计算机来说都是相等的时间,也就是一个常数,因此用我们算法中学到的时间复杂度的概念来说,它的存取时间性能为O(1)。我们通常把具有这一特点的存储结构称为随机存取结构。

2、顺序存储结构的插入与删除

2.1、获得元素

对于线性表的顺序存储结构来说,如果我们要实现GetElem操作,即将线性表L中的第i个位置元素值返回,其实是非常简单的。就程序而言,只要i的数值在数组下标范围内,就是把数组第i-1下标的值返回即可。来看代码:

#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
// Status是函数的类型,其值是函数结果状态代码,如OK等
typedef int Status;

// 初始条件:顺序线性表L已存在,1≤i≤ListLength(L)操作结果:用e返回L中第i个数据元素的值
Status GetElem(SqList L, int i, ElemtType *e) {
    if (L.length == 0 || i < 1 || i > L.length) {
        return ERROR;
    }
    *e = L.data[i - 1];
    return OK;
}

2.2、插入操作

刚才我们也谈到,这里的时间复杂度为O(1)。我们现在来考虑,如果我们要实现ListIn-sert(*L,i,e),即在线性表L中的第i个位置插入新元素e,应该如何操作?

举个例子,本来我们在春运时去买火车票,大家都排队排的好好的。这时来了一个美女,对着队伍中排在第三位的你说,“大哥,求求你帮帮忙,我家母亲有病,我得急着回去看她,这队伍这么长,你可否让我排在你的前面?”你心一软,就同意了。这时,你必须得退后一步,否则她是没法进到队伍来的。这可不得了,后面的人像蠕虫一样,全部都得退一步。骂声四起。但后面的人也不清楚这加塞是怎么回事,没什么办法。

这个例子其实已经说明了线性表的顺序存储结构,在插入数据时的实现过程(如图3-5-1所示)。

image-20200405202449263

插入算法的思路:

  • 如果插入位置不合理,抛出异常;
  • 如果线性表长度大于等于数组长度,则抛出异常或动态增加容量;
  • 从最后一个元素开始向前遍历到第i个位置,分别将它们都向后移动一个位置;
  • 将要插入元素填入位置i处; ?表长加1。

实现代码如下:

// 初始条件:顺序线性表L已存在,1≤i≤ListLength(L),
// 操作结果:在L中第i个位置之前插入新的数据元素e,L的长度加1
Status ListInsert(SqList *L, int i, ElemtType e) {
    // 顺序表是否已满
    if (L->length == MAXSIZE) {
        return OK;
    }
    // 判断i值是否在合理的范围内
    if (i < 1 || i > L->length + 1) {
        return ERROR;
    }
    // 如果插入的数据不在表尾部
    if (i <= L->length) {
        //将要插入位置后数据元素向后移动一位
        for (int j = L->length - 1; j >= i - 1; j--) {
            L->data[j + 1] = L->data[j];
        }
    }
    // 将新元素e 放入第i个位置上
    L->data[i - 1] = e;
    // 更新顺序表的长度
    L->length++;
    return OK;
}

2.3、删除操作

接着刚才的例子。此时后面排队的人群意见都很大,都说怎么可以这样,不管什么原因,插队就是不行,有本事,找火车站开后门去。就在这时,远处跑来一胖子,对着这美女喊,可找到你了,你这骗子,还我钱。只见这女子二话不说,突然就冲出了队伍,胖子追在其后,消失在人群中。哦,原来她是倒卖火车票的黄牛,刚才还装可怜。于是排队的人群,又像蠕虫一样,均向前移动了一步,骂声渐息,队伍又恢复了平静。

这就是线性表的顺序存储结构删除元素的过程(如图所示)。

image-20200405204126327

删除算法的思路:

  • 如果删除位置不合理,抛出异常;
  • 取出删除元素;
  • 从删除元素的位置,直到最后一个元素的位置,分别将它们向前移动一个位置;
  • 表长度减1;

实现代码如下:

// 初始条件:顺序线性表L已存在,1≤i≤ListLength(L)
// 操作结果:删除L的第i个数据元素,并用e返回其值,L的长度减1

Status ListDelete(SqList *L, int i, ElemtType *e) {
    // 线性表为空
    if (L->length == 0) {
        return ERROR;
    }
    // 位置不正确
    if (i < 1 || i > L->length) {
        return ERROR;
    }
    if (e != NULL) {
        *e = L->data[i - 1];
    }
    // 如果删除不是最后位置
    if (i < L->length) {
        // 将每个元素前移一个位置
        for (int j = i; j < L->length; j++) {
            L->data[j - 1] = L->data[j];
        }

    }
    L->length--;
    return OK;
}

2.4、输出所有元素

算法思路:

  • 判断线性表是否为空;
  • 从第一个位置开始表里到最后一个位置,依次输出所有的元素;

代码实现:

// 初始条件:顺序线性表L已存在
Status ListPrint(SqList L) {
    if (L.length == 0) {
        return ERROR;
    }
    for (int i = 1; i <= L.length; i++) {
        ElemtType elem;
      	// 调用获取元素的函数,在2.1中定义的函数
        GetElem(L, i, &elem);
        printf("%d  ", elem);
    }
    printf("\n");
    return OK;
}

2.5、清空线性表

算法思路:

  • 我们只需要把表的长度置为0即可。
// 初始条件:顺序线性表L已存在
Status ListClear(SqList *L) {
    L->length = 0;
    return OK;
}

2.6、时间复杂度分析

现在我们来分析一下,插入和删除的时间复杂度。

2.6.1、最好情况

如果元素要插入到最后一个位置,或者删除最后一个元素,此时时间复杂度为O(1),因为不需要移动元素的,就如同来了一个新人要正常排队,当然是排在最后,如果此时他又不想排了,那么他一个人离开就好了,不影响任何人。

2.6.2、最坏情况

如果元素要插入到第一个位置或者删除第一个元素,此时时间复杂度是多少呢?那就意味着要移动所有的元素向后或者向前,所以这个时间复杂度为O(n)

2.6.3、平均情况

至于平均的情况,由于元素插入到第i个位置,或删除第i个元素,需要移动n-i个元素。根据概率原理,每个位置插入或删除元素的可能性是相同的,也就说位置靠前,移动元素多,位置靠后,移动元素少。最终平均移动次数和最中间的那个元素的移动次数相等,为\frac{(n-1)}{2}

3、总结

线性表的顺序存储结构,在存、读数据时,不管是哪个位置,时间复杂度都是O(1);而插入或删除时,时间复杂度都是O(n)。这就说明,它比较适合元素个数不太变化,而更多是存取数据的应用。当然,它的优缺点还不只这些……

线性表顺序存储结构的优缺点

image-20200405213036323