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

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.h"using namespacestd;class ChainHashTablepublic :ChainHashTable( int divisor);Chai nH ashTable();bool Insert( int k);bool Search( int k); void print();priva

3、te :int d;Chai nH ashTableNode *ht;ChainH ashTableNode.cpp#i nclude "Chai nH ashTable.h"#include <iostream>divisor )using namespacestd;ChainHashTable:ChainHashTable( int d = divisor ;ht = new ChainHashTableNoded; bool ChainHashTable :Insert( int k) int j = k%d;if (htj.Insert( k)retur

4、n true ;else return false ;void ChainHashTable:print()Chai nH ashTableNode.h#pragma once#include "Node.h"class ChainHashTableNode Ifirst = 0;bool ChainHashTableNode:Search( int k) if (first = 0) return false ;Node *curre nt = first;while (current)if (current->value = k)return true ;curr

5、e nt = curre nt->li nk;if (current)| dif (current->value =k)return true ;return false ;bool ChainHashTableNode:Insert(int k)if (Search( k)cout << "已经存在此元素"<< endl;return falsevoid ChainHashTableNode:print() Node *curre nt = first;if (first)while (first)cout << first

6、->value << first = first->li nk;cout << en dl; first = curre nt;else cout << -1 << en dl;HashTable.h#pragma onceclass HashTablepublic :HashTable( int divisor);HashTable();int Search( int k); / 搜索算法bool Insert( int e);#in elude "HashTable.h"#inelude <iostrea

7、m>using namespaeestd;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;int HashTable:hSearch( int k) 搜索值为 K的元素 int i = k%d;int j = i;doif (htj = k | emptyj) return j;j =

8、 (j + 1) % d; while (j != i);return j;nt 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 fals

9、e ;elsecout << "表已经满了 " << endl; return false ;void HashTable:print()for (int i = 0; i < 961; i+)cout << hti <<""cout << en dl;return ;LowerTria ngularMatrix.h #pragma once class LowerTriangularMatrix public :int Retrieve( int i, int j);/返回矩阵中的一个元

10、素void print();private :int n; /矩阵维数LowerTria ngularMatrix.cpp#i nclude "LowerTria ngularMatrix.h"#in elude <iostream>using namespacestd;LowerTriangularMatrix:LowerTriangularMatrix(int size )void LowerTriangularMatrix :Store( int x, int i , int j)if ( i <0 | j <0 | i >= n | j

11、 >= n)cout << "下三角矩阵行列输入错误"<< 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) +

12、 ( i - j) = x; return ;nt LowerTriangularMatrix :Retrieve( int i , int j)if(i<0 |j<0 |i >= (n - 1) |j >= (n - 1)cout <<"三对角矩阵行列输入错误” << endl;return-1;else if ( i>=j)else return 0; void LowerTriangularMatrix:print()for ( int i = 0; i < sum; i+) cout << ti <

13、<""cout << en dl;return ;friend class ChainH ashTableNode;private :int value;Node *li nk;Node.cpp #i nclude "Node.h" using namespacestd;SparseMatrix.h #pragma once #include "Term.h" class SparseMatrix public :SparseMatrix( int row, int col);void transpose();int

14、 row, col; / 数组维数int sum; /元素个数int maxsum;/最多的元素个数Term *t; /存储的数组 ;lSparseMatrix.cpp#in elude "SparseMatrix.h"#in elude <iostream>using namespacestd;SparseMatrix :SparseMatrix( int r, int c) maxsum = r *c;t = new Termmaxsum;void SparseMatrix :transpose()Term *cur = new Termmaxsum;int

15、 *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+) 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+)delete t;t = cur;void SparseMatrix :Store( int x, int i, int j)tsum.value =x;tsum.row = i ;tsum.col = j ;sum+;returnvoid SparseMatrix :print()for ( int i = 0; i < sum; i+) cout << ti.value <<cout << en dl;return ; void SparseMatrix

17、 :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

18、= tsa.row;else if (tsa.row < b.tsb.row) curk.value = tsa.value; curk.row = tsa.row; curk.col = tsa.col;k+;sa+;k+;sb+;else if (tsa.col < tsb.col)elsesum = k;delete t; t = cur;return ;Term.h #pragma once class Term friend class SparseMatrix ;rivate :int col, row;int value;Term.cpp#in clude "

19、;Term.h"Tridiag on alMatrix.h#pragma onceclass TridiagonalMatrixpublic :TridiagonalMatrix( int size);void Store( int x, int i, int j); / 向矩阵里存储一个元素 int Retrieve( int i, int j);/返回矩阵中的一个元素void print();private :int n; /矩阵非0元素个数int *t; /用数组来存储矩阵； JTridiag on alMatrix.cpp#i nclude "Tridiago na

20、lMatrix.h"#in elude <iostream>using namespacestd;TridiagonalMatrix:TridiagonalMatrix( int size )n = size ;t = new int 3 * n - 2;void TridiagonalMatrix:Store( int x, int i, int j)if ( i <0 | j <0 | i >= n | j >= n)cout << "三对角矩阵行列输入错误“ vv i << “ “ vv j <<

21、 endl; return ;else if ( x = 0)cout << "三对角矩阵所添加的元素必须非零"<< endl;return ;else if (abs( i - j )>1)cout << "三对角矩阵添加元素位置错误"<< endl; return ;switch ( i - j)case -1:t3 * j - 1 = x;nt TridiagonalMatrix :Retrieve( int i, int j)if ( i <0 II j<0 II i >=

22、(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 <<I! I!.>cout << en dl; return ;Test.cpp#inelud

23、e <iostream>#inelude <cstring>#include <cstdlib>#include "TridiagonalMatrix.h"#include "LowerTriangularMatrix.h"#include "SparseMatrix.h"#include "HashTable.h"#include "ChainHashTable.h" using namespacestd;nt wei, num100100;void c()

24、int main()Qint k = 0, l = 0;/*三对角矩阵实验开始测试数据4103n-24c()；TM- >prin t();cout << "请输入要查询的元素的位置 "<< endl;cin >> k >> l;l = TM->Retrieve(k, l);cout << "查询结果："<< l << endl;cout vv "*"<< en dl;/*下三角矩阵实验开始测试数据410n*(n+1)/247 8

25、 9 -1*/if (numji != 0)cout << "请输入下三角矩阵维数及内容："<< endl;LTM->Store( numji, j, i);LTM->prin t();cout << "请输入要查询的元素的位置 "<< endl; cin >> k >> l;l = LTM->Retrieve(k, l);cout << "查询结果："<< l << endl;cout <<“*“

26、<< en dl;/*稀疏角矩阵实验开始 测试数据454 51 0 0 0 2 0 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 << "请输入稀疏矩阵的维数及内容："<< endl; cin >> k >> l;SparseMatrix *SM = new SparseMatrix (k, l);for ( int i = 0; i < k;

27、 i+)for (int j = 0; j < l; j+)cin >> n umij;if (numij)SM->Store( numij, i, j);cout << "稀疏矩阵为："；SM->pri nt();SM->tra nspose();cout << "转置后稀疏矩阵为：”；SM->pri nt();SM->tra nspose();cout << "重新转置后稀疏矩阵为：”；SM-> pri nt();cout << "矩阵相加

28、开始，请输入要使用的矩阵维数及内容："<< endl;cin >> k >> l;SparseMatrix *SM2 = new SparseMatrix (k, l);for ( int i = 0; i < k; i+)for (int j = 0; j < l; j+)cin >> n umij;if (numij)SM2->Store( numij, i, j);cout << "新矩阵为：”；SM2->prin t();SM->Add(*SM2);cout <<

29、"矩阵相加后为：”；SM->pri nt();cout vv "*"<< en dl;ci n. get();system( "pause");/*使用散列表设计实现一个字典，假设关键字为整数且D为961,在字典中插入随机产生的500个不同的整数，实现字典的建立和搜索操作。分别使用线性开型寻址和链表散列解决溢出*/k = 0; l = 0;cout << "随即建立关键字为961,500个元素的散列表"<< endl;HashTable *BT = new HashTable(961

30、);for ( int i = 0; i < 500;)int j = rand() % 64435 + 1;if (BT->Insert(j) i+;BT->pri nt();cout << "请输入要搜索的元素"<< endl;cin >> k;l = BT->Search(k);cout << "元素位置为："<< l << endl;cout << "输入要插入的元素"<< endl;cin >> k;BT->I nsert(k);BT->pri nt();cout << "实现溢岀处理，插入所插入元素 *2的元素"<< endl;BT- >ln sert(2 * k);BT-> pri nt();