顺序表的插入、删除和查找和代码讲解

顺序表

用顺序存储的方式实现线性表顺序存储，把逻辑上相邻的元素存储在物理位置上也相邻的存储单元中，元素之间的关系由存储单元的邻接关系来体现

计算一个数据元素的大小： C语言中提供的一个函数sizeof(Elem Type) eg:

sizeof(int) = 4B

当然一个结构体的数据元素也可以算出来

typedef struct {
    int num;
    int people;
} Customer


sizeof(Customer) = 8B

顺序表的静态分配

define定义中的MaxSize决定了最大数组的长度，

#define MaxSize 10 //定义最大长度
typedef struct{
    ElemType data[MaxSize]; //用静态的“数组”存放数据元素
    int length //顺序表当前长度
}SqList;  //顺序表的类型定义（静态分配方式）

初始化一个顺序表

void InitList(SqList $L){
    L.length=0;   //顺序表初始长度为0
}

静态的顺序表当被声明后就不容易被修改

顺序表的动态分配

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

c语言中的malloc、free函数分别可以动态的申请和释放内存空间，malloc函数返回一个指针，需要强制转性为你定义的数据元素类型指针；在c++中可以用new、delete这两个关键字来实现

L.data=(ElemType *) malloc(sizeof(ElemType *InitSize))

顺序表的插入

ListInsert($L,i,e):插入操作，在表L中的第i个位置上插入指定元素e

实现的基本思路就是把原L中第i个元素及之后的元素后移

void ListInsert(SqList $L,int i,int e){
    for(int j=L.length;j>=i;j--)
        L.data[j]=L.data[j-1];
    L.data[i-1]=e;
    L.length++;
}

在实现的过程中需要判断i是否是合法的，同时要考虑顺序表的长度。改进后的代码：

void ListInsert(SqList $L,int i,int e){
    if(i<1 || i>L.length+1)  //判断i是否合法
        return false;
    if(L.length>=MaxSize)  //储存空间已满，不能插入
        return false;
    for(int j=L.length;j>=i;j--)
        L.data[j]=L.data[j-1];
    L.data[i-1]=e;
    L.length++;
    return true;
}

时间复杂度：

• 最好情况：新元素插入到表尾，不用移动元素，T（n）= O（1）
• 最坏情况：新元素插入到表头，T（n）= O（n）
• 平均情况：T（n）= O（n）

顺序表的删除

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
    retrun true;
}

时间复杂度：

• 最好情况：删除表尾元素，不用移动元素，T（n）= O（1）
• 最坏情况：删除表头元素，将n+1个元素全部向前移动，T（n）= O（n）
• 平均情况：T（n）= O（n）

顺序表的查找

按位查找

GetElem(L,i)：按位查找操作，获取表L中的第i个位置的元素的值

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

时间复杂度：T(n)=O(n)

按值查找

LocateElem(L,e)：按值查找操作，在表L中查找具有给定关键字值的元素

int LocateElem(SeqList L, ElemType e){
    for(int i=0; i<L.length; i++)
        if(L.data[i]==e)
            return i+1;
    return 0;
}

在顺序表L中查找第一个元素值等于e的元素，并返回其位序，当数组中的下标为i的元素的值等于e的时候，返回位序i+1

时间复杂度：T(n)=O(n)