2022年数据结构实验四矩阵和散列表代码实现 .pdf

《2022年数据结构实验四矩阵和散列表代码实现 .pdf》由会员分享，可在线阅读，更多相关《2022年数据结构实验四矩阵和散列表代码实现 .pdf（14页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、1、创建稀疏矩阵类，采用行主顺序把稀疏矩阵映射到一维数组中，实现稀疏矩阵的转置和两个稀疏矩阵的加法操作。#include#include using namespace std;/三元组struct Trituple int row,col;/非零元素的行号、列号int val;/非零元素的值;/稀疏矩阵类声明class SparseMatrix public:SparseMatrix(int maxt=100);/构造函数SparseMatrix();/析构函数bool TransposeTo(SparseMatrix&);/转置void add(SparseMatrix&,SparseMa

2、trix&);/加运算void map();/采用行主顺序把稀疏矩阵映射到一维数组中bool Input();/输入稀疏矩阵void Output();/输出稀疏矩阵Trituple*data;/存储非零元素三元组的数组int rows,cols,terms;/矩阵的行数、列数、非零元素个数int maxterms;/数组 data 的大小;/构造函数，分配maxt 个三元组结点的顺序空间，构造一个空的稀疏矩阵三元组表。SparseMatrix:SparseMatrix(int maxt)maxterms=maxt;data=new Trituple maxterms;terms=rows=c

3、ols=0;/析构函数，将三元组表结构销毁。SparseMatrix:SparseMatrix()if(data!=NULL)delete data;/输出稀疏矩阵ostream&operator (ostream&out,SparseMatrix&M)名师资料总结-精品资料欢迎下载-名师精心整理-第 1 页，共 14 页 -out rows=M.rows endl;out cols=M.cols endl;out terms=M.terms endl;for(int i=0;i M.terms;i+)out data M.datai.row ,M.datai.col =M.datai.val

4、 (istream&in,SparseMatrix&N)cout 输入稀疏矩阵的行数、列数以及非零元素个数 N.rows N.cols N.terms;if(N.terms N.maxterms)exit(1);cout terms=N.terms endl;for(int i=0;i N.terms;i+)cout 输入非零元素的行号、列号和元素值 i+1 N.datai.row N.datai.col N.datai.val;return in;/转置，将*this 的转置矩阵送入B bool SparseMatrix:TransposeTo(SparseMatrix&B)if(terms

5、 B.maxterms)return false;B.rows=cols;B.cols=rows;B.terms=terms;if(terms 0)int p=0;for(int j=1;j=cols;j+)for(int k=0;k terms;k+)if(datak.col=j)B.datap.row=j;B.datap.col=datak.row;B.datap.val=datak.val;p+;return true;void SparseMatrix:add(SparseMatrix&A,SparseMatrix&B)名师资料总结-精品资料欢迎下载-名师精心整理-第 2 页，共 14

6、 页 -if(A.rows!=B.rows|A.cols!=B.cols)cout矩阵不相容，不能相加!endl;else rows=A.rows;cols=A.cols;terms=0;int a,b,e,k;a=b=e=0;for(k=1;k=A.rows;k+)while(A.dataa.row=k&B.datab.row=k)/两结点属于同一行 if(A.dataa.col B.datab.col)/A 中下标 a的结点小于B中下标为b的结点的列数 datae.val=A.dataa.val;datae.row=A.dataa.row;datae.col=A.dataa.col;e+;

7、a+;else if(A.dataa.col=B.datab.col)/两结点属于同一列 int temp=A.dataa.val+B.datab.val;if(temp=0)/两结点数值相加等于0 a+;b+;else/两结点数值相加不等于0 datae.val=temp;datae.row=A.dataa.row;datae.col=A.dataa.col;e+;a+;b+;else /A 中下标 a的结点大于B中下标为 b 的结点的列数datae.val=B.datab.val;名师资料总结-精品资料欢迎下载-名师精心整理-第 3 页，共 14 页 -datae.row=B.datab.

8、row;datae.col=B.datab.col;e+;b+;while(A.dataa.row=k)/只有 A 中剩下行数为k 的未处理结点datae.val=A.dataa.val;datae.row=A.dataa.row;datae.col=A.dataa.col;e+;a+;while(B.datab.row=k)/只有 B中剩下行数为k 的未处理结点datae.val=B.datab.val;datae.row=B.datab.row;datae.col=B.datab.col;e+;b+;terms=e;cout和矩阵为：1);size-)int indexOfMax=0;so

9、rted=true;for(int i=1;isize;i+)if(dataindexOfMax.row1);size-)名师资料总结-精品资料欢迎下载-名师精心整理-第 4 页，共 14 页 -int indexOfMax=0;sorted=true;for(int i=1;i datai.row)if(dataindexOfMax.col=datai.col)indexOfMax=i;else sorted=false;swap(dataindexOfMax,datasize-1);for(int i=0;i terms;i+)cout datai.val ;cout n;bool Spa

10、rseMatrix:Input()cout 输入稀疏矩阵的行数、列数以及非零元素个数 rows cols terms;if(terms maxterms)cout 非零元个数太多！endl;return false;if(terms=0)return true;cout 按行序输入 terms 个非零元素的三元组 endl;for(int i=0;i terms;i+)cout 输入第 i+1 个非零元素的行号、列号和元素值 datai.row datai.col datai.val;if(datai.row rows|datai.col cols)cout 矩阵输入有误！endl;retur

11、n false;return true;/输出稀疏矩阵void SparseMatrix:Output()名师资料总结-精品资料欢迎下载-名师精心整理-第 5 页，共 14 页 -cout rows=rows endl;cout cols=cols endl;cout terms=terms endl;for(int i=0;i terms;i+)cout data datai.row ,datai.col =datai.val endl;int main()SparseMatrix M,T,C,D;if(M.Input()cout 原始矩阵：endl;M.Output();cout 采用行主

12、顺序把稀疏矩阵映射到一维数组中并输出 endl;M.map();cout 转置矩阵：endl;if(M.TransposeTo(T)T.Output();cout输入第二个矩阵endl;if(C.Input()cout 第二矩阵：endl;C.Output();D.add(M,C);cout 采用行主顺序把稀疏矩阵映射到一维数组中并输出 endl;D.map();system(pause);return 0;2、使用散列表设计实现一个字典，假设关键字为整数且D 为 961，在字典中插入随机产生的 500 个不同的整数，实现字典的建立和搜索操作。分别使用线性开型寻址和链表散列解决溢出。#incl

13、ude#include#include#include using namespace std;template class HashTable 名师资料总结-精品资料欢迎下载-名师精心整理-第 6 页，共 14 页 -public:HashTable(int divisor=11);HashTable()delete ht;delete empty;HashTable&Insert(const E&e);void Output(ostream&out)const;friend ostream&operator(ostream&out,const HashTable&ht)ht.Output(

14、out);return out;private:int hSearch(const K&k)const;int D;/hash function divisor E*ht;/hash table array bool*empty;/1D array;template class HashTable;template HashTable:HashTable(int divisor)D=divisor;ht=new ED;empty=new boolD;for(int i=0;i D;i+)emptyi=true;template int HashTable:hSearch(const K&k)c

15、onst int i=k%D;int j=i;do if(emptyj|htj=k)return j;j=(j+1)%D;while(j!=i);return j;名师资料总结-精品资料欢迎下载-名师精心整理-第 7 页，共 14 页 -template HashTable&HashTable:Insert(const E&e)K k=e;int b=hSearch(k);if(emptyb)emptyb=false;htb=e;return*this;if(htb=k)cout输入错误;cout没有可用内存;template void HashTable:Output(ostream&out

16、)const out 表是否满：;bool isFull=true;for(int i=0;i D;i+)if(!emptyi)isFull=false;break;if(isFull)out 否;else out 是;out endl;out 散列余数(所存储数值的余数),所存储数值 endl;for(int i=0;i D;i+)out i(hti%D),thti t|;if(i+1)%3=0)out endl;if(D%3!=0)out endl;templateclass SortedChain;名师资料总结-精品资料欢迎下载-名师精心整理-第 8 页，共 14 页 -template

17、 class SortedChainNode friend class SortedChain;private:E data;SortedChainNode*link;template class SortedChain public:SortedChain()first=0;SortedChain();bool IsEmpty()const return first=0;int Length()const;SortedChain&Delete(const K&k,E&e);SortedChain&Insert(const E&e);SortedChain&DistinctInsert(con

18、st E&e);void Output(ostream&out)const;friend ostream&operator(ostream&out,const SortedChain&sc)sc.Output(out);return out;private:SortedChainNode*first;template class SortedChainNode;template class SortedChain;template SortedChain:SortedChain()SortedChainNode*p=first;SortedChainNode*tmp;while(p)名师资料总

19、结-精品资料欢迎下载-名师精心整理-第 9 页，共 14 页 -tmp=p;p=p-link;delete tmp;template SortedChain&SortedChain:Delete(const K&k,E&e)SortedChainNode*p=first,*tp=0;/trail p/search for match with k for(;p&p-datalink);/verify match if(p&p-data=k)/found a match e=p-data;/save data/remove p from chain if(tp)tp-link=p-link;el

20、se first=p-link;/p is first node.delete p;return*this;cout输入错误;/no match template SortedChain&SortedChain:Insert(const E&e)SortedChainNode*p;if(!first|first-data=e)p=new SortedChainNode();p-data=e;p-link=first;first=p;else p=first;while(p-link)if(p-link-datalink;else SortedChainNode*ncn=new SortedCh

21、ainNode();名师资料总结-精品资料欢迎下载-名师精心整理-第 10 页，共 14 页 -ncn-data=e;ncn-link=p-link;p-link=ncn;break;if(!p-link)p-link=new SortedChainNode();p=p-link;p-link=0;p-data=e;return*this;template SortedChain&SortedChain:DistinctInsert(const E&e)SortedChainNode*p=first,*tp=0;/trail p/move tp so that e can be inserte

22、d after tp for(;p&p-datalink);/check if duplicate if(p&p-data=e)cout输入错误;/not duplicate,set up node for e SortedChainNode*q=new SortedChainNode;q-data=e;/insert node just after tp q-link=p;if(tp)tp-link=q;else first=q;return*this;template void SortedChain:Output(ostream&out)const SortedChainNode*p=f

23、irst;if(!first)out(Empty chain.);else while(p)out datalink;out endl;template class ChainHashTable public:ChainHashTable(int divisor=11)D=divisor;ht=new SortedChain D;ChainHashTable()delete ht;ChainHashTable&Insert(const E&e)hte%D.Insert(e);return*this;ChainHashTable&Delete(const K&k,E&e)htk%D.Delete

24、(k,e);return*this;void Output(ostream&out)const;friend ostream&operator(ostream&out,const ChainHashTable&cht)cht.Output(out);return out;private:int D;/divisor SortedChain*ht;/array of chains;template class ChainHashTable;template void ChainHashTable:Output(ostream&out)const out 散列余数,数值 endl;for(int

25、i=0;i D;i+)out i,thti;void deal()名师资料总结-精品资料欢迎下载-名师精心整理-第 12 页，共 14 页 -int D=961;int num=500;cout 除数 D 的值为默认值961endl;cout 插入的随机整数的个数为默认值500endl;long min,max;min=0;max=RAND_MAX;srand(unsigned(time(0);long rmin,rmax;rmin=rmax=(min+max)/2;long randret;/开放寻址HashTable*ht=new HashTable(D);/链表散列ChainHashTa

26、ble*cht=new ChainHashTable(D);for(int i=0;i num;i+)randret=rand();if(min=randret&randret rmax)rmax=randret;if(randret Insert(randret);cht-Insert(randret);cout 0:退出 endl;cout 1:开放寻址法 endl;cout 2:链表散列法 endl;/cout 3:搜索 choice;while(choice!=0)switch(choice)case 0:break;case 1:名师资料总结-精品资料欢迎下载-名师精心整理-第 13

27、 页，共 14 页 -cout 开放寻址法：endl;cout (*ht);cout 所有随机数的最大值:rmin endl;cout 所有随机数的最小值:rmax endl;break;case 2:cout 链表散列法：endl;cout (*cht);cout 所有随机数的最大值:rmin endl;cout 所有随机数的最小值:rmax endl;break;cout 0:退出 endl;cout 1:开放寻址法 endl;cout 2:链表散列法 choice;int main()deal();return 0;名师资料总结-精品资料欢迎下载-名师精心整理-第 14 页，共 14 页 -