關於在矩陣乘法中執行Strassen算法的C編程中的分段錯誤

我在寫一個代碼，其目的是使用Strassen算法乘以兩個稠密矩陣。主代碼是一個遞歸函數，其基本情況是當兩個矩陣的大小是2×2時，因此矩陣的乘法只是實數的乘法。如果不滿足基本情況，則通過再次調用遞歸函數計算用於計算最終乘法結果的七個矩陣，矩陣的大小除以一半。然而，當試圖運行這段代碼時，我遇到了段錯誤，但我無法弄清楚爲什麼。我使用gdb調試器，似乎在某些時候我得到NULL temp1和C1，但我不知道爲什麼會發生這種情況。另外，for循環中使用的計數器超出了限制（它們應該被限制在n/2以內）。最後，這是遞歸執行Strassen算法的正確方法嗎？這是我的代碼。關於在矩陣乘法中執行Strassen算法的C編程中的分段錯誤

#include "assignment2.h" 

void denseMatrixMult(int ** A, int ** B, int *** resultMatrix, int n) 
{ 
    if(n==2) 
    { 
     int M0,M1,M2,M3,M4,M5,M6; 
     M0=(A[0][0]+A[1][1])*(B[0][0]+B[1][1]); 
     M1=(A[1][0]+A[1][1])*B[0][0]; 
     M2=A[0][0]*(B[0][1]-B[1][1]); 
     M3=A[1][1]*(B[1][0]-B[0][0]); 
     M4=(A[0][0]+A[0][1])*B[1][1]; 
     M5=(A[1][0]-A[0][0])*(B[0][0]+B[0][1]); 
     M6=(A[0][1]-A[1][1])*(B[1][0]+B[1][1]); 
     int** temp; 
     initMatrix(&temp,2); 
     resultMatrix=&temp; 
     *(resultMatrix)[0][0]=M0+M3-M4+M6; 
     *(resultMatrix)[0][1]=M2+M4; 
     *(resultMatrix)[1][0]=M1+M3; 
     *(resultMatrix)[1][1]=M0-M1+M2+M5; 
     /*free(freeMatrix(temp);*/ 
     return; 
    } 
    else 
    { 
     int a,b,c,d,e,f,g,h; 
     int** N0; 
     int** N1; 
     int** N2; 
     int** N3; 
     int** N4; 
     int** N5; 
     int** N6; 
     int** zero; 
     int** C1; 
     int** C2; 
     int** C3; 
     int** C4; 
     initMatrix(&N0,n/2); 
     initMatrix(&N1,n/2); 
     initMatrix(&N2,n/2); 
     initMatrix(&N3,n/2); 
     initMatrix(&N4,n/2); 
     initMatrix(&N5,n/2); 
     initMatrix(&N6,n/2); 
     initMatrix(&zero,n/2); 
     denseMatrixMult(sum(A,A,0,0,n/2,n/2,n/2),sum(B,B,0,0,n/2,n/2,n/2),&N0,n/2); 
     denseMatrixMult(sum(A,A,n/2,0,n/2,n/2,n/2),sum(B,zero,0,0,0,0,n/2),&N1,n/2); 
     denseMatrixMult(sum(A,zero,0,0,0,0,n/2),sub(B,B,0,n/2,n/2,n/2,n/2),&N2,n/2); 
     denseMatrixMult(sum(A,zero,n/2,n/2,0,0,n/2),sub(B,B,n/2,0,0,0,n/2),&N3,n/2); 
     denseMatrixMult(sum(A,A,0,0,0,n/2,n/2),sum(B,zero,n/2,n/2,0,0,n/2),&N4,n/2); 
     denseMatrixMult(sub(A,A,n/2,0,0,0,n/2),sum(B,B,0,0,0,n/2,n/2),&N5,n/2); 
     denseMatrixMult(sub(A,A,0,n/2,n/2,n/2,n/2),sum(B,B,n/2,0,n/2,n/2,n/2),&N6,n/2); 
     C1=sum(sub(sum(N0,N3,0,0,0,0,n/2),N4,0,0,0,0,n/2),N6,0,0,0,0,n/2); 
     C2=sum(N2,N4,0,0,0,0,n/2); 
     C3=sum(N1,N3,0,0,0,0,n/2); 
     C4=sum(sum(sub(N0,N1,0,0,0,0,n/2),N2,0,0,0,0,n/2),N5,0,0,0,0,n/2); 
     int** temp1; 
     initMatrix(&temp1,n); 
     resultMatrix=&temp1; 
     for(a=0;a<n/2;a++) 
     { 
      for(b=0;b<n/2;b++) 
      { 
       (*resultMatrix)[a][b]=C1[a][b]; 
      } 
     } 
     for(c=n/2;c<n;c++) 
     { 
      for(d=0;d<n/2;d++) 
      { 
       (*resultMatrix)[c][d]=C3[c-n/2][d]; 
      } 
     } 
     for(e=0;e<n/2;e++) 
     { 
      for(f=n/2;f<n;f++) 
      { 
       (*resultMatrix)[e][f]=C2[e][f-n/2]; 
      } 
     } 
     for(g=n/2;g<n;g++) 
     { 
      for(h=n/2;h<n;h++) 
      { 
       (*resultMatrix)[g][h]=C4[g-n/2][h-n/2]; 
      } 
      } 
      /*freeMatrix(N0); 
      freeMatrix(N1); 
      freeMatrix(N2); 
      freeMatrix(N3); 
      freeMatrix(N4); 
      freeMatrix(N5); 
      freeMatrix(N6); 
      freeMatrix(C1); 
      freeMatrix(C2); 
      freeMatrix(C3); 
      freeMatrix(C4);*/ 


    } 
} 
int **sum(int ** A, int ** B, int x1, int y1, int x2, int y2, int n) 
{ 
    int i,j,k; 

    int ** res=(int**)malloc(n*sizeof(int*)); 
    if(res!=NULL) 
    { 
     for(i=0;i<n;i++) 
     { 
      res[i]=(int*)malloc(n*sizeof(int)); 
     } 

     for(j=0;j<n;j++) 
     { 
      for(k=0;k<n;k++) 
      { 
       res[j][k]=A[x1+j][y1+k]+B[x2+j][y2+k]; 
      } 
     } 
    } 
    return res; 

} 
int **sub(int **A, int **B, int x1, int y1, int x2, int y2, int n) 
{ 
    int i,j,k; 

    int ** res=(int**)malloc(n*sizeof(int*)); 
    if(res!=NULL) 
    { 
     for(i=0;i<n;i++) 
     { 
      res[i]=(int*)malloc(n*sizeof(int)); 
     } 

     for(j=0;j<n;j++) 
     { 
      for(k=0;k<n;k++) 
      { 
       res[j][k]=A[x1+j][y1+k]-B[x2+j][y2+k]; 
      } 
     } 
    } 
    return res; 
} 
void initMatrix(int ***mat,int n) 
{ 
    int i,j,k; 
    int ** Mat=(int**)malloc(n*sizeof(int*)); 
    for(i=0;i<n;i++) 
    { 
     Mat[i]=(int*)malloc(n*sizeof(int)); 
    } 
    for(j=0;i<n;i++) 
    { 
     for(k=0;k<n;i++) 
     { 
      Mat[j][k]=0; 
     } 
    } 
    *mat=Mat; 
} 

int **readMatrix(char * filename) 
{ 
    int i,j,k; 
    int **mat=(int**)malloc(MATSIZE*sizeof(int*)); 
    for(i=0;i<MATSIZE;i++) 
    { 
     mat[i]=(int*)malloc(MATSIZE*sizeof(int)); 
    } 
    FILE *fp=fopen(filename,"r"); 
    for(j=0;j<MATSIZE;j++) 
    { 
     for(k=0;k<MATSIZE;k++) 
     { 
      fscanf(fp,"%d",&mat[j][k]); 
     } 
    } 
    fclose(fp); 
    return mat; 

} 
void freeMatrix(int n, int ** matrix) 
{ 
    int i; 
    for(i=0;i<n;i++) 
    { 
     free(matrix[i]); 
    } 
    free(matrix); 
} 

void printMatrix(int n, int ** A) 
{ 
    int i,j; 
    for(i=0;i<n;i++) 
    { 
     for(j=0;j<n;j++) 
     { 
      printf("%d",A[i][j]); 
     } 
    } 
} 
#include "assignment2.h" 

void p1(void) 
{ 
    int **matrix; 
    initMatrix(&matrix,MATSIZE); 
    printMatrix(MATSIZE,matrix); 
    freeMatrix(MATSIZE, matrix); 
} 

void p2(void) 
{ 
    int ** matrix1=readMatrix("matrix1.txt"); 
    printMatrix(MATSIZE,matrix1); 
    freeMatrix(MATSIZE, matrix1); 
} 

void p3a(void) 
{ 
    int ** matrix1=readMatrix("matrix1.txt"); 
    int ** matrix2=readMatrix("matrix2.txt"); 
    int ** sumMatrix = sum(matrix1, matrix2, 1, 1, 0, 1, 3); 
    printMatrix(MATSIZE,matrix1); 
    printMatrix(MATSIZE,matrix2); 
    printMatrix(3,sumMatrix); 
    freeMatrix(MATSIZE, matrix1); 
    freeMatrix(MATSIZE, matrix2); 
    freeMatrix(3, sumMatrix); 
} 

void p3b(void) 
{ 
    int ** matrix1=readMatrix("matrix1.txt"); 
    int ** matrix2=readMatrix("matrix2.txt"); 
    int ** subMatrix = sub(matrix1, matrix2, 1, 1, 0, 1, 3); 
    printMatrix(MATSIZE,matrix1); 
    printMatrix(MATSIZE,matrix2); 
    printMatrix(3,subMatrix); 
    freeMatrix(MATSIZE, matrix1); 
    freeMatrix(MATSIZE, matrix2); 
    freeMatrix(3, subMatrix); 
} 

void p4(void) 
{ 
    char dataFileMat1[]="matrix1.txt"; 
    char dataFileMat2[]="matrix2.txt"; 
    int ** matrix1=readMatrix(dataFileMat1); 
    int ** matrix2=readMatrix(dataFileMat2); 
    int ** resultingMatrix; 
    denseMatrixMult(matrix1, matrix2, &resultingMatrix, MATSIZE); 
    printMatrix(MATSIZE,resultingMatrix); 
    freeMatrix(MATSIZE,resultingMatrix); 
    freeMatrix(MATSIZE,matrix1); 
    freeMatrix(MATSIZE,matrix2); 
} 

int main(int argc, char *argv[]) 
{ 
    if(argc < 2) 
    { 
     printf("Expecting at least one argument. Please try again\n"); 
    } 
    else if(argc==2) 
    { 
     if(atoi(argv[1])==3) 
     { 
      printf("Expecting two arguments for this part. Please try again.\n"); 
     } 
     else 
     { 
      if(atoi(argv[1])==1) 
      { 
       p1(); 
      } 
      else if(atoi(argv[1])==2) 
      { 
       p2(); 
      } 
      else if(atoi(argv[1])==4) 
      { 
       p4(); 
      } 
      else 
      { 
       printf("Incorrect argument supplied.\n"); 
      } 
     } 
    } 
    else if(argc==3) 
    { 
     if(atoi(argv[1])!=3) 
     { 
      printf("Expecting two arguments only for Part 3. Please try again.\n"); 
     } 
     else 
     { 
      if(atoi(argv[2])==1) 
      { 
       p3a(); 
      } 
      else if(atoi(argv[2])==2) 
      { 
       p3b(); 
      } 
     } 
    } 
    else 
    { 
     printf("The argument supplied is %s\n", argv[1]); 
    } 
}

來源

2017-02-21 yifan zhang

Stackoverflow不是「轉儲代碼並要求其他人爲您調試它」。特別是不是300多行代碼，其中有一兩個字母變量。建議您使用[valgrind]（http://valgrind.org）這樣的工具來幫助您縮小根本原因。 – kaylum

似乎問題出現在第20行和第47行。 –

的失敗free讓這堆管理已損壞的嫌疑。可能的原因是超出範圍寫入訪問分配的內存。爲什麼不簡化矩陣的分配？

只有一個malloc()需要分配。爲此，您可以分配適當大小的一維數組。

您可以使用分配的數組連續存儲矩陣元素（行的行）。讀取和寫入訪問必須以i * N + j（i ...行索引，j ...列索引，N ...列數）的形式完成。
你可以使用一些C-cast-magic，甚至可以用它作爲二維數組。

予製備的小樣本來演示此：

#include <stdio.h> 
#include <stdlib.h> 

enum { N = 4 }; 

int main(int argc, char **argv) 
{ 
    int i, n; 
    /* allocation of an array with size NxN: */ 
    double *arr = (double*)malloc(N * N * sizeof (double)); 
    /* initialization of array (with some illustrative values) */ 
    for (i = 0, n = N * N; i < n; ++i) { 
    int row = i/N, col = i % N; 
    arr[i] = (double)(row + col * 0.1); 
    } 
    /* show contents */ 
    printf("arr[]:\n"); 
    for (i = 0; i < N; ++i) { 
    int j; 
    for (j = 0; j < N; ++j) { 
     printf("%s%.1f", j ? "\t" : "", arr[i * N + j]); 
    } 
    printf("\n"); 
    } 
    /* how this is used as two-dimensional array */ 
    { double (*mat)[N] = (double(*)[N])arr; 
    printf("mat[][]:\n"); 
    for (i = 0; i < N; ++i) { 
     int j; 
     for (j = 0; j < N; ++j) { 
     printf("%s%.1f", j ? "\t" : "", mat[i][j]); 
     } 
     printf("\n"); 
    } 
    } 
    /* clean-up */ 
    free(arr); 
    /* done */ 
    return 0; 
}

編寫和用gcc上cygwin的測試：

$ gcc -o test-mat test-mat.c 

$ ./test-mat 
arr[]: 
0.0  0.1  0.2  0.3 
1.0  1.1  1.2  1.3 
2.0  2.1  2.2  2.3 
3.0  3.1  3.2  3.3 
mat[][]: 
0.0  0.1  0.2  0.3 
1.0  1.1  1.2  1.3 
2.0  2.1  2.2  2.3 
3.0  3.1  3.2  3.3

類型double (*)[N]必須被理解爲「一個一個的地址大小爲N的三維數組「。括號可能看起來令人驚訝，但是必要的。（沒有，編譯器會將其讀作「一維地址數組」）什麼不是我的意圖。）

來源

2017-02-21 06:00:30 Scheff

謝謝先生，我會檢查一下。 –

關於在矩陣乘法中執行Strassen算法的C編程中的分段錯誤

回答

相關問題