2023年山東大學(xué)數(shù)據(jù)結(jié)構(gòu)實(shí)驗報告四

山東大學(xué)軟件工程學(xué)院數(shù)據(jù)結(jié)構(gòu)課程實(shí)驗報告學(xué)號：姓名：班級:軟件工程2023級2班實(shí)驗題目:矩陣和散列表實(shí)驗學(xué)時：實(shí)驗日期：2023.11.11實(shí)驗?zāi)康模赫莆仗厥饩仃嚭拖∈杈仃嚒Ｕ莆丈⒘斜砑捌鋺?yīng)用。硬件環(huán)境：實(shí)驗室軟件環(huán)境:VistualStudio2023實(shí)驗環(huán)節(jié)與內(nèi)容：實(shí)驗內(nèi)容：1、創(chuàng)建三對角矩陣類，采用按列映射方式，提供store和retrieve方法。2、創(chuàng)建下三角矩陣類，采用按列映射方式，提供store和retrieve方法。3、創(chuàng)建稀疏矩陣類，采用行主順序把稀疏矩陣映射到一維數(shù)組中，實(shí)現(xiàn)稀疏矩陣的轉(zhuǎn)置和兩個稀疏矩陣的加法操作。4、使用散列表設(shè)計實(shí)現(xiàn)一個字典，假設(shè)關(guān)鍵字為整數(shù)且D為961,在字典中插入隨機(jī)產(chǎn)生的500個不同的整數(shù)，實(shí)現(xiàn)字典的建立和搜索操作。分別使用線性開型尋址和鏈表散列解決溢出。代碼體：ChainllashTableNode.h#pragmaoncevoidSparseMatrix:：print(){。for(inti=0;i<sum；i++){3。cout<<tLi],value<<〃"；6}。cout<<end1;return;)voidSparseMatrix::Add(SparseMatrix&b)//兩個稀疏矩陣相加(if(co1!=b.co1Irow!=b.row){?cout<<〃兩個矩陣行列不同無法相加〃<<end1；。return;)intsa=0；intsb=0;Term*cur=newTerm[maxsum];intk=0;。while(sa<sum||sb<b.sum){。。if(t[sa].co1==b.t[sb].col&&t[sa].row==b.t[sb].row)O0{b。cur[k].col=t[sa].col;。cur[k].row=t[sa].row;3ocur[k].value=t[sa].value+b.t[sb].value;bbk++；。。。sa++;3sb++;)。eelseif(t[sa].row<b.t[sb].row)(。cur[k].value=t[sa].value;3cur[k].row=t[sa].row;。ocur[k].col=t[sa].col；OOOk++；bbsa++;。belseif(t[sa].row>b.t[sb].row)。{33cur[k].value=b.t[sb].value;ocur[k].row=b.t[sb].row；ecur[k],col=b?t[sb],col；bbbk++；b0sb++;06)b。elseif(t[sa].col<t[sb].co1){socur[k].col=t[sa].col；3cur[k].row=t[sa].row;。cur[k].value=t[saLvalue；ok++;3。sa++；O0)b。eIse(3ocur[k].value=b.t[sb].value;cur[k].row=b.t[sb].row;。ocur[kJ.col=b?t[sb].col;b0k++；bbSb++；)6)sum=k;de1etet;t=cur;。return;)Term.h#pragmaonceclassTerm{friendc1assSparseMatrix;private:3intcol,row;intva1ue；}；Term,cpp#include〃Term.h〃TridiagonalMatrix.h#pragmaonceclassTridiagonalMatrix(pub1ic:TridiagonalMatrix(intsize);。voidStore(intx,inti,intj);//向矩陣?yán)锎鎯σ粋€元素intRetrieve(inti,intj);//返[II矩陣中的一個元素voidprint();private：。intn;〃矩陣非0元素個數(shù)。int*t;〃用數(shù)組來存儲矩陣};TridiagonalMatrix.cpp#include"TridiagonaIMatrix.hz，#inelude<iostream>usingnamespacestd;Tridiagona1Matrix::TridiagonalMatrix(intsize){n=size；。t=newint[3*n—2]；)voidTridiagonalMatrix：：Store(intx,inti,intj(oif(i<0I|j<0||i>=n||j>=n)。{j<<endl;j<<endl;j<<endl;。cout<<〃三對角矩陣行列輸入錯誤〃<<i<<""?return;j<<endl;6)。elseif(x==0)(。cout<<〃三對角矩陣所添加的元素必須非零〃<<end1;oreturn；)e1seif(abs(i—j)>1)(。cout?”三對角矩陣添加元素位置錯誤〃<<endl;。。return；)3switch(i-j)。{case-1:。t[3*j-1]=x;obreak；case0:t[3*j]=x；break;case1:。t[3*j+1]=x;break;return;)intTridiagonaIMatrix：：Retrieve(inti,intj)(。if(i<0|Ij<0I|i>=(n-1)||j>=(n—1))。(bcout<<〃三對角矩陣行列輸入錯誤〃<<endl;return-1；。}。e1seif(abs(i-j)<=1){3breturnt[3*j+(i—j)];6}e1se(return0;voidTridiagonalMatrix::print(){for(inti=0;i<3*n-2;i++){cout<<t[i]<<";)。cout<<end1；return;)Test.cppinc1ude<iostream>include<cstring>#include<cstdlib>ttinclude〃TridiagonalMatrix.h〃include"LowerTriangularMatrix.hnincludez，SparseMatrix.h〃include，zHashTable,h"#include〃ChainllashTable.h〃usingnamespacestd；intwei,num[100][100];voidc()(。for(inti=0；i<wei;i++)for(intj=0;j<wei;j++)。cin〉>num[i][j];)intmain()intk0,1。/*三對角矩陣實(shí)驗開始測試數(shù)據(jù)4-10?3n-2。40120034500789o0087°*/。cout?”請輸入三對焦矩陣維數(shù)及內(nèi)容："?endl;cin>>wei;。c();。Tridiagona1Matrix*TM=newTridiagonalMatrix(wei);for(inti=0;i<wei;i++)。。for(intj=0;j<wei;j++)oeif(num[j][i]!=0)。TM->Store(numEj][i],j,i);。TM—>print();bcout<〈〃請輸入要查詢的元素的位置〃<<endl;cin>>k>>1;。1=TM->Retrieve(k,1)；bcout?”查詢結(jié)果：〃?1?endl；ocout<<"***********************************************”<<endl;/*下三角矩陣實(shí)驗開始測試數(shù)據(jù)4?10?n*(n+l)/24o10002300。4560789-1。cout?〃請輸入下三角矩陣維數(shù)及內(nèi)容："?endl;k=0,1=0;。cin>>wei;。c();。LowerTriangularMatrix*LTM=newLowerTriangularMatrix(wei);for(inti=0;i<wei;i++)。。for(intj=0;j<wei;j++)if(num[j][i]!=0)。。LTM—>Store(num[j][i],j,i);3LTM->print();cout<<〃請輸入要查詢的元素的位置〃?endl;。cin>>k>>1；1=LTM->Retrieve(k,1);。cout<<”查詢結(jié)果：〃<<1<<end1;<<endl;cout<<"***********************火***********************〃。/*稀疏角矩陣實(shí)驗開始測試數(shù)據(jù)45<<endl;451000203000o4005006708o4508076005004o00030o2000190762o08004o40080o26709*/。cout?〃請輸入稀疏矩陣的維數(shù)及內(nèi)容："?endl;。cin>>k?1;SparscMatrix*SM=newSparseMatrix(k,1);for(inti=0;i<k;i++)…for(intj=0;j<1;j++)(。。。cin>>num[i][j];。if(num[i][j])ooSM->Store(num[i][j],i,j);0)cout?”稀疏矩陣為：〃；。SM->print()；。SM->transpose();coutV〈〃轉(zhuǎn)置后稀疏矩陣為：";。SM—>print();SM->transpose();。cout<〈〃重新轉(zhuǎn)置后稀疏矩陣為：〃；SM->print();cout?〃矩陣相加開始，請輸入要使用的矩陣維數(shù)及內(nèi)容:〃?end1;ocin?k>>1;。SparseMatrix*SM2=newSparseMatrix(k,1);for(inti=0;i<k;i++)for(intj=0;j<1;j++)661cin>>num[i][j];bif(num[i][j])SM2->Store(num[i][j],i,j);cout?”新矩陣為：〃;bSM2->print();SM->Add(*SM2);。cout<<〃矩陣相加后為：〃；SM—>print();ocout<<"***********************************************〃<<endl;。cin.get();system("pause");。/*使用散列表設(shè)計實(shí)現(xiàn)一個字典，假設(shè)關(guān)鍵字為整數(shù)且D為961,在字典中插入隨機(jī)產(chǎn)生的500個不同的整數(shù)，實(shí)現(xiàn)字典的建立和搜索操作。分別使用線性開型尋址和鏈表散列解決溢出0*/k=0;1=0;cout?〃隨即建立關(guān)鍵字為961,500個元素的散列表〃?endl;HashTab1e*BT=newHashTable(961)；。for(inti=0;i<500;){intj=rand()%64435+1;if(BT->Insert(j))i++;)3BT->print();bcoutv<〃請輸入要搜索的元素〃?end1;cin?k;1=BT->Search(k)；。cout<<〃元素位置為："<<1?endl；。cout<<"輸入要插入的元素"<<endl；cin>>k;BT—>1nsert(k);。BT—>print();。cout?”實(shí)現(xiàn)溢出解決，插入所插入元素*2的元素〃*endl;。BT—>Insert(2*k);。BT->print();ocout<<*****************火******************************〃<vendl；system(〃pause〃)；/*鏈表散列解決溢出0*/Cout?〃鏈表散列解決溢出，關(guān)鍵字為50,元素個數(shù)100〃《end1；ChainHashTable*HT=newChainHashTable(50);for(inti=0;i<1001)0{bintj=rand()%9661+1;if(HT->Insert(j))oi++；00)b}HT->print()；。cout?〃輸入要插入的元素〃V<end1;。cin>>k;HT->Insert(k);HT->print();bCout<<〃實(shí)現(xiàn)溢出解決，插入所插入元素*2的元素"<<end1；IIT->Insert(2*k);IIT—>print();ocout<<〃***********************火*************火********火"<<endl；cin.get();system("pause");)實(shí)驗結(jié)果：

三C:\Users\qufub\Documents\VisualStudio2013\Projectebuexe789-14560230010000087078934501200---Iq刖44V主789-14560230010000087078934501200---Iq刖44V主DE、IK11自詢結(jié)果：4-丫-―丫一―——丫―――丫―?丫——丫―,,—丫―諳輸入下三角矩陣維數(shù)及內(nèi)容：4124735869-1卜青輸入要查詢的元素的位置聲詢結(jié)果：6請輸入稀疏矩陣的維數(shù)及內(nèi)容:45100020300040050搜狗拼音輸入法全：xeC:\Users\qufub\Document5\VisualStudio2013\Projectebuexe聲詢結(jié)果：6值輸入稀疏矩陣的維數(shù)及內(nèi)容：?4L10?4L104050306000700502008稀疏矩陣為：12345678'陡置后稀疏矩陣為：14］僮新轉(zhuǎn)置后稀疏矩陣為：矩陣相加開始，請輸入要使用的矩陣維數(shù)及內(nèi)容:4JL5054JL50500700060300401慚矩陣為：87654321矩陣相加后為：976284486279?~丫----——(----請按任意鍵繼續(xù)??.搜狗拼音輸入法全書結(jié)論分析與體會：矩陣在數(shù)學(xué)應(yīng)用的十分廣泛，他有各種各樣的分類例如稀疏矩陣，下三角矩陣等等，很是又去。高效而便捷,實(shí)際中發(fā)揮了很大的作用。操作原理也很簡樸。#include”ChainHashTab1eNode.h〃usingnamespacestd;classChainIIashTable{public：ChainIIashTable(intdivisor);3~ChainHashTable();boolInsert(intk);。boo1Search(intk)；。voidprint()；private:3intd;3ChainHashTab1eNode*ht;}；ChainHashTableNode.cpp#include〃ChainilashTable.h〃#include<iostream>usingnamespacestd;ChainHashTab1e::ChainHashTable(intdivisor)d=divisor；ht=newChainHashTabieNode[d];)boo1ChainllashTable::Insert(intk)intj=k%d;3if(ht[j].Insert(k))(returntrue；)3else{3。returnfa1se;3)}voidChainllashTable：:print()(。for(inti=0;i<d；i++)ht[i].print()；ChainHashTableNode.h#pragmaonce#inc1ude〃Node.h〃classChainHashTableNodepub1ic:3ChainHashTab1eNode();。boolInsert(intk);boo1Search(intk)；3voidprint()；private:Node*first;)；ChainHashTableNode.cpp#inc1ude〃ChainHashTab1eNode,h"#inc1ude<iostream>usingnamespacestd;ChainHashTab1eNode:：ChainllashTab1eNode()(。first=0;}boolChainHashTab1eNode:：Search(intk)i。if(first==0)returnfalse；Node*current=first;while(current)。{。if(current->value==k)O0{6returntrue;o)。。current=current—>1ink;if(current)6O(3bif(current->va1ue==k)000(b3returntrue；O0))6)。returnfalse；)boo1ChainHashTableNode：:Insert(intk)(if(Search(k))ocout<<〃已經(jīng)存在此元素〃<<end1;。returnfaIse;)e1se(匕Node*p=newNode()；。。p->value二k；。if(first==0)6(。first=p;3。returntrue；0)else(qp->link=first;first=p；。returntrue;00\voidChainllashTab1eNode::print()(Node"current=first;if(first)6(。。whi1e(first){。。。cout<<first->value<<"。first=first->link；0)cout<<end1;ofirst=current;)else{cout<<-1?endl；6})HashTab1e.h#pragmaonceclassHashTablepublie:。HashTab1e(intdivisor)；?HashTab1e()；intSearch(intk)；//搜索算法。boo1Insert(inte);。voidprint();private：inthSearch(intk);intd；//除數(shù)int*ht;//桶，大小取決于d就是除數(shù)是多少bool*empty;〃一維數(shù)組，用來存儲第I個桶是否存入了元素)；HashTable.cpp#ineludez/HashTable.hn#include<iostream>usingnamespacestd;IlashTable:：HashTable(intdivisor){。d二divisor;ht=newint[d];empty=newboo1[d];for(inti=0;i<d;i++){bempty[i]=true;ht[i]=0;)jHashTab1e：：^HashTab1e(){de1ete[]ht;3delete[]empty;)intHashTable：:hSearch(intk)//搜索值為K的元素{inti=k%d；intj=i；do{f(ht[j]==kI|empty[j])returnj;。j=(j+1)%d;。}while(j!=i)；returnj;intHashTable::Search(intk)〃搜索值為K的元素(。intb=hSearch(k);if(ht[b]==k)returnb;。returnT;)boolHashTable::Insert(inte){。intb=hSearch(e);。if(empty[b])(eht[b]=e;匕empty[b]=false；。returntrue;)eIseif(ht[b]==e)(cout<<〃已經(jīng)存在此元素〃<<endl；。。returnfalse；。)e1se(。。cout<<〃表已經(jīng)滿了"<<end1；oreturnfalse;))voidHashTable::print()(for(inti=0;i<961；i++){。cout<<ht[i]<<"〃；b}。cout<<endl;return;)LowerTriangu1arMatrix.h#pragmaonceclassLowerTriangu1arMatrix(pub1ic:。LowerTriangularMatrix(intsize);。voidStore(intx,inti,intj);〃向矩陣?yán)锎鎯σ粋€元素。intRetrieve(inti,intj);//返回矩陣中的一個元素voidprint();private:。intn;〃矩陣維數(shù)。intsum;//矩陣非零元素個數(shù)。int*t;〃用數(shù)組來存儲矩陣}；LowerTriangularMatrix.cpp#inelude"LowerTriangu1arMatrix.h〃#inelude<iostream>usingnamespacestd；LowerTriangu1arMatrix::LowerTriangularMatrix(intsize)(n=size;。sum=n*(n+1)/2；t=newint[sum];}voidLowerTriangularMatrix::Store(intx,inti,intj){。if(i<0||j<0||i>二n|Ij>=n)6{。coutv〈〃下三角矩陣行列輸入錯誤〃i?zzzz?j?endl;33return；6)。elseif(x==0){。cout<<〃下三角所添加的元素必須非零〃VVendl;33return;)。elseif(i<j){oocout<<〃下三角添加元素位置錯誤〃?endl;。。return;3)t[sum-((n-j)*(n-j+1)/2)+(i-j)]=x;。return;)intLowerTriangularMatrix::Retrieve(inti,intj){if(l<0||j<0|Ii>=(n-1)|Ij>=(n-1))6{…Cout?”三對角矩陣行列輸入錯誤〃v<endl;。。return-1;。}elseif(i〉=j)oreturnt[sum—((n-j)*(n-j+1)/2)+(i-j)];6)。else(return0;0}}voidLowerTriangularMatrix::print(){3for(inti=0;i<sum;i++){3cout?t[i]<<"；)cout<<end1;return;)Node,h#pragmaonceclassNode{friendclassChainllashTab1eNode;private:intvalue；Node*link;}；Node.cpp#inc1ude"Node.h〃usingna