发布时间 : 星期三 文章数据结构课程设计之稀疏矩阵实现与应用1更新完毕开始阅读1a5a4f7e0912a2161479297b
cout.width(4);
cout << T.data[k++].e; } else {
cout.width(4); cout << \ } }
cout << endl; }
return true;
}// 输出矩阵，按标准格式输出
bool TransposeSMatrix() // 求矩阵的转置矩阵 {
TSMatrix M, T; //定义预转置的矩阵 InPutTSMatrix(M, 0); //输入矩阵 int num[MAXROW + 1];
int cpot[MAXROW + 1]; // 构建辅助数组 int q, p, t; T.tu = M.tu; T.mu = M.nu; T.nu = M.mu; if (T.tu) {
for (int col = 1; col <= M.nu; col++) num[col] = 0; for (t = 1; t <= M.tu; t++) ++num[M.data[t].j]; cpot[1] = 1;
for (int i = 2; i <= M.nu; i++) cpot[i] = cpot[i - 1] + num[i - 1]; // 素在三元组中出现的位置
for (p = 1; p <= M.tu; p++) {
int col = M.data[p].j; q = cpot[col];
T.data[q].i = M.data[p].j; T.data[q].j = M.data[p].i; T.data[q].e = M.data[p].e; ++cpot[col]; } }
cout << \输入矩阵的转置矩阵为\ OutPutSMatrix(T); return true; }
求出每一列中非零元
bool Count(RLSMatrix &T) { int num[MAXROW + 1];
for (int row = 1; row <= T.mu; row++) num[row] = 0; for (int col = 1; col <= T.tu; col++) ++num[T.data[col].i]; T.rpos[1] = 1;
for (int i = 2; i <= T.mu; i++) T.rpos[i] = T.rpos[i - 1] + num[i - 1]; // 求取每一行中非零元素在三元组中出现的位置
return true; }
bool MultSMatrix() // 两个矩阵相乘 {
RLSMatrix M, N, Q; // 构建三个带“链接信息”的三元组表示的数组 InPutTSMatrix(M, 1); // 用普通三元组形式输入数组 InPutTSMatrix(N, 1); Count(M); Count(N);
cout << \输入的两矩阵的乘矩阵为：\ if (M.nu != N.mu) return false; Q.mu = M.mu; Q.nu = N.nu;
Q.tu = 0; // Q初始化
int ctemp[MAXROW + 1]; // 辅助数组 int arow, tp, p, brow, t, q, ccol;
if (M.tu * N.tu) // Q是非零矩阵 {
for (arow = 1; arow <= M.mu; arow++) {
///memset(ctemp,0,N.nu);
for (int x = 1; x <= N.nu; x++) // 当前行各元素累加器清零 ctemp[x] = 0;
Q.rpos[arow] = Q.tu + 1; // 当前行的首个非零元素在三元组中的位置为此行前所有非零元素+1
if (arow < M.mu) tp = M.rpos[arow + 1]; else tp = M.tu + 1;
for (p = M.rpos[arow]; p < tp; p++) // 对当前行每个非零元素进行操作 {
brow = M.data[p].j; // 在N中找到i值也操作元素的j值相等的行 if (brow < N.mu) t = N.rpos[brow + 1]; else t = N.tu + 1;
for (q = N.rpos[brow]; q < t; q++) // 对找出的行当每个非零元素进行操作 {
ccol = N.data[q].j;
ctemp[ccol] += M.data[p].e * N.data[q].e; // 将乘得到对应值放在相应的元素累加器里面 } }
for (ccol = 1; ccol <= Q.nu; ccol++) // 对已经求出的累加器中的值压缩到Q中 if (ctemp[ccol]) {
if (++Q.tu > MAXSIZE) return false; Q.data[Q.tu].e = ctemp[ccol]; Q.data[Q.tu].i = arow; Q.data[Q.tu].j = ccol; } } }
OutPutSMatrix(Q); return true; }
bool CreateSMatrix_OL(CrossList & M)// 创建十字链表 {
int x, y, m;
cout << \请输入矩阵的行，列，及非零元素个数\ cin >> M.mu >> M.nu >> M.tu;
if (!(M.rhead = (OLink*) malloc((M.mu + 1) * sizeof (OLink)))) exit(0); if (!(M.chead = (OLink*) malloc((M.nu + 1) * sizeof (OLink)))) exit(0); for (x = 0; x <= M.mu; x++)
M.rhead[x] = NULL; // 初始化各行，列头指针，分别为NULL for (x = 0; x <= M.nu; x++) M.chead[x] = NULL;
cout << \请按三元组的格式输入数组：\ for (int i = 1; i <= M.tu; i++) {
cin >> x >> y >> m; // 按任意顺序输入非零元，（普通三元组形式输入） OLink p, q;
if (!(p = (OLink) malloc(sizeof (OLNode)))) exit(0); // 开辟新节点，用来存储输入的新元素 p->i = x; p->j = y; p->e = m;
if (M.rhead[x] == NULL || M.rhead[x]->j > y) {
p->right = M.rhead[x]; M.rhead[x] = p; } else {
for (q = M.rhead[x]; (q->right) && (q->right->j < y); q = q->right); // 查找节点在行表中的插入位置
p->right = q->right;
q->right = p; // 完成行插入 }
if (M.chead[y] == NULL || M.chead[y]->i > x) {
p->down = M.chead[y]; M.chead[y] = p; } else {
for (q = M.chead[y]; (q->down) && (q->down->i < x); q = q->down); // 查找节点在列表中的插入位置
p->down = q->down; q->down = p; // 完成列插入
} }
return true; }
bool OutPutSMatrix_OL(CrossList T)// 输出十字链表，用普通数组形式输出 {
for (int i = 1; i <= T.mu; i++) {
OLink p = T.rhead[i];
for (int j = 1; j <= T.nu; j++) {
if ((p) && (j == p->j)) {
cout << setw(3) << p->e; p = p->right; } else
cout << setw(3) << \ }
cout << endl; }
return true;