《山东大学数据结构实验报告四.doc》由会员分享，可在线阅读，更多相关《山东大学数据结构实验报告四.doc（19页珍藏版）》请在三一文库上搜索。
1、山东大学 软件工程 学院 数据结构 课程实验报告学号：姓名： 班级：软件工程2014级2班实验题目：矩阵和散列表实验学时：实验日期： 2015.11.11 实验目的：掌握特殊矩阵和稀疏矩阵。掌握散列表及其应用。硬件环境：实验室软件环境：Vistual Studio 2013 实验步骤与内容：实验内容：1、创建三对角矩阵类，采用按列映射方式，提供store和retrieve 方法。2、创建下三角矩阵类，采用按列映射方式，提供store和retrieve 方法。3、创建稀疏矩阵类，采用行主顺序把稀疏矩阵映射到一维数组中，实现稀疏矩阵的转置和两个稀疏矩阵的加法操作。4、使用散列表设计实现一个字典，假
2、设关键字为整数且D为961，在字典中插入随机产生的500个不同的整数，实现字典的建立和搜索操作。分别使用线性开型寻址和链表散列解决溢出。代码体：ChainHashTableNode.h#pragma once#includeChainHashTableNode.husing namespace std;class ChainHashTablepublic:ChainHashTable(int divisor);ChainHashTable();bool Insert(int k);bool Search(int k);void print();private:int d;ChainHashTa
3、bleNode *ht;ChainHashTableNode.cpp#include ChainHashTable.h#includeusing namespace std;ChainHashTable:ChainHashTable(int divisor)d = divisor;ht = new ChainHashTableNoded;bool ChainHashTable:Insert(int k)int j = k%d;if (htj.Insert(k)return true;elsereturn false;void ChainHashTable:print()for (int i =
4、 0; i d; i+)hti.print();ChainHashTableNode.h#pragma once#includeNode.hclass ChainHashTableNodepublic:ChainHashTableNode();bool Insert(int k);bool Search(int k);void print();private:Node *first;ChainHashTableNode.cpp#include ChainHashTableNode.h#include using namespace std;ChainHashTableNode:ChainHas
5、hTableNode()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 已经存在此
6、元素 value = k;if (first = 0)first = p;return true;elsep-link = first;first = p;return true;void ChainHashTableNode:print()Node *current = first;if (first)while (first)cout value link;cout endl;first = current;else cout -1 endl;HashTable.h#pragma onceclass HashTablepublic:HashTable(int divisor);HashTa
7、ble();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#includeusing namespace std;HashTable:HashTable(int divisor)d = divisor;ht = new intd;empty = new boold;for (int
8、 i = 0; i d; i+)emptyi = true;hti = 0;HashTable:HashTable()deleteht;deleteempty;int HashTable:hSearch(int k)/搜索值为K的元素int i = k%d;int j = i;doif (htj = k | emptyj) return j;j = (j + 1) % d; while (j != i);return j;int HashTable:Search(int k)/搜索值为K的元素int b = hSearch(k);if (htb = k) return b;return -1;
9、bool HashTable:Insert(int e)int b = hSearch(e);if (emptyb)htb = e;emptyb = false;return true;else if (htb = e)cout 已经存在此元素 endl;return false;elsecout 表已经满了 endl;return false;void HashTable:print()for (int i = 0; i 961; i+)cout hti ;cout endl;return;LowerTriangularMatrix.h#pragma onceclass LowerTrian
10、gularMatrixpublic:LowerTriangularMatrix(int size);void Store(int x, int i, int j);/向矩阵里存储一个元素int Retrieve(int i, int j);/返回矩阵中的一个元素void print();private:int n;/矩阵维数int sum;/矩阵非零元素个数int *t;/用数组来存储矩阵;LowerTriangularMatrix.cpp#include LowerTriangularMatrix.h#include using namespace std;LowerTriangularMa
11、trix:LowerTriangularMatrix(int size)n = size;sum = n*(n + 1) / 2;t = new intsum;void LowerTriangularMatrix:Store(int x, int i, int j)if (i0 | j= n | j = n)cout 下三角矩阵行列输入错误 i j endl;return;else if (x = 0)cout 下三角所添加的元素必须非零 endl;return;else if (ij)cout 下三角添加元素位置错误 endl;return;tsum - (n - j)*(n - j + 1
12、) / 2) + (i - j) = x;return;int LowerTriangularMatrix:Retrieve(int i, int j)if (i0 | j= (n - 1) | j = (n - 1)cout 三对角矩阵行列输入错误 = j)return tsum - (n - j)*(n - j + 1) / 2) + (i - j);elsereturn 0;void LowerTriangularMatrix:print()for (int i = 0; i sum; i+)cout ti ;cout endl;return;Node.h#pragma onceclas
13、s Nodefriend class ChainHashTableNode;private:int value;Node *link;Node.cpp#include Node.husing namespace std;SparseMatrix.h#pragma once#includeTerm.hclass SparseMatrixpublic:SparseMatrix(int row, int col);void transpose();void Store(int x, int i, int j);/向矩阵里存储一个元素void Add(SparseMatrix &b);/两个稀疏矩阵相
14、加void print();private:int row, col;/数组维数int sum;/元素个数int maxsum;/最多的元素个数Term *t;/存储的数组;SparseMatrix.cpp#include SparseMatrix.h#include using namespace std;SparseMatrix:SparseMatrix(int r, int c)row = r;col = c;sum = 0;maxsum = r*c;t = new Termmaxsum;void SparseMatrix:transpose()Term *cur = new Termm
15、axsum;int *ColSize = new intcol;int *RowNext = new introw;for (int i = 0; i col; i+) ColSizei = 0;for (int i = 0; i row; i+) RowNexti = 0;for (int i = 0; i sum; i+) ColSizeti.col+;/表示每一列的非零元素个数RowNext0 = 0;for (int i = 1; i col; i+) RowNexti = RowNexti - 1 + ColSizei - 1;/表示新矩阵中每一行的矩阵的前面的矩阵的个数/进入转置操
16、作for (int i = 0; i sum; i+)int j = RowNextti.col+;curj.value = ti.value;curj.col = ti.row;curj.row = ti.col;delete t;t = cur;void SparseMatrix:Store(int x, int i, int j)tsum.value = x;tsum.row = i;tsum.col = j;sum+;return;void SparseMatrix:print()for (int i = 0; i sum; i+)cout ti.value ;cout endl;re
17、turn;void SparseMatrix:Add(SparseMatrix &b)/两个稀疏矩阵相加if (col != b.col | row != b.row)cout 两个矩阵行列不同无法相加 endl;return;int sa = 0;int sb = 0;Term *cur = new Termmaxsum;int k = 0;while (sa sum | sb b.sum)if (tsa.col = b.tsb.col&tsa.row = b.tsb.row)curk.col = tsa.col;curk.row = tsa.row;curk.value = tsa.val
18、ue + b.tsb.value;k+;sa+;sb+;else if (tsa.row b.tsb.row)curk.value = b.tsb.value;curk.row = b.tsb.row;curk.col = b.tsb.col;k+;sb+;else if (tsa.col tsb.col)curk.col = tsa.col;curk.row = tsa.row;curk.value = tsa.value;k+;sa+;elsecurk.value = b.tsb.value;curk.row = b.tsb.row;curk.col = b.tsb.col;k+;sb+;
19、sum = k;delete t;t = cur;return;Term.h#pragma onceclass Termfriend class SparseMatrix;private:int col, row;int value;Term.cpp#include Term.hTridiagonalMatrix.h#pragma onceclass TridiagonalMatrixpublic:TridiagonalMatrix(int size);void Store(int x, int i, int j);/向矩阵里存储一个元素int Retrieve(int i, int j);/
20、返回矩阵中的一个元素void print();private:int n;/矩阵非0元素个数int *t;/用数组来存储矩阵;TridiagonalMatrix.cpp#include TridiagonalMatrix.h#include using namespace std;TridiagonalMatrix:TridiagonalMatrix(int size)n = size;t = new int3 * n - 2;void TridiagonalMatrix:Store(int x, int i, int j)if (i0 | j= n | j = n)cout 三对角矩阵行列输
21、入错误 i j endl;return;else if (x = 0)cout 三对角矩阵所添加的元素必须非零 1)cout 三对角矩阵添加元素位置错误 endl;return;switch (i - j)case -1:t3 * j - 1 = x;break;case 0:t3 * j = x;break;case 1:t3 * j + 1 = x;break;return;int TridiagonalMatrix:Retrieve(int i, int j)if (i0 | j= (n - 1) | j = (n - 1)cout 三对角矩阵行列输入错误 endl;return -1;
22、else if (abs(i - j) = 1)return t3 * j + (i - j);elsereturn 0;void TridiagonalMatrix:print()for (int i = 0; i 3 * n - 2; i+)cout ti ;cout endl;return;Test.cpp#include#include#include#includeTridiagonalMatrix.h#includeLowerTriangularMatrix.h#includeSparseMatrix.h#includeHashTable.h#includeChainHashTab
23、le.husing namespace std;int wei, num100100;void c()for (int i = 0; i wei; i+)for (int j = 0; j numij;int main()int k = 0, l = 0;/*三对角矩阵实验开始测试数据4103n-241 2 0 03 4 5 00 7 8 90 0 8 7*/cout 请输入三对焦矩阵维数及内容： wei;c();TridiagonalMatrix *TM = new TridiagonalMatrix(wei);for (int i = 0; i wei; i+)for (int j = 0
24、; j Store(numji, j, i);TM-print();cout 请输入要查询的元素的位置 k l;l = TM-Retrieve(k, l);cout 查询结果： l endl;cout * endl;/*下三角矩阵实验开始测试数据410n*(n+1)/241 0 0 02 3 0 04 5 6 07 8 9 -1*/cout 请输入下三角矩阵维数及内容： wei;c();LowerTriangularMatrix *LTM = new LowerTriangularMatrix(wei);for (int i = 0; i wei; i+)for (int j = 0; j S
25、tore(numji, j, i);LTM-print();cout 请输入要查询的元素的位置 k l;l = LTM-Retrieve(k, l);cout 查询结果： l endl;cout * endl;/*稀疏角矩阵实验开始测试数据4 54 51 0 0 0 20 3 0 0 04 0 0 5 00 6 7 0 84 58 0 7 6 00 5 0 0 40 0 0 3 02 0 0 0 19 0 7 6 20 8 0 0 44 0 0 8 02 6 7 0 9*/cout 请输入稀疏矩阵的维数及内容： k l;SparseMatrix *SM = new SparseMatrix(k
26、, l);for (int i = 0; i k; i+)for (int j = 0; j numij;if (numij)SM-Store(numij, i, j);cout print();SM-transpose();cout print();SM-transpose();cout print();cout 矩阵相加开始，请输入要使用的矩阵维数及内容: k l;SparseMatrix *SM2 = new SparseMatrix(k, l);for (int i = 0; i k; i+)for (int j = 0; j numij;if (numij)SM2-Store(num
27、ij, i, j);cout print();SM-Add(*SM2);cout print();cout * endl;cin.get();system(pause);/*使用散列表设计实现一个字典，假设关键字为整数且D为961，在字典中插入随机产生的500个不同的整数，实现字典的建立和搜索操作。分别使用线性开型寻址和链表散列解决溢出*/k = 0; l = 0;cout 随即建立关键字为961,500个元素的散列表 endl;HashTable *BT = new HashTable(961);for (int i = 0; i Insert(j) i+;BT-print();cout 请
28、输入要搜索的元素 k;l = BT-Search(k);cout 元素位置为： l endl;cout 输入要插入的元素 k;BT-Insert(k);BT-print();cout 实现溢出处理，插入所插入元素*2的元素 Insert(2 * k);BT-print();cout * endl;system(pause);/*链表散列解决溢出*/cout 链表散列解决溢出,关键字为50，元素个数100 endl;ChainHashTable *HT = new ChainHashTable(50);for (int i = 0; i Insert(j)i+;HT-print();cout 输入要插入的元素 k;HT-Insert(k);HT-print();cout 实现溢出处理，插入所插入元素*2的元素 Insert(2 * k);HT-print();cout * endl;cin.get();system(pause);实验结果：结论分析与体会：矩阵在数学应用的十分广泛，他有各种各样的分类例如稀疏矩阵，下三角矩阵等等，很是又去。高效而便捷，实际中发挥了很大的作用。操作原理也很简单。