数据结构顺序表

顺序表定义

1，前言

线性表的顺序存储又称为顺序表。它是用一组地址连续的存储单元依次存储线性表中的数据元素，从而使得逻辑上相邻的两个元素在物理位置上也相邻。其最大的特点就是：元素的逻辑顺序与其物理顺序相同。

线性表的顺序存储结构中任一元素都可以随机存取，并且注意：线性表中元素的位序是从1 开始的，而数组中元素的下标是从0 开始的。假定线性表的元素类型为 EleType ，则线性表的顺序存储类型可以描述为：

#define MaxSize 50	//定义线性表的最大长度
typedef struct {
    ElemType data[MaxSize];	//顺序表的元素
    int length;	//顺序表的当前长度
}SqList；	//顺序表的类型定义

2，动态实现

1，结构定义：

#define InitSize 10	//默认的最大长度
typedef struct{
    int *data;		//指示动态分配数组的指针
    int MaxSize;	//顺序表的最大容量
    int length;		//顺序表的当前长度
}SeqList；

2，初始化顺序表：

void InitList(SeqList &L){
    //用malloc函数申请一片连续的存储空间
    L.data=(int *)malloc(InitSize*sizeof(int));
    L.length=0;
    L.MaxSize=InitSize;
}

3，增加动态数组的长度：

void IncreaseSize(SeqList &L,int len){
    int *p=L.data;
    L.data=(int *)malloc((L.MaxSize+len)*sizeof(int));
    for(int i=0;i<L.length;i++)
        L.data[i]=p[i];		//将数据复制到新区域，时间开销很大
    L.MaxSize=L.MaxSize+len;	//顺序表最大长度增加len
    free(p);			//释放原来的内存空间
}

顺序表上的基本操作

1，插入操作（Listsert(&L,i,e)

在表L 中的第i 个位置上插入指定元素e 。以下采用的是“静态分配的方式实现。

以下给出实现的主要代码部分，便于我们阅读理解：

#define MaxSize 10	//定义线性表的最大长度
typedef struct {
    int data[MaxSize];	//用静态的“数组”存放数据元素
    int length;	//顺序表的当前长度
}SqList；	//顺序表的类型定义
    
bool ListInsert(Sqlist &L,int i,int e){
    if(i<1||i>L.length+1)
        return false;
    if(L.length>=MaxSize)   //当前存储空间已满，不能插入
        return false;
    for(int j=L.length;j>=i;j--)    //将第i个元素及其后的元素后移
        L.data[j]=L.data[j-1];
    L.data[i-1]=e;  //在位置i处放入e
    L.length++; //线性表的长度加1
    return true;
    
int main(){
    SqList L;	//声明一个顺序表
    InitList(L);	//初始化顺序表
    //...此处省略插入几个元素的代码
    ListInsert(L,3,3);
    return 0;
}

插入操作的时间复杂度分析：

通过观察以上代码，我们分析时间复杂度时只需要关注最深层循环语句的执行次数与问题规模n 的关系。即语句“L.data[j]=L.data[j-1];”即可：

• 最好情况：新元素插入到表位，不需要移动元素，i=n+1，循环0次；最好的时间复杂度为O(1)
• 最坏情况：新元素插入到表头，需要将原有的n 个元素全都向后移动，i =1，循环n 次；最坏的时间复杂度为O(n);
• 平均情况：假设新元素插入到任何一个位置的概率相同，概率为P=1/(n+1)。i=1，循环n 次；i =2 时，循环n-1次；i =3 ，循环n-2 次 ..... i =n+1 时，循环0 次。平均循环次数 =np+(n-1)p+(n-2)p+.....+1.p= n/2。即得平均时间复杂度= O(n)

提示：如果以上的分析i 的值和循环次数n 的关系不是太清楚，要回想下开头提到的线性表中元素的位序是从1 开始的，而数组中元素的下标是从0 开始的。

2，删除操作（ListDelete(SqList &L,int i,int &e)）

删除顺序表L 中的第i （1<=i<=L.length)个位置的元素，用引用变量e 返回。若输入的i 不合法，则返回false ；否则，将被删元素赋给引用变量e ，并将第i+1 个元素及其后的所有元素一次往前移动一个位置，返回true 。

下面给出部分代码，辅助我们理解阅读：

bool ListDelete(SqList &L,int i,int &e){
    if(i<1||i>L.length)	//判断i的范围是否有效
        return false；
     e=L.data[i-1];	//将删除元素赋给引用变量e
    for(int j=i;j<L.length;j++)	//将第i个位置后的元素前移
        L.data[j-1]=L.data[j];//这里再次提醒位序与数组下标的关系
    L.length--;	//线性表长度减1
    return true;
}

int main(){
    SqList L;	//声明一个顺序表
    InitList(L);	//初始化
    //.....省略一些代码
    int e=-1;	//用标量e将删除的变量“带回来”
    if(ListDelete(L,3,3))
        printf("已删除第3个元素，删除元素值为=%d\n",e);//试一下
    else
        printf("位序i不合法，删除失败\n");
    return 0;
}

删除操作的是时间复杂度分析：

通过观察以上代码，我们分析时间复杂度时只需要关注最深层循环语句的执行次数与问题规模n 的关系。即语句“L.data[j-1]=L.data[j];”即可：

• 最好情况：删除元素，不需要移动其他元素，i=n，循环0次；最好的时间复杂度为O(1)
• 最坏情况：删除表头元素，需要将后续的n-1个元素全都向前移动。i=1，循环n-1次；最坏时间复杂度= O(n)
• 平均情况：假设删除任何一个元素的概率相同，及p=1/n，i=1，循环n-1次；i=2，循环n-2 次..... i=n 时，循环0次，故平均循环次数=(n-1)p+(n-2)p+.....+1.p=(n-1)/2.则时间复杂度为O(n)

3，按位查找（GetElem(L,i)）

获取表L 中第i 个位置的元素的值。下面给出一段简单的代码示例：

#define InitSize 10	//顺序表的初始长度
typedef struct{
    ElemType *data;	//指示动态分配数组的指针
    int MaxSize;	//顺序表中的最大容量
    int length;	//顺序表的当前长度
}SeqList;		//顺序表的类型的定义（动态分配方式）

ElemType GetElem(SeqList L,int i){
    return L.data[i-1];
}

由于顺序表的各个元素在内存中连续存放，因此可以根据起始地址和数据元素大小立即找到第i 个元素，这也就是 随机存取特性的体现。因此其时间复杂度可得为 O(1)。

4，按值查找（LocateElem( L, e) ）

在表L 中查找具有给定关键字的元素。如下给出在顺序表L 中查找第一个元素值等于e 的元素，并返回其位序：

int LocateElem(SeqList L,ElemType e){
    for(int i=0;i<L.length;i++)
        if(L.data[i]==e)
            return i+1;	//注意数组下标与顺序表位序的关系
    return 0;	//退出循环，说明查找失败
}

对于时间复杂度的分析：

通过观察以上代码，我们分析时间复杂度时只需要关注最深层循环语句的执行次数与问题规模n 的关系。即语句“ if(L.data[i]==e ”即可：

• 最好情况：目标元素在表头，循环1次；最好时间复杂度为O(1)
• 最坏情况：目标元素在表尾，循环n 次；最坏时间复杂度为O(n);
• 平均情况：假设目标元素出现在任何一个位置的概率相同，都是1/n，目标元素在第一位，循环1次；第2位，循环2次；....... 在第n 为，循环n 次，则平均循环次数 =1\n+2.1/n+....+n.1/n=(n+1)/2；则平均时间复杂度为O(n)。

关于顺序表的一些知识先就说这么多，共勉！