[数据结构与算法]【C/C++版】王道数据结构代码题——线性表部分持续更新

一、顺序表

/*
 * 2.1 删除最小元素，并用最后一个元素填充
 */
void delete_min(sqlList &L, ElemType &e) {
    //顺序表为空时，输出错误信息
    if (L.length == 0) {
        cout << "error!" << endl;
        e = -1;
        return;
    }
    /*
     * min:最小值
     * min_i:最小值对应下标
     */
    int min = L.data[0];
    int min_i = 0;
    //找最小值
    for (int i = 0; i < L.length; i++) {
        if (L.data[i] <= min) {
            min = L.data[i];
            min_i = i;
        }
    }
    //返回最小值
    e = min;
    //删除最小值，最小值位置用最后一个元素填充
    L.data[min_i] = L.data[L.length - 1];
    L.length--;
}

/*
 * 2.2
 */
void list_reverse(sqlList &L) {
    if (L.length == 0)
        return;
    int *p = L.data;
    int *q = L.data + L.length - 1;
    while (p <= q) {
        swap(*p, *q);
        p++;
        q--;
    }
}

/*
 * 2.3
 */
//此问题有三种其他解法
//※※双指针法解决移除所有值为e的元素
void delete_e(sqlList &L, ElemType e)
{
    if (L.length == 0)
        return;
    int slowIndex = 0;
    for (int fastIndex = 0; fastIndex < L.length; fastIndex++)
    {
        if (e != L.data[fastIndex])
            L.data[slowIndex++] = L.data[fastIndex];
    }
    L.length = slowIndex;
}

//2.3答案写法
void List_delete2(sqlList &L, ElemType e)
{
    int k = 0;
    for(int i = 0; i < L.length; i++)
        if(e != L.data[i])
        {
            L.data[k] = L.data[i];
            k++;
        }
    L.length = k;
}

void List_delete3(sqlList &L, ElemType e)
{
    int k = 0;
    int i = 0;
    while(i < L.length)
    {
        if(e == L.data[i])
            k++;
        else
            L.data[i - k] = L.data[i];
    }
    L.length = L.length - k;
}

//2.3自创方法
//时间复杂度:O(n)
//空间复杂度:O(1)
//优点:可以将重复元素全部换到最后
void List_delete1(sqlList &L, ElemType e)
{
    int i=0;
    int j=1;
    if(0 == L.length)
        return;
    while(j < L.length)
    {
        if(e == L.data[i])
        {
            if(e == L.data[j])
                j++;
            else
            {
                swap(L.data[i],L.data[j]);
                i++;
                j = i + 1;
            }
        }
        else
        {
            i++;
            j=i+1;
        }
    }
    L.length = i;
}

/*
 * 2.4,2.5
 * 这种做法对有序表和顺序表都适用
 * 有序表的做法会更简便
 */
void delete_st(sqlList &L, ElemType s, ElemType t)
{
    int i=0;
    int j=1;
    if(0 == L.length || s > t)
        return;
    while(j < L.length)
    {
        if(L.data[i] > s && L.data[i] < t)
        {
            if(L.data[j] > s && L.data[i] < t)
                j++;
            else
            {
                swap(L.data[i],L.data[j]);
                i++;
                j = i + 1;
            }
        }
        else
        {
            i++;
            j=i+1;
        }
    }
    L.length = i;
}

/*
 * 2.6
 */
//答案做法
void List_6(sqlList &L)
{
    if(0 == L.length)
        return;
    int i, j;
    for(i = 0, j = 1; j < L.length; j++)
        if(L.data[i] != L.data[j])
            L.data[++i] = L.data[j];
    L.length = i + 1;
}