数据结构--线性表的顺序表示（1~5）

线性表的顺序存储类型为：

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

1 . 从顺序表中删除具有最小值的元素（假设唯一）并由函数返回被删除元素的值，空出的位置由最后一个元素填补，若顺序表为空则显示出错信息并退出。

• 算法思想：记录最小元素所在的位置，搜索结束后将最后一个元素赋予最小元素所在的位置。

bool Del_Min(SqList &L,int &value)
{
    if (L.length == 0)
        return false;

    value = L.data[0];
    int pos = 0;
    for (int i = 1; i < L.length; i++)
    {
        if (L.data[i] < value)
        {
            value = L.data[i];
            pos = i;
        }
    }
    L.data[pos] = L.data[L.length - 1];
    L.length--;

    return true;
}

2 . 设计一个高效的算法，将顺序表中所有元素逆置，要求算法的空间复杂度为O(1)。

• 算法思想：用循环将第i个元素和第length-1-i个元素的值交换。

void Reverse(SqList &L)
{
    int temp;
    for (int i = 0; i <= L.length/2; i++)
    {
        temp = L.data[i];
        L.data[i] = L.data[L.length-1-i];
        L.data[L.length - 1 - i] = temp;
    }
}

开始犯了一个很严重的错误：L.data={1,2,3,4,5,6,7,8,9};
error C2440: “=”: 无法从“initializer-list”转换为“int”
百度了一下：只有定义时才可以用花括号扩起来的列表进行初始化。
定义变量int L[10] = {1,2,3,4,5,6,7,8,9};实际上是先分配10个内存，同时将内存初始化。而定义SqList L;实际上是先分配sizof(SqList)个内存，然后调用默认构造函数初始化LL.data={1,2,3,4,5,6,7,8,9};编译通不过是因为L已经初始化了,不能再初始化一次了。

int main()
{
    SqList A;
    A.length = 10;
    for (int i = 0; i<A.length; i++)
        A.data[i] = i;

    Reverse(A);
    for (int i = 0; i < A.length; i++)
    {
        cout << A.data[i]<<" ";
    }

    return 0;
}

3 . 长度为n的顺序表L。编写一个时间复杂度为O(n)，空间复杂度为O(1)的算法该算法删除线性表中所有值为x的元素。

• 算法思想：用count记录表A中等于x的元素个数，将不等于x的向前移动count个位置。

void Del_X(SqList &L, int x)
{
    int count = 0, i = 0;
    while (i < L.length)
    {
        if (L.data[i] == x)
        {
            count++;
        }
        else
        {
            L.data[i - count] = L.data[i];
        }
        i++;
    }

    L.length -= count;
}

4 .从有序顺序表中删除其值在给定值s与t之间（要求s小于t）的所有元素，如果s或t不合理或者顺序表为空则显示出错误信息并退出运行。

• 算法思想：只需要在上一题的思路上稍加改进就可以了，因为是有序表所以可以直接找到与s值相同的第一个元素和与t相同的最后一个元素，直接删除一整块。

bool Del_S_T(SqList &L, int x, int t)
{
    int pos1, pos2;
    if (x > t)
        return false;
    int i = 0;
    while (i < L.length)
    {
        if (L.data[i] >= x&&L.data[i] < t)
        {
            pos1 = i;
            break;
        }
        i++;
    }
    while (i < L.length)
    {
        if (L.data[i + 1]>t)
        {
            pos2 = i + 1;
            break;
        }
        i++;
    }
    while (pos2 < L.length)
    {
        L.data[pos1++] = L.data[pos2++];
    }

    L.length = L.length - pos2 + pos1;

    return true;
}

5 .从顺序表中删除所有其值在给定值s与t之间的元素（包含s与t，要求s小于t）的所有元素，如果s与t不合理或者顺序表为空则显示错误信息并退出。

• 算法思想：跟上一题思路一样，上一题同样也可以用这个思路来做。

bool Del_S_T_Du(SqList &L, int x, int t)
{
    if (x > t)
        return false;
    int count = 0, i = 0;
    while (i < L.length)
    {
        if (L.data[i] >= x&&L.data[i] <= t)
        {
            count++;
        }
        else
        {
            L.data[i - count] = L.data[i];
        }
        i++;
    }

    L.length -= count;

    return true;
}

完整的代码贴在：https://github.com/shuailishasls/git_share/tree/master/linear_list_question_1-5