山东大学数据结构实验报告四.docx
《山东大学数据结构实验报告四.docx》由会员分享，可在线阅读，更多相关《山东大学数据结构实验报告四.docx（26页珍藏版）》请在冰点文库上搜索。
山东大学数据结构实验报告四
山东大学软件工程学院
数据结构课程实验报告
学号：
姓名：
班级：
软件工程2014级2班
实验题目：
矩阵和散列表
实验学时：
实验日期：
2015.11.11
实验目的：
掌握特殊矩阵和稀疏矩阵。
掌握散列表及其应用。
硬件环境：
实验室
软件环境：
VistualStudio2013
实验步骤与内容：
实验内容：
1、创建三对角矩阵类，采用按列映射方式，提供store和retrieve方法。
2、创建下三角矩阵类，采用按列映射方式，提供store和retrieve方法。
3、创建稀疏矩阵类，采用行主顺序把稀疏矩阵映射到一维数组中，实现稀疏矩阵的转置和两个稀疏矩阵的加法操作。
4、使用散列表设计实现一个字典，假设关键字为整数且D为961，在字典中插入随机产生的500个不同的整数，实现字典的建立和搜索操作。
分别使用线性开型寻址和链表散列解决溢出。
代码体：
ChainHashTableNode.h
#pragmaonce
#include"ChainHashTableNode.h"
usingnamespacestd;
classChainHashTable
{
public:
ChainHashTable（intdivisor）;
~ChainHashTable（）;
boolInsert（intk）;
boolSearch（intk）;
voidprint（）;
private:
intd;
ChainHashTableNode*ht;
};
ChainHashTableNode.cpp
#include"ChainHashTable.h"
#include
usingnamespacestd;
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;i{
ht[i].print（）;
}
}
ChainHashTableNode.h
#pragmaonce
#include"Node.h"
classChainHashTableNode
{
public:
ChainHashTableNode（）;
boolInsert（intk）;
boolSearch（intk）;
voidprint（）;
private:
Node*first;
};
ChainHashTableNode.cpp
#include"ChainHashTableNode.h"
#include
usingnamespacestd;
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<<"已经存在此元素"<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）
{
cout<value<<"";
first=first->link;
}
cout<first=current;
}
else{
cout<<-1<}
}
HashTable.h
#pragmaonce
classHashTable
{
public:
HashTable（intdivisor）;
~HashTable（）;
intSearch（intk）;//搜索算法
boolInsert（inte）;
voidprint（）;
private:
inthSearch（intk）;
intd;//除数
int*ht;//桶，大小取决于d就是除数是多少
bool*empty;//一维数组，用来存储第I个桶是否存入了元素
};
HashTable.cpp
#include"HashTable.h"
#include
usingnamespacestd;
HashTable:
:
HashTable（intdivisor）
{
d=divisor;
ht=newint[d];
empty=newbool[d];
for（inti=0;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<<"已经存在此元素"<returnfalse;
}
else
{
cout<<"表已经满了"<returnfalse;
}
}
voidHashTable:
:
print（）
{
for（inti=0;i<961;i++）{
cout<}
cout<return;
}
LowerTriangularMatrix.h
#pragmaonce
classLowerTriangularMatrix
{
public:
LowerTriangularMatrix（intsize）;
voidStore（intx,inti,intj）;//向矩阵里存储一个元素
intRetrieve（inti,intj）;//返回矩阵中的一个元素
voidprint（）;
private:
intn;//矩阵维数
intsum;//矩阵非零元素个数
int*t;//用数组来存储矩阵
};
LowerTriangularMatrix.cpp
#include"LowerTriangularMatrix.h"
#include
usingnamespacestd;
LowerTriangularMatrix:
:
LowerTriangularMatrix（intsize）
{
n=size;
sum=n*（n+1）/2;
t=newint[sum];
}
voidLowerTriangularMatrix:
:
Store（intx,inti,intj）
{
if（i<0||j<0||i>=n||j>=n）
{
cout<<"下三角矩阵行列输入错误"<return;
}
elseif（x==0）
{
cout<<"下三角所添加的元素必须非零"<return;
}
elseif（i{
cout<<"下三角添加元素位置错误"<return;
}
t[sum-（（n-j）*（n-j+1）/2）+（i-j）]=x;
return;
}
intLowerTriangularMatrix:
:
Retrieve（inti,intj）
{
if（i<0||j<0||i>=（n-1）||j>=（n-1））
{
cout<<"三对角矩阵行列输入错误"<return-1;
}
elseif（i>=j）
{
returnt[sum-（（n-j）*（n-j+1）/2）+（i-j）];
}
else{
return0;
}
}
voidLowerTriangularMatrix:
:
print（）
{
for（inti=0;icout<}
cout<return;
}
Node.h
#pragmaonce
classNode
{
friendclassChainHashTableNode;
private:
intvalue;
Node*link;
};
Node.cpp
#include"Node.h"
usingnamespacestd;
SparseMatrix.h
#pragmaonce
#include"Term.h"
classSparseMatrix
{
public:
SparseMatrix（introw,intcol）;
voidtranspose（）;
voidStore（intx,inti,intj）;//向矩阵里存储一个元素
voidAdd（SparseMatrix&b）;//两个稀疏矩阵相加
voidprint（）;
private:
introw,col;//数组维数
intsum;//元素个数
intmaxsum;//最多的元素个数
Term*t;//存储的数组
};
SparseMatrix.cpp
#include"SparseMatrix.h"
#include
usingnamespacestd;
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;ifor（inti=0;ifor（inti=0;iRowNext[0]=0;
for（inti=1;i//进入转置操作
for（inti=0;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;icout<}
cout<return;
}
voidSparseMatrix:
:
Add（SparseMatrix&b）//两个稀疏矩阵相加
{
if（col!
=b.col||row!
=b.row）{
cout<<"两个矩阵行列不同无法相加"<return;
}
intsa=0;
intsb=0;
Term*cur=newTerm[maxsum];
intk=0;
while（sa{
if（t[sa].col==b.t[sb].col&&t[sa].row==b.t[sb].row）
{
cur[k].col=t[sa].col;
cur[k].row=t[sa].row;
cur[k].value=t[sa].value+b.t[sb].value;
k++;
sa++;
sb++;
}
elseif（t[sa].row{
cur[k].value=t[sa].value;
cur[k].row=t[sa].row;
cur[k].col=t[sa].col;
k++;
sa++;
}
elseif（t[sa].row>b.t[sb].row）
{
cur[k].value=b.t[sb].value;
cur[k].row=b.t[sb].row;
cur[k].col=b.t[sb].col;
k++;
sb++;
}
elseif（t[sa].col{
cur[k].col=t[sa].col;
cur[k].row=t[sa].row;
cur[k].value=t[sa].value;
k++;
sa++;
}
else
{
cur[k].value=b.t[sb].value;
cur[k].row=b.t[sb].row;
cur[k].col=b.t[sb].col;
k++;
sb++;
}
}
sum=k;
deletet;
t=cur;
return;
}
Term.h
#pragmaonce
classTerm
{
friendclassSparseMatrix;
private:
intcol,row;
intvalue;
};
Term.cpp
#include"Term.h"
TridiagonalMatrix.h
#pragmaonce
classTridiagonalMatrix
{
public:
TridiagonalMatrix（intsize）;
voidStore（intx,inti,intj）;//向矩阵里存储一个元素
intRetrieve（inti,intj）;//返回矩阵中的一个元素
voidprint（）;
private:
intn;//矩阵非0元素个数
int*t;//用数组来存储矩阵
};
TridiagonalMatrix.cpp
#include"TridiagonalMatrix.h"
#include
usingnamespacestd;
TridiagonalMatrix:
:
TridiagonalMatrix（intsize）
{
n=size;
t=newint[3*n-2];
}
voidTridiagonalMatrix:
:
Store（intx,inti,intj）
{
if（i<0||j<0||i>=n||j>=n）
{
cout<<"三对角矩阵行列输入错误"<return;
}
elseif（x==0）
{
cout<<"三对角矩阵所添加的元素必须非零"<return;
}
elseif（abs（i-j）>1）
{
cout<<"三对角矩阵添加元素位置错误"<return;
}
switch（i-j）
{
case-1:
t[3*j-1]=x;
break;
case0:
t[3*j]=x;
break;
case1:
t[3*j+1]=x;
break;
}
return;
}
intTridiagonalMatrix:
:
Retrieve（inti,intj）
{
if（i<0||j<0||i>=（n-1）||j>=（n-1））
{
cout<<"三对角矩阵行列输入错误"<return-1;
}
elseif（abs（i-j）<=1）
{
returnt[3*j+（i-j）];
}
else{
return0;
}
}
voidTridiagonalMatrix:
:
print（）
{
for（inti=0;i<3*n-2;i++）{
cout<}
cout<return;
}
Test.cpp
#include
#include
#include
#include"TridiagonalMatrix.h"
#include"LowerTriangularMatrix.h"
#include"SparseMatrix.h"
#include"HashTable.h"
#include"ChainHashTable.h"
usingnamespacestd;
intwei,num[100][100];
voidc（）
{
for（inti=0;ifor（intj=0;jcin>>num[i][j];
}
intmain（）
{
intk=0,l=0;
/*三对角矩阵实验开始
测试数据4~10~3n-2
4
1200
3450
0789
0087
*/
cout<<"请输入三对焦矩阵维数及内容：
"<cin>>wei;
c（）;
TridiagonalMatrix*TM=newTridiagonalMatrix（wei）;
for（inti=0;ifor（intj=0;jif（num[j][i]!
=0）
TM->Store（num[j][i],j,i）;
TM->print（）;
cout<<"请输入要查询的元素的位置"<cin>>k>>l;
l=TM->Retrieve（k,l）;
cout<<"查询结果：
"<cout<<"***********************************************"</*下三角矩阵实验开始
测试数据4~10~n*（n+1）/2
4
1000
2300
4
升级会员 