【数据结构】P5顺序表的插入删除和查找_C

顺序表如何插入

顺序表的插入，如同排队做核酸检测，要是有人插队，那他后面的每一个人都需要往后挪动一个位置，所以由他插队这个行为带来的时间复杂度就是O(n)。

#define MaxSize 10

typedef struct 
{
    int data[MaxSize];
    int length;
}SqList;

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++;
}

int main(){
    SqList L;
    InitList(L);
    ListInsert(L,3,3);
    return 0;
}

顺序表如何删除

顺序表的删除，删除指定位置元素，将该位置后所有元素往前挪动一个位置，所以其时间复杂度也为O(n)。
然而思考删除与插入的区别，插入是将后续序列从最后一个往前以此往后挪一个位置，而删除则是从后续序列的第一个依次往前挪动一个位置。

顺序表如何查找按位查找

按位查找概念是根据提供的表L以及要找到的元素的位置i，找到元素e。

GetElem(L,i);		//按位查找，获取表L中第i个位置的元素的值。

#define MaxSize 10
typedef struct{
	ElemType data[MaxSize];
	int length;
}SqList;

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

时间复杂度：所以顺序表按位查找的时间复杂度为O(1)。

按值查找

按值查找是根据提供的表L以及要找到的元素的值e，找到满足条件的元素的位置i+1。

typedef struct
{
    int *data;
    int MaxSize;
    int length;
}SeqList;

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