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

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

《数据结构实验报告图的基本运算及飞机换乘次数最少问题Word下载.docx》由会员分享，可在线阅读，更多相关《数据结构实验报告图的基本运算及飞机换乘次数最少问题Word下载.docx（28页珍藏版）》请在冰点文库上搜索。

T'

------Tracethetree:

PreOrderandInOrdertheBTree."

E'

------Generatecode:

Accordingtothebuildeduphfmtree,generatethecodesforallcharacter."

C'

------Encode:

Inputarbitarystringformedbycharacterswhichhavebeengeneratedcode,utilizethecodestoecodeandprinttheresultofencoding.（endwith'

#'

）"

D'

------Translate:

readcodefile.txt,utilizetheexisitinghfmtreetotranslatecodeandrestorecodeIntohardwarefileresult.txt."

P'

------Print:

Printthecontentsoffile:

textfile.txt,codefile.txt,result.txtonthescreen."

X'

------Exit:

Exitthissystem."

-'

------Delete:

Deletecharacterset,characterfrequencies,codesandHfmTreeiftheyareexist."

intw[100];

chardata[100];

intn;

charchoice;

inti,j;

HfmTree<

int>

hfm;

HfmNode*ht;

HfmCode*hc;

chars[1000];

repeat1:

Pleaseinputyourchioce:

"

;

cin>

choice;

if（choice=='

b'

||choice=='

）

{

Pleaseinputthenumberofelementarycode:

n;

cout<

---------------------------------------------------------------"

Allocatingthememory..."

Allocatingthecomplete."

Pleaseinputalltheelementarycodes:

for（inti=0;

i<

i++）cin>

data[i];

PleaseinputalltheFrenquencies:

for（i=0;

w[i];

hfm=CreateHfmTree（w,data,4）;

gotorepeat1;

}

t'

hfm"

hfm.PreOrder（Visit）;

hfm.InOrder（Visit）;

e'

Generatingcode..."

ht=newHfmNode[2*n-1];

hc=newHfmCode[n];

hfm.Grcode（w,data,n,ht,hc）;

for（i=0;

i++）

{

ht[i].word<

:

for（j=hc[i].start+1;

j<

j++）

hc[i].bit[j];

}

CodeGeneratecomplete."

gotorepeat1;

c'

Pleaseinputthearticlethatyouwanttocode:

charch;

inti=0;

while

（1）

{

cin>

ch;

s[i++]=ch;

if（ch=='

break;

}

intlength=i;

ofstreamoutf（"

testfile.txt"

）;

if（!

outf）

Can'

tOpenthefile!

return;

i=0;

while（s[i]!

='

outf.put（s[i]）;

i++;

outf.close（）;

Resultofencoding:

hfm.Encode（ht,hc,n,"

"

codefile.txt"

Encodingcomplete."

gotorepeat1;

d'

Startingtranslatingcode..."

Result:

hfm.Decode（ht,n,"

resultfile.txt"

p'

----------------------testfile.txt----------------------"

hfm.Print（"

--------------------------------------------------------"

----------------------codefile.txt----------------------"

----------------------resultfile.txt----------------------"

x'

return;

hfm.Clear（）;

DeleteAll..."

二叉树类：

BTNode.h"

seqqueue.h"

template<

classT>

classBinaryTree

public:

BinaryTree（）{root=NULL;

}

boolIsEmpty（）const;

voidClear（）;

boolRoot（T&

x）const;

voidMakeTree（constT&

x,BinaryTree<

T>

&

left,BinaryTree<

right）;

x,constT&

y,BinaryTree<

voidBreakTree（T&

voidPreOrder（void（*Visit）（T&

x））;

voidInOrder（void（*Visit）（T&

voidPostOrder（void（*Visit）（T&

voidLevalOrder（）;

intSize（）;

protected:

BTNode<

*root;

private:

voidClear（BTNode<

*t）;

x）,BTNode<

*T）;

voidLevalOrder（BTNode<

intSize（BTNode<

};

boolBinaryTree<

IsEmpty（）const

returnroot==NULL;

}

voidBinaryTree<

Clear（BTNode<

*t）

if（t）

if（t->

lChild）

Clear（t->

lChild）;

rChild）

rChild）;

deletet;

t=NULL;

Clear（）

Clear（root）;

template<

Root（T&

x）const

if（root）

x=root->

element;

returntrue;

else

returnfalse;

MakeTree（constT&

x,BinaryTree<

left,BinaryTree<

right）

hereinBinaryTree<

MakeTree."

if（root||&

left==&

right）return;

root=newBTNode<

（x,left.root,right.root）;

left.root=right.root=NULL;

MakeTree（constT&

（x,y,left.root,right.root）;

BreakTree（T&

x,BinaryTree<

left,BinaryTree<

right）

BreakTree."

root||&

left==&

right||left.root||right.root）return;

x=root->

left.root=root->

lChild;

right.root=root->

rChild;

deleteroot;

root=NULL;

voidVisit（T&

x）

x<

PreOrder（void（*Visit）（T&

x））

{

先序遍历为：

PreOrder（Visit,root）;

PreOrder（void（*Visit）（T&

*t）

if（t）

Visit（t->

element）;

PreOrder（Visit,t->

InOrder（void（*Visit）（T&

中序遍历为：

InOrder（Visit,root）;

InOrder（void（*Visit）（T&

if（t）

InOrder（Visit,t->

PostOrder（void（*Visit）（T&

后序遍历为：

PostOrder（Visit,root）;

PostOrder（Visit,t->

PostOrder（Visit,t->

LevalOrder（BTNode<

SeqQueue<

BTNode<

*>

q（100）;

t）return;

q.EnQueue（t）;

while（!

q.IsEmpty（））

t=q.DeQueue（）;

t->

element<

if（t->

lChild）q.EnQueue（t->

rChild）q.EnQueue（t->

}

LevalOrder（）

LevalOrder（root）;

intBinaryTree<

Size（BTNode<

t）return0;

else

returnSize（t->

lChild）+Size（t->

lChild）+1;

Size（）

returnSize（root）;

二叉树结点类：

iostream.h>

structBTNode

BTNode（）{lChild=rChild=NULL;

BTNode（constT&

element=x;

lChild=rChild=NULL;

x,BTNode<

*l,BTNode<

*r）

lChild=l;

rChild=r;

BTNode（constT&

y,BTNode<

word=y;

Telement;

Tword;

BTNode<

*lChild,*rChild;

哈夫曼树类：

BinaryTree.h"

structHfmNode

charword;

intweight;

intparent;

intlchild;

intrchild;

structHfmCode

intbit[10000];

intstart;

classHfmTree:

publicBinaryTree<

public:

operatorT（）const{returnweight;

TgetW（）{returnweight;

voidputW（constT&

x）{weight=x;

voidSetNull（）{root=NULL;

voidGrcode（Tw[],charc[],intn,HfmNodeht[],HfmCodehc[]）;

voidEncode（HfmNodeht[],HfmCodehc[],intcount,char*record,char*tranvers）;

voidDecode（HfmNodeht[],intcount,char*in,char*fout）;

voidPrint（char*in）;

private:

Tweight;

voidHfmTree<

Grcode（Tw[],charc[],intn,HfmNodeht[],HfmCodehc[]）

intm1,m2,x1,x2;

chard1,d2;

2*n-1;

if（i<

n）

ht[i].weight=w[i];

ht[i].word=c[i];

ht[i].weight=0;

ht[i].word='

ht[i].parent=0;

ht[i].lchild=-1;

ht[i].rchild=-1;

n-1;

m1=m2=1000;

x1=x2=0;

d1=d2='

for（j=0;

n+i;

if（ht[j].weight<

m1&

ht[j].parent==0）

m2=m1;

m1=ht[j].weight;

d2=d1;

d1=ht[j].word;

x2=x1;

x1=j;

elseif（ht[j].weight<

m2&

m2=ht[j].weight;

d2=ht[j].word;

x2=j;

ht[x1].parent=n+i;

ht[x2].parent=n+i;

ht[n+i].weight=ht[x1].weight+ht[x2].weight;

ht[n+i].lchild=x1;

ht[n+i].rchild=x2;

HfmCodecd;

intchild,parent;