数据结构-实验6-稀疏矩阵(共6页).doc

1、 实验目的（1) 掌握稀疏矩阵三元组表的存储方法；（2) 掌握稀疏矩阵三元组表的创建、显示、转置和查找算法2、 实验内容（1) 编写稀疏矩阵三元组表的存储程序；（2) 编写稀疏矩阵三元组表的创建、显示、转置和查找程序3、 实验要求（1) 用C（C++）语言完成算法设计和程序设计2) 上机调试通过实验程序3) 输入数据，检验程序运行结果4) 给出具体的算法分析，包括时间复杂度和空间复杂度等5) 撰写实验报告（把输入实验数据及运行结果用抓图的形式粘贴到实验报告上）4、 实验步骤与源程序 ⑴ 实验步骤先从具体的问题中抽象出适当的数学模型，然后设计出相应的算法，其中，需要设计一个主函数来实现菜单的输出，设计另外五个函数来求分别实现新建，转置，查找，显示，最后，串接函数，并调试程序，在调试的时候，我先进行新建操作，输入数据之后，然后开始转置操作，再进行查找其中的非零元素，多次调试后，发现没有问题，得出实验结果，并截图 ⑵ 源代码#include#include#include#include#define SMAX 100 // 三元组非零元素的最大个数typedef struct SPNode // 定义三元组{ int i,j,v; // 三元组非零元素的行、列和值};typedef struct sparmatrix // 定义稀疏矩阵{ int rows,cols,terms; // 稀疏矩阵行、列和非零元素的个数 SPNode data[SMAX]; // 三元组表};sparmatrix CreateSparmatrix() // 创建稀疏矩阵{ sparmatrix A; printf("\n\t\t请输入稀疏矩阵的行数,列数和非零元个数(用逗号隔开): "); scanf("%d,%d,%d",&A.rows,&A.cols,&A.terms); for(int n=0;n<=A.terms-1;n++) { printf("\n\t\t输入非零元值(格式: 行号,列号,值): "); scanf("%d,%d,%d",&A.data[n].i,&A.data[n].j,&A.data[n].v); } return A;}sparmatrix Trans(sparmatrix A) // 转置稀疏矩阵{ sparmatrix B; B.rows=A.cols; B.cols=A.rows; B.terms=A.terms; for(int n=0;n<=A.terms-1;n++) { B.data[n].i=A.data[n].j; B.data[n].j=A.data[n].i; B.data[n].v=A.data[n].v; } return B;}void ShowSparmatrix(sparmatrix A) // 显示稀疏矩阵{ int k; printf("\n\t\t"); for(int x=0;x<=A.rows-1;x++) { for(int y=0;y<=A.cols-1;y++) { k=0; for(int n=0;n<=A.terms-1;n++) { if((A.data[n].i==x)&&(A.data[n].j==y)) { printf("%8d",A.data[n].v);k=1;} } if(k==0) printf("%8d",k); } printf("\n\t\t"); }}void SearchSparmatrix(sparmatrix A,int s) // 查找稀疏矩阵中非零元素{ int n,t; t=A.terms; for(n=0;n

先做简单的输出，一步步的再做其它格式的设置在实验的过程中，我加深了对稀疏矩阵各种操作的理解，因为稀疏矩阵非零元素较少，为了节省空间可以只存储非零元素的值，并记下它所在的行和列的信息，这样就可以方便找出相应的元素，在做矩阵转置的时候，尤其要注意，算法不能只是进行简单的行列互换，转化之后，行的下标不是从小到大排列的，所以必须再对行的下标进行排序才行若把具有同一行号的非零元素用一个链表连接起来，则稀疏矩阵中的若干行组成若干个单向链表，合起来就成为带行指针的单向链表了所以掌握稀疏矩阵的各种操作算法很有必要。