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

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#include "ChainHashTableNode.h"usingnamespace std;classChainHashTablepublic :ChainHashTable( intdivisor);ChainHashTable();bool Insert(intk);bool Search( intk);void print();private:intd;C

3、hainHashTableNode *ht;ChainHashTableNode.cpp#include"ChainHashTable.h"#include <iostream>usingnamespace std;ChainHashTable :ChainHashTable(intdivisor)d =divisor;ht =new ChainHashTableNoded;boolChainHashTable :Insert(intk)intifj = k%d; (htj.Insert(k)returntrue ;else returnfalse ;voidC

4、hainHashTable :print()for ( inti = 0; i < d; i+)hti.print();ChainHashTableNode.h#pragma once#include "Node.h"classChainHashTableNodepublic :ChainHashTableNode();bool Insert(intk);bool Search( intk);void print();private:Node *first;ChainHashTableNode.cpp#include"ChainHashTableNode.h

5、"#include<iostream>usingnamespace std;ChainHashTableNode:ChainHashTableNode()first = 0;boolChainHashTableNode:Search(intk)if (first = 0) return Node *current = first; while (current) false ;if(current->value =k )returntrue ;current = current->link;if(current)if(current->value =k)

6、returntrue ;returnfalse ;boolChainHashTableNode:Insert(intk)if(Search(k)cout <<" 已经存在此元素 " << endl;returnfalse ;else Node *p =p->value =new Node();k;if(first = 0)first = p;returntrue ;elsep->link = first;first = p;returntrue ;voidChainHashTableNode:print()Node *current =

7、first;if(first)while (first)cout << first->value <<first = first->link;" " ;cout << endl;first = current;else cout << -1 << endl;HashTable.h#pragma onceclassHashTablepublic :HashTable( intdivisor);HashTable();intSearch( intk); / 搜索算法bool Insert(inte);voi

8、d print();private:inthSearch( intk);intd; / 除数int*ht;/ 桶，大小取决于 d就是除数是多少bool *empty; / 一维数组，用来存储第I 个桶是否存入了元素;HashTable.cpp#include"HashTable.h"#include <iostream>usingnamespace std;HashTable:HashTable(intdivisor)d =divisor;ht =new int d;empty =new bool d;for ( inti = 0; i < d; i+)e

9、mptyi =hti = 0;true ;HashTable:HashTable()delete ht;delete empty;intHashTable:hSearch(intk) /搜索值为K的元素intinti =j = i;k%d;doif(htj =j = (j + 1) % d;k | emptyj)returnj; while (j != i); return j;intHashTable:Search(intk) /搜索值为K的元素intb = hSearch(if(htb =k)k);returnb;return-1;boolHashTable:Insert(inte)int

10、ifb = hSearch( (emptyb)e);htb =e;emptyb =returntruefalse ;elseif(htb =e)cout <<" 已经存在此元素 " << endl;returnfalse ;elsecout <<" 表已经满了 " << endl;returnfalse ;voidHashTable:print()for ( inti = 0; i < 961; i+)cout << hti <<" " ;cout <

11、< endl;return ;LowerTriangularMatrix.h#pragma onceclassLowerTriangularMatrixpublic :LowerTriangularMatrix(void Store(intx,intintRetrieve(inti,void print();private:intsize);i,intj);/ 向矩阵里存储一个元素intj);/ 返回矩阵中的一个元素intn; / 矩阵维数intsum; / 矩阵非零元素个数int*t;/ 用数组来存储矩阵;LowerTriangularMatrix.cpp#include"L

12、owerTriangularMatrix.h"#include<iostream>usingnamespace std;LowerTriangularMatrix:LowerTriangularMatrix(intsize )n =size ;sum = n*(n + 1) / 2;t =new int sum;voidLowerTriangularMatrix:Store(intx ,inti ,intj )if( i <0 |j <0 |i >= n |j >= n)cout <<" 下三角矩阵行列输入错误" &

13、lt;<i <<" "<<j << endl;return ;elseif( x = 0)cout <<" 下三角所添加的元素必须非零" << endl;return ;elseif( i <j )cout <<" 下三角添加元素位置错误" << endl;return ;tsum - (n -j )*(n -j + 1) / 2) + (i -j ) =x;return ;intLowerTriangularMatrix:Retrieve

14、(inti ,intj )if( i <0 |j <0 |i >= (n - 1) |j >= (n - 1)cout <<" 三对角矩阵行列输入错误" << endl;return-1;elseif( i >=j )returntsum - (n -j )*(n -j + 1) / 2) + (i -j );else return0;voidLowerTriangularMatrix:print()for ( inti = 0; i < sum; i+)cout << ti <<"

15、; " ;cout << endl;return ;Node.h#pragma onceclassNodefriendclassChainHashTableNode;private:intvalue;Node *link;Node.cpp#include"Node.h"usingnamespace std;SparseMatrix.h#pragma once#include"Term.h"classSparseMatrixpublic:SparseMatrix(introw,intcol);voidtranspose();voidS

16、tore( intx,inti,intj); / 向矩阵里存储一个元素voidAdd( SparseMatrix&b); /两个稀疏矩阵相加voidprint();private:introw, col;/ 数组维数intsum; / 元素个数intmaxsum;/ 最多的元素个数Term *t;/ 存储的数组;SparseMatrix.cpp#include"SparseMatrix.h"#include<iostream>usingnamespace std;SparseMatrix:SparseMatrix(int r , int c )row =

17、r ;col =c;sum = 0;maxsum = r * c;t =new Termmaxsum;voidSparseMatrix:transpose()Term *cur =new Termmaxsum;int*ColSize =new intcol;int*RowNext = new introw;for(inti = 0; i < col; i+) ColSizei = 0;for(inti = 0; i < row; i+) RowNexti = 0;for(inti = 0; i < sum; i+) ColSizeti.col+;/ 表示每一列的非零元素个数R

18、owNext0 = 0;for(inti = 1; i < col; i+) RowNexti = RowNexti - 1 + ColSizei - 1;/ 表示新矩阵中每一行的矩阵的前面的矩阵的个数/ 进入转置操作for ( inti = 0; i < sum; i+)intj = RowNextti.col+;curj.value = ti.value;curj.col = ti.row;curj.row = ti.col;deletet;t = cur;voidSparseMatrix :Store(intx ,inti ,intj )tsum.value =x;tsum.

19、row =i ;tsum.col =j ;sum+;return ;voidSparseMatrix :print()for ( int i = 0; i < sum; i+) cout << ti.value <<" " ;cout << endl;return ;voidSparseMatrix :Add( SparseMatrix&b) / 两个稀疏矩阵相加if(col !=cout <<b.col | row !=b.row)" 两个矩阵行列不同无法相加" << endl;

20、return ;intsa = 0;intsb = 0;Term *cur =new Termmaxsum;intk = 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.value +b.tsb.value;k+;sa+;sb+;elseif(tsa.row <b.tsb.row)curk.value = tsa.value;curk.row = tsa.r

21、ow;curk.col = tsa.col;k+;sa+;elseif(tsa.row >b.tsb.row)curk.value =curk.row =curk.col =k+;b.tsb.value;b.tsb.row;b.tsb.col;sb+;elseif(tsa.col < tsb.col)curk.col = tsa.col;curk.row = tsa.row;curk.value = tsa.value;k+;sa+;elsecurk.value =curk.row =curk.col =k+;sb+;b.tsb.value;b.tsb.row;b.tsb.col;

22、sum = k;deletet;t = cur;return ;Term.h#pragma onceclassTermfriendclassSparseMatrix ;private:intcol, row;intvalue;Term.cpp#include"Term.h"TridiagonalMatrix.h#pragma onceclassTridiagonalMatrixpublic :TridiagonalMatrix(void Store(intx,intRetrieve(inti,void print();intsize);inti,intj);/ 向矩阵里存储

23、一个元素intj);/ 返回矩阵中的一个元素private:intn; / 矩阵非 0元素个数int*t;/ 用数组来存储矩阵;TridiagonalMatrix.cpp#include"TridiagonalMatrix.h"#include<iostream>usingnamespace std;TridiagonalMatrix:TridiagonalMatrix(intsize )n =size ;t =new int 3 * n - 2;voidTridiagonalMatrix:Store(intx,inti ,intj )if( i <0 |

24、j <0 |i >= n |j >= n)cout << " 三对角矩阵行列输入错误 " << i << " " << j << endl; return ;elseif( x = 0)cout <<" 三对角矩阵所添加的元素必须非零" << endl;return ;elseif(abs( i -j )>1)cout <<" 三对角矩阵添加元素位置错误" << endl;return

25、 ;switch( i -j )case -1:t3 *j - 1 =x;break ;case 0:t3 *j =x;break ;case 1:t3 *j + 1 =x;break ;return ;intTridiagonalMatrix:Retrieve(inti ,intj )if( i <0 |j <0 |i >= (n - 1) |j >= (n - 1)cout <<" 三对角矩阵行列输入错误" << endl;return-1;elseif(abs(i -j ) <= 1)returnt3 *j + (

26、i -j );else return0;voidTridiagonalMatrix:print()for(inti = 0; i < 3 * n - 2; i+)cout << ti <<" " ;cout << endl;return ;Test.cpp#include <iostream>#include <cstring>#include <cstdlib>#include "TridiagonalMatrix.h"#include "LowerTriangul

27、arMatrix.h"#include "SparseMatrix.h"#include "HashTable.h"#include "ChainHashTable.h"usingnamespace std;intwei, num100100;void c()for(int for(i = 0; i < wei; i+)intj = 0; j < wei; j+)cin >> numij;intmain()intk = 0, l = 0;/* 三对角矩阵实验开始测试数据 4103n-241200345

28、007890087*/cout <<" 请输入三对焦矩阵维数及内容：" << endl;cin >> wei;c();TridiagonalMatrix*TM =new TridiagonalMatrix(wei);for ( inti = 0; i < wei; i+)for ( intj = 0; j < wei; j+)if(numji != 0)TM->Store(numji, j, i);TM->print();cout <<" 请输入要查询的元素的位置" <<

29、 endl;cin >> k >> l;l = TM->Retrieve(k, l);cout <<" 查询结果： " << l << endl;cout <<"*"<< endl;/* 下三角矩阵实验开始测试数据 410n*(n+1)/24100023004560789-1*/cout <<" 请输入下三角矩阵维数及内容：" << endl;k = 0, l = 0;cin >> wei;c();LowerT

30、riangularMatrix*LTM =new LowerTriangularMatrixfor ( inti = 0; i < wei; i+)for ( intj = 0; j < wei; j+)if(numji != 0)LTM->Store(numji, j, i);(wei);LTM->print();cout <<" 请输入要查询的元素的位置" << endl;cin >> k >> l;l = LTM->Retrieve(k, l);cout <<" 查询结

31、果： " << l << endl;cout <<"*"<< endl;/* 稀疏角矩阵实验开始测试数据 4 54 5100020300040050067084 58076005004000302000190762080044008026709*/cout <<" 请输入稀疏矩阵的维数及内容：" << endl;cin >> k >> l;SparseMatrix*SM = new SparseMatrix (k, l);for ( inti = 0

32、; i < k; i+)for ( intj = 0; j < l; j+)cin >> numij;if(numij)SM->Store(numij, i, j);cout <<" 稀疏矩阵为：" ;SM->print();SM->transpose();cout <<" 转置后稀疏矩阵为：" ;SM->print();SM->transpose();cout <<" 重新转置后稀疏矩阵为：" ;SM->print();cout <

33、<" 矩阵相加开始，请输入要使用的矩阵维数及内容cin >> k >> l;SparseMatrix*SM2 =new SparseMatrix (k, l);for ( inti = 0; i < k; i+)for ( intj = 0; j < l; j+):" << endl;cin >> numij;if(numij)SM2->Store(numij, i, j);cout <<" 新矩阵为：" ;SM2->print();SM->Add(*SM2);cout <<" 矩阵相加后为：SM->print();" ;cout <<"*"cin.get();system( "pause" );<< endl;/*使用散列表设计实现一个字典，假设关键字为整数且D为 961，在字典中插入随机产生的500个不同的整数，实现字典的建立和搜索操作。分别使用线性开型寻址和链表散列解决溢出*/k = 0; l = 0;cout <<" 随即建立关键字为961,