数据结构第五章作业

---

第一题

设计算法，给定两个均含有n个元素的整形数组A和B，判定B是否是A循环右移若干位得到的。

解：

使用KMP算法进行模式匹配即可，时间复杂度 \(O(n)\)，空间复杂度 \(O(n)\)。

bool isRightMove(int A[], int B[], int n) {
    // 求 next 数组, 假设下标从0开始
    int* next = (int*) calloc(n, sizeof(int));
    for (int i = 1, j = 0; i < n; i++) {
        while (j > 0 && B[i] != B[j]) j = next[j - 1];
        if (B[i] == B[j]) ++j;
        next[i] = j;
    }
    // 模式匹配
    bool found = false;
    for (int i = 0, j = 0; i < 2*n; i++) {
        int a = A[i%n];
        while (j > 0 && a != B[j]) j = next[j - 1];
        if (a == B[j]) ++j;
        if (j == n) found = true;
    }
    free(next);
    return found;
}

---

第二题

设对称矩阵A如下所示：

1. 若将A视为对称矩阵，画出对其压缩存储的存储表，并讨论如何存取A中元素 $ a_{ij} $ (\(1 <= i, j <= 4\));

2. 若将A视为稀疏矩阵，画出A的十字链表结构。

\[ \begin{bmatrix} 2 & 0 & 0 & 4 \\ 0 & 0 & 3 & 0 \\ 0 & 3 & 0 & 0 \\ 4 & 0 & 0 & 0 \\ \end{bmatrix} \]

1. 

存取方式：\(a_{ij} = \begin{cases} sa_{\frac{i(i-1)}{2} + j} & \text{if } i \ge j, \\ sa_{\frac{j(j-1)}{2} + i} & \text{if } i < j. \end{cases}\)

1. 

---

第三题

求下列广义表操作的结果：

解：

1. Head[Tail[Head[((a, b),(c,d))]]] = a
2. Tail[Head[Tail[((a,b),(c,d))]]] = (d)

---

第四题

利用广义表的Head和Tail操作把原子c从广义表L=((a,b),(c,d))中分离出来，并求表L的长度和深度。

解：

c = Head[Tail[L]]，L的长度为2，深度为2。

---

第五题

假设一个稀疏矩阵t的行列数相同，采用三元组TSMatrix表示，TSMatrix结构参见课件第17页，设计算法求左上->右下对角线上非0元素之和。

解：

如果不是方阵，返回false，否则遍历所有元素，如果行标和列标相同，加入sum，最后返回true。

bool Sum(TSMatrix t, elemtype &sum) {
    if (t.m != t.n) return false;
    sum = 0;
    for (int p = 1; p <= t.t; ++p) {
        if (t.data[p].i == t.data[p].j) {
            sum += t.data[p].v;
        }
    }
    return true;
}

---