稀疏矩阵乘法优化

稀疏矩阵的乘法运算

程序代码：

#include #include #include #include #include #include #define Ture 1 #define Overflow -1 typedef struct OLnode {

int i,j; int e;

struct OLnode *right,*down; }OLnode,*Olink; typedef struct {

Olink *rhead,*chead; int mu,nu,tu; }Crosslist;

//在十字链表M.rhead[row]中插入一个t结点

void insert_row(Crosslist &M,OLnode *t,int row) {

OLnode *p;

int col=t->j;

if(M.rhead[row]==NULL||M.rhead[row]->j>col) {

t->right=M.rhead[row];

M.rhead[row]=t;

} else {

for(p=M.rhead[row];

#include <iostream>

#include <iomanip>

using namespace std;

const int MAXSIZE=100; // 定义非零元素的对多个数

const int MAXROW=10; // 定义数组的行数的最大值

typedef struct { // 定义三元组的元素

int i,j;

int e;

}Triple;

typedef struct { // 定义普通三元组对象

Triple data[MAXSIZE+1];

int mu,nu,tu;

}TSMatrix;

typedef struct { // 定义带链接信息的三元组对象

Triple data[MAXSIZE+2];

int rpos[MAXROW+1];

int mu,nu,tu;

}RLSMatrix;

template <class P>

bool InPutTSMatrix(P & T,int y){ //输入矩阵，按三元组格式输入

cout<<"输入矩阵的行，列和非零元素个数:"<<endl;

cin>>

数据结构课程设计,稀疏矩阵转置和乘法

燕山大学

课 程 设 计 说 明 书

题目：稀疏矩阵的转置和乘法

学院（系）： 理学院 年级专业： 12级信息一班、二班 学 号： 120108010002 学生姓名： 吴中原 学 号： 120108010004 学生姓名： 黄志豪 学 号： 120108010050 学生姓名： 李红旭

指导教师： 教师职称：

数据结构课程设计,稀疏矩阵转置和乘法

燕山大学课程设计（论文）任务书

院（系）： 理学院 基层教学单位：

说明：此表一式四份，学生、指导教师、基层教学单位、系部各一份。

年 月 日

数据结构课程设计,稀疏矩阵转置和乘法

燕山大学课程设计评审意见表

数据结构课程设计,稀疏矩阵转置和乘法

一：课设内容

建立稀疏矩阵的三元组顺序表，实现稀疏矩阵的转置。->建立行逻辑链接顺序表，实现稀疏矩阵乘法。 二：课设步骤

小组讨论—>查阅资料—>编写代码—>完成设计报告—>制作PPT—>准备答辩 三：算法思想 转置算法一

数据结构课程设计

设计说明书

稀疏矩阵相关操作的实现

学生姓名 学班成

号 级 绩

指导教师

数学与计算机科学学院 2012 年 3 月 2 日

数据结构课程设计评阅书

题 目 学生姓名 指导教师评语及成绩 稀疏矩阵相关操作的实现 学号 成绩： 教师签名： 年 月 日 答辩教师评语及成绩 成绩： 教师签名： 年 月 日 教研室意见 总成绩： 室主任签名： 年 月 日 注：指导教师成绩60%，答辩成绩40%，总成绩合成后按五级制记入。

课程设计任务书

2011—2012学年第二学期

专业： __________________ 学号： __________ 姓名： _______ 课程设计名称： 数据结构课程设计 设 计 题 目： 稀疏矩阵相关操作的实现

稀疏矩阵相乘(三元组)

# include <stdio.h> # include <stdlib.h> # define NULL 0 # define OK 1 # define ERROR 0

# define MAXSIZE 100 /* 矩阵中非零元的最大值 */

# define MAXRC 10 /* 矩阵的最大行值 */

typedef int status ;

/********** 稀疏矩阵的行逻辑链接的顺序表存储表示 **********/

typedef struct /* 非零元的三元组 */ {

int i, j ; /* 非零元的行下标和列下标 */ int e ;

}Triple;

typedef struct /* 稀疏矩阵的行逻辑链接的顺序表 */ {

Triple data[MAXSIZE+1]; /* 非零三元组表，data[0]未用，以下定义的数组都是从1

稀疏矩阵应用

摘 要 本课程设计主要实现在三元组存储结构与十字链表存储结构下输入稀疏矩阵，并对稀疏矩阵进行转置，相加，相乘操作，最后输出运算后的结果。在程序设计中，考虑到方法的难易程度，采用了先用三元组实现稀疏矩阵的输入，输出，及其转置，相加，相乘操作的方法，再在十字链表下实现。程序通过调试运行，结果与预期一样，初步实现了设计目标。

关键词 程序设计；稀疏矩阵；三元组；十字链表

1 引言

? 课程设计任务

本课程设计主要实现在三元组存储结构与十字链表存储结构下输入稀疏矩阵，并对稀疏矩阵进行转置，相加，相乘操作，最后输出运算后的结果。稀疏矩阵采用三元组和十字链表表示，并在两种不同的存储结构下，求两个具有相同行列数的稀疏矩阵A和B的相加矩阵C，并输出C； 求出A的转置矩阵D，输出D； 求两个稀疏矩阵A和B的相乘矩阵E，并输出E。

? 课程设计性质

数据结构课程设计是重要地实践性教学环节。在进行了程序设计语言课和《数据结构》课程教学的基础上，设计实现相关的数据结构经典问题，有助于加深对数据结构课程的认识。本课程设计是数据结构中的一个关于稀疏矩阵的算法的实现，包括在三元组和十字链表下存储稀疏矩阵，并对输入的稀疏矩阵进行转置，相加，相乘等操

数据结构

课程设计报告

设计题目：稀疏矩阵

专业：计算机科技 院系：计算机学院

姓名：xxxxxxx

学号：xxxxxxxx

时间：2013年9月22日

目录

一需求分析---------------------------------------------------------------- 3

1. 问题描述-------------------------------------------------------------------------------------- 3

2. 基本要求-------------------------------------------------------------------------------------- 3

3 实现提示-------------------------------------------------------------------------------------- 3

二概要设计----------------------------------------------------------------------3

三详细设计--------------------

矩阵乘法运算效率

摘要

近年来，处理器运行速度的增长和存储器访问速度的增长之间存在着巨大的差距，这使得两者之间的速度差距越来越大，现代计算机体系结构中广泛采用高速缓冲存储器（Cache）来缓解这两者之间的速度差距。

本文根据矩阵乘法运算的六种不同程序代码，构建了矩阵乘法运算时间的测试程序，得到矩阵乘法运算六种不同版本的运行时间；并通过分析六种不同矩阵乘法运算程序代码中的空间局部性与时间局部性，得出由于高速缓冲存储器和程序访问的局部性差异，同一算法的不同程序代码运行时间相差很大。为了充分利用高速缓冲存储器，提高程序运行效率，在编写程序时需要考虑程序和数据的空间局部性和时间局部性。

为了充分利用高速缓冲存储器，论文又给出了分块矩阵乘法运算程序，它可以进一步提高矩阵乘法运算效率。 关键字：高速缓冲存储器；矩阵乘法；分块矩阵；局部性原理；时间局部性；空间局部性

Abstract

Recent years, there has been a big gap between the growth of processor and memory runs access speed, which makes the speed difference b

特殊矩阵与稀疏的压缩存储和算法实现 1998年论文

维普资讯

第1 5卷19 9 8年

第 3期8月

贵州大学学报 (自然科学版 )Ju nl l u huUnvri ( a rl ce c) o ra 0 G i o i s y N t a S in e z e t u—

、

1 No, 5. Au 1 9 g. 9 8

—

0—

特殊矩阵与稀疏的压缩存储和算法实现mH十^摘要

.

下；’ (6Ⅷ㈣) f。 、 1f f/f、f

本丈结合《学结构 *中遇到教学问题，就对称矩阵、三角矩阵、三对角教

矩阵、稀疏矩阵的压缩储进行了计论，并给出了建立这些存付的类 p sa算法描述 . acl

苎 .中分图 g竺类-

T t 3 .1 11 1

、塑三 三丝苎’

稀矩、组疏障数

奄 .‘ 留 存罐矩阵的运算在计算机中一般用二维组来实现 .将矩阵存放到~维的线性存储空问中，一般有两种存储方式：一种以行序为主的存储方式，即先存放第一行，接着存放的第二行…直

到第 N行；另一种以列序为主的存储方式，即先存放第一列，接着存放第二列…直接到第 N 行.对于普通矩阵的这种存储结构的读与写运算，用高级语言来实现已趋于成熟，这里不再讨论.

在现实问题经常会遇到阶数很高并且矩阵中有许多

数据结构----稀疏矩阵运算器课程设计

目 录

稀疏矩阵运算器设计 ............................................................................................ I 摘 要 ................................................................................................................... II

第一章 需求分析 .......................................................................................... 1 第二章 概要设计 .......................................................................................... 2 第三章 设计步骤 ..............................................................