第五章稀疏矩阵三元组表示

注意：

程序：加法、乘法不调用。

#include

#include //稀疏矩阵的三元组顺序表存储表示

#define MAX_SIZE 12500 //假设非零元个数的最大值为12500

#define OK 1

#define ERROR 0

typedef int ElemType;

typedef int Status;

typedef struct{

int i,j; //该零元的行下标和列下标

ElemType e; //非零元素值

}Triple;//三元组结构

typedef struct{

Triple data[MAX_SIZE+1]; //非零元三元组表，data[0]未用

int mu,nu,tu; //矩阵的行数、列数和非零元个数

}TSMatrix;

//函数声明

Status CreateTSMatrix(TSMatrix &M);

void DestroyTSMatrix(TSMatrix &M);

void PrintTSMatrix(TSMatrix M);

void PrintTSMatrix1(TSMatrix M);

void CopyTSMatrix(TSMatrix M,TSMatrix &T);

int comp(int c1,int c2);

Status AddTSMatrix(TSMatrix M,TSMatrix N,TSMatrix &Q);

Status SubtTSMatrix(TSMatrix M,TSMatrix N,TSMatrix &Q);

Status MultTSMatrix(TSMatrix M,TSMatrix N,TSMatrix &Q);

Status TransposeTSMatrix(TSMatrix M, TSMatrix &T);

//主函数

void main()

{

TSMatrix A,B,C; printf("创建矩阵A：\n"); CreateTSMatrix(A); PrintTSMatrix(A); printf("由矩阵A复制矩阵B：\n"); CopyTSMatrix(A,B); PrintTSMatrix1(B); DestroyTSMatrix(B); printf("销毁矩阵B后：\n"); PrintTSMatrix1(B); printf("重新创建矩阵B：（与矩阵A的行、列数相同，行、列分别为%d,%d）\n",A.mu,A.nu);

//

//

} CreateTSMatrix(B); PrintTSMatrix1(B); AddTSMatrix(A,B,C); printf("矩阵C1(A+B)：\n"); PrintTSMatrix1(C); SubtTSMatrix(A,B,C); printf("矩阵C2(A-B)：\n"); PrintTSMatrix1(C); TransposeTSMatrix(A,C); printf("矩阵C3(A的转置)：\n"); PrintTSMatrix1(C); printf("创建矩阵A2："); CreateTSMatrix(A); PrintTSMatrix1(A); printf("创建矩阵B2：（行数应与矩阵A的列数相同=%d）\n",A.nu); CreateTSMatrix(B); PrintTSMatrix1(B); MultTSMatrix(A,B,C); printf("矩阵C5(A*B)：\n"); PrintTSMatrix1(C);

//1.创建稀疏矩阵M

Status CreateTSMatrix(TSMatrix &M)

{

int i,m,n; ElemType e; Status k; printf("请输入矩阵的行数，列数，非零元素数："); scanf("%d%d%d",&M.mu,&M.nu,&M.tu); if(M.tu>MAX_SIZE) return ERROR; M.data[0].i=0;//为以下比较顺序做准备 for(i=1;i

{

printf("请按行序顺序输入第%d个非零元素所在的行（1~%d）、列（1~%d）、元素值",i,M.mu,M.nu);

scanf("%d%d%d",&m,&n,&e); k=0; if(mM.mu||nM.nu)//行或列超出范围 k=1; if((m

或列的顺序有错

}

//2.销毁稀疏矩阵M

void DestroyTSMatrix(TSMatrix &M) //&一定要有

{

} M.mu=M.nu=M.tu=0; } return OK; k=1; }while(k); //当k为0时，跳出while循环 M.data[i].i=m; M.data[i].j=n; M.data[i].e=e;

//3.输出稀疏矩阵M

void PrintTSMatrix(TSMatrix M)

{

int i; printf("%d行%d列%d个非零元素\n",M.mu,M.nu,M.tu); printf("行 列 元素值\n"); for(i=1;i

}

//按矩阵形式输出M

void PrintTSMatrix1(TSMatrix M)

{

int i,j,k=1;

Triple *p=M.data; p++; //p指向第一个非零元素 for(i=1;ii==i&&p->j==j) //p指向非零元，且p所指元素为当前处理 { 元素 printf("%3d",p->e);//输出p所指元素的值 p++;//p指向下一个元素 k++;//计数器+1 } else //p所指元素不是当前处理元素 printf("%3d",0);//输出0

printf("\n");

}

}

//4.由稀疏矩阵M复制得到T

void CopyTSMatrix(TSMatrix M,TSMatrix &T)

{

} T=M;

//5.求稀疏矩阵的和Q=M+N，M和N的行数和列数相等

//AddTSMatrix()中要用到

int comp(int c1,int c2)

{

}

Status AddTSMatrix(TSMatrix M,TSMatrix N,TSMatrix &Q)

{

int m=1,n=1,q=0; if(M.mu!=N.mu||M.nu!=N.nu) //M、N两稀疏矩阵行或列数不同 return ERROR; Q.mu=M.mu; Q.nu=M.nu; while(m

if(Q.data[q].e==0) //元素值为0，不存入压缩矩阵 q--; break; case 1: Q.data[++q]=N.data[n++]; } break; case 1: Q.data[++q]=N.data[n++];//将矩阵N的当前元素值赋给矩阵Q } } while(mMAX_SIZE)//非零元素个数太多 return ERROR;

return OK;

}

//6.求稀疏矩阵的差Q=M-N，M和N的行数和列数相等

Status SubtTSMatrix(TSMatrix M,TSMatrix N,TSMatrix &Q)

{

} int i; if(M.mu!=N.mu||M.nu!=N.nu) return ERROR; for(i=1;i

//7.求稀疏矩阵的乘积Q=M*N，M的列数和N的行数相等

Status MultTSMatrix(TSMatrix M,TSMatrix N,TSMatrix &Q)

{

int i,j; ElemType *Nc,*Tc; TSMatrix T; //临时矩阵 if(M.nu!=N.mu) return ERROR; T.nu=M.mu; //临时矩阵T是Q的转置矩阵 T.mu=N.nu;

T.tu=0;

Nc=(ElemType*)malloc((N.mu+1)*sizeof(ElemType));//Nc为矩阵N一列的临时数组（非压缩，【0】不用）

Tc=(ElemType*)malloc((M.nu+1)*sizeof(ElemType));//Tc为矩阵T一行的临时数组（非压缩，【0】不用）

if(!Nc||!Tc) //创建临时数组不成功

exit(ERROR);

for(i=1;i

{

for(j=1;j

Nc[j]=0; //矩阵Nc的初值为0

for(j=1;j

Tc[j]=0; //临时数组Tc的初值为0，【0】不用

for(j=1;j

Tc[M.data[j].i]+=M.data[j].e*Nc[M.data[j].j];//Tc中存N的第i列与M相乘

的结果

for(j=1;jMAX_SIZE) //非零元素个数太多 return ERROR; TransposeTSMatrix(T,Q); //将T的装置赋给Q DestroyTSMatrix(T); //销毁临时矩阵T free(Tc); //释放动态数组Tc和Nc free(Nc); return OK;

}

//8.求稀疏矩阵M的转置矩阵T TransposeTSMatrix(TSMatrix M,TSMatrix &T)

Status TransposeTSMatrix(TSMatrix M, TSMatrix &T)

{ // 算法5.1

// 采用三元组顺序表存储表示，求稀疏矩阵M的转置矩阵T int p, q, col; T.mu = M.nu; T.nu = M.mu; T.tu = M.tu; if (T.tu) { q = 1; for (col=1; col

for (p=1; p

运行结果：

注意：

程序：加法、乘法不调用。

#include

#include //稀疏矩阵的三元组顺序表存储表示

#define MAX_SIZE 12500 //假设非零元个数的最大值为12500

#define OK 1

#define ERROR 0

typedef int ElemType;

typedef int Status;

typedef struct{

int i,j; //该零元的行下标和列下标

ElemType e; //非零元素值

}Triple;//三元组结构

typedef struct{

Triple data[MAX_SIZE+1]; //非零元三元组表，data[0]未用

int mu,nu,tu; //矩阵的行数、列数和非零元个数

}TSMatrix;

//函数声明

Status CreateTSMatrix(TSMatrix &M);

void DestroyTSMatrix(TSMatrix &M);

void PrintTSMatrix(TSMatrix M);

void PrintTSMatrix1(TSMatrix M);

void CopyTSMatrix(TSMatrix M,TSMatrix &T);

int comp(int c1,int c2);

Status AddTSMatrix(TSMatrix M,TSMatrix N,TSMatrix &Q);

Status SubtTSMatrix(TSMatrix M,TSMatrix N,TSMatrix &Q);

Status MultTSMatrix(TSMatrix M,TSMatrix N,TSMatrix &Q);

Status TransposeTSMatrix(TSMatrix M, TSMatrix &T);

//主函数

void main()

{

TSMatrix A,B,C; printf("创建矩阵A：\n"); CreateTSMatrix(A); PrintTSMatrix(A); printf("由矩阵A复制矩阵B：\n"); CopyTSMatrix(A,B); PrintTSMatrix1(B); DestroyTSMatrix(B); printf("销毁矩阵B后：\n"); PrintTSMatrix1(B); printf("重新创建矩阵B：（与矩阵A的行、列数相同，行、列分别为%d,%d）\n",A.mu,A.nu);

//

//

} CreateTSMatrix(B); PrintTSMatrix1(B); AddTSMatrix(A,B,C); printf("矩阵C1(A+B)：\n"); PrintTSMatrix1(C); SubtTSMatrix(A,B,C); printf("矩阵C2(A-B)：\n"); PrintTSMatrix1(C); TransposeTSMatrix(A,C); printf("矩阵C3(A的转置)：\n"); PrintTSMatrix1(C); printf("创建矩阵A2："); CreateTSMatrix(A); PrintTSMatrix1(A); printf("创建矩阵B2：（行数应与矩阵A的列数相同=%d）\n",A.nu); CreateTSMatrix(B); PrintTSMatrix1(B); MultTSMatrix(A,B,C); printf("矩阵C5(A*B)：\n"); PrintTSMatrix1(C);

//1.创建稀疏矩阵M

Status CreateTSMatrix(TSMatrix &M)

{

int i,m,n; ElemType e; Status k; printf("请输入矩阵的行数，列数，非零元素数："); scanf("%d%d%d",&M.mu,&M.nu,&M.tu); if(M.tu>MAX_SIZE) return ERROR; M.data[0].i=0;//为以下比较顺序做准备 for(i=1;i

{

printf("请按行序顺序输入第%d个非零元素所在的行（1~%d）、列（1~%d）、元素值",i,M.mu,M.nu);

scanf("%d%d%d",&m,&n,&e); k=0; if(mM.mu||nM.nu)//行或列超出范围 k=1; if((m

或列的顺序有错

}

//2.销毁稀疏矩阵M

void DestroyTSMatrix(TSMatrix &M) //&一定要有

{

} M.mu=M.nu=M.tu=0; } return OK; k=1; }while(k); //当k为0时，跳出while循环 M.data[i].i=m; M.data[i].j=n; M.data[i].e=e;

//3.输出稀疏矩阵M

void PrintTSMatrix(TSMatrix M)

{

int i; printf("%d行%d列%d个非零元素\n",M.mu,M.nu,M.tu); printf("行 列 元素值\n"); for(i=1;i

}

//按矩阵形式输出M

void PrintTSMatrix1(TSMatrix M)

{

int i,j,k=1;

Triple *p=M.data; p++; //p指向第一个非零元素 for(i=1;ii==i&&p->j==j) //p指向非零元，且p所指元素为当前处理 { 元素 printf("%3d",p->e);//输出p所指元素的值 p++;//p指向下一个元素 k++;//计数器+1 } else //p所指元素不是当前处理元素 printf("%3d",0);//输出0

printf("\n");

}

}

//4.由稀疏矩阵M复制得到T

void CopyTSMatrix(TSMatrix M,TSMatrix &T)

{

} T=M;

//5.求稀疏矩阵的和Q=M+N，M和N的行数和列数相等

//AddTSMatrix()中要用到

int comp(int c1,int c2)

{

}

Status AddTSMatrix(TSMatrix M,TSMatrix N,TSMatrix &Q)

{

int m=1,n=1,q=0; if(M.mu!=N.mu||M.nu!=N.nu) //M、N两稀疏矩阵行或列数不同 return ERROR; Q.mu=M.mu; Q.nu=M.nu; while(m

if(Q.data[q].e==0) //元素值为0，不存入压缩矩阵 q--; break; case 1: Q.data[++q]=N.data[n++]; } break; case 1: Q.data[++q]=N.data[n++];//将矩阵N的当前元素值赋给矩阵Q } } while(mMAX_SIZE)//非零元素个数太多 return ERROR;

return OK;

}

//6.求稀疏矩阵的差Q=M-N，M和N的行数和列数相等

Status SubtTSMatrix(TSMatrix M,TSMatrix N,TSMatrix &Q)

{

} int i; if(M.mu!=N.mu||M.nu!=N.nu) return ERROR; for(i=1;i

//7.求稀疏矩阵的乘积Q=M*N，M的列数和N的行数相等

Status MultTSMatrix(TSMatrix M,TSMatrix N,TSMatrix &Q)

{

int i,j; ElemType *Nc,*Tc; TSMatrix T; //临时矩阵 if(M.nu!=N.mu) return ERROR; T.nu=M.mu; //临时矩阵T是Q的转置矩阵 T.mu=N.nu;

T.tu=0;

Nc=(ElemType*)malloc((N.mu+1)*sizeof(ElemType));//Nc为矩阵N一列的临时数组（非压缩，【0】不用）

Tc=(ElemType*)malloc((M.nu+1)*sizeof(ElemType));//Tc为矩阵T一行的临时数组（非压缩，【0】不用）

if(!Nc||!Tc) //创建临时数组不成功

exit(ERROR);

for(i=1;i

{

for(j=1;j

Nc[j]=0; //矩阵Nc的初值为0

for(j=1;j

Tc[j]=0; //临时数组Tc的初值为0，【0】不用

for(j=1;j

Tc[M.data[j].i]+=M.data[j].e*Nc[M.data[j].j];//Tc中存N的第i列与M相乘

的结果

for(j=1;jMAX_SIZE) //非零元素个数太多 return ERROR; TransposeTSMatrix(T,Q); //将T的装置赋给Q DestroyTSMatrix(T); //销毁临时矩阵T free(Tc); //释放动态数组Tc和Nc free(Nc); return OK;

}

//8.求稀疏矩阵M的转置矩阵T TransposeTSMatrix(TSMatrix M,TSMatrix &T)

Status TransposeTSMatrix(TSMatrix M, TSMatrix &T)

{ // 算法5.1

// 采用三元组顺序表存储表示，求稀疏矩阵M的转置矩阵T int p, q, col; T.mu = M.nu; T.nu = M.mu; T.tu = M.tu; if (T.tu) { q = 1; for (col=1; col

for (p=1; p

运行结果：


相关内容

  • 基于三元组表表示的稀疏矩阵的快速转置算法及其改进

    • 基于三元组表表示的稀疏矩阵的快速转置算法及其改进 摘 要:介绍基于三元组表表示的稀疏矩阵的快速转置算法,此算法在转置前需要先确定原矩阵中各列第一个非零元在转置矩阵中的位置,在此使用2个数组作为辅助空间,为了减少算法所需的辅助空间,通过引入2个简单变量提出一种改进算法.该改进算法在时间复杂度保持不变的 ...

  • 稀疏矩阵三元组实现矩阵转置算法实验报告

    • 实验三 稀疏矩阵的三元组表示实现矩阵转置算法 学院 专业 班 学号 姓名 一．实习目的 1. 掌握稀疏矩阵的三元组顺序表存储表示: 2. 掌握稀疏矩阵三元组表示的传统转置算法的实现: 3. 掌握稀疏矩阵三元组表示的快速转置算法的实现: 二．实习内容 1. 稀疏矩阵的按三元组形式输入,即按行序输入非零 ...

  • 稀疏矩阵的运算

    • 数 据 结 构 课 程 设 计 稀疏矩阵的运算 学 生 姓 名: 学 号: 指 导 教 师: 完 成 日 期: 目录: 1.分析问题和确定解决方案 „„„„„„„„„„ 3 1.1问题描述 „„„„„„„„„„„ 3 1.2 输入的形式和输入值的范围 „„„„„„„„ 3 1.3 输出的形式 „„„ ...

  • 稀疏矩阵快速转置

    • 题目:假设稀疏矩阵A采用三元组表表示,编写程序实现该矩阵的快速转置 要求:输入一个稀疏矩阵A,由程序将其转换成三元组表存储:转置后的三元组 表,由程序将其转换成矩阵形式后输出. 二.概要设计 ⒈ 为实现上述算法,需要线性表的抽象数据类型: ADT SparseMatrix { 数据对象:D={aij ...

  • 4.1稀疏矩阵运算器

    • 稀疏矩阵运算器 一．实验目的 使读者能深入研究数组的存储表示和实现技术 二．实验内容 [问题描述]稀疏矩阵是指那些多数元素为零的矩阵,利用"稀疏"特点进行存储和计算可以大大节省存储空间,提高计算效率.实现一个能进行稀疏矩阵基本运算的运算器. [基本要求]以"带行逻辑链接 ...

  • [数据结构]教学大纲

    • <数据结构>教学大纲 Data Structure 课程编号:J6110G0003 课程性质:学科基础课程 适用专业:计算机科学与技术.网络工程.数字媒体技术 先行课:计算机科学导论.离散数学.高级语言程序设计: 后续课:无 . 学分数:5 主讲教师:任燕.王命延.冯豫华.周石林.王玮立 ...

  • [数据结构课程设计]课程设计方案

    • <算法与数据结构课程设计>方案 Course Design of Data Structure 适用专业:计算机科学与技术专业 本科 课程代码:B08233004 一.课程设计的性质和目的 软件设计能力培养对学生是很重要.通过数据结构的学习,使学生对软件编程能力有一定的提高.数据结构学习 ...

  • 中国地质大学数据结构实习报告

    • Practice Report for Data Structures and Algorithm Analysis Data Structures Course Report Candidate: Student Number: Major: Communication Engineering S ...

  • 太原理工大学数据结构试题库及答案

    • 数据结构试题库及答案 第一章 概论 一.选择题 1.研究数据结构就是研究( D). A.数据的逻辑结构 B.数据的存储结构 C.数据的逻辑结构和存储结构 D.数据的逻辑结构.存储结构及其基本操作 2.算法分析的两个主要方面是(A). A. 空间复杂度和时间复杂度 B. 正确性和简单性 C. 可读性和 ...

热门内容

标签

篝火晚会主持词   清明节放假通知范文   英文书信范文   讲座邀请函范文   创业计划书格式范文   计算机实习计划范文   文员月总结范文   房屋变更申请书范文   qq群聚会通知范文   药店辞职报告范文   社会调研方案范文   煤矿安全总结范文   心内门诊病历模板   工程管理实习日记