当前位置:首页 >> 计算机软件及应用 >>

课程设计实验报告 稀疏矩阵应用


数据结构课程设计
《数据结构》课程设计

一. 题目:
稀疏矩阵应用( 人完成) 稀疏矩阵应用(限 1 人完成) 要求:实现三元组,十字链表下的稀疏矩阵的加、转、乘的实现。 (1)稀疏矩阵的存储 (2)稀疏矩阵加法 (3)矩阵乘法 (4)矩阵转置

二. 算法思想描述:
1.需求分析 (1)设计函数建立稀疏矩阵,初始化值。 (2)设计函数输出稀疏矩阵的值。 (3)构造函数进行两个稀疏矩阵相加,输出最终的稀疏矩阵。 (4)构造函数进行两个稀疏矩阵的相乘,输出最终的稀疏矩阵。 (5)构造函数进行稀疏矩阵的转置,并输出结果。 (6)退出系统。

1.算法概述:首先用两个结构体来定义十字链表元素: typedef struct OLNode{ int i,j; int e; struct OLNode *right,*down; }OLNode,*OLink; OLNode 结构为链表结点,i,j,e 分别表示稀疏矩阵中元素的行,列和值。

typedef struct { int mu,nu,tu; //行数 mu,列数 nu,非零元素的个数 tu OLink *rhead,*chead; }CrossList; CrossList 结构用于连接起各个结点, mu,nu,tu 分别表示整个矩阵的行数列数和非零元 素的个数。 整个程序包含 CreateSMatix_OL(用于创建十字链表) ,SMatrix_ADD(十字链表相加) , ShowMAtrix(十字链表显示),MultSMatrix_OL(十字链表相乘) ,TurnSMatrix_OL(十字链 表转置) ,DestroySMatrix_OL(十字链表销毁)六个函数。 CreateSMatix_OL 的功能如下: 首先输入稀疏矩阵的行数,列数,非零元素的个数,为*rhead 和*chead 分配内存空间, 并将十字链表中节点初始化为 NULL。然后依次输入非零元素的行,列,值,以 0 0 0 为结 尾结束链表的连接和 while 循环。

SMatrix_ADD 的功能如下: 在初始化稀疏矩阵后选择十字链表相加会提示输入另一个稀疏矩阵,连接结束后 SMatrix_ADD 函数以循环的方式比较非零元素是否为同一行列,如果是则两值相加,如果不 是则把第二个元素加入链表中。 ShowMAtrix 的功能如下: 逐一输出链表的行,列,值三个元素知道达到表尾的 NULL。 MultSMatrix_OL 的功能如下: 与相加类似, 在初始化稀疏矩阵后选择十字链表相加会提示输入另一个稀疏矩阵, 连接 结束后 MultSMatrix_OL 函数以循环的方式比较非零元素是否为同一行列,如果是则两值相 乘,如果不是则修改原来的元素值为 0。 TurnSMatrix_OL 的功能如下: 逐一查找十字链表中各个元素,将他们的 i,j 值对调已达到转置的目的.

2.算法具体分析 (1)、输入需要执行的操作:1 为创建稀疏矩阵,调用 CreateSMatix_OL 函数, 输入稀疏矩阵的行数列数和非零元素的个数(如 2 2 1,中间以空格分开) CreateSMatix_OL 函数会将各个元素的信息保存在十字链表的结点中并连接起来。2 为 退出程序。 (2)、选择接下来要执行的操作:1 为稀疏矩阵转置调用 TurnSMatrix_OL 函数逐 一查找十字链表中各个元素,将他们的 i,j 值对调已达到转置的目的。2 为稀疏矩阵相 加,调用 SMatrix_ADD 函数创建另一个稀疏矩阵并且将两矩阵中的非零元素相加。3 为 稀疏矩阵相乘,调用 MultSMatrix_OL 函数创建另一个稀疏矩阵并且将两矩阵中的同行 列的非零元素项相乘,其余项修改为 0。4 为退出。 (3)、程序显示操作结果,运行正常,结果正确。

三、程序结构
main()函数

Switch()函 数

CreateSMatix _OL()函数 Switch()函 数

退出

exit()函数

TurnSMatrix_ OL()函数

CreateSMatix _OL();函数

CreateSMatix _OL()函数

ShowMAtrix() 函数

SMatrix_ADD ();函数

MultSMatrix_ OL()函数

四、实验结果与分析
上述程序在 Visual C++ 6.0 环境下加以实现,经过多次的测试,程序运行正确。

例如:输入 1,再输入 2 2 1 接着输入非零元素为第 2 行第 1 列值为 9(2 1 9).运行 结果如图 2,图中创建十字链表成功可以选择后续操作稀疏矩阵转置,稀疏矩阵相加,稀疏 矩阵相乘。

图2
选择稀疏矩阵相加实验,输入 2,再输入 2 2 2 创建另一个稀疏矩阵,接着输入 1 1 9 和 2 1 1 两个非零元素,SMatrix_ADD 函数会将两个矩阵的非零元素相比较,在同行列的值相加, 不在同行列的为十字链表添加结点,计算结果如图 3,可以看到第一行第一列的元素 9 被加 入到链表中,而第 2 行第 1 列的两个元素 9 和 1 相加得到 10,程序运行成功。

图3 五.体会
通过这次课程设计,我有很深的体会,具体如下: 1. 十字链表的建立,和使用有了更深层次的理解。 2. 各种循环语句的使用和 switch 语句的应用比较熟悉了。 3. 把各个功能写在不同的函数体里,分工明确,条理清晰,这样不但语句简洁,而且十分 明了。 4. 从用户角度出发来编写程序,使结果尽量简洁明了。

附代码: #include<stdio.h> #include<stdlib.h> #include<malloc.h>

#define MAXSIZE 100 int num[100];

typedef struct OLNode{ int i,j; int e; struct OLNode *right,*down; }OLNode,*OLink;

typedef struct { int mu,nu,tu; //行数 mu,列数 nu,非零元素的个数 tu OLink *rhead,*chead; }CrossList;

int CreateSMatix_OL(CrossList &M){ int i,j,e; OLink q; OLink p; printf("请输入稀疏矩阵的行数,列数,非零元素的个数:"); scanf("%d%d%d",&M.mu,&M.nu,&M.tu); M.rhead=(OLink *)malloc((M.mu+1)*sizeof(OLNode)); M.chead=(OLink *)malloc((M.nu+1)*sizeof(OLNode));

for( i=1;i<=M.mu;i++)M.rhead[i]=NULL; for( i=1;i<=M.nu;i++)M.chead[i]=NULL; printf("请输入元素的行 列 值。最后输入 0 0 0 为结束\n"); scanf("%d%d%d",&i,&j,&e); while(i!=0){ p=(OLink)malloc(sizeof(OLNode)); p->i=i;p->j=j;p->e=e;

if(M.rhead[i]==NULL||M.rhead[i]->j>j){p->right=M.rhead[i];M.rhead[i]=p;} else{ q=M.rhead[i]; while(q->right&&q->right->j<j)q=q->right; p->right=q->right; q->right=p;} if(M.chead[j]==NULL||M.chead[j]->i>i){p->down=M.chead[j];M.chead[j]=p;} else{ q=M.chead[j]; while(q->down&&q->down->i<i)q=q->down; p->down=q->down; q->down=p; } scanf("%d%d%d",&i,&j,&e); } return 1; }//创建十字链表

int Compare(int a1,int b1,int a2,int b2){ if(a1>a2)return 1; else if(a1<a2)return -1; else if(b1>b2)return 1; if(b1<b2)return -1; else return 0;

}

int SMatrix_ADD(CrossList *A,CrossList *B){ OLNode *pa,*pb,*pre,*p,*cp[100]; int i,j,t; t=A->tu+B->tu; for(j=1;j<=A->nu;j++)cp[j]=A->chead[j]; for(i=1;i<=A->mu;i++){ pa=A->rhead[i]; pb=B->rhead[i]; pre=NULL; while(pb){

if(pa==NULL||pa->j>pb->j){ p=(OLink)malloc(sizeof(OLNode)); if(!pre)A->rhead[i]=p; else pre->right=p; p->right=pa; pre=p; p->i=i;p->j=pb->j;p->e=pb->e;

if(!A->chead[p->j]){ A->chead[p->j]=cp[p->j]=p; p->down=NULL; } else{ cp[p->j]->down=p; cp[p->j]=p; } pb=pb->right; } else if(pa->j<pb->j){pre=pa; pa=pa->right;} else if(pa->e+pb->e){ t--; pa->e+=pb->e; pre=pa; pa=pa->right; pb=pb->right;} else { t=t-2; if(!pre)A->rhead[i]=pa->right; else pre->right=pa->right;

p=pa;pa=pa->right; if(A->chead[p->j]==p)A->chead[p->j]=cp[p->j]=p->down; else cp[p->j]->down=p->down; free(p); pb=pb->right; } } } A->mu=A->mu>B->mu?A->mu:B->mu; A->nu=A->nu>B->nu?A->nu:B->nu; return 1; }//十字链表相加

int ShowMAtrix(CrossList *A){ int col; OLink p;

for(col=1;col<=A->mu;col++)if(A->rhead[col]){p=A->rhead[col]; while(p){printf("%3d%3d%3d\n",p->i,p->j,p->e);p=p->right;} } return 1; }//十字链表显示

int MultSMatrix_OL(CrossList M, CrossList N, CrossList &Q) { int i, j, e; //中间变量 OLink p0, q0, p, pl, pla; //中间变量 //检查稀疏矩阵 M 的列数和 N 的行数是否对应相等 if(M.nu != N.mu) { printf ( "稀疏矩阵 A 的列数和 B 的行数不相等,不能相乘。\n" ); return 0; }

Q.mu = M.mu, Q.nu = N.nu, Q.tu = 0; if(!(Q.rhead = (OLink *)malloc((Q.mu + 1) * sizeof(OLink)))) exit(-2); if(!(Q.chead = (OLink *)malloc((Q.nu + 1) * sizeof(OLink)))) exit(-2); for(i = 1; i <= Q.mu; i++) Q.rhead[i] = NULL; for(i = 1; i <= Q.nu; i++) Q.chead[i] = NULL; //相乘 for(i =1; i <= Q.mu; i++) for(j = 1; j <= Q.nu; j++) {

p0 = M.rhead[i], q0 = N.chead[j], e = 0; while(p0&&q0)//M 第 i 行和 N 第 j 列有元素 { if( p0->j > q0->i) q0 = q0->down; //M 的列大于 N 的行,则 N 的 列指针后移 else if(p0->j < q0->i) p0 = p0->right;//M 的列小于 N 的行,则 M 的 行指针右移 else {//M 的行等于 N 的列 e += p0->e * q0->e; //乘积累加 q0 = q0->down, p0 = p0->right;//移动指针 } } if(e)//乘积不为 0 { if(!(p = (OLink)malloc(sizeof(OLNode)))) exit(-2); Q.tu++;//非零元素增加 p->i = i, p->j = j, p->e = e, p->right = NULL, p->down = NULL;// 赋值,指针后移 //将 p 插入十字链表 //行插入 if(Q.rhead[i] == NULL) //若 p 为该行的第 1 个结点 Q.rhead[i] = pl = p; //p 插在该行的表头且 pl 指 向 p(该行的最后一个结点) else pl->right = p, pl = p; //插在 pl 所指结点之后, pl 右移 //列插入 if(Q.chead[j] == NULL) //若 p 为该列的第一个结点 Q.chead[j] = p; //该列的表头指向 p else {//插在列表尾 pla = Q.chead[j];//pla 指向 j 行的第 1 个结点 while(pla->down) pla = pla->down;//pla 指向 j 行最后一个结点 pla->down = p; } } } return 1; }//十字链表相乘

void TurnSMatrix_OL(CrossList &M){ int col,row; OLink p,q; for(col=1;col<=M.mu;col++) { q=p=M.rhead[col];

while(q){ row=p->i; p->i=p->j; p->j=row; q=p->right; p->right=p->down; p->down=q; } } }//十字链表转置

int DestroySMatrix_OL(CrossList &M) { int i;//中间变量 OLink p, q;//中间变量

if(!M.rhead || !M.chead) return 1;//M 不存在 else {//M 存在 if(M.chead)//所有列链表头指针置为空 for(i = 1; i <= M.nu; i++) M.chead[i] = NULL;

if(M.rhead)//按行释放节点 for(i = 1; i <= M.mu; i++) { p = M.rhead[i]; while(p) { q = p, p = p->right; free(q); } }

//释放行和列链表头指针指向基址 free(M.rhead); free(M.chead); //返回 return 1; } }//十字链表销毁

void main(){ int n,i;

//TSMatrix M,T,S; CrossList MM,TT,SS;

printf("请你选择操作:\n1:用十字建表创建稀疏矩阵。\n2:退出\n(1|2):"); scanf("%d",&n); switch(n){

case 1:{CreateSMatix_OL(MM); printf("已经选择十字链表创建稀疏矩阵,请选择操作\n1:稀疏矩阵转置\n2:稀 疏矩阵相加\n3:稀疏矩阵相乘\n4:退出\n(1|2|3|4):"); scanf("%d",&i); switch(i){ case 1: TurnSMatrix_OL(MM); ShowMAtrix(&MM); break; case 2: printf("请你输入另一个稀疏矩阵:"); CreateSMatix_OL(TT); SMatrix_ADD(&MM,&TT); ShowMAtrix(&MM);break; case 3:printf("请你输入另一个稀疏矩阵:"); CreateSMatix_OL(TT); MultSMatrix_OL(MM,TT,SS); ShowMAtrix(&SS);break; case 4:exit(0);

}};break; case 2:exit(0); default :printf("erorr"); } }


相关文章:
稀疏矩阵 实验报告
稀疏矩阵 实验报告_计算机软件及应用_IT/计算机_专业资料。所有代码均已调试通过...课程设计实验报告稀疏矩... 暂无评价 10页 免费 实现稀疏矩阵(采用三元组.....
课程设计 稀疏矩阵应用
课程设计实验报告 稀疏矩... 10页 2下载券 数据结构课程设计稀疏矩... 34页...-1- 稀疏矩阵应用 2.4 三元组的乘法将两个按三元组存储的稀疏矩阵进行相乘并...
实验报告---数据结构课程设计稀疏矩阵的应用
实验报告---数据结构课程设计稀疏矩阵应用_计算机软件及应用_IT/计算机_专业资料。数据结构课程设计 稀疏矩阵应用 数学与计算机学院 课程设计说明书课 程名称: ...
稀疏矩阵课程设计
运用 C、JAVA、VC++编程 工具,编程实现稀疏矩阵的相关操作。 要求: 1) 阐述...3) 从时间、空间对算法分析; 4) 较好的界面设计; 5) 编写课程设计报告。 ...
数据结构课程设计稀疏矩阵应用
程序设计 数组的运算 实验目的:掌握稀疏矩阵的压缩存储方法及主要运算的实现。 实验内容与要求:设计一个稀疏矩阵计算器, 要求能够: ⑴输入并建立稀疏矩阵; ⑵输出...
稀疏矩阵程序设计报告
稀疏矩阵程序设计报告_计算机软件及应用_IT/计算机_专业资料。C++稀疏矩阵程序设计报告 苏州科技学院二○一五 ~二○一六学年第一学期 电子信息工程学院 课程设计...
数据结构稀疏矩阵课程设计报告
课程设计报告课程设计题目:稀疏矩阵应用 学生姓名 专班业级 ___ 网络工程 13*** ___ 指导教师 2015 年 1 月 8 日 ***大学一、问题概述、分析及研究...
课程设计 稀疏矩阵的运用 源代码
课程设计 稀疏矩阵运用 源代码_理学_高等教育_教育专区 暂无评价|0人阅读|0次下载|举报文档 课程设计 稀疏矩阵运用 源代码_理学_高等教育_教育专区。#include...
稀疏矩阵(实验报告)
稀疏矩阵(实验报告) 数据结构数据结构隐藏>> 《数据结构课程设计实验报告编号 ...这种方式可以使我们很好的掌握算法的应用, 以此推广到其 它的算法中去。 分享...
推荐C语言《数据结构》实验报告稀疏矩阵运算的设计与实...
推荐C语言《数据结构》实验报告稀疏矩阵运算的设计与实现 精品_计算机软件及应用_IT/计算机_专业资料。更多课程设计、论文、毕业设计请访问: http://www.docin.com...
更多相关标签: