数据结构实验(4)数组

《数据结构实验(4)数组》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、计算机系数据结构实验报告（4）实验目的：深入研究数组的存储表示和实现技术，着重掌握对稀疏矩阵的表示方法及其运算的实现。问题描述：稀疏矩阵是指那些多数元素为零的矩阵。利用‘稀疏’特点进行存储和计算可以大大节省存储空间，提高效率。通过对稀疏矩阵的存储表示，实现矩阵的基本操作。实验要求：文法是一个四元1．要求矩阵的输入形式采用三元组表示，以“带行逻辑链接信息”的三元组顺序表表示稀疏矩阵。2．设计矩阵的逆置算法，实现矩阵的逆置。3．实现两个稀疏矩阵的相加、相减和相乘等运算。4．要求运算结果的矩阵则以通常的阵列形式出现。算法分析：（1）矩阵的输入采用的是三元

2、组的形式，这样直接输入的话输入步骤显得繁琐（特别是非零元个数较多的情况下），而且一旦输入有误，之前的输入也得重现，因此，为了简化用户端的输入步骤并增加其容错性，可考虑先在一个缓冲区里将数据全部输入，然后由程序自动输入矩阵，在这里可以用一个文本文档存储数据，然后程序打开文本文档，完成输入。（2）由于文本文档为ASCII文件，读入的是字符，要先转换成整型，并将处理后的数据入栈，最后出栈完成输入。具体步骤与实验2的表达式求值类似。（3）在输入之后，行逻辑链接信息并未完成，此处使用Gain_rpos()，要求在已知三元组的情况下求出各行的rpos利用每行非

3、零元个数与第一行的rpos=1及其递归来完成。（4）向着满足用户界面友好方向考虑，可以在输入后，即刻输出矩阵的阵列形式。其中输出函数Output()，使用两层for循环遍历每个元素，判断某行某列元素值非零则输出其值，否则输出为零。（5）本程序要实现的矩阵运算包括转置、加减、相乘。转置算法采用快速转置法，矩阵的相加减使用双层for循环和累加器。（6）使用goto语句完成程序的循环。实验内容和过程：源程序：#include#include#include#includeusingna

4、mespacestd;//-----稀疏矩阵的三元组顺序表存储表示-----#defineMAX12500#defineMAXR110typedefintElemType;typedefstruct{inti,j;ElemTypee;}Triple;typedefstruct{intmu,nu,tu;Tripledata[MAX+1];-8-intrpos[MAXR+1];}RLSMatrix;intIn(charch)//定义辅助函数：判断是否为数字字符{if(ch>='0'&&ch<='9')return1;elsereturn0;}FILE*

5、input(RLSMatrix&M,FILE*fp)//以三元组形式输入一个矩阵，利用文件类型指针读取文本文档内的数据{charch,flag='';inta,b,k,num=0;stackstatus;while(num<3

6、

7、In(flag)==1)//每次读取一个字符，并将字符型转换成整型{ch=fgetc(fp);if(!In(ch)){flag=ch;continue;}if(In(flag)==1){status.pop();--num;a=a*10+((int)ch-48);}elsea=(int)ch-48;status.

8、push(a);//入栈++num;flag=ch;}M.tu=status.top();status.pop();//出栈并输入行数，列数，非零元个数M.nu=status.top();status.pop();M.mu=status.top();status.pop();num=0;for(k=1;k<=M.tu;++k)//完成非零元的输入{while(num<3

9、

10、In(flag)==1){ch=fgetc(fp);if(!In(ch)){flag=ch;continue;}if(In(flag)==1){status.pop();--nu

11、m;b=b*10+((int)ch-48);}elseb=(int)ch-48;status.push(b);++num;flag=ch;}num=0;M.data[k].e=status.top();status.pop();M.data[k].j=status.top();status.pop();M.data[k].i=status.top();status.pop();}-8-returnfp;//返回当前指针的值，以便下个矩阵的输入}intInput(RLSMatrix&M,RLSMatrix&N)//完成本程序两个矩阵的输入{FILE*

12、fp,*FP;if((fp=fopen("E:\矩阵数据.txt","r"))==NULL)//在文本文档中打开文件，读