【数据结构】一般线性表

代码会在结束后更新，题都很简单，恶心的一点是不给数据范围让用户自己试。

函数题#

带头结点的链式表操作集#

1
List MakeEmpty() {
2
    return malloc(sizeof(struct LNode));
3
}
4

5
Position Find( List L, ElementType X ) {
6
    while (L) {
7
        if (L->Data == X) return L;
8
        L = L->Next;
9
    }
10
    return ERROR;
11
}
12

13
bool Insert( List L, ElementType X, Position P ) {
14
    while (L && L->Next != P) {
15
        L = L->Next;
16
    }
17
    if (!L) {
18
        printf("Wrong Position for Insertion\n");
19
        return false;
20
    }
21
    List t = malloc(sizeof(struct LNode));
22
    t->Data = X;
23
    t->Next = L->Next, L->Next = t;
24
    return true;
25
}
26

27
bool Delete( List L, Position P ) {
28
    if (!P) {
29
        printf("Wrong Position for Deletion\n");
30
        return false;
31
    }
32
    while (L && L->Next != P) {
33
        L = L->Next;
34
    }
35
    if (!L || !L->Next) {
36
        printf("Wrong Position for Deletion\n");
37
        return false;
38
    }
39
    L->Next = P->Next;
40
    free(P);
41
    return true;
42
}

求链表的倒数第m个元素#

1
ElementType Find( List L, int m ) {
2
    int len = 0;
3
    for (List t = L; t; t = t->Next) len++;
4
    m = len - m;
5
    while (L && m--) L = L->Next;
6
    return L ? L->Data : ERROR;
7
}

单链表分段逆转#

一段一段做，段内反转，同时需要记录下一个点和这段最左边的点的地址，段间连起来，第 4 个点段错误是因为没有特判 n < k 爆掉了，别问我怎么知道的。

1
void K_Reverse( List L, int K ) {
2
    int len = 0;
3
    for (List p = L; p; p = p->Next) len++;
4
    len--;
5
    if (len < K) return;
6
    len = len / K * K;
7
    List h = L, cur, pre, tmp;
8
    L = L->Next;
9
    for (int i = 0; i < len; i += K) {
10
        cur = L, pre = L, tmp = NULL;
11
        L = L->Next;
12
        for (int j = 1; j < K; ++j) {
13
            tmp = L->Next;
14
            L->Next = pre;
15
            pre = L;
16
            L = tmp;
17
        }
18
        h->Next = pre;
19
        h = cur;
20
    }
21
    h->Next = tmp;
22
}

共享后缀的链表#

先往后移动长的链表的头指针，对齐之后同时右移，直到重合，类似暴力的 lca 的做法。

1
PtrToNode Suffix( List L1, List L2 ) {
2
    int l1 = 0, l2 = 0;
3
    for (List p = L1->Next; p; p = p->Next) l1++;
4
    for (List q = L2->Next; q; q = q->Next) l2++;
5
    if (l1 > l2) for (int i = 0; i < l1 - l2; ++i) L1 = L1->Next;
6
    else for (int i = 0; i < l2 - l1; ++i) L2 = L2->Next;
7
    while (L1 && L1 != L2) L1 = L1->Next, L2 = L2->Next;
8
    return L1;
9
}

编程题#

两个有序链表序列的合并#

参考归并排序的合并。

1
#include <iostream>
2
#include <list>
3

4
using namespace std;
5

6
int main() {
7
    list<int> a, b, c; // STL！爽！
8
    int t;
9
    while (scanf("%d", &t), t != -1) a.emplace_back(t);
10
    while (scanf("%d", &t), t != -1) b.emplace_back(t);
11
    auto h1 = a.begin(), h2 = b.begin();
12
    while (h1 != a.end() && h2 != b.end()) {
13
        if (*h1 <= *h2) c.emplace_back(*h1++);
14
        else c.emplace_back(*h2++);
15
    }
16
    while (h1 != a.end()) c.emplace_back(*h1++);
17
    while (h2 != b.end()) c.emplace_back(*h2++);
18
    if (c.empty()) printf("NULL");
19
    for (auto h = c.begin(); h != c.end(); h++) {
20
        if (h == c.begin()) printf("%d", *h);
21
        else printf(" %d", *h);
22
    }
23
    return 0;
24
}

一元多项式的乘法与加法运算#

其实就是一个高精乘法和高精加法，而且不用进位。个人感觉他的本意是想考链表，但是数据给太小了，直接开 2000 的数组就能跑过去。如果 p 给个 10⁶ 以上那就得老老实实用链表了。

1
#include <iostream>
2

3
using namespace std;
4
const int N = 1010;
5
int a[N], b[N], c[N * 2];
6

7
int main() {
8
    int n, m;
9
    scanf("%d", &n);
10
    for (int i = 1; i <= n; ++i) {
11
        int t, p;
12
        scanf("%d%d", &t, &p);
13
        a[p] = t;
14
    }
15
    scanf("%d", &m);
16
    for (int i = 1; i <= m; ++i) {
17
        int t, p;
18
        scanf("%d%d", &t, &p);
19
        b[p] = t;
20
    }
21
    for (int i = 0; i <= 1000; ++i) {
22
        for (int j = 0; j <= 1000; ++j) {
23
            c[i + j] += a[i] * b[j];
24
        }
25
    }
26
    bool print = false;
27
    for (int i = 2000; i >= 0; --i) {
28
        if (c[i]) {
29
            if (!print) print = true, printf("%d %d", c[i], i);
30
            else printf(" %d %d", c[i], i);
31
        }
32
    }
33
    if (!print) printf("0 0\n");
34
    else printf("\n");
35
    for (int i = 0; i <= 1000; ++i) a[i] += b[i];
36
    print = false;
37
    for (int i = 1000; i >= 0; --i) {
38
        if (a[i]) {
39
            if (!print) print = true, printf("%d %d", a[i], i);
40
            else printf(" %d %d", a[i], i);
41
        }
42
    }
43
    if (!print) printf("0 0\n");
44
    else printf("\n");
45
    return 0;
46
}

多项式 A 除以 B#

这道其实是高精除法，本意应该也是想考链表，但是实测数组开 10⁴ 能过，p 给个 10⁵ 以上差不多就能卡掉数组了。

1
#include <iostream>
2
#include <cmath>
3

4
using namespace std;
5

6
const int N = 10010;
7
const double eps = 0.05;
8
double a[N], b[N], c[N];
9

10
void print(double a[]) {
11
    int t = 0;
12
    for (int i = 0; i <= 10000; ++i) {
13
        if (fabs(a[i]) >= eps) t++;
14
    }
15
    if (!t) printf("0 0 0.0\n");
16
    else {
17
        printf("%d", t);
18
        for (int i = 10000; i >= 0; --i) {
19
            if (fabs(a[i]) >= eps) printf(" %d %.1lf", i, a[i]);
20
        }
21
        printf("\n");
22
    }
23
}
24

25
int main() {
26
    int n, m, l1 = 0, l2 = 0;
27
    scanf("%d", &n);
28
    for (int i = 1; i <= n; ++i) {
29
        int t, p;
30
        scanf("%d%d", &p, &t);
31
        l1 = max(l1, p);
32
        a[p] = t;
33
    }
34
    scanf("%d", &m);
35
    for (int i = 1; i <= m; ++i) {
36
        int t, p;
37
        scanf("%d%d", &p, &t);
38
        l2 = max(l2, p);
39
        b[p] = t;
40
    }
41
    for (int i = l1 - l2; i >= 0; --i) {
42
        if (a[i + l2]) {
43
            c[i] = a[i + l2] / b[l2];
44
            for (int j = 0; j <= l2; ++j) {
45
                a[i + j] -= c[i] * b[j];
46
            }
47
        }
48
    }
49
    print(c);
50
    print(a);
51
    return 0;
52
}

Star's Blog