完成经典算法的C语言实现
发表Code0次访问

完成经典算法的C语言实现

[button color=”success” icon=”” url=”https://git.tanknee.cn/tanknee/DataStruct" type=””]全文源码git地址[/button]

基于磁盘的带替换选择的合并排序

先替换选择，再进行外部合并排序。

替换选择

先从源文件中读取M个数据，然后将M个数据中的最小值输出到输出文件中，再从源文件读取下一个数据。直到死区放满了或者源文件读完了再更换输出文件，直到全部处理完成，源文件与输出文件的指针交换，进行合并排序。

合并排序

从两个有数据的文件中读取第一个数据，然后比较大小，将较小的打印在输出文件上，直到这个顺串打印完成。当两个文件全部输出完后进行下一次合并排序。

合并排序结束的条件是输出文件中只有一个是有数据的，另一个没有数据。

源代码

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
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
#define INF (~(0x1 << 31)) // 最大值(即0X7FFFFFFF)
#define NUM(N) N * 2 + 1
#define runN 3

int num = runN;
void DiskMerge();
void swapArray();
// 插入排序
//这里使用排序来替代原本的构建堆，其目的都是找出最小的元素，因此我认为效果是一致的，所以为了方便我选择使用插入排序。
void insertSort(int A[], int length)
{
    // 插入排序的主要思想是排过序的前一部分是永远有序的，只需要将当前元素放置到正确位置就好
    int temp = 0;
    int j = 0;
    for (int i = 1; i < length; i++) //可以选择直接从第一个元素开始
    {
        temp = A[i];
        for (j = i; j > 0 && A[j - 1] > temp; j--) // 第一个j=i的元素是还没有被排序的待排元素！所以要从第i-1个元素开始排序
        {
            A[j] = A[j - 1];
        }
        // 退出上一个循环的原因要么是找到了该放的正确位置，要么是到了数组的第一位。
        // 但是不管是那种情况，此时j就是正确位置的下标！
        A[j] = temp;
    }
}

/**
 * fa1 fa2是输入磁带
 * fb1 fb2是输出磁带
 * */
void DiskMergeSort(FILE *fa_1, FILE *fa_2, FILE *fb_1, FILE *fb_2)
{

    //定义缓冲区
    int tempBuff[runN] = {INF, INF, INF};
    // 死区，存放不符合要求的元素
    int deadSpace[runN] = {INF, INF, INF};
    //数据缓存
    int dataCache[1] = {0};
    int index = 0;
    int j = 0;
    int flag = 0;
    // 读入三个初始数据
    while (!feof(fa_1) && j < 3)
    {
        fscanf(fa_1, "%d", tempBuff + j);
        ++j;
    }
    //排序
    insertSort(tempBuff, runN);

    while (1)
    {
        // 循环继续的条件是输入磁盘的指针没有达到末尾，并且当前顺串没有完结,并且死区没有放满
        // 当tempBuff的第一个元素都是INF时，说明队列已经清空了。
        while (!feof(fa_1) && tempBuff[0] != INF && index != 3)
        {
            /*  把最小的记录写道输出磁盘上，再从输入磁盘读入下一个记录，如果它比刚刚写的记录要大，那么就把他加入到数组中，否则就放入死区。
         *
         * */
            insertSort(tempBuff, runN);
            fprintf(fb_1, "%d ", tempBuff[0]);
            fscanf(fa_1, "%d", dataCache);
            // 如果读入的值比刚刚打印的那个值要大，那么就将这个数据放入到队列中
            if (dataCache[0] > tempBuff[0])
            {
                tempBuff[0] = dataCache[0];
                insertSort(tempBuff, runN);
            }
            else
            {
                //将打印了的那个位置置为最大正数
                tempBuff[0] = INF;
                insertSort(tempBuff, runN);
                //如果这个读入的值比打印的值还要小，那么就将这个数据放入死区中
                deadSpace[index++] = dataCache[0];
            }
        }
        //如果此时输入磁盘已经读取完了，那么就将当前队列中的所有数据导入到该磁盘中
        if (feof(fa_1))
        {
            index = 0;
            while (tempBuff[index] != INF && index < 3)
            {
                fprintf(fb_1, "%d ", tempBuff[index]);
                index++;
            }
            //队列打印完成之后，将死区的元素放入到另一个输出磁盘中
            FILE *tempFp = fb_1;
            fb_1 = fb_2;
            fb_2 = tempFp;
            index = 0;
            //重新构建队列，然后把它输入到输出磁盘中去
            insertSort(deadSpace, runN);
            while (deadSpace[index] != INF)
            {
                fprintf(fb_1, "%d ", deadSpace[index]);
                index++;
            }
            break;
        }
        // swapPoint(fb_1,fb_2);
        fprintf(fb_1, "%d ", INF);
        FILE *tempFp = fb_1;
        fb_1 = fb_2;
        fb_2 = tempFp;
        // 将死区内存储的数据转移到队列中
        swapArray(tempBuff, deadSpace, runN);
        for (int i = 0; i < runN; i++)
        {
            deadSpace[i] = INF;
        }
        index = 0;
    }
    fclose(fa_1);
    fclose(fa_2);
    fclose(fb_1);
    fclose(fb_2);
    // 将a1 a2中的文件合并排序到b1，b2中
    fa_1 = fopen("SortSource\\TA1.txt", "a+");
    fa_2 = fopen("SortSource\\TA2.txt", "a+");
    fb_1 = fopen("SortSource\\TB1.txt", "a+");
    fb_2 = fopen("SortSource\\TB2.txt", "a+");
    //下面进行合并排序
    DiskMerge(fb_1, fb_2, fa_1, fa_2);
}
/**
 * 合并部分
 * fa1 fa2是输入磁带
 * fb1 fb2是输出磁带
 * */
void DiskMerge(FILE *fa1, FILE *fa2, FILE *fb1, FILE *fb2)
{
    int temp1 = 0;
    int temp2 = 0;

    // 抹去输出磁盘上的全部内容
    fb1 = fopen("SortSource\\TA1.txt", "w");
    fb2 = fopen("SortSource\\TA2.txt", "w");
    // 重新打开输出磁盘
    fb1 = fopen("SortSource\\TA1.txt", "a+");
    fb2 = fopen("SortSource\\TA2.txt", "a+");
    // 选择当前要输出的磁盘
    FILE *outp = fb1;
    //用于交换的临时变量
    FILE *tempPoint;
    // 输入输出磁盘的标志
    //1 - TB对应输入  -1 - TA对应输入
    int flag = 1;
    // 读取元素
    fscanf(fa1, "%d", &temp1);
    fscanf(fa2, "%d", &temp2);
    while (1)
    {
        // 如果两个输入磁盘都没有读到文件末尾那么就一直进行，直到全部数据都被合并完成
        while (!feof(fa1) || !feof(fa2))
        {
            //当读取到分割符号时，或者是读取到文件末尾，就将另一个输入磁盘顺串全部输出到输出磁盘上
            if (temp1 == INF || feof(fa1))
            {
                if (!feof(fa1))
                {
                    fscanf(fa1, "%d", &temp1);
                }
                while (temp2 != INF && !feof(fa2))
                {
                    fprintf(outp, "%d ", temp2);
                    fscanf(fa2, "%d", &temp2);
                }
                outp = fb2;
                if (temp2 == INF && !feof(fa2))
                {
                    fprintf(outp,"%d ",INF);
                    fscanf(fa2, "%d", &temp2);
                }
                if (feof(fa1) && feof(fa2))
                {
                    break;
                }
                if (feof(fa1))
                {
                    temp1 = INF;
                }
            }
            if (temp2 == INF || feof(fa2))
            {
                if (!feof(fa2))
                {
                    fscanf(fa2, "%d", &temp2);
                }

                while (temp1 != INF && !feof(fa1))
                {
                    fprintf(outp, "%d ", temp1);
                    fscanf(fa1, "%d", &temp1);
                }
                outp = fb2;
                if (temp1 == INF && !feof(fa1))
                {
                    fprintf(outp,"%d ",INF);
                    fscanf(fa1, "%d", &temp1);
                }
                if (feof(fa1) && feof(fa2))
                {
                    break;
                }
                if (feof(fa2))
                {
                    temp2 = INF;
                }
            }
            // 将较小的那个数放到当前输出磁盘中去，然后读取下一个元素
            if (temp1 > temp2)
            {
                fprintf(outp, "%d ", temp2);
                fscanf(fa2, "%d", &temp2);
            }
            else if (temp1 < temp2)
            {
                fprintf(outp, "%d ", temp1);
                fscanf(fa1, "%d", &temp1);
            }
        }
        // 当两个文件都读取完成了，那么就关闭文件，完成文件的写入操作
        fclose(fb1);
        fclose(fb2);
        //接下来就是重新打开外部文件，并且此时要将原本的输入磁盘和输出磁盘交换。也就是输入变成了输出，输出变成了输入
        //下面这一段是将原本输入磁盘全部抹去，因为它们将要被当作输出磁盘使用

        // 输入输出磁盘的标志
        //1 - TB对应输入  -1 - TA对应输入
        if (flag == 1)
        {
            //清除当前的输入磁盘，并把它赋给输出磁盘指针
            fb1 = fopen("SortSource\\TB1.txt", "w");
            fb2 = fopen("SortSource\\TB2.txt", "w");
            fb1 = fopen("SortSource\\TB1.txt", "a+");
            fb2 = fopen("SortSource\\TB2.txt", "a+");

            // 打开输入文件，创建指针赋值给输入指针
            fa1 = fopen("SortSource\\TA1.txt", "r");
            fa2 = fopen("SortSource\\TA2.txt", "r");
        }
        else if (flag == -1)
        {
            // 与上面类似
            fb1 = fopen("SortSource\\TA1.txt", "w");
            fb2 = fopen("SortSource\\TA2.txt", "w");
            fb1 = fopen("SortSource\\TA1.txt", "a+");
            fb2 = fopen("SortSource\\TA2.txt", "a+");

            fa1 = fopen("SortSource\\TB1.txt", "r");
            fa2 = fopen("SortSource\\TB2.txt", "r");
        }
        flag *= -1;
        int temp3 = fscanf(fa1, "%d", &temp1);
        int temp4 = fscanf(fa2, "%d", &temp2);
        outp = fb1;
        if (fa1 != NULL && temp4 == -1)
        {
            break;
        }
        else if (temp3 == -1 && fa2 != NULL)
        {
            break;
        }
    }
}
void swapArray(int A[], int B[], int length)
{
    for (int i = 0; i < length; i++)
    {
        A[i] = B[i];
    }
}
int main(int argc, char const *argv[])
{
    FILE *fa_1, *fa_2, *fb_1, *fb_2;
    fa_1 = fopen("SortSource\\TA1.txt", "a+");
    fa_2 = fopen("SortSource\\TA2.txt", "a+");
    fb_1 = fopen("SortSource\\TB1.txt", "a+");
    fb_2 = fopen("SortSource\\TB2.txt", "a+");
    DiskMergeSort(fa_1, fa_2, fb_1, fb_2);
    //关闭文件流
    fclose(fa_1);
    fclose(fa_2);
    fclose(fb_1);
    fclose(fb_2);
    return 0;
}

测试用例

一共五十个数据。

1
3326 8497 13428 12105 29791 18956 18729 16025 27748 17760 11586 3912 1443 20730 6316 26020 28423 11436 9791 8752 13264 28739 8677 26431 6875 32184 511 15554 2852 25515 4100 9823 6537 17420 1131 24515 9169 4892 6604 13112 7404 17044 23362 7802 28284 11555 12819 14790 5013 22046

测试结果

1
511 1131 1443 2852 3326 3912 4100 4892 5013 6316 6537 6604 6875 7404 7802 8497 8677 8752 9169 9791 9823 11436 11555 11586 12105 12819 13112 13264 13428 14790 15554 16025 17044 17420 17760 18729 18956 20730 22046 23362 24515 25515 26020 26431 27748 28284 28423 28739 29791 32184

AVL树的插入

  1. 左旋转
  2. 右旋转
  3. 左右旋转
  4. 右左旋转

完全二叉树

定义：一棵二叉树中，只有最下面两层结点的度可以小于2，并且最下一层的叶结点集中在靠左的若干位置上。这样的二叉树称为完全二叉树。
特点：叶子结点只能出现在最下层和次下层，且最下层的叶子结点集中在树的左部。显然，一棵满二叉树必定是一棵完全二叉树，而完全二叉树未必是满二叉树。

插入

四种情况
LL:
RR:
LR:

相当于进行了一次RR旋转一次LL旋转。

RL:

相当于先进行了LL旋转在进行了RR旋转。

源代码

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
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
#define MAX(a,b) (a > b) ? (a) : (b)
/**
 * AVL树的结构体定义
 * */
typedef struct AVLTreeNode
{   
    int data;   //节点存储的值
    int height; //当前节点的高度
    struct AVLTreeNode *leftChild;  //左儿子
    struct AVLTreeNode *rightChild; //右儿子
}Node,*AVLTree;
/***
 * @param data 存储的数据
 * @param left 左儿子
 * @param right 右儿子
 * */
static Node *createAVLTreeNode(int data,Node *left,Node *right){
    // 为这个新的节点开辟内存空间
    Node *node;
    if (((node = (Node *)malloc(sizeof(Node))) == NULL)){
        return NULL;
    }
    // 为这个node赋初值
    node->data = data;
    // 空子树的高度为0
    node->height = 0;
    node->leftChild = left;
    node->rightChild = right;

    return node;
}
// 获取节点的高度
int getHeightOfNode(Node *node){
    return (node==NULL) ? 0 : node->height;
}
/*
 * LL：左左对应的情况(左单旋转)。
 *
 * 返回值：旋转后的根节点
 */
static Node* leftLeftRotation(AVLTree k2){
    AVLTree k1;

    k1 = k2->leftChild;
    // k2与k1的右子树进行互换
    k2->leftChild = k1->rightChild;
    k1->rightChild = k2;

    k2->height = MAX( getHeightOfNode(k2->leftChild), getHeightOfNode(k2->rightChild)) + 1;
    k1->height = MAX( getHeightOfNode(k1->leftChild), k2->height) + 1;
    // 旋转完成之后的根节点是k1，即k1上浮了而原本的k2下沉为k1的儿子了
    return k1;
}
/*
 * RR：右右对应的情况(右单旋转)。
 *
 * 返回值：旋转后的根节点
 */
static Node* rightRightRotation(AVLTree k2){
    AVLTree k1;

    k1 = k2->rightChild;
    // k2与k1的右子树进行互换
    k2->rightChild = k1->leftChild;
    k1->leftChild = k2;

    k2->height = MAX( getHeightOfNode(k2->leftChild), getHeightOfNode(k2->rightChild)) + 1;
    //此时的k2为k1的左儿子，所以只需要比较k2和k1的右儿子的高度就好了
    k1->height = MAX( getHeightOfNode(k1->rightChild), k2->height) + 1;
    // 旋转完成之后的根节点是k1，即k1上浮了而原本的k2下沉为k1的儿子了
    return k1;
}
/**
 * 
 * LR
 * 相当于进行了一次RR旋转一次LL旋转。
 * */
static Node *leftRightRotation(Node *k3){
    //先对k3的左子树进行RR旋转，再对旋转后的k3进行LL旋转
    k3->leftChild = rightRightRotation(k3->leftChild);
    return leftLeftRotation(k3);
}
/**
 * 
 * RL
 * 相当于进行了一次LL旋转一次RR旋转。
 * */
static Node *rightLeftRotation(Node *k3){
    //先对k3的右子树进行LL旋转，再对旋转后的k3进行RR旋转
    k3->rightChild = leftLeftRotation(k3->rightChild);
    return rightRightRotation(k3);
}
/**
 * 传入要插入的树
 * 传入要插入的数据
 * 返回更新后的树的根节点
 * */
Node *insertIntoAVLTree(AVLTree tree,int data){
    // 如果树是一个空树
    if (tree == NULL){
        // 那么就建立一个空节点
        tree = createAVLTreeNode(data,NULL,NULL);
        // 如果创建失败的话
        if (tree == NULL){
            printf("Create Node Failed");
        }
        
    }
    if (data < tree->data)//如果要插入的数值比根节点的值要小，那么就插入到其左子树中
    {
        // 然后递归调用插入方法，直到找到一个空节点再插入！
        tree->leftChild = insertIntoAVLTree(tree->leftChild,data);
        // 由于是插入到左子树中，因此只可能是左子树的高度大于右子树的高度
        if (getHeightOfNode(tree->leftChild) - getHeightOfNode(tree->rightChild) == 2)
        {
            // 如果需要插入的值根节点的左子树还要小那么说明插入到了左子树的左侧，那就可以判断此时的不平衡状态为左左LL，调用LL旋转即可
            if (data < tree->leftChild->data)
            {
                tree->leftChild = leftLeftRotation(tree->leftChild);
            }else   // 否则就说明大于这个节点的值，插入到在左子树的右儿子上，调用LR旋转
            {
                tree->leftChild = leftRightRotation(tree->leftChild);
            }
        }
    }else if (data > tree->data)
    {//如果要插入的数值比根节点的值要大，那么就插入到其由子树中
        tree->rightChild = insertIntoAVLTree(tree->rightChild,data);
        if (getHeightOfNode(tree->rightChild) - getHeightOfNode(tree->leftChild) == 2)// 由于插入到右子树中那么就是只有可能右子树的高度大于左子树的高度
        {
            if (data > tree->rightChild->data)
            {
                tree->rightChild = rightRightRotation(tree->rightChild);
            }else
            {
                tree->rightChild = rightLeftRotation(tree->rightChild);
            }
        }
    }else
    {
        printf("Don't Insert The Same Node");
    }
    // 更新根节点的高度
    int temp = MAX(getHeightOfNode(tree->leftChild),getHeightOfNode(tree->rightChild));
    if (((MAX(getHeightOfNode(tree->leftChild),getHeightOfNode(tree->rightChild))) == 0) && (tree->leftChild != NULL || tree->rightChild != NULL))
    {
        // 其子节点全部都是叶子节点
        // 说明两个子树至少存在一个，那么这个根节点的高度就是1
        tree->height = 1;
    }else if (tree->leftChild == NULL && tree->rightChild == NULL)
    {
        // 如果两个子树都不存在那么说明这个节点就是叶子节点，直接返回就好
        return tree;
    }else
    {
        tree->height = (MAX(getHeightOfNode(tree->leftChild),getHeightOfNode(tree->rightChild))) + 1;
    }
    
    return tree;
}

int main()
{
    Node *root = createAVLTreeNode(10,NULL,NULL);
    Node *left = createAVLTreeNode(6,NULL,NULL);
    Node *right = createAVLTreeNode(13,NULL,NULL);
    root->leftChild = left;
    root->rightChild = right;
    root = insertIntoAVLTree(root,5);
    root = insertIntoAVLTree(root,3);
    return 0;
}

测试用例

1
2
3
4
5
6
7
Node *root = createAVLTreeNode(10,NULL,NULL);
Node *left = createAVLTreeNode(6,NULL,NULL);
Node *right = createAVLTreeNode(13,NULL,NULL);
root->leftChild = left;
root->rightChild = right;
root = insertIntoAVLTree(root,5);
root = insertIntoAVLTree(root,3);

测试结果

1576112863289

图的表示

图的拓扑排序

在图论中，拓扑排序是一个有向无环图的所有顶点的线性序列

且该序列必须满足以下两个条件：

  • 每个顶点出现且只出现一次
  • 若存在一条从顶点A到顶点B的路径那么在序列中，A就在B的前面！

因此只有有向无环图才会有拓扑排序，非有向无环图是没有拓扑排序的！

求拓扑排序的方法：

  1. 从有向无环图中选取一个入度为0(没有前驱)的顶点，并输出
  2. 从这个图中删除这个顶点以及所有它指向其他顶点的有向边。也就是删除所有的出边！
  3. 重复1，2直到图为空或者图中不再存在没有入度的顶点，如果到最后是第二种情况，那么就说明有向图中必定存在环（类似于循环结构，有出有入）

由于一个图中，在同一个时间点，可能存在有多个入度为零的顶点，因此一个有向无环图可以有多个不同的拓扑排序序列！

源代码

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
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
#define MAX 5
typedef struct _ENode
{
    int index;                 // 该边的顶点的位置
    struct _ENode *nextEdge; // 指向下一条弧的指针
} ENode, *PENode;// _ENode 的变量别名

// 邻接表中表的顶点
typedef struct _VNode
{
    int index;          // 顶点信息
    ENode *firstEdge; // 指向第一条依附该顶点的弧
} VNode;

// 邻接表
typedef struct _LGraph
{
    int vexNum; // 图的顶点的数目
    int edgNum; // 图的边的数目
    VNode vexs[MAX];
} LGraph;

// 边的数据
typedef struct _EData
{
    int start; // 起始顶点
    int end;   // 结束顶点
} EData;
static EData gData[] = {
    {0, 1},
    {0, 3},
    {1, 2},
    {1, 3},
    {2, 4},
    {3, 2},
    {3, 4}
};
void LinkToTheEnd(ENode *list, ENode *node){
    ENode *p = list;
    while (p->nextEdge)
    {
        p=p->nextEdge;
    }
    p->nextEdge = node;
    
}
// 创建一张图
LGraph *createLinkedGraph()
{
    ENode *node;
    LGraph *pG;
    int start,end;
    if ((pG = (LGraph *)malloc(sizeof(LGraph))) == NULL)
        return NULL;
    memset(pG, 0, sizeof(LGraph));
    pG->vexNum = MAX;
    pG->edgNum = 7;
    for (int i = 0; i < pG->vexNum; i++)
    {
        pG->vexs[i].index = i;
        pG->vexs[i].firstEdge = NULL;
    }
    // 初始化"邻接表"的边
    for (int i = 0; i < pG->edgNum; i++)
    {
        // 读取边的起始顶点,结束顶点
        start = gData[i].start;
        end = gData[i].end;

        // 初始化node1
        node = (ENode *)malloc(sizeof(ENode));
        memset(node,0,sizeof(ENode));
        node->index = end;
        // 将node1链接到"p1所在链表的末尾"
        if (pG->vexs[start].firstEdge == NULL)
            pG->vexs[start].firstEdge = node;
        else
            LinkToTheEnd(pG->vexs[start].firstEdge, node);
    }
    return pG;
}
// 获取图的出度数组
void createInDegree(LGraph *g,int InDegree[]){
    ENode *p;
    for (int i = 0; i < g->vexNum; i++)
    {
        p = g->vexs[i].firstEdge;
        
        while (p)
        {
            InDegree[p->index]++;
            p = p->nextEdge;   
        }
        
    }
}
// 更新维护入度数组
/**
 * g    图指针
 * InDegree 入度数组
 * node 需要改变的节点指针
 * 删除节点后把它在入度数组中置为-1
 * */
void updateInDegree(LGraph *g,int InDegree[],int index){
    InDegree[index] = -1;
    ENode *p;
    p = g->vexs[index].firstEdge;
    while (p)
    {
        InDegree[p->index]--;
        p = p->nextEdge;   
    }
}
// TopologicalSort 拓扑排序
void TopologicalSort(LGraph *g){
    ENode *node;
    int InDegree[g->vexNum];
    memset(InDegree,0,sizeof(int)*g->vexNum);
    createInDegree(g,InDegree);
    while (1)
    {
        int j = -1;
        for (int i = 0; i < g->vexNum; i++)
        {
            if (InDegree[i] == 0)
            {
                j = i;
                break;
            }
        }
        if (j == -1)
        {
            break;
        }
        printf("%d",j);
        updateInDegree(g,InDegree,j);
    }   
}
int main(int argc, char const *argv[])
{
    LGraph *g;
    g = createLinkedGraph();
    TopologicalSort(g);
    return 0;
}

测试用例

1
2
3
4
5
6
7
8
9
static EData gData[] = {
    {0, 1},
    {0, 3},
    {1, 2},
    {1, 3},
    {2, 4},
    {3, 2},
    {3, 4}
};

测试结果

最小编辑距离

在有的文章中，替换的代价是2，而在有的文章中，替换的代价是1，本文按照代价为1的来计算。不过个人认为代价为二更加合理。

动态规划表的初始化

  • D(0,j)=j，空串和长度为j的Y子串间的最小编辑距离（添加或删除对应的次数）
  • D(i,0)=i，长度为i的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
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
#define min(a, b) (a < b ? a : b)
#define MAX 10
/**
 * res 字符1--原始字符串
 * des 字符2--目标字符串
 * 
 * */
int minEditDistance(char *res, char *des)
{
    //首先初始化动态表--填充相对于空字符的编辑距离，也就是字符长度
    int dis[MAX][MAX] = {0};
    for (int i = 1; i <= (int)strlen(des); i++)
    {
        dis[0][i] = i;
    }
    for (int j = 1; j <= (int)strlen(res); j++)
    {
        dis[j][0] = j;
    }
    //循环遍历整个数组，计算每一个编辑距离
    for (int i = 1; i <= (int)strlen(res); i++)
    {
        for (int j = 1; j <= (int)strlen(des); j++)
        {
            // 如果在该位置的两个元素相同，那么到此的最小编辑距离就等同于不包含这两个元素的最小编辑距离
            if (res[i-1] == des[j-1])
            {
                dis[i][j] = dis[i-1][j-1];
            }
            else
            {
                /**
                 * 相对而言的！向下走的意思就是多出了一个多余元素，在相对于上面那一格的最小编辑距离而言需要将这个多出来的元素删掉
                 * 同理，向下走就是目标串多了一个元素，要在左侧编辑的基础下再多加一个元素
                 * 向右下角走也是差不多的道理，既有一个多余元素，而且目标串也多了一个元素，所以要使用替换操作。
                 * */
                int delEd = dis[i][j-1]+1;//往下走就是删除 
                int insEd = dis[i-1][j]+1;//往右走是插入
                int subEd = dis[i-1][j-1]+1;//向右下角走--对角线走就是替换 在这里替换的代价是1

                int minEd = min(min(delEd,insEd),subEd);
                dis[i][j] = minEd;
            }
        }
    }
    for(int m = 0; m < MAX; m++){
        for(int n = 0; n < MAX; n++){
            printf("%d",dis[m][n]);
        }
        printf("\n");
    }
    return dis[(int)strlen(res)][(int)strlen(des)];
}

int main(int argc, char const *argv[])
{
    printf("Min Distance of %s to %s is %d \n","sunny","snowy",minEditDistance("sunny","snowy"));
    printf("Min Distance of %s to %s is %d","me","ame",minEditDistance("me","ame"));
    return 0;
}

测试用例

1
2
printf("Min Distance of %s to %s is %d \n","sunny","snowy",minEditDistance("sunny","snowy"));
  printf("Min Distance of %s to %s is %d","me","ame",minEditDistance("me","ame"));

测试结果

表格表示

· s n o w y
· 0 1 2 3 4 5
s 1 0 1 2 3 4
u 2 1 1 2 3 4
n 3 2 1 2 3 4
n 4 3 2 2 3 4
y 5 4 3 3 3 3

所以最终的结论是sunny到snowy的最小编辑距离为3 。

· a m e
· 0 1 2 3
m 1 1 1 2
e 2 2 2 1

所以最终的结论是me到ame的最小编辑距离为1 。

霍夫曼编码

由此可以得到字符编码的前缀码，不过使用前缀码的前提是每个字符编码都不是其他编码的前缀！因此每个字符都要放在树的叶子节点上。

这样做就确保了编码没有二义性。

编码的比特数：

$$
c_i在d_i的深度出现了f_i次，那么这个字符所占用的比特数为：
\begin{equation*}

\sum_{i=1}^Nd_if_i

\end{equation*}
$$

其中深度的数值等于其编码的位数！

Huffman算法

算法对一个由树组成的森林进行，该森林中一共有C片叶子，也就是有C个字符需要编码。一棵树的权重等于它的树叶的频率之和。任取最小权重的两棵树$T_1$,$T_2$,并以这两棵树为子树形成新的树，将这样的过程进行C-1次，最终得到的就是Huffman编码的最优树。

为什么需要进行C-1次：

​ 因为森林中最开始有C棵树，也就是一共有C棵只有一个节点的树，每一次选取都会让两棵树合并成一棵树，树的总数减少一，因此从C到1也就需要进行C-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
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
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include <stdfix.h>
/***
 * 哈夫曼编码树
 * */
typedef struct HuffmanTree
{
    char con[2];                       // 节点的内容
    int f;                          //节点的频率
    struct HuffmanTree *leftChild;  //左儿子
    struct HuffmanTree *rightChild; //右儿子
} * Node;
// 创建一个新的节点
Node createNode(char con[], int f, Node left, Node right)
{
    // 先创建一个指针
    Node newNode;
    if ((newNode = (Node)malloc(sizeof(Node))) == NULL)
    {
        return NULL;
    }
    memset(newNode, 0, sizeof(Node));
    // strcpy(newNode->con,con);
    if (con)
    {
        memcpy(newNode->con,con,2*sizeof(char));
    }else
    {
        memset(newNode->con,0,2*sizeof(char));
    }
    // newNode->con = con;
    newNode->f = f;
    newNode->leftChild = left;
    newNode->rightChild = right;
    return newNode;
}
/**
 * tree 树的数组
 * legth 数组的长度
 * */
Node huffman(Node tree[], int length)
{
    Node tempNode, node1, node2,parent;
    //如果这个数组里面只剩下了两个元素，那么就说明已经排序完成了
    if (length == 2)
    {   
        node1 = tree[0];
        node2 = tree[1];
        parent = createNode(NULL,node1->f+node2->f,node1,node2);
        return parent;
    }
    
    // 给这个节点数组排序，找出频率最小的两个点
    int j = 0;
    for (int i = 0; i < length; i++)
    {
        tempNode = tree[i];
        for (j = i; j > 0 && tempNode->f < tree[j - 1]->f; j--)
        {
            tree[j] = tree[j - 1];
        }
        tree[j] = tempNode;
    }
    // 频率最小的两个节点
    node1 = tree[0];
    node2 = tree[1];
    parent = createNode(NULL,node1->f+node2->f,node1,node2);
    // 重新构建一个数组
    Node newArray[length-1];
    for (int i = 0; i < length - 2; i++)
    {
        newArray[i] = tree[i+2];
    }
    newArray[length-2] = parent;
    parent = huffman(newArray,length-1);
    return parent;
}

int main(int argc, char const *argv[])
{
    Node node_a, node_e, node_i, node_s, node_t, node_sp, node_nl,result;
    node_a = createNode("a", 10, NULL, NULL);
    node_e = createNode("e", 15, NULL, NULL);
    node_i = createNode("i", 12, NULL, NULL);
    node_s = createNode("s", 3, NULL, NULL);
    node_t = createNode("t", 4, NULL, NULL);
    node_sp = createNode("sp", 13, NULL, NULL);
    node_nl = createNode("nl", 1, NULL, NULL);
    Node nodeArray[] = {node_a, node_e, node_i, node_s, node_t, node_sp, node_nl};
    result = huffman(nodeArray, 7);
    return 0;
}

测试用例

1
2
3
4
5
6
7
8
9
10
Node node_a, node_e, node_i, node_s, node_t, node_sp, node_nl,result;
node_a = createNode("a", 10, NULL, NULL);
node_e = createNode("e", 15, NULL, NULL);
node_i = createNode("i", 12, NULL, NULL);
node_s = createNode("s", 3, NULL, NULL);
node_t = createNode("t", 4, NULL, NULL);
node_sp = createNode("sp", 13, NULL, NULL);
node_nl = createNode("nl", 1, NULL, NULL);
Node nodeArray[] = {node_a, node_e, node_i, node_s, node_t, node_sp, node_nl};
result = huffman(nodeArray, 7);

测试结果

图的表示

完成经典算法的C语言实现

https://www.tanknee.cn/2019/12/12/547/

作者

TankNee

发布于

12/12/2019

更新于

06/17/2022

许可协议

#

喜欢这篇文章？打赏一下作者吧

评论

最新文章

分类

×