Scribd
Upload
3 views22 pages

Section 07 - Data Structures

OCR A Level PG Online Text Book - Section 07 - Data Structures

Uploaded by

jlivermore089
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF or read online on Scribd
3 views22 pages

Section 07 - Data Structures

OCR A Level PG Online Text Book - Section 07 - Data Structures

Uploaded by

jlivermore089
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF or read online on Scribd
Tr - arta, ruc an ncn a en Z cnapter 33 — Arrays, tuples and records iectives petamiar wih the concept ofa data structure pean wih arrays of UP to3 dimensions, tuples and records ja structures La per anguages such a8 Python, Pascal and VB have bu ee er. real, Boolean and char. They also have some built Let “narecord. These are made Up of a numberof element s esorsting iin elementary data types such as in structured data types such as string, ts of a specified type such as char, integer, mensional arrays sray's defined as a finite, ordered set of elements of the same type, such as integer, real or cha. frie means that thee isa shee number of elements inthe aay. Ordered implies that there is fa, second, third etc. element of the array i rerexampl, (assuming the fst element ofthe aay is mnyArray (0) nyarray = (51, 72, 35, 37, 0, 3] nyArray(2] fassigns 35 to x x srample 1 fier year the RSPB organises a Big Garden Birdwatch to involve the public in ceuntng the number of birds of diferent types that they seein their gardens on a weekend, During 30-31 January 2016, more than 8 million birds were ‘counted and reported. ‘Te scientists add all the sightings together, and once the data has been analysed, they can ciscover trends and understand how cifferent birds and other wii are faring. An ary of stings could be used to hold the names of the birds, and an array of integers to hold the results as they come in. As a simple example we will hold the names of 8 birds in an array: birdName = ["robin", "blackbird", "pigeon", "magpie", "bluetit", "thrush", "wren", "starling") We can reference each element of the array using an index. For example: birdName[2] = "pigeon" #the index here is 2 Mes languages have a function which will return the length of an array, so that humSpecies = len{birdName] Wwilassign & to numspecies. 179 A nal arrays coms : use the following Teun pet nwt ne ™ enter bird name? ” seem ce a i "a : ype a 2-dimensional caled numbers, wth 3 28.2 lable, rathor ie : ~ Sunbers (1,3) = tS in the aray can be ie Ssoetens a 2 print ("Bird found one ach bie Species ODSEVEd. We can We need a second array of Intiaee each element t 270 irdcount = {0/0/0104 0,0,001 “oud $ to ne lait cont the second een the st] we can write 2 satement res birdcount [1] = birdCount (2 uta tr results as they The folowing algorhm enables @ mamber of he Brawatch team 10 or omni members ol the pubic topes to accumte tefl of staff = ("Anna", "Bob", "carol") quarterSales = [(200,110,120,110), (350, 355, 360, 360), (200,210,220, 220} for 8 = 0 to2 annualsales = 0 foutput staff nane (ingert statement here) eplackbird", "pigeon", "magpie", "bluetics, Schrush", "wren", "starling™) robin" birdtane = irdcount ~ [0,0,040, 0040/0) » ease input name of bird (x to end): for q-0to3 print ("Quarter ", q, quartersales(s,q)) annualSales = annualSeles + quartersales(s,q) bird = input ( while bird t= "x" biraFound = False for count = 0 to ‘if bird == birdNane [count] then a eee ey print ("Annual sales: ", annualsales) Arrays of three dimensions ‘srs may have more than two dmensons, An n-Snesionl rays ase of eerie sane birdscbserved = input (number observed: = bird¢ount [count] + birdsObserved irdcoune [coun endif Af birdFound == Fal print ("Bird species no in arcay") bird = input ("Please input nane of bird (x to end): *) endehite ‘ype, indexed by n integers. Ina 3-dimensional aay x, a partcuar element may be relered to as toow print out the totals for each bird (4, 5,2], for example. The frst element woud be refered 0 2 0, 0,0), for count = 0 to 7 print (birdNane [count], birdCount (count]} 181 180 182 Tuples: tanga nna junes win cous 02 a i 5 = : tuple, ike a sang. is imme r elerents 10 OF pupil ‘Yu can refer to incisal elements name = pupii(0) butte fowing statements iva pupito) = "Mary" Records ou wat str cia perma 2 YH lobe dren ae di ead ol osteragt YO OF He Meena tt sete Goneraly fle consists ofa numberof records. fone tem of data, Fr example, 0 record structure: such as ste events of ay 18 105, tages erie rays, Ne MEN donot a fe hg stale, winch mears that its elemente ee laments fm a tuple, yr read or update i at future date, the data ‘of storing lerge amounts of data convenient record conta 2 numberof feds, ech ting rjc ntdng data about students, yOU might Nav the folowing [cena es 01/0572004 = ie Pas sera Thies —fat 2016 Been Danson o3y0er2002 Es “The table shows a fe containing thee records, each 0 type wil be declared inthe flowing mane: cord ing surnane date dateogBirth ring class end record ‘This ican example ofa user-defined data type named student Type. variable student oftype student Type may then be declared as dent + studentType Every fled na record can be identi by .. The surname of the student, for example, would be referred fo as student . surname ora having 5 fields. In some languages, a recog | Ina certain gama, treasure is hidden in @ 10x10 gi. The ise8 or tothe Bren program gen ., eterna OTaM HEN are ths chap gaplan why the £0r~ next loop Dated below nis situation. '5P0t the most of in iclnt type ofto0p for count = 0 if bird == biraNane [coun birdFound = True birdsObserved = input ("enter birdcount (count) = binges MOET Of bicds 0 Count [cou ved: + coat (count) + pirdsdbserved fp Reve he ageritm wig oe ype tgp 8 ‘re bith wets n grams of 100 babies, which ay beta ran array weight. 500 to 4000 grams, are held ite pseudocode for an algorithm which caleltes fut the number of babies wi are mere than 500g wath the average weight of these, the average bith oe Wht and then prints alow the average weight, together ichioved by the 4th student. Any missing assignments ae te sont mar raw table presenting this ray, anc Hit th est at, \wte a pseudocode algorithm which alows the user to en tthe mas Clute the average mark or each Studer, andthe css average 88S lass average, 1 ‘td coorsnates are given by Pl hand corner and grid, 9] the ‘ae sonifed bya 1 at grid cow, col) grid{row, col] where grid 0,0) represents th to bottom right comer. The grid coordinates ofthe treasure ‘Al oer gid elements ae filed with zeeos, \Wnats the purpose of the fllowing pseudocode algrthm? for row = 0 to 9 for col = 0 to 9 Af grid{row, col] == 1 then print ("row *, ro“, * column ", col) endif next col next. row Wie pseudocode statements to ftialse the grid and “ide the treasure” a a random location Inside tho gi. 1 seonow7—paTASTRUCTIRES Chapter 34 — Queues tives ee 4 ofan abstract ata PS Understand he concen ee te conceot and uses f& Be eer wi ot data win a queve nea, CHCUBK, Prioy) > Deserve te cretion ard maintenance eee @ Desert ane poy tow 18 (© add an itm (0 remove an tem teat foran empy queue © teat fora ful queue Abstract data types ‘An abstract datatypes one tha is created y in pew ie than a wine ss pec i or ae Ry degenerate carson open eno Scheme ammeter ome Si oe et sy es on con ae met en are MO em taen Cie cident wie iemcicur area ct ect ana tee ima she eg eon and he maint genta ena rg La ee Queues 'A queve i 8 First In First Out (FIFO) cata structure. New elamenis may only be added 10 the endota {qusun and elements may only be retrieved rom the rt of a queve. The sequence of data itnsina {queues determined, therfore, by he order n which they ar inserted. The sizeof the queue depends Gh the numberof tems in, ust ie @ queue a trafic ights or ata sypermarkt checkout ‘Queues are used ina varity o applicatons + Ouiput waiing to be printed is commeniy stored ina queue on disk. In a room ful of networked ‘ampules, several pecple may send werk o be prntd at more or les the same timo, By puting the output into @ queue on dik, the outputs printed ona fst come, frst served basis 8s soon as the pater is to. ‘Characters typed at a keyboard ae held in 2 queue in a keyboard buler, ‘+ Queues ae use insta problems. simulation program is one which attempts to model 28 reas Situation so as to lan something about. An example isa program tha simulates customers arming at random mes atthe check-outs in a supermarket store, and taking arcon times to pass through tho checkout, With th ad ofa Simulation program, the optimum ruber ot ‘check-out counters can be established. os a tions on a queue a t/P2 qUeUS is deinos by spstact 0 pS 8 gical src jedan ts described 28 an ordered clacton yg 8 oro wich tome which an can be me: neg removed tom the front 4 pe otowing cueve operons ae nade: ‘Ad @ new itr 0 the rear of ths queue + enQuevetter) 1 aeQueve Remove the font tem rom he queue and eta + sérety0 Test to Se0 whether the queve is empty ar “Test to 580 whether queue ist 188 sen PARSTUETURES Dynamic vs static data SHUTS na aynamic oF Sate data Sct mont ‘An abstract data type may De mm ture ers 1020 ‘came dat oe wine 3 fh Hea, Mecsas equ “cca won vapor draric data SES, SUH 8 the bin en cir i aco pele Pinon. pater ar ry tad the BOG wl crash Te overigw @t exceeds the mas ry etx roaring oa SIE UN A GL Yh py orem csr hl a canons ee ana zo oth i outs ocean 0 alecal P38 aban maximum to avid causa meron eT ig sve such a6 @ List that mary aga un dyraic 08 SOU a sors i =e eg cf edt omchre SOh a5. 8 UE Flack a rays edn ze, apd COMG TEES IN S200 Fe yp Me outable for sonng a feed numberof tems won ame the progam ering. An ay 9 =0 ce rage een! tear eda data svc such 20. aves thal he Se of he ary hs to be ara lomplorent rar ane ramba ots aided up hea. hen mee ang nates ee fea rareis man Pthon dows Ml Reve abun en data structure econ of datain memory that has the abity o gry, wh ig a portion of Memory from whien stein in sie. I'd0es is md automaticaly aocsted a rene code for implementing a circu alee the Ue: procedure initialise lar queue front +0 static data structure such as 6" = naxSize = size of array endprocedure otestfor an empty queue: function isEmp: 4€ size == 0 then return True Implementing a linear queue else “Tere are basicaly two ways to mplement a naar queue in an array or Hist con poise 1. As ems lave the queve, al ofthe othe tems move uP one poston i allocated memory 0 that ne at fron ofthe queue aay the rst eement of the structure, e.g. q[0]. With a long queue, the may weenie : ‘To test for a full queue: 2. near queue can be implemented as an array with pointers tothe front and reer of the queue, A ‘tegerheding these tthe aay the maximum size ofthe queue) is needed, 28 wel a a varie ‘jung the number of tems curently in the quoue. However, clearly a problem wil tise as many tans fre auiged {0 and deleted fom the queve, a8 space created atthe front of the quaue which canst be filed and tems are adied unt he ear pointer pons fo the last element ofthe data structure, function isFull if size == maxSize then else return False endit endfunetion Toad an element to the queue: procedure enqueue (newrtem) if isFull then print ("Queue full") elee rear = (rear + 1) MOD maxSize A circular queue (One way of overcoming the imitation ofa static data structure such as an aay is to implement the usu 5 8 erealar queue, sa when the ara fils wp andthe er port peinstth st ret Gli ay sy be made onto he fest det, qf}, when the next person ns queue, assuring this element is empiy. This solution requites Some extra effort onthe pat ofthe Programmer, and s less fee than a dynam regan sess fete ena yraic data suture the maximum nub of tes alrear] = newrtem endif - endprocedure ecm 7 -DATASTUCTIRES [a rene ae ini vere ems we paadin2qunue 0am of roils Used For exam gy eres ae Ai tyson ci minora 0 os cise or iin OE YD Teena sche in what is meant by a dynar w queue, el edt se © clue na OTN age may gree oS Jobs ae Putin a deve 0 be ented. The gua 0, as rouar aueve which cen hag sn ‘f9p2, 4068, JOD4, JobS. Piers front ang oes re cueve respective, raw dag 0 Show hw he sas (9 Twos ped erate he seu Act, a round data tg 3 queue mente in ots ere th ott the et (@ Pent a 1s ple 0208 i the sequence Job and as ons 2d rear Draw a diagram representing the new stun, 1, me sec s0ne da SINCE hed when ct cas, fa) Stat the tom Usd 1 describ sch dt cts Ge one exa0 Of yP2 dla stu hoes saves fe Give one advantage of using a feed sz daa sca 0) Acueve dla STUCie ae v0 porte cae ont nn ich a finda: . front pots 1 the rst item in ho queue next pomis fo the next avaats space The queue is defied a stn rst out FIFO data struct, () ‘State the condition ofthe pores when the ques erp. (@ Wt an eigorthm 1 remove ene deta tom tom aque nm 4 {@) The quove may be represented bya fined size cata stuctre, deta stuctve —_ plain, with the ad of @ agra, what happens whan atompting to a6 3 data items tothe queve. ol (OCR F530 Qu5 Ane 2012 190 seco 7 -BMTASTRUCTIRES Chapter 35 — Lists and linked lists Objectives + Explain how ast may ay be acded too deleted smarts ester stati of gna et Se be imelemen from ast ‘+ Sow how items + Describe the inked ist data stucte ° sree ow ta crete, vere, a0 27d 2 ‘ror a tnked Hist Definition of a list ata type In computer scince, ists an abstract ate NPs item may occur more than once. The fst s Sequence tee canals refer to the ast eement ofthe ve varety of operations, and can be used for example, yee peueve, stank oF ree, SOMeIANGUBGES SUCH 25 Py, io ist of numbers could be shown as hee 145, 13, 19, 13, 8] consisting of a numberof items in which th fd so can ofr tothe fst, Second, thi, a"® tem Ati a very sel datatype or 8 implement other data structures suc putin ist datatype, s0 that or exe Operations on lists Some possible t operator are shown te follwing table. The it 28 ASSUME YO Hol! the vat [45, 13, 10,13, ina, wn he tt element refered to 28 a0] isEmpiy) [Test or omoty lt alse 18.18,19,8) | Fase 6 ete 00 sccenctam | ASSarew ten aopenct) | M8, 19,1919, 6,53) | erovehe t oaurence| rerevotam [Parone Mofo aremevelt9) | 45,19, 1, 6,33) seaciion) [Search oranaeminist [asoarn22)— |45.10,18.6.09) [Faso | [rar awn e mberofiens [elena [45.10.1080 [6 [rnseiteni_[Retsnite poston ottem [aindwis) 46,10, 18, 8.95) [9 a tet new tem at | sentpositens | Senn ansen7) | 5, 19,7, 13,6, $3) a Remove and een te st Heke pce) 145,19,7,19,8) [9 Remove ae tun he eos = 1928) [erat positon pos 2ponit) (45,7, 19,8) 19 075 - USTs wm wep usts isin an array norte ga re Tarn rier Oda toms sat eye ea Cs oes 2nd is known in advance, 1st data type and sspoost neue ine mer then has t0 Workout and Laveen Code algorithms erie decared in 267408 8 Beng a parr ant eae prioty QUEUE. ce ing a new name in the list : hel in sequent vit ist needs 10 BO ne alortm coud rt determin wh ine where a new tev to beaded, and then if necessany, stat tt and gin oder 0 ae 0 of Kt hast ard move he rst fhe tana, a Holly | James | Nathan | Pout] Sophie st operaton. The empty aay oul be used, for example, to hold a Hoty | James Natta | Paul] Sophie rhe tps aoa foows Test for List already fv11, print message if te is and quit Determine ve new item needs to be inserted - Starting at the end of the list, nove other items alon e Insert new item in correct place perenne Deleting a name from the list ‘Sunpase the name Ken isto be deleted from thelist shown below. The raes coming alter Ken nthe Ist need tobe moved up to fil tha gap. (Cony [vores [ven | Naton [ Paul | Sone — — SHPTER 3 UTS Axo LD USTs is inased prio fo entering ary nama. cam | reat! 8.2 wl conto erst, 02X22 POMS! hee ner Heo space med start will pont othe trst dat torn ata poe tat the at ENDL. The lst om ny paca he last available fee space in the gt i 3. ge not MEE IS NOW COS ih: se them tothe Previous Spot in the 5 nthe empty space by cor ay. moved wf st, ems a 5 = anon [Pet Senne | Sanh [eae ony | samen is replaced wih a blank st. Thi wt 0808s so has Denise ton A pointer of nu 5 fre ineating ow duplicate, Fray the ast element ich snow OF (iar [om [ome | Pot Ls Fi 1 : 2 [3] E} Linked lists 7 snot Definition dered sequence, a8 described bein 6 a sed o hold an 6 ‘Atrio it isa mai data stu waS in contiguous data locations, or «The tems which fam he sequence ae not necessary nln cont atOn8, onthe goquence crdorn which they ovcurin the Sec — cd conta a data ld and anext 2c eld cated sy ner to nares Browning, Tuner, Johnson ae Cay hae bee ace ‘he ary wit ok ke ts Each item inthe sts called a node a of several subtle) oF pointer field (he data fed may consist of Se z a «The dtd nal the acta data ascoitd wh the st fe, andthe POM FE Contain hy 1 ee 7 ‘addres of the next er in he sequence : Te «The ink flo the ast tem nate that there reno further tems by the Use fe mul poner 3 = ; «= Assocatd wth the it pointer variable whch points oe. contains the adress othe fg : = rode the ist Fiwe 5.2 Operations on linked lists Inthe examples which fokow we wi assume thatthe inked it ald in memory in an aray of reco, tad tet aach node consists of @ person's name (te data fel) and a pointer tothe next tem inthe is, tice that we now have twa inked sts Going ing the free nodes thelist inking the nodes containing names and he ist Inking the tree nodes. + pointer start points to the fist item inthe st ‘We wil explore how to st up o inte an empty st insert new dat in the corect place inthe it, er lee an unwanted item ard pint outa tars inthe Ist, We wil also look atthe problem of managing tha re space in the lt. “20 is 8 pointer tothe nex re cation nthe aray 1+ the free spaces in the aray are organised as a inked ist ‘Anode ecard may be defined ike this + names can be retrieved in alphabetical order by folowing the inks type nodetyp string name endtyp= Inserting an item We'l now werk out an algorithm for inserting @ name ino the middle of the st As an example, wet inser Mortimer between Johnson and Turner. Te pointers wil have tobe changed o thet inked into the correct place, dim Nanes(0..5} of nodeType ing a linked list ‘We need to ego 90 Inked Ist: one forthe actual data, and one forthe frea space. When a new item ‘dec sun node pote by next Foe When a node i dled, Ris irked > space ist 192 De 199 Here are the steps: store the new determine, bY change next fre change Mort ime change Johnson ane nortiner 19 vSog liner Felden Ment feee 1068858 =o eo point to Toner se eee co point to MoeEiner Diagrammatic, tis is what we have dene ore irserton he node pointed to by nextfree here new item should be Linked sy tat “oolong ooo Extra steps wil be needed to be ace to the algorithm to cape withthe special cases of inserting a ‘ame at he very tot tt ae 194 Tuner Figure 95.4 st (9. Alen, or inserting the tst name into an empty list. 00 rd the notation used ftp) -name holds the name in node. tp] -pointer holds the value of hy otce how you can ‘Beek ahead using the panes, i ater that one, and Soon is cuca because YOU need to know where you have co Trine node that has arame “greater than the new one to ‘#0 what names inthe rext nade, er even the me fom the previous noe, when you get be insarted samp sooth 9846 arn ane tis acon rar nrg wa Mt Gat wine perso saa eat je conmers nit agin tr rng Renaneherecne 95.2 and 35.4. res (next free) ane = neviana praure follow pointers unts2 Haes(p| poner points ta name > now nane Coop 7 next fren Tipu in tap (Seep 1) ‘Siete = Nanes{tenp) pointer ‘ipa & in sertaee step 2) Nanes{ empl pointer Nones([Link] fut 1 in mertone’s pointer feta (sep 3 putin canons Poloter field (tap # the inked ist shown in gues W/store nane in next free node anes (p] -pointer = temp lagramaticaly: 196 Sec 7 - ATA STRUCTURES — item Pseudocode algorithm for inserting 2° ava titan ‘The fotowng aor copes wt Ist it also manages the fee space (nevane) ure aaatcenteaeae) sinext free] -n2m€ ~ f start o= null then emp ~ Manes (ex ree) pointer spo ose EtG HOM eg so, print error message 11 empty List Nemes nexttree] pointer = null start = nextfree 2 nextfree = temp Nanes{p) name then Tinsext at front 3 Jenp ~ Names (next anes next anes p] -poi p= Nemes p emp] -point x Nanes [ip] pointer reel pointer = 2 ral case inter != nuil and placeFound = fase janes (Nanes[p] pointer] -nare then empl pointer _//update nextfree = tlanes (p) pointer emp //-and pointer in free List ‘an iter stein rot abe 25° FOYE 64, hoon agape et 7 “8 We Wl delete Jonson, —|start=0 exten = 4 follow the pointers untit Jotnson Sfange Cray"s pointer to poine co sett"? Sfange Johnson’ pointer to nearer change nextfree to Point to Johnson ris te shown dlagrammaticaly bow. axeroctton Cha abo = see a tomer Frat Powe 357 Hers the serpiiog agri: follow pointers until Nanes(p) pointer points to the nane to delete temp ~ Names [p] -pointer Jipat 2 in emp Nanes(p] .pointer = Nanes(temp] pointer //put 1 in Cray’s point field Names temp] .pointer = nextfree Jipot 4 in Johnton's pointer fala opt 2 an next nextfrae = temp a S rise - ps fe IEE TURES eon? -OATASTRUCTURES = UST ano une srs aay, re psnocad ADH BOW canbe ed cay ng _ etl operation ona tet Listhength > 0 then while p< ListLength avp 1 CIP] < Newtten rabed i aii m deleting janie fe = ListLength Pseudocode algorithm for for q = ListLength downte p doc Ig seater ic as naiegnt30 2M ONG ha histla + 1) = Listtq) Theta tndas eT eye ae Pe = ue Pana ee eon : 11 hac for thea Hiettangth = Bistbenged «1 ee eis emer” else “The initia vales ofthe variables for one parc ne Tp = start 7 Moce table below, labeled Table 4 execution the algritn ao shown in the aaa eee ese crow cee te mete a sg ° comes draw extra rows, He algoritm. The fst ine is gven and you wa need to 5 deleteName !* Names (Names [p] -pointer] .name dit jopounter now points to the node to be deleted : ae Doubs me prom de aniea Cal 2 (@ Ast inpermented using an arayis tac ata sce. The coud be rpleried ° sng tad lates rum du ort nace Describe one diference between a static dala stuctue and a dynamic data stuct, 0 2. (a) The bids Robin, Sparrow, Blackbird, are entered nthe order gen, toa Inked Ist so ‘hat they may be processed aiphabeticaly. Draw a dagram of tis inked ist a (b). draw the diagram after two atonal tems, Chafnch and Goldinch, are adda, a (©) Show the list implemented in an array of records, wth each node ecg a data em and 2 Pointer, after the adtion ofthe naw tems. 4 (6) Wite a pseudocode algortim to prin out the bids i th st in aprabetical ce. “ i 199 200 SECTON 7 BATA STRUCTURES Chapter 36 — Stacks Objectives «Be tamiar withthe conceat cretion nd mai and uses of + Beadle to deserbe te + Be able to desert ibe and apply the folowing oF astack intenance of data within 2 stack eral: Pus. PoP, BEEK Ot or stack, test or ful S20 + cosutoneunnoanccranlsusnswansaroune io Ste en ete parameters and loa varies Concept of a stack >> ta structure. This means that, ke a ‘Astack is Last In, Fst Out (LIFO) dat ‘Stack of plates ina cafe, Hems ae a the top. Applications of stacks |A stack san important data struct adoresses when subroutines ar call taken back trough the previous pages thet from the stack and reloaded. When you use ‘operation you cared outs popped rom th Implementation of a stack ‘stack may be implemented as ether a static or dynamic data A static dota structure auch as an array can be us cand the othor holding the sizeof the aay (the maximum size ofthe stack) the top ofthe stack Topotstack__p 2 raged tothe top and removed ftom roe ee mormon "ou loked at, in reverse oer as their URLS are re the Undo button in @ word processing package, the st 1 stack and undone. structure. sed with two acational variables, one being & pont Red eae ations ona stack a er ee ting oP TS SOLES omen 8 stack MT yaiten) A808 80H LSM Deo oh ag ee Temoves and retusth ep tam tom ng ~ mth st ee Fetus the op tom tom te tack bet dos og ieemond 10181 898 Whether he stacks emp ioeaett and * aay Wee 10800 Weta estat ana uns a Becean vaio sistmoty) n push) eet [te | sesh(Fed) | aus | su ac ee teem eat Tb, Res Geert | ane ‘3.5000 (Bs Rea oor soe) [Ble Rest i ‘he folowing pseudocode implements four of he st tack operations sing a fied size ary. function isEmpty Af top == -1 then geturn True else return False endif endfunction function {sFull if top == maxSize then return True else return False dit ndunction procedure push (item) if isFull then print ("Stack is full") else top = top +1 8 (top)= item endis endprocedure 201 _ 202 sec 7—asmUCTORS function PoP Jement a stack using the bul-n dynam sumtet ‘element of the list. ono ofthe stack beng the ist Tis data structure, withthe top “te tuncton en 2) canbe used to dtemine whaler te stacks empty. and iis rot, pop) aa ace etn te top element, The bun method append (tem) wil append oF Bush an en ‘nto the top ofthe stack the ast ement of the ht Overflow and underflow ‘Actack wil alvays have 8 maxmum size, because memory cannot grow indefinitely. the stacks irolerentad as onary afl stack can be tested for by examining the value ofthe stack pointer Ay ‘Blom to pus another em onto the stack would cause overflow 50 an eT Message Can be gen the user to evid th, Simla the slack ponte is 1, te stack 8 empty and underflow wil cccurt ‘en attempts made fo pop an lem. Functions of a call stack ‘Ammar use ofthe stack data structure so store information about the active subroutines wie a ‘computer program sunning, The deals ae hidden fro the user nal high level languages. Holding return addresses “The eal stack koops rack ofthe aes o the instruction that control shou return to when a subroutine ends (te return address}. Sovera subroutines may be nested, so thatthe stack may contain several retun adoresses whch vil be papped as each subroutine completes. For example, & subroutine which draws a obot may call suooutnes drawCizcle, drawRectangle etc, Subroutine ‘recursive subroutine may contin savera alt isl, that with each cal, @ new tam the rtm ‘adress s pushed onto the stock. When the recursion finaly ends, te return addresses that have bet _—— a“ tack each er tho rou onto ths run cal ay WN Oe SEC coy apg et ODS anc wee wt 2m wl crash, sooner or ising parameters ee ciate may oo. P8 eo Frenette subosre) may Be held on hcl stan care OI ne coor ane it gone on re Cl Siac hese va Nal oa naatmnanees = jen s variables et un ase UH arb wn jlcation. which uses heap space, rremon al pe tak frame 5 stacks COMPOSE of Stack ames, Each stack tame oo nee tate me Conesponds oa calto a subroutine which stack potter ‘Sack rane fo Exercises 1. Astin, First Out (LIFO) data structure has a pointer cle top, (a) Whats this type of data structure krown as? 0 (b) Name and brief describe one type of ero that coud occur when atameting to ads dala iter or remove a data tem fom the data stuctu. a (0) Describe rey ane use ofthis ype of data stuctuein a comput 10m. a (@) Wite a pseudocode procedure for reversing the elements fa ques wit head of a stack eo ‘Be fair with a hash table and its USS eo ‘Be able to apply simple hashing algartms oO now what is meant by @ olson and POW eo ‘Be farmar withthe concept of a cctionary e ‘Be famiar with simple applications of & cone colsions are handed using rehashing Hashing org entacor ot ct, fer cpl caster cats 9 clase, Teh be aces Sr cane Sorby M9 ane, a etree rug os » sy wean eae cls ha Oren Bee ee? — oto thea nth ky flo 62h ect “haar ig art = ‘Tr roar hat ening or any me poseie ys Ne St srt eo a8 Na oon re ech UT ANNE "op tapas ny bales see 20 it toy by eu of a8 SSE8Ss ata ag J conan ashing igen hi 2 oa thm (address = key mod 1000): remainder asthe acdtess Using th gor 453781 would be stored at adress 781 1447883 woud be stored a adoress 883 134552 woud be stores at adress 552 ‘na wit happen when the record wh hey 631652 tobe stored? This wl hash tothe same adress we 14s¢2 er iscaled # synonym. Synceys are bound to occur with any hashing algorthm, andy record keys hashing fo the same address refered to as @ collision, ‘A simple way of deolng wth collsions it store the em in he next avaiable fee space, Thus 134559 would be stored at adores S53, assuring hs space Is unoccupied. Hash table ‘noah al i a clecn of ams tren such a way thal hay Can qi be located. The haha ul bs muerte san aa "In o2 ren Sze wih a number ef mot Spaces. An ry hash tobe that can stow a acu o 11 fans shown blow, vt spaces lboted 0,1, 2.10 o 1 2 s «4 5 6 7 8 9» » (Emo [Empiy | Empty | Empty | Empty | Empty | Empty | Empty | Empty | Empty | Erewy) Now assume we wh a str es 7, 5, 9,19 nc 29 te table wing the method deserbes 201, usa dvson by 11 an arg he ean. Colisons are stored inthe next aaa eS Fist of a, calcuate the hash valve of each tem o be stored i pee tem can NOW be See Ho eran poy in he es ala, canal searching for an item ‘whan searing fr an item, these stops ae folowed: «anny the hashing ert to the key eld tne tom 1 examina the resulting Cel inthe ist 4 teitem is there, return he tom «tne clis empty, he em 1 notin he table | itn is another tem in that sp, ep moun nes [sence whens appre thal he em ath eta, nS RF Bak cot other hashing algorithms Pet aeaia eta tov cerateceere a eee eter Folding method ‘Tree many ote agoits fr determining hash aes. The folding method ws. 1 method des the tem to tors, at ads he prs oor ha aa, er ange a paneer is eras can be cided into groups of two, namely 1, 58,3, 77,69, 6. Adin hese together we get 253 ihe tele nas tower spaces than the masimusn posse sum generated y ths meta, ay TCD el hen ‘testa ste of dvcing by 100 needs o be appa : 124344585102 205 206 ecm? -DATASTRICIBES hing a string «sings ui the ASC 205088 ng z neni a sng 8D ast tn j Aran nc gn roto na was cre noc at gra a the hash table, fr exaroe, 67 + 654 65 = 198 Hash vaie = 196 mad 11 = 0 so CAB qoesincsten Oasszing tat eaten oT Collision resolution es, he mot ily tisha thee wl be eolisons, and ths needs ite Fresing agorthm and dectng on he table size. For range that whon athe items are Stored, Only 70% of the tebe cy “The ler th hash table become taken nto account when designing the the Se othe table coud be cesoned 0 ar occupies, Fehashing the came gen tothe process of dng an empty lot when 2 colson has occured. ‘Fervensoring agrthm used above Smply looks forthe pat empty st. vl oop ound to he rt cre tine abisof ine ends each, Avaraton on this WoUS be to ook a every third ca for xan the pos east, Ateratvay te hash valu coud be wereented by 1, 9,5 7. Unt ee span Dferentrasting and rehashing methods wit work more efcienty on diferent data sets - the sm sp mince calisors Uses of hash tables ash tables are primary used for efcetlokup, so tha for example an index would typical be ‘organised as a hash table. A nach fable cou be used o lookup, saya persons telephone uber ‘en tar nae, of ve vrs Tey can also be used to store data Such as user codes and encryses [passwords that ned oe looked up and veld quichy. ash tables aro used nth implantation of tho data structure caled a dletionary, whichis discuss below, A cctonay suse data structure ar mplamenting graphs, noduced inthe next chapter | Se ee ie an abstract data type con det ave. Wis a buit-n data singe 2SS°°tEd pa 10 ee to associated vue me PHO ar yang ga ojos te Ker Ae ted en 2 Va Base nS a const of 000 gitlonary 2s required ocean SE br rate Wn Pa ene, ded in, detonate ae witlen 2 comma 00 10 removed ne For exo: Ted pas inthe va * format ey "al and ercosed in (942: "Harey", 6342730, neces gos = y rasms rss MITE 3. ALON Ug te aon needs 0 lu the cova Wr emniaon need © PCS Ih foun pean * EME Sls, Tha cate new empty ctonary jada new Key: Value Da 10 the cetionary palte a Key: ¥a21Ue Pal fom the dictionary mend ie vaio in a Key:value par peturn a value associated with key 1 tun Tee Fase Spending on Wet he tn 7 turn the langth ofthe cctionary the number a ny Of Key value pare anintracti Python Session is shown below . soo toa > (HIE Harry’, BU annie ay 3) ws jis yameinn', S71 tenes So> t0=18651 ‘nx! Spe 1001993] = Mars BS oe (oot: ‘Jasmine’, S71: *Shedlat, 6s: So tos( a5) = "waxines >> 108 {0t: "Jaomine', S7L: ‘Shella, 865: ‘Maxine! ‘Maria’ ) = Pes >>> del 1051995) p> 1D {602 SJaamine', 571: ‘sheila’, 342 >>> 64 in Ibs tre 25> Len(105) ‘ Max', S71: 'Sheita') tWarry', 333: Marka’) “harry', 333; Harry", 33 Note thatthe pairs are not held in any patolar sequence. The ke is hashed using a hashing algortrn {nd placed atthe resulting location in a hash tbl, so tha fst lookups posse 208 ripase which organises the data in fgg {Student records ety # ‘wang sting content of string oatain 2 6 expan what hash function. schoo are stored 02 fa) nthe coo urique 6-398 teger SIUGEN DS nth lp gos ora masa of" ‘hashing function that cou 0 06 ves cords. Gwe an exo cisions. Q (b) Tresystem al haidng cunt ster to nda partir record 9° fete dpe bores nen customers can so alate desu ones ted by 6 cst wl 8 ICA acco nents we entes in the ictlonary are: ante 4, 1170612: "86", 0567129; ‘A34") 2, Abank has a numb for possessions. The deta f lr ned in a dictionary data ste, SOM posse: "C11, 0154068: 8 te ened by okup operation using the Key 11786127 4 (@) What vate wit eth 1b) The detonaryis implemented usng a hash tbl, using the a accountNuber med 500 rao pled SoH bro ‘can be made in the dictionary? ! What yl tured bythe rasa ty (6 Whats the maximum nub of ene ha Wy (@) @ Explan whats meant bya cxison. d h i) ce an exanpe of how a colison might Occur ns Scenario, using sample — ° ae " (a) Describe one way of desig wth colisons i the hash table _ chapter 38 — Graphs vie¥@® » ceo orien ape 0° Sandan 27% ete eg now now an AGBC8NCY Mar and an nieces grap, adiecency ist rt IT tring oO 0 pefinil wo compart uso re aa fe ae tocomeare ne 19 oa rey aes ane, 10 reoesent a graph So ition of a graph ms 13 eget a w Sopnis said to bea drected orp ye is 2 egos may be one-way or tw magaonan alone way te ary St Erurds ‘osven Fgue 98.1: An rset raph uth wets estoy be wae to te sto on Tessin maple mrs circa eee pion res nen Fae 3 pausteenn ero by eet a eae Anu cS et wy ances end conectons na suctued ruercamesariaion ONO Figure 38.2 A dreced, unweighted anh ajnconey matx nd he adlacency ig maton about 2 Sreted OF UNCTECed gray pier ; The adjacency matrix reser on re onan oases ee Each cea ne abe sre th he same iptv case ofan undacted graph th acer mat Wi fh He Same enya, 2519(1.0, tr eae sanurwonhtea graph may be reprzeted a isinsead of wets he leant cal rnage tore att ‘Advantages and disa The adjacency list “An acjcency lis a mocespace-eticient way to plement a sparsely Connected graph, As of ty ‘odes ead, ar each node pats to 2st of alte adjacent nodes to which tis direct Ink. he jaceny lst can be mplsmenied as ast of cctenaris, withthe kay in each dictonsry beng the ote and teva, th ede wogrt. “The raph above woud be represented as flows —> [aca —+ | 15.03) — | fe —| 4 So J 210 grad 70MIN FEE 28-2 WOU bg no at gts of Odes ACaOent to each ngewe shown A dctoren ga ei weights Toray deta snes 2 te ntae ft iMpeentan ht ues my satan MCh ess marten mosis tana qraversing a. graph Tre ae M0 WayS 1 VOVEEE Graph 9 tha vey odes eee + Adepthfirst reversal «+ A breadth-frst vaversal pepth-first traversal x vaversal, We go as far down one ue as we can bh 6 foe bacrsctng and tk he next ut. consider te folowing ora: Powe sa Stating at A, we can ether go eto ight. We wl choose to go whenever thr is a coisa ees We si ©, J, H, D, G, We have already visod F so we have resched the end ofthis path Bak vp to and visit. Now we must retrace our stops va, H, J. FC, 19. and go conte atsativ route to Bandk scam? ~AASTRUCTURES ox [ED one Aor NODE ‘ Nodes wor vateg nto qe. ote pt 010 WOU by rr fg HW SHON a ices, 501870 ‘Tis sequence involved som : NY mati Sesentaton of 0 dete graph soap, ACDEHJFGBK. ——__ -first search —— ain nighours of anode, nd then athe neghbous of hy start node. (0) raw clapram ofthe cect asp, shoving ee wages ‘Consider tne graph below: {p) Oraw an achacency Ist representing tis raph, 8 8 fg) ve one acvartge of using an acacoey ato a Sermenacnser i san a Gon ich each is more apres, [a 4, anundiected graph is shown blo Figure 38.4 va eo sarig at A, we st than 6, then D for we cous have stated by visting Cor Dy © © Tren wa nave 1 8, whch has nonétghbous, so we backup 18 and go tC. From C, we ist O-© Paere owe tok Nes we go Dand sl. Alinodes have row bean ted, nthe order AB 69 EF (a) Complete the acjaceney mati below to represent hs gach tl avevTec[Tolelrleln (a 8 c D Applications of graphs E Graphs maybe used 1 represen, or example: F + computer networks, with nodes representing computers and weighted edges representing the a bandweth between fem H + roads between oun, wih edge weights representing distances, al fares or joumey mes (©) List he nodes in the edarin which they would be vst using + tasks na prot, some of which have o be completed bol others Project be ipleted before othe 0) a depth-first search a * wed pages arin (se Google’ Pagefank algorthm in Section 6) r (@) abeeadth-frst search 212 213 a4 Cc Objectives Q- dire a bina @ = Create and raverse 3 nny Hee = create, search and reverse aay searct hapter 39 - Trees ch each node hes at most two chidren od toe whi ry 109 38 2108 hee Concept of a tree ‘Tes area very commen data su Use a re in nature, 2 rooted tree in computer science has ts oot atthe 1 “Typical uses fr rooted res include sue in many seas of computor S8TC9 and other contents 1 pranches and leaves. the otlerence being that ay has 00 a 1p and is leaves atthe bottom. sg nerarhcal data. suchas oer structures or moves 3 GOMe + wind . tree search below) “+ making information easy to search (see binary + manipulating sorted ists of data rations ofa tamiy may be thought of as hawng a tree truce ener + Posto + Lest node “The ree shown above has a reet nade, andi therefore defined as @ rooted tree. Here are some ems sed in connection wth rated tees: Node: The nades contain the re data age: ‘An edge connect two nades. Every nade except the root is connected by exactly one edge fam another node Foot Ths s the ony nade that has no incoming edges nia These of nodes that have incoming edges from the same node Parent! Anodes a parent of al the nades it connects to with outgoing edges Sublwe: The set ofnoges and edges comprised ofa parent and al descendants ofthe pat. ‘sues may aso be all Leat node: Anode tat has no chien Dead en Sealer note tn nace, and to its children. i ean ae aware search tree ara aur A Rede can ony be comecied to rarer Spleens non saree ton Bao amar teen” eon canstucting a binary Search tree ypose te fotowNg Ist MUNBETS so be neta at toe ee can be Gui searched 3 He, nthe cde ge, n sucha way rattan at het Pte (ms Sawer bv tensive ee Mec than ve a he Curent node, Conte coun the tapch spar oe eater Series are tn cre min nce innather it's less than or greater than the valve at that node aon Fallowing his algorithm, 17 is placed at the root. less than th 1008 "ess han 17, 30s placed at anew node to the lt {isles han 17, 80 we branch lef at he rot, branch et at and place itt the t2lsess than 17, so we branch eft at he root, branch right a 8, and place tt the rh “he fal tr Hooks ke this: To search the tree forthe numer 19, fo example, we folow ne sae steps. 19's greater than 17, 80 branch ight 19 less than 22, so branch lft. There ts) 216 cron 7 Traversing a binary tree “Tae are tree ways of traversing 89S: + Preorder traversal + nnd travers Post-ooerraversl ‘The names ero whether 2 have boon traverses, cot ofeach sup en's vite befor, DEINE Or oth i hh Pre-order traversal ene ve were te ee orcas, sangrotrete tere AS YU ESS 0 ee, tat the gatan that node Fea {were the 9 cot is marked 0 nodes willbe visited in spo nodes wil be vised in the sequence 4 5,8, 12.14, 17, re in-order traversal visits the nodes in sequenal ocr, i post-order traversal raw an outline round the res struct ote ur, start te here the red dot is marked), olp tect tht cae 0 AS YOU pass fo he ight ofa Terres ib ited he sequence 17,845,114, 22, 19,90, 25 ‘soar reves my be ved orks rte nolo, ued ~— von poe ntaton en nto programing ag a ei toeanaartr= soe ayahertant = 87 bee ‘ihe operation comes before the operands rather than between tham, as in infix notation. “a 216 The nodes will be be visited in the sequonce 5,4 14, 12,8, 19,25 90,2217 a7 Jementation of a binary search tree imp of recat, wth each nod enplarert vs an 2 consist ‘Ana search we can be OE 9 ot 7 or ao ton eee + daa tem sags or anne eis rant porter Je the left subs sor treo sopra ISt OF YS, On fr, exavers cree st of ples of tree Sera ATVs, ON€ fr ch of ing eigie the root node ‘aerate, coud be eld 9 pointers and one forthe eta HES : of in-order traversal ‘chow = ae] Mt expres i repre “ea "8 HI oy ay : 3 ware sional. arrays cas ist wth each ioe ihe ler cla re witlerse the Fight subtree 15.30, 25 used to construct the 98 above could be hag tel 4 pit pointers 0 the eft and right subt vl | - - sand suboes. The van oi = : £ é nest eat rade seed ashe © veo | a a easy | 8 | @ wos Lt | 1 weg fot fe | 8 ‘veel 7 6 . woos! | 2 | © 5 eet) 1 25 ‘ Figure 39.1 or example, thet prinr nto pots towel] ad the gt oie ois to tees. The a suppove this data eld a8 shown below er ne ate wich rates at aos chien te relevant ide eto ight). [Ten a Tone] tee | 1 watt! | wet] [5 wea tea toe wee [1 a 4 Inpseudocode: procedure inorderTraverse (p) f tree[p).left != -1 then inorderTraverse (tree(p) -Left) endit print (tree{p] .data) Lf teee(p) right != -1 then inordertraverse(tree(pl right) endif endprocedure 218 beesd SD sence sir ae ‘output in the order | “rang tough te ort, te nos Use of in-order traversal algorithm ‘Aan in-order traversal i used wih @ TS ‘Algorithm for post-order traversal “The lgritm for @ post-order averse ye left subtree gne subtree ‘re, to porto an efclent Search for any ite, traverse the Fi visit the root node In pseudocode: procedure postorderTraverse (P) if tree(p) left = “2 then postorderTraverse (tree|P] Left) endif Sf treetp] right != ~1 then postordertraverse (tree[P) -r33ht) endit int (tree(p] -d3ta) cendprocedure ¢d/+ Thisis the sequence in which algebraic excess “The nodes are output inthe sequence a b* hich is used by compilers to evaluate expressions, ao writen usng Reverse Polish Notation, wi Algorithm for pre-order traversal “The aor for 9 pre rd traversal is visit the root node traverse the left subtree traverse the right subtree In pseudocode: procedure preorderTraverse(p) print (tree(pl .data) fee[[Link] != 1 then preorderfraverse (tree|p] -le ight t= -1 then jerse (tree(p].right) A rere tvr ayn sd recresomnrai0s\ Pekeueinomompesavesuace s cise 0 nay ed a3 = (a snow now he long data mayb abetic order by craving the ts. asses re Forest ofthe data items are iets re rete van tit org 9 en ne tem Pe oot Mee nd pata tems: magpie, robin ch ven teh, et tay ec Mh Benoit, sea atk gen ip Show now the data cous be rproseieg sng thee one mensional aay, a (g st the ode thatthe Nodes Wau be td sing () apre-order traversal (@ enin-order traversal a (@ a post-order traversal Bm @ 2. nnat order shoul he flowing eet aver pénted in the correct sequence? 80 hat each section and subsct " o 221

You might also like