还剩10页未读,继续阅读
本资源只提供10页预览,全部文档请下载后查看!喜欢就下载吧,查找使用更方便
文本内容:
数据结构实验报告一一实验六〃if!find//coutv“空”;classDBSTree{public:DBSTree{root=0;};BinaryTreeNode*root;DBSTreeBSInitializeinta[]int1en;DBSTreeBSInsertconstinte;};DBSTreeDBSTree:BSInsertconstinte{BinaryTreeNode*p=root*Pp=0;whilep{pP=p;ifep-datap=p—LeftChild;elseifep-datap=p—RightChild;BinaryTreeNode*r=newBinaryTreeNodee;ifroot{ifepp-datapp-LeftChild=r;eIsepp-RightChi1d=r;}e1seroot=r;return*this;DBSTreeDBSTreeBSInitia1izeinta[]int1en{forinti=0;i1en;i++BSInserta[i];return*this;voidmain{MaxHeapmaxHeap;DBSTreebstree;intsnselAlen;char**codeA;int*IntA*w;coutVv”输入最大堆元素个数”;int1en;cin»len;int*a=newint[len];forinti=0;ilen;i++{cout«输入第Vi+1个元素endl;cin»a[i];maxHeap.Initia1izealen;cout«!最大堆操作n«endl;cout«
0.堆排序vVend1;maxHeap.HeapSortalen;forinth=0;hlen;h++cout«a[h]«nn;coutendl;cout«”
1.初始化层次遍历输出最大堆end1;TravelmaxHeap.root;coutendl;coutv”前序遍历输出最大堆n”;PrOrdermaxHeaproot;coutendl;coutv”
2.插入整数元素”《endl;cin»s;maxHeap.Inserts;coutv”层次遍历输出最大堆\n”;Travelmaxlleap.root;cout«end1;cout«n前序遍历输出最大堆\n”;Pr0rdermaxHeap.root;coutendl;coutvv”
3.删除最大元素\n”;maxHeap.De1eteMaxs;coutv”层次遍历输出最大堆\n”;TravelmaxHeap.root;coutendl;//////////nn/////mu///////////////cout«”Huffman操作”;cout”输入元素个数vVend1;cin»A1en;IntA=newint[A1en];w=newint[Alen];forn=0;nAlen;n++{coutH\n输入第n+l”个元素\n”;cinIntA[n];cout«n\n输入相应权值\n”;cin»w[n];}HuffmanCodingcodeAwIntAlen;HTEcodecodeAwIntAA1enalen;coutend1;/m////////m///////mu/////////////mcout«”二叉搜索树层次遍历〈Vend1;cou输入二叉搜索树元素个数”;intbs1en;cin»bs1en;int*b=newint[bs1en];forintj=0;jbslen;j++{cout«输入第j+1vv”个元素Vend1;cinb[j];}bstree.BSInitia1izebbslen;cout”前序遍历输出二叉搜索树Hendl;PrOrderbstree.root;cout«endl;cout«n中序遍历输出二叉搜索树«endl;InOrderbstree.root;coutend1;coutv”层次遍历输出二叉搜索树Vendl;Travelbstree.root;coutendl;实验结果:BinaryTreeNodeconstinteBinaryTreeNode*1BinaryTreeNode*rdata=e;LeftChild=l;RightChild=r;}intdata;BinaryTreeNode*LeftChild*RightChild;;voidTravelBinaryTreeNode*roots{queueBinaryTreeNode*q;whileroots{coutroots-data«n”;ifroots-LeftChildq.pushroots-LeftChild;ifroots-RightChildq.pushroots—RightChild;tryroots=q.front;q.poP;catch...{return;}voidPrOrderBinaryTreeNode*roots{ifroots{cout«roots-datan;PrOrderroots-LeftChild;PrOrderroots-RightChild;}}voidInOrderBinaryTreeNode*roots{ifroots{InOrderroots-LeftChiId;coutroots—data«Hu;InOrderroots-RightChiId;}}classMaxHeap{public:MaxHeap{root=0;state=0;voidMakeHeapintelementMaxHeapleftMaxHeapright;intMax{if!rootreturn0;returnroot-data;MaxHeapInsertconstintx;MaxHeapDeleteMaxintx;MaxHeapInitia1izeinta[]intn;voidDeactivate{heap=0;}voidHeapSortinta[]intn;BinaryTreeNode*root*last*p」ast;intstate;voidConditionOrderBinaryTreeNode*uintkintiBinaryTreeNode*temp;voidAdjustBinaryTreeNode*u;BinaryTreeNode*LocateLastBinaryTreeNode*uintkinti;private:MaxHeap*heap;;voidMaxHeap:MakeHeapinte1ementMaxHeapleftMaxHeaprightroot=newBinaryTreeNodeelement1eft.rootright.root;left.root二right.root=0;1ast=p_last=root;stated+;}BinaryTreeNode*MaxHeap::LocateLastBinaryTreeNode*uintkintiifk=1returnu;elseintn=intpow
2.0k-1;ints=n/2;ifi=sreturnLocateLastu-LeftChildk—li;elsereturnLocateLastu—RightChiIdk-1i—s;}voidMaxHeap:ConditionOrderBinaryTreeNode*uintkintiBinaryTreeNode*tempinthalf=intpow
2.0k—2;ifu-datatemp-dataswapu—datatemp-data;if!u-LeftChild||!u-RightChiId{if!u-LeftChildu—LeftChiId=temp;p_last=u;state++;e1se{u-RightChild=temp;p」ast=u;state++;elseifi=ha1fCondition0rderu-LeftChi1dk—1itemp;elseConditionOrderu-RightChi1dk-1i-halftemp;}MaxHeapMaxHeap::Insertconstintx{ifroot{intk=intlogdoublestate/log
2.0+1;intindex=state-intpow
2.0k-1-1;intp_index=index/2+1;BinaryTreeNodeemp=newBinaryTreeNodex;last=temp;ifindex==intpow
2.0k—1{pindex=1;ConditionOrderrootkp_indextemp;elseConditionOrderrootk—1p_indextemp;else{root=newBinaryTreeNodex;last=p_1ast=root;state++;}return*this;}voidMaxHeap::AdjustBinaryTreeNode*u{if!u-LeftChild!u-RightChildreturn;e1seifu-LeftChildu—RightChi1d{ifu-LeftChild-datau-RightChild-data{ifu-datau-LeftChi1d—dataswapu—datau-LeftChi1d-data;Adjustu-LeftChi1d;}else{ifu-datau-RightChi1d-data{swapu-datau-RightChi1d-data;Adjustu—RightChi1d;}}}MaxHeapMaxHeap::De1eteMaxintxif!rootexit1;elseif!1ast{x=root—data;state=0;root=0;}else{x=root—data;root—data=last-data;intk=int1ogdoublestate/logdoub1e2+1;intindex=state-intpow
2.0k-1-1;Adjustroot;ifindex%2p_last-LeftChi1d=0;elsep_last-RightChild=O;deletelast;state-;k=intlogdoublestate-1/logdouble2+1;index二state-1-intpow
2.0k-1-1;intp_index=index/2+1;ifindex=intpow
2.0k-1{p—index=l;p_last=LocateLastrootkp—index;e1sep_last=LocateLastrootk—1p_index;if!p_1ast-RightChi1d1ast=p_1ast-LeftChild;eIselast=p_1ast-RightChiId;}return*this;MaxHeapMaxHeap::Initializeinta[]intnMaxHeapLMaxHeapRMaxHeap;MakeHeapa
[0]LMaxHeapRMaxHeap;forinti=l;in;i++Inserta|i];return*this;}voidMaxHeap::HeapSortint*aintn〃创建一个最大堆MaxHeapmaxHeap;maxHeap.Initializean;〃从最大堆中逐个抽取元素intx;forinti=n-l;i=0;i—maxHeap.DeleteMaxx;//cout«i=i—H«xend1;//Travelroot;cout«endl;a[i]=x;//在堆的析构函数中保存数组a//maxHeap.Deactivate;classHTNode{public:intweight;〃权重intparentlchi1drchi1d;;typedefHTNode*HuffmanTree;HuffmanTreeHuffmanCodingchar**HCintw[]inta[]intn;voidSelectHuffmanTreeHTintnintslints2;voidHTEcodechar**HCintw[]intcode[]intcodeLeninta[]intaLen;voidSe1ectHuffmanTreeHTintnints1ints2inti=lj;whileHT[i].parent!=0i++;J=i+1;whileHT[j].parent!=0j++;ifHT[i].weightHT[j].weightsl=j;〃sl为权重小的s2=i;e1ses1=i;s2=j;}i=j+l;whilei=nifHT[i].parent!=Oi++;elseifHT[i].weightHT[s1].weight{s2=s1;sl=i;e1seifHT[i].weightHT[s2].weights2=i;i++;}}HuffmanTreeHuffmanCodingchar**HCintw[]inta[]intnintistartcf;HTNode*p;char*cd;ifnlreturnNULL;intm=2*n—1;〃定义一个有m+1个节点的霍夫曼树HuffmanTreeHT=newHTNode[m+1];//初始化forp=HT+li=l;i=n;i++p++p-weight=w[i-1];p—lchi1d=0;p—rchild=0;p—parent=O;}ints1s2;for;i=m;++i{SelectHTi-1s1s2;IIT[sl].parent=i;HT[s2].parent=i;HT[i].parent=0;HT[i].1child=sl;HT[i].rchild=s2;HT[i].weight=HT[s1].weight+HT[s2].weight;}HC=newchar*[n];cd=newchar[n];cd[n-l]=\O;fori=l;i=n;++istart=n-l;forc=if=HT[i].parent;f!=O;c=ff=HT[f].parent{ifHT[f].1chi1d==ccd[—start]=O;elsecd[-start]=T;HC[i-1]=newchar[n-start];strcpyHC[i-1]cd[start];returnHT;voidHTEcodechar**HCintw[]intcode|]intcodeLeninta[]intaLen{intj;HuffmanTreeHT=HuffmanCodingHCwcodecodeLen;//forintf=l;f=2*codeLen-l;f++//coutVvbn序号:n«f«n双亲结点:«HT[f].parent«n左孩子结点:“HT[f].1child«n右孩子结点:“«HT[f].rchild«H权值:weight«endl;forintr=0;rcodeLen;r++cout«n\nH«code[r]”的字符的赫夫曼编码为:YHC[r]«end1;forinti=0;iaLen;i++{boolfind=false;forj=0;jcodeLen;j++ifa[i]==code[j]find=true;coutHC[j];实验题目排序算法学号日期:
2023.
12.11班级计机
14.1姓名刘方铮Email实验目的堆和搜索树任务规定
一、实验目的
1、掌握堆和搜索树的基本概念,插入、删除方法
二、实验内容创建最大堆类最大堆的存储结构使用链表提供操作堆的插入、堆的删除堆的初始化Huffman树的构造二叉搜索树的构造接受键盘录入的一系列整数输出其相应的最大堆、Huffman编码以及二叉搜索树堆排序软件环境Win7操作系统开发工具:visua1C++
6.0实验代码inc1udeiostreamincludestringinc1udecmath#inc1udequeueusingnamespacestd;classBinaryTreeNode{public:BinaryTreeNode{LeftChild=RightChild=O;}BinaryTreeNodeconstinte{data—e;LeftChi1d=RightChild=0;。