2023年山东大学数据结构实验报告四.docx

山东大学 软件工程 学院数据结构课程实验报告学号：姓名：班级:软件工程2023级2班实验题目:矩阵和散列表实验学时：实验日期：20 2 3. 1 1.11实验目的：掌握特殊矩阵和稀疏矩阵。掌握散列表及其应用。硬件环境：实验室软件环境:Vi st ual Studio 2023实验环节与内容：实验内容：1、创建三对角矩阵类，采用按列映射方式，提供store和retrie v e方法。2、创建下三角矩阵类，采用按列映射方式，提供sto r e和r e t rieve方法。3、创建稀疏矩阵类，采用行主顺序把稀疏矩阵映射到一维数组中，实现稀疏矩阵的转置和 两个稀疏矩阵的加法操作。4、使用散列表设计实现一个字典，假设关键字为整数且D为961,在字典中插入随机产 生的500个不同的整数，实现字典的建立和搜索操作。分别使用线性开型寻址和链表散 列解决溢出。代码体：Cha inlla s hTableNode. h#p r agma oncevoid SparseMa t r i x: ： print () 。f or (int i = 0; i < sum； i+) 3。cout << t Li, v alue << "；6 。cou t << e n d 1;ret urn;)void Spar seM a tri x : Ad d ( S pars e Ma t rix &b)/ / 两个稀疏矩阵相加 (if (co 1!= b. co 1 I row != b. row) » cou t << 两个矩阵行列不同无法相加 << en d 1；。ret urn;)i n t sa = 0；int sb = 0;T e rm *cur = new Term maxsum;int k = 0 ;。whil e (sa < sum | | sb < b. s um) 。i f (t sa. c o 1 = b. t sb . col&&t sa. r o w = b. t sb . row)O 0b 。 cur k. c ol = tsa. col;。 c u r k. row = ts a . row ;3 o c ur k. v a lu e = t sa. v alu e + b . t s b . value;b b k+；。s a +;3 s b +;)。e else if (t s a . r ow < b.t sb. row) (。curk. valu e = t s a .valu e;3 curk. row = tsa. row;。 o cu r k.col = t s a .col；OOO k+；b b sa+;。b else if (tsa. row > b. t s b. r o w) 。3 3 cu r k . v alue = b. t sb. valu e ;o cur k . row = b. t s b . row；e c u rk, c ol = b t sb, c ol；b b b k+ ；b 0 s b+;06)b 。 el s e if (t s a . col < t s b . c o 1)so cur k. c ol = t sa . col；3 cur k. r ow = t s a .row;。cu r k . value = t saL value；o k+;3 。 sa+；O 0)b 。 e Ise(3 o c ur k. valu e = b.t s b . v alue; cur k . row = b. t s b . r ow;。o cur kJ. col = b t sb. col;b0 k+；bb Sb+；)6 )s u m = k ;d e 1 e t e t ;t = c ur;。re t ur n ;)T e rm. h#p r a g ma on c ec la s s T e r mf r iend c 1 ass Spar s eMatr i x ;p rivate:3 i nt col, row;in t v a 1 ue；Term, c p p#in c lude T e rm. hTridiagonalMa t r i x . h#p r agma onceclass T r idiagonalMatr i x(p ub 1 i c:T r id i ag o n alMatrix (in t size);。void S t o r e( i nt x , int i, in t j ) ;/ 向矩阵里存储一个元素 int Retrieve(int i,int j) ; / /返II矩阵中的一个元素void pr i nt ();pri v at e ：。int n;矩阵非0元素个数。int *t; 用数组来存储矩阵;T r id i a go n alM a trix. cp p#in c lude "Tridi a g on a IMatrix. hz，#i n elude <i o stream>usin g names p ace s t d ;Tr i diag o na 1 Ma t rix: :Tridiago n al Ma t rix (in t size) n = s i ze；。t = n e w i n t 3 * n 2；)v oid T ri d ia g o n alMatrix： ： Sto r e (in t x, int i , int j (oif ( i <0 I | j <0 |i>=n | j >=n)。j << endl;j << endl;。cou t << 三对角矩阵行列输入错误 << i << " " « ret u rn;6 )。else if (x =0 )(。co u t << 三对角矩阵所添加的元素必须非零 << end 1 ;o re t ur n ；)e 1 se if (abs( i j ) >1)(。cout « ”三对角矩阵添加元素位置错误 << endl;。retu r n；)3 switch ( i - j )。c a se -1:。t3 * j - 1 = x;o b re a k；cas e 0 :t 3 * j = x；break;case 1:。t3 * j + 1 = x;b re a k;return;)i n t Tri d i a gon a IMa t r ix： ： R e t r ieve (int i, int j)(。i f ( i <0 | I j<0 I | i >= (n - 1) | j >= (n 1)。(b cout << 三对角矩阵行列输入错误 << endl;retu r n -1；。e 1 s e if ( a b s (i - j) <= 1)3 b ret u rn t3*j+(i j);6 e 1 s e (re t u r n 0;void Tri d i a g onalMat r i x: :print ()for (int i = 0;i <3* n - 2 ; i+) cou t << t i <<")。c o ut << end 1 ； ret urn;)Te s t. cp p# in c 1 ude<io s tr e a m># i nclude< c string>#include<cstdlib>ttinclud e Tr i di ago n alM a tri x . h # in c lude " Low e rT r iangul a rMatr i x. h n# i n c ludez，SparseMatrix. h# i n clu d e，zHas h Table, h "#i n clud e Cha i nllashT a ble. husin g name spac e s td；i nt we i , n um100 1 00;v o i d c()(。for ( i nt i = 0 ； i < wei; i+) fo r (i n t j = 0;j < wei; j+)。ci n> numi j;)int main ()int k0, 1。/*三对角矩阵实验开始测试数据4-103n-2。40 1 2 0 03 4 5 00 7 8 9o 0 0 8 7° * /。cout « ”请输入三对焦矩阵维数及内容：" « endl;cin >> wei;。c();。Tridi a gona 1 Ma t ri x *TM = n e w Tridia gon alM a t r i x ( wei);for (int i = 0; i < wei; i+)。fo r (int j =0; j < wei; j + +)o e i f (n u mj i != 0)。TM-> S tor e (num E j i, j , i );。TM >pri n t ();b cout <请输入要查询的元素的位置 << e ndl;c i n >> k >> 1;。1 = T M->R e trieve (k, 1)；b cout « ”查询结果： « 1« endl；o co u t < < "*” << e ndl;/*下三角矩阵实验开始测试数据41 0n*(n+l) / 24o 1 0 0 02 3 0 0。4 5 6 07 8 9 - 1。cout « 请输入下三角矩阵维数及内容："« endl;k = 0 , 1=0;。cin >> wei;。c ();。Lowe rTri a ngularM a trix *LTM = n e w LowerTri a ngularMatri x (w e i);f or (inti = 0; i< wei; i + + )。for (int j = 0; j < we i ; j+)if (n umj i != 0)。LT M > S t ore (num j i, j, i);3 LTM->prin t ();cou t << 请输入要查询的元素的位置 « e ndl;。cin >> k >> 1；1 = LTM->Re t r i e v e( k , 1);。c o ut << ”查询结果： << 1 << e n d 1;<< endl;co u t << " * * * * * * * * 火 * * * * * * *。/*稀疏角矩阵实验开始 测试数据4 54 51 0 0 0 20 3 0 0 0o 4 0 0 5 00 6 7 0 8o 4 50 8 0 7 6 00 5 0 0 4o 0 0 0 3 0o 2 0 0 0 19 0 7 6 2o 0 8 0 0 4o 4 0 0 8 0o 2 6 7 0 9*/ 。cout « 请输入稀疏矩阵的维数及内容：" « endl;。cin >> k »1 ;SparscMatrix *SM = new Spa rseMatri x (k,1);f or (in t i = 0; i < k; i+)f or (i n t j = 0; j < 1; j +)(。ci n >> n umi j;。if (num i j)o o SM->Store(numi j , i, j);0 )cout «”稀疏矩阵为：；。SM->p r int ()；。SM->tra n spose ();cout V转置后稀疏矩阵为："。SM >print ();SM-> t ranspose();。cou t <重新转置后稀疏矩阵为：；SM->pri n t ();c o u t « 矩阵相加开始，请输入要使用的矩阵维数及内容: « end 1 ;o c i n » k >> 1 ;。Spa rseM a t ri x *SM2 = n ew SparseMatrix (k,1 );fo r (in t i = 0; i < k; i+ + ) for (int j = 0; j < 1 ; j+)661ci n >> numi j;b i f (numi j)S M 2->Store(numi j, i, j);cout « ”新矩阵为：;b SM 2 ->print ();SM->Add (*SM2);。cout <<矩阵相加后为：；SM >pr i nt ();o cout << "* << e ndl;。ci n . g e t ();sy s t e m ("pause");。/*使用散列表设计实现一个字典，假设关键字为整数且D为9 61,在字典中插入随机产生的5 00个不同的整数，实 现字典的建立和搜索操作。分别使用线性开型寻址和链表散列解决溢出0*/k = 0 ; 1 = 0;cout « 随即建立关键字为9 6 1,500个元素的散列表 « endl;HashTab 1 e *BT = n e w Has h Table(961)；。for (int i = 0; i < 500;)int j = rand () % 644 3 5 + 1 ;if (BT->In s e r t(j) i+;)3 BT->print ();b c out v< 请输入要搜索的元素 « e n d 1;cin » k ;1 = BT->Search (k)；。cout << 元素位置为："<< 1 « e ndl；。cout << "输入要插入的元素"<< endl；ci n >> k ;BT >1 n sert ( k );。B T >pri n t ();。cout « ”实现溢出解决，插入所插入元素*2的元素* endl;。B T >Insert ( 2 * k);。BT->pri n t ();o cout <<* * 火 * * <v e n dl ；s y s t e m( p au s e )；/ *链表散列解决溢出0*/C out « 链表散列解决溢出，关键字为5 0,元素个数1 0 0 end 1 ；Chai n Hash T a ble * HT = new Cha i nH a s h Table (50);f o r (int i = 0; i < 10 0 1)0 b i nt j = ran d () %9 66 1 + 1;if (HT->I n s e r t (j)o i +；00)b HT-> p r int ()；。co u t « 输入要插入的元素 V< e n d 1;。ci n >> k;HT-> I nser t (k);HT->pri n t ();b C o ut << 实现溢出解决，插入所插入元素*2的元素"<< e n d 1； IIT->In s e r t ( 2 * k);IIT >pr int();o cout << * 火 *火*火" << e ndl； c in. get ();s y s t em ("pause ");)实验结果：三C:UsersqufubDocumentsVisual Studio 2013Projectebuexe7 8 9 -14 5 6 02 3 0 010 0 00 0 8 70 7 8 93 4 5 01 2 0 0-Iq刖 44V 主DE 、IK1324758897 请输入要查询的元素的位置11自询结果：4>>a>m oa* » aL » «L m a>m aaL vL » «L « «L <* via «L «« «L « 1 » «L * »L * * 1 «L ao«a-丫- -j - -j - - - - - - - 丫一 丫 j - I , 丫 j ,丫 丫 , J 丫 i J , J ,谙输入下三角矩阵维数及内容：41 24735869 -1卜青输入要查询的元素的位置声询结果：6-j - -j - -j - - y - -j - - - -j - - - - - - - - - - - - - - - J - - - - - - - - - - - - - - - - -请输入稀疏矩阵的维数及内容:4 51 0 0 0 20 3 0 0 04 0 0 5 0搜狗拼音输入法全：xeC:UsersqufubDocument5Visual Studio 2013Projectebue声询结果：6-L*-j » -j - -y - -j - j - -j - -j - -j - - y - -y - -j - -j - -j - -j - -j - -j - -j - -j - -j - -j - -j - -j - -j - -j - «j - -j - -j - -j - -j - -j - -y - «j - - - - -j -j - - j - j - -j - -j - -j - j - - j - - y » j -j - -j -值输入稀疏矩阵的维数及内容：? 4L 104050306000700502008稀疏矩阵为：1 2 3 4 5 6 7 8'陡置后稀疏矩阵为：1 4 僮新转置后稀疏矩阵为：矩阵相加开始，请输入要使用的矩阵维数及内容:4JL50500700060300401惭矩阵为：8 7 6 5 4 3 2 1矩阵相加后为：976284486279- 1 1 11 1 1 1 11 1 1 1 1 1 1 0 1 1 1 1 1 1 1 11 1 1 1 - 1 1 1 111« 1 - 1 1 1 1 1 I 1 1 1 1 1 - 1 1-I - I - I- - - - - - - - j - - I - - - - - 1 丫- - - ( - - - j - - - - - - I - j - - j - - - - « - j - y - - ( * - - y - - - 请按任意键继续.搜狗拼音输入法全书结论分析与体会：矩阵在数学应用的十分广泛，他有各种各样的分类例如稀疏矩阵，下三角矩阵等等，很是又 去。高效而便捷,实际中发挥了很大的作用。操作原理也很简朴。#i n c lud e ” Cha inHa s hTab 1 eN o de. h u s ing n a mes p ace std;class Ch a inIIash T a blepubli c ：Ch a inIIashTable(in t d i visor);3 ChainHas h Table ();b ool In s er t ( i nt k);。b oo 1 Sear c h (int k )；。voi d print ()；pri v a t e :3 int d;3 Cha i n HashTa b 1 eNode *ht;；ChainHashTableNod e . cpp# i nclude C h a i nil a s hTable. h#incl u de< i o s t r e am>us i ng nam e spa c e s t d ;ChainHashTa b1e :Cha i nHashTable(int divi s or)d = diviso r ；h t = new Ch a i n Has h Tabi eNode d;)b o o 1 Ch a i nlla s hT able: Inse r t (in t k)int j = k% d ;3 i f ( h t j. In s ert (k) ( retur n true； )3 else 3。ret u rn f a 1 se;3 )vo i d Ch a i nlla s hTable： : print ()(。for (int i = 0; i < d； i +)ht i. pr i n t ()；ChainHashTableN ode. h #p r agma once#inc 1 udeN o de. hclass Ch a i nHash T a bleNode pub 1 i c:3 C h a i nH a shTab 1 eN o d e ();。b ool Ins ert (int k);bo o 1 Sea r c h(int k)；3 void pr i nt ()； p r i v at e :Node * firs t ;)；Chai n Hash T a bl eNod e . c p p# i n c 1 ude C ha i nHa s h T a b 1 eNode, h "#inc 1 ude <i o stream> using n a mespace std;ChainHas h Ta b 1 e Node: ： Chainllas h T a b 1 e Node () (。f i rs t = 0;bool Cha inHa s hTa b 1 e N ode: ： S earch (int k) i。if ( f irst = 0) return fals e ；Nod e * c u rrent = f i r s t ; while (cur rent) 。 。 i f (cur r ent->v a lue = k) O 06 r eturn tru e ;o )。cur r ent = cu r r ent >1 ink; if (curre nt)6 O (3 b if (cu r r e n t->v a 1 u e = k) 000(b 3 return t r ue；O0)6 )。re t u r n false；)bo o 1 ChainHa s hTableNode： : Insert (in t k ) (i f (Search ( k )o c o ut << 已经存在此元素 << en d 1;。 re t ur n f a Ise;)e 1 se (匕 Node *p = new N o de ()；。p ->v a lue 二 k；。 if (first = 0)6 (。f i rs t = p;3。re t ur n true；0)el s e(。 q p->li n k = first;first = p；。retu r n true;00voi d Chai nllashTab 1 eNode: :pri n t () (No d e "current = f ir s t;if ( f ir s t)6 (。w h i 1 e (firs t )。cout << firs t ->val u e << "。f irst = f irst->lin k ；0 )co u t << end 1 ;o f i rst = c urren t ;)el s e cout << -1 « e n dl；6 )HashTab 1 e . h# p ragm a on c ecla s s Hash T able pu b lie:。Ha s h T ab 1 e ( i n t divis o r)；HashTab 1 e ()；i n t S e ar c h(int k) ； / /搜索算法。boo 1 Inser t (in t e);。void print ();private：i n t hSearch(in t k);in t d； /除数int *h t ;/桶，大小取决于d就是除数是多少b ool *emp t y ;一维数组，用来存储第I个桶是否存入了元素 )；Has h T a ble. cpp#i n elude z/ HashTable. h n#incl u d e <iost r e a m>using namespace s t d;Ila s hTable: ： Has h Tabl e ( i n t d ivisor)。d 二 divis o r;ht = n ew int d;emp t y = new bo o 1 d ;for ( i nt i = 0; i < d; i + + )b em p t y i = tr u e;h t i = 0;)jHashTab 1 e： ： HashTa b 1 e ()d e 1 e t e ht;3 del e t e e mpt y ;)int HashT a b le： :h S ea r ch(int k) / / 搜索值为K的元素int i = k%d；int j = i ；d o f (htj = k I | e mpty j ) retur n j;。 j =(j + 1)% d;。 while (j != i)；r e turn j;i n t Has h T a ble: : S earch (i n t k)搜索值为K的元素(。 i nt b = hSea r ch(k);if (ht b = k) r e t u rn b;。r e tur n T ;)bool Hash T abl e :Insert(int e)。i nt b = h S e a r c h(e);。if (em p ty b)(e htb = e;匕 emp t yb = fals e ；。 ret urn true;)e Ise if (ht b = e )(c o u t << 已经存在此元素 << endl；。retur n f alse；。)e 1 se(。cout << 表已经满了 " << en d 1；o r e turn false;)voi d Hash Table: p r in t ()(for ( i n t i = 0; i < 9 61；i + + ) 。 cout << hti << " ；b 。cout << e n dl;r e turn;)L o wer T r i ang u 1 arM a tr i x. h#pr a g m a oncecla s s Low e r T ria n g u 1 a r Ma t r i x(pu b 1 i c:。L owerT r iangularM a tr i x ( i n t si z e );。vo i d Store (int x, int i, int j);向矩阵里存储一个元素。i nt Retriev e (int i, in t j) ; / /返回矩阵中的一个元素void pr i n t ();p rivate:。int n ;矩阵维数。in t s um ; / /矩阵非零元素个数。int *t;用数组来存储矩阵；Low er T ria n gul a rMatrix. cp p#i n elude " LowerTriangu1arM a tr i x. h# i n elude <iostr e am>using names pace s td；Low e r Triang u 1 ar Mat r i x : : Lower T ri a ngularMatr i x ( i nt s ize)(n = s i ze;。sum = n*(n + 1) / 2；t = new in t sum;void LowerTriangu larMa t rix:S t o r e(int x, int i , int j)。i f (i<0 | | j <0 | | i >二 n | I j >= n)6 。 cout v下三角矩阵行列输入错误i « zz zz « j « endl;3 3 r eturn；6 )。el s e if (x = 0)。cout << 下三角所添加的元素必须非零 VV endl;3 3 ret urn;)。els e if ( i <j)o o cout << 下三角添加元素位置错误 « e ndl;。r etu r n;3 )t sum - ( (n - j)*(n - j + 1)/2)+ (i - j) = x;。return;)int L o werTriangularMat r ix: :Retr i eve (int i, int j )if (l<0 | | j<0 | I i >= (n - 1) | I j >= (n - 1)6 C out « ”三对角矩阵行列输入错误 v< endl;。re t urn - 1 ;。else i f (i=j)o r e t u r n t s u m (n - j) * (n - j + 1) / 2) +(i - j);6 )。else( return 0;0 vo i d Low e rT r i a ngula r Matr i x:print () 3 fo r (int i = 0; i < s um; i+)3 co u t « ti <<" ；)c o u t << e n d 1; return;)Node, h#pr a g ma on c e cla s s No d e f r iend c lass Chai nllashT a b 1 eNode;p rivate:int v a lue； Node *lin k ;；No d e . cpp#inc 1 u d e "Node. h using nam e s p a c e std; Spa r seMatrix. h #pra g m a once# i n c 1 ud e，?T e rm. h class Spar seMa t ri x ( publ i c:S p arseM a tri x (int r ow, int c ol); void tr a n spose ();void S t ore (int x, int i, int j)； 向矩阵里存储一个元素 v o id Ad d (Spa r seMa t r i x &b); 两个稀疏矩阵相加。void pr i n t (); p r i vate：。i n t row, col;/ / 数组维数。int sum； / /元素个数i n t m a x sum; / /最多的元素个数 T e rm *t； / /存储的数组;S parseMatr i x. c p p ttinclu d e "Spars e Matr i x. h Sinclude <i o st r e a m> using name s pace std;Spa r s e M a trix: : S pa r s eMatr i x (int r, in t c)row = r;b c ol = c;。sum = 0;3 maxsum=rc;。 t = new Termm a x s um;)