[已解决]分块矩阵转置

晴雨皆宜

开卷有益，多多益善·····

人造人

这个你还是没有说对不对
不过你没有说错，而且从你说的内容来看，应该是对的，那我就认为是对的了

#include <algorithm>
#include <iostream>

using namespace std;

void TransposeMatri(int **array, int n) { //全部转置
    for(int i = 0; i < n; i++)
        for(int j = 0; j < n; j++) {
            if(j > i) //主副三角
                swap(array[i][j], array[j][i]);
        }
}

void Block_transpose(int **array, int n) { //分块转置
    int k = 2;
    for(int i = 0; i < n; i += k)
        for(int j = 0; j < n; j += k)
            TransposeMatri((int **)((int *)array + i * n + j), k);
}

int main() {
    int **a = new int *[4];
    for(int i = 0; i < 4; i++)
        a[i] = new int[4];
    for(int i = 0; i < 4; i++) {
        for(int j = 0; j < 4; j++) {
            a[i][j] = i * 4 + j;
        }
    }
    for(int i = 0; i < 4; i++) {
        for(int j = 0; j < 4; j++)
            cout << a[i][j] << ' ';
        cout << endl;
    }
    Block_transpose(a, 4);
    cout << "---------------------" << endl;
    /*
    for(int i = 0; i < 4; i++)
        for(int j = 0; j < 4; j++)
            cout << a[i][j] << ' ';
    cout << endl;
    */
    for(int i = 0; i < 4; i++) {
        for(int j = 0; j < 4; j++)
            cout << a[i][j] << ' ';
        cout << endl;
    }
    // 释放一定要写，不写释放的代码在一些环境下会报错的
    for(int i = 0; i < 4; i++)
        delete[] a[i];
    delete[] a;
    return 0;
}

这个代码是错的，因为你进行了强制类型转换，可以通过编译了，但是类型不对
地址值是一样的，但是类型不对
应该转成下面这样

#include <algorithm>
#include <iostream>

using namespace std;

void TransposeMatri(int **array, int n) { //全部转置
    for(int i = 0; i < n; i++)
        for(int j = 0; j < n; j++) {
            if(j > i) //主副三角
                //swap(array[i][j], array[j][i]);
                swap((*(int (*)[n][n])(array))[i][j], (*(int (*)[n][n])(array))[j][i]);
        }
}

void Block_transpose(int **array, int n) { //分块转置
    int k = 2;
    for(int i = 0; i < n; i += k)
        for(int j = 0; j < n; j += k)
            TransposeMatri((int **)((int *)array + i * n + j), k);
}

int main() {
    int **a = new int *[4];
    for(int i = 0; i < 4; i++)
        a[i] = new int[4];
    for(int i = 0; i < 4; i++) {
        for(int j = 0; j < 4; j++) {
            a[i][j] = i * 4 + j;
        }
    }
    for(int i = 0; i < 4; i++) {
        for(int j = 0; j < 4; j++)
            cout << a[i][j] << ' ';
        cout << endl;
    }
    Block_transpose(a, 4);
    cout << "---------------------" << endl;
    /*
    for(int i = 0; i < 4; i++)
        for(int j = 0; j < 4; j++)
            cout << a[i][j] << ' ';
    cout << endl;
    */
    for(int i = 0; i < 4; i++) {
        for(int j = 0; j < 4; j++)
            cout << a[i][j] << ' ';
        cout << endl;
    }
    // 释放一定要写，不写释放的代码在一些环境下会报错的
    for(int i = 0; i < 4; i++)
        delete[] a[i];
    delete[] a;
    return 0;
}

TransposeMatri((int **)((int *)array + i * n + j), k);

我一开始确实是在这里改的，但是我发现这里修改对 int a[4][4];，这样的数组无效，所以修改了

swap((*(int (*)[n][n])(array))[i][j], (*(int (*)[n][n])(array))[j][i]);

但是这样依然不对，因为这样的转换要求数组中的值是连续存放的，通过 new 这样的形式创建出来的数组，数组中存储的值不是连续的

#include <algorithm>
#include <iostream>

using namespace std;

void TransposeMatri(int **array, int n) { //全部转置
    for(int i = 0; i < n; i++)
        for(int j = 0; j < n; j++) {
            if(j > i) //主副三角
                //swap(array[i][j], array[j][i]);
                swap((*(int (*)[n][n])(array))[i][j], (*(int (*)[n][n])(array))[j][i]);
        }
}

void Block_transpose(int **array, int n) { //分块转置
    int k = 2;
    for(int i = 0; i < n; i += k)
        for(int j = 0; j < n; j += k)
            TransposeMatri((int **)((int *)array + i * n + j), k);
}

int main() {
    /*
    int **a = new int *[4];
    for(int i = 0; i < 4; i++)
        a[i] = new int[4];
    */
    int a[4][4];
    for(int i = 0; i < 4; i++) {
        for(int j = 0; j < 4; j++) {
            a[i][j] = i * 4 + j;
        }
    }
    for(int i = 0; i < 4; i++) {
        for(int j = 0; j < 4; j++)
            cout << a[i][j] << ' ';
        cout << endl;
    }
    //Block_transpose(a, 4);
    Block_transpose((int **)a, 4);
    cout << "---------------------" << endl;
    /*
    for(int i = 0; i < 4; i++)
        for(int j = 0; j < 4; j++)
            cout << a[i][j] << ' ';
    cout << endl;
    */
    for(int i = 0; i < 4; i++) {
        for(int j = 0; j < 4; j++)
            cout << a[i][j] << ' ';
        cout << endl;
    }
    /*
    // 释放一定要写，不写释放的代码在一些环境下会报错的
    for(int i = 0; i < 4; i++)
        delete[] a[i];
    delete[] a;
    */
    return 0;
}

$ ./main
0 1 2 3 
4 5 6 7 
8 9 10 11 
12 13 14 15 
---------------------
0 2 1 4 
3 5 6 7 
8 10 9 12 
11 13 14 15 
$ 

这样就能运行了，不会在运行的时候报错，然后停止运行了
但是结果依然不对
因为这个数组在内存中是这样存储的
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
是线性的，0 后面存储 1，1 后面存储 2，2 后面存储 3，。。。
第一个子矩阵中，你要互换的是 1 和 4，但是 1 和 4 并不挨着
要么进行计算，算出 4 的地址，要么创建一个临时数组，让 1 和 4 挨着
我选择了后者

#include <algorithm>
#include <iostream>

using namespace std;

void TransposeMatri(int **array, int n) { //全部转置
    for(int i = 0; i < n; i++)
        for(int j = 0; j < n; j++) {
            if(j > i) //主副三角
                //swap(array[i][j], array[j][i]);
                swap((*(int (*)[n][n])(array))[i][j], (*(int (*)[n][n])(array))[j][i]);
        }
}

void Block_transpose(int **array, int n) { //分块转置
    /*
    int k = 2;
    for(int i = 0; i < n; i += k)
        for(int j = 0; j < n; j += k)
            TransposeMatri((int **)((int *)array + i * n + j), k);
    */
    int k = 2;
    for(int i = 0; i < n; i += k)
        for(int j = 0; j < n; j += k) {
            int a[k][k];
            for(int y = 0; y < k; ++y) {
                for(int x = 0; x < k; ++x) {
                    a[y][x] = (*(int (*)[n][n])array)[i + y][j + x];
                }
            }
            //TransposeMatri((int **)((int *)array + i * n + j), k);
            TransposeMatri((int **)a, k);
            for(int y = 0; y < k; ++y) {
                for(int x = 0; x < k; ++x) {
                    (*(int (*)[n][n])array)[i + y][j + x] = a[y][x];
                }
            }
        }
}

int main() {
    /*
    int **a = new int *[4];
    for(int i = 0; i < 4; i++)
        a[i] = new int[4];
    */
    int a[4][4];
    for(int i = 0; i < 4; i++) {
        for(int j = 0; j < 4; j++) {
            a[i][j] = i * 4 + j;
        }
    }
    for(int i = 0; i < 4; i++) {
        for(int j = 0; j < 4; j++)
            cout << a[i][j] << ' ';
        cout << endl;
    }
    //Block_transpose(a, 4);
    Block_transpose((int **)a, 4);
    cout << "---------------------" << endl;
    /*
    for(int i = 0; i < 4; i++)
        for(int j = 0; j < 4; j++)
            cout << a[i][j] << ' ';
    cout << endl;
    */
    for(int i = 0; i < 4; i++) {
        for(int j = 0; j < 4; j++)
            cout << a[i][j] << ' ';
        cout << endl;
    }
    /*
    // 释放一定要写，不写释放的代码在一些环境下会报错的
    for(int i = 0; i < 4; i++)
        delete[] a[i];
    delete[] a;
    */
    return 0;
}

$ ./main
0 1 2 3 
4 5 6 7 
8 9 10 11 
12 13 14 15 
---------------------
0 4 2 6 
1 5 3 7 
8 12 10 14 
9 13 11 15 
$ 

a[y][x] = (*(int (*)[n][n])array)[i + y][j + x];

其实这样也需要计算 4 的地址，然后读取 4 的值到 临时数组
我认为创建临时数组比较好，所以选择了创建临时数组

人造人

其实对于调试程序，输入和输出是很重要的，不知道输出就不知道努力的方向，不知道应该把程序调试成什么样子，不知道应该通过调试让程序输出什么
而输出依赖于输入
正确的输出依赖于正确的输入，知道了输入和输出问题就简单了，因为你知道正确的输出，就知道了要把程序调试成什么样子

万千只cnm

人造人 发表于 2021-9-21 10:34
这个你还是没有说对不对
不过你没有说错，而且从你说的内容来看，应该是对的，那我就认为是对的了

”通过 new 这样的形式创建出来的数组，数组中存储的值不是连续的“
请问这句话啥意思 跟c的malloc不一样吗 不都是申请的一整块空间嘛

swap((*(int (*)[n][n])(array))[i][j], (*(int (*)[n][n])(array))[j][i]);

这是先array转换为一个指向二维数组的指针然后解引用吗

“这个代码是错的，因为你进行了强制类型转换，可以通过编译了，但是类型不对
地址值是一样的，但是类型不对”
如果说array本来是个指针数组名  我强制转换为int** 为啥会不对

万千只cnm

jhq999 发表于 2021-9-21 06:58
这个流程，而且成员越多，小矩阵互换越多

是不不止要分成4个子矩阵换吗
我感觉正中间的子矩阵也要互换才能

人造人

万千只cnm 发表于 2021-9-21 12:49
”通过 new 这样的形式创建出来的数组，数组中存储的值不是连续的“
请问这句话啥意思 跟c的malloc不一 ...

#include <iostream>

int main() {
    int a[4][4];
    for(int i = 0; i < 4; i++) {
        for(int j = 0; j < 4; j++) {
            a[i][j] = i * 4 + j;
        }
    }
    for(int i = 0; i < 4; i++) {
        for(int j = 0; j < 4; j++) {
            std::cout << &a[i][j] << ": " << a[i][j] << std::endl;
        }
    }
    return 0;
}
/*
0xffffcbd0: 0
0xffffcbd4: 1
0xffffcbd8: 2
0xffffcbdc: 3
0xffffcbe0: 4
0xffffcbe4: 5
0xffffcbe8: 6
0xffffcbec: 7
0xffffcbf0: 8
0xffffcbf4: 9
0xffffcbf8: 10
0xffffcbfc: 11
0xffffcc00: 12
0xffffcc04: 13
0xffffcc08: 14
0xffffcc0c: 15
*/

#include <iostream>

int main() {
    int **a = new int *[4];
    for(int i = 0; i < 4; i++) {
        a[i] = new int[4];
        for(int j = 0; j < 4; j++) {
            a[i][j] = i * 4 + j;
        }
    }
    for(int i = 0; i < 4; i++) {
        for(int j = 0; j < 4; j++) {
            std::cout << &a[i][j] << ": " << a[i][j] << std::endl;
        }
    }
    for(int i = 0; i < 4; i++) delete[] a[i];
    delete[] a;
    return 0;
}
/*
0x800038ca0: 0
0x800038ca4: 1
0x800038ca8: 2
0x800038cac: 3
0x800038cc0: 4      // 这里应该是 0x800038cb0 才是连续的
0x800038cc4: 5
0x800038cc8: 6
0x800038ccc: 7
0x80004b140: 8      // 0x800038cd0，如果从数组开始，这个地址是 0x800038cc0
0x80004b144: 9
0x80004b148: 10
0x80004b14c: 11
0x80004b160: 12     // 0x80004b150, 0x800038cd0
0x80004b164: 13
0x80004b168: 14
0x80004b16c: 15
*/

人造人

万千只cnm 发表于 2021-9-21 12:49
”通过 new 这样的形式创建出来的数组，数组中存储的值不是连续的“
请问这句话啥意思 跟c的malloc不一 ...

地址一样，类型不对

#include <iostream>

void func(int **a) {
    for(int i = 0; i < 4; i++) {
        std::cout << a[i] << std::endl;
    }
    /*
    for(int i = 0; i < 4; i++) {
        for(int j = 0; j < 4; j++) {
            std::cout << a[i][j] << std::endl;
        }
    }
    */
}

int main() {
    int a[4][4];
    for(int i = 0; i < 4; i++) {
        for(int j = 0; j < 4; j++) {
            a[i][j] = i * 4 + j;
        }
    }
    func((int **)a);
    return 0;
}
/*
0x100000000
0x300000002
0x500000004
0x700000006
*/

这个输出结果你可能已经明白了，但是看了下面这个输出结果，你肯定明白了

#include <iostream>

void func(long long **a) {
    for(int i = 0; i < 4; i++) {
        std::cout << a[i] << std::endl;
    }
    /*
    for(int i = 0; i < 4; i++) {
        for(int j = 0; j < 4; j++) {
            std::cout << a[i][j] << std::endl;
        }
    }
    */
}

int main() {
    long long a[4][4];
    for(int i = 0; i < 4; i++) {
        for(int j = 0; j < 4; j++) {
            a[i][j] = i * 4 + j;
        }
    }
    func((long long **)a);
    return 0;
}
/*
0
0x1
0x2
0x3
*/

一次解引用得到的就已经是数组中存储的值了，然后再对这个值解引用？
如果这个值是 0，那就是对 0 解引用
对于第二个代码，a[i][j] 就是对 0x00000000、0x00000001、0x00000002、0x00000003
这 4 个地址解引用

#include <iostream>

void func(long long **a) {
    for(int i = 0; i < 4; i++) {
        std::cout << a[i] << std::endl;
    }
    for(int i = 0; i < 4; i++) {
        for(int j = 0; j < 4; j++) {
            std::cout << a[i][j] << std::endl;
        }
    }
}

int main() {
    long long a[4][4];
    for(int i = 0; i < 4; i++) {
        for(int j = 0; j < 4; j++) {
            a[i][j] = i * 4 + j;
        }
    }
    func((long long **)a);
    return 0;
}
/*
0
0x1
0x2
0x3
Segmentation fault (core dumped)
*/

人造人

人造人

地址一样，但是类型不对

#include <iostream>

int main() {
    long long a[4][4] = {
        {123, 456, 789, -1},
        {223, 556, 889, -2},
        {323, 656, 989, -3},
        {423, 756, 189, -4}
    };
    long long **x = (long long **)a;
    std::cout << a[0] << std::endl;
    std::cout << x[0] << std::endl;
    std::cout << (long long)a[0] << std::endl;
    std::cout << (long long)x[0] << std::endl;
    return 0;
}
/*
0xffffcb90
0x7b
4294953872
123
*/

万千只cnm

人造人 发表于 2021-9-21 13:51
地址一样，但是类型不对

道理我是懂呀。
但我是new申请的数组不算严格的数组吧 new申请的二维数组不就是指针形式吗
为什么swap还要换呢

人造人

万千只cnm 发表于 2021-9-21 21:44
道理我是懂呀。
但我是new申请的数组不算严格的数组吧 new申请的二维数组不就是指针形式吗
为什么swap ...

没明白你的问题

万千只cnm

人造人 发表于 2021-9-21 22:22
没明白你的问题

 swap(array[i][j], array[j][i]);

array本来就是一个int ** 指针呀  指向new申请的空间
不是二维数组名 ，不存在强制转换类型吧？

人造人

万千只cnm 发表于 2021-9-22 18:14
array本来就是一个int ** 指针呀  指向new申请的空间
不是二维数组名 ，不存在强制转换类型吧？

TransposeMatri((int **)((int *)array + i * n + j), k);

你在这里进行了强制类型转换
还有，你可以写一个示例代码说明你的问题吗？我还是不理解你的问题
示例代码越短小越好，能够说明你的问题就好了

你这样描述，我也没有什么概念，还是尽量用代码说话比较好

万千只cnm

人造人 发表于 2021-9-22 18:29
你在这里进行了强制类型转换
还有，你可以写一个示例代码说明你的问题吗？我还是不理解你的问题
示 ...

array本身就是一个指针

 int **a = new int *[4];

用这种方式来形成二维数组
我为了定位到 下一个子矩阵  i*n就是一行的总地址，j就列的地址
array+行+列 就是子矩阵的首地址，然后转换为 int**  就跟原形式一样了  
但你说了new申请的空间不一定连续 我就知道我错了

人造人

万千只cnm 发表于 2021-9-22 18:43
array本身就是一个指针

用这种方式来形成二维数组

嗯，也就是说这个问题你明白了？

万千只cnm

人造人 发表于 2021-9-22 19:25
嗯，也就是说这个问题你明白了？