山东大学-数据结构实验报告-矩阵及散列表.docx

山东大学计算机科学与技术学院
数据结构课程实验报告

学号：
姓名：徐大鹏
班级：
实验题目：实验四_矩阵和散列表
实验学时：2
实验日期：2015.11.24
实验目的：
掌握特殊矩阵和稀疏矩阵。
掌握散列表及其应用。
硬件环境： 
略
软件环境：
Ubuntu Kylin 15.04 64-bit
Linux GCC 4.9.2
Java SE Runtime Environment (build 1.8.0_60-b27)
Eclipse IDE for C/C++ Developers Mars.1 Release (4.5.1)
实验内容与设计：
1. 实验内容（题目内容，输入要求，输出要求）
(1)创建三对角矩阵类，采用按列映射方式，提供store和retrieve 方法。
(2)创建下三角矩阵类，采用按列映射方式，提供store和retrieve 方法。
(3)创建稀疏矩阵类，采用行主顺序把稀疏矩阵映射到一维数组中，实现稀疏矩阵的转置和两个稀疏矩阵的加法操作。
(4)使用散列表设计实现一个字典，假设关键字为整数且D为961，在字典中插入随机产生的500个不同的整数，实现字典的建立和搜索操作。分别使用线性开型寻址和链表散列解决溢出。

2.数据结构与算法描述 （整体思路描述，所需要的数据结构与算法）
对问题一，从数学上推导得出三对角方阵列主映射的函数关系式
i = 2c + r - 3
其中i为元素在数组e中的下标， c为列数， r为行数，c≥1且r≥1。以此关系式为TridiagonalMatrix类编写了Store和Retrieve函数，并扩展编写了Input函数和Output函数。
对问题二，从数学上推导得出下三角方阵列主映射的函数关系式
i = n × (c - 1) - 1 + r + c × (1 - c) / 2
其中i为元素在数组e中的下标，n为方阵的大小，c为列数， r为行数，c≥1且r≥1。以此关系式为LowerTriangularMatrix类编写了Store和Retrieve函数，并扩展编写了Input函数和Output函数。
对问题三，仿课本所述，定义Term类作为SparseMatrix类的友元类，包含行、列、值三个要素的成员变量，用Term类的数组实现稀疏矩阵的行主映射存储。查找行为的实现方式是，找到位于目标元素前一行的最后一个元素，再从这个元素开始向下搜索，直到找到和目标元素同一行但是列数小于目标元素的元素a[k-1]，然后决定下一步的行为————插入一个新项Term作为a[k]并将已有元素向后移位，还是修改已存在的项a[k]。以此原理编写了Store和Retrieve函数，并扩展编写了Input函数和Output函数。
对问题四，仿照课本例子编写了有序链表类SortedChain、开放寻址的散列表类HashTable、基于有序链表链接的散列表类ChainHashTable，并对这三个类分别扩展编写了Output函数。
3. 测试结果（测试输入，测试输出）
问题一：

问题二：

上图显示了输入不符合下三角方阵约束时，抛出异常并退出程序。

上图是正常运行的结果。
问题三：
普通的输入和输出操作如下：

矩阵相加：

矩阵转置：

问题四：

以上图的数据为例。从346就应该在链表链接的散列表上看到开放寻址解决冲突的例子。返回开放寻址的输出段，可以看到符合预期的结果：

4.实现源代码（程序风格清晰易理解，有充分的注释）
/*
* TridiagonalMatrix.h
*
* Created on: Nov 22, 2015
* Author: xudp
*/

#ifndef TRIDIAGONALMATRIX_H_
#define TRIDIAGONALMATRIX_H_

#include <iostream>
using namespace std;

template<class T>
class TridiagonalMatrix {
public:
// 1、创建三对角矩阵类,采用按列映射方式,提供 store 和 retrieve 方法。
TridiagonalMatrix(int size = 10);
~TridiagonalMatrix();
// row>0, column>0
TridiagonalMatrix<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<< (ostream& out, const TridiagonalMatrix<T>& matrix){
matrix.Output(out);
return out;
}
friend istream& operator>> (istream& in, TridiagonalMatrix<T>& matrix){
matrix.Input(in, cout);
return in;
}
private:
T* e; // Store all elements
int size;
};

template class TridiagonalMatrix<double>;

#endif /* TRIDIAGONALMATRIX_H_ */

/*
* TridiagonalMatrix.cpp
*
* Created on: Nov 22, 2015
* Author: xudp
*/

#include "TridiagonalMatrix.h"
#include "Exceptions.h"

template<class T>
TridiagonalMatrix<T>::TridiagonalMatrix(int size) {
if (size < 1)
throw InvalidParameterValue();
e = new T[3 * size - 2];
this->size = size;
}

template<class T>
TridiagonalMatrix<T>::~TridiagonalMatrix() {
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();
e[2 * column + 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 e[2 * column + row - 3];
}

template<class T>
void TridiagonalMatrix<T>::Input(istream& in, ostream& out) {
out << "请按行主顺序依次输入元素，" << endl;
out << "元素个数必须恰好是" << (3 * size - 2) << "个: "
<< endl;
for (int i = 0; i < size; i++) {
for (int j = i - 1; j <= i + 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 < size; i++) {
for (int j = 0; j < size; j++)
if ((i - j) > 1 || (i - j) < -1)
out << "0\t";
else {
out << e[2 * j + i] << "\t";
}
out << endl;
}
}

/*
* SparseMatrix.h
*
* Created on: Oct 20, 2015
* Author: xudp
*/

#ifndef SPARSEMATRIX_H_
#define SPARSEMATRIX_H_

#include <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、创建稀疏矩阵类,采用行主顺序把稀疏矩阵映射到一维数组中,实现稀
* 疏矩阵的转置和两个稀疏矩阵的加法操作。
*/
SparseMatrix(int 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
* row-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>& 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 dimensions
int terms; // current number of nonzero terms
Term<T> * a; // term array
int 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"

template<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& 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 (a[cursor].row < theRow
|| (a[cursor].row == theRow && a[cursor].col < theCol));

if (a[cursor].row == theRow && a[cursor].col == theCol) // (theRow,theCol) is already existent.
a[cursor].value = theVal;
else {
if (terms >= MaxTerms)
throw NoMem();
for (int k = terms - 1; k >= cursor; k--) {
a[k + 1] = a[k];
}
a[cursor].row = theRow;
a[cursor].col = theCol;
a[cursor].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 (a[cursor].row < theRow
|| (a[cursor].row == theRow && a[cursor].col < theCol)) {
cursor++;
if (cursor == terms) // not in the sparse matrix
return 0;
}

if (a[cursor].row == theRow && a[cursor].col == theCol) // (theRow,theCol) is already existent.
return a[cursor].value;
else
return 0;
}

template<class T>
void SparseMatrix<T>::Output(ostream& out) const {
out << "最大容许行数：" << rows << " 最大容许列数：" << cols << " 非零元素数：" << terms
<< endl;

// put terms, one per line
for (int i = 0; i < terms; i++)
out << "a(" << a[i].row << ',' << a[i].col << ") = " << a[i].value
<< endl;
}

template<class T>
void SparseMatrix<T>::Input(istream& in, ostream& out) {
out << "分别输入行数最大值，列数最大值，以及本次输入的元素组数：";
int theTerms;
in >> rows >> cols >> theTerms;
if (theTerms > MaxTerms)
throw NoMem();

// input terms
int theRow, theCol;
T theVal;
for (int i = 0; i < theTerms; i++) {
out << "依次输入第" << (i + 1) << "项的所在的行、列，以及它对应的数值";
in >> theRow >> theCol >> theVal;
Store(theVal, theRow, theCol);
}
}

template<class T>
void SparseMatrix<T>::Transpose(SparseMatrix<T> &b) const {
// Return transpose of *this in b.

// make sure b has enough space
if (terms > b.MaxTerms)
throw NoMem();

// set transpose characteristics
b.cols = rows;
b.rows = cols;
b.terms = terms;

// initialize to compute transpose
int *ColSize, *RowNext;
ColSize = new int[cols + 1];
RowNext = new int[rows + 1];

// find number of entries in each column of *this
for (int i = 1; i <= cols; i++) // initialize
ColSize[i] = 0;
for (int i = 0; i < terms; i++)
ColSize[a[i].col]++;

// find the starting point of each row of b
RowNext[1] = 0;
for (int i = 2; i <= cols; i++)
RowNext[i] = RowNext[i - 1] + ColSize[i - 1];

// perform the transpose copying from *this to b
for (int i = 0; i < terms; i++) {
int j = RowNext[a[i].col]++; // position in b
b.a[j].row = a[i].col;
b.a[j].col = a[i].row;
b.a[j].value = a[i].value;
}

}

template<class T>
void SparseMatrix<T>::Add(const SparseMatrix<T> &b, SparseMatrix<T> &c) const {
// Compute c = (*this) + b.
// 矩阵规模匹配
if (rows != b.rows || cols != b.cols)
throw SizeMismatch();
c.cols = cols;
c.rows = rows;

// 重新初始化稀疏矩阵c
delete[] c.a;
int newMaxTerms = b.terms + terms;
c.MaxTerms = (newMaxTerms > c.MaxTerms) ? newMaxTerms : c.MaxTerms;
c.a = new Term<T> [c.MaxTerms];

// Not the best way.
bool* hasMatched_b = new bool[b.terms];
for (int i = 0; i < b.terms; i++)
hasMatched_b[i] = false;
int curIndex = 0;
for (int i = 0; i < terms; i++) {
bool isMatched = false;
for (int j = 0; j < b.terms; j++) {
if (a[i].row == b.a[j].row && a[i].col == b.a[j].col) {
isMatched = true;
hasMatched_b[j] = true;
c.a[curIndex].row = a[i].row;
c.a[curIndex].col = a[i].col;
c.a[curIndex].value = a[i].value + b.a[j ].value;
break;
}
}
if (!isMatched) {
c.a[curIndex].row = a[i].row;
c.a[curIndex].col = a[i].col;
c.a[curIndex].value = a[i].value;
}
curIndex++;
}
for (int i = 0; i < b.terms; i++) {
if (!hasMatched_b[i]) {
c.a[curIndex].row = b.a[i].row;
c.a[curIndex].col = b.a[i].col;
c.a[curIndex].value = b.a[i].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 *this
if (terms >= MaxTerms)
throw NoMem();
a[terms] = 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 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;
}
~SortedChain();
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(ostream& 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_ */

/*
* 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->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 element that matches k in e.
// Return false if no match.
SortedChainNode<E, K> *p = first;

// search for match with k
for (; p && p->data < k; p = p->link)
;

// verify match
if (p && p->data == k) // yes, found match
{
e = p->data;
return true;
}
return false;
}

template<class E, class 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 k
for (; p && p->data < k; tp = p, p = p->link)
;

// 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;
else
first = p->link; // p is first node.

delete p;
return *this;
}
throw BadInput(); // no match
}

template<class E, class K>
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->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>
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 tp
for (; p && p->data < e; tp = p, p = p->link)
;

// check if duplicate
if (p && p->data == e)
throw BadInput();

// not duplicate, set up node for e
SortedChainNode<E, K> *q = new SortedChainNode<E, K>;
q->data = e;

// insert node just after tp
q->link = p;
if (tp)
tp->link = q;
else
first = q;

return *this;
}

template<class E, class K>
void SortedChain<E, K>::Output(ostream& out) const{
SortedChainNode<E, K> *p = first;
if (!first)
out << "(Empty chain.)";
else
while(p){
out << p->data << "\t";