#include <string> #include <iostream> using namespace std;
template<class T> struct element { int row, col; T item; };
const int MaxTerm = 100;
template<class T> class SparseMatrix { public: SparseMatrix() {}; SparseMatrix(int intmu, int intnu, int inttu, element<T> datatemp[]); ~SparseMatrix() {}; element<T> GetMatrix(int intnumber); void Prt(); void Trans1(SparseMatrix<T> &B); void Trans2(SparseMatrix<T> A, SparseMatrix<T> &B); private: element<T> data[MaxTerm]; int mu, nu, tu; };
template<class T> SparseMatrix<T>::SparseMatrix(int intmu, int intnu, int inttu, element<T>datatemp[]) { if (inttu > MaxTerm) throw"构造函数的初始化参数不正确"; mu = intmu; nu = intnu; tu = inttu; for (int i = 0; i < intnu; ++i) { data[i] = datatemp[i]; } }
template<class T> element<T> SparseMatrix<T>::GetMatrix(int intnumber) { if (intnumber >= tu || intnumber < 0) throw"输入位置不正确"; return data[i]; }
template<class T> void SparseMatrix<T>::Prt() { for (int i = 0; i < tu; ++i) { cout << data[i].col << " " << data[i].row << " " << data[i].item << "\n"; } }
template<class T> void SparseMatrix<T>::Trans1(SparseMatrix<T> &B) { int pb, pa; B.mu = this->nu; B.nu = this->mu; B.tu = this->tu; if (B.tu > 0) { pb = 0; for (int col = 0; col < this->nu; col++) for (pa = 0; pa < this->tu; pa++) if (this->data[pa].col == col) { B.data[pb].row = this->data[pa].col; B.data[pb].col = this->data[pa].row; B.data[pb].item = this->data[pa].item; pb++; } } }
template<class T> void SparseMatrix<T>::Trans2(SparseMatrix<T> A, SparseMatrix<T> &B) { int i, j, k, num[MaxTerm], cpot[MaxTerm]; B.mu = A.mu; B.nu = A.mu; B.tu = A.tu; if (B.tu > 0) { for (i = 0; i < A.nu; ++i) num[i] = 0; for (i = 0; i < A.nu; ++i) { j = A.data[i].col; num[j]++; } cpot[0] = 0; for (i = 1; i < A.nu; i++) cpot[i] = cpot[i - 1] + num[i - 1]; for (i = 0; i < A.tu; ++i) { j = A.data[i].col; k = cpot[j]; B.data[k].row = A.data[i].col; B.data[k].col = A.data[i].row; B.data[k].item = A.data[i].item; cpot[j]++; } } }
void Function_1(int n) { int Ma[MaxTerm][MaxTerm]; memset(Ma, 0, sizeof(Ma)); int max, row = 1, col, row_, col_; max = n * n; col = n / 2 + 1; Ma[row][col] = 1; for (int i = 2; i <= max; ++i) { if (row == 1)row_ = n; else row_ = row - 1; if (col == n)col_ = 1; else col_ = col + 1; if (Ma[row_][col_] != 0) { row_ = row + 1; col_ = col; } Ma[row_][col_] = i; row = row_, col = col_; } for (int i = 1; i <= n; ++i) { for (int j = 1; j <= n; ++j) { printf("%2d ", Ma[i][j]); } cout << "\n"; } }
void Function_2(int n) { int Ma[MaxTerm][MaxTerm]; memset(Ma, 0, sizeof(Ma)); int tem = 1, Sum = n*n + 1; for (int i = 1; i <= n; ++i) { for (int j = 1; j <= n; ++j) { Ma[i][j] = tem; tem++; } } if (n != 4) { for (int i = 1, j = 1; i <= n&&j <= n; i++, j++)Ma[i][j] = Sum - Ma[i][j]; for (int i = 1, j = n / 2; i <= n / 2 && j >= 1; i++, j--) Ma[i][j] = Sum - Ma[i][j]; for (int i = n / 2 + 1, j = n; i <= n && j >= n / 2 + 1; i++, j--) Ma[i][j] = Sum - Ma[i][j]; for (int i = 1, j = n; i <= n &&j >= 0; i++, j--) Ma[i][j] = Sum - Ma[i][j]; for (int i = n / 2 + 1, j = 1; i <= n && j <= n / 2; ++i, ++j) Ma[i][j] = Sum - Ma[i][j]; for (int i = 1, j = n / 2 + 1; i <= n / 2 && j <= n; i++, j++) Ma[i][j] = Sum - Ma[i][j]; } else { for (int i = 1, j = 1; i <= n&&j <= n; i++, j++)Ma[i][j] = Sum - Ma[i][j]; for (int i = 1, j = n; i <= n &&j >= 0; i++, j--) Ma[i][j] = Sum - Ma[i][j]; } for (int i = 1; i <= n; ++i) { for (int j = 1; j <= n; ++j) { printf("%2d ", Ma[i][j]); } cout << "\n"; } }
void Fun(int n , int Ma[MaxTerm][MaxTerm]) { int max, row = 1, col, row_, col_; max = n * n; col = n / 2 + 1; Ma[row][col] = 1; for (int i = 2; i <= max; ++i) { if (row == 1)row_ = n; else row_ = row - 1; if (col == n)col_ = 1; else col_ = col + 1; if (Ma[row_][col_] != 0) { row_ = row + 1; col_ = col; } Ma[row_][col_] = i; row = row_, col = col_; } }
void Function_3(int n) { int Ma[MaxTerm][MaxTerm] , k , tem; memset(Ma, 0, sizeof(Ma)); k = n / 2 , tem = k * k; int k_ , chan; k_ = (n - 2) / 4; //赋初值 Fun(k, Ma); for (int i = k+1, p = 1; i <= n; ++i, ++p) for (int j = k+1, l = 1; j <= n; ++j, ++l) Ma[i][j] = Ma[p][l] + tem; tem += tem; for (int i = 1, p = 1; i <= k; ++i, ++p) for (int j = k + 1, l = 1; j <= n; ++j, ++l) Ma[i][j] = Ma[p][l] + tem; tem += tem; tem -= k*k; for (int i = k + 1, p = 1; i <= n; ++i, ++p) for (int j = 1, l = 1; j <= k; ++j, ++l) Ma[i][j] = Ma[p][l] + tem; //赋值结束 //左区域交换 for (int i = 0; i < k_; ++i) { Ma[3 * k_+2][k_+1+i]^= Ma[k_+1][k_ + 1+i]; Ma[k_+1][k_ + 1+i] ^= Ma[3 * k_+2][k_ + 1+i] ; Ma[3 * k_+2][k_ + i+1] ^= Ma[k_+1][k_ + 1+i]; }// for (int i = 1; i <= 2 * k_ + 1; ++i) { if (i != k_ + 1) { for (int j = 1; j <= k_; ++j) { chan = Ma[i][j]; Ma[i][j] = Ma[i + 2 * k_ + 1][j]; Ma[i + 2 * k_ + 1][j] = chan; } } } //结束 //右区域交换 for (int i = 1 , j = k_ +1 ; i <= 4 * k_ + 2; ++i) { for (int p = 0; p < k_ - 1; p++) { Ma[i][j - p] ^= Ma[i + 2*k_ + 1][j - p]; Ma[i + 2 * k_ + 1][j - p] ^= Ma[i][j - p]; Ma[i][j - p] ^= Ma[i + 2 * k_ + 1][j - p]; } } // for (int i = 1; i <= n; ++i) { for (int j = 1; j <= n; ++j) { printf("%2d ", Ma[i][j]); } cout << "\n"; } }
void MagicMatrix(int n) { if (n & 1) Function_1(n); else if (n % 4 == 0) Function_2(n); else Function_3(n); }
int main() { try { element<int> elementtemp3, elementtemp2, elementtemp; elementtemp.col = 0; elementtemp.row = 0; elementtemp.item = 15; elementtemp2.col = 1; elementtemp2.row = 2; elementtemp2.item = 16; elementtemp3.col = 1; elementtemp3.row = 0; elementtemp3.item = 17; element<int> A[3]; A[0] = elementtemp; A[1] = elementtemp2; A[2] = elementtemp3; SparseMatrix<int> sparsematrixB; SparseMatrix<int> sparsematrixA(3, 3, 3, A); cout << "源三元组顺序表如下:" << "\n"; sparsematrixA.Prt(); sparsematrixA.Trans1(sparsematrixB); cout << "使用顺序取、顺序存转置算法转置后的三元组顺序表如下:" << "\n"; sparsematrixB.Prt(); sparsematrixA.Trans2(sparsematrixA, sparsematrixB); cout << "使用顺序取、直接存转置算法后的三元组顺序表如下:" << "\n"; sparsematrixB.Prt(); } catch (char *e) { cout << e; } int n; cout << "输入魔方阵的阶数:" << endl; cin >> n; MagicMatrix(n); system("pause"); return 0; }
