课程设计报告报告—稀疏矩阵的完全链表表示及其运算 - 图文 

学院

计算机科学与技术系

课程设计报告

2014 ～2015 学年第 2 学期

课

程 数据结构与算法

稀疏矩阵的完全链表表示及其运算

课程设计名称 学学专指

业导

班教

生 号 级 师

13软件工程（2）班

老师

20 15 年 1 月

..

稀疏矩阵的完全链表表示及其运算

【问题描述】

稀疏矩阵的每个结点包含down，right，row，col和value五个域。用单独一个结点表示一个非零项，并将所有结点连接在一起，形成两个循环链表。使得第一个表即行表，把所有结点按照行序（同一行按列序）用right域起来。使得第二个表即列表，把所有结点按照列序（同一列按行序）用down起来。这两个表共用一个头结点。另外，增加一个包含矩阵维数的结点。稀疏矩阵的这种存储表示称为完全链表表式。

实现一个完全链表系统进行稀疏矩阵运算，并分析下列操作函数的计算时间和额外存储空间的开销。 【设计目的】

认识和掌握稀疏矩阵的完全链表表示；能够建立并运用这种存储结构 【基本要求】

建立一个用户友好、菜单式系统进行下列操作，并使用合当的测试数据测试该系统。 读取一个稀疏矩阵建立其完全链表表示 输出一个稀疏矩阵的容 删除一个稀疏矩阵 两个稀疏矩阵相加 两个稀疏矩阵相减 两个稀疏矩阵相乘 稀疏矩阵的转置 【实现提示]

链表上的操作。

二、数据结构的选择和概要设计 （一）、问题分析

1、功能要求：根据用户输入的矩阵，实现稀疏矩阵的求和运算，并输出结果。 2、输入要求：矩阵的数据在程序运行的时候由用户提供，先由用户输入稀疏矩阵的行数、列数和非零元个数。再根据非零元个数，输入这些非零元，还需要用户为这些非零元输入行、列和非零元的值。这样，一个稀疏矩阵就输入完成。 3、用单链表存储非零元素的结点信息，并且将之用矩阵的形式打印出来 （二）、概要设计 1、结构体的定义 typedef int ElemType;

..

struct OLNode {

int i,j; //非零元所在行、列 ElemType e;//非零元值 OLNode *right,*down; };

typedef OLNode *OLink; struct CrossList {

OLink *rhead,*chead;//行、列表头的头节点 int mu,nu,tu;//矩阵的行、列和非零元个数 };

2、存储结构选择

采用十字链表存储稀疏矩阵，它是稀疏矩阵链式表示的一种较好的表示方法。在十字链表中，每一个非零矩阵元素存储在一个结点。每一个节点除了存储非零元素的三元组以外，还设置了right和down两个指针，分别指向同一行的下一个非零元素结点和同一列的下一个非零元的结点。 3、主函数

主函数包括相加、相减、相乘的各个子函数。 4、菜单

具有选择功能的用户友好、菜单式系统，可以选择相应的功能来处理输入的数据。

..

三、详细设计和编码 1. 设计表示

（1）函数调用关系图

1、相加 2、相减 3、相乘非零元 OVERFLOW

（2）算法思想

稀疏矩阵的每个结点包含down，right，row，col和value五个域。用单独一个结点表示一个非零项，并将所有结点连接在一起，形成两个循环链表。使得第一个表即行表，把所有结点按照行序（同一行按列序）用right域起来。使得第二个表即列表，把所有结点按照列序（同一列按行序）用down起来。这两个表共用一个头结点。另外，增加一个包含矩阵维数的结点。稀疏矩阵的这种存储表示称为完全链表表式。 (3) 主要编码

int Create(CrossList &M) {

int i,j,k,m,n,t; ElemType e; OLNode *p,*q;

printf(\请输入稀疏距阵的行数列数非零元的个数：\ scanf(\ M.mu=m; M.nu=n; M.tu=t;

M.rhead=(OLink*)malloc((m+1)*sizeof(OLink)); if(!M.rhead)

exit(OVERFLOW);

M.chead=(OLink*)malloc((n+1)*sizeof(OLink)); if(!M.chead)

exit(OVERFLOW);

for(k=0;k!=m;k++)//初始化行头指针 M.rhead[k]=NULL;

for(k=0;k!=n;k++)//初始化列头指针

..

主函数

M.chead[k]=NULL;

printf(\请按任意次序输入%d个非零元的行列元素值:\\n\ for(k=0;k

scanf(\ if(i>m||j>n) {

printf(\你输入的元素不在矩阵中请检查重输:\\n\ exit(OVERFLOW); } else {

p=(OLNode*)malloc(sizeof(OLNode)); if(!p)

exit(OVERFLOW); p->i=i; p->j=j; p->e=e;

if(M.rhead[i]==NULL||M.rhead[i]->j>j)//p插入该行第一节点处 {

p->right=M.rhead[i]; M.rhead[i]=p; }

else//寻找行表插入位置 {

for(q=M.rhead[i];q->right&&q->right->jright); p->right=q->right;//完成行插入 q->right=p; }

if(M.chead[j]==NULL||M.chead[j]->i>i)//p插入该列第一节点处 {

p->down=M.chead[j]; M.chead[j]=p; }

else//寻找列表插入位置 {

for(q=M.chead[j];q->down&&q->down->idown); p->down=q->down;//完成列插入 q->down=p; } } }

return OK; }

..