山东大学数据结构实验报告四

山东大学软件工程学院数据结构课程实验报告学号：姓名：班级：软件工程2014级2班实验题目：矩阵和散列表实验学时：实验日期：2015.11.11实验目的：掌握特殊矩阵和稀疏矩阵。掌握散列表及其应用。硬件环境：实验室软件环境：VistualStudio2013实验步骤与内容：实验内容：1、创建三对角矩阵类，采用按列映射方式，提供store和retrieve方法。2、创建下三角矩阵类，采用按列映射方式，提供store和retrieve方法。3、创建稀疏矩阵类，采用行主顺序把稀疏矩阵映射到一维数组中，实现稀疏矩阵的转置和两个稀疏矩阵的加法操作。4、使用散列表设计实现一个字典，假设关键字为整数且D为961，在字典中插入随机产生的500个不同的整数，实现字典的建立和搜索操作。分别使用线性开型寻址和链表散列解决溢出。代码体：ChainHashTableNode.h#pragmaonce#includeChainHashTableNode.husingnamespacestd;classChainHashTable{public:ChainHashTable(intdivisor);~ChainHashTable();boolInsert(intk);boolSearch(intk);voidprint();private:intd;ChainHashTableNode*ht;};ChainHashTableNode.cpp#includeChainHashTable.h#includeiostreamusingnamespacestd;ChainHashTable::ChainHashTable(intdivisor){d=divisor;ht=newChainHashTableNode[d];}boolChainHashTable::Insert(intk){intj=k%d;if(ht[j].Insert(k)){returntrue;}else{returnfalse;}}voidChainHashTable::print(){for(inti=0;id;i++){ht[i].print();}}ChainHashTableNode.h#pragmaonce#includeNode.hclassChainHashTableNode{public:ChainHashTableNode();boolInsert(intk);boolSearch(intk);voidprint();private:Node*first;};ChainHashTableNode.cpp#includeChainHashTableNode.h#includeiostreamusingnamespacestd;ChainHashTableNode::ChainHashTableNode(){first=0;}boolChainHashTableNode::Search(intk){if(first==0)returnfalse;Node*current=first;while(current){if(current-value==k){returntrue;}current=current-link;if(current){if(current-value==k){returntrue;}}}returnfalse;}boolChainHashTableNode::Insert(intk){if(Search(k)){cout已经存在此元素endl;returnfalse;}else{Node*p=newNode();p-value=k;if(first==0){first=p;returntrue;}else{p-link=first;first=p;returntrue;}}}voidChainHashTableNode::print(){Node*current=first;if(first){while(first){coutfirst-value;first=first-link;}coutendl;first=current;}else{cout-1endl;}}HashTable.h#pragmaonceclassHashTable{public:HashTable(intdivisor);~HashTable();intSearch(intk);//搜索算法boolInsert(inte);voidprint();private:inthSearch(intk);intd;//除数int*ht;//桶，大小取决于d就是除数是多少bool*empty;//一维数组，用来存储第I个桶是否存入了元素};HashTable.cpp#includeHashTable.h#includeiostreamusingnamespacestd;HashTable::HashTable(intdivisor){d=divisor;ht=newint[d];empty=newbool[d];for(inti=0;id;i++){empty[i]=true;ht[i]=0;}}HashTable::~HashTable(){delete[]ht;delete[]empty;}intHashTable::hSearch(intk)//搜索值为K的元素{inti=k%d;intj=i;do{if(ht[j]==k||empty[j])returnj;j=(j+1)%d;}while(j!=i);returnj;}intHashTable::Search(intk)//搜索值为K的元素{intb=hSearch(k);if(ht[b]==k)returnb;return-1;}boolHashTable::Insert(inte){intb=hSearch(e);if(empty[b]){ht[b]=e;empty[b]=false;returntrue;}elseif(ht[b]==e){cout已经存在此元素endl;returnfalse;}else{cout表已经满了endl;returnfalse;}}voidHashTable::print(){for(inti=0;i961;i++){coutht[i];}coutendl;return;}LowerTriangularMatrix.h#pragmaonceclassLowerTriangularMatrix{public:LowerTriangularMatrix(intsize);voidStore(intx,inti,intj);//向矩阵里存储一个元素intRetrieve(inti,intj);//返回矩阵中的一个元素voidprint();private:intn;//矩阵维数intsum;//矩阵非零元素个数int*t;//用数组来存储矩阵};LowerTriangularMatrix.cpp#includeLowerTriangularMatrix.h#includeiostreamusingnamespacestd;LowerTriangularMatrix::LowerTriangularMatrix(intsize){n=size;sum=n*(n+1)/2;t=newint[sum];}voidLowerTriangularMatrix::Store(intx,inti,intj){if(i0||j0||i=n||j=n){cout下三角矩阵行列输入错误ijendl;return;}elseif(x==0){cout下三角所添加的元素必须非零endl;return;}elseif(ij){cout下三角添加元素位置错误endl;return;}t[sum-((n-j)*(n-j+1)/2)+(i-j)]=x;return;}intLowerTriangularMatrix::Retrieve(inti,intj){if(i0||j0||i=(n-1)||j=(n-1)){cout三对角矩阵行列输入错误endl;return-1;}elseif(i=j){returnt[sum-((n-j)*(n-j+1)/2)+(i-j)];}else{return0;}}voidLowerTriangularMatrix::print(){for(inti=0;isum;i++){coutt[i];}coutendl;return;}Node.h#pragmaonceclassNode{friendclassChainHashTableNode;private:intvalue;Node*link;};Node.cpp#includeNode.husingnamespacestd;SparseMatrix.h#pragmaonce#includeTerm.hclassSparseMatrix{public:SparseMatrix(introw,intcol);voidtranspose();voidStore(intx,inti,intj);//向矩阵里存储一个元素voidAdd(SparseMatrix&b);//两个稀疏矩阵相加voidprint();private:introw,col;//数组维数intsum;//元素个数intmaxsum;//最多的元素个数Term*t;//存储的数组};SparseMatrix.cpp#includeSparseMatrix.h#includeiostreamusingnamespacestd;SparseMatrix::SparseMatrix(intr,intc){row=r;col=c;sum=0;maxsum=r*c;t=newTerm[maxsum];}voidSparseMatrix::transpose(){Term*cur=newTerm[maxsum];int*ColSize=newint[col];int*RowNext=newint[row];for(inti=0;icol;i++)ColSize[i]=0;for(inti=0;irow;i++)RowNext[i]=0;for(inti=0;isum;i++)ColSize[t[i].col]++;//表示每一列的非零元素个数RowNext[0]=0;for(inti=1;icol;i++)RowNext[i]=RowNext[i-1]+ColSize[i-1];//表示新矩阵中每一行的矩阵的前面的矩阵的个数//进入转置操作for(inti=0;isum;i++){intj=RowNext[t[i].col]++;cur[j].value=t[i].value;cur[j].col=t[i].row;cur[j].row=t[i].col;}deletet;t=cur;}voidSparseMatrix::Store(intx,inti,intj){t[sum].value=x;t[sum].row=i;t[sum].col=j;sum++;return;}voidSparseMatrix::print(){for(inti=0;isum;i++){coutt[i].value;}coutendl;return;}voidSparseMatrix::Add(SparseMatrix&b)//两个稀疏矩阵相加{if(col!=b.col||row!=b.row){cout两个矩阵行列不同无法相加endl;return;}intsa=0;intsb=0;Term*cur=newTerm[maxsum];intk=0;while(sasum||sbb.sum){i