山东大学 数据结构实验报告 矩阵和散列表

山东大学计算机科学与技术学院数据结构课程实验报告学号：姓名：徐大鹏班级：实验题目：实验四_矩阵和散列表实验学时：2实验日期：2015.11.24实验目的：掌握特殊矩阵和稀疏矩阵。掌握散列表及其应用。硬件环境：略软件环境：UbuntuKylin15.0464-bitLinuxGCC4.9.2JavaSERuntimeEnvironment(build1.8.0_60-b27)EclipseIDEforC/C++DevelopersMars.1Release(4.5.1)实验内容与设计：1.实验内容（题目内容，输入要求，输出要求）(1)创建三对角矩阵类，采用按列映射方式，提供store和retrieve方法。(2)创建下三角矩阵类，采用按列映射方式，提供store和retrieve方法。(3)创建稀疏矩阵类，采用行主顺序把稀疏矩阵映射到一维数组中，实现稀疏矩阵的转置和两个稀疏矩阵的加法操作。(4)使用散列表设计实现一个字典，假设关键字为整数且D为961，在字典中插入随机产生的500个不同的整数，实现字典的建立和搜索操作。分别使用线性开型寻址和链表散列解决溢出。2.数据结构与算法描述（整体思路描述，所需要的数据结构与算法）对问题一，从数学上推导得出三对角方阵列主映射的函数关系式i=2c+r-3其中i为元素在数组e中的下标，c为列数，r为行数，c≥1且r≥1。以此关系式为TridiagonalMatrix类编写了Store和Retrieve函数，并扩展编写了Input函数和Output函数。对问题二，从数学上推导得出下三角方阵列主映射的函数关系式i=n×(c-1)-1+r+c×(1-c)/2其中i为元素在数组e中的下标，n为方阵的大小，c为列数，r为行数，c≥1且r≥1。以此关系式为LowerTriangularMatrix类编写了Store和Retrieve函数，并扩展编写了Input函数和Output函数。对问题三，仿课本所述，定义Term类作为SparseMatrix类的友元类，包含行、列、值三个要素的成员变量，用Term类的数组实现稀疏矩阵的行主映射存储。查找行为的实现方式是，找到位于目标元素前一行的最后一个元素，再从这个元素开始向下搜索，直到找到和目标元素同一行但是列数小于目标元素的元素a[k-1]，然后决定下一步的行为————插入一个新项Term作为a[k]并将已有元素向后移位，还是修改已存在的项a[k]。以此原理编写了Store和Retrieve函数，并扩展编写了Input函数和Output函数。对问题四，仿照课本例子编写了有序链表类SortedChain、开放寻址的散列表类HashTable、基于有序链表链接的散列表类ChainHashTable，并对这三个类分别扩展编写了Output函数。3.测试结果（测试输入，测试输出）问题一：问题二：上图显示了输入不符合下三角方阵约束时，抛出异常并退出程序。上图是正常运行的结果。问题三：普通的输入和输出操作如下：矩阵相加：矩阵转置：问题四：以上图的数据为例。从346就应该在链表链接的散列表上看到开放寻址解决冲突的例子。返回开放寻址的输出段，可以看到符合预期的结果：4.实现源代码（程序风格清晰易理解，有充分的注释）/**TridiagonalMatrix.h**Createdon:Nov22,2015*Author:xudp*/#ifndefTRIDIAGONALMATRIX_H_#defineTRIDIAGONALMATRIX_H_#includeiostreamusingnamespacestd;templateclassTclassTridiagonalMatrix{public://1、创建三对角矩阵类,采用按列映射方式,提供store和retrieve方法。TridiagonalMatrix(intsize=10);~TridiagonalMatrix();//row0,column0TridiagonalMatrixT&Store(introw,intcolumn,constT&value);TRetrieve(introw,intcolumn);voidInput(istream&in,ostream&out);voidOutput(ostream&out)const;friendostream&operator(ostream&out,constTridiagonalMatrixT&matrix){matrix.Output(out);returnout;}friendistream&operator(istream&in,TridiagonalMatrixT&matrix){matrix.Input(in,cout);returnin;}private:T*e;//Storeallelementsintsize;};templateclassTridiagonalMatrixdouble;#endif/*TRIDIAGONALMATRIX_H_*//**TridiagonalMatrix.cpp**Createdon:Nov22,2015*Author:xudp*/#includeTridiagonalMatrix.h#includeExceptions.htemplateclassTTridiagonalMatrixT::TridiagonalMatrix(intsize){if(size1)throwInvalidParameterValue();e=newT[3*size-2];this-size=size;}templateclassTTridiagonalMatrixT::~TridiagonalMatrix(){delete[]e;}templateclassTTridiagonalMatrixT&TridiagonalMatrixT::Store(introw,intcolumn,constT&value){if(row1||rowsize||column1||columnsize||(row-column)1||(row-column)-1)throwInvalidParameterValue();e[2*column+row-3]=value;return*this;}templateclassTTTridiagonalMatrixT::Retrieve(introw,intcolumn){if(row1||rowsize||column1||columnsize||(row-column)1||(row-column)-1)throwInvalidParameterValue();returne[2*column+row-3];}templateclassTvoidTridiagonalMatrixT::Input(istream&in,ostream&out){out请按行主顺序依次输入元素，endl;out元素个数必须恰好是(3*size-2)个:endl;for(inti=0;isize;i++){for(intj=i-1;j=i+1;j++){if(i==0&&j==-1)continue;if(i==size-1&&j==size)continue;Telement;inelement;Store(i+1,j+1,element);}}out操作成功完成.endl;}templateclassTvoidTridiagonalMatrixT::Output(ostream&out)const{for(inti=0;isize;i++){for(intj=0;jsize;j++)if((i-j)1||(i-j)-1)out0\t;else{oute[2*j+i]\t;}outendl;}}/**SparseMatrix.h**Createdon:Oct20,2015*Author:xudp*/#ifndefSPARSEMATRIX_H_#defineSPARSEMATRIX_H_#includeiostreamusingnamespacestd;templateclassTclassSparseMatrix;templateclassTclassTerm{friendSparseMatrixT;private:introw,col;Tvalue;};templateclassTclassSparseMatrix{public:/*3、创建稀疏矩阵类,采用行主顺序把稀疏矩阵映射到一维数组中,实现稀*疏矩阵的转置和两个稀疏矩阵的加法操作。*/SparseMatrix(intmaxTerms=10);SparseMatrix(constSparseMatrixT&spm);~SparseMatrix(){delete[]a;}voidTranspose(SparseMatrixT&b)const;voidAdd(constSparseMatrixT&b,SparseMatrixT&c)const;/**Writethestoreandretrievefunctionsforasparsematrixstoredin*row-majororderinaone-dimensionalarray.*/SparseMatrixT&Store(constT&x,inti,intj);TRetrieve(inti,intj)const;voidInput(istream&in,ostream&out);voidOutput(ostream&out)const;friendostream&operator(ostream&out,constSparseMatrixT&matrix){matrix.Output(out);returnout;}friendistream&operator(istream&in,SparseMatrixT&matrix){matrix.Input(in,cout);returnin;}intGetMaxSize(){returnMaxTerms;}private:voidAppend(constTermT&t);introws,cols;//matrixdimensionsintterms;//currentnumberofnonzerotermsTermT*a;//termarrayintMaxTerms;//sizeofarraya};templateclassSparseMatrixdouble;#endif/*SPARSEMATRIX_H_*//**SparseMatrix.cpp**Createdon:Oct20,2015*Author:xudp*/#includeSparseMatrix.h#includeExceptions.htemplateclassTSparseMatrixT::SparseMatrix(intmaxTerms){//Sparsematrixconstructor.if(maxTerms1)throwBadInitializers();MaxTerms=maxTerms;a=newTermT[MaxTerms];terms=cols=rows=0;}templateclassTSparseMatrixT&SparseMatrixT::Store(constT&theVal,inttheRow,inttheCol){if(theRow1||theCol1||theRowrows||theColcols)throwOutOfBounds();intcursor=-1;do{cursor++;if(cur