线性表(一)——顺序表

2020-01-19 本文已影响0人风紧扯呼

在前一篇文章中我们讲解了线性表的定义以及线性表的特性，知道了线性表的两种存储结构：一种是顺序存储结构，一中是链式存储结构。本文将分析讨论线性表顺序存储结构的实现。

线性表-概述
 线性表(一)——顺序表
 线性表(二)——单链表的表示和实现
 线性表(三)——双向链表的表示和实现

1、顺序表的存储结构

顺序表是线性表中的一种，顺序存储结构的线性表称作顺序表。实现顺序存储结构的方式是使用数组。数组把线性表的数据元素存储在一块连续地址空间的内存单元中，这样线性表中逻辑相邻的数据元素在物理存储地址上也是相邻的。数组有静态数组和动态数组两种，不同之处在于前者的存储空间的申请和释放是由系统自动完成的，后者的存储空间的申请和释放是由用户通过调用系统函数自己完成的。不管是静态数组还是动态数组，其功能都是向系统申请一块连续地址的有限空间，只是申请空间的方式不同而已。本文主要讨论静态数组方法实现的顺序表。
如下图所示是顺序表的存储结构示意图。其中 $a_0,a_1,a_2,···a_{MaxSize-1}$ 表示顺序表中存储的数据元素，list表示用于存储顺序表数据元素的数组，MaxSize表示数组list的最大存储个数，size表示顺序表当前存储数据元素的个数。

用C语言描述上图所示的结构，定义如下：

typedef struct {
    DateType list[MaxSize];
    int size;
}SeqList;

其中DateType表示数据元素的数据类型，MaxSize表示数组的最大容量，list表示顺序表的数组成员，size表示顺序表中当前存储的数据元素的个数，且必须满足size $\leq$ MaxSize。

2、顺序表的操作实现

2.1 初始化ListInitiate(L)

/*初始化列表*/
void ListInitiate(SeqList *L) {
    L->size = 0;
}

2.2 获取顺序表长度ListLength(L)

/*获取列表的长度*/
int ListLength(SeqList L) {
    return L.size;
}

2.3 插入数据ListInsert(L,index,x)

在顺序表L的第index（0 $\leq index \leq size$ ）个位置前插入数据元素值x，插入成功返回1，插入失败返回0。

/*
 * 插入元素
 * */
int ListInsert(SeqList *L, int index, DataType x) {
    if (L->size >= MaxSize) {
        printf("顺序表结构数据已满");
        return 0;
    } else if (index < 0 || index > L->size) {
        printf("插入数据的位置不合法");
        return 0;
    } else {
//        从后向前依次后移数据，为插入数据做准备
        for (int i = L->size; i > index; i--) {
            L->list[i] = L->list[i - 1];
        }
        L->list[index] = x;//插入x
        L->size++;//元素的个数添加1
        return 1;
    }
}

从上面的程序看，在index正确的前提下，首先把存储单元size-1至存储单元为index中的数据元素依次后移，然后把数据元素x插入到存储单元index中，最后把数据元素个数加1。这个操作称做是前插入，即在顺序表的第index个位置前插入数据元素，还可以有后插入操作，即在顺序表的第index个位置后插入数据元素。

2.4 删除数据ListDelete(L,index,x)

删除顺序表L的第index（0 $\leq index \leq size-1$ ）个位置上的数据元素并保存到x中，删除成功返回1，删除失败返回0。

int ListDelete(SeqLsit *L, int index, DataType *x) {

    if (L->size <= 0) {
        printf("顺序表中已经没有可以删除的元素");
        return 0;
    } else if (index < 0 || index > L->size - 1) {
        printf("删除数据的位置不合法");
        return 0;
    } else {
        *x = L->list[index];
        for (int i = index + 1; i <= L->size - 1; i++) {
            L->list[i - 1] = L->list[I];
        }
        L->size--;
        return 1;
    }
}

当顺序表非空且参数index正确时，首先把存储单元index中的数据元素存放到x中，然后从前向后依次千亿从存储位置index到存储位置size-1中的数据元素，最后把数据元素个数减1。

2.5 取数据元素ListGet(L,index,x)

取顺序表L中第index个数据元素存与x中，成功返回1，失败返回0。

int ListGet(SeqLsit *L, int index, DataType *x) {
    if (index < 0 || index > L->size - 1) {
        printf("数据的位置不合法");
        return 0;
    } else {
        *x = L->list[index];
        return 1;
    }
}

2、顺序表的操作效率

从上面的分析来看，顺序表的插入和删除是顺序表中时间复杂度最高的操作。在顺序表中插入一个数据元素时，算法中时间复杂度最高的操作是循环移动数据元素。循环移动数据元素的效率和插入数据元素位置i有关，最坏情况是i=0，需移动size个数据元素；最好的情况是i=size，需要移动0个数据元素。设 $P_i$ 是在第i个位置插入一个数据元素的概率，设顺序表中的数据元素个数为n，当顺序表的任何位置上插入数据元素的概率相等时，有 $P_i=1/(n+1)$ ，则像顺序表插入一个数据元素需要移动的数据元素的平均次数为：
$E_{is} = \sum\limits_{i=0}^n P_{i}(n-i) = \frac{1}{n+1} \sum\limits_{i=0}^n (n-i) = \frac{n}{2}$

从顺序表中删除一个数据元素时，算法中时间复杂度最高的操作也是循环移动数据元素。循环移动数据元素的效率与删除数据元素的位置i有关，最坏的情况是i=0，需要移动size-1个数据元素；最好的情况是i=size，需要移动0个数据元素。设 $q_i$ 是删除第i个位置数据元素的概率，设顺序表的数据元素个数为n，当删除顺序表任何位置上数据元素的概率相等时，有 $q_i=1/n$ ，则删除顺序表任意位置数据元素所需要移动数据元素的平均次数为：
$E_{dl} = \sum\limits_{i=0}^{n-1} q_{i}(n-i) = \frac{1}{n} \sum\limits_{i=0}^{n-1} (n-i) = \frac{n-1}{2}$

根据上面的分析可知，在顺序表中插入和删除一个数据元素的平均时间复杂度为O(n)。
顺序表的其他操作与数据元素的个数n无关，所以顺序表的查询元素和获取元素的时间复杂度为O(1)。
顺序表的主要优点是：算法简单，内存单元利用率较高。主要缺点是：需要预先确定数据元素的最大个数。