数据结构实验报告书.doc

数据结构实验报告 日期： 2009 年 04 月 19 日 实验成绩：_班 级姓名学号实验项目名称 对串的删除操作指导教师实验目的： 学习稀疏矩阵的压缩式存储，了解三元组的存储架构，并学习矩阵的转置；了解线性表的逻辑结构，并熟练掌握数组的使用；实验内容：1. 实现对稀疏矩阵的转置，用两种方法。2. 编写算法实现两个数组相乘，并输出结果；3. 利用二维数组实现对二维数组的马鞍点算法；实验要求：1、 必须有可展示的实验结果，并将实验结果或结论写在本实验报告中。2、 要求实验步骤思路清晰，发现问题请及时追踪并记录。3、 实验报告书要求排版整齐，采用书面用语，态度端正，避免错别字。4、 在规定时间内将合格的实验报告电子版和打印稿一起交到各班课代表处，过期课代表可不予等候，不合格者重做。实验步骤：（含基本步骤及异常情况记录等：问题你是怎么解决的，在实验过程中碰到的哪些问题）1. 首先，打开vc界面，创建工程并输入工程名，完成后确定即可。然后新建cpp源文件，输入文件名点击确定即可。2. 在输入相关代码之后，进行编译，然后执行程序，若程序正常，则会出现运行界面，否则在编译时会出现错误。根据提示可进行修改。3. 在矩阵转置调试过程中，由于结构体element中含有模板，即item变量的类型为T所以存在在赋值过程中，出现错误无法进行。解决办法是不对变量进行模板定义只是单纯的声明int类型而已；4. 在函数实现过程中，函数体循环体，若在每个循环体中书写如下：for(int i=1;ia.nu;i+) for(int i=0;ia.tu;i+)则在编译过程中会出现错误，即i已经定义，因此把第二句换成for(int j=0;ja.tu;j+)即可；5. 当创建动态数组时出现异常，用new来创建动态存储空间，char p=new pn；new声明的是指针数组，而char p声明的仅是数组，因此应该把p声明为指针。6. 再循环体中for(int i=1;ia.nu;i+) 该语句的括号内必须对i进行类型声明即int 如果只是单纯的for( i=1;ia.nu;i+)则程序会出错7. 在马鞍点求解过程中，由于是二维数组，所以定义时必须满足下标支持相应的数值否则定义数组出现错误。这是二维数组定义规则8.在求解马鞍点过程中，声明数组用于存储每行中最小值即int minn;但这是错误的，数组中的n虽然是形参但作为不定的内存是不被认可的。因此应该对该数组进行动态声明或者是int min100; 存储空间定义为一较大值。9.关于二维指针的应用也出现过相应问题。二维指针*p刚开始时指向数组的首地址，在函数调用中函数体实现内容中把指针所指向的值给相应的变量用得语句*(a+(i*j)此句为获得指针中的数值，而*(ai+j) 则是取其地址而已。关键源程序及相应注释：（程序类作业选用，美工设计类可略）1. 稀疏矩阵的转置#include#include/templatestruct element int row; int col; int item;const int MaxTerm=100; /声明常量struct SparseMatrixelement dataMaxTerm; int mu,nu,tu;void Trans1(SparseMatrix A,SparseMatrix &B) B.mu=A.nu; /设置行数列数以及非零元素的个数；B.nu=A.mu;B.tu=A.tu;if(B.tu0) /若存在非零元素则转换；int pb=0;for( int col=0;colA.nu;col+) /依次考察每一列for(int pa=0;paA.tu;pa+) /在a中扫描整个三元组；if(A.datapa.col=col) /对col列元素进行处理；B.datapb.row=A.datapa.col;B.datapb.col=A.datapa.row;B.datapb.item=A.datapa.item;coutB.datapb.row B.datapb.col B.datapb.itemendl;pb+;void main()element data4;/data0=0,0,1;data1=0,1,3;/data2=1,1,2;data3=2,1,5;/SparseMatrix A=data,5,6,3; /对对结构体元素负初值；SparseMatrix a;a.data0.row=0;a.data0.col=0;a.data0.item=2;a.data1.row=0;a.data1.col=1;a.data1.item=3;a.data2.row=1;a.data2.col=1;a.data2.item=2;/a.data1=0,1,3;a.data2=1,1,2;/a.data3=2,1,5;a.mu=5;a.nu=5;a.tu=4;SparseMatrix B; Trans1(a,B); /函数调用#include/templatestruct elementint row;int col;int item;struct SparseMatrixelement data100; int mu,nu,tu;void Trans2(SparseMatrix a,SparseMatrix &b)b.mu=a.nu;b.nu=a.mu;b.tu=a.tu; /设置行数列数以及非零元素的个数；int num100;int cpot100;if(b.tu0) /若存在非零元素则转换；for(int i1=0;i1a.nu;i1+) /A中每一列非零元素个数初始化为零numi1=0;for(int i2=0;i2a.tu;i2+) /求矩阵中每一列非零元素个数int j=a.datai2.col; /取三元组的序号 numj+; cpot0=0; /A中第零列第一个非零元素在B中位置为零； for(int i3=1;i3a.nu;i3+) /求A中每一列第一个非零元素在B中的下标 cpoti3=cpoti3-1+numi3-1; for(int i=0;ia.tu;i+) /扫描三元组表A int j=a.datai.col; /当前三元族的列号； int k=cpotj; /当前三元组在B中的下标b.datak.row=a.datai.col;b.datak.col=a.datai.row;b.datak.item=a.datai.item;coutb.datak.row b.datak.col b.datak.itemendl;cpotj+; /预置同一列的三元组的下一个列标void main()element data4;/data0=0,0,1;data1=0,1,3;/data2=1,1,2;data3=2,1,5;/SparseMatrix A=data,5,6,3;SparseMatrix a;a.data0.row=0; /对对结构体元素负初值；a.data0.col=0;a.data0.item=2;a.data1.row=0;a.data1.col=1;a.data1.item=3;a.data2.row=1;a.data2.col=1;a.data2.item=2;/a.data1=0,1,3;a.data2=1,1,2;/a.data3=2,1,5;a.mu=5;a.nu=5;a.tu=4;SparseMatrix B; Trans2(a,B);2. 用二维数组求马鞍点#include/templatevoid search1(int *a,int n,int m) /查询函数/T * min=new Tn;int min100; /声明一个数组用于存储一行中的最小值；/int * listnumber=new intn;int listnumber100; /用于存储每行中的最小值的列标；for(int i1=0;i1n;i1+)mini1=ai1; /负初值；listnumberi1=0;for(int j=0;j(*(a+(i1*j) /该循环体实现对一列中所用元素求最小值得功能；mini1=(*(a+(i1*j);listnumberi1=j;/T *max=new Tm;int max100; /声明一个数组用于存储一列中的最大值；int hangnumber100; /用于存储每行中的最小值的列标；/int *hangnumber=new intm;for(int j=0;jm;j+)maxj=(*(a+j);hangnumberj=0;for(int i=0;in;i+) /该循环体实现了对每列求最大值的功能；if(maxj(*(a+(i*j)maxj=(*(a+(i*j);hangnumberj=i;for(int i=0;in;i+) /该函数体语句的作用是判断行的最小值与列的最大值是否为同一个值，若为同一个则为马鞍点否则不是；for(int j=0;jm;j+)if(mini=maxj)if(listnumberi=j)if(hangnumberj=i)coutminiendl;void main()int n,m;n=3;m=4;int a34=1,2,3,4,1,2,3,4,1,2,3,4;/cout请输入数组行数与列数nm; /int *an=new intnm;/cout输入数组元素endl;/for(int i=0;in;i+)/for(int j=0;jaij;int *p=&a00; /声明指针指向第一个地址；search1(p,n,m); /函数体调用3. 设计函数实现两个矩阵相乘#includevoid Mutiply(int *a,int *b,int na,int ma,int nb,int mb) /函数体用于实现乘法；其中两个指针为指针数组，其他分表表示数组的行数列数；if(ma=nb) /两个矩阵相乘必须满足第一个矩阵列数与第二个矩阵行数相等；int c100100; /用于存储相乘所的结果for(int i=0;ina;i+)for(int j=0;jmb;j+)int t=0;for(int r=0;rma;r+) /各相应元素相乘，所得结果相加然后存储在sum中；int sum=0; sum=(*(a+(i*j) * (*(b+(r*j);t=t+sum;cij=t;/coutcijendl;for(int c1=0;c1na;c1+) /输出结果矩阵for(int d=0;dmb;d+)cout*(*(c+c1)+d) ;coutendl;elsecout两个数组应满足第一个数组列数等于第二个数组行数endl;void main()int a23=1,2,3,2,3,4;int b32=1,2,2,3,3,4;int *p=&a00;int *q=&b00;Mutiply(p,q,2,3,3,2);实验体会： 1. 稀疏矩阵的存储用三元组表示存储结构会在一定程度上节约存储空间，方便快捷。2. 在结构体中，每一个元素的赋值可以通过整体赋值也可以单个进行赋值，但进行选择时应注意是否存在非相应类型的元素。3. 对数组进行声明时，须指定存储空间，尽量超过数组元素的最大值，或者动态分配存储空间，当数组元素过大时进行自行扩展。4. 数组指针的声明会使数组更加灵活，只需把数组的首地址给指针，通过指针移动可查询到相应元素，获得对应的结果，时间复杂度相比较而言较低。5. c+中不同的头文件提供不同的函数应用，有些系统函数只有在导入其所在的头文件之后，才会被识别。因此在程序出错时，即代码不能被识别时，不仅看一下它是否被定义还要看一下是不是系统所定义的函数，是否导入了所需的文件。6. 做程序时要考虑全面，对问题中出现的多种情况要进行统一分析，如矩阵相乘程序中，要考虑相乘的基本条件，才能使程序实现更加完善本次实验存在问题及下一步改进设想：1. 在求马鞍点时，二维