顺序表简述

线性表的顺序存储结构

顺序映象：

  —— 以x的存储位置和y的春初位置之间某种关系表示逻辑关系

最简单的一种顺序映象方式是：

  令 y 的存储位置和 x 的存储位置相邻。用一组==地址连续==的存储单元==依次存放==线性表中的元素。==线性表的起始地址==，称作线性表的基地址。也就是第一个元素。

以“存储位置相邻”表示有序对$$,即：$LOC(a~i~) = LOC(a~i-1~) + C$;

  所有数据元素的存储位置。$LOC(a~i~) = LOC(a~1~) + (i - 1) \times C$,其中LOC(a~1~)就是基地址。

• 存取结构：与存储结构是两个不同的概念。
• 存取结构是在一个数据结构上对查找操作的时间性能的一种描述。

• 通常由两种存取结构；随机存取结构和顺序存取结构。

  • 随机存取结构是指在一个数据结构上进行查找的时间性能是$O(1)$,即查找任意一个数据元素的时间时候相等的，均为常数时间，例如顺序表示一种随机存期结构。
  • 顺序存取结构是指在一个数据结构上进行查找的时间性能是$O(n)$，即查找一个数据元素的时间复杂度是线性的，与该元素在结构中的位置有关，例如单链表是一种顺序存储结构。

顺序映象的C语言描述

#define LISTSIZE 100  //存储空间最大分配量
typedef struct {
    ElemType elem[LISTSZIE];
    int length;  //当前长度
}Sqlist; 
//Sqlist，代表线性表;

• 在线性表的静态分配顺序存储结构中，线性表的最多数据元素个数为LSITSIZE，元素数量不能随意增加，这是以数组方式描述线性表的缺点。

  为了实现线性表最大存储数据元素数可随意变化，可以使用一个动态的数组来取代上面的固定长度数组，如下描述。

线性表的动态分配顺序储存结构：

#define LIST_INIT_SIZE 100  //初始分配量
#define LISTINCREMENT 10 //分配分配增量

typedef struct {
    ElemType *elem;  //储存空间基址
    int length; //当前长度
    int listsize; //当前分配的存储容量
}SqList;// 俗称 顺序表

线性表操作

1.InitList(&L);

  InitList(&L); 的实现是一个加工型的运算，因此，将L设为引用参数，首先动态分配存储空间，然后，将length设置为0，表示表中没有数据元素。

代码实现：

Status InitList_Sq (SqList &L){
    L.elem = (ElemType* )malloc(LIST_INIT_SIZE * sizeof (ElemType));
    if (!L.elem){
        exit (1);//储存分配失败
    }
    L.length = 0;
    L.listsize = LIST_INIT_SIZE;//初始储存容量;
    return OK;
}

2.LocateElme(L,x,compare());

• 线性表中的按置操作是指在线性表中查找与给定值X相等的数据元素。
• 顺序表中完成该运算最简单的方法是：从第一个元素a~1~起依次和X比较，直到找到一个与X相等的数据元素，则返回它在顺序表中的存储下标记或序号(二者差1);或者查遍整个表都没有找到与X相等的元素，返回ERROR。

代码实现：

Status LocateElem_Sq (SqList L, ElemType x){
    int i = 0;
    while (i <= L.length-1 && L.elem[i] != x){
        i++;
    }
    if(i > L.length - 1){
        return ERROR;
    }
    else return i;
}

本算法的主要运算是比较，显然比较的次数与x在表中的位置有关，也与表长有关。当a~1~ = x时，比较一次成功，当a~n~ = x时比较n次成功，按值查找的平均比较次数为 $\frac{(N+1)}{2}$,时间性能为$O(n)$。

3. ListInsert(&L, i, e)

代码实现:

Status ListInsert_Sq (SqList &L, int i, ElemType e){
    //在顺序表L的第i个元素之前插入新的元素e
    //i的合法范围为 1 <=i<=L.length+1
    ElemType *q = &(L.elem[i-1]);//q指示插入位置
    ElemType *p;
    for (p = &(L.elem[L.length-1]); p >= q; --p){
            *(p + 1) = *p;//插入位置及之后的元素右移
            *q = e;//插入e
        ++L.length;//表长增1
    }
}

算法时间复杂度为：$O(ListLength(L))$

if (i < 1 || i > L.length + 1){
    return ERROR;//插入位置不合法
}

if (L.length >= L.listsize){
    return OVERFLOW;//当前存储空间已满
}

考虑移动元素的平均情况：

  假设在第i个元素之前插入的概率为p~i~,则在长度为n的线性表中插入一个元素为所需移动元素次数的期望值为：

$$E_is = \sum_{i = 1}^{n + 1} P_i(n - i + 1)$$

所有为位置的概率的累加和。

  若假定在线性表中任何一个位置上进行插入的概率都是相等的，则移动元素的期望值为：

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

4. ListDelete(&L, i, &e)的实现：

代码实现：

Status LsitDelet_Sq (SqList &L, int i, ElemType &e){
    if((i < 1) || (i > L.length)){
        return ERROR;//删除位置不合法
    }
    p = &(L.elem[i-1]);//p为被删除元素的位置
    e = *p;//被删除元素的值赋给e,可以查看被删元素
    q = L.elem + L.length-1;//表尾元素的位置，基址加上一个整数值
    for (++p; p <= q; ++p){
        *(p-1) = *p;//被删除元素之后的元素左移
        --L.length;//表长减一
    }
    return OK;
}

算法时间复杂度为：$O(ListLength(L))$

考虑移动元素的平均情况：

  假设删除第i个元素的概率为$q_i$,则在长度为$n$的线性表中删除一个元素所需移动元素次数的期望值为：

$$E_dl = \sum_{i=1}^{n}q_i(n-i)$$

  假设定在线性表中任何一个位置上进行删除的概率都是相等的，则移动元素的期望值为：

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