王道数据结构编程题(顺序表)

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

输入样例:
5
3 4 1 6 7
6
5 2 7 9 3 6
0

输出样例:
1
3 4 6 7
2
5 6 7 9 3
error

#include <stdio.h>

#define MAX_SIZE 100

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

void ListPrint(SqList L);

int ListDelete(SqList *L);

int main() {
    SqList L;

    while (scanf("%d", &L.length) && L.length!= 0) {
        for (int i = 0; i < L.length; i++) {
            scanf("%d", &(L.data[i]));
        }
        printf("%d\n", ListDelete(&L));
        ListPrint(L);
    }
    printf("error");
    return 0;
}

void ListPrint(SqList L) {
    for (int i = 0; i < L.length; i++) {
        printf("%d%c", L.data[i], (i == L.length - 1) ? 10 : 32);
    }
}

int ListDelete(SqList *L) {
    int min_pos = 0, min_val = 0;

    for (int i = 0; i < L->length; i++) {
        if (L->data[i] < L->data[min_pos]) min_pos = i;
    }
    min_val = L->data[min_pos];
    L->data[min_pos] = L->data[L->length - 1];
    L->length--;
    return min_val;
}

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

输入样例:
5
3 4 1 6 7
6
5 2 7 9 3 6
0

输出样例:
7 6 1 4 3
6 3 9 7 2 5

#include <stdio.h>

#define MAX_SIZE 100

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

void ListPrint(SqList L);

void ListInvert(SqList *L);

int main() {
    SqList L;

    while (scanf("%d", &L.length) && L.length!= 0) {
        for (int i = 0; i < L.length; i++) {
            scanf("%d", &(L.data[i]));
        }
        ListInvert(&L);
        ListPrint(L);
    }
    return 0;
}

void ListPrint(SqList L) {
    for (int i = 0; i < L.length; i++) {
        printf("%d%c", L.data[i], (i == L.length - 1) ? 10 : 32);
    }
}

void ListInvert(SqList *L) {
    for (int i = 0; i < L->length / 2; i++) {
        L->data[i] = L->data[i] + L->data[L->length - i - 1];
        L->data[L->length - i - 1] = L->data[i] - L->data[L->length - i - 1];
        L->data[i] = L->data[i] - L->data[L->length - i - 1];
    }
}

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

输入样例:
5
3 5 8 3 1
3
5
3 5 8 3 1
8
0

输出样例:
5 8 1
3 5 3 1

#include <stdio.h>

#define MAX_SIZE 100

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

void ListPrint(SqList L);

void ListDelete(SqList *L, int x);

void ListDelete_(SqList *L, int x);

int main() {
    SqList L;

    while (scanf("%d", &L.length) && L.length!= 0) {
        int x;

        for (int i = 0; i < L.length; i++) {
            scanf("%d", &(L.data[i]));
        }
        scanf("%d", &x);
        ListDelete(&L, x);
        /*ListDelete_(&L, x);*/
        ListPrint(L);
    }
    return 0;
}

void ListPrint(SqList L) {
    for (int i = 0; i < L.length; i++) {
        printf("%d%c", L.data[i], (i == L.length - 1) ? 10 : 32);
    }
}

void ListDelete(SqList *L, int x) {
    int cursor = 0, offset = 0;//offset记录等于x的元素的个数

    while (cursor + offset < L->length) {
        if (L->data[cursor + offset] == x) {
            offset++;
        } else {
            L->data[cursor] = L->data[cursor + offset];//将当前不等于x的元素向前偏移offset
            cursor++;
        };
    }
    L->length -= offset;//更新顺序表长度
}

void ListDelete_(SqList *L, int x) {
    int slow = 0;

    for (int fast = 0; fast < L->length; fast++) {
        if (L->data[fast] != x) {
            L->data[slow] = L->data[fast];
            slow++;
        }
    }
    L->length = slow;//更新顺序表长度
}

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

输入样例:
5
1 2 3 4 5
2 4
6
5 6 7 8 9 10
8 10
0

输出样例:
1 5
5 6 7
error

#include <stdio.h>

#define MAX_SIZE 100

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

void ListPrint(SqList L);

void ListDelete(SqList *L, int s, int t);

int main() {
    SqList L;

    while (scanf("%d", &L.length) && L.length!= 0) {
        int s, t;

        for (int i = 0; i < L.length; i++) {
            scanf("%d", &(L.data[i]));
        }
        scanf("%d %d", &s, &t);
        if (s >= t) break;
        ListDelete(&L, s, t);
        ListPrint(L);
    }
    printf("error");
    return 0;
}

void ListPrint(SqList L) {
    for (int i = 0; i < L.length; i++) {
        printf("%d%c", L.data[i], (i == L.length - 1) ? 10 : 32);
    }
}

void ListDelete(SqList *L, int s, int t) {
    int slow = 0;

    for (int fast = 0; fast < L->length; fast++) {
        if (L->data[fast] < s || L->data[fast] > t) {
            L->data[slow] = L->data[fast];
            slow++;
        }
    }
    L->length = slow;
}

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

输入样例:
5
3 4 1 6 7
4 6
6
5 2 7 9 3 6
7 9
0

输出样例:
3 1 7
5 2 3 6

#include <stdio.h>

#define MAX_SIZE 100

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

void ListPrint(SqList L);

void ListDelete(SqList *L, int s, int t);

int main() {
    SqList L;

    while (scanf("%d", &L.length) && L.length!= 0) {
        int s, t;

        for (int i = 0; i < L.length; i++) {
            scanf("%d", &(L.data[i]));
        }
        scanf("%d %d", &s, &t);
        if (s >= t) break;
        ListDelete(&L, s, t);
        ListPrint(L);
    }
    printf("error");
    return 0;
}

void ListPrint(SqList L) {
    for (int i = 0; i < L.length; i++) {
        printf("%d%c", L.data[i], (i == L.length - 1) ? 10 : 32);
    }
}

void ListDelete(SqList *L, int s, int t) {
    int slow = 0;

    for (int fast = 0; fast < L->length; fast++) {
        if (L->data[fast] < s || L->data[fast] > t) {
            L->data[slow] = L->data[fast];
            slow++;
        }
    }
    L->length = slow;
}

6.从有序表中删除所有其值重复的元素,使表中所有元素的值均不同。

输入样例:
5
1 2 2 2 3
10
1 2 2 2 3 4 4 4 5 5 

输出样例:
1 2 3
1 2 3 4 5

#include <stdio.h>

#define MAX_SIZE 10

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

void ListPrint(SqList L);

void ListDelete(SqList *L);

void ListDelete_(SqList *L);

int main() {
    SqList L;

    while (scanf("%d", &L.length) && L.length!= 0) {
        for (int i = 0; i < L.length; i++) {
            scanf("%d", &(L.data[i]));
        }
        ListDelete(&L);
        /*ListDelete_(&L);*/
        ListPrint(L);
    }
    printf("error");
    return 0;
}

void ListPrint(SqList L) {
    for (int i = 0; i < L.length; i++) {
        printf("%d%c", L.data[i], (i == L.length - 1) ? 10 : 32);
    }
}
/*对有序表和无序表都适用*/
void ListDelete(SqList *L) {
    for (int i = 0; i < L->length; i++) {
        int same = 0;//重复元素的个数
        /*将当前元素与后面的所有元素进行比较*/
        for (int j = i + 1; j < L->length; j++) {
            if (L->data[i] == L->data[j]) {
                same++;
            } else {
                L->data[j - same] = L->data[j];
            }
        }
        L->length -= same;
    }
}
/*只能处理有序表*/
void ListDelete_(SqList *L) {
    int slow = 0, fast = 0;

    while (fast < L->length) {
        while (L->data[fast] == L->data[fast + 1]) {
            fast++;
        }
        L->data[slow++] = L->data[fast++];
    }
    L->length = slow;
}

7.将两个有序顺序表合并为一个新的有序顺序表。

输入样例:
3 4
1 3 5
2 4 6 8
0 0

输出样例:
1 2 3 4 5 6 8

#include <stdio.h>

#define MAX_SIZE 10

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

void ListPrint(SqList L);

void ListMerge(SqList A, SqList B, SqList *L);

int main() {
    SqList A;
    SqList B;

    while (scanf("%d %d", &A.length, &B.length) && A.length != 0 && B.length != 0) {
        SqList L;

        L.length = 0;
        for (int i = 0; i < A.length; i++) {
            scanf("%d", &(A.data[i]));
        }
        for (int i = 0; i < B.length; i++) {
            scanf("%d", &(B.data[i]));
        }
        ListMerge(A, B, &L);
        ListPrint(L);
    }
    return 0;
}

void ListPrint(SqList L) {
    for (int i = 0; i < L.length; i++) {
        printf("%d%c", L.data[i], (i == L.length - 1) ? 10 : 32);
    }
}

void ListMerge(SqList A, SqList B, SqList *L) {
    int cur_a = 0, cur_b = 0, cursor = 0;

    while (cur_a < A.length && cur_b < B.length) {
        if (A.data[cur_a] < B.data[cur_b]) {
            L->data[cursor++] = A.data[cur_a++];
            L->length++;
        } else {
            L->data[cursor++] = B.data[cur_b++];
            L->length++;
        }
    }
    while (cur_a < A.length) {
        L->data[cursor++] = A.data[cur_a++];
        L->length++;
    }
    while (cur_b < B.length) {
        L->data[cursor++] = B.data[cur_b++];
        L->length++;
    }
}

8.已知在一维数组A[m+n]中依次存放两个线性表 ( a 1 , a 2 , a 3 , … a m ) (a_1, a_2, a_3, \dots a_m) (a1​,a2​,a3​,…am​)和 ( b 1 , b 2 , b 3 , … b n ) (b_1, b_2, b_3, \dots b_n) (b1​,b2​,b3​,…bn​)。试编写一个函数,将数组中两个顺序表的位置互换,即将 ( b 1 , b 2 , b 3 , … b n ) (b_1, b_2, b_3, \dots b_n) (b1​,b2​,b3​,…bn​)放在 ( a 1 , a 2 , a 3 , … a m ) (a_1, a_2, a_3, \dots a_m) (a1​,a2​,a3​,…am​)前面。

输入样例:
2 3
1 2 3 4 5
3 4
1 2 3 4 5 6 7
0 0

输出样例:
3 4 5 1 2
4 5 6 7 1 2


9.

输入样例:
5
3 4 1 6 7
6
5 2 7 9 3 6
0

输出样例:



10.

输入样例:
5
3 4 1 6 7
6
5 2 7 9 3 6
0

输出样例:



11.

输入样例:
5
3 4 1 6 7
6
5 2 7 9 3 6
0

输出样例:



12.

输入样例:
5
3 4 1 6 7
6
5 2 7 9 3 6
0

输出样例:



13.

输入样例:
5
3 4 1 6 7
6
5 2 7 9 3 6
0

输出样例:



14.

输入样例:
5
3 4 1 6 7
6
5 2 7 9 3 6
0

输出样例:



上一篇:八皇后问题(递归)


下一篇:【专题复习4:Dijkstra】1003、1018、1030、1072、1087、1111