用十字链表和一般方法分别实现稀疏矩阵的乘法和加法

1、分别用一般方法和和十字链表法，存储稀疏矩阵，并实现矩阵的加法和乘法 运算。用一般方法时，用M..rops[i]保存矩阵M中第i行的首非零元在矩阵 所有非零元中的顺序，并用M.data[]保存矩阵M的非零元，矩阵最多有2500 个非零元，最大有50行。用十字链表法时，用right和down分别指示非零 元的行后继和列后继元素，rhead和chead分别指向行表和列表的头，头结 点都没有用到。 2、演示程序程序以用户和计算机的对话方式进行，即在计算机终端上显示提示 信息之后，由用户在键盘上输入演示程序中规定的运算命令;相应的输入数 据和运算结果显示在其后。 3、程序执行的命令包括: 、稀疏矩阵的加法，并输出结果，2、稀疏矩阵乘法，并输出结果 请选择:1 十字链表加法,并输出，4、十字链表乘法并输出，5、结束: 4、测试数据 (1)、乘法 矩阵原型: 4 -3 0 0 1 3 0 0 24 -6 0 0 0 0 8 0 * -4 2 0 8 0 0 0 0 1 0 0 0 1 0 = 0 1 0 0 0 0 0 70 1 0 0 0 0 0 4 5 6 1 1 4 3 1 2 - 1 5 1 2 4 8 3 3 1 4 5 70 5 3 5 1 1 3 2 1 -4 2 2 2 3 2 1 4 1 1 (2)、加法 矩阵原型: 4 0 0 -8 0 0 0 0 1 4 0 -7 0 0 9 0 0 1 10 0 8 -6 0 0 0 -3 7 6 0 -2 + 1 0 0 0 0 0 = 1 5 0 0 0 0 0 3 0 0 0 0 -4 0 0 -2 0 9 0 0 0 -1 0 0 4 0 1 -4 0 -7 10 0 17 -6 0 1 1 -3 7 6 0 -2 1 8 0 0 0 0 -4 0 0 -3 0 9 5 6 13 1 1 4 1 4 -8 2 3 9 2 6 1 3 2 -3 3 3 7 3 4 6 3 6 -2 4 1 1 4 2 5 4 5 1 - 5 4 -2 5 6 9 5 6 9 1 3 1 1 4 4 1 6 -7 2 1 10 2 3 8 2 4 -6 3 1 1 4 2 3 5 4 -1 二、概要设计 1.稀疏矩阵的抽象数据类型定义为: ADT juzhen { 数据对象:D={ m，n，t，data |m，n，t，data 属于 Elemset} 数据关系:R={，，} 基本操作: Create(juzhen M) 操作结果:构造了矩阵M。 Add(juzhen A，juzhen B，juzhen &C) 初始条件:矩阵A，B已存在。 操作结果:使A，B矩阵相加并把结果赋到C矩阵。 Multy(juzhen A，juzhen B，juzhen &C) 初始条件:矩阵A，B已存在。 操作结果:使A，B矩阵相乘并把结果赋到C矩阵。 Print(juzhen A) 初始条件:矩阵A已存在。 。 操作结果:输出稀疏矩阵A }ADT juzhen 2、十字链表的抽象数据类型定义为: ADT crosslist { 数据对象:{rhead，chead，m，n，t | rhead，chead，m，n，t 属于Elementset} 数据关系:R1={} 基本操作: Createcross(crosslist &M) 创建十字链表矩阵M。 Addcross() 操作结果:创建两个十字链表a，b，使a+b的值赋给a，并返回a。 Multycross(crosslist &c) ，b，使a*b的值赋给c。 操作结果:创建两个十字链表a Printcross(crosslist A) 初始条件:矩阵A已经存在。 操作结果:输出十字链表。 }ADT crosslist 3、本程序包括三个模块 (1)、主程序模块 Void main() { Switch() { } } (2)、稀疏矩阵模块----实现稀疏矩阵的加法，乘法，及输出操作 (3)、十字链表模块----实现稀疏矩阵的加法，乘法，及输出操作 三、详细设计 1、三元组类型 typedef struct { int i; int j; int e;//非零元的值 }triple; //定义三元组 2、稀疏矩阵类型 typedef struct { triple data[Size+1];//矩阵中的元素 int rops[Size1+1];// rops[i]为第i行元素中的首非零元在data[]中的序 号 int mu;//行数 int nu;//列数 int tu;//非零元数 } juzhen;//定义矩阵 3、结点类型 typedef struct node { int i,j,e; struct node *right,*down;// 该非零元所在行表和列表的后继元素 }node,*link; 4、十字链表类型 typedef struct // 定义十字链表对象结构体 { link *rhead,*chead;//行和列的头指针 int m,n,t;// 系数矩阵的行数，列数，和非零元素个数 }crosslist; 其中部分操作的算法: void printcross(crosslist A)//输出十字链表 { printf("十字链表为:\n"); int i,j; for(i=1;i<=A.m;i++) { link p=A.rhead[i]; for(j=1;j<=A.n;j++) { if((p)&&(j==p->j)) { printf("%5d",p->e); p=p->right; } else printf("%5d",0); } printf("\n"); } printf("\n"); } crosslist addcross() { printf("十字链表加法:\n"); crosslist a,b;// 创建两个十字链表对象，并初始化 createcross(a); createcross(b); node *pre,*h[51],*pa,*pb,*q;//定义辅助指针，pa，pb分别为a,b当前比 较的元素，pre为pa的前驱元素 int i,j,k=0,m,n; //h[j]指向j列的当前插入位置 if(a.m!=b.m||a.n!=b.n) printf("格式不对，不能相加!\n"); else { for(i=1;i<=a.m;i++) { pa=a.rhead[i]; pb=b.rhead[i]; pre=NULL; for(j=1;j<=a.n;j++) h[j]=NULL; while(pb) { link p; p=(node *)malloc(sizeof(node)); // 开辟新节点，存储b中 取出的元素 p->i=pb->i; p->j=pb->j; p->e=pb->e; if(pa==NULL||pa->j>pb->j)//当a此行已经检查完或者pb因该 放在pa前面 { if (pre==NULL) a. rhead [p->i]=p; else pre->right=p; p->right=pa; pre = p; if (h[p->j]==NULL)//当前插入位置下面无非零元 //因为是逐行处理，so,h[p->j]，依次下移 //因此每次都是指向插入的 位置 { a. chead [p->j]= p; p->down = NULL; } else { p->down = h[p->j]->down; h[p->j]->down = p; } h[p->j]=p;//*******h[p->j]下移指向下次插入的位置 pb=pb->right;//pb指向该行下个元素 } else if((pa&&pa->jj))//只要移动pa的指针****先不加 ||(pb==NULL&&pa) { pre = pa; h[pa->j]=pa;//移动h[]，使其指向下次插入的位置 pa = pa->right; } ->j) else if(pa->j==pb { pa->e+=pb->e; 不为零 if(pa->e)// { pre=pa; h[pa->j]=pa; pb=pb->right;//加 } else//pa->e为零，删除节点 { if (pre ==NULL) a.rhead [pa->i]=pa->right; else { pre->right=pa->right; } p=pa;//p指向pa，用来在下面修改列指针 pa=pa->right; if (h [p->j]==NULL) a.chead [p->j]=p->down; else { h[p->j]->down=p->down; } free(p); pb=pb->right; } } } } } return a; } void multycross(crosslist &c)//十字链表乘法 { node *p,*q,*u,*v,*p1,*p2; crosslist a,b; link *r; int i,j,k,e; printf("十字链表乘法:\n"); createcross(a); createcross(b); c.m=a.m; c.n=b.n; c.t=0; c.rhead=(link *)malloc((a.m+1)*sizeof(link));//给行和列的头指针分 配内存 c.chead=(link *)malloc((b.n+1)*sizeof(link)); for(k=1;k<=a.m;k++)//初始化行，列的头指针 c.rhead[k]=NULL; for(k=1;k<=b.n;k++) c.chead[k]=NULL; r=(link *)malloc((b.n+1)*sizeof(link)); for(i=1;i<=a.m;i++) { u=(node *)malloc(sizeof(node)); u->e=0; u->i=0; u->j=0; for(k=1;k<=b.n;k++)//初始化r[] r[k]=u; p1=p=a.rhead[i]; for(j=1;j<=b.n;j++) { p=p1; q=b.chead[j]; v=(node *)malloc(sizeof(node));//初始化v，v为将插入c矩阵 的元素 v->e=0; v->i=i; v->j=j; while(p&&q) { if(p->j>q->i) q=q->down; else if(p->ji) p=p->right; else { v->e+=p->e*q->e; p=p->right; q=q->down; } } if(v->e)//如果不为零，则插入c矩阵中 { //同建立十字链表 if(c.rhead[i]==NULL||c.rhead[i]->j>j)//插入元素所在行无 非零元或首非零元的列标大于插入元素的列标 { v->right=c.rhead[i]; c.rhead[i]=v; } else { for(p2=c.rhead[i];(p2->right)&&(p2->right->jright);// 空循环找到第一个列标大于或等于插入元素列标的元素 v->right=p2->right; p2->right=v; } if(c.chead[j]==NULL||c.chead[j]->i>i)//插入元素所在列无 非零元或首非零元的行标大于插入元素的行标 { v->down=c.chead[j]; c.chead[j]=v; } else { for(p2=c.chead[j];(p2->down)&&(p2->down->idown);//空循 环找到第一个行标大于或等于插入元素行标的元素 v->down=p2->down; p2->down=v; } } } } } 5、主函数代码 void main() { juzhen A,B,C,D; crosslist a,b,c,d; lable: printf("请选择:1、稀疏矩阵的加法，并输出结果，2、稀疏矩阵乘法， 并输出结果\n"); 十字链表加法,并输出，4、十字链表乘法并输出，5、结 printf("\n3、 束:"); printf("\n"); int x; scanf("%d",&x); switch(x) { case 1: add(A,B,C); print(C); printf("\n"); goto lable; case 2: multy(A,B,C); print(C); printf("\n"); goto lable; case 3: a=addcross(); printcross(a); printf("\n"); goto lable; case 4: multycross(b); printcross(b); printf("\n"); goto lable; case 5: break; } printf("\n"); } 四、调试分析 1、开始时忘了引用&，因此结果一直不对，费了很长时间。 2、在做十字链表的加法时插入列结点时，只考虑了该列无非零元和非零元在插入元之前的情况，漏掉了有非零元，但非零元在插入元素之后的情况，费时不少。 3、做十字链表的乘法时，没有给临时结点动态分配内存，导致赋值时，每次都改变了原有矩阵中的值，今后注意此点。 4、做这个题，最重要的一点是把每一种情况都考虑到，否则在测试时总会出现意想不到的小错误。 5、本次课程设计将程序划分为三个部分:一般稀疏矩阵的存储与运算，利用十字链表对稀疏矩阵存储与运算，主程序。而前两部分又分为，创建，加法，乘法和输出四个小的部分，并且在思路分析上有相似的地方，使得设计时思路清晰，实现时调试顺利。通过本次的课程设计确实得到了一次很好的训练。 五、用户手册 1、本程序的运行环境为DOS操作系统，执行文件为:xishujuzhen.exe。 2、进入演示程在思路分析上有相似的地方序后即显示文本方式的用户界面: ********************************************************************* * 请选择:1、稀疏矩阵的加法，并输出结果，2、稀疏矩阵乘法，并输出结果 3、十字链表加法,并输出，4、十字链表乘法并输出，5、结束: 3、如果输入“3”，则会创建两个十字链表，并输出其相加的结果。 4、接收其他命令后会执行相应的元素按和显示相应结果。 六、测试结果 执行命令“1”:输入两个稀疏矩阵的非零元，输出相加后的结果 执行命令“2”:输入两个稀疏矩阵的非零元，输出相乘后的结果 执行命令“3”:输入两个稀疏矩阵的非零元，输出相加后的结果 执行命令“4”:输入两个稀疏矩阵的非零元，输出相乘后的结果 执行命令“5”:结束程序的运行 七、附录 Xishujuzhen.cpp:用C++语言编写的源代码文件。 课程设计.dsp:VC开发环境生成的

工程

路基工程安全技术交底工程项目施工成本控制工程量增项单年度零星工程技术标正投影法基本原理

文件， 课程设计.dsw:VC开发环境生成的WorkSpace文件，用来把多个工程组织到一个WorkSpace中。 课程设计.ncb:NCB是“No Compile Browser”的缩写，其中存放了供ClassView、WizardBar和Component Gallery使用的信息，由VC开发环境自动生成。无编译浏览文件。当自动完成功能出问题时可以删除此文件。编译工程后会自动生成。