p2documentWord格式文档下载.docx
《p2documentWord格式文档下载.docx》由会员分享，可在线阅读，更多相关《p2documentWord格式文档下载.docx（13页珍藏版）》请在冰点文库上搜索。
Introduction
ProblemDescription:
In1953,DavidA.Huffmanpublishedhispaper“AMethodfortheConstructionofMinimum-RedundancyCodes”,andhenceprintedhisnameinthehistoryofcomputerscience.AsaprofessorwhogivesthefinalexamproblemonHuffmancodes,Iamencounteringabigproblem:
theHuffmancodesareNOTunique.Forexample,givenastring“aaaxuaxz”,wecanobservethatthefrequenciesofthecharacters'
a'
'
x'
u'
and'
z'
are4,2,1and1,respectively.Wemayeitherencodethesymbolsas{'
=0,'
=10,'
=110,'
=111},orinanotherwayas{'
=1,'
=01,'
=001,'
=000},bothcompressthestringinto14bits.Anothersetofcodecanbegivenas{'
=11,'
=100,'
=101},but{'
=011,'
=001}isNOTcorrectsince“aaaxuaxz”and“aazuaxax”canbothbedecodedfromthecode00001011001001.Thestudentsaresubmittingallkindsofcodes,andIneedacomputerprogramtohelpmedeterminewhichonesarecorrectandwhichonesarenot.
OurpurposeistojudgewhetherthesubmissionofthestudentsisHuffmancodeornot.
Firstweshouldmentionthatthecodethatgenetaredbythehuffmanalgorithmisuniquecausethenodeswillbesortedbeforecreatingthetree,while,generally,Huffmancodeisnotunique,justbecauseunsotednodeshavemanysequences.Itwillbeanimportantpointwhileconsideringthealgorithm.Youwillseemoredetailsinthenextchapter:
AlgorithmsSpecification.
Background:
AboutDavidA.Huffman（August9,1925–October7,1999）:
DavidA.Huffmanwasapioneerinthecomputersciencefield.Throughouthislife,Huffmanmademanyimportantcontributionstothestudyoffinitestatemachines,switchingcircuits,synthesisprocedures,andsignaldesignsetc.
However,DavidHuffmanisbestknownforhislegendary“Huffmancode”,whichwewillstudyinthisproject,acompressionschemeforlosslessvariablelengthencoding.ItwastheresultofatermpaperhewrotewhileagraduatestudentattheMassachusettsInstituteofTechnology（MIT）,whereheearnedaScDdegreeonathesisnamedTheSynthesisofSequentialSwitchingCircuits,advisedbySamuelH.Caldwell（1953）.[1]
"
HuffmanCodes"
arewidelyusedinnearlyeveryapplicationthatinvolvesthecompressionandtransmissionofdigitaldata,suchasfaxmachines,modems,computernetworks,andhigh-definitiontelevision（HDTV）,whichiswidelyusedinmodernsociety.
AboutHuffmancode:
AlgorithmSpecification
DataStructures:
MainDataStructureforaHuffmanTreeTreeNode:
typedefstruct
{
unsignedintweight;
unsignedintparent,lchild,rchild;
}HTNode;
Algorithms:
1.First,bulidtheHuffmantree:
for（i=n+1;
i<
=m;
++i）
{
select（*HT,i-1,&
s1,&
s2）;
/*selectthetwosmallestnodewhoseparentiszerofromHT[1]toHT[i-1]*/
（*HT）[s1].parent=（*HT）[s2].parent=i;
（*HT）[i].lchild=s1;
（*HT）[i].rchild=s2;
（*HT）[i].weight=（*HT）[s1].weight+（*HT）[s2].weight;
}
BulidingmethodHuffmantree:
1.choosethesmallesttwonumberofthearray,assighitsparentpointertoi;
2.assighitsweightrightafterthat.
Thendoitrepeatedly.sowegottheHuffmantree.
Nowillustratingit:
Doitbyuppermethodrepeadly:
Finalstate:
NowwegotHuffmantree!
2.ThenwecalculatetheWPLofthestandardHuffmantree.
for（i=1;
=n;
i++）
{
WPL=WPL+w[i-1]*strlen（HC[i]）;
/*calculatetogetthevalueofWPL*/
}
3.CalculatetheWPLoftheinputsubmissions.
sum=0;
/*initializationsum*/
for（i=0;
n;
{
scanf（"
%s"
&
c）;
getchar（）;
gets（string[i]）;
sum=sum+w[i]*strlen（string[i]）;
/*thetotallengthofcodeneededtodetermine*/
}
4.CompareWPLandWPL’
Ifthemareequalinputcaseright.Elsecheckwhetherinputcasehavetherelationshipofprefixion
if（sum!
=WPL）/*ifsumnotequalsWPL,thenwecansaynoimmediately*/
printf（"
No\n"
）;
else/*ifnot,weneedtolookwhethertheyhavetherelationshipofprefixion*/
{
for（k=0;
k<
k++）
{
for（i=k+1;
{
l=strlen（string[k]）;
if（strlen（string[i]）<
l）
l=strlen（string[i]）;
r=strncmp（string[i],string[k],l）;
if（r==0）break;
if（r==0）
printf（"
break;
}
else
if（k==n-1）{
printf（"
Yes\n"
}
}
TestingResults
1.Sampletest
Sampleinputofthisproject:
SampleInput:
4
a4x2u1z1
2
a0
x10
u110
z111
x01
u011
z001
7
A1B1C1D3E3F6G6
A00000
B00001
C0001
D001
E01
F10
G11
A000
B001
C010
D011
E100
F101
G110
Ouputresultoftheprogrmme:
Compareitwiththecorrectoutput:
Case1:
Yes
No
Case2:
Wecanseeitcorrespondsverywell,soitisRight!
Analysis[justonNo]:
AboutfirsNo:
a0x01sowecanseethata’scodeistheprefixofx’s,thoughithavetheshotestWPL.
AboutsecondNo:
Thoughtheredonotexistprefix-relationship,butitsWPLisnottheshotestsoitisnotHuffmancode.
2.FurtherTest
A.somesmall-mediumscaletestdata:
BecauseitiseasytocreatesmalltestcasessoIjustcreatethembyhand.
a3b4c5d6
a00
b01
c10
d11
a11
b10
c01
d00
a01
c00
20
a1b2c3d4e5f6g7h8i9j10k11l12m13n14o15p16q17r18s19t20
1
a1010000
b1010001
c101001
d101010
e101011
f10000
g10001
h11000
i11001
j0100
k0101
l0110
m0111
n1001
o1011
p1101
q1110
r1111
s000
t001
Output:
Analysis:
Isimplyaddsomecodeintheprogromtheprogrammerhandtome.
Here:
And:
Sothecontentintheouputfilearechangedasfollows:
WPL:
36Case1:
WPL'
:
36Yes
864Case2:
866No
Nowwecanseeitclearlytheformerfourcases’WPLcorrespondwithshotestWPLwell,sotheprogramprint“Yes”immediately。
Whileinthecasetwo.WPL'
=866>
WPL=864,soitisnottheHuffmancode.soprintfNo!
Toconclude:
Testingofthesesetoftestcasesareallright.
B.LargeScaletestdata
inthistestIprovidesometestcasethataregeneratedbyprogram,sothattestwhetherthenon-prifixjudgingisrightornot.
Ijustchangethesampleinput.
Inputcases:
AnalysisandComments
Timecomplexity&
spacecomplexityAnalysis
SomeFurtherComments
Furtherimprovement:
A.Aboutalgorithm:
ThisalgorithmfirstneedtocreateanHuffmantreetocalculatethesmallestWPLofcertaininputcharacters,andthenitcalculatetheinput
WPL,andcomparethem.ImeancalculatingWPLbycreatingaHuffmantreewillbecosty.Itcanbeimprovedusinganotheralgorithm,whileitisreallydifficulttowrite.Iftimepermititwillbeapotentialbreakthroughpointinthisprogramme.
B.AboutOthers:
1.Theuserinterfaceoftheprogramcanbemorefriendly.
2.Theoverallstyleofthedocumentcanbesmarter.
3.Ourgroupwrkingcanbemoreefficient.
SourceCode（inC）
AppendixII:
DutyAssignments
Programmer王园园3072211113
Tester王迪3079901015
ReportWriter郭宇波3079901016
升级会员 