2.1顺序表的基本操作和常用算法--C

顺序表的定义：

#define ElemType int

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

初始化表

void InitList(SqList &L){
    L.length = 0;
}

插入操作

// 将元素e插入到顺序表L中第i个位置 
// L: 顺序表
// i: 第i个位置，表示位序，从1开始
// e: 待插入元素 
bool ListInsert(SqList &L, int i, ElemType 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 --){    // 将第i个元素及之后的元素后移 
        L.data[j] = L.data[j - 1];
    }
    L.data[i - 1] = e;      // 在位置i处放入e 
    L.length ++;        // 更新表长 
    return true;
}

image.png

删除操作

// 删除顺序表L中第i个位置的元素 
bool ListDelete(SqList &L, int i, ElemType &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;
} 

按值查找

// 在顺序表L中查找第一个元素值等于e的元素
// 若查找成功，则返回元素位序，否则返回0 
int LocateElem(SqList L, ElemType e){
    int i;
    for(i = 0; i < L.length; i ++){
        if(L.data[i] == e)
            return i + 1;
    }
    return 0;
}

逆置所有元素

// 扫描顺序表L的前半部分元素
// 将其与后半部分对应元素进行交换 
void Reverse(SqList &L){
    for(int i = 0; i < L.length / 2; i ++){
        ElemType temp = L.data[i];
        L.data[i] = L.data[L.length - i - 1];
        L.data[L.length - i - 1] = temp;
    }
}

逆置给定位置元素

// form: 开始转换的下标 0<=from
// to: 结束转换的下标  to<=L.lenth-1
void Reverse(SqList &L,int from, int to){
    for(int i = 0; i < (to - from + 1) / 2; i ++){
        ElemType temp = L.data[from + i];
        L.data[from + i] = L.data[to - i];
        L.data[to - i] = temp;
    }
}

子表位置互换问题L:(a1,a2...am,b1,b2...bn) -> L:(b1,b2...bn,a1,a2...am) T(n)=O(n)

void Converse(SqList &L, int m, int n){
    Reverse(L, 0, m - 1);
    Reverse(L, m, m + n - 1);
    Reverse(L, 0, m + n - 1);
}

删除值为给定值的元素 T(n)=O(n) S(n)=O(1)

void Del_x(SqList &L, ElemType x){
    int k = 0;
    for(int i = 0; i < L.length; i ++){
        if(L.data[i] != x){
            L.data[k] = L.data[i];
            k ++;
        }
    }
    L.length = k;
}

有序去重

bool Delete_Same(SqList &L){
    if(L.length == 0)
        return false;
    int k = 1;
    for(int i = 1; i < L.length; i ++){
        if(L.data[i] != L.data[k - 1]){
            L.data[k] = L.data[i];
            k ++;
        } 
    }
    L.length = k;
    return true;
}

有序合并

bool Merge(SqList A, SqList B, SqList &C){
    if(A.length + B.length > MaxSize)
        return false;
    int i = 0, j = 0, k = 0;
    while(i < A.length && j < B.length){
        if(A.data[i] < B.data[j])
            C.data[k++] = A.data[i++];
        else
            C.data[k++] = B.data[j++];
    }
    while(i < A.length)
        C.data[k++] = A.data[i++];
    while(j < B.length)
        C.data[k++] = B.data[j++];
    C.length = k;
    return true;
}

折半查找

// 在有序顺序表L中查找x，返回x下标 
// 若未找到则返回-1 
int Search(SqList &L, ElemType x){
    int low = 0, high = L.length - 1, mid;
    while(low <= high){
        mid = (low + high) / 2;
        if(L.data[mid] == x)
            return mid;
        else if(L.data[mid] < x)
            low = mid + 1;
        else
            high = mid - 1;
    }
    return -1;
}