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

《2023年山东大学数据结构实验报告四.docx》由会员分享，可在线阅读，更多相关《2023年山东大学数据结构实验报告四.docx（19页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、山东大学 软件工程 学院数据结构课程实验报告学号：姓名：班级:软件工程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、使用散列表设计实现

2、一个字典，假设关键字为整数且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 (c

3、o 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

4、 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 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

5、 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

6、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矩

7、阵中的一个元素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 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 alM

8、atrix： ： Sto r e (in t x, int i , int j (oif ( i 0 I | j =n | j =n)。j endl;j endl;。cou t 三对角矩阵行列输入错误 i ret u rn;6 )。else if (x =0 )(。co u t 三对角矩阵所添加的元素必须非零 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 =

9、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= (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

10、 - 2 ; i+) cou t t i ;)。c o ut end 1 ； ret urn;)Te s t. cp p# in c 1 ude# i nclude#includettinclud 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 w

11、e 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 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

12、wei; i+)。fo r (int j =0; j S tor e (num E j i, j , i );。TM pri n t ();b cout 请输入要查询的元素的位置 k 1;。1 = T M-R e trieve (k, 1)；b cout ”查询结果： 1 endl；o co u t *” 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 S t ore (num

13、j i, j, i);3 LTM-prin t ();cou t 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 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 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 ()

14、;cout V转置后稀疏矩阵为：;。SM print ();SM- t ranspose();。cou t 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 numi j;b i f (numi j)S M 2-Store(numi j, i, j);cout ”新矩阵为：;b SM 2 -print ();SM-Add (*

15、SM2);。cout 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 In s e r t(j) i+;)3 BT-prin

16、t ();b c out vSearch (k)；。cout 元素位置为： 1 e ndl；。cout 输入要插入的元素 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 = n

17、ew Cha i nH a s h Table (50);f o r (int i = 0; i I n s e r t (j)o i +；00)b HT- p r int ()；。co u t 输入要插入的元素 V k;HT- I nser t (k);HT-pri n t ();b C o ut 实现溢出解决，插入所插入元素*2的元素In s e r t ( 2 * k);IIT pr int();o cout * 火 *火*火 am oa* aL L m am aaL vL L L * via L L 1 L * L * * 1 L aoa-丫- -j - -j - - - - - -

18、- 丫一 丫 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

19、 -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 僮新转置后稀疏矩

20、阵为：矩阵相加开始，请输入要使用的矩阵维数及内容: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 -

21、 - - 请按任意键继续.搜狗拼音输入法全书结论分析与体会：矩阵在数学应用的十分广泛，他有各种各样的分类例如稀疏矩阵，下三角矩阵等等，很是又 去。高效而便捷,实际中发挥了很大的作用。操作原理也很简朴。#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

22、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 deus 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 nl

23、la 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

24、: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 using n a mespace std;ChainHas h Ta b 1 e Node: ： Chainllas h T a b 1 e Node

25、() (。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

26、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 已经存在此元素 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 =

27、 f ir s t;if ( f ir s t)6 (。w h i 1 e (firs t )。cout val u e 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

28、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 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

29、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 H

30、as 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(。co

31、ut 表已经满了 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 S

32、tore (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 using names pace s td；Low e r Triang u 1 ar Mat r i

33、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 (i0 | | j 二 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;)。el

34、s 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 (l0 | | j= (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

35、 + 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

36、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 ();

37、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 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;)