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

计算机科学与技术系

课程设计报告

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(\"%d%d%d\ 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;kscanf(\"%d%d%d\ 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; }

int Print(CrossList M) {

int i,j,k; OLink p;

int array[100][100]; for(i=0;i!=M.mu;i++) {

for(j=0;j!=M.nu;j++) {

array[i][j]=0;//初始化数组所需部分 } }

for(k=0;k!=M.nu;k++) {

p=M.chead[k]; while(p) {

array[p->i][p->j]=p->e;//将非零元存入数组中 p=p->down; } }

for(i=0;i!=M.mu;i++) {

for(j=0;j!=M.nu;j++) {

if(j==M.nu-1)

cout<cout<return OK; }

int Add(CrossList M,CrossList N,CrossList &Q) {

int i,k;

OLink p,pq,pm,pn; OLink *col;

Q.mu=M.mu;//初始化Q Q.nu=M.nu; Q.tu=0;

Q.rhead=(OLink*)malloc((Q.mu+1)*sizeof(OLink)); if(!Q.rhead)

exit(OVERFLOW);

Q.chead=(OLink*)malloc((Q.nu+1)*sizeof(OLink)); if(!Q.chead)

exit(OVERFLOW);

for(k=0;k!=Q.mu;k++)//初始化行 Q.rhead[k]=NULL;

for(k=0;k!=Q.nu;k++)//初始化列 Q.chead[k]=NULL;

col=(OLink*)malloc((Q.nu+1)*sizeof(OLink));//生成指向列的最后节点的数组 if(!col)

exit(OVERFLOW);

for(k=0;k!=Q.nu;k++)//赋初始值 col[k]=NULL;

for(i=0;i!=M.mu;i++)//按行序相加 {

pm=M.rhead[i]; pn=N.rhead[i]; while(pm&&pn) {

if(pm->jj)//矩阵M当情前结点的列小于矩阵N当前结点的列 {

p=(OLink)malloc(sizeof(OLNode));//生成Q的结点 if(!p)

exit(OVERFLOW);

Q.tu++; //非零元个数＋1 p->i=i; //赋值 p->j=pm->j; p->e=pm->e; p->right=NULL;

pm=pm->right; //pm右移 }

else if(pm->j>pn->j) {

p=(OLink)malloc(sizeof(OLNode));

if(!p)

exit(OVERFLOW); Q.tu++; p->i=i; p->j=pn->j; p->e=pn->e; p->right=NULL; pn=pn->right; }

else if(pm->e+pn->e)//M,N当前结点的列相同并且两元素之和非零 {

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

exit(OVERFLOW); Q.tu++; p->i=i; p->j=pn->j;

p->e=pm->e+pn->e; p->right=NULL;

pm=pm->right;//pm右移 pn=pn->right;//pn右移 }

else//两元素相加为零 {

pm=pm->right; pn=pn->right; continue; }

if(Q.rhead[i]==NULL) Q.rhead[i]=pq=p; else {

pq->right=p;//完成行插入 pq=pq->right; }

if(Q.chead[p->j]==NULL) Q.chead[p->j]=col[p->j]=p; else {

col[p->j]->down=p;//完成列插入 col[p->j]=col[p->j]->down; } }

while(pm)//将矩阵M该行的剩余元素插入矩阵Q

{

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

exit(OVERFLOW); Q.tu++; p->i=i;

p->j=pm->j; p->e=pm->e; p->right=NULL; pm=pm->right;

if(Q.rhead[i]==NULL) Q.rhead[i]=pq=p; else {

pq->right=p; pq=pq->right; }

if(Q.chead[p->j]==NULL) Q.chead[p->j]=col[p->j]=p; else {

col[p->j]->down=p;

col[p->j]=col[p->j]->down; } }

while(pn)//将矩阵N该行的剩余元素插入矩阵Q {

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

exit(OVERFLOW); Q.tu++; p->i=i; p->j=pn->j; p->e=pn->e; p->right=NULL; pn=pn->right;

if(Q.rhead[i]==NULL) Q.rhead[i]=pq=p; else {

pq->right=p; pq=pq->right; }

if(Q.chead[p->j]==NULL)

Q.chead[p->j]=col[p->j]=p; else {

col[p->j]->down=p;

col[p->j]=col[p->j]->down; } } }

for(k=0;k!=Q.nu;k++) if(col[k])

col[k]->down=NULL; free(col); return OK; }

CrossList Negative(CrossList M) {

OLink p;

for(int j=0;j!=M.mu;j++) {

p=M.rhead[j]; while(p) {

p->e=-p->e;//将非零元的值反号 p=p->right; } }

return (M); }

int Mult(CrossList M,CrossList N,CrossList &Q) {

int i,j,e;

OLink q,p0,q0,q1,q2; if(M.nu!=N.mu) {

printf(\"你输入的两个距阵不能进行此操作\\n\"); exit(OVERFLOW); } else {

Q.mu=M.mu; Q.nu=N.nu; Q.tu=0;

Q.rhead=(OLink*)malloc((Q.mu+1)*sizeof(OLink)); if(!Q.rhead)

exit(OVERFLOW);

Q.chead=(OLink*)malloc((Q.nu+1)*sizeof(OLink)); if(!Q.chead)

exit(OVERFLOW);

for(i=0;i!=Q.mu;i++)//初始化行 Q.rhead[i]=NULL;

for(i=0;i!=Q.nu;i++)//初始化列

Q.chead[i]=NULL; for(i=0;i!=Q.mu;i++) for(j=0;j!=Q.nu;j++) {

p0=M.rhead[i]; q0=N.chead[j]; e=0;

while(p0&&q0) {

if(q0->ij)

q0=q0->down;//列后移 else if(q0->i>p0->j)

p0=p0->right;//行后移 else {

e=e+p0->e*q0->e;//乘积累加 q0=q0->down;

p0=p0->right;//行列后移 } }

if(e)//e不为零则插入Q {

Q.tu++;

q=(OLink)malloc(sizeof(OLNode)); if(!q)

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

q->right=NULL; q->down=NULL; if(!Q.rhead[i]) Q.rhead[i]=q1=q; else

q1=q1->right=q; if(!Q.chead[j]) Q.chead[j]=q; else {

q2=Q.chead[j]; while(q2->down) q2=q2->down; q2->down=q; }

} }

return OK; } }

四、上机调试过程

1.调试过程中遇到的主要问题是如何解决的：

由于代码是仿照网上代码参照而写出来的，网上代码是c++编写的，所以部分代码需要改写成C语言，由于C++我们没学过，所以还要通过查询书籍和网络了解C++语言如何改写成C语言，1、cout endl;语句等价于printf 例：cout<<\"你输入的是\"<>Select;等价于scanf(\"%d\其中Select是int型 3、c语言中变量的定义必须在函数的首部：

像这种的要把int j;提出来

2.对设计和编码的回顾讨论和分析：

在设计方面，主要就是算法思想的设计，以及具体函数的设计运行。在这方面，主

要的算法设计思想倒不是特别的难想，主要是具体函数例如加法的函数的具体设计比较繁琐，耗费了较多时间。而在编码方面，由于c语言的学习还是在大一下学期，所以对于相关知识已经有所遗忘，所以在编码的过程遇到了不少问题需要查阅书籍，尤其涉及到具体代码的编写，更是花费了不少时间来修正调试。

五、测试结果及其分析

1、改进设想：

对于运算的界面可以更加精美有条理性一些；除此以外，可以给运算设计一个选择界

面，用户可以选择进行计算和退出；

由于部分代码是参考网上案列c++编码的，我想把它改成C语言代码，丹改过来后，他总是报错，调试也找不来原因，null指没有声明，但在头文件stdio.h中已有null值得申明，最后自定义个null值得声明，还是不行，所以导致我的部分代码有些不理解，这好似一部分遗憾，希望通过以后的学习和学习中明白这些原因。 2、经验和体会：

十字链表作为存储结构表示随机稀疏矩阵，进行两矩阵的相加运算，所以首先要定义一个十字链表作为存储结构。仅有此还是不够的，还需要定义指针来指向链表中的元素。在开始的时候，老是得不到想象中的结果，通过几次的检查才发现问题出在对矩阵中的元素指向没有弄清楚，所以即使是相位置上的元素也没有处理好它们的相加问题。这个实验从最初的设计到完成，出现了很多错误，通过最终的修正发现，其实犯的都是小错误，都是些指针的问题。因为指针是我比较薄弱的环节。我发现了这些问题，所以我就要进行弥补、查缺补漏。

通过这次课程设计，敦促我将过去学习过的知识进行了温习，知识只有多巩固，才能真正的理解与领悟。

六、用户使用说明

按提示进行相关操作。

1、先运行出来：出现主界面

2、先选择你将要运算的功能，列如1、相加，然后输入你第一个稀疏矩阵的行、列、非

零元的个数，接着输入非零元素的行、列和值；

输入第二个稀疏矩阵的行、列、非零元的个数，接着输入非零元素的行、列和值； 3、输入完成后，点击回车，它会显示出你所输入的第一个稀疏矩阵、第二个稀疏矩阵，

以及它们相加后得到的稀疏矩阵。

一、 源程序

#include #include #include #include #define OK 1 #define ERROR 0

#define OVERFLOW -2 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;//矩阵的行、列和非零元个数 };

int Create(CrossList &M) {

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

printf(\"请输入稀疏距阵的行数 列数 非零元的个数：\"); scanf(\"%d%d%d\ 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;kscanf(\"%d%d%d\ 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; }

int Print(CrossList M) {

int i,j,k; OLink p;

int array[100][100]; for(i=0;i!=M.mu;i++) {

for(j=0;j!=M.nu;j++) {

array[i][j]=0;//初始化数组所需部分 } }

for(k=0;k!=M.nu;k++) {

p=M.chead[k]; while(p) {

array[p->i][p->j]=p->e;//将非零元存入数组中 p=p->down; } }

for(i=0;i!=M.mu;i++) {

for(j=0;j!=M.nu;j++) {

if(j==M.nu-1)

cout<cout<return OK; }

int Add(CrossList M,CrossList N,CrossList &Q) {

int i,k;

OLink p,pq,pm,pn; OLink *col;

Q.mu=M.mu;//初始化Q Q.nu=M.nu; Q.tu=0;

Q.rhead=(OLink*)malloc((Q.mu+1)*sizeof(OLink)); if(!Q.rhead)

exit(OVERFLOW);

Q.chead=(OLink*)malloc((Q.nu+1)*sizeof(OLink)); if(!Q.chead)

exit(OVERFLOW);

for(k=0;k!=Q.mu;k++)//初始化行 Q.rhead[k]=NULL;

for(k=0;k!=Q.nu;k++)//初始化列 Q.chead[k]=NULL;

col=(OLink*)malloc((Q.nu+1)*sizeof(OLink));//生成指向列的最后节点的数组 if(!col)

exit(OVERFLOW);

for(k=0;k!=Q.nu;k++)//赋初始值

col[k]=NULL;

for(i=0;i!=M.mu;i++)//按行序相加 {

pm=M.rhead[i]; pn=N.rhead[i]; while(pm&&pn) {

if(pm->jj)//矩阵M当情前结点的列小于矩阵N当前结点的列 {

p=(OLink)malloc(sizeof(OLNode));//生成Q的结点 if(!p)

exit(OVERFLOW); Q.tu++; //非零元个数＋1 p->i=i; //赋值 p->j=pm->j; p->e=pm->e; p->right=NULL;

pm=pm->right; //pm右移 }

else if(pm->j>pn->j) {

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

exit(OVERFLOW); Q.tu++; p->i=i; p->j=pn->j; p->e=pn->e; p->right=NULL; pn=pn->right; }

else if(pm->e+pn->e)//M,N当前结点的列相同并且两元素之和非零 {

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

exit(OVERFLOW); Q.tu++; p->i=i; p->j=pn->j;

p->e=pm->e+pn->e; p->right=NULL;

pm=pm->right;//pm右移 pn=pn->right;//pn右移 }

else//两元素相加为零 {

pm=pm->right; pn=pn->right; continue; }

if(Q.rhead[i]==NULL) Q.rhead[i]=pq=p; else {

pq->right=p;//完成行插入 pq=pq->right; }

if(Q.chead[p->j]==NULL) Q.chead[p->j]=col[p->j]=p; else {

col[p->j]->down=p;//完成列插入 col[p->j]=col[p->j]->down; } }

while(pm)//将矩阵M该行的剩余元素插入矩阵Q {

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

exit(OVERFLOW); Q.tu++; p->i=i;

p->j=pm->j; p->e=pm->e; p->right=NULL; pm=pm->right;

if(Q.rhead[i]==NULL) Q.rhead[i]=pq=p; else {

pq->right=p; pq=pq->right; }

if(Q.chead[p->j]==NULL) Q.chead[p->j]=col[p->j]=p; else {

col[p->j]->down=p;

col[p->j]=col[p->j]->down; } }

while(pn)//将矩阵N该行的剩余元素插入矩阵Q {

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

exit(OVERFLOW); Q.tu++; p->i=i; p->j=pn->j; p->e=pn->e; p->right=NULL; pn=pn->right;

if(Q.rhead[i]==NULL) Q.rhead[i]=pq=p; else {

pq->right=p; pq=pq->right; }

if(Q.chead[p->j]==NULL) Q.chead[p->j]=col[p->j]=p; else {

col[p->j]->down=p;

col[p->j]=col[p->j]->down; } } }

for(k=0;k!=Q.nu;k++) if(col[k])

col[k]->down=NULL; free(col); return OK; }

CrossList Negative(CrossList M) {

OLink p;

for(int j=0;j!=M.mu;j++) {

p=M.rhead[j]; while(p)

{

p->e=-p->e;//将非零元的值反号 p=p->right; } }

return (M); }

int Mult(CrossList M,CrossList N,CrossList &Q) {

int i,j,e;

OLink q,p0,q0,q1,q2; if(M.nu!=N.mu) {

printf(\"你输入的两个距阵不能进行此操作\\n\"); exit(OVERFLOW); } else {

Q.mu=M.mu; Q.nu=N.nu; Q.tu=0;

Q.rhead=(OLink*)malloc((Q.mu+1)*sizeof(OLink)); if(!Q.rhead)

exit(OVERFLOW);

Q.chead=(OLink*)malloc((Q.nu+1)*sizeof(OLink)); if(!Q.chead)

exit(OVERFLOW);

for(i=0;i!=Q.mu;i++)//初始化行 Q.rhead[i]=NULL;

for(i=0;i!=Q.nu;i++)//初始化列 Q.chead[i]=NULL; for(i=0;i!=Q.mu;i++) for(j=0;j!=Q.nu;j++) {

p0=M.rhead[i]; q0=N.chead[j]; e=0;

while(p0&&q0) {

if(q0->ij)

q0=q0->down;//列后移 else if(q0->i>p0->j)

p0=p0->right;//行后移 else {

e=e+p0->e*q0->e;//乘积累加 q0=q0->down;

p0=p0->right;//行列后移 } }

if(e)//e不为零则插入Q {

Q.tu++;

q=(OLink)malloc(sizeof(OLNode)); if(!q)

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

q->right=NULL; q->down=NULL; if(!Q.rhead[i]) Q.rhead[i]=q1=q; else

q1=q1->right=q; if(!Q.chead[j]) Q.chead[j]=q; else {

q2=Q.chead[j]; while(q2->down) q2=q2->down; q2->down=q; } } }

return OK; } }

void main() {

CrossList A,B,C;//声明三各矩阵 int Select;

cout<<\"请选择你需要的操作\"<cout<<\"2 减法\"<>Select; switch(Select) {

case 1 ://稀疏矩阵相加 {

Create(A); Create(B);

cout<<\"你输入的是\"<cout<<\"加上\"<cout<<\"结果是\"<case 2 ://稀疏矩阵相减 {

Create(A); Create(B);

cout<<\"你输入的是\"<cout<<\"减去\"<cout<<\"结果是\"<case 3 ://稀疏矩阵相乘 {

Create(A); Create(B);

cout<<\"你输入的是\"<cout<<\"乘以\"<cout<<\"结果是\"<} } }