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

山东大学 软件工程 学院 数据结构 课程实验报告 学号： 姓名： 班级：软件工程 2014 级 2 班 实验题目：矩阵和散列表 实验学时： 实验日期： 2015.11.11 实验目的： 掌握特殊矩阵和稀疏矩阵。 掌握散列表及其应用。 硬件环境： 实验室 软件环境： Vistual Studio 2013 实验步骤与内容： 实验内容： 1、创建三对角矩阵类，采用按列映射方式，提供 store 和 retrieve 方法。 2、创建下三角矩阵类，采用按列映射方式，提供 store 和 retrieve 方法。 3、创建稀疏矩阵类，采用行主顺序把稀疏矩阵映射到一维数组中，实现稀疏矩阵的转 置和两个稀疏矩阵的加法操作。 4 、使用散列表设计实现一个字典，假设关键字为整数且 D 为 961 ，在字典中插入随机产 生的 500 个不同的整数，实现字典的建立和有哪些信誉好的足球投注网站操作。分别使用线性开型寻址和链表散 列解决溢出。 代码体： ChainHashTableNode.h #pragma once #includeChainHashTableNode.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 #includeiostream 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 #includeNode.h class ChainHashTableNode { public: ChainHashTableNode(); bool Insert(int k); bool Search(int k); void print(); private: Node *first; }; ChainHashTableNode.cpp #include ChainHashTableNode.h #include iostream using namespace std; ChainHashTableNode::ChainHashTableNode() { first = 0; } bool ChainHashTableNode::Search(int k) { if (first == 0