山东大学数据结构实验报告四

.. . 下载可编辑 . 大学 软件工程 学院 数据结构 课程实验报告

学号： ： 班级：软件工程2014级2班 实验题目：矩阵和散列表 实验学时： 实验日期： 2015.11.11 实验目的：

掌握特殊矩阵和稀疏矩阵。 掌握散列表及其应用。

硬件环境： 实验室 软件环境： Vistual Studio 2013

实验步骤与容：

实验容： 1、创建三对角矩阵类，采用按列映射方式，提供store和retrieve 方法。 2、创建下三角矩阵类，采用按列映射方式，提供store和retrieve 方法。 3、创建稀疏矩阵类，采用行主顺序把稀疏矩阵映射到一维数组中，实现稀疏矩阵的转置和两个稀疏矩阵的加法操作。 4、使用散列表设计实现一个字典，假设关键字为整数且D为961，在字典中插入随机产生的500个不同的整数，实现字典的建立和搜索操作。分别使用线性开型寻址和链表散列解决溢出。 代码体： ChainHashTableNode.h #pragma once #include"ChainHashTableNode.h" .. . 下载可编辑 . using namespace std; class ChainHashTable { public: ChainHashTable(int divisor); ~ChainHashTable(); bool Insert(int k); bool Search(int k); void print(); private: int d; ChainHashTableNode *ht; }; ChainHashTableNode.cpp #include "ChainHashTable.h" #include using namespace std;

ChainHashTable::ChainHashTable(int divisor) { d = divisor; ht = new ChainHashTableNode[d]; } bool ChainHashTable::Insert(int k) { int j = k%d; if (ht[j].Insert(k)) { return true; } else{ return false; } } void ChainHashTable::print() { for (int i = 0; i < d; i++) { ht[i].print(); } } ChainHashTableNode.h #pragma once #include"Node.h" .. . 下载可编辑 . class ChainHashTableNode { public: ChainHashTableNode(); bool Insert(int k); bool Search(int k); void print(); private: Node *first; }; ChainHashTableNode.cpp #include "ChainHashTableNode.h" #include using namespace std; ChainHashTableNode::ChainHashTableNode() { first = 0; } bool ChainHashTableNode::Search(int k) { if (first == 0) return false; Node *current = first; while (current) { if (current->value == k) { return true; } current = current->link; if (current) { if (current->value == k) { return true; } } } return false; } bool ChainHashTableNode::Insert(int k) { if (Search(k)) { cout << "已经存在此元素" << endl; .. . 下载可编辑 . return false; } else { Node *p = new Node(); p->value = k; if (first == 0) { first = p; return true; } else { p->link = first; first = p; return true; }

} } void ChainHashTableNode::print() { Node *current = first; if (first) { while (first) { cout << first->value << " "; first = first->link; } cout << endl; first = current; } else { cout << -1 << endl; } } HashTable.h #pragma once class HashTable { public: HashTable(int divisor); ~HashTable(); int Search(int k);//搜索算法 .. . 下载可编辑 . bool Insert(int e); void print(); private: int hSearch(int k); int d;//除数 int *ht;//桶，大小取决于d就是除数是多少 bool *empty;//一维数组，用来存储第I个桶是否存入了元素 }; HashTable.cpp #include "HashTable.h" #include using namespace std;

HashTable::HashTable(int divisor) { d = divisor; ht = new int[d]; empty = new bool[d]; for (int i = 0; i < d; i++) { empty[i] = true; ht[i] = 0; }

}

HashTable::~HashTable() { delete[]ht; delete[]empty; }

int HashTable::hSearch(int k)//搜索值为K的元素 { int i = k%d; int j = i; do{ if (ht[j] == k || empty[j]) return j; j = (j + 1) % d; } while (j != i); return j; } .. . 下载可编辑 . int HashTable::Search(int k)//搜索值为K的元素 { int b = hSearch(k); if (ht[b] == k) return b; return -1; } bool HashTable::Insert(int e) { int b = hSearch(e); if (empty[b]) { ht[b] = e; empty[b] = false; return true; } else if (ht[b] == e) { cout << "已经存在此元素" << endl; return false; } else { cout << "表已经满了" << endl; return false; } } void HashTable::print() { for (int i = 0; i < 961; i++){ cout << ht[i] << " "; } cout << endl; return; } LowerTriangularMatrix.h #pragma once class LowerTriangularMatrix { public: LowerTriangularMatrix(int size); void Store(int x, int i, int j);//向矩阵里存储一个元素 int Retrieve(int i, int j);//返回矩阵中的一个元素 void print(); private: