数据结构（Java语言） 课件 项目六 矩阵-核算产品费用

项目六矩阵---核算产品费用目录项目六5123

典型工作任务6.1矩阵项目需求分析典型工作任务6.2矩阵数据结构设计典型工作任务6.3矩阵软件代码设计典型工作任务6.4矩阵软件测试执行典型工作任务6.5矩阵软件文档编写46典型工作任务6.6矩阵项目验收交付知识目标掌握数组的概念与性质掌握数组的逻辑结构及存储结构掌握矩阵的压缩存储掌握矩阵的基本运算技能目标能进行项目需求分析能进行矩阵的算法分析及编程能用矩阵的知识编程解决问题能进行软件测试及项目功能调整能撰写格式规范的软件文档思政目标掌握数组顺序存储，树立规矩意识掌握稀疏矩阵特殊处理，培养善于思考创新意识锻炼发现问题分析问题解决问题的逻辑思维编写算法细致严谨，养成科学严谨的学习习惯总体要求

有一家光明食品厂，它们的产品包括罐头、糖果、巧克力、饮料、啤酒。为了核算各类产品在一年中的成本费用，我们可以按月统计每类产品的成本，然后把一年12个月的统计表累加起来，就可以核算出各类产品的成本以及企业一年的生产成本。

为了分类统计，我们可以设计如表6-1所示的产品成本月统计表。

表6-1产品成本月统计表（单位：万元）典型工作任务6.1矩阵项目需求分析产品名称材料成本人工成本制造成本罐头1.451.230.35糖果0.980.870.65巧克力1.430.940.89饮料0.870.650.35啤酒0.840.610.56

有为了便于核算产品费用，本项目以光明食品厂的产品各项成本为例，使用数组对各类产品的各项费用进行输入及计算，具体需求如下：(1)使用数组存储每个月产品成本；(2)显示每个月的产品成本矩阵；(3)产品成本矩阵可进行转置；(4)产品成本矩阵可进行加法；(5)输出矩阵操作后结果。典型工作任务6.1矩阵项目需求分析6.2.1数组的概念

数组是相同类型的数据有序的集合，数组中每一个数据通常称为数组元素，数组元素用下标识别，下标的个数取决于数组的维数。

如果是一个下标确定一个元素，就是一维数组；如果是两个下标能确定一个元素，就是二维数组。【提示】上述为m×n阶矩阵是个二维数组，其中每个元素都可以用下标变量aij来表示，i为元素的行下标，j为元素的列下标典型工作任务6.2矩阵数据结构设计6.2.2数组结构具有的性质1．数组元素数目固定。一旦说明了一个数组结构，其元素不再有增减变化；

2．数组中数据元素具有相同的数据类型；3．数组元素的下标关系具有上下界的约束且下标有序；4.数组元素的值由数组名和下标唯一确定；5.数组名是数组的首地址，每个元素是连续存放的。对数组可以施加的操作主要有以下两种：取值操作：给定一组下标，读其对应的数据元素。赋值操作：给定一组下标，存储或修改与其相对应的数据元素。典型工作任务6.2矩阵数据结构设计6.2.3数组的顺序存储

一般采用顺序存储结构表示数组。顺序存储结构即用一块连续的存储空间存储数组元素。（1）按行优先存储：一行分配完了接着分配下一行。如前面的m×n阶矩阵的二维数组，按行存储数据：a11,a12,…,a1n,a21,a22,…,a2n,…,am1,am2,…,amn（2）按列优先存储：一列一列地存放。如前面的m×n阶矩阵的二维数组，按列存储数据：a11,a21,…,am1,a12,a22,…,am2,…,a1n,a2n,…,amn典型工作任务6.2矩阵数据结构设计对于一维数组A[n],数据元素的存储地址为LOC(i)=LOC(1)+i×L(1≤i≤n),其中，LOC(i)是第i个元素的存储地址，LOC(1)是数组的首地址，L是每个数据元素占用的字节数。对于一个m×n的二维数组A[m][n]，以行为主序存储时，数组元素aij的存储地址为：LOC(aij)=LOC(a11)+((i-1)×n+j-1)×L(0≤i≤m,0≤j≤n)其中，LOC(aij)是第i行第j列数组元素的存储地址，LOC(a11)是数组的首地址，L是每个数据元素占用的字节数。若以列为主序存储二维数组A[m][n]，则数组元素aij的存储地址为：LOC(aij)=LOC(a11)+((j-1)×m+i-1)×L(1≤i≤m,1≤j≤n)典型工作任务6.2矩阵数据结构设计

将计算数组元素存储地址的公式推广到一般情况，可以得到n维数组A[m1][m2]…[mn]的数据元素a[i1][i2]…[in]的存储地址：LOC(i1,i2,…,in)=LOC(0,0,…,0)+(i1×m2×…mn+i2×m3×…×mn+…+in-1×mn+in)×L典型工作任务6.2矩阵数据结构设计

6.2.4特殊矩阵的压缩存储

特殊矩阵是具有很多相同数据元素或者零元素且数据元素的分布具有一定规律的矩阵。m×n矩阵用二维数组存储时，最少需要m×n个存储单元。当矩阵的阶数比较大时，会浪费大量的存储空间，显然是不合适的。

1.对称矩阵若n阶矩阵满足性质：aij=aji

，则称为对称矩阵。为每一对对称元素分配一个存储空间，因此可以将n×n个元素存储到n(n+1)/2个存储单元中。典型工作任务6.2矩阵数据结构设计

对于任意给定的一组下标(i,j),均可以在S中找到矩阵元素aij，反之，对于所有的k=1,2,…,n(n+1)/2,都能确定s中的元素在矩阵中的位置(i,j)。

典型工作任务6.2矩阵数据结构设计a00a01a02…a0n-1a11…an-1,0…an-1,n-12.三角矩阵

三角矩阵分为上三角矩阵和下三角矩阵。下三角矩阵是指矩阵的主对角线（不包括主对角线）上方的元素的值均为0；上三角矩阵是指矩阵的主对角线（不包括主对角线）下方的元素的值均为0。

下三角矩阵上三角矩阵典型工作任务6.2矩阵数据结构设计3.对角矩阵

对角矩阵是指矩阵的所有非零元素都集中在以主对角线为中心的带状区域中，即除去主对角线上和直接在主对角线上、下方若干条对角线上的元素之外，其余元素皆为零。若以一维数组进行存储，则存储形式如下：典型工作任务6.2矩阵数据结构设计123456789101112a12a21a22a23a32a33a34a43a44a45a54a55

6.2.4特殊矩阵的压缩存储矩阵阶数比较大，零元素个数比较多，非零元素个数比较少，且分布无规律，这类矩阵就是稀疏矩阵。设矩阵A是一个m×n的矩阵，其中有t个非零元素，设称为稀疏因子，如果<=0.05，矩阵A就是稀疏矩阵。典型工作任务6.2矩阵数据结构设计

1.三元组表存储对于稀疏矩阵中的每个元素，都由行下标、列下标和数值三个部分唯一确定，因此，可以用这三项内容表示稀疏矩阵中的元素，这就是三元组表示法，如下形式：（i,j,value）i表示非零元素的行下标，j表示非零元素的列下标，value表示非零元素的值。典型工作任务6.2矩阵数据结构设计典型工作任务6.2矩阵数据结构设计行下标列下标元素值13315221152611352254763321）三元组顺序表的定义publicclassTripleNode//三元组结点类{ publicintrow;//行号 publicintcol; //列号 publicdoublevalue; //元素值

publicTripleNode(introw,intcol,doublevalue)//有参构造函数{ this.row=row; this.col=col; this.value=value;}publicTripleNode()//无参构造函数{this(1,1,0);}}典型工作任务6.2矩阵数据结构设计稀疏矩阵的三元组顺序表类定义：publicclassSparseMatrix{ publicTripleNodedata[]; //三元组表 publicintrows; //行数 publicintcols; //列数 publicintnums; //非零元素个数 publicSparseMatrix(intmaxSize){ //构造方法 data=newTripleNode[maxSize];//为顺序表分配maxSize个存储单元 for(inti=0;i<data.length;i++){

data[i]=newTripleNode(); } rows=0; cols=0; nums=0; } publicvoidprintMatrix()//打印输出稀疏矩阵 { System.out.println("稀疏矩阵的三元组存储结构"); System.out.print("行数:"+rows+",列数"+cols+",非零元素个数："+nums+"\n");for(inti=0;i<nums;i++) System.out.print(data[i].row+"\t"+data[i].col+"\t"+data[i].value+"\n");} }典型工作任务6.2矩阵数据结构设计2）三元组表的基本操作

初始化三元组顺序表publicSparseMatrix(doublemat[][]) { inti,j,k=0,count=0; rows=mat.length; cols=mat[0].length; for(i=0;i<rows;i++) //统计非零元素的个数 for(j=0;j<mat[i].length;j++) if(mat[i][j]!=0) count++; nums=count; //非零元素的个数 data=newTripleNode[nums];//申请三元组结点空间 for(i=0;i<rows;i++) for(j=0;j<mat[i].length;j++) if(mat[i][j]!=0) { data[k]=newTripleNode(i,j,mat[i][j]); //建立三元组 k++; } }典型工作任务6.2矩阵数据结构设计

矩阵转置矩阵转置是一种简单的矩阵运算，指的是把矩阵中每个元素的行号和列号互换。

转置-------

矩阵A’转置矩阵A’的三三元组表元组表(按行优先)典型工作任务6.2矩阵数据结构设计行下标列下标元素值3135121215621153224573632行下标列下标元素值1215313363245751253226211矩阵转置算法：publicSparseMatrixtran() { SparseMatrixtr=newSparseMatrix(nums); tr.cols=rows; tr.rows=cols; tr.nums=nums; intn=0; for(intcol=0;col<cols;col++) for(intm=0;m<nums;m++) if(data[m].col==col) { tr.data[n].row=data[m].col; tr.data[n].col=data[m].row; tr.data[n].value=data[m].value; n++; } returntr; }典型工作任务6.2矩阵数据结构设计(3)矩阵快速转置快速转置算法的思想为：按三元组表A的次序进行转置，转置后直接放到三元组表B的正确位置上。转置过程中的元素并不连续放入到B.data，而是直接放到B.data中应有的位置上，只需对A.data扫描一次。因为A中第一列的第一个非零元素一定存储在B.data[1]中，如果还不知道第一列非零元素的个数，那么第二列的第一个非零元素在B.data中的位置便等于第一列的第一个元素在B.data中的位置加上第一列的非零元素的个数，依次类推，因为A中三元组的存放顺序是先行后列，对同一行来说，必定先遇到列号小的元素，这样只需要扫描一遍A.dta即可。典型工作任务6.2矩阵数据结构设计

矩阵快速转置算法：publicSparseMatrixfasttran(){

SparseMatrixtr=newSparseMatrix(nums);//创建矩阵对象

tr.cols=rows; //行数变列数 tr.rows=cols; //列数变行数 tr.nums=nums; //非零元素个数 inti,j=1,k=0; int[]num,cpos; if(nums>0) { num=newint[cols+1]; cpos=newint[cols+1]; for(i=1;i<=cols;i++) { num[i]=0; } for(i=1;i<=nums;i++) { j=data[i].col; num[j]++; } cpos[1]=1;典型工作任务6.2矩阵数据结构设计

for(i=2;i<=cols;i++){ cpos[i]=cpos[i-1]+num[i-1];}//执行转置操作for(i=1;i<=nums;i++) //扫描整个三元组顺序表{ j=data[i].col; k=cpos[j]; tr.data[k].row=data[i].col; tr.data[k].col=data[i].row; tr.data[k].value=data[i].value; cpos[j]++;

}}}典型工作任务6.2矩阵数据结构设计(4)矩阵的加法

当两个矩阵进行加法运算时，要求两个矩阵的大小必须相同，即行数和列数分别对应相等，且结果仍为一个具有相同大小的矩阵，并且其三元组线性表仍然是有序线性表，即三元组是按照行、列号升序排列的。2.十字链表存储

十字链表是稀疏矩阵的另一种存储结构，在十字链表中矩阵的每一个非零元素用一个结点表示，每个结点由5个域组成。row域存放该元素的行号，col域存放该元素的列号，value域存放该元素的值，此外还有两个链域：right域用于链接同一行中的下一个非零元素，down域用以链接同一列中的下一个非零元素。典型工作任务6.2矩阵数据结构设计rowcolvaluedownright典型工作任务6.2矩阵数据结构设计稀疏矩阵的十字链表表示的结点结构类定义：publicclassOLnode{ //十字链表结点类 publicintrows; //元素的行号 publicintcols; //元素的列号publicintvalue; //元素的值 publicOLnoderight; //行链表指针 publicOLnodedown; //列链表指针publicOLnode(){this(0,0,0); //无参构造方法}publicOLnode(introws,intcols,intvalue) //有参构造方法 { this.rows=rows; this.cols=cols; this.value=value; right=null; down=null; }}典型工作任务6.2矩阵数据结构设计稀疏矩阵的十字链表类定义：publicclassCrosslist{ //十字链表 publicintmu,nu,tu; //行数、列数、非零元素个数 publicOLnode[]rhead,chead; //行、列指针数组 publicCrosslist(intm,intn) { mu=m; nu=n; rhead=newOLnode[m]; chead=newOLnode[n]; tu=0; for(inti=0;i<m;i++) rhead[i]=newOLnode(); for(inti=0;i<n;i++) chead[i]=newOLnode(); }…}典型工作任务6.2矩阵数据结构设计以光明食品厂每月产品成本统计表的处理为主，设计本系统的程序，系统由两部分组成，第1部分为矩阵的6种操作算法，包含矩阵三元组结点的无参初始化、有参初始化、元组顺序表的两个有参初始化、三元组顺序表输出、矩阵相加，第2部分为主程序Test，该程序实现矩阵操作算法的调用及数据输出及显示。程序框图如图6-10所示。

图6-10核算产品成本程序框图

典型工作任务6.3矩阵软件代码设计本系统均未使用数组0下标元素，因此数组大小均多申请1个空间，核算产品成本系统源代码如下publicclassTripleNode//三元组结点类{ publicintrow;//行号 publicintcol; //列号 publicdoublevalue; //元素值//1.无参构造方法publicTripleNode(){this(0,0,0);} //2.有参构造方法publicTripleNode(introw,intcol,doublevalue)//行，列，元素值{ this.row=row; this.col=col; this.value=value;}}

典型工作任务6.3矩阵软件代码设计publicclassSparseMatrix//三元组类{ publicTripleNodedata[];//三元组表 publicintrows; //行数 publicintcols; //列数 publicintnums; //非零元素个数//3.有参构造方法

publicSparseMatrix(intmaxSize){ data=newTripleNode[maxSize+1];//为顺序表分配maxSize个存储单元 for(inti=1;i<=data.length;i++)//创建三元组表{ data[i-1]=newTripleNode();} rows=1; cols=1; nums=0;}

典型工作任务6.3矩阵软件代码设计//4.有参构造方法

publicSparseMatrix(doublemat[][])//稀疏矩阵{inti,j,k=1,count=0;rows=mat.length;//矩阵行数cols=mat[1].length;//矩阵列数for(i=1;i<=rows;i++)//统计非零元素的个数 for(j=1;j<=mat[i-1].length;j++) if(mat[i-1][j-1]!=0) count++; nums=count; data=newTripleNode[nums+1]; //申请三元组结点空间 for(i=1;i<=rows;i++) for(j=1;j<=mat[i-1].length;j++) if(mat[i-1][j-1]!=0) { data[k]=newTripleNode(i,j,mat[i-1][j-1]); //建立三元组 k++; } }

典型工作任务6.3矩阵软件代码设计//5.打印输出矩阵三元组表publicvoidprintMatrix() { System.out.println("矩阵的三元组存储结构"); System.out.print("行数:"+rows+",列数"+cols+",非零元素个数："+nums+"\n"); for(inti=1;i<=nums;i++) System.out.print(data[i].row+"\t"+data[i].col+"\t"+data[i].value+"\n"); }//6.矩阵加法publicstaticSparseMatrixSpareAdd(SparseMatrixam,SparseMatrixbm) //矩阵am+bm {SparseMatrixsm=newSparseMatrix(am.rows*am.cols);//矩阵sm存和 inti=1,j=1,k=1; doubletemp; if(am.rows!=bm.rows||am.cols!=bm.cols)//判断am与bm矩阵大小 { System.out.print("两个矩阵大小不同，无法进行加法运算"); System.exit(1); } sm.rows=am.rows; sm.cols=am.cols;

典型工作任务6.3矩阵软件代码设计while(i<=am.nums&&j<=bm.nums)//当am和bm矩阵三元组表均未扫描结束{ if(am.data[i].row==bm.data[j].row){if(am.data[i].col<bm.data[j].col)//am元素在bm前面，先存am的元素 { sm.data[k].row=am.data[i].row; sm.data[k].col=am.data[i].col; sm.data[k].value=am.data[i].value;k++;i++; } elseif(am.data[i].col>bm.data[j].col)//bm元素在am前，先存bm的元素{ sm.data[k].row=bm.data[j].row; sm.data[k].col=bm.data[j].col; sm.data[k].value=bm.data[j].value; k++;j++; }

典型工作任务6.3矩阵软件代码设计else//两个元素在同一个位置，两者相加{temp=am.data[i].value+bm.data[j].value; if(temp!=0) { sm.data[k].row=am.data[i].row; sm.data[k].col=am.data[i].col; sm.data[k].value=temp; i++;j++;k++; }else{i++;j++;}//相加元素为0，各自取下一个元素 } } elseif(am.data[i].row<bm.data[j].row)//两个元素不在同一行，am在bm前面 { sm.data[k].row=am.data[i].row; sm.data[k].col=am.data[i].col; sm.data[k].value=am.data[i].value; k++;i++; }

典型工作任务6.3矩阵软件代码设计else //bm在am的前面{ sm.data[k].row=bm.data[j].row; sm.data[k].col=bm.data[j].col; sm.data[k].value=bm.data[j].value; k++;j++;} }while(i<=am.nums)//bm先结束，把am剩余插入三元组表{ sm.data[k].row=am.data[i].row; sm.data[k].col=am.data[i].col; sm.data[k].value=am.data[i].value; k++;i++; }

典型工作任务6.3矩阵软件代码设计while(j<=bm.nums)//am先结束，把bm剩余插入三元组表 { sm.data[k].row=bm.data[j].row; sm.data[k].col=bm.data[j].col; sm.data[k].value=bm.data[j].value; k++;j++; }sm.nums=k-1;//非零元素个数 returnsm; }//7.主程序importjava.util.Scanner;publicclasstest{ staticdoubleJan[][]=newdouble[5][3];//1月成本统计 staticdoubleFeb[][]=newdouble[5][3];//2月成本统计

典型工作任务6.3矩阵软件代码设计

staticdoubleadd[][]=newdouble[5][3];//成本求和 staticSparseMatrixsum;//sum和矩阵三元组 staticSparseMatrixtran;//tran转置矩阵三元组staticSparseMatrixfirst;//1月成本矩阵 staticSparseMatrixsecond;//2月成本矩阵 publicstaticvoidmain(String[]args) { intflag=1; intchoice; while(flag==1) { menu(); System.out.print("请输入您的选择:"); Scannersc=newScanner(System.in);choice=sc.nextInt(); switch(choice){ case0:flag=0;break;case1:input();break;//输入月统计表 case2:output();break;//输出月成本矩阵及三元组表 case3:transpose();break;//输出月成本矩阵转置及三元组表case4:add();break;//1月和2月成本求和 default:System.out.println("输入有误，请重新输入！"); } } System.out.println("感谢您的使用！"); } }

典型工作任务6.3矩阵软件代码设计publicstaticvoidmenu(){//系统主菜单 System.out.println("************************************"); System.out.println("**********核算产品成本系统*********"); System.out.println("*****1.输入月统计数据****"); System.out.println("*****2.查看月统计三元组表****"); System.out.println("*****3.月统计矩阵转置****"); System.out.println("*****4.产品成本核算矩阵****"); System.out.println("*****0.退出****");System.out.println("************************************");}publicstaticvoidinput()//输入指定月数据{ System.out.print("请输入月份（1或2）:"); Scannerm=newScanner(System.in); intchoicemonth=m.nextInt(); Scannerinm=newScanner(System.in); System.out.println("请输入5行3列数据："); for(inti=0;i<5;i++) for(intj=0;j<3;j++) {

典型工作任务6.3矩阵软件代码设计

if(choicemonth==1)//1月份数据存入Jan数组 Jan[i][j]=inm.nextDouble(); if(choicemonth==2)//2月份数据存入Feb数组 Feb[i][j]=inm.nextDouble(); } System.out.println(choicemonth+"月数据输入完成");}publicstaticvoidoutput()//输出指定月数据{ System.out.print("请选择查看月份（1或2）:"); Scannerm=newScanner(System.in); intmonth=m.nextInt(); System.out.println(month+"月统计数据矩阵"); if(month==1) { for(inti=0;i<5;i++) { for(intj=0;j<3;j++) { System.out.print(Jan[i][j]+"");//输出选择月份的矩阵 first=newSparseMatrix(Jan);//生成1月份矩阵三元组表 } System.out.print("\n"); } first.printMatrix(); }

典型工作任务6.3矩阵软件代码设计if(month==2) { for(inti=0;i<5;i++) { for(intj=0;j<3;j++) { System.out.print(Feb[i][j]+"");//输出选择月份的矩阵 second=newSparseMatrix(Feb);//生成1月份矩阵三元组表 } System.out.print("\n"); } second.printMatrix(); }}publicstaticvoidtranspose()//转置指定月成本矩阵 { System.out.print("请输入月份（1或2）:"); Scannerscan=newScanner(System.in); intm=scan.nextInt(); if(m==1) tran=first.tran();//1月份矩阵转置

典型工作任务6.3矩阵软件代码设计 if(m==2) tran=second.tran();//2月份矩阵转置 tran.printMatrix();//输出转置后矩阵三元组表}publicstaticvoidadd()//1，2月份成本矩阵求和{ sum=SparseMatrix.SpareAdd(first,second); System.out.println("1,2月份成本核算矩阵"); for(inti=0;i<5;i++) { for(intj=0;j<3;j++) {add[i][j]=Jan[i][j]+Feb[i][j]; System.out.print(add[i][j]+"");//输出求和矩阵 } System.out.print("\n"); } sum.printMatrix();}}

典型工作任务6.3矩阵软件代码设计使用数据结构中的数组编写核算产品费用的程序，通过Eclipse编译和运行，选择输入1月统计表数据，测试结果如图6-11所示。输入菜单“2”及月份“1”，查看1月统计矩阵三元组表，测试结果如图6-12所示。

图6-111月份统计数据图

图6-121月统计矩阵的三元组表

典型工作任务6.4矩阵软件测试执行通过Eclipse编译和运行，选择菜单“3”及输入月份“1”，查看1月统计矩阵的转置三元组表，测试结果如图6-13所示。继续选择菜单“1”及输入月份“2”，查看2月统计数据表，如图6-14所示。

图6-131月统计矩阵转置后的三元组表

图6-14输入2月统计数据

典型工作任务6.4矩阵软件测试执行通过Eclipse编译和运行，选择菜单“2”及输入月份“2”，查看2月统计矩阵的转置三元组表，测试结果如图6-15所示。选择菜单“4”，核算1月和2月产品成本，测试结果如图6-16所示。

图6-152月统计矩阵三元组表

图6-161月和2月产品成本核算矩阵

典型工作任务6.4矩阵软件测试执行

为了构造出稀疏矩阵,系统以表6-6、表6-7所示两个月的产品成本统计表数据为例,进行系统功能测试。

表6-61月份产品成本统计表（单位：万元）

表6-72月份产品成本统计表（单位：万元）

典型工作任务6.5矩阵软件文档编写产品名称材料成本人工