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

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 &,SparseMatrix &);/加运算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 = cols = 0; /析构函数，将三元组表结构销毁。 SparseMatrix:SparseMatrix() if (data != NULL) delete data; /输出稀疏矩阵 ostream& operator (ostream & out, SparseMatrix & M) 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 (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 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) 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+; 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; datae.row=B.datab.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; sorted = true; for(int i = 1;isize; i+) if (dataindexOfMax.row1); size-) 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 SparseMatrix: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; return false; return true; /输出稀疏矩阵 void SparseMatrix:Output() 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 采用行主顺序把稀疏矩阵映射到一维数组中并输出 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个不同的整数，实现字典的建立和搜索操作。分别使用线性开型寻址和链表散列解决溢出。#include#include#include#includeusing namespace std;templateclass HashTable 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(out);return out;private:int hSearch(const K& k) const;int D;/ hash function divisorE *ht;/ hash table arraybool *empty;/ 1D array;template class HashTable;templateHashTable:HashTable(int divisor) D = divisor;ht = new ED;empty = new boolD;for (int i = 0; i D; i+)emptyi = true;templateint HashTable:hSearch(const K& k) const int i = k % D;int j = i;do if (emptyj | htj = k)return j;j = (j + 1) % D; while (j != i);return j;templateHashTable&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没有可用内存;templatevoid HashTable:Output(ostream& out) const out 表是否满：;bool isFull = true;for (int i = 0; i D; i+)if (!emptyi) isFull = false;break;if (isFull)out 否;elseout 是;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;templateclass SortedChainNode friend class SortedChain ; private: E data; SortedChainNode *link;templateclass 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(const 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 ;templateSortedChain:SortedChain() SortedChainNode* p = first;SortedChainNode* tmp;while (p) tmp = p;p = p-link;delete tmp;templateSortedChain&SortedChain:Delete(const K& k, E& e) SortedChainNode *p = first, *tp = 0; / trail p/ search for match with kfor (; p & p-datalink);/ verify matchif (p & p-data = k) / found a matche = p-data; / save data/ remove p from chainif (tp)tp-link = p-link;elsefirst = p-link; / p is first node.delete p;return *this;cout输入错误; / no matchtemplateSortedChain&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 SortedChainNode();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;templateSortedChain&SortedChain:DistinctInsert(const E& e) SortedChainNode *p = first, *tp = 0; / trail p/ move tp so that e can be inserted after tpfor (; p & p-datalink);/ check if duplicateif (p & p-data = e)cout输入错误;/ not duplicate, set up node for eSortedChainNode *q = new SortedChainNode;q-data = e;/ insert node just after tpq-link = p;if (tp)tp-link = q;elsefirst = q;return *this;templatevoid SortedChain:Output(ostream& out) constSortedChainNode *p = first;if (!first)out (Empty chain.);elsewhile(p)out datalink;out endl;templateclass 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(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;/ divisorSortedChain * ht;/ array of chains;template class ChainHashTable ;templatevoid ChainHashTable:Output(ostream& out) const out 散列余数, 数值 endl;for (int i = 0; i D; i+) out i ,thti;void dea