Keshawn_lu's Blog

王道数据结构 线性表的顺序表示(课后算法题)

字数统计: 1.6k阅读时长: 7 min
2020/05/03 Share
  1. 从顺序表中删除具有最小值的元素(假设唯一)并由函数返回被删元素的值。空出的位置由最后一个元素填补,若顺序表为空则显示出错信息并退出运行。

    代码如下:

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    #include <iostream>
    #include <vector>
    using namespace std;

    bool EraseMindata(int& value, vector<int> &data) {

    if (data.size() == 0)
    return false;

    value = data[0];
    int pos = 0;

    for (int i = 1; i < data.size(); i++) {

    if (data[i] < value) {

    value = data[i];
    pos = i;
    }
    }

    data[pos] = data[data.size() - 1];
    return true;
    }

    int main()
    {
    vector<int>data = { 1,2,3,4,5 };
    int value;

    EraseMindata(value, data);

    for (int i = 0; i < data.size(); i++) {

    cout << data[i] << " ";
    }

    cout << endl << value;
    }
  2. 设计一个高效算法,将顺序表的所有元素逆置,要求算法的空间复杂度为O(1)。

    思路:将数组一分为二,互相交换即可。

    代码如下:

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    #include <iostream>
    using namespace std;

    void Reverse(int*& data, int size) {

    int temp;

    for (int i = 0; i < size / 2; i++) {

    temp = data[i];
    data[i] = data[size - i - 1];
    data[size - i - 1] = temp;
    }
    }

    int main()
    {
    int* data = new int[5];

    for (int i = 0; i < 5; i++) {
    data[i] = i + 1;
    }

    Reverse(data, 5);

    for (int i = 0; i < 5; i++) {

    cout << data[i] << " ";
    }
    cout << endl;
    }
  3. 对长度为n的顺序表,编写一个时间复杂度为O(n)、空间复杂度为O(1)的算法,该算法删除线性表中所有值为x的数据元素。

    思路:定义一个num,表示不是x的值的数量。每次将不为x的值赋给data[num],即删除了值为x的数据。

    代码如下:

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    #include <iostream>
    using namespace std;

    void DeleteX(int x, int*& data, int &size) {

    int num = 0;
    for (int i = 0; i < size; i++) {

    if (data[i] != x) {

    data[num] = data[i];
    num++;
    }
    }

    size = num;
    }

    int main()
    {
    int size = 5;
    int* data = new int[size];

    for (int i = 0; i < 4; i++) {
    data[i] = 6;
    }
    data[4] = 5;

    DeleteX(6, data, size);

    for (int i = 0; i < size; i++) {

    cout << data[i] << " ";
    }

    cout << endl;

    }
  4. 从有序顺序表中删除其值在给定值s和t之间(要求s < t)的所有元素,如果s或t不合理或顺序表为空,则显示出错信息并退出运行。

    思路:先找出需要删除的区间,再将 > t 的值赋值给data[i](s <= data[i] <= t),即实现前移填补。

    代码如下:

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    #include <iostream>
    using namespace std;

    bool Delete_s_t(int s, int t, int*& data, int& size) {

    //以升序顺序表为例

    if (s >= t || size <= 0)
    return false;


    int i, j;
    for (i = 0; i < size && data[i] < s; i++) {

    }

    if (i >= size)
    return false; //所有值均小于s

    for (j = i; j < size && data[j] <= t; j++) {

    }

    if (j == i)
    return false; //所有值均大于t

    for (; j < size; j++, i++) {

    data[i] = data[j]; //前移,填补被删数据
    }

    size = i;
    return true;
    }

    int main()
    {
    int size = 5;
    int* data = new int[size];

    for (int i = 0; i < 4; i++) {
    data[i] = 5;
    }
    data[4] = 6;

    Delete_s_t(1, 5, data, size);

    for (int i = 0; i < size; i++) {

    cout << data[i] << " ";
    }

    cout << endl;

    }
  5. 从顺序表中删除其值在给定值s与t之间(包含s和t,要求 s < t)的所有元素,如果s或t不合理或顺序表为空,则显示出错信息并退出运行。

    思路:用num来表示在s和t之间的值的个数,遇到不符合要求的元素,将其往前移动num值,即填补删除的元素,遇到符合的元素,即num++。

    代码如下:

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    #include <iostream>
    using namespace std;

    bool Delete_s_t(int s, int t, int*& data, int& size) {

    //非顺序表
    if (s >= t || size <= 0)
    return false;

    int num = 0; //表示在s和t之间的值的个数
    for (int i = 0; i < size; i++) {

    if (data[i] >= s && data[i] <= t)
    num++;
    else
    data[i - num] = data[i]; //将当前元素往前移动num值,即填补删除的元素
    }

    size = size - num;
    return true;
    }

    int main()
    {
    int size = 5;
    int* data = new int[size];

    for (int i = 0; i < 4; i++) {
    data[i] = i + 1;
    }
    data[4] = 0;

    Delete_s_t(0, 2, data, size);

    for (int i = 0; i < size; i++) {

    cout << data[i] << " ";
    }

    cout << endl;
    }
  6. 从有序顺序表中删除所有值重复的元素,使表中所有元素的值均不同。

    思路:与前一题差不多,遇到重复数据,num++,不同数据时,前移填补。

    代码如下:

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    #include <iostream>
    using namespace std;

    void DeleteSame(int*& data, int& size) {

    int same_num = 0;
    for (int i = 1; i < size; i++) {

    if (data[i] == data[i - 1])
    same_num++;
    else
    data[i - same_num] = data[i]; //前移删除相同的数据
    }

    size = size - same_num;
    }

    int main()
    {
    int size = 10;
    int* data = new int[size];

    for (int i = 0; i < 4; i++) {
    data[i] = 3;
    }
    for (int i = 4; i < size - 1; i++) {

    data[i] = i + 1;
    }

    data[size - 1] = 9;

    cout << "删除前:";
    for (int i = 0; i < size; i++) {

    cout << data[i] << " ";
    }

    cout << endl;

    DeleteSame(data, size);

    cout << "删除后:";
    for (int i = 0; i < size; i++) {

    cout << data[i] << " ";
    }

    cout << endl;
    }
  7. 将两个有序顺序表合并为一个新的有序顺序表,并由函数返回结果顺序表。

    思路:每次赋两者小的值,小的表向后移动一位,大的不动,再将有剩余的表赋值即可。

    代码如下:

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    #include <iostream>
    using namespace std;

    void Merge(int*& data1, int& size1, int*& data2, int& size2, int*& res, int& size3) {

    //合并两个升序顺序表
    int i = 0;
    int j = 0;
    size3 = 0;

    while (i < size1 && j < size2) {

    if (data1[i] < data2[j]) {
    res[size3] = data1[i];
    i++;
    }

    else {
    res[size3] = data2[j];
    j++;
    }
    size3++;
    }

    //将剩余的赋值
    if (i < size1) {

    for (int k = size3; i < size1; k++, i++) {

    res[k] = data1[i];
    }
    }
    else if(j < size2) {
    for (int k = size3; j < size2; k++, j++) {

    res[k] = data1[j];
    }
    }

    size3 = size1 + size2;
    }

    int main()
    {
    int size = 5;
    int size2 = size * 2;
    int* data1 = new int[size];
    int* data2 = new int[size];
    int* res = new int[size2];

    for (int i = 0; i < size; i++) {
    data1[i] = i + 1;
    }
    for (int i = 0; i < size; i++) {

    data2[i] = i - 1;
    }

    cout << endl;

    Merge(data1, size, data2, size, res, size2);

    for (int i = 0; i < size2; i++) {

    cout << res[i] << " ";
    }

    cout << endl;
    }
CATALOG