企业官网建设流程全解析

2023/11/13-14 周一周二

GDPU数据结构实验10 哈夫曼树

【实验内容】
假设用于通信的电文仅由8个字母 {a, b, c, d, e, f, g, h} 构成，它们在电文中出现的概率分别为{ 0.07, 0.19, 0.02, 0.06, 0.32, 0.03, 0.21, 0.10 }，试为这8个字母设计哈夫曼编码，请输出哈夫曼树数组及编码。

提示：包含两个过程：（1）构建哈夫曼树，（2）输出编码。输出界面参考下图（测试数据请使用本实验中的数据）。

【参考代码】

#include <stdio.h> #include <malloc.h> #define MaxNode 20 #define MaxInt 99 #define Max 7 struct HtNode{ int ww; int parent, lchild, rchild; }; struct HtTree { int root; struct HtNode ht[MaxNode]; }; typedef struct HtTree PHtTree; typedef struct { int bit[MaxNode]; int start; int weight; }code; PHtTree* huffman(int m, int* w)//m为结点个数 { PHtTree* pht; int i, j, x1, x2, m1, m2; pht = (PHtTree*)malloc(sizeof(PHtTree)); if (pht == NULL) { printf("Out of space!!\n"); return pht; } for (i = 0; i < 2 * m - 1; i++) { pht->ht[i].lchild = -1; pht->ht[i].rchild = -1; pht->ht[i].parent = -1; if (i < m) { pht->ht[i].ww = w[i]; } else { pht->ht[i].ww = -1; } } for (i = 0; i < m - 1; i++) { m1 = MaxInt; m2 = MaxInt; x1 = -1; x2 = -1; for (j = 0; j < m + i; j++) { if (pht->ht[j].ww < m1 && pht->ht[j].parent == -1) { m2 = m1; x2 = x1; m1 = pht->ht[j].ww; x1 = j; } else if (pht->ht[j].ww < m2 && pht->ht[j].parent == -1) { m2 = pht->ht[j].ww; x2 = j; } } pht->ht[x1].parent = m + i; pht->ht[x2].parent = m + i; pht->ht[m + i].ww = m1 + m2; pht->ht[m + i].lchild = x1; pht->ht[m + i].rchild = x2; } pht->root = m + i; return pht; } void HuffmanCode(PHtTree *HuffTree, int n, code HuffCode[]) { int i, j, child, parent; code* p = (code*)malloc(sizeof(code)); if (p != NULL) { for (i = 0; i < n; i++) { p->start = n - 1; p->weight = HuffTree->ht[i].ww; child = i; parent = HuffTree->ht[child].parent; //由叶结点向上直到根结点 while (parent != -1) { if (HuffTree->ht[parent].lchild == child) p->bit[p->start] = 0; //左孩子编码0 else p->bit[p->start] = 1; //右孩子编码0 p->start--; child = parent; parent = HuffTree->ht[child].parent; } //保存每个结点的编码和不等长编码的起始位 for (j = p->start + 1; j < n; j++) HuffCode[i].bit[j] = p->bit[j]; HuffCode[i].start = p->start + 1; HuffCode[i].weight = p->weight; } } } int main() { int w[] = { 7, 19, 2, 6, 32, 3, 21, 10 };//叶子 PHtTree* pht; pht = huffman(8, w); int i, j; printf("index weight parent lchild rchild\n"); for (i = 0; i < 2*8-1; i++) { printf("%d\t%d\t%d\t%d\t%d\n", i, pht->ht[i].ww, pht->ht[i].parent, pht->ht[i].lchild, pht->ht[i].rchild); } printf("哈夫曼编码为：\n"); code *HCode = (code *)malloc(8 * sizeof(code)); HuffmanCode(pht, 8, HCode); if (HCode != NULL) { for (i = 0; i < 8; i++) { printf("weight = %d Code = ", pht->ht[i].ww); for (j = HCode[i].start; j < 8; j++) { printf("%d", HCode[i].bit[j]); } printf("\n"); } } free(pht);//删除哈夫曼树 free(HCode);//删除哈夫曼数组 }

【实验结果】

【实验总结】

• 我另外加了index，（中文名下标）更方便看表。
• 我把合并两个最小值，并且构造一个新的内部结点那段代码放在找两个最小值for循环里面，导致输出错误
• Bit数组不能是n-1，不然会越界，输出乱码

2023/11/15-19 周三--周日 分治后续

循环赛日程表

【参考代码】

递归版本

#include <iostream> using namespace std; int arr[100][100] = { 0 }; //row可以省略，为什么？ void dc(int row, int col, int n) { if (n == 1) { arr[0][col] = col + 1; return; } dc(0, col, n / 2); dc(0, col + n / 2, n / 2); for (int i = 0; i < n / 2; i++) { for (int j = 0; j < n / 2; j++) { arr[n / 2 + i][col + j] = arr[i][col + n / 2 + j]; arr[n / 2 + i][col + n / 2 + j] = arr[i][col + j]; } } } int main() { int m = 0; cin >> m; m = 1 << m; //2^m次方 dc(0, 0, m); //输出 for (int i = 0; i < m; i++) { for (int j = 0; j < m; j++) { cout << arr[i][j] << " "; } cout << endl; } }

非递归版本

#include <iostream> using namespace std; int arr[100][100] = { 0 }; //现有正方形左上角为（1，1） 边长为d， //向右生成同样大的正方形。具体来说： //将矩阵(x,y)-->(x+d-1, y + 2d - 1) //复制时每个元素值加d(边长) void generate(int x, int y, int d) { int i, j; for (i = x; i <= x + d - 1; i++) { for (j = y; j <= y + 2*d - 1; j++) { arr[i][j + d] = arr[i][j] + d; } } //return; } //相同复制 void copy(int x1, int y1, int d, int x2, int y2) { int i, j; for (i = 0; i <= d - 1; i++) { for (j = 0; j <= d - 1; j++) { arr[x2 + i][y2 + j] = arr[x1 + i][y1 + j]; } } //return; } void printSquare(int x, int y, int d) { int i, j; for (i = x; i <= d; i++) { for (j = y; j <= d; j++) { cout << " " << arr[i][j]; } cout << endl; } } int main() { int d = 1; int k = 3; arr[1][1] = 1; for (int i = 0; i < k; i++) { generate(1, 1, d); copy(1, 1, d, 1 + d, 1 + d);//左上copy到右下 copy(1, 1 + d, d, 1 + d, 1);//右上copy到左下 d = d * 2; } printSquare(1, 1, d); }

【运行结果】

【视频讲解链接】

非递归：【分治算法，循环比赛日程表，讲评】 https://www.bilibili.com/video/BV1rp4y1X7mb/?share_source=copy_web&vd_source=7ffbd7feaeedb3d59fb21e59435a53d8

递归：【信息学奥赛教程】分治算法 - 循环比赛日程表】 https://www.bilibili.com/video/BV12d4y1Q7YR/?share_source=copy_web&vd_source=7ffbd7feaeedb3d59fb21e59435a53d8

分治算法求解大整数乘法

说句实话，比赛的时候可不要这么折腾，好好的乘法不用，非要用这个。（除非数据很大，自带的乘法不能满足题目要求）

【参考代码】

#include <iostream> #include <math.h> using namespace std; #define signBit(A) ((A > 0) ? 1 : -1)//正负符号位 double IntegerMultiply(double X, double Y, int N)//参数为大整数 X，Y及它们相同的位数 N { int signBit = signBit(X) * signBit(Y); //确定两数乘积的正负 double x = abs(X); //将两数化为绝对值，之后计算再加入正负号 double y = abs(Y); if ((x == 0) || (y == 0)) //乘数有一个为 0，两数相乘为 0 return 0; if (N == 1) //只剩一位时，返回 return signBit * x * y; else { double A = x / pow(10, N / 2); //X的前N / 2位 double B = x - A * pow(10, N / 2); //X的后N / 2位 double C = y / pow(10, N / 2); //Y的前N / 2位 double D = y - C * pow(10, N / 2); //Y的后N / 2位 double AC = IntegerMultiply(A, C, N / 2); double BD = IntegerMultiply(B, D, N / 2); double ADBC = IntegerMultiply(A - B, D - C, N / 2) + AC + BD; //XY = AC*10^n + [(A - B)(D - C) + AC + BD]10^n / 2 + BD可根据公式化简: if(N % 2 != 0) //位数为单数，会多一位0，位数为双数，不会 return signBit * (AC * pow(10, N-1) + ADBC * pow(10, N / 2) + BD); else return signBit * (AC * pow(10, N) + ADBC * pow(10, N / 2) + BD); } } int main() { int x, y, z, n = 0; cin >> x >> y; z = x; while (z != 0) // 求 X，Y有多少位 { z = z / 10; ++n; } cout << "x = " << x << "\ty =" << y << "\t位数：" << n << "\n"; cout << "x * y = " << IntegerMultiply(x, y, n) << endl; cout << "x * y = " << x * y << endl; return 0; }

【运行结果】

矩阵乘法和Strassen矩阵乘法

普通矩阵乘法

代码思想：以2*2矩阵为例：

C11 = A11 * B11 + A12 * B21

C12 = A11 * B12 + A12 * B22

C21 = A21 * B11 + A22 * B21

C22 = A21 * B12 + A22 * B22

【参考代码】

暴力解法 O(n^3)

#include <iostream> using namespace std; //2X2的矩阵乘法： int main() { int a[4][4] = { 1,1,1,1, 1,1,1,1, 1,1,1,1, 1,1,1,1 }; int b[4][4] = { 1,1,1,1, 1,1,1,1, 1,1,1,1, 1,1,1,1 }; int c[4][4] = { 0 }; //存放乘法后的新矩阵 int i, j, k; int n = 4; for (i = 0; i < n; i++) { for (j = 0; j < n; j++) { for(k = 0; k < n; k++) c[i][j] += a[i][k] * b[k][j]; } } for (i = 0; i < 4; i++) { for (j = 0; j < 4; j++) { cout << c[i][j] << " "; } cout << "\n"; } }

k是怎么来的？

矩阵乘法计算

c[0][0] = a[0][0] * b[0][0] + a[0][1] * b[1][0];//左上元素

c[0][1] = a[0][0] * b[0][1] + a[0][1] * b[1][1];//右上元素

c[1][0] = a[1][0] * b[0][0] + a[1][1] * b[1][0];//左下元素

c[1][1] = a[1][0] * b[0][1] + a[1][1] * b[1][1];//右下元素

标红的数字都是k

【运行结果】

Strassen矩阵乘法

【代码思想】

待补充

【伪代码】

辅助函数伪代码：

// 对应代码中的 Merge_Matrix // 将四个子矩阵 a, b, c, d 合并为一个大矩阵 c0，rows 是子矩阵的边长 Function Merge_Matrix(a, b, c, d, c0, rows): // 合并 A11 (左上) j = 0 For i = 0 to (rows * rows) - 1: If (i % rows == 0) and (i != 0): j = (rows * 2) * (i / rows) c0[j] = a[i] j = j + 1 // 合并 A12 (右上) j = rows For i = 0 to (rows * rows) - 1: If (i % rows == 0) and (i != 0): j = (rows * 2) * (i / rows) + rows c0[j] = b[i] j = j + 1 // 合并 A21 (左下) j = rows * 2 * rows For i = 0 to (rows * rows) - 1: If (i % rows == 0) and (i != 0): j = rows * 2 * rows + (rows * 2) * (i / rows) c0[j] = c[i] j = j + 1 // 合并 A22 (右下) j = rows * 2 * rows + rows For i = 0 to (rows * rows) - 1: If (i % rows == 0) and (i != 0): j = rows * 2 * rows + rows + (rows * 2) * (i / rows) c0[j] = d[i] j = j + 1 // 对应代码中的 Matrix_SUB // 矩阵减法 c0 = x - y Function Matrix_SUB(x, y, c0, rows): For i = 0 to (rows * rows) - 1: c0[i] = x[i] - y[i] // 对应代码中的 Matrix_ADD // 矩阵加法 c0 = x + y Function Matrix_ADD(x, y, c0, rows): For i = 0 to (rows * rows) - 1: c0[i] = x[i] + y[i] // 对应代码中的 Matrix_division // 将大矩阵 c0 拆分为四个小矩阵 a, b, c, d，rows 是大矩阵边长的一半 Function Matrix_division(a, b, c, d, c0, rows): // 提取 A11 (左上) j = 0 For i = 0 to (rows * rows) - 1: If (i % rows == 0) and (i != 0): j = (rows * 2) * (i / rows) a[i] = c0[j] j = j + 1 // 提取 A12 (右上) j = rows For i = 0 to (rows * rows) - 1: If (i % rows == 0) and (i != 0): j = (rows * 2) * (i / rows) + rows b[i] = c0[j] j = j + 1 // 提取 A21 (左下) j = rows * 2 * rows For i = 0 to (rows * rows) - 1: If (i % rows == 0) and (i != 0): j = rows * 2 * rows + (rows * 2) * (i / rows) c[i] = c0[j] j = j + 1 // 提取 A22 (右下) j = rows * 2 * rows + rows For i = 0 to (rows * rows) - 1: If (i % rows == 0) and (i != 0): j = rows * 2 * rows + rows + (rows * 2) * (i / rows) d[i] = c0[j] j = j + 1

核心乘法函数伪代码：

// 对应代码中的 Matrix_Multiply // x, y 是输入矩阵，c0 是结果矩阵，rows 是当前矩阵的边长 Function Matrix_Multiply(x, y, c0, rows): // 声明源矩阵的子矩阵 Array A11, A12, A21, A22 Array B11, B12, B21, B22 // 声明 Strassen 预处理矩阵 S1 - S10 Array s1, s2, s3, s4, s5, s6, s7, s8, s9, s10 // 声明 7 个中间乘积矩阵 P1 - P7 Array p1, p2, p3, p4, p5, p6, p7 // 递归终点 If rows == 1: c0[0] = x[0] * y[0] Else: // 1. 分割矩阵 Matrix_division(A11, A12, A21, A22, x, rows / 2) Matrix_division(B11, B12, B21, B22, y, rows / 2) // 2. 计算 S1 - S10 Matrix_SUB(B12, B22, s1, rows / 2) // s1 = B12 - B22 Matrix_ADD(A11, A12, s2, rows / 2) // s2 = A11 + A12 Matrix_ADD(A21, A22, s3, rows / 2) // s3 = A21 + A22 Matrix_SUB(B21, B11, s4, rows / 2) // s4 = B21 - B11 Matrix_ADD(A11, A22, s5, rows / 2) // s5 = A11 + A22 Matrix_ADD(B11, B22, s6, rows / 2) // s6 = B11 + B22 Matrix_SUB(A12, A22, s7, rows / 2) // s7 = A12 - A22 Matrix_ADD(B21, B22, s8, rows / 2) // s8 = B21 + B22 Matrix_SUB(A11, A21, s9, rows / 2) // s9 = A11 - A21 Matrix_ADD(B11, B12, s10, rows / 2) // s10 = B11 + B12 // 3. 计算 P1 - P7 (递归调用) Matrix_Multiply(A11, s1, p1, rows / 2) // p1 = A11 * s1 Matrix_Multiply(B22, s2, p2, rows / 2) // p2 = B22 * s2 Matrix_Multiply(B11, s3, p3, rows / 2) // p3 = B11 * s3 Matrix_Multiply(A22, s4, p4, rows / 2) // p4 = A22 * s4 Matrix_Multiply(s5, s6, p5, rows / 2) // p5 = s5 * s6 Matrix_Multiply(s7, s8, p6, rows / 2) // p6 = s7 * s8 Matrix_Multiply(s9, s10, p7, rows / 2) // p7 = s9 * s10 // 4. 计算结果的四个象限 c11, c12, c21, c22 // 注意：c11, c12, c21, c22 和 temp1, temp2 在代码中是全局变量 // C11 = P5 + P4 - P2 + P6 -> (P5 + P6) + (P4 - P2) Matrix_ADD(p5, p6, temp1, rows / 2) // temp1 = P5 + P6 Matrix_SUB(p4, p2, temp2, rows / 2) // temp2 = P4 - P2 Matrix_ADD(temp1, temp2, c11, rows / 2) // c11 = temp1 + temp2 // C12 = P1 + P2 Matrix_ADD(p1, p2, c12, rows / 2) // C21 = P3 + P4 Matrix_ADD(p3, p4, c21, rows / 2) // C22 = P5 + P1 - P3 - P7 -> (P5 - P3) + (P1 - P7) Matrix_SUB(p5, p3, temp1, rows / 2) // temp1 = P5 - P3 Matrix_SUB(p1, p7, temp2, rows / 2) // temp2 = P1 - P7 Matrix_ADD(temp1, temp2, c22, rows / 2) // c22 = temp1 + temp2 // 5. 合并结果 Merge_Matrix(c11, c12, c21, c22, c0, rows / 2)

【参考代码】

http://t.csdnimg.cn/HZdrX

#include <iostream> using namespace std; #include<stdlib.h> //此处size指的是n*n矩阵的宽度或者长度n //由于Strassen算法本身的局限性 //两个相乘的矩阵只能是n*n,且n只能是2的幂 //即size为1,2,4,8,16... #define size 4 //矩阵的合并 //就是将A11,A12,A21,A22合并为 // |A11 A12| // |A21 A22| 这样的形式 // c11 c12 c21 c22 c0 rows/2 void Merge_Matrix(int* a, int* b, int* c, int* d, int* c0, int rows) { //rows是子矩阵的宽度，那么合并后矩阵的宽度就是2*rows int i = 0; int j = 0;//此处先合并A11 for (i = 0; i < (rows * rows); i++) { //如果执行了rows次就需要换行，要锁定到合并后矩阵的第二行，所以加上2*rows即可 if ((i % rows == 0) && i != 0) { j = (rows * 2) * (i / rows);//(i/rows)代表需要换多少行；(rows*2)就是行数 c0[j] = a[i]; j++; } else { c0[j] = a[i];//divide反过来就是合并，合并到c0 j++; } } //此处是A12的首元素，令索引等于子矩阵的那个函数 j = rows; for (i = 0; i < (rows * rows); i++) { if ((i % rows == 0) && i != 0) { //换行要换到第二部分(右上)，所以需要再加一个rows j = (rows * 2) * (i / rows) + rows; c0[j] = b[i]; j++; } else { c0[j] = b[i]; j++; } } //此处是A21的首元素，令索引等于子矩阵的那个函数 j = rows * 2 * rows; for (i = 0; i < (rows * rows); i++) { if ((i % rows == 0) && i != 0) { j = rows * 2 * rows + (rows * 2) * (i / rows); c0[j] = c[i]; j++; } else { c0[j] = c[i]; j++; } } //此处是A22的首元素，令索引等于子矩阵的那个函数 j = rows * 2 * rows + rows; for (i = 0; i < (rows * rows); i++) { if ((i % rows == 0) && i != 0) { j = rows * 2 * rows + rows + (rows * 2) * (i / rows); c0[j] = d[i]; j++; } else { c0[j] = d[i]; j++; } } } //两个n*n矩阵的减法，是x-y void Matrix_SUB(int* x, int* y, int* c0, int rows) { int i = 0; for (i = 0; i < (rows * rows); i++) { c0[i] = x[i] - y[i]; } } //两个n*n矩阵的加法，是x+y void Matrix_ADD(int* x, int* y, int* c0, int rows) { int i = 0; for (i = 0; i < (rows * rows); i++) { c0[i] = x[i] + y[i]; } } //将一个矩阵 // |A11 A12| // |A21 A22| //分解为四个矩阵 //A11,A12,A21,A22 //这个函数其实是Matrix_merge的一个逆运算 //逻辑是一致的，只需要交换赋值位置即可 // A11/B11 A12/B12 A21/B21 A22/B22 a rows/2 void Matrix_division(int* a, int* b, int* c, int* d, int* c0, int rows) { int i = 0; int j = 0; for (i = 0; i < (rows * rows); i++)//rows=2，rows*rows = size = 4 { if ((i % rows == 0) && i != 0)//i=2时，跳转到第二行第一个元素 { j = (rows * 2) * (i / rows);//j=4 a[i] = c0[j];//j=4 j++;//j=5 } else { a[i] = c0[j];//j=5，第二行第二个元素，也就是第5个 j++; } } j = rows;//j=2开始 for (i = 0; i < (rows * rows); i++) { if ((i % rows == 0) && i != 0)//i=2时，跳转到第二行第三个 { j = (rows * 2) * (i / rows) + rows;//j=6 b[i] = c0[j];//j=6 j++;//j=7 } else { b[i] = c0[j];//j=7，第二行第四个元素 j++; } } j = rows * 2 * rows;//j=8 for (i = 0; i < (rows * rows); i++)//i=2时，跳转到第四行第一个元素 { if ((i % rows == 0) && i != 0) { j = rows * 2 * rows + (rows * 2) * (i / rows);//j=12 c[i] = c0[j];//j=12 j++;//j=13 } else { c[i] = c0[j];//j=13，第四行第二个元素 j++; } } j = rows * 2 * rows + rows;//j=10 for (i = 0; i < (rows * rows); i++) { if ((i % rows == 0) && i != 0)//i=2时，跳转到第四行第三个元素 { j = rows * 2 * rows + rows + (rows * 2) * (i / rows);//j=14 d[i] = c0[j];//j=14 j++;//j=15 } else { d[i] = c0[j];//j=15，第四行第四个元素 j++; } } } //定义四个子矩阵，结果矩阵的子矩阵 int c11[300]; int c12[300]; int c21[300]; int c22[300]; //代码实现需要的暂存矩阵 int temp1[300]; int temp2[300]; //矩阵乘法的函数 a b 结果矩阵 size void Matrix_Multiply(int* x, int* y, int* c0, int rows) { //定义八个子矩阵，两个乘数矩阵各四个 int A11[300]; int A12[300]; int A21[300]; int A22[300]; int B11[300]; int B12[300]; int B21[300]; int B22[300]; //Strassen方法需要的中间矩阵 //预处理矩阵S1--S10等式： int s1[300]; int s2[300]; int s3[300]; int s4[300]; int s5[300]; int s6[300]; int s7[300]; int s8[300]; int s9[300]; int s10[300]; //P1--P7等式 int p1[300]; int p2[300]; int p3[300]; int p4[300]; int p5[300]; int p6[300]; int p7[300]; //rows==1说明矩阵只有一个元素，是递归的结束，递归树的终点 if (rows == 1) { c0[0] = x[0] * y[0]; } else { //将矩阵分割 Matrix_division(A11, A12, A21, A22, x, rows / 2); Matrix_division(B11, B12, B21, B22, y, rows / 2); //按照Strassen方法，进行矩阵预处理 //S1 = B12 - B22 Matrix_SUB(B12, B22, s1, rows / 2); //S2 = A11 + A12 Matrix_ADD(A11, A12, s2, rows / 2); //S3 = A21 + A22 Matrix_ADD(A21, A22, s3, rows / 2); //S4 = B21 - B11 Matrix_SUB(B21, B11, s4, rows / 2); //S5 = A11 + A22 Matrix_ADD(A11, A22, s5, rows / 2); //S6 = B11 + B22 Matrix_ADD(B11, B22, s6, rows / 2); //S7 = A12 - A22 Matrix_SUB(A12, A22, s7, rows / 2); //S8 = B21 + B22 Matrix_ADD(B21, B22, s8, rows / 2); //S9 = A11 - A21 Matrix_SUB(A11, A21, s9, rows / 2); //S10 = B11 + B12 Matrix_ADD(B11, B12, s10, rows / 2); //按照Strassen方法，进行矩阵乘法上的递归 (共7条) //P1 = A11 * S1 Matrix_Multiply(A11, s1, p1, rows / 2); //P2 = B22 * S2 Matrix_Multiply(B22, s2, p2, rows / 2); //P3 = B11 * S3 Matrix_Multiply(B11, s3, p3, rows / 2); //P4 = A22 * S4 Matrix_Multiply(A22, s4, p4, rows / 2); //P5 = S5 * S6 Matrix_Multiply(s5, s6, p5, rows / 2); //P6 = S7 * S8 Matrix_Multiply(s7, s8, p6, rows / 2); //P7 = S9 * S10 Matrix_Multiply(s9, s10, p7, rows / 2); //按照Strassen方法，进行结果矩阵的计算 //得到c11,c12,c21,c22 //C11 = P5 + P4 - P2 + P6 -> (P5 + P6) + (P4 - P2) //temp1 = P5 + P6 Matrix_ADD(p5, p6, temp1, rows / 2); //temp2 = P4 - P2 Matrix_SUB(p4, p2, temp2, rows / 2); //C11 = temp1 + temp2 Matrix_ADD(temp1, temp2, c11, rows / 2); //C12 = P1 + P2 Matrix_ADD(p1, p2, c12, rows / 2); //C21 = P3 + P4 Matrix_ADD(p3, p4, c21, rows / 2); //C22 = P5 + P1 - P3 - P7 -> (P5 - P3) + (P1 - P7) //temp1 = P5 - P3 Matrix_SUB(p5, p3, temp1, rows / 2); //temp2 = P1 - P7 Matrix_SUB(p1, p7, temp2, rows / 2); //C22 = temp1 + temp2 Matrix_ADD(temp1, temp2, c22, rows / 2); //最后将c11,c12,c21,c22合并为C Merge_Matrix(c11, c12, c21, c22, c0, rows / 2); } } int main() { int i = 0; int* a = NULL; int* b = NULL; int* c = NULL; //动态生成三个n*n矩阵 a = (int*)malloc(size * size * sizeof(int)); b = (int*)malloc(size * size * sizeof(int)); c = (int*)malloc(size * size * sizeof(int)); if (a != NULL && b != NULL) { for (i = 0; i < (size * size); i++) { a[i] = 1; b[i] = 1; } } //打印乘数矩阵A和B printf("A matrix is:\n\n"); if (a != NULL) { for (i = 0; i < (size * size); i++) { if (((i + 1) % size) == 0) { //printf("%6d\n", a[i]); cout << "\t " << a[i] << "\n"; } else { //printf("%6d", a[i]); cout << "\t " << a[i]; } } } printf("B matrix is:\n\n"); if (b != NULL) { for (i = 0; i < (size * size); i++) { if (((i + 1) % size) == 0) { //printf("%6d\n", b[i]); cout << "\t " << b[i] << "\n"; } else { //printf("%6d", b[i]); cout << "\t " << b[i]; } } } //进行矩阵乘法 Matrix_Multiply(a, b, c, size); //打印结果矩阵 printf("C matrix is:\n\n"); if (c != NULL) { for (i = 0; i < (size * size); i++) { if (((i + 1) % size) == 0) { cout << "\t " << c[i] << "\n"; //printf("%6d\n", c[i]); } else { cout << "\t " << c[i]; //printf("%6d", c[i]); } } } //释放动态生成的矩阵 free(a); free(b); free(c); return 0; }

【运行结果】