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

1、山东大学软件工程学院数据结构课程实验报告学号：|姓名：|班级：软件工程2014级2班实验题目：矩阵和散列表实验学时:|实验日期:2015.11.11实验目的：掌握特殊矩阵和稀疏矩阵。掌握散列表及其应用。硬件环境：实验室软件环境：Vistual Studio 2013实验步骤与内容：实验内容：1、 创建三对角矩阵类，采用按列映射方式，提供store和retrieve方法。2、 创建下三角矩阵类，采用按列映射方式，提供store和retrieve方法。3、创建稀疏矩阵类，采用行主顺序把稀疏矩阵映射到一维数组中，实现稀疏矩阵的转 置和两个稀疏矩阵的加法操作。4、 使用散列表设计实现一个字典，假设关键

2、字为整数且D为961，在字典中插入随机产 生的500个不同的整数，实现字典的建立和搜索操作。分别使用线性开型寻址和链表散 列解决溢出。代码体：Chai nH ashTableNode.h#pragma once#include ChainHashTableNode.husing namespacestd;class ChainHashTablepublic :ChainHashTable( int divisor);Chai nH ashTable();bool Insert( int k);bool Search( int k);void print();private :int d;Cha

3、i nH ashTableNode *ht;ChainH ashTableNode.cpp#i nclude Chai nH ashTable.h#include divisor )using namespacestd;ChainHashTable:ChainHashTable( int d = divisor ;ht = new ChainHashTableNoded; bool ChainHashTable :Insert(int k)int j = k%d;if (htj.Insert( k)return true ;else return false ;void ChainHashTa

4、ble:print() for (int i = 0; i d; i+)hti.pri nt();Chai nH ashTableNode.h#pragma once#include Node.hclass ChainHashTableNode public :Chai nH ashTableNode(); bool Insert( int k); bool Search( int k);void print();private :Node *first;ChainH ashTableNode.cpp#in clude Chai nH ashTableNode.h#in clude using

5、 namespacestd;Chai nH ashTableNode:Chai nH ashTableNode() first = 0;bool ChainHashTableNode:Search( int k) if (first = 0) return false ;Node *curre nt = first;while (current)if (current-value =k) |return true ;curre nt = curre nt-li nk;if(curre nt)if (current-value =k)return true ;return false ;bool

6、 ChainHashTableNode:Insert( int k)if (Search( k)cout 已经存在此元素value = k;if (first = 0) |first = p; return true ;elsep-li nk = first;first = p; return true ; |void ChainHashTableNode:print()Node *curre nt = first;if (first)while (first) |cout value li nk; |cout en dl;first = curre nt;else cout -1 en dl

7、;HashTable.h#pragma onceclass HashTablepublic :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#in clude HashTable.h#include using namespace

8、std;HashTable:HashTable( int divisor ) d = divisor ;ht = new int d;empty = new bool d;for (int i = 0; i d; i+)emptyi = true ;hti = 0;HashTable:HashTable() delete ht;delete empty; nt HashTable:hSearch( int k) 搜索值为 K的元素 int i = k%d;int j = i;doif (htj = k | empty。)return j;| j 岂+ 1) % d; | while (j !=

9、 i);return j;int HashTable:Search( int k) 搜索值为 K的元素 int b = hSearch( k);if (htb = k) return b;return -1;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;1return false ;uvoidHashTable

10、:pri nt()for (int i = 0; i 961; i+) cout hti cout en dl;return ;LowerTria ngularMatrix.h#pragma onceclass LowerTriangularMatrix public :LowerTria ngularMatrix(int size);void Store( int x, inti,int j); /向矩阵里存储一个兀素int Retrieve( int i, int j);/返回矩阵中的一个元素void print();private :int n; /矩阵维数int sum; II矩阵非零

11、元素个数int *t; II用数组来存储矩阵；LowerTria ngularMatrix.cpp#i nclude LowerTria ngularMatrix.h#in clude using namespacestd;LowerTriangularMatrix:LowerTriangularMatrix(int size )n = size ;sum = n *( n + 1) / 2;t = new int sum;void LowerTriangularMatrix:Store( int x, int i , int j)if ( i 0 | j = n | j = n)cout 下

12、三角矩阵行列输入错误 i j endl; return ;else if ( x = 0)cout 下三角所添加的元素必须非零 endl; return ;else if ( i j)cout 下三角添加元素位置错误 endl; return ;tsum - (n - j )*(n - j + 1) / 2) + ( i - j) = x;return ;nt LowerTriangularMatrix :Retrieve( int i , int j)if ( i 0 | j= (n - 1) | j = (n - 1)cout 三对角矩阵行列输入错误” = j)return tsum -

13、(n - j )*(n - j + 1) / 2) + ( i - j); else return 0;void LowerTriangularMatrix:print()for ( int i = 0; i sum; i+)cout ti ;cout en dl;return ;Node.h#pragma onceclass Nodefrie nd class ChainH ashTableNode;private :int value;Node *li nk;Node.cpp#i nclude Node.husing namespacestd; |SparseMatrix.h#pragma

14、 once#include Term.hclass SparseMatrixpublic :SparseMatrix( int row, int col);void transpose();void Store( int x, int i, int j); / 向矩阵里存储一个元素void Add( SparseMatrix &b); / 两个稀疏矩阵相加 void print();private :int row, col; / 数组维数int sum; /元素个数int maxsum;/最多的元素个数Term *t; /存储的数组jSparseMatrix.cpp#in elude Spa

15、rseMatrix.h#in elude using namespacestd;SparseMatrix :SparseMatrix( int r, int c) maxsum = r *c;t = new Termmaxsum;void SparseMatrix :transpose()Term *cur = new Termmaxsum;int *ColSize = new int col;int *RowNext = new int row;for (int i = 0; i col; i+) ColSizei = 0;for ( int i = 0; i row; i+) RowNex

16、ti = 0;for (int i = 0; i sum; i+) ColSizeti.col+;/ 表示每一列的非零元素个数|RowNext0 = 0; |for (int i = 1; i col; i+) RowNexti = RowNexti - 1 + ColSizei - 1;/ 表示新矩阵中每一行的矩阵的前面的矩阵的个数/进入转置操作for (int i = 0; i sum; i+)int j = RowNextti.col+;curj.value = ti.value;curj.col = ti.row;curj.row = ti.col;void SparseMatrix

17、: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+)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.t

18、sb.col&tsa.row = b.tsb.row)curk.col = tsa.col;curk.row = tsa.row;curk.value = tsa.value +b.tsb.value;k+;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+;elsec

19、urk.value =b.tsb.value;curk.row =b.tsb.row;curk.col =b.tsb.col;k+;sb+; |sum = k;delete t;t = cur;return ;Term.h#pragma onceclass Termfriend class SparseMatrix ;private :int col, row;int value;Term.cpp#i nclude Term.hTridiag on alMatrix.h#pragma onceclass TridiagonalMatrixpublic :TridiagonalMatrix( i

20、nt size);void Store( int x, int i, int j); / 向矩阵里存储一个元素 int Retrieve( int i, int j);/返回矩阵中的一个元素void print();privateint n; /矩阵非0元素个数int *t; /用数组来存储矩阵；Tridiag on alMatrix.cpp#i nclude Tridiago nalMatrix.h#in elude using namespacestd;TridiagonalMatrix:TridiagonalMatrix( int size )n = size ;t = new int

21、3 * n - 2;void TridiagonalMatrix:Store( int x, int i, int j)if ( i 0 | j = n | j = n)cout 三对角矩阵行列输入错误“ vv i “ “ vv 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;re

22、turn ;int TridiagonalMatrix :Retrieve( int i, int j)if ( i 0 II j= (n - 1) | j = (n - 1) cout 三对角矩阵行列输入错误” endl; return -1;else if (abs( i - j) = 1)return t3 * j + ( i - j );else return 0;voidTridiago nalMatrix:prin t()for ( int i = 0; i 3 *n - 2; i+)cout ti cout en dl; return ;Test.cpp#inelude #ine

23、lude #include #include TridiagonalMatrix.h#include LowerTriangularMatrix.h#include SparseMatrix.h#include HashTable.h#include ChainHashTable.h using namespacestd; | int wei, num100100;void c()for (int i = 0; i wei; i+)for (int j = 0; j n umij;int main()JIint k = 0, l = 0;/*三对角矩阵实验开始测试数据4103n-24cout

24、请输入三对焦矩阵维数及内容： wei;c()；TridiagonalMatrix *TM = new TridiagonalMatrix (wei);for (int i = 0; i wei; i+)for (int j = 0; j Store( numji, j, i);TM-pri nt();cout 请输入要查询的元素的位置 k l;l = TM-Retrieve(k, l);cout 查询结果： l endl;cout vv * en dl;/*下三角矩阵实验开始 测试数据410n*(n+1)/247 8 9 -1*/cout 请输入下三角矩阵维数及内容： wei;c();Lowe

25、rTriangularMatrix*LTM = new LowerTriangularMatrix (wei);for (int i = 0; i wei; i+)for (int j = 0; j Store( numji, j, i);LTM-prin t();cout 请输入要查询的元素的位置 k l;l = LTM-Retrieve(k, l);cout 查询结果： l endl;cout “*“ en dl;/*稀疏角矩阵实验开始 测试数据454 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

26、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, l);for ( int i = 0; i k; i+)for (int j = 0; j n umij;if (numij)SM-Store( numij, i, j);cout pri nt();SM-tra nspose();cout pri nt();SM-tra nspose();cout pri nt();cout 矩阵相加开始，请输入要使用的矩阵维数及内容： k l;SparseMatrix *SM2 = new SparseMatrix (k, l);for ( int i = 0; i k; i+)for (int j