2023年上海交大数据结构实验报告

《数据结构》实验报告说明：本软件在win764位系统测试通过,需要安装.ｎｅt3.5以上版本七、数制转换问题1.问题描述对于输入的任意一个非负十进制整数,输出与其等值的其他进制数(二进制、八进制或十六进制）。2.任务规定⑴建立模型，拟定存储结构;⑵对任意十进制数，实现进制转换问题。3.实验指导(1)实验类型：设计实验。本实验规定同学们针对“数制转换”这个经典的问题，应用栈的存储结构,自己设计一个方案，并上机实现。此实验的目的是培养学生对数据结构的简朴应用能力。(2)预备知识:栈的基本定义、栈的基本操作算法、栈的存储结构。(3)实现方法提醒:1)以十进制转换为八进制为例。将十进制数整除8,计算过程中得到的余数依次进栈,按出栈序列输出栈中的内容即为与输入的十进制数相应的八进制数。设Coｎverｓion函数执行数制转换的操作,对(１348)10转换为8进制的过程如下:NNｄiv８Nmod８134８1６8416８210２12５２022)设计数制转换的算法。４.实现方案方案描述:本方案采用Ｃ#语言实现,实现十进制与其他进制直接的转换实现代码:重要实现代码如下usingSystem;usiｎgSysｔｅm.Coｌleｃtions.Generic；ｕsingSysｔem．ComｐｏnｅntModel;usiｎgSysｔem.Ｄaｔa;usiｎgＳｙstem.Ｄrawing;usingSystem.Teｘｔ;uｓｉnｇＳystｅm．Wiｎdoｗs.Ｆｏｒms;namｅspａce进制转换器{ｐuｂliｃpartialｃｌaｓsMainFｒm：Ｆｏrm{publicＭａinFrｍ(){InitializeCoｍｐoｎenｔ(）;｝pｒivatevoｉdMainFrm＿Ｌｏad_１(oｂjeｃtsender,ＥveｎtArｇse）｛tｘtSｔart.Fｏｃus();}///<suｍmary＞/／/十进制转换为八进制/／/</sumｍaｒy>／//<paraｍname="sｅｎder"></paraｍ>//／<paramname=＂e"><／paｒａm＞priｖatevoidrａdｉo_ｄto_Click＿1(objｅctsender,EveｎtArgsｅ）｛txtEnd.Tｅxｔ="＂;if(txtＳtarｔ.Text．Length！=0){//TＯDO:十进制转为八进制。Iｎt32i;try{i=Coｎｖert.ＴoIｎt32(txtStart.Text．Tｒim（));lblTiｔｌｅ.Text＝"十进制转为八进制";txtEnd.Teｘt=Ｃonverｔ.TｏStｒｉｎg（i,8）；｝cａｔｃｈ｛ＭessａgeBox.Ｓｈow("请输入合法的十进制数＂,"提醒＂,MeｓsaｇeBoxBｕttｏnｓ.OK，MeｓsageBoxIcon．Waｒｎｉｎg);}}else{ＭessaｇeBoｘ．Show("请提供转换数据!＂,"提醒",MesｓageBoｘBuｔtｏns.ＯK,MessagｅBoxＩcon.Ｗａrning);｝tｘtStart.Ｆocus（)；}///<sumｍary＞／//十进制转换为十六进制///</ｓuｍmary>／//＜ｐａramnaｍe＝"sｅnｄer＂></ｐaｒam>/／/<ｐaramｎaｍe="e">＜/paｒaｍ>priｖａteｖoidｒadｉｏ_dth_Click(objectsendeｒ,EvenｔArｇse){tｘtEnｄ．Teｘt=＂";if（ｔxtSｔarｔ．Texｔ．Lｅnｇth！=0){／/TOＤＯ:十进制转换为十六进制。Int32i;ｔrｙ{ｉ＝Cｏnｖｅrt．ToＩｎt3２(ｔxtＳtａrt.Tｅxt．Tｒｉm()）;lbｌＴitle.Ｔext="十进制转换为十六进制＂;txｔEnd．Ｔext=Converｔ.ＴoString(i，16);}catch｛ＭeｓsageBoｘ．Shｏw("请输入合法的十进制数","提醒",MｅssａｇeBoxBuｔｔｏns.OＫ,MeｓsageＢoxIcｏn.Warｎinｇ）;}}elｓe{MesｓaｇeＢoｘ．Show("请提供转换数据!",＂提醒",MessagｅBoxＢuｔtonｓ．OＫ,MｅssaｇｅBoｘIcon.Wａrning);｝txtSｔarｔ．Ｆocus（);}///<suｍmary>//／十进制转换为二进制///</sｕmmary>／／／<pａraｍnaｍe="senｄeｒ＂></parａm＞/／/＜ｐaｒamnamｅ="e"＞</pａｒam>privatevoｉdradio_dｔb_Ｃlick（obｊｅｃｔｓｅnder,EｖeｎｔAｒｇse){ｔxｔEnd.Ｔext="";if(txｔStａrt.Ｔexｔ.Lengｔh！=0）｛//TOＤO:十进制转换为二进制。Iｎｔ32ｉ；try{ｉ=Coｎvert.ToＩnt3２（txtＳｔart.Texｔ.Tｒiｍ(）);lｂlTitlｅ.Text="十进制转换为二进制";ｔxtEnd.Teｘt=Conｖert．ToＳtring(ｉ,2)；}catch{MｅssageBox．Show("请输入合法的十进制数","提醒",MｅssageBoxBｕｔtons．ＯＫ,ＭessageBoxIcon.Ｗarｎiｎg)；｝}eｌsｅ{MessageＢox.Shoｗ("请提供转换数据!"，"提醒"，MesｓagｅBoｘBｕｔtonｓ.OＫ，ＭesｓageBｏｘIcon.Wａｒｎing);}txtＳtarｔ.Ｆocuｓ（）;}///<sumｍaｒy>/／/八进制到十进制/／／<／ｓummary＞//／<paｒamｎame＝"sｅnder"></paｒａm>///<ｐaramname=＂e"></ｐａrａm＞ｐｒivａｔｅｖoidradio_otd_Ｃlｉck(objecｔｓender,EveｎｔArｇsｅ)｛txtEnd.Tｅxt=""；if(txｔStart.Tｅｘt.Leｎgｔh!=0）｛//TODO:八进制到十进制。try{lblＴitｌe.Text=＂八进制到十进制";tｘｔEnd.Text=Convert.ToString(Coｎvert．ＴｏＩnt32（txtStart.Text.Tｒｉｍ（),8））；／/八进制转为十进制}cａｔch{MessａｇeBｏx.Show("请提供合法的八进制数","提醒",MeｓsａｇeＢoｘButtons.OK,MesｓagｅBoxIcon．Warniｎg)；｝｝eｌｓｅ{ＭｅsｓageBｏｘ.Ｓhow("请提供转换数据！"，"提醒",ＭessageBoxBｕttoｎs.OK,MesｓageBoxIcon．Warｎｉng)；}txtStaｒt.Foｃus();}//／＜summarｙ＞///十六进制到十进制/／/＜/summary＞///＜ｐaramｎaｍe=＂ｓeｎdｅr">＜/ｐaram>///＜paramｎame＝"e"></pａraｍ>priｖaｔevoiｄradio_ｈtd＿Cliｃk(ｏbｊecｔｓender,EvｅｎtArgsｅ)｛tｘｔEnd.Tｅxt=＂＂;ｉｆ(tｘtSｔart.Text．Leｎgth！=0){tｒy{//TODO:十六进制到十进制。lblＴitle．Text="十六进制到十进制";txｔEnd．Ｔext=Convｅrｔ.TｏStrinｇ(Convert.ＴｏＩｎｔ３2（ｔxtStart．Ｔeｘt,16))；}cａtcｈ{MessagｅBox.Show(＂请提供合法的十六进制数!","提醒",ＭessａgｅBoxButtons.OK,MeｓｓａgeBｏxIｃon.Warniｎg);}｝else{MesｓaｇeBox.Sｈoｗ（"请提供转换数据！",＂提醒＂，MessageBoxBuｔtons．OK,MessａｇｅBｏxＩcon.Waｒning)；｝txｔStart.Focus（);}///<summary>／//二进制到十进制/／/</sumｍarｙ>/／/<paramname="ｓｅnｄer"></ｐaram>／//<ｐａramｎaｍｅ="e＂></param>privatevoidｒadio_ｂtd_Cｌicｋ(objecｔsender,EｖentArgse){txtEｎｄ.Texｔ="";if（tｘtStart.Teｘt.Leｎgth!=０）{try{//TODO:二进制到十进制。lｂlTｉtlｅ.Ｔexｔ=＂二进制到十进制";txtEｎd.Text＝Convert.TｏStrinｇ（Ｃoｎvert.ToIｎｔ32（ｔxｔStarｔ.Teｘｔ,２)）;}catｃh｛MｅssageBｏx.Show("请提供合法的二进制数!＂,"提醒"，ＭessaｇeBoｘButtonｓ.OK,MesｓageBoxIｃoｎ．Warning）；}}else{ＭeｓsagｅBox.Ｓhow(＂请提供转换数据！","提醒",MessaｇeＢoxButtons.OK,ＭessａｇｅBoxIcon.Warning);}ｔxtStarｔ.Focｕs(）;｝ｐrivａtｅvoｉdreseｔ＿Clｉck(ｏbjeｃtsｅnder,EｖentArgse）{txtStａｒt．Text＝"";ｔxtEnd．Tｅｘt="";tｘtStart．Ｆｏcus（);}privaｔｅｖｏｉdclｏse_Clicｋ(objｅcｔsender，EvｅnｔAｒｇse）{this.Closｅ（);｝}}测试过程：不输入数据,软件会温馨提醒2．输入数据选择转换模式３.测试完毕,结果对的十四、Huffmaｎ编码1.问题描述设某编码系统共有个字符,使用频率分别为,设计一个不等长的编码方案，输出每个字符相应的编码,使得该编码系统的空间效率最佳。2．任务规定⑴掌握Huｆfｍａｎ树的概念、特点和存储结构；⑵掌握Hｕffman树的构造算法;⑶运用Ｈuｆｆmａｎ树解决编码问题。3.实验指导（1）实验类型：设计实验。本实验规定同学们针对“Huffman树”这个经典的问题，应用二叉树这种数据结构，自己设计一个解决方案，并上机实现。此实验目的是培养学生对数据结构的简朴应用能力。(２)预备知识：二叉树的定义、二叉树的基本操作算法。(3）实现方法提醒：1)以字符出现的次数为权值,个结点作为根结点分别构成棵二叉树；2)所有二叉树中选取两棵根结点权值最小的树作为左右子树构造一棵新二叉树，新二叉树根结点的权值为左右子树上根结点的权值之和，并删除原先的两棵二叉树;3）反复上述环节，直到只剩一棵二叉树为止。4）Hｕffｍan树的存储结构如下:sｔrｕｃt{uｎsｉgnｅdintweight；unsｉgnedintpaｒeｎt,lchiｌd,rchild;}HＴNode,＊HuffmａnTｒee;4.实现方案方案描述:本方案采用C＃语言实现数据的Huffmａn编码与解码实现代码：重要实现代码如下：ｕsｉngSysｔｅm;usingSｙｓｔeｍ．Coｌlecｔiｏns．Generic;usiｎｇＳystｅm．ComponentMｏdel；usｉngSysteｍ.Daｔa;usinｇＳysｔem．Drａwing;usingSystｅm.Teｘt；usiｎgＳysｔｅｍ.Wｉndows.Ｆormｓ;usingSyｓｔem.Collectioｎs．Speｃｉalized;ｎamesｐaceHｕffmaｎCodｅ{publicｐaｒtialclaｓsForm1：Fｏｒm{cｌａssNoｄe{pｕblicｃharcode;publicｕiｎｔｐrｉoｉｒry；publicＮodelｃｈiｌｄ;publicNｏｄerchｉlｄ;}publicＦorｍ1(){ＩniｔializeComponeｎｔ();}ｐrivateDiｃtionaｒｙ＜chａr，string>ｄｉｃｔｃoｄe=nｅwＤictionａrｙ<char,strｉng>();prｉｖateＮodehuffＴreｅ;prｉvaｔｅｉｎｔｃｏｍparｉsoｎNｏdｅ(Ｎoden１,Ｎｏden2){rｅtｕｒn(int)(n1.ｐrioirry-ｎ２.prioｉrｒy）；｝privateｓtｒｉngenｃode(strｉngstr)｛ｄicｔcoｄｅ．Clｅar()；hｕffＴree=ｎull;iｆ(striｎg．IsNuｌlOrEmpty(ｓtr)){ｒｅtuｒn"";}Dictionary<ｃhar，uｉｎｔ>prioｒｉtｙQueue=neｗＤictiｏnaｒy＜char,ｕint＞(）；for（intｉ=0;i＜str.Lengｔｈ；i++)｛if（priorityQｕeue．ContａｉｎsＫｅy（str［ｉ]）){prioriｔyQueue［str[ｉ］]+＋;}ｅlsｅ{priｏrityQueue.Adｄ(sｔｒ[i］,１);}｝List<Ｎoｄｅ＞listpｃ=nｅwＬisｔ<Ｎode＞()；ｆoreach(vａriｔeminprｉoｒｉtyQueｕe)｛ｌiｓtpc.Ａdd(ｎewNode(）{priｏirｒｙ=iｔem.Valｕｅ,lchiｌd＝ｎull，rｃｈild=null,ｃｏde=item.Key});}lｉｓtｐc．Sort(comparｉsoｎＮｏｄe）;whilｅ(liｓtpc.Cｏunt＞1）{Nodｅn＝ｎｅwNoｄｅ();n.ｐｒioｉrry＝liｓtpc［0]．pｒioirry+lisｔpc[1].prｉoｉrry;n.lchild=ｌistpc[0]；n.ｒchiｌd=listｐc[1];listpc．ＲemoveAt(０）;ｌisｔpｃ.RｅmoveAt（0);inｔｉndeｘ＝－1;ｆｏr(iｎti=０；i<ｌｉstpc.Ｃounｔ;ｉ++)｛ｉf(n.prioirrｙ＜=lｉstpc［i].pｒioiｒry)｛iｎｄｅx=ｉ；break;}｝if(iｎdex=＝-１){iｎdeｘ=lｉstｐc.Couｎt;}lｉstｐc.Iｎsｅrt(index,n);}strｉngencodｅsｔr=＂";vieｗＴree(ｌistpc[０],"");huffＴreｅ=ｌｉstpｃ[0]；foｒ(ｉnti＝0;ｉ＜ｓtr.Lenｇｔh；i++）{encodesｔr+=dｉｃｔcｏｄe[str［i］];｝reｔｕrnenｃｏｄｅsｔr；}pｒｉvatevｏidｖiｅｗTree(Noden，ｓtriｎgv){if(n．cｏde!=＇\0')｛dicｔcｏdｅ.Ａdd(ｎ．ｃｏdｅ,v）;}ｅlsｅ{if(n.lchiｌd！=ｎｕｌl){stringｖl＝v＋"0";viｅwＴｒee(n.ｌcｈiｌd，vl);}if（ｎ.ｒchiｌｄ!=nｕll)｛ｓtringvr＝ｖ+"1";viewTree(n.rｃhild,vr）;}｝}privatesｔrｉｎgdｅcodｅ(stringstr)｛Nｏderoｏt=huffTrｅe;stｒinｇｒesｕlｔ＝＂";for(iｎｔi=