ࡱ> pro @ lbjbj5*5* (pW@W@.S8& d T6 !!!!!!5555555$7R:h6i#!!##6!!}6'''#!!5'#5''>34! 0sq$ 356064:}%:04:48!>",'E"$i"!!!66s'(COMP 401, Spring 2008 Program 4: Searching, sorting, linked lists, composition, and algorithm analysis (oh my) Due: April 17, 2008, 4:30 pm edt. Objectives: % Implement several data storage and search techniques. % Make a new class from an existing class by composition. % Build a linked list (actually, build a bunch of linked lists). % Keep track of running time both by operation counting and by timing. In this program, you will read and store a dictionary file in several forms. Then you will perform a set of searching experiments, keeping track of the number of comparisons required and the actual clock times required. I. The dictionary file The dictionary file (dict.txt) is on the web site. Copy it into the same directory as your program. It contains just over 25,000 lines. When you read the file, you should exclude any lines that are empty or that are more than 25 characters long or that contain characters other than letters. You should also convert all letters to lower case (see String method toLowerCase). There are approximately 25,020 valid lines. You should store the dictionary in the following forms. An array of Strings in the same order as the input file. A linked list of WordNode objects (see below). A LinkedList of WordNode objects. A sorted array of Strings. Use a quicksort to sort the array. An array of 26 linked lists where the ith list contains only those words of length i. The 0th list will be empty. A 26x26 array of linked lists where the [i][j]th list contains words that are length i and have j as their first letter, where a is 0; b is 1; c is 2; ;z is 25. So, for example, the element [5][3] will be a linked list of 5-letter words that start with d. Hint: you can cast a character to an integer. For example, (int)a has the value 97. Read the dictionary file only once and set up lists a, b, c, e, and f on that one pass. Then make a copy of the unsorted array (a) and sort it to get d using quicksort. Helpful hints for creating the 1-dimensional and 2-dimensional arrays. When you define an array of objects (as opposed to an array of primitive types), you dont actually create any objects. You merely create an array of references. You must explicitly create the objects. So, for example, to create the array of 26 WordLL objects, the code is: WordLL[] wLList = new WordLL[26]; // Create the array of references. for (int i=0; iAE}  !"#()-59@ATij,;STUcd¼ᶬ h=5CJhkh5CJ h$CJ h_CJ h=CJ hCJ hhhh=hH) h=CJh5fOJQJh5fh5fOJQJ h5fCJ>defgklm{}0123@CLTUǿvnvh]vnvh#Kh=CJaJ hkCJhkOJQJhkhkOJQJh#KhCJaJhkhOJQJ hH)CJ h$CJhH)hH)OJQJ h=CJh=h=CJaJh=OJQJh=h=OJQJhkh=>*CJhkh>*CJ hCJh#KhF5CJaJ h=5CJ!2@B,.e  & F @ gdVKn @ gdVKn p$ @ gdH) p$ @ gdVKn/8;<vw񶰥񰙶vrnjfhhhFh`zhh=CJhhCJ h.CJh (h (OJQJ h (CJ hFCJhu#hkOJQJ h`zCJh`zh`zOJQJhkh>*CJ hk>*CJhkhk>*CJhH)hH)CJ h@@CJ hCJ hkCJhhCJ(  .37tu  EF^_`abcdeklhI6hI6OJQJjho`0JCJU hVKnCJhhI6OJQJ h!^>*CJ hI6>*CJhhI6OJQJ h_CJhOJQJhI6OJQJ hh hI6>* hk>*hI6 hkCJ hI6CJ h`zCJ3stBcd"$L   @ gd @ p^p`gdVKn @ gdVKngd  @ gdVKn @ gdVKnl "$&JRT         # - ̻̻̯|vp hKnCJ h@CJ hCJ h5fCJ h=CJ h$CJh=hh] hhCJ h7WCJjh#K0JCJU h@@CJhI6hVKnOJQJ hVKnCJhkhkOJQJ h`zCJ hkCJ h (CJhI6hI6OJQJ hI6CJ,  " # C D !! "F"""-#{## $ $ $%$&$g&k'l'6(c(g(((gdVKn & F & FgdVKn "!F!G!O!R!!!!!! " "C"D"G"""",#/#z#}#####$$$ $ $ $$$$&$%@&_&&&&&&h'5(6(8(((())@)`)a)b)d)ľ hB]CJhBfOJQJhBfhBfOJQJ hBfCJ hCJ h@@CJ h$CJ h CJ hQKCJ h5fCJ hIqCJ h.CJ h=CJ h#KCJ h`zCJ hVKnCJ hKnCJ9((()a)b)c)d)e)f)g)h))))0*K*L****<+++,v,,gdBf^gdBf`gdKnd)e)h)))))**$*-*0*7*K*L* + +++<++++++,,,",^,b,s,,,,-)-*-.-?--------....оииЬиЦиʦЦĝ h!^CJ h]CJ hu#CJh]hu#5CJaJh]5CJaJ h (CJjh$0JCJU haCJ h CJ h CJ hWjCJ hB]CJ h$CJ hCJ h[CJ hBfCJ hKnCJ hQKCJ h@CJ2,-|------...6/W////10y001r112 h^h`gd ^`gd-`gdgd]gdu#gdBf`gdWjgdWj.3/H/I/V//10e0o0y0000000111)131q1r1111W2X2Y2Z2[2\2]222 33373F3K3f3g333333445555(6066躳֭֭ h LCJ hCJh h OJQJ h]CJ h CJ h]5CJhPnh5CJ h=CJ h!^CJ h@CJ h5fCJ hu#CJ hCJ hQKCJ h?'CJ h-CJ hPnCJ82X2Y2Z2[22222G3H3556688882iRjjlllll$a$gd5fgd  h^h`gd6666.70788A9hhh2i3iRjSjjjlllllllllllllƼƴưƦƴh]0JmHnHu ha0Jjha0JUhL h]h#Kjh#K0JUhajha0JU h]CJU h5fCJ h=CJ hPnCJ h CJ hCJ h%25CJry, swap it with its predecessor. Frequently used words (e.g. "the" and "and") will tend to migrate to the top of the list; seldom used words will drift to the bottom. And this will make sequential searching more efficient. Try this with real text. Does the average search length get better with time?  The numbers in parentheses are the number of lines of code in my version of the program. This includes method headers and lines containing only an opening or closing bracket, but excludes comments and assertions. This is meant only as a guideline; you dont have to match my numbers.  Notice that this is not a very useful search method because it doesn't tell you if it found what it was looking for. But it is useful in comparing search strategies.  Successful sequential searches require on average n/2 comparisons; unsuccessful searches require n comparisons. But if the list is sorted, you can end a sequential search early if you pass the place where the word should have been. For example, if you are searching a sorted list for hellq and find the word hells, then you know that hellq is not in the dictionary and you can quit. 401-30. PAGE 6 llgd5f&&P:p5f/ =!"8#$%8@8 Normal_HmH sH tH 8@8 Heading 1$@&5j@j Heading 2.$@& # 8pHP>*CJOJQJb@b Heading 3+$@& pHP 5>*CJ8@8 Heading 4$@&CJD@D Heading 5$ & F@&5CJR@R Heading 6$ p$ @&`>*CJDA@D Default Paragraph FontViV  Table Normal :V 44 la (k@(No List 4@4 Header  !4 @4 Footer  !.)@. Page NumberXB@"X Body Text( # 8pHPCJ6@26 C Footnote Text:OB: Program  & FOJQJ@&@Q@ CFootnote ReferenceH*a 1 RU1pqrV{|}ABz|E' ( n " # . / Q R _ ` ( g ~  ()@ATUefl12@B,.estBcdL~Cz!m   +TXY     Dk_`% Z !l!!""J"K"L"["\"a#b####9$[$$$%v%%&e&&&&'','-'''''Y*Z***++5,6,.9//k1l1~11100000000000000000000 0 0 0 0 00 000000000000000x0000x000x000x00000x00x000H00)0)0)0)0)0)0)0)0)x0)0)0)0)0)0)0)0)0)0)0)00)0)00)0)00)00)00)00)00)0)0)H00H0H00 0800tx0t0t0t0t0t0t0t0t0t0t0tx0t0t0t0t0t0tH0t H0t0 00000000000000 000000x0x0x000000000000000x0x0x000 00 00000000 0 00 00000 0|0 0| 0|0|00 00 0|0| 0 0 0 0|0 00 0|0 0 0|0|x0| 0 0x0 0|x0| 0|0|0|(0|0|0@0x@0@00g @0@00DWg } dl d).6l "$%'(*,.02`2 (,2ll!#&)+-/17l!8@0(  B S  ? H H\+S HDQN H4Yx11B*urn:schemas-microsoft-com:office:smarttagscountry-region8*urn:schemas-microsoft-com:office:smarttagstime9*urn:schemas-microsoft-com:office:smarttagsplace8*urn:schemas-microsoft-com:office:smarttagsdate  16172008304DayHourMinuteMonthYear % -    "" ##--.l111 mt% 2 Z g l!y!##:$Z$v%{%%%e&p&-..l1r1s1113333333333333333333r}@% . S _ n )AUm/kxkl%,   +% 3 Z h l!z!!!#"K":$[$%%++--..//l1s111--.l111 !g3[Lj9YAB&P pP>$4;3R!x`hQ$sq x%tp1B;[x|Mhh^h`o(.808^8`0o(. ^`hH. pLp^p`LhH. @ @ ^@ `hH. ^`hH. L^`LhH. ^`hH. ^`hH. PLP^P`LhH.hh^h`o(.0^`0o(.88^8`o(.808^8`0o(. ^`hH. pLp^p`LhH. @ @ ^@ `hH. ^`hH. L^`LhH. ^`hH. ^`hH. PLP^P`LhH.hh^h`o(.^`o(. ^`hH. pLp^p`LhH. @ @ ^@ `hH. ^`hH. L^`LhH. ^`hH. ^`hH. PLP^P`LhH.88^8`o(. ^`hH.  L ^ `LhH.   ^ `hH. xx^x`hH. HLH^H`LhH. ^`hH. ^`hH. L^`LhH. 4;3R!g3&PpP$sq!x`;[x9YAx%t v        &:                 &        HGB]% ] .  =[_ / "u#?'H)5,%25I6<@@fC (J#KQK L5V7W(,[!^o`a5fBfXfWj3/lVKnKnPnIq}OBF.:-k5`z$~ ( @$=-rL S13]==C@--9b--d*+,1 @@@6p@@UnknownGz Times New Roman5Symbol3& z ArialO1 CourierCourier New"qh)dFnfes&48'S8'S!24d.. 3QH(? COMP 114, Spring 2000weissweiss0         Oh+'0 $ @ L X dpxCOMP 114, Spring 2000weiss Normal.dotweiss8Microsoft Word 10.0@8P@.[4@2m@$s8'՜.+,0 hp  UNC-CHS. COMP 114, Spring 2000 Title  !"#$%&'()*+,-./012345678:;<=>?@BCDEFGHIJKLMNOPQRSTUVWXYZ[\]^`abcdefhijklmnqRoot Entry F;ssData 91TableA:WordDocument(pSummaryInformation(_DocumentSummaryInformation8gCompObjj  FMicrosoft Word Document MSWordDocWord.Document.89q