1、山東大學(xué)計算機(jī)科學(xué)與技術(shù)學(xué)院數(shù)據(jù)結(jié)構(gòu)課程實驗報告 學(xué)號：姓名：徐大鵬班級：實驗題目：實驗四_矩陣和散列表實驗學(xué)時：2實驗日期：2015.11.24實驗?zāi)康模赫莆仗厥饩仃嚭拖∈杈仃嚒Ｕ莆丈⒘斜砑捌鋺?yīng)用。硬件環(huán)境： 略軟件環(huán)境：Ubuntu Kylin 15.04 64-bitLinux GCC 4.9.2Java SE Runtime Environment (build 1.8.0_60-b27)Eclipse IDE for C/C+ Developers Mars.1 Release (4.5.1)實驗內(nèi)容與設(shè)計：1. 實驗內(nèi)容（題目內(nèi)容，輸入要求，輸出要求）(1)創(chuàng)建

2、三對角矩陣類，采用按列映射方式，提供store和retrieve 方法。(2)創(chuàng)建下三角矩陣類，采用按列映射方式，提供store和retrieve 方法。(3)創(chuàng)建稀疏矩陣類，采用行主順序把稀疏矩陣映射到一維數(shù)組中，實現(xiàn)稀疏矩陣的轉(zhuǎn)置和兩個稀疏矩陣的加法操作。(4)使用散列表設(shè)計實現(xiàn)一個字典，假設(shè)關(guān)鍵字為整數(shù)且D為961，在字典中插入隨機(jī)產(chǎn)生的500個不同的整數(shù)，實現(xiàn)字典的建立和搜索操作。分別使用線性開型尋址和鏈表散列解決溢出。2.數(shù)據(jù)結(jié)構(gòu)與算法描述（整體思路描述，所需要的數(shù)據(jù)結(jié)構(gòu)與算法）對問題一，從數(shù)學(xué)上推導(dǎo)得出三對角方陣列主映射的函數(shù)關(guān)系式i = 2c + r - 3其中i為元素在數(shù)組e中

3、的下標(biāo)， c為列數(shù)， r為行數(shù)，c1且r1。以此關(guān)系式為TridiagonalMatrix類編寫了Store和Retrieve函數(shù)，并擴(kuò)展編寫了Input函數(shù)和Output函數(shù)。對問題二，從數(shù)學(xué)上推導(dǎo)得出下三角方陣列主映射的函數(shù)關(guān)系式i = n × (c - 1) - 1 + r + c × (1 - c) / 2其中i為元素在數(shù)組e中的下標(biāo)，n為方陣的大小，c為列數(shù)， r為行數(shù)，c1且r1。以此關(guān)系式為LowerTriangularMatrix類編寫了Store和Retrieve函數(shù)，并擴(kuò)展編寫了Input函數(shù)和Output函數(shù)。對問題三，仿課本所述，定義Term類作為S

4、parseMatrix類的友元類，包含行、列、值三個要素的成員變量，用Term類的數(shù)組實現(xiàn)稀疏矩陣的行主映射存儲。查找行為的實現(xiàn)方式是，找到位于目標(biāo)元素前一行的最后一個元素，再從這個元素開始向下搜索，直到找到和目標(biāo)元素同一行但是列數(shù)小于目標(biāo)元素的元素ak-1，然后決定下一步的行為插入一個新項Term作為ak并將已有元素向后移位，還是修改已存在的項ak。以此原理編寫了Store和Retrieve函數(shù)，并擴(kuò)展編寫了Input函數(shù)和Output函數(shù)。對問題四，仿照課本例子編寫了有序鏈表類SortedChain、開放尋址的散列表類HashTable、基于有序鏈表鏈接的散列表類ChainHashTabl

5、e，并對這三個類分別擴(kuò)展編寫了Output函數(shù)。3. 測試結(jié)果（測試輸入，測試輸出）問題一：問題二：上圖顯示了輸入不符合下三角方陣約束時，拋出異常并退出程序。上圖是正常運行的結(jié)果。問題三：普通的輸入和輸出操作如下：矩陣相加：矩陣轉(zhuǎn)置：問題四：以上圖的數(shù)據(jù)為例。從346就應(yīng)該在鏈表鏈接的散列表上看到開放尋址解決沖突的例子。返回開放尋址的輸出段，可以看到符合預(yù)期的結(jié)果：4.實現(xiàn)源代碼（程序風(fēng)格清晰易理解，有充分的注釋）/* * TridiagonalMatrix.h * * Created on: Nov 22, 2015 * Author: xudp */#ifndef TRIDIAGONALM

6、ATRIX_H_#define TRIDIAGONALMATRIX_H_#include <iostream>using namespace std;template<class T>class TridiagonalMatrix public:/ 1、創(chuàng)建三對角矩陣類,采用按列映射方式,提供 store 和 retrieve 方法。TridiagonalMatrix(int size = 10);TridiagonalMatrix();/ row>0, column>0TridiagonalMatrix<T>& Store(int ro

7、w, int column, const T& value);T Retrieve(int row, int column);void Input(istream& in, ostream& out);void Output(ostream& out) const;friend ostream& operator<< (ostream& out, const TridiagonalMatrix<T>& matrix)matrix.Output(out);return out;friend istream&

8、operator>> (istream& in, TridiagonalMatrix<T>& matrix)matrix.Input(in, cout);return in;private:T* e;/ Store all elementsint size;template class TridiagonalMatrix<double>#endif /* TRIDIAGONALMATRIX_H_ */* * TridiagonalMatrix.cpp * * Created on: Nov 22, 2015 * Author: xudp */

9、#include "TridiagonalMatrix.h"#include "Exceptions.h"template<class T>TridiagonalMatrix<T>:TridiagonalMatrix(int size) if (size < 1)throw InvalidParameterValue();e = new T3 * size - 2;this->size = size;template<class T>TridiagonalMatrix<T>:Tridiagona

10、lMatrix() delete e;template<class T>TridiagonalMatrix<T>& TridiagonalMatrix<T>:Store(int row, int column,const T& value) if (row < 1 | row > size | column < 1 | column > size| (row - column) > 1 | (row - column) < -1)throw InvalidParameterValue();e2 * colu

11、mn + row - 3 = value;return *this;template<class T>T TridiagonalMatrix<T>:Retrieve(int row, int column) if (row < 1 | row > size | column < 1 | column > size| (row - column) > 1 | (row - column) < -1)throw InvalidParameterValue();return e2 * column + row - 3;template<

12、;class T>void TridiagonalMatrix<T>:Input(istream& in, ostream& out) out << "請按行主順序依次輸入元素，" << endl;out << "元素個數(shù)必須恰好是" << (3 * size - 2) << "個: "<< endl;for (int i = 0; i < size; i+) for (int j = i - 1; j <= i +

13、1; j+) if (i = 0 && j = -1)continue;if (i = size - 1 && j = size)continue;T element;in >> element;Store(i + 1, j + 1, element);out << "操作成功完成. " << endl;template<class T>void TridiagonalMatrix<T>:Output(ostream& out) const for (int i = 0; i

14、 < size; i+) for (int j = 0; j < size; j+)if (i - j) > 1 | (i - j) < -1)out << "0t"else out << e2 * j + i << "t"out << endl;/* * SparseMatrix.h * * Created on: Oct 20, 2015 * Author: xudp */#ifndef SPARSEMATRIX_H_#define SPARSEMATRIX_H_#include

15、 <iostream>using namespace std;template<class T> class SparseMatrix;template<class T>class Term friend SparseMatrix<T> ;private:int row, col;T value;template<class T>class SparseMatrix public:/* 3、創(chuàng)建稀疏矩陣類,采用行主順序把稀疏矩陣映射到一維數(shù)組中,實現(xiàn)稀 * 疏矩陣的轉(zhuǎn)置和兩個稀疏矩陣的加法操作。 */SparseMatrix(int

16、maxTerms = 10);SparseMatrix(const SparseMatrix<T>& spm);SparseMatrix() delete a;void Transpose(SparseMatrix<T> &b) const;void Add(const SparseMatrix<T> &b, SparseMatrix<T> &c) const;/* * Write the store and retrieve functions for a sparse matrix stored in * ro

17、w-major order in a one-dimensional array. */SparseMatrix<T>& Store(const T& x, int i, int j);T Retrieve(int i, int j) const;void Input(istream& in, ostream& out);void Output(ostream& out) const;friend ostream& operator<<(ostream& out, const SparseMatrix<T&g

18、t;& matrix) matrix.Output(out);return out;friend istream& operator>>(istream& in, SparseMatrix<T>& matrix) matrix.Input(in, cout);return in;int GetMaxSize()return MaxTerms;private:void Append(const Term<T>& t);int rows, cols; / matrix dimensionsint terms; / curr

19、ent number of nonzero termsTerm<T> * a; / term arrayint MaxTerms; / size of array a;template class SparseMatrix<double> ;#endif /* SPARSEMATRIX_H_ */* * SparseMatrix.cpp * * Created on: Oct 20, 2015 * Author: xudp */#include "SparseMatrix.h"#include "Exceptions.h"temp

20、late<class T>SparseMatrix<T>:SparseMatrix(int maxTerms) / Sparse matrix constructor.if (maxTerms < 1)throw BadInitializers();MaxTerms = maxTerms;a = new Term<T> MaxTerms;terms = cols = rows = 0;template<class T>SparseMatrix<T>& SparseMatrix<T>:Store(const T

21、& theVal, int theRow,int theCol) if (theRow < 1 | theCol < 1 | theRow > rows | theCol > cols)throw OutOfBounds();int cursor = -1;do cursor+;if (cursor = terms) Term<T> t;t.row = theRow;t.col = theCol;t.value = theVal;Append(t);return *this; while (acursor.row < theRow| (acur

22、sor.row = theRow && acursor.col < theCol);if (acursor.row = theRow && acursor.col = theCol) / (theRow,theCol) is already existent.acursor.value = theVal;else if (terms >= MaxTerms)throw NoMem();for (int k = terms - 1; k >= cursor; k-) ak + 1 = ak;acursor.row = theRow;acursor

23、.col = theCol;acursor.value = theVal;terms+;return *this;template<class T>T SparseMatrix<T>:Retrieve(int theRow, int theCol) const if (theRow < 1 | theCol < 1 | theRow > rows | theCol > cols)throw OutOfBounds();int cursor = 0;while (acursor.row < theRow| (acursor.row = the

24、Row && acursor.col < theCol) cursor+;if (cursor = terms) / not in the sparse matrixreturn 0;if (acursor.row = theRow && acursor.col = theCol) / (theRow,theCol) is already existent.return acursor.value;elsereturn 0;template<class T>void SparseMatrix<T>:Output(ostream&am

25、p; out) const out << "最大容許行數(shù)：" << rows << " 最大容許列數(shù)：" << cols << " 非零元素數(shù)：" << terms<< endl;/ put terms, one per linefor (int i = 0; i < terms; i+)out << "a(" << ai.row << ',' << ai.col

26、 << ") = " << ai.value<< endl;template<class T>void SparseMatrix<T>:Input(istream& in, ostream& out) out << "分別輸入行數(shù)最大值，列數(shù)最大值，以及本次輸入的元素組數(shù)："int theTerms;in >> rows >> cols >> theTerms;if (theTerms > MaxTerms)throw NoM

27、em();/ input termsint theRow, theCol;T theVal;for (int i = 0; i < theTerms; i+) out << "依次輸入第" << (i + 1) << "項的所在的行、列，以及它對應(yīng)的數(shù)值"in >> theRow >> theCol >> theVal;Store(theVal, theRow, theCol);template<class T>void SparseMatrix<T>:

28、Transpose(SparseMatrix<T> &b) const / Return transpose of *this in b./ make sure b has enough spaceif (terms > b.MaxTerms)throw NoMem();/ set transpose characteristicsb.cols = rows;b.rows = cols;b.terms = terms;/ initialize to compute transposeint *ColSize, *RowNext;ColSize = new intcol

29、s + 1;RowNext = new introws + 1;/ find number of entries in each column of *thisfor (int i = 1; i <= cols; i+) / initializeColSizei = 0;for (int i = 0; i < terms; i+)ColSizeai.col+;/ find the starting point of each row of bRowNext1 = 0;for (int i = 2; i <= cols; i+)RowNexti = RowNexti - 1 +

30、 ColSizei - 1;/ perform the transpose copying from *this to bfor (int i = 0; i < terms; i+) int j = RowNextai.col+; / position in bb.aj.row = ai.col;b.aj.col = ai.row;b.aj.value = ai.value;template<class T>void SparseMatrix<T>:Add(const SparseMatrix<T> &b, SparseMatrix<T&

31、gt; &c) const / Compute c = (*this) + b./ 矩陣規(guī)模匹配if (rows != b.rows | cols != b.cols)throw SizeMismatch();c.cols = cols;c.rows = rows;/ 重新初始化稀疏矩陣cdelete c.a;int newMaxTerms = b.terms + terms;c.MaxTerms = (newMaxTerms > c.MaxTerms) ? newMaxTerms : c.MaxTerms;c.a = new Term<T> c.MaxTerms;/

32、 Not the best way.bool* hasMatched_b = new boolb.terms;for (int i = 0; i < b.terms; i+)hasMatched_bi = false;int curIndex = 0;for (int i = 0; i < terms; i+) bool isMatched = false;for (int j = 0; j < b.terms; j+) if (ai.row = b.aj.row && ai.col = b.aj.col) isMatched = true;hasMatche

33、d_bj = true;c.acurIndex.row = ai.row;c.acurIndex.col = ai.col;c.acurIndex.value = ai.value + b.aj .value;break;if (!isMatched) c.acurIndex.row = ai.row;c.acurIndex.col = ai.col;c.acurIndex.value = ai.value;curIndex+;for (int i = 0; i < b.terms; i+) if (!hasMatched_bi) c.acurIndex.row = b.ai.row;c

34、.acurIndex.col = b.ai.col;c.acurIndex.value = b.ai.value;curIndex+;/ When writing this function by myself, I forgot the following:c.terms = curIndex;delete hasMatched_b;template<class T>void SparseMatrix<T>:Append(const Term<T>& t) / Append a nonzero term t to *thisif (terms &g

35、t;= MaxTerms)throw NoMem();aterms = t;terms+;/* * SortedChain.h * * Created on: Nov 9, 2015 * Author: xudp */#ifndef SORTEDCHAIN_H_#define SORTEDCHAIN_H_#include <iostream>using namespace std;/* template note: E denotes the data type of the chain elements, and K * that of the keys on which the

36、 chain is sorted. */template<class E, class K> class SortedChain;template<class E, class K>class SortedChainNode friend class SortedChain<E, K> ;private:E data;SortedChainNode<E, K> *link;template<class E, class K>class SortedChain public:SortedChain() first = 0;SortedC

37、hain();bool IsEmpty() const return first = 0;int Length() const;bool Search(const K& k, E& e) const;SortedChain<E, K>& Delete(const K& k, E& e);SortedChain<E, K>& Insert(const E& e);SortedChain<E, K>& DistinctInsert(const E& e);void Output(ostrea

38、m& out) const;friend ostream& operator<< (ostream& out, const SortedChain<E,K>& sc)sc.Output(out);return out;private:SortedChainNode<E, K> *first;template class SortedChainNode<long, long> ;template class SortedChain<long, long> ;#endif /* SORTEDCHAIN_H_

39、 */* * SortedChain.cpp * * Created on: Nov 9, 2015 * Author: xudp */#include "SortedChain.h"#include "Exceptions.h"template<class E, class K>SortedChain<E, K>:SortedChain() SortedChainNode<E, K>* p = first;SortedChainNode<E, K>* tmp;while (p) tmp = p;p = p

40、->link;delete tmp;template<class E, class K>int SortedChain<E, K>:Length() const SortedChainNode<E, K> *p = first;int ret = 0;while (p) ret+;p = p->link;return ret;template<class E, class K>bool SortedChain<E, K>:Search(const K& k, E& e) const / Put elemen

41、t that matches k in e./ Return false if no match.SortedChainNode<E, K> *p = first;/ search for match with kfor (; p && p->data < k; p = p->link);/ verify matchif (p && p->data = k) / yes, found matche = p->data;return true;return false;template<class E, class

42、K>SortedChain<E, K>& SortedChain<E, K>:Delete(const K& k, E& e) / Delete element that matches k./ Put deleted element in e./ Throw BadInput exception if no match.SortedChainNode<E, K> *p = first, *tp = 0; / trail p/ search for match with kfor (; p && p->da

43、ta < k; tp = p, p = p->link);/ 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;throw BadInput(); / no matchtemplate<class E, class K>

44、;SortedChain<E, K>& SortedChain<E, K>:Insert(const E& e) SortedChainNode<E, K>* p;if (!first | first->data >= e) p = new SortedChainNode<E, K>();p->data = e;p->link = first;first = p; else p = first;while (p->link) if (p->link->data < e) p = p-

45、>link; else SortedChainNode<E, K>* ncn = new SortedChainNode<E, K>();ncn->data = e;ncn->link = p->link;p->link = ncn;break;if (!p->link) p->link = new SortedChainNode<E, K>();p = p->link;p->link = 0;p->data = e;return *this;template<class E, class K

46、>SortedChain<E, K>& SortedChain<E, K>:DistinctInsert(const E& e) / Insert e only if no element with same key/ currently in list./ Throw BadInput exception if duplicate.SortedChainNode<E, K> *p = first, *tp = 0; / trail p/ move tp so that e can be inserted after tpfor (;

47、p && p->data < e; tp = p, p = p->link);/ check if duplicateif (p && p->data = e)throw BadInput();/ not duplicate, set up node for eSortedChainNode<E, K> *q = new SortedChainNode<E, K>q->data = e;/ insert node just after tpq->link = p;if (tp)tp->link =

48、 q;elsefirst = q;return *this;template<class E, class K>void SortedChain<E, K>:Output(ostream& out) constSortedChainNode<E, K> *p = first;if (!first)out << "(Empty chain.)"elsewhile(p)out << p->data << "t"p = p->link;out << endl

49、;/* * LowerTriangularMatrix.h * * Created on: Nov 22, 2015 * Author: xudp */#ifndef LOWERTRIANGULARMATRIX_H_#define LOWERTRIANGULARMATRIX_H_#include <iostream>using namespace std;template<class T>class LowerTriangularMatrix public:/ 2、創(chuàng)建下三角矩陣類,采用按列映射方式,提供 store 和 retrieve 方法。LowerTriangu

50、larMatrix(int size = 10);LowerTriangularMatrix();/ row>0, column>0LowerTriangularMatrix<T>& Store(int row, int column, const T& value);T Retrieve(int row, int column);void Input(istream& in, ostream& out);void Output(ostream& out) const;friend ostream& operator<

51、;<(ostream& out,const LowerTriangularMatrix<T>& matrix) matrix.Output(out);return out;friend istream& operator>>(istream& in, LowerTriangularMatrix<T>& matrix) matrix.Input(in, cout);return in;private:T* e;/ Store all elementsint size;template class LowerTria

52、ngularMatrix<double> ;#endif /* LOWERTRIANGULARMATRIX_H_ */* * LowerTriangularMatrix.cpp * * Created on: Nov 22, 2015 * Author: xudp */#include "LowerTriangularMatrix.h"#include "Exceptions.h"template<class T>LowerTriangularMatrix<T>:LowerTriangularMatrix(int si

53、ze) if (size < 1)throw InvalidParameterValue();e = new Tsize * (size + 1) / 2;this->size = size;template<class T>LowerTriangularMatrix<T>:LowerTriangularMatrix() delete e;template<class T>LowerTriangularMatrix<T>& LowerTriangularMatrix<T>:Store(int row, int co

54、lumn,const T& value) if (row < 1 | row < column | column < 1)throw InvalidParameterValue();esize * (column - 1) - 1 + row + column * (1 - column) / 2 = value;return *this;template<class T>T LowerTriangularMatrix<T>:Retrieve(int row, int column) if (row < 1 | row > size

55、 | column < 1 | column > size| (row - column) > 1 | (row - column) < -1)throw InvalidParameterValue();return esize * (column - 1) - 1 + row + column * (1 - column) / 2;template<class T>void LowerTriangularMatrix<T>:Input(istream& in, ostream& out)out << "請按

56、行主順序依次輸入元素，" << endl;out << "元素個數(shù)必須恰好是" << (size * (size + 1) / 2) << "個: "<< endl;for (int i = 0; i < size; i+) for (int j = 0; j <= i; j+) T element;in >> element;Store(i + 1, j + 1, element);out << "操作成功完成. " <&

57、lt; endl;template<class T>void LowerTriangularMatrix<T>:Output(ostream& out) const for (int i = 0; i < size; i+) for (int j = 0; j < size; j+)if (j > i)out << "0t"else out << esize * j + i - j * (j + 1) / 2 << "t"out << endl;/* * HashTable.h * * Created on: Nov 23, 2015 * Author: xudp */#ifndef HASHTABLE_H_#define HASHTABLE_H_#include <iostream>using namespace std;template<class E, class K>class HashTable /* * 4、使用散列表設(shè)計實現(xiàn)一個字典,假設(shè)關(guān)鍵字為整數(shù)且 D 為 961,在字典 * 中插入隨機(jī)產(chǎn)生的 500 個不同的整數(shù),實現(xiàn)字典的建立和搜索操作。