数据结构实验报告_图的基本运算及飞机换乘次数最少问题

实验报告实验名称二叉树的基本操作及哈夫曼编码译码系统的实现一、问题描述1实验目的和要求A创建一棵二叉树，实现先序、中序和后序遍历一棵二叉树，计算二叉树结点个数等操作。B哈夫曼编码/译码系统。2实验任务能成功演示二叉树的有关运算，运算完毕后能成功释放二叉树所有结点占用的系统内存3实验内容A创建一棵二叉树；先序、中序和后序遍历这棵二叉树；计算二叉树结点个数B哈夫曼编码译码系统二程序设计三程序代码主函数INCLUDE“CREATEHFMTREEH“INCLUDEINCLUDEUSINGNAMESPACESTDVOIDMAINCOUT“HFMHFMNODEHTHFMCODEHCCHARS1000REPEAT1COUTCHOICECOUTNCOUTDATAICOUTWIHFMCREATEHFMTREEW,DATA,4GOTOREPEAT1IFCHOICET|CHOICETCOUTCHSICHIFCHBREAKINTLENGTHIOFSTREAMOUTF“TESTFILETXT“IFOUTFCOUTCLASSBINARYTREEPUBLICBINARYTREEROOTNULLBOOLISEMPTYCONSTVOIDCLEARBOOLROOTTVOIDMAKETREECONSTTVOIDMAKETREECONSTTVOIDBREAKTREETVOIDPREORDERVOIDVISITTVOIDINORDERVOIDVISITTVOIDPOSTORDERVOIDVISITTVOIDLEVALORDERINTSIZEPROTECTEDBTNODEROOTPRIVATEVOIDCLEARBTNODETVOIDPREORDERVOIDVISITTVOIDINORDERVOIDVISITTVOIDPOSTORDERVOIDVISITTVOIDLEVALORDERBTNODETINTSIZEBTNODETTEMPLATEBOOLBINARYTREEISEMPTYCONSTRETURNROOTNULLTEMPLATEVOIDBINARYTREECLEARBTNODETIFTIFTLCHILDCLEARTLCHILDIFTRCHILDCLEARTRCHILDDELETETTNULLTEMPLATEVOIDBINARYTREECLEARCLEARROOTTEMPLATEBOOLBINARYTREEROOTTRETURNTRUEELSERETURNFALSETEMPLATEVOIDBINARYTREEMAKETREECONSTTLEFTROOTRIGHTROOTNULLTEMPLATEVOIDBINARYTREEMAKETREECONSTTROOTNEWBTNODEX,Y,LEFTROOT,RIGHTROOTLEFTROOTRIGHTROOTNULLTEMPLATEVOIDBINARYTREEBREAKTREETLEFTROOTROOTLCHILDRIGHTROOTROOTRCHILDDELETEROOTROOTNULLTEMPLATEVOIDVISITTPREORDERVISIT,TLCHILDPREORDERVISIT,TRCHILDTEMPLATEVOIDBINARYTREEINORDERVOIDVISITTVISITTELEMENTINORDERVISIT,TRCHILDTEMPLATEVOIDBINARYTREEPOSTORDERVOIDVISITTPOSTORDERVISIT,TRCHILDVISITTELEMENTTEMPLATEVOIDBINARYTREELEVALORDERBTNODETSEQQUEUEQ100IFTRETURNQENQUEUETWHILEQISEMPTYTQDEQUEUECOUTELEMENTLCHILDQENQUEUETLCHILDIFTRCHILDQENQUEUETRCHILDCOUTVOIDBINARYTREELEVALORDERLEVALORDERROOTTEMPLATEINTBINARYTREESIZEBTNODETIFTRETURN0ELSERETURNSIZETLCHILDSIZETLCHILD1TEMPLATEINTBINARYTREESIZERETURNSIZEROOT二叉树结点类INCLUDETEMPLATESTRUCTBTNODEBTNODELCHILDRCHILDNULLBTNODECONSTTLCHILDRCHILDNULLBTNODECONSTTLCHILDLRCHILDRBTNODECONSTTWORDYLCHILDLRCHILDRTELEMENTTWORDBTNODELCHILD,RCHILD哈夫曼树类INCLUDE“BINARYTREEH“INCLUDESTRUCTHFMNODECHARWORDINTWEIGHTINTPARENTINTLCHILDINTRCHILDSTRUCTHFMCODEINTBIT10000INTSTARTINTWEIGHTTEMPLATECLASSHFMTREEPUBLICBINARYTREEPUBLICOPERATORTCONSTRETURNWEIGHTTGETWRETURNWEIGHTVOIDPUTWCONSTTVOIDSETNULLROOTNULLVOIDGRCODETW,CHARC,INTN,HFMNODEHT,HFMCODEHCVOIDENCODEHFMNODEHT,HFMCODEHC,INTCOUNT,CHARRECORD,CHARTRANVERSVOIDDECODEHFMNODEHT,INTCOUNT,CHARIN,CHARFOUTVOIDPRINTCHARINPRIVATETWEIGHTTEMPLATEVOIDHFMTREEGRCODETW,CHARC,INTN,HFMNODEHT,HFMCODEHCINTM1,M2,X1,X2CHARD1,D2INTI,JFORI0IVOIDHFMTREEENCODEHFMNODEHT,HFMCODEHC,INTCOUNT,CHARRECORD,CHARTRANVERSIFSTREAMINFILERECORDIFINFILECOUTVOIDHFMTREEDECODEHFMNODEHT,INTCOUNT,CHARIN,CHARFOUTINTI0CHARCH,BUFFER100/用来存放编码文件中的字符IFSTREAMINFILEINIFINCOUTVOIDHFMTREEPRINTCHARINIFSTREAMINFILEINIFINFILECOUTHFMTREECREATEHFMTREETW,CHARC,INTNPRIOQUEUEPQN/定义一个元素类型为HFMTREE的优先权队列HFMTREEX,Y,Z,ZEROFORINTI0ITEMPLATECLASSQUEUEPUBLICVIRTUALBOOLISEMPTYCONST0VIRTUALBOOLISFULLCONST0VIRTUALBOOLFRONTTVIRTUALBOOLENQUEUETX0VIRTUALTDEQUEUE0VIRTUALBOOLCLEAR0INCLUDE“QUEUEH“TEMPLATECLASSSEQQUEUEPUBLICQUEUEPUBLICSEQQUEUEINTMSIZESEQQUEUEDELETEQBOOLISEMPTYCONSTRETURNFRONTREARBOOLISFULLCONSTRETURNREAR1MAXSIZEFRONTBOOLFRONTTBOOLENQUEUETXTDEQUEUEBOOLCLEARFRONTREAR0RETURNTRUEPRIVATEINTFRONT,REARINTMAXSIZETQTEMPLATESEQQUEUESEQQUEUEINTMSIZEMAXSIZEMSIZEQNEWTMAXSIZEFRONTREAR0/在X中返回队头元素。操作成功返回TRUE,否则返回FALSETEMPLATEBOOLSEQQUEUEFRONTTPRIOQUEUEDELETEQBOOLISEMPTYCONSTRETURNN0BOOLISFULLCONSTRETURNNMAXSIZEVOIDAPPENDCONSTTVOIDSERVETPRIVATEVOIDADJUSTDOWNINTR,INTJVOIDADJUSTUPINTJTQINTN,MAXSIZETEMPLATEPRIOQUEUEPRIOQUEUEINTMSIZEMAXSIZEMSIZEQNEWTMAXSIZEN0/元素值为X的新元素入列TEMPLATEVOIDPRIOQUEUEADJUSTUPINTJINTIJTTEMPQIWHILEI0QNXADJUSTUPN1/在X中返回具有最高优先权的元素值，并从优先权中删除该元素；TEMPLATEVOIDPRIOQUEUEADJUSTDOWNINTR,INTJINTCHILD2R1TTEMPQRWHILE