ࡱ> tvs'` 0)bjbj{P{P f::Z!E4DDDX@@@8xT4XFl LXnnn!"|A#@cFeFeFeFeFeFeF$PHhJFD# "!##FnnF&&&#8nDncF&#cF&&#A,DCn M@#%#C,7F,F0FOCK%KXCCKDC<##&#####FFu&j###F####XXX$ |XXX|XXX Project 4 (45 points) Assigned: Thursday, February 11, 2010 Due: Friday, February 19, 2010, 11:59 PM Programming Assignment #4 Binary Trees Abstract Write a program in C++ and Visual Studio to scan one or more text files and count the number of occurrences of each word in those files. Use a binary tree to keep track of all words. When all input files have been scanned, print out the results to another file. Outcomes After successfully completing this assignment, you should be able to: Define a class of objects and operations on those objects. Build a massive, recursive data structure comprising those objects. Search for an item in that data structure and, if it is not found, add it to the structure. Create a file for your output and write to it. Put together a non-trivial program in C++. Before Starting Read Chapter 19 of Deitel & Deitel, especially 19.7-19-9. Also read 21.6 regarding new and delete. Review the concept of binary tree from your previous courses. You may also refer to 6.5 of Kernighan & Ritchie or 12.7 of Deitel & Deitel about binary trees in C. In Visual Studio, create a Console Application Project (similar to that you created for Laboratory Assignment #4) called PA4 to hold the program and interface files for this project. This Assignment Your program must accept an indeterminate number of arguments on the command line, the first of which specifies the output file and the remaining of which specify the input files. Thus, a user could invoke your program in a Windows Command Prompt by typing ./PA4 outputFile inputFile1 inputFile2 ... Under this command, the program would open and read each of the input files in turn, building up a binary tree of words and counts as it progresses. Once all files have been read and closed, it must create the output file and write out the words in the tree in alphabetical order, one word per line, along with the number of occurrences of that word. Your program should ignore the case of the words, so that This and this are considered the same. However, words that are actually spelled differently such as car and cars are considered to be different words. A sample output might look like the following: 166 a 25 and 11 as 3 command 15 each 2 file 4 files 109 in 4 input 98 it 99 of 3 open 6 program 18 read 152 the 41 this 3 under 30 would ------------- 17 Total number of different words To allow for very long input files, the field width of the number of occurrences of each word should be at least six decimal digits. You should also total and print the number of distinct words. For debugging, you may use the following text files: HYPERLINK "http://www.cs.wpi.edu/~cs2303/c10/Common/Kennedy.txt"http://www.cs.wpi.edu/~cs2303/c10/Common/Kennedy.txt HYPERLINK "http://www.cs.wpi.edu/~cs2303/c10/Common/Obama.txt"http://www.cs.wpi.edu/~cs2303/c10/Common/Obama.txt HYPERLINK "http://www.cs.wpi.edu/~cs2303/c10/Common/MartinLutherKing.txt"http://www.cs.wpi.edu/~cs2303/c10/Common/MartinLutherKing.txt For fun, you may also any of Shakespeares plays, which can be downloaded from the Internet. Implementation in C++ You must implement this project in an object-oriented style. Think, for example, how you might have done it in Java, and then use that approach as a guideline for your C++ program. At the very minimum, you should define one or more Class Interface files (see 19.9 of D&D) and a corresponding Class Implementation file for each Class Interface. In addition, you should have one or more.cpp files for your main() function, input and output, and anything else that is appropriate. For example, you might define a treenode class to represent an individual word in the input text as a node of the binary tree. This class might have four members: One pointer each to the left and right subtrees. Each would be of type treenode * i.e., pointer to treenode. An int containing the count of the number of occurrences of the word. A string containing the word itself. The treenode class would also contain methods to increment and access the count, access the string, and add or access the left and right subtrees. Of particular importance are the constructor and destructor for a treenode. Note that since a treenode contains a string, and since the string is a class itself, you must pay attention to the order of creation and destruction of these objects. In addition to the treenode class, you might also have a binaryTree class that provides search, insertion, construction, destruction, and traversal methods for your binary tree. Note: The C++ Standard Template Library contains templates for trees. You should ignore these for this project. They are likely to make it more difficult and time-consuming.. Note: Dont forget to invoke the destructor of your tree. This is tantamount to freeing memory in C. Failure to do so can result in memory leaks. The graders will be looking for this. Individual Project This is an individual project. You may consult classmates and others on the algorithms for creating and manipulating binary trees, but you must implement them in your program on your own. Deliverables Before submitting your project, be sure to clean it in Visual Studio. You must submit the following: A zip file containing all of the Visual Studio files of a clean project, including your .cpp and .h files. The project name should be PA4. A document called README.txt, README.pdf, or README.doc summarizing your program, how to run it, and detailing any problems that you had. Also, if you borrowed all or part of the algorithm for this assignment, be sure to cite your sources. The output of at least two different test cases. From your CCC Linux shell, submit your C program using the following turnin command: /cs/bin/turnin submit cs2303 PA4 Programs submitted after 11:59 pm on due date (February 19) will be tagged as late, and will be subject to the HYPERLINK "../../index.htm" \l "_Late_policy"late homework policy. Grading This assignment is worth forty-five (45) points. Your program must compile without errors in Visual Studio 2008 in order to receive any credit. If you do your work on any other system, it is strongly suggested that you compile and test it on Visual Studio at least one day prior to submitting it, in order to flush out any differences in C++ implementation. Correctly build in Visual Studio 2008 (Debug mode) without warnings 5 points Correct definition of class and methods for nodes of binary tree 5 points Correct definition of class and methods for the binary tree as a whole 5 points Correct construction of binary tree and insertion of nodes 5 points Correct traversal of binary tree and output of information according to specified format 5 points Proper destruction of tree and all of its objects before exiting 10 points Correct execution with graders test cases 5 points Satisfactory README file, including output of two test cases 5 points Penalty of five points if your project is not clean before creating the zip file or for submitting your programs in something other than a zip file. Additional Notes Command Line Arguments Command line arguments are the same in C++ as in C. That is, the function prototype of main() is int main(int argc, char *argv[]); The elements of the argv array in this problem are file names. They can be used in the ifstream and ofstream constructors (see below). Input and Output Streams Figure 26.2 in Deitel & Deitel shows the Stream-I/O hierarchy, but it does not seem to show how to open a stream on a file. The following is from Stroustrup, The C++ Programming Language, 3rd edition, 21.5.1: #include ... ofstream output(argv[1]); if (!output) error("Cannot open output file", argv[1]); This declares and creates an ofstream object called output connected to the file named by the command line argument. It can be used in the same way as cout. ifstream input(argv[i]); if (!input) error("Cannot open input file", argv[i]); This declares and creates an ifstream object called input connected to the file named by the ith command line argument. It can be used in the same way as cin. Formatted Output Section 26.6 of Deitel and Deitel discusses how to format output so that it prints correctly and neatly. These are controlled by a set of stream manipulators that are inserted into the stream along with the characters to be printed. You can work out how to make the output of this project look like the specification on the top of page 2.     Programming Assignment #4  PAGE 4 February 19, 2010 CS-2303, System Programming Concepts, C-term 2010    !)+68<BHSUW[efg ! - Q R W o p " # % ' 8 ž h)J6h"h. hgh)Jhz\x h)JNHhKIEhz\xh)J6]h ~d h `h ` h `h.h)JmHnHuhImHnHujh `UmHnHu hTh4h$hXhXh)Jh44f - q ' 8 B edCc+gdedCc+gdCedCc+gd"edCc+gd_QedCc+gd)JedCc+edCc+gd)JedCc+gd ~dedCc+gdX"$ !k&#$-D/M a$edCc+gd$Z)))  ? A B U ] x y   56  7鿺| h/hKIE h:P6h hKIEhKIE hKIENH#hKIEhKIE5CJOJQJ^JaJ h:PNHh:P h.6 hKIE6hKIE h"NH h"6 h"h"'h"h"5CJNHOJQJ^JaJh"#h"h"5CJOJQJ^JaJ. 6ro3j@V 5H;edCc+gd9iedCc+gdz\xedCc+gdIFedCc+gd:PedCc+"$ & Fa$edCc+gdKIE $ TedCc+gdKIE!edCc+gdxedCc+gdKIE78M%&.PRSar-2noRhjk"#$VWXY@ȶȶ럪뎪냪jh(Ujh(U hKIE0Jjh(UjhKIEUh:P#h1hKIE5CJOJQJ^JaJhKIE5CJOJQJ^JaJ hKIENH hl!NHhl!hjnhKIEh:hKIE6] hThKIE2$*2=>MRSf{/045U] *>FKN,25CDE򭉭#hIFhIF5CJOJQJ^JaJ#hIFh9i5CJOJQJ^JaJhIFhl! h9iNHhz\x#h9ih9i5CJOJQJ^JaJ hjnNH#hjnhjn5CJOJQJ^JaJ hjn6hjnh9ih:P h:P66'23:;NVt~3=OVW[\u|}NRTg!"#0[\`cuü霘ۑuhz\xh:*6] hz\x6] h:*6]h. hn hn h:Phn h_Q hIF6]h0:/hiHh0:/6NH] h0:/6]hIFhIF6] hiH6] hIF5\h9i hIFNHhz\xhIF#hIFhIF5CJOJQJ^JaJ+Tg#0v!B} :!edCc+gd:*edCc+gd$!edCc+gdxedCc+gdRedCc+gd_QedCc+gd}edCc+gd:*edCc+gdz\xedCc+gd edCc+0^`0edCc+gd_Q0^`0edCc+gdiHuv !3=?INXYlm?@ABLPUV[ijkr򼸴hX h!h. hV =NHhV =hFI/h.0J)h h.6hhIh h.hRh h:*NH hIFh:* h:*6]#hFI/h:*5CJOJQJ^JaJh:*hIFh:*h:*6]6()56cdeyz   D L M V w !!!1!2!8!9!żżżŬŬŬŬłhIh:*h:*6] h:*6] hKh:*hKhKhK5\h:* h6NH h:*6 h6h!ph h.0JjhlUhzpjh.U h.NHh$h}h4hIFh.39!:!z!}!~!!!!!!!"&"C"""""""####)#A#D#E#M#|###########2$3$<$>$u$$$$$$$$$$$%%%%%ӽӹӹ hFI/6]hFI/hFI/0J,hFI/ hx6]hx hz\xNHhFI/hz\x0J, hz\x6]hz\xhFI/hI0J,hIh4hj1h}hhb"hKh;:!!!"""#M#N### $l$$%.%&edCc+gdFI/edCc+gdFI/!edCc+gdxedCc+gdxedCc+gdxedCc+gdxedCc+gdz\x & F^`edCc+gdz\xedCc+gdb"edCc+gd}edCc+gdKedCc+gd%%%%1&E&F&]&^&i&j&&&&&&&''2'3'I'J's'{''''''''X)Y)Z)[)])^)`)a)c)d)f)~))))!jh=h!0JCJUaJhjn0JCJaJh=h=0JCJaJhSsjhSsU hFI/h>mmFMMr~~֗JJj G @11=CC EEgffHH77dd\ ==UqqV +##H㋁XWW"++_``߮ qtttrrχPmm###7::ǔΪզ` 00 yyy77gg\\~޳bKGDH cmPPJCmp0712HsIDAThC[TUÐ@ G 4HK)-2T)" D[Bâ4ZݺJ[PV7Z9[-mYPʢK6$-/ڼxp7.:bwW Ӹ{Bp QuA-u`季a?ħPD$ p4[:]' Mj<@-Yq*vW&d9/ȑʽ: nX^EhɖtK(aSW4$ VR^;T:&|k&=ZZq|G.\P\UGzL6:3d@]x2o0|vYg&ҵ~<3:ᯰbGz.>U5Jv{ܽT jD ޟιOT*B_T*WW 7GhΫ7"L޷ \]=ٱaԅp*[Jq̑M\@_oP+uu{VC͉©e\_?Hp՝E:57 B YRhAdž\ҴNwl/ǧN2Y7jCd *Z*2Wٺ31l˹uR}6!*H#-=+EY@z9{Eo>*"QQoH2f ly%Bt/ AGYhؚ$oPVvc*kqv\M~,Cck݃93EO M#$r)S3)(CQ<2W_8U3\q_ eAd٦󩶮ur/ˢBgS~mA28u]--EHd{Ą~\D /Ec C "g_BrĺH%fIFZh]=x&X=Uu&+ uLMx([6;. Db{،^x/*Ņ%oJW)pNU8܂'XH5/BW}&Ըqƶ&vvvf[Q 4p&BH"FAeƳ$ lbgȐR-k*`Q >;M„zn (33&}A;tF|n>8o.?8'^˼ 2 tj~ PESh O G>y*x˚w/Fkz_> k= O\GŲPP 7)n唖Lpۤ!GL A p$#g I -D+,>TggVkMdQA(l%ة2H)(.8C uP)"Yeqِ#cf\'JߵZ @[ HN T8up#ֽ]wխ[o"WM`>qG9H$ Gۙp qdoĐ͈;2&T4Z#mXX0P3F^{J#hJq@j0\6RB,QSE1S:^ґBē ]wdW.ކERDvZhΙd;'Ի 6 *$A*v[=6A"8n)5Wd21C@J`)J !iHfwv ,ڤ6aY U_8[(] MTY2}2\馡- RͧVz-hbJȓ}>*U@^w9(goњ*~C!=~\e+WǾr5hWG4.5#)lFAʾ^):!l6tDayYH1axo4v֥kpH!|!e$ ,ҢСHtka3HwaWp6$G%H ;.AW%V9.$ye?ӡ6~f/mڰY PGǷ@wNB HDƕLxĤ ,z B{_n0? ;r@P_^+r 鍸0J#yq >Xco[줄R"&28t#-RA%~ PU`av(@pNy@AU I5#/(}޳oߣCo-y>|2'nDγ?G*hx^W'thͷ3E#ajoS~'"4ץȵWQ@: kilm _;H:rWFNQF?I7녿|l%]C=Dfe0U8ZNӫK|8?eΰrmr(f`N?UWױ@~a97{@g?۟Y#-\aa Z^WT+N@–EK ͷ?b xk1km9](o4[;ɑ=vnqϔgZ#?nՊ?nLBhqIj}m A{V;< (-a=CWrl/ZU]Pw6+\H$TPy Q_>63S>oPL<(ǎMowjuNHo;ŽaT(;wj%-v{7ׇ1(1톡v'YC2[S{/dҸ-s!޼aZB:Jyi$5M*^zϱ|63+>_ET=6CG|pz)Lޟ_#]]Dލz Vf^ND67'L(7ST84ݏfc`: k#mAes>ِb_؁O91oIt ,hG w^U,NruRG.fw`@X+̥t߼M+a}ƪύ̭.̭̍|hj{E-:-y]*r|;ϭPO~欸sxH Ο|Xp\0e{@r7m9j\VPPZz^:4rv$F"SْݪU]^S`(ӓ"{Sp³(9! OP( )7)^q:8 o>$]\>/m+N'M98(頩V<)hGa=п*#~g!3>5LQ8EBM޷ޫÇ uua3n4xi7AKJX!V9z31P[.]azO7N!^!?I 'BuIENDB`DyK yK http://www.cs.wpi.edu/~cs2303/c10/Common/Kennedy.txtyX;H,]ą'cDyK yK ~http://www.cs.wpi.edu/~cs2303/c10/Common/Obama.txtyX;H,]ą'cDyK yK http://www.cs.wpi.edu/~cs2303/c10/Common/MartinLutherKing.txtyX;H,]ą'cDyK  yK 8../../index.htmyX;H,]ą'c _Late_policy-H@H ~dNormal CJOJQJ_HaJmH sH tH Z@Z  Heading 1$<@&5CJ KH OJQJ\^JaJ N@"N $ Heading 2dd@&[$\$5CJ$\aJ$J@rJ V = Heading 3$x@&5CJ\aJB@rB } Heading 4$x@&6\DA@D Default Paragraph FontRiR  Table Normal4 l4a (k(No Liste@ HTML Preformatted7 2( Px 4 #\'*.25@9CJOJQJ^JaJB^@B Normal (Web)dd[$\$4U@4 Hyperlink >*phDV@!D FollowedHyperlink >*phN>@BN  ~dTitle$<@&a$5CJ KH\^JaJ >J@r>  ~dSubtitle$@&a$^JTO1BT `Style Title + Garamond CJOJQJ>6@b> + List Bullet 2  & F6B@r6 ! Body Text xx0Oq0 xO Body Text24Oq4 !Indented ^4@4 !Header  !4 @4 !Footer  !.)@. ! Page NumberNON 4 Char Char3 CJOJQJ_HaJmH sH tH B0@B [y List Bullet & F<<FD@F mA List Continueh<<^hF:@!F y List Number 2 & F <<\Oq\ x code fragment! hhd^h5CJOJQJ:1@": y List Number " & F :1:Style Bulleted# FZOAZ 4/Heading 2 Char&5CJ$OJQJ\_HaJ$mH sH tH >@R> + Footnote Text%CJaJ@&a@ +Footnote ReferenceH*,OQr, +Footnote'Oq )FI/DStyle Body Text + (Latin) Courier New (Complex) Courier New 11 pt...(5CJOJQJ^JaJO (FI/IStyle Body Text + (Latin) Courier New (Complex) Courier New 11 pt... Char5CJOJQJ^JaJOa ,FI/DStyle List Bullet 2 + (Latin) Courier New (Complex) Courier New 1...*5CJOJQJ^JaJ\O\ FI/List Bullet 2 Char CJOJQJ_HaJmH sH tH O *FI/IStyle List Bullet 2 + (Latin) Courier New (Complex) Courier New 1... Char5CJOJQJ^JaJ3!36!Lf-q'8B  6ro 3 j @ V 5H;Tg#0v!B}:MN l.jV Y!Z!\!]!_!`!b!c!e!f!!!!!!!0Cc+0Cc+(0Cc+0Cc+(0Cc+0Cc+ 0Cc+ 0Cc+ 0Cc+ 0Cc+ 0Cc+(0Cc+0Cc+0Cc+0Cc+(0Cc+0Cc+!0Cc+0Cc+0Cc+0Cc+0Cc+0Cc+"0Cc+0Cc+(0Cc+0Cc+0Cc+0Cc+ 0Cc+ 0Cc+ 0Cc+0Cc+0Cc+0Cc+0Cc+(0Cc+0Cc+(0Cc+0Cc+0Cc+ 0Cc+ 0Cc+ 0Cc+0Cc+!0Cc+0Cc+(0Cc+0Cc+ 0Cc+ 0Cc+ 0Cc+ 0Cc+ 0Cc+ 0Cc+ 0Cc+ 0Cc+0Cc+ 0Cc+(0Cc+80Cc+0Cc+!0Cc+0Cc+80Cc+0Cc+!0Cc+!0Cc+!0Cc+0Cc+!0Cc+0Cc+80Cc+0Cc+0Cc+@000@000@000@000@0@000000Ff8  0!B}!0Cc+ 0Cc+*0]Cc+*0]Cc+*0]Cc+@0VCc+*0]Cc+@ "0Cc+00Cc+060 Cc+060Cc+ @0Cc+080Cc+00Cc+ 0Cc+ 0Cc+ 0Cc+0'0Cc+0?0Cc+0)0Cc+0?0Cc+0 DDDG 7u9!%)) "$ :!&))!#%)j # V X 5dy!XXXX&-/G!l,b$N^iyP}88L@(  th ]x  # |#"   3 $A?logohomeC"`] t  S "`]x  B S  ?f!m4 _Hlt253492879 _Hlt253492896 _Hlt253492884 _Hlt253492939 _Hlt253492874 _Hlt253492868 _Hlt213388512 _Hlt213388513 _Hlt213388542 _Hlt244914752 _Hlt244914753 _Hlt250979546 _Hlt250979547 _Hlt213388667 _Hlt213388668 I tttttuuvv!@@@@@@@@@ @ @ @ @ @@ J uuuuuvvww! KNt~louxy}  (,`dLPQRs{Z!Z!\!\!]!]!_!`!b!c!e!f!!!!|lo Z!Z!\!\!]!]!_!`!b!c!e!f!!!!333f  6.g!{ Z!Z!\!\!]!]!_!`!b!c!e!f!!!!!!!Z!Z!\!\!]!]!_!`!b!c!e!f!!!!|fa}2H~>%Ps, L0Ir|:*"("8!\n_1n -5&x-C!nx>#JB'P46AT7V 2i~(^`.^`.88^8`.h^`6]. ^`OJQJo( ^`OJQJo( 88^8`OJQJo( ^`OJQJo(hh^h`. hh^h`OJQJo(^`CJOJQJo(^`CJOJQJo(opp^p`CJOJQJo(@ @ ^@ `CJOJQJo(^`CJOJQJo(^`CJOJQJo(^`CJOJQJo(^`CJOJQJo(PP^P`CJOJQJo(h^`CJOJQJhHh ^`OJQJo(oh pp^p`OJQJo(h @ @ ^@ `OJQJo(h ^`OJQJo(oh ^`OJQJo(h ^`OJQJo(h ^`OJQJo(oh PP^P`OJQJo(h^`.h^`.h pp^p`OJQJo(h @ @ ^@ `OJQJo(h ^`OJQJo(oh ^`OJQJo(h ^`OJQJo(h ^`OJQJo(oh PP^P`OJQJo(^`CJOJQJo(^`CJOJQJo(opp^p`CJOJQJo(@ @ ^@ `CJOJQJo(^`CJOJQJo(^`CJOJQJo(^`CJOJQJo(^`CJOJQJo(PP^P`CJOJQJo(^`CJOJQJo(^`CJOJQJo(opp^p`CJOJQJo(@ @ ^@ `CJOJQJo(^`CJOJQJo(^`CJOJQJo(^`CJOJQJo(^`CJOJQJo(PP^P`CJOJQJo(h^`.h ^`hH.h pLp^p`LhH.h @ @ ^@ `hH.h ^`hH.h L^`LhH.h ^`hH.h ^`hH.h PLP^P`LhH.h88^8`OJQJo(hHh^`OJQJ^Jo(hHoh  ^ `OJQJo(hHh  ^ `OJQJo(hHhxx^x`OJQJ^Jo(hHohHH^H`OJQJo(hHh^`OJQJo(hHh^`OJQJ^Jo(hHoh^`OJQJo(hHh^`CJOJQJhHh ^`OJQJo(oh pp^p`OJQJo(h @ @ ^@ `OJQJo(h ^`OJQJo(oh ^`OJQJo(h ^`OJQJo(h ^`OJQJo(oh PP^P`OJQJo(^`.^`.pp^p`.@ @ ^@ `.^`.^`.^`.^`.PP^P`.-C!>#\n_2i~}|-5JB'AT7V1n P4                   lJ        Cc+17 05 K4[(Cb"8=OqJ}4JZ"$V7$w(+"/4/0:/FI/u1j1P2.3|6ri7V ==?KIEIFIFC\GHHJ)Jx5MdO_QrRThttp://www.cs.wpi.edu/~cs2303/c10/Common/MartinLutherKing.txto d 3http://www.cs.wpi.edu/~cs2303/c10/Common/Obama.txto V5http://www.cs.wpi.edu/~cs2303/c10/Common/Kennedy.txto   !"#$%&'()*+,-./012356789:;=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_`abdefghijlmnopqruRoot Entry F`4wData 41Table<(LWordDocumentfSummaryInformation(cDocumentSummaryInformation8kCompObjq  FMicrosoft Office Word Document MSWordDocWord.Document.89q