数据结构和数值分析复习

频度

1
2
3
4
5
k=0;
for(i=1;i<=n;i++) {
    for(j=i; j<=n; j++)
        @  k++;
}

@语句的频度为

$$\displaystyle\sum^n_{i=1}i= \frac{n(n+1)}{2}$$

循环队列

假设将循环队列定义为：以域变量rear和length分别指示循环队列中队尾元素的位置和内含的元素个数，试给出此循环队列的队满条件，写出相应的入队列和出队列算法（出队列算法应返回队头元素）

设num为队列大小

队满条件可以设置为(rear + length) % num = 0 或 rear->next == front
队空条件可设置为rear == front

入队列算法，先检查队满与否，若不满，则在rear位置插入数据，rear和length都加一。

1
2
3
4
5
6
7
8
9
10
int enqueue(int queue[], int rear, int length, int element) {
    // 队满检查
    if ((rear + length) % num== 0) {
        return -1;
    }
    queue[rear] = element;
    rear = (rear + 1) % num;
    length++;
    return 0;
}

出队列算法，先检查队空与否，若不空，则在(rear - length + 1) % num位置获取front，然后减少length的值，由于rear只指示队尾指针，因此不需要变化。

1
2
3
4
5
6
7
8
9
10
int dequeue(int queue[], int rear, int length) {
    // 队空检查
    if (*length == 0) {
        return -1;
    }
    int front = (rear - length + 1) % num;
    int element = queue[front];
    length --;
    return element;
}

由于队首位置可以直接指定，因此不需要再赋0，当然赋0也可以。

模式匹配算法

个人认为kmp算法讲得比较好的一位

现在指定字符串的数据结构为

1
2
3
4
5
6
7
typedef struct String {
    char *str;
    int length;
    String(char *str, int length) : str(str), length(length) {}
} *string;

int next[length] = {0};

暴力匹配算法

赋初值后开始比较，若对应字符相等则i与j同时相加，指示串中下个位置，比较下一字符。否则指针i后退重新开始匹配，从主串的下一个字符开始比较。
如果是j > t->length导致的循环结束，那么就是找到了指定位置，可以进行输出。反之则是匹配不成功，返回-1；

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int brute_force(string s, string t, int pos) // s串为主串，t串为模式，pos为开始比较的位置
{
    int i = pos, j = 0;
    while (i <= s->length && j <= t->length)
    {
        if (s->str[i] == t->str[j])
            i++, j++;
        else
            i = i - j + 2, j = 1;
    }
    if (j > t->length)
        return i - t->length;
    else
        return -1;
}

临时数组next

以下举例说明，设模式串为abaabcac

  • next[0]固定为0
  • i = 1，a与b不等，next[1] = j = 0
  • i = 2，a和a相等，j = 1，next[2] = 1
  • i = 3，b与a不等，j = next[0] = 0，a与a相等，j = 1，next[3] = 1
  • i = 4，b与b相等，j = 2，next[4] = 2
  • 最后为[0, 0, 1, 1, 2, 0, 1, 0]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
void get_next(string t, int *next)
{
    for (int i = 0; i < 100; i++) // 包括了next[0] = 0
        next[i] = 0;
    int j = 0;
    for (int i = 1; i < t->length; i++)
    {
        while (j && t->str[i] != t->str[j])
            j = next[j - 1];
        if (t->str[i] == t->str[j])
            ++j;
        next[i] = j;
    }
}

kmp

若匹配失败，则在next数组中寻找对应的回溯位置。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int kmp(string s, string t, int pos)
{
    int i = pos, j = 0;
    get_next(t, next);
    while (i <= s->length && j <= t->length)
    {
        if (j == 0 || s->str[i] == t->str[j])
            ++i, ++j;
        else
            j = next[j];
    }
    if (j > t->length)
        return i - t->length;
    else
        return 0;
}

稀疏矩阵压缩

设有上三角矩阵A[n][n]，将其上三角元素逐行存于数组B[m]中，使得B[k] = A[i][j], k = f1(i)+f2(j)+c，试推导出函数f1，f2和常数c。

对上三角矩阵，设i<=j有

$$
k=\underbrace{n + (n-1) + (n+2)+…+(n-i+2)}{前i-1行}+\underbrace{(j-i+2)}{第i行}\\ =\frac{n-(i-1)}{2}i+j-n\\ 故f_1(i) = \frac{n-(i-1)}{2},\ f_2(j)=j,\ c=-n
$$

二叉树的遍历

假设一棵二叉树的先序遍历序列为EBADCFHGIKJ，中序遍历序列为ABCDEFGHIJK，请画出该二叉树

可通过递归寻找。

  • 先序遍历的第一个节点E一定是根节点，中序遍历从这个节点开始划分成{ABCD}{FGHIJK}两部分
  • 以左划分为例，中序遍历对应的先序遍历序列为{BADC}，B为父节点，中序遍历划分为{A}{CD}两部分
  • 如此递归，即可得到结果
graph TD
E-->B-->A
B-->D-->C
D-->a[null]
E-->F-->b[null]
F-->H-->G
H-->I-->c[null]
I-->K-->J
K-->d[null]

前序遍历代码

1
2
3
4
5
6
7
void pre(tree t) {
    if (!t)
        return;
    std::cout << t->value << " ";
    pre(t->left);
    pre(t->right);
}

中序遍历代码

1
2
3
4
5
6
7
void in(tree t) {
    if (!t)
        return;
    in(t->left);
    std::cout << t->value << " ";
    in(t->right);
}

后序遍历代码

1
2
3
4
5
6
7
void post(tree t) {
    if (!t)
        return;
    post(t->left);
    post(t->right);
    std::cout << t->value << " ";
}

层序遍历二叉树（BFS）代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
std::vector<int> BFS(tree t)
{
    std::queue<tree> q;
    std::vector<int> v;
    if(t)
        q.push(t);
    while(!q.empty())
    {
        tree temp = q.front();
        v.push_back(temp->value);
        if(temp->left)
            q.push(temp->left);
        if(temp->right)
            q.push(temp->right);
        q.pop();
    }
    return v;
}

线索二叉树

线索二叉树的系节点形式

lchildLTagdataRTagrchild

其中，若LTag/RTag为0，则表示child域指示节点的孩子，若为1，则指示节点的前驱/后继。

平均查找长度

$$ASL=\displaystyle\sum^n_{i=1}P_iC_i$$

$P_i$为查找表中第i个记录的概率（显然有$\sum^n_{i=1}P_i=1$），$C_i$为找到第i个记录时进行过比较的次数，可类比于数学期望。

顺序查找的 $ASL=\displaystyle\frac{1}{n} \sum^n_{i=1}i=\frac{n+1}{2}$
将顺序表进行排序后可以进行折半查找。

1
2
3
4
5
6
7
8
9
10
11
12
13
int find(int *a, int length, int value) {
    int low = 0, high = length, mid;
    while(low <= high) {
        mid = (low + high) / 2;
        if(key == a[mid])
            return mid;
        else if (key < a[mid])
            high = mid - 1;
        else
            low = mid + 1;
    }
    return -1;
}

n很大时， $ASL=\log _2(n+1)-1$

BST

其删除操作

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
tree del(int value, tree t)
{
    tree p = t, f = nullptr;
    while (p) // 查找指定结点
    {
        if (p->value == value)
            break;
        if (p->value > value)
            p = p->left;
        else
            p = p->right;
    }
    if (!p)
        return;

    tree q = p;
    if (p->left && p->right) // 左右均不为空
    {
        tree s = p->left;
        while (s = s->right != nullptr)
            q = s;
        p->value = s->value;
        if (q != p)
            q->right = s->right;
        else
            q->left = s->left;
        delete s;
        return;
    }

    else if (!p->right) // 被删节点无右子树，只需重接其左子树
        p = p->left;
    else if(!p->left) //被删节点无左子树，只需重接其右子树
        p = p->right;
    // 将p所指的子树挂接到其双亲节点*f相应的位置
    if(!f) // 被删节点为根节点
        t = p;
    else if(q == f->left) // 挂接到*f的左子树位置
        f->left = p;
    else // 挂接到*f的右子树位置
        f->right = p;
    delete q;
}

霍夫曼编码

哈希表处理冲突（顺序表）

探测公式： $H_i=(H(key)+d_i)% m \quad i\leq m-1$
线性探测时， $d_i=1,2,…,m-1$
伪随机探测时， $d_i$为指定的伪随机数列
进行查找时，通过不断计算下一个下一个散列地址$H_i$查找数据。

不同排序方法

插入排序

按顺序取一个数，放到指定的位置上。时间复杂度为$O(n^2)$，是稳定排序，适合记录基本有序的情况。

1
2
3
4
5
6
7
8
9
10
11
for (int i = 1; i < length; ++i)
{
    if (array[i] > array[i - 1])
    {
        tmp = array[i];
        array[i] = array[i - 1];
        for (index = i - 1; tmp > array[index]; --index)
            array[index + 1] = array[index];
        array[index + 1] = tmp;
    }
}

将插入与折半结合，为折半插入排序，仍然是稳定排序，适合初始记录无序的情况。

希尔排序

将整个排序记录序列分成几组，从而减少直接插入排序的数据量。需要提前指定分组数量和分组次数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
void ShellInsert(int *a, int length, int dk) // 对顺序表L进行一趟增量是dk的希尔插入排序
{
    int tmp;
    for (i = dk; i <= length; ++i)
        if (a[i] < a[i - dk].key) // 需将a[i]插入有序增量子表
        {
            tmp = a[i]; // 暂存在tmp中
            for (j = i - dk; j > 0 && tmp < a[j]; j -= dk)
                a[j + dk] = a[j]; // 记录后移，直到找到插入位置
            a[j + dk] = tmp;     // 将tmp即原a[i]，插入正确位置
        }
}
void ShellSort(int *a, int *dt, int t) // 按增量序列dt[0..t-1]对顺序表L进行t趟希尔排序
{
    for (k = 0; k < t; ++k)
        ShellInsert(a, length, dt[k]); // 一趟增量为dt[t]的希尔插入排序
}

希尔排序不稳定，其最后一个增量必须为1，适合初始记录无序，n较大的情况。

冒泡排序

较为稳定，但n较大时不适宜使用。

快速排序

算法partition完成一趟快速排序，返回枢轴的位置。若待排序序列长度大于1（low < high），算法sort调用partition获取枢轴位置，然后递归执行，分别对分割所得的两个子表进行排序。

partition函数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int partition(int array[], int low, int high)
{
    int tmp = array[low];
    while (low < high)
    {
        while (low < high && array[high] >= tmp)
            --high;
        array[low] = array[high];
        while (low < high && array[low] <= tmp)
            ++low;
        array[high] = array[low];
    }
    array[low] = tmp;
    return low;
}

sort函数

1
2
3
4
5
6
7
8
9
void sort(int array[], int low, int high)
{
    if (low < high)
    {
        int tmp = partition(array, low, high);
        sort(array, low, tmp - 1);
        sort(array, tmp + 1, high);
    }
}

快速排序不稳定，当枢轴量每次都能平分数组时最快，适合初始记录无序的情况。平均状况下时间复杂度为$O(n\log n)$。

简单选择排序

与插入排序相反，从未排序的数组中选择一个合适的数放进去。

1
2
3
4
5
6
7
8
9
10
for(int i = 0; i< length; ++i)
{
    index = i;
    for(int j = i; j < length; ++j)
        if(array[j] < array[index])
            index = j;
    tmp = array[index];
    array[index] = array[i];
    array[i] = tmp;
}

理论上是稳定的，但稳定与否与交换的方法有关。其移动次数较少，可用于记录占用空间较多时的排序方式。

堆排序

序列${k_1,…,k_n}$在满足
$$k_i \geq k_{2i},\quad k_i \geq k_{2i+1}\\ k_i \leq k_{2i},\quad k_i \leq k_{2i+1}$$
其中之一时，可以称为堆。

筛选法调整成堆

1
2
3
4
5
6
7
8
9
10
11
12
13
14
void heap_adjust(int array[], int s, int m)
{   
    int temp = array[s];
    for(int j = 2 * s; j <= m; j *= 2)
    {
        if(j < m && array[j] < array[j + 1])
            ++j;
        if(temp >= array[j])
            break;
        array[s] = array[j];
        s = j;
    }
    array[s] = temp;
}

建初堆

1
2
3
4
5
void create_heap(int array[])
{
    for(int i = length / 2; i >= 0; --i)
        heap_adjust(array, i, length);
}

在堆中进行排序

1
2
3
4
5
6
7
8
9
10
11
12
void sort(int array[])
{
    create_heap(array);
    int temp;
    for(int i = length; i > 0; --i)
    {
        temp = array[0];
        array[0] = array[i];
        array[i] = temp;
        heap_adjust(array, 0, i - 1);
    }
}

是不稳定排序，时间复杂度接近于$O(n\log n)$，记录较多时更有优势。

归并排序

通过递归进行排序，稳定排序。

图的遍历

以下是对邻接矩阵和邻接表的定义
邻接矩阵

1
2
3
4
5
6
7
8
typedef struct Matrix_array
{
    bool array[maxnum][maxnum];
    bool visited[maxnum];
    int dot;
    int line;
} Matrix_array;
Matrix_array matrix_array;

邻接表

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
typedef struct Node
{
    int belong;
    int weight;
    struct Node *next;
    Node(int belong, int weight, struct Node *next) : belong(belong), weight(weight), next(next) {}
} *node;

typedef struct Link
{
    node matrix_link[maxnum];
    int dot;
    int line;
    int visited[maxnum];
    Link()
    {
        for (int i = 0; i < maxnum; i++)
            matrix_link[i] = new Node(emp, emp, nullptr);
    }
    void insert(int last_node, int next_node, int weight)
    {
        node before = new Node(next_node, weight, matrix_link[last_node]->next);
        matrix_link[last_node]->next = before;
        node after = new Node(last_node, weight, matrix_link[next_node]->next);
        matrix_link[next_node]->next = after;
    }
} Link;
Link link;

在邻接数列中进行DFS遍历

1
2
3
4
5
6
7
8
9
10
11
12
void DFS_in_array(int v)
{
    matrix_array.visited[v] = true;
    for (int w = 0; w < matrix_array.dot; w++)
    {
        if (matrix_array.array[v][w] && !matrix_array.visited[w])
        {
            q.push(w + 1);
            DFS_in_array(w);
        }
    }
}

在邻接表中进行DFS遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
void DFS_in_link(int v)
{
    link.visited[v] = true;
    int w;
    node p = link.matrix_link[v]->next;
    while (p)
    {
        w = p->belong;
        if (!link.visited[w])
        {
            q.push(w + 1);
            DFS_in_link(w);
        }
        p = p->next;
    }
}

在邻接数列中进行BFS遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
void BFS_in_array(int v)
{
    std::queue<int> temp;
    matrix_array.visited[v] = true;
    temp.push(v + 1);
    while (!temp.empty())
    {
        q.push(temp.front());
        temp.pop();
        for (int w = 0; w < matrix_array.dot; w++)
            if (matrix_array.array[v][w] && !matrix_array.visited[w])
            {
                temp.push(w + 1);
                BFS_in_array(w);
            }
    }
}

在邻接表中进行BFS遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
void BFS_in_link(int v)
{
    queue<int> temp;
    link.visited[v] = true;
    temp.push(v + 1);
    while (!temp.empty())
    {
        q.push(temp.front());
        temp.pop();
        for (node p = link.matrix_link[v]->next; p != nullptr; p = p->next)
            if (!link.visited[p->belong])
            {
                temp.push(p->belong + 1);
                link.visited[p->belong] = true;
            }
    }
}

若图中有不止一个连通分量，则需要另设一个大循环，在循环中不断检测未遍历到的分量继续遍历

克鲁斯卡尔算法更适合求稀疏网的最小生成树

矩阵分解

Doolittle分解

例

$
\begin{array}{l}
A=
\begin{pmatrix}1&2&-3\\2&-1&3\\3&-2&2\end{pmatrix} \rightarrow\begin{pmatrix}1&2&-3\\ \ \end{pmatrix}\\ \quad\rightarrow\begin{pmatrix}1&2&-3\\ \frac{2}{1} \\ \frac{3}{1} \end{pmatrix} \rightarrow\begin{pmatrix}1&2&-3\\ 2 \\ 3\end{pmatrix}\\ \quad \rightarrow\begin{pmatrix}1&2&-3\\ 2&{-1-2\times 2}&{3-2 \times -3} \\ 3\end{pmatrix} \rightarrow\begin{pmatrix}1&2&-3\\ 2&-5&9 \\ 3\end{pmatrix}\\ \quad \rightarrow\begin{pmatrix}1&2&-3\\ 2&-5&9 \\ 3&{\frac{-2-2\times 3}{-5}}\end{pmatrix}\rightarrow\begin{pmatrix}1&2&-3\\ 2&-5&9 \\ 3&\frac{8}{5}\end{pmatrix}\\ \quad \rightarrow \begin{pmatrix}1&2&-3\\ 2&-5&9 \\ 3&\frac{8}{5}&2-9\times\frac{8}{5}+3\times 3\end{pmatrix} \rightarrow\begin{pmatrix}1&2&-3\\ 2&-5&9 \\ 3&\frac{8}{5}&-\frac{17}{5}\end{pmatrix}\\ \quad \rightarrow L=\begin{pmatrix}1&\\ 2&1\\ 3&\frac{8}{5}&1\end{pmatrix},\quad U=\begin{pmatrix}1&2&-3\\&-5&9 \\ &&-\frac{17}{5}\end{pmatrix}
\end{array}
$

平方根分解

例

$
\begin{array}{l}
A=
\begin{pmatrix}1&2&3\\2&8&14\\ 3&14&29\end{pmatrix} \\ \quad L=\begin{pmatrix}\sqrt{1}&&\\ \displaystyle\frac{2}{\sqrt{1}}&&\\ \displaystyle\frac{2}{\sqrt{1}}\end{pmatrix} \rightarrow\begin{pmatrix}1&&\\ 2&&\\ 3&&\end{pmatrix} \\ \quad \rightarrow\begin{pmatrix}1&&\\ 2&\sqrt{8-2^2}&\\ 3&\displaystyle\frac{14-3\times 2}{\sqrt{8-2^2}}&\end{pmatrix}\rightarrow\begin{pmatrix}1&&\\ 2&2&\\ 3&4&\end{pmatrix} \\ \quad \rightarrow\begin{pmatrix}1&&\\ 2&2&\\ 3&4&\sqrt{29-3^2-4^2}\end{pmatrix} \rightarrow\begin{pmatrix}1&&\\ 2&2&\\ 3&4&2\end{pmatrix}
\end{array}
$

插值

下列节点的拉格朗日三次插值多项式和牛顿插值多项式

$
\begin{array}{}x_i&1&2&5&6\\ f(x_i)&-3&3&9&27\end{array}
$

拉格朗日插值多项式

$
\begin{array}{l}
-3\times\displaystyle\frac{(x-2)(x-5)(x-6)}{(1-2)(1-5)(1-6)}+3\times\displaystyle\frac{(x-1)(x-5)(x-6)}{(2-1)(2-5)(2-6)} \\ +9\times\displaystyle\frac{(x-1)(x-2)(x-6)}{(5-1)(5-2)(5-6)}+27\times\displaystyle\frac{(x-1)(x-2)(x-5)}{(6-1)(6-2)(6-5)}
\end{array}
$

差商表

$
\begin{array}{}x_k&f(x_k)&1阶&2阶&3阶\\1&-3\\2&3&6\\5&9&2&-1\\6&27&18&4&1\end{array}
$

牛顿插值

$
N(x)=-3+6(x-1)-(x-1)(x-2)+(x-1)(x-2)(x-5)
$

法方程逼近

$(f,g)=\displaystyle\int^{+\infty}_{-\infty}f(x)g(x)dx$

求$y=e^x$在[0,1]上的一次最佳平方逼近多项式

$
\begin{array}{l}
设为y=a_0+a_1x.\\ (\psi_0,\psi_0)=\int^1_01dx=1,\quad(\psi_1,\psi_0)=\int^1_0xdx=\frac{1}{2} \quad (\psi_1,\psi_1)=\int^1_0x^2dx=\frac{1}{3}\\\ (f,\psi_0)=\int^1_0e^xdx=e-1,\quad(f,\psi_1)=\int^1_0xe^xdx=1\\\ \\ 则\begin{bmatrix}1&\displaystyle\frac{1}{2}\\\displaystyle\frac{1}{2}&\displaystyle\frac{1}{3}\end{bmatrix}\begin{bmatrix}a_0\\ a_1\end{bmatrix}=\begin{bmatrix}15\\ 10\end{bmatrix}\\ 解得a_0=6(3-e), a_1=3(3e-8)
\end{array}
$

最小二乘曲线拟合

$
方程组为p(x)=a_0+a_1x+\dots+a_nx^n\\
$
$
\begin{bmatrix} m&\displaystyle\sum^m_{i=1}x_i&\displaystyle\sum^m_{i=1}x_i^2&\dots&\displaystyle\sum^m_{i=1}x_i^n\\ \displaystyle\sum^m_{i=1}x_i&\displaystyle\sum^m_{i=1}x_i^2&\displaystyle\sum^m_{i=1}x_i^3&\dots&\displaystyle\sum^m_{i=1}x_i^{n+1}\\ \vdots&\vdots&\vdots&&\vdots\\ \displaystyle\sum^m_{i=1}x_i^n&\displaystyle\sum^m_{i=1}x_i^{n+1}&\displaystyle\sum^m_{i=1}x_i^{n+2}&\dots&\displaystyle\sum^m_{i=1}x_i^{2n}\end{bmatrix}\ \cdot \begin{bmatrix}a_0\\ a_1\\ \vdots \\ a_n\end{bmatrix}=\begin{bmatrix}\displaystyle\sum^m_{i=1}xy_i\\\displaystyle\sum^m_{i=1}x_iy_i\\\vdots\\ \displaystyle\sum^m_{i=1}x_i^ny_i\end{bmatrix}
$

勒让德多项式

$
P_0(x)=1\\P_1(x)=x\\P_2(x)=\displaystyle\frac{1}{2}(3x^2-1)\\…\\P_n(x)=\displaystyle\frac{1}{2^nn!}\frac{d^n}{dx^n}(x^2-1)^n
$

$
S_n(t)=\displaystyle\frac{(f,P_0)}{(P_0,p_0)}P_0(t)+ \dots + \displaystyle\frac{(f,P_n)}{(P_n,P_n)}P_n(t)
$

结果最后考试和复习题里的基本一样，我还是花太多时间在这上面了 (ﾟДﾟ*)ﾉ

日常
#日常 #复习
数据结构和数值分析复习
http://example.com/2024/12/30/review-1/
作者
Ivan Chen
发布于
2024年12月30日
许可协议
IVAN