數(shù)據(jù)結(jié)構(gòu)實驗四矩陣和散列表代碼實現(xiàn)

1、1、創(chuàng)建稀疏矩陣類，采用行主順序把稀疏矩陣映射到一維數(shù)組中，實現(xiàn)稀疏矩陣的轉(zhuǎn)置和兩個稀疏矩陣的加法操作。#include #include using namespace std; /三元組 struct Trituple int row, col; /非零元素的行號、列號 int val; /非零元素的值 ; /稀疏矩陣類聲明 class SparseMatrix public: SparseMatrix(int maxt = 100); /構(gòu)造函數(shù) SparseMatrix(); /析構(gòu)函數(shù) bool TransposeTo(SparseMatrix &); /轉(zhuǎn)置 void add(Sp

2、arseMatrix &,SparseMatrix &);/加運算void map();/采用行主順序把稀疏矩陣映射到一維數(shù)組中 bool Input(); /輸入稀疏矩陣 void Output();/輸出稀疏矩陣 Trituple *data; /存儲非零元素三元組的數(shù)組 int rows, cols, terms; /矩陣的行數(shù)、列數(shù)、非零元素個數(shù) int maxterms; /數(shù)組data的大小 ; /構(gòu)造函數(shù)，分配maxt個三元組結(jié)點的順序空間，構(gòu)造一個空的稀疏矩陣三元組表。 SparseMatrix:SparseMatrix(int maxt) maxterms = maxt; d

3、ata = new Trituple maxterms; terms = rows = cols = 0; /析構(gòu)函數(shù)，將三元組表結(jié)構(gòu)銷毀。 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

4、 M.datai.row , M.datai.col = M.datai.val (istream & in, SparseMatrix & N) cout 輸入稀疏矩陣的行數(shù)、列數(shù)以及非零元素個數(shù) 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; ; /轉(zhuǎn)置，將*th

5、is的轉(zhuǎn)置矩陣送入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 = da

6、tak.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) /兩結(jié)點屬于同一行 if(A.dataa.col

7、B.datab.col) /A中下標(biāo)a的結(jié)點小于B中下標(biāo)為b的結(jié)點的列數(shù) 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) /兩結(jié)點屬于同一列 int temp = A.dataa.val+B.datab.val; if(temp = 0) /兩結(jié)點數(shù)值相加等于0 a+; b+; else /兩結(jié)點數(shù)值相加不等于0 datae.val = temp; datae.row = A.dataa.row; datae.col = A

8、.dataa.col; e+; a+; b+; else /A中下標(biāo)a的結(jié)點大于B中下標(biāo)為b的結(jié)點的列數(shù) datae.val = B.datab.val; datae.row=B.datab.row; datae.col=B.datab.col; e+; b+; while(A.dataa.row = k) /只有A中剩下行數(shù)為k的未處理結(jié)點 datae.val = A.dataa.val; datae.row = A.dataa.row; datae.col = A.dataa.col; e+; a+; while(B.datab.row = k) /只有B中剩下行數(shù)為k的未處理結(jié)點 dat

9、ae.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) in

10、dexOfMax = i; else sorted = false; swap(dataindexOfMax,datasize-1); for (int i = 0;i terms;i+)cout datai.val ;cout n; bool SparseMatrix:Input() cout 輸入稀疏矩陣的行數(shù)、列數(shù)以及非零元素個數(shù) rows cols terms; if (terms maxterms) cout 非零元個數(shù)太多！ endl; return false; if (terms = 0) return true; cout 按行序輸入 terms 個非零元素的三元組 endl

11、; 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 ter

12、ms; 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 采用行主順序把稀疏矩陣映射到一維數(shù)組中并輸出 endl;M.map(); cout 轉(zhuǎn)置矩陣： endl; if(M.TransposeTo(T) T.Output();cout輸入第二個矩陣endl; if (C.Input() cout 第二矩陣： endl; C.Output();D.add(M,C);cout 采

13、用行主順序把稀疏矩陣映射到一維數(shù)組中并輸出 endl;D.map(); system(pause); return 0; 2、使用散列表設(shè)計實現(xiàn)一個字典，假設(shè)關(guān)鍵字為整數(shù)且D為961，在字典中插入隨機產(chǎn)生的500個不同的整數(shù)，實現(xiàn)字典的建立和搜索操作。分別使用線性開型尋址和鏈表散列解決溢出。#include#include#include#includeusing namespace std;templateclass HashTable public:HashTable(int divisor = 11);HashTable() delete ht;delete empty;HashTabl

14、e & 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:Ha

15、shTable(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 =

16、e;int b = hSearch(k);if (emptyb) emptyb = false;htb = e;return *this;if (htb = k)cout輸入錯誤;cout沒有可用內(nèi)存;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 散列余數(shù)(所存儲數(shù)值的余數(shù)), 所存儲數(shù)值e

17、ndl;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(

18、);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:SortedC

19、hainNode *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

20、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) Sor

21、tedChainNode* 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(

22、);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

23、 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 ChainH

24、ashTable 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 散列余數(shù), 數(shù)值 endl;for (int i = 0; i D; i+) out i ,thti;void dea