数据结构之线性表

发表于 | 分类于

线性表之顺序表

插入元素

在第i（1<=i<=n）个元素前插入一个元素,插入元素时，需要先将最后边的元素向后移一个位置，依次类推（共n-i+1个）

  • 1—— 指针法：
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    Status ListInsert_sq(SqList &L,int i, ElemType e){
        // 合法性
        if(i<1||i>L.length+1) return ERROR;
        //当前存储空间已满时，追加(重新分配)存储空间
        if(L.length>=L.listsize){
            newbase=(ElemType *)realloc(L.elem,      //  L.elem 表示原表地址
                                    (L.listsize+LISTNCREMENT)* sizeof(ElemType));
            if(!newbase)exit(OVERFLOW);
            L.elem=newbase;   //将新分配的地址赋值给L.elem
            L.listsize+=LISTINCREMENT;
        }
        // 第i个元素的下标为'i-1', 'L.elem[i-1]'表示第i 个元素,'&(L.elem[i-1])'表示第i个元素的地址
        q = &(L.elem[i-1]);         //q为插入位置
        // 'L.elem[L.length-1]'中'L.length-1'表示最后一个元素的下标，则L.elem[L.length-1]表示最后一个元素
        for(p=&(L.elem[L.length-1]); p>=q; --p;)    //p为最后一个元素的地址
            * (p+1) = * p;       //将元素向后移动
        * q=e;   //插入e
        ++L.length;    //表长增1
        return OK;
    }
  • 2—— 下标法：
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    Status ListInsert_sq(SqList &L,int i, ElemType e){
        // 合法性
        if(i<1||i>L.length+1) return ERROR;
        //当前存储空间已满时，追加(重新分配)存储空间
        if(L.length>=L.listsize){
            newbase=(ElemType *)realloc(L.elem,      //  L.elem 表示原表地址
                                    (L.listsize+LISTNCREMENT)* sizeof(ElemType));
            if(!newbase)exit(OVERFLOW);
            L.elem=newbase;      //将新分配的地址赋值给L.elem
            L.listsize+=LISTINCREMENT;
        }
        // 第i个元素的下标为'i-1', 'L.elem[i-1]'表示第i 个元素,'&(L.elem[i-1])'表示第i个元素的地址
        q = &(L.elem[i-1]);         //q为插入位置
        // j为下标，L.length-1 为最后一个元素的下标，从表最后一个元素循环到第i个元素
        for(j=L.length-1;j>=i-1;j++)
            L.elem[j+1]=L.elem[j];    //将元素向后移动一个位置
        * q=e;   //插入e
        ++L.length;    //表长增1
        return OK;