Arrays, Records and Pointers nea} amrays Midet the linear arrays “AAA(5 150), BBB(-5: 10) and CCC(18). * i rind the number of elements in each array. ) IM(AAA) = 300 and w-= 4 words pet memory call for AAA. Find the 1 suppose a 0) Se AAALISH AAADSS} and AAAISS) (@) The number of elements is equal to the length; hence use the formula Length = UB - LB +1 Length(AAA) = 50-5+1=46 =10-(-5)+1=16 18-1+1=18 ‘Note that Length(CCC) = UB, since LB = 1. (b) Use the formula ‘Accordingly, LOC(AAAIK]) = Base(AAA) + w(K - LB) LOC(AAATI5]) = 300 + 4(15 - 5) = 340 LOC(AAAI35]) = 300 + 4(35 - 5) = 420 AAA(55] is not an element of AAA, since 55 exceeds UB = 50. 42 Suppoie'a company Keeps a linear array YEAR(i920:1970) such that YEAR[K] contains the numberof employees born in year K.. Write a module for each of the following tasks: {@) To print each of the years in-which-no employee was born: (0) Tofnd the number NNN of yeas in which no employee was bom. Hence:cast 50 yeurs old at the end of find the numb who will be at feast 50 y the year. (As: (@) To tind the numt year. (As is the current year.) Ht b 5 old at the end of the who will be least Lye employees current year.) Each module traverses the array (@) 1, Repeat for K = 1920 to 1970 If YEAR{K] = 0, then: Wri (End of toop.} 2. Return (b) 1. Sct NNN := 0, 2. Repeat for K = 1920 to 1970: a If YEAR{K] = 0, then: Set NNN := NNN + | [End of loop.] 3. (ce) 1920 to 1934: NSO + YEAR[K]. 2. Repeat for K = Set NSO. {End of loop.} 3. Return, (d) We want the number of employees born in year 1984 ~ L or earlier. 1. Set NL := 0 and LLL := 1984 -L 2. Repeat for K = 1920 to LLL: Set NL := NL + YEARIK]. [End of loop.] 3. Return. 4.3, Suppose a 10-clement array A contains the values Q, ay, after each loop. jo. Find the values in A (a) Repeat for K = | to 9: Set A[K + 1] = A[K]. [End of loop.) (b) Repeat for K = Set A[K + 1 {End of loop.] Note that the index K runs from 1 to 9 in Part (a) but in reverse order from 9 back to 1 in part (b), (a) First A[2) := Afl] sets A(2] = 4, the value of All]. Then A[3] := A(2] sets A[3] = a, the current value of Al2]. Then A[4] := A[3] sets Al4] = a, the current value of A[3]. And so on. Thus every clement of A will have the value %, the original value of A{l]. to I by =I: = ADI.Arrays, Reco \rrays, Records and Pointers bh et ALOE * ALO] sets ALO] = ay st “gore ALBI sets ALL Shs AAITI sets AIS] = ay. And so on ~ aque in A will move to th xt f 10 the next location. At the © w » Fe ah qnen AU very sample illustrates the reason that, in the insert . in the insertion Re’ ai ved downward in reverse order, as in Toop ( ex. as in loop (b) he alphabetized Tineat azray NAME in Fig. 4.2 consider Y os tn | 2} ciak | 9] joan Goodman | Irwin _— Klein | Lewis Morgan ae 41 | Richards Scott |—— 43 | Tucker “44 | Walton Fig. 4.23 (a) Find the number of elements that must be moved if Brown. Johnson and Peters are inserted into NA! ifferent times. (b) How many ¢l coved if the three mam (c) How does the telephone company handle insertions in & fe (a) Inserting Brown requires-13 elements to be ing Johnson requires to be moved and inserting Peters requires 4 element: .d, Hence 2 are moved. (b) If the elements are inserted at the same time, once (with the obvious algorithm). (c) The telephone company keeps & telephone directory once a year. es are inserted at the same time? ephone directory? moved, insert! 7 elements 5 to be move 14 elements then 13 elements need De moved. each only running list of newSearching, Sorting AE Onstdler the alphabetized linear array NAME in Fig. 4.23. parisons C are used wo Eo (9) Using the linear search algorithm, Algorithm 4.5, how many comp: 4 locate Hobi i Hobbs, Morgan and Fisher? ed array to make an () Indicate how the algorithm may be changed for och ee Unsuccessful search more efficient. How does this affect p: ine with Allen, un (a) C(Hobbs) = 6, since Hobbs is compared with cach name, beginning mo Gl Hobbs is found in NAMED! AME(10} (Morgan) = 10, since Morgan appears in NAMEL 0) a compare CiFisher) = 15, since Fisher is initially placed in NAME[15] aes the fea i: with every name until it is found in NAME(I5]. He broom eateed unsuccessful. . ; ; stop afte (b) Observe that NAME is alphabetized. Accordingly, the DAE MCR given name XXX is compared with a name YYY such that X2 C(Fisher) = 5, since the alphabetically, XXX comes before YYY). With this Se AMEEST search can stop after Fisher is compared with Goodman in } i is appli y NAME in Fig, 46 Suppose the binary search algorithm, Algorithm 4.6, is applied to the array NAS 4.2310 find the Tocation of Goodman, Find the ends BEG and END and the middle MID for the test segment in each step of the algorithm. Recall that MID = INT((BEG + END)/2), where INT means integer value. Step 1. Here BEG = | [Allen] and END = 14 [Walton), so MID = 7 {Irwin}. Step 2. Since Goodman < Irwin, reset END = 6. Hence MID = 3 [Dickens] Step 3. Since Goodman > Dickens, reset BEG = 4. Hence MID = 5 [Goodman] We have found the location LOC = 5 of Goodman in the array. Observe that, there were C = 3 comparisons. 4.7 Modify the binary search algorithm, Algorithm 4.6, so that it becomes a search and insertion algorithm. There is no change in the first four steps of the algorithm. The algorithm transfers control to Step 5 only when ITEM does not appear in DATA. In such a case, ITEM is inserted before or after DATA{MID] according to whether ITEM < DATA(MID] or ITEM = DATA[MID]. The algorithm follows. Algorithm P4.7: (Binary Search and Insertion) DATA is a sorted array with N elements, and ITEM is a given item of information, This algorithm finds the EM in its proper place in Steps | through 4, Same as in Algorithm 4.6, 5. IfITEM < DATA[MID), then: Set LOC := MID. Else: Set LOC := MID + 1. (End of If structure.] 6. ia ITEM into DATA[LOC] using Algorithm 4.2. 7. Exit,suppose A is with the same average-case 1 4s a sorted array with 200 elements, and supposi probability in 3 __Arrays, Records and Pointers any play iné a given clement x appears nd the worst-case running time f(u) and the unning time g(v) to find x in A using the binary search algorithm, For any value of & let ng denote the number of those elements in A that will require & comparis The 73 comes from th The worst-case running time f(r elements lel ko ng A obtained as follows: Bln) = 4 n approximately equal. 1353 x ons to be located in A, Then: 23 4 Oueaunoatl 8 Dkeny kal Le]42-243-444-84 00 = 6.765 4.9} \sing the bubble sort algorithm, Algorithm “umber D of interchanges which alphabetize the = 6 letters in PEOPLE. The sequences of pairs of letters ‘a square indicates that the pair of 5 67 8 6 32 64 73 fact that 1 +2444... +64 = 127 so there are only 200 - 127 = 73 8. The average-case rumning time g(n) is +6-3247-64+8-73 200 Observe that, for the binary search, the average-case and worst-case running times are 4.4, find the number C of comparisons and the which are compared in.each of the m ~ 1 = 5 passes follow: f letters is compared and interchanged, and a circle indicates that the pair of letters is compared but not interchanged. Pass 1. Pass 2, Pass 3. Pass 4. Pass 5. PEOPLE, EPOPLE, EO! EOMPLE EOPLPE|EOPLEP - €Orcer, EQDLED EOpLer EOLPEP, EOLEPP Go.err, elouerr, evlorrr ELEOPP Edeorr, ELEjory, EELOPP G@DLopp, EELOPP Since n = 6, the number of comparisons will be C= 5+4+3+241= 15. The number D of interchanges depends also on the data, as well as on the number 7 of elements. In this case D = 9,ate Structures 4.10 Prove the following identity, which is used in the analysis of various sorting and searching algorithms; a(n+1) 142434..4¢0= = Writing the sum § forward and backward, we obtain: S2l+2s34..¢(2-Dea Sene(n-I+(n-2H+.. 4241 We find the sum of the two values of S by adding pairs as follows: WeneHene hee Hen tae Dee) There are n such sums, so 25 = n(n + 1). Dividing by 2 gives us our result. Multidimensional Arrays; Matrices Sippose multidimensional arrays A and B are declared using Cet AC22, 2:22) and BCL 5, -10:5) : ss & (a) Find the length of each dimension and the number of elements in A and ie ee (b) Consider the element B[3, 3, 3] in B, Find the effective indices Ey, £2, E and the address of the element, assuming Base(B) = 400 and there are w = 4 words per memory location, —| L (éf The length of a dimension is obtained by: Length = upper bound - lower bound + 1 / Hence the lengths £, of the dimensions of A are: 2)=2-(-2)+1=5 and L)=22-24+1=21 Accordingly, A has 5; 2h = 105 elements, The lengths L, of the dimensions of B L=8-1l+1=8 L,=5-(-5)+1 211 Therefore, B has 8 - 11 --16 = 1408 elements. (b) The effective index E, is obtained from E, LB is the lower bound. Hence are: L,=5~-(-10)+i=16 ~ LB, where &; is the given index and E,=3-1=2 £,=3-(-5) 28 The address depends on whether the order or column-major order, Assumin (4.8): 3=3-(-10)=13 Programming language stores B in row-major ie B is stored in column-major order, we use Eq Eyl) = 13-11 (Egly + EL, = 151-8 = Therefore, LOC(B(3, 143 208 143+ 8= 151 ly + E, = 1208 +2 = 1210 00 + 4(1210) = 400 + 4840 = 5240 (Bly +E__Attays, Records and Pointers Let A be an n xn square matrix array, Write a module which (a) Finds the number NUM of nonzero elements in A (b) Finds the SUM of the elements above the diagonal, i.e., elements A{1, 5] where 1 < J (©) Finds the product PROD of the diagonal elements (41, 33, ... yy) (a) 1. Sct NUM 2. Repeat for I= 1 to N: 3. Repeat for J = 1 to N: If All, J] # 0, then: Set NUM := NUM + I. _ [End of inner loop.) — {End of outer loop.) 4, Return. (b) 1. Set SUM := 0, 2, Repeat for J = 2 to N: 3, Repeat for I= 1 toJ-1: Set SUM := SUM + ATI, JJ. [End of inner Step 3 loop.] 4, Return. J. Set PROD := 1. [This is analogous to setting SUM = 0.] 2, Repeat for K = I to N: Set PROD := PROD*AIK, K]. [End of loop.] 3. Return, «c 4.13 Consider an n-square tridiagonal array A as shown in Fig. 4.24. Note that A has n elements on the diagonal and n - | elements above and n — 1 elements below the diagonal. Hence A contains at most 3n ~ 2 nonzero elements. Suppose we want to store A ina linear array B as indicated by the arrows in Fig. 4.24; i.c., BUJ= ay. B= ay B= a, BIA] = ay, Find the formula that will give us L in terms of J and K such that BIL] = AU, K] (so that one can access the value of A[J, K] from the array B). year Aj Aze—p Ae 832-299-234 Fig. 4.24 Tridiagonal ArrayC | Data Structures [466 | __ Pata Structures above AU, KJ and K J+ ¥ elements ta Note that there a of AU. KI]. Hence Le(d-24e(K-+ Ue laaek 4.14 An nesquare matrix array A is said to be symmetric if ALJ, K) = Al K, J] for all and (a) Which of the following matrices are symmetric? 23 s\f1 11d (1 3-7 3-2 4]/1 111 3.6 -l 5 6 sll 1d i\-7 -1 2 (b) Describe an efficient way of storing a symmetric matrix A in memory. (c) Suppose A and B are two n-square symmetric matrices. Describe an efficient way of storing A and B in memory. (a), The first matrix is not symmetric, since a;3 = 4 but ay, = 6. The second matrix is nota square matrix so it cannot be symmetric, by definition. The third matrix is symmetric, (b) Since AU, K] = AIK, J], we need only store those clements of A which lie on or below the diagonal. This can be done in the same way as that for triangular matrices described in Example 4.25. First note that, for a symmetric matrix, we need store only cither those elements on or below the diagonal or those on or above the diagonal. Therefore, A and B can be stored in an n x (n + 1) array C as pictured in Fig. 4.25, where C[J, K] = AQ, K] when J 2K but CU, K] = B[J, K -1] when J < K. (c (ar by Be Bnet Bin a WBS been ant Ban ayy Bae ag ~ by Bat naz ng An Fig. 4.25 Pointer Arrays; Record Structures 4.15 Three lawyers, Davis, Levine and Nelson, ‘share the same office. Each lawyer has his own clients. Figure 4.26 shows three ways of organizing the data. () Here there is an alphabetized array CLIENT and an i array Li ER s ql LAWYERIK] is the lawyer for CLIENT[K), Sy Ea Asicswor Arrays, Records ond Pointers CLIENT LAWYER paws. LEVINE NELSON 1 [Adame] [[Notson + [erown] + [non] + [Adame | 2 | Brown | | Davis 2 [cones | 2 |Fiscner | 2 | Gioson 3 | Cohen | | Davis 3 |eisen |, | 3 | Harris 4 [Dixon | | Levine “ : 5 | Elsen Davis . , Jt. . 6 | Fischer Levine ° 7 [Gibson | | Nelson rc a | Haris | | Netson LAWYER NUMB PTA CLIENT a 1 | Davis | | 94 1[--——~ 1 | Brown : Levine | | 72 125 2 | Cohen’ @ 3 | Netson| | 86 | [278 al 125 | Dixon 126 |Fischer| 27s | Adams 276 | Gibson () Fig. 4.26 (b) Here there are three separate arrays, DAVIS, LEVINE and NELSON, each array containing the list of the lawyer's clients. (c) Here there is a LAWYER array, and arrays NUMB and PTR giving, respectively, the number and location of each lawyer’s alphabetized list of clients in an array CLIENT. Which data structure is most useful? Why? The most useful data structure depends on how the office is organized and how the clients are processed. Suppose there are only one secretary and one telephone number, and suppose there is a single monthly billing of the clients. Also, suppose clients frequently change from one lawyer to another. Then Fig. 4.26(a) would probably be the most useful structure. Suppose the lawyers operate completely independently: each lawyer has his own secretary and his own telephone number and bills his clients differently. Then Fig. 4.26(b) would likely be the most useful data structure.ae] at Stee sh lawyer has to process his teach Jawyer i : ients frequently am ful data structure, yee pre ot) woul Tikely be the most use " quently. Then Fig. 4. : umbers, in a student's record: iddle Initial) 2 Sex st 3 First 3 MI (Midd 1 Stud me 3 Last 3 S 3 Verbal ao ee Bee ‘Momh 3 Year 2 SAT 3 Math structure. 4.16 The following is a tist of entries, with level ™ (a) Draw the corresponding hierarchical i" (b) Which of the items are elementary items* (a) Although the items are listed linearly, the ee relationship between the items. The corresponcine 1 Student 2 Number 2 Name 3. Last 3 First 3 Ml Sex Birthday 3 Day 3) Month 3. Year 2 SAT 3° Math 3. Verbal (b) The elementary items are the data items which do not contain subitems: Number, Last, First, MI, Sex, Day, Month, Year, Math and Verbal. Observe that an item is elementary only if it is not followed by an item with a higher level number. J numbers describe the hierarchical hierarchical structure follows: we 4.17 A professor keeps the following data for each student in a class of 20 students: Name (Last, Fiist, MI), Three Tests, Final, Grade 2-character entry, for example, B+ or C or A~. Describe a PL/I structure: Here Grade is to store the data An clement in a record structure m separately, we store them in an array be itself. Instead of storing the three tests uch a structure follows; DECLARE 1 STUDENT(20), 2 NAM 3 LAST CHARACTER(10), 3. FIRST CHARACTER(O), 3 MI CHARACTER(), TEST(3) FIXED, FINAL FIXED, GRADE — CHARACTER(2); 10-84.18 A college uses the following structure for a graduating class: 1 Student(200) 2 Name 3 Last 3. First 3. Middle Initial Major SAT 3. Verbal 3. Math GPA(4) CUM Here, GPA[K! refers to the grade point average during the Ath year and CUM refers to the cumulative grade point average. (a) How many elementary items are there in the file? i (b) How does one access (i) the major of the eighth student and (ii) the sophomore GPA of the forty-fifth student? (c) Find each output: (i) Write: Name(15] (i) Write: CUM (ili) Write: GPA(2]. (iv) Write: GPALI, 3]. (a) Since GPA is counted 4 times per student, there are 11 elementary-items per student, so there are altogether 2200 elementary items. (b) (i) Student. Major{8] or simply MAJOR{8}. (ii) GPAT45, 2). (©) (i) Here Name{15] refers to the name of the fifteenth student. But Name is a group item. Hence LAST[15}, First{15] and MI{15] are printed. (ii) Here CUM refers to all the CUM values. That is, CUM, — CUM[2}, CUM[3},_—...,- CUM[200] are printed. (iii) GPA[2] refers to the GPA array of the second student. Hence, GPA(2, 1], GPA|2, 2], GPA[2, 3], GPA[2, 4) are printed. | (iv) GPALL, 3] is a single item, the GPA during the junior year of the first student. That is, only GPA{I, 3} is printed. 4.19 An automobile dealership keeps track of the s automobiles in arrays AUTO and PRICE, res; structure in Fig. 4.27, which combines Chevys, new Buicks, new Oldsmobile erial number. and price of each of its pectively. In addition, it uses the data a record structure with pointer variables. The new S, and used cars are listed together in AUTO. The1 DEALER 2 NEW 3° CHEVY a 4 NUMB, 4 PTR ef 3 BUICK — 4 NUMB Ca 4 PTR 3 OLDS 4 NUMB a 4 PTR 2 USED 3 NUMB 3 PTR Fig, 4.27 ely, the number and location of variables NUMB and PTR under USED give, respectiv the list of used automobiles. ‘ro? i if the list of new Buicks in AU (a) How doe on i sera bers of all new Buicks under $10 000. (b) Write a procedure to print serial num (a) Since PTR appears more than once in the record structure, One must use BUICK.PTR ane ference the location of tne list of new Buicks in AUTO. eos (b) One must traverse the list of new Buicks but print out only those Buicks whose P! is less than $10 000. The procedure follows: Procedure P4.19: The data are stored in the structure in Fig. outputs those new Buicks whose price is less 1. Set FIRST := BUICK.PTR. [Location of first clement in Buick list.) 2. Set LAS’ FIRST + BUICK.NUMB - 1. [Location of last element in list.] 3. Repeat for K = FIRST to LAST. If PRICE[K] < 10 000, then: Write: AUTO[K], PRICEIK]. [End of If structure.} [End of loop] 4, Exit. 4.27. This procedure han $10 000. 4.20 Suppose in oe Problem 4.19 the dealership had also wanted to keep track of the accessories o| each automobile, such as air-conditioning, radio, and rusty ing. Si this involves variable-length data, how might this be done? mane This can be accomplished as in Fig. 4.28. That is, besid ; . 4.28, n les AUTO and PRICE, isa arfay POINTER such that POINTERIK] gives the location in an array ReCES ORES i the list of accessories (with sentinel ‘S$$") of AUTO[K). °3 | AMF radio 26 | 02 rR ng | 84 | Rustprooting a5 | sss Fig. 4.28 Arrays Con der the linear arrays XXX(-10: 10), YYY(1935: 1985), ZZZ(35). (a) Find the number . of elements in cach array. (b) Suppose Buse(YYY) = 400 and w = 4 words per memory cell for YYY. Find the address of YYY[1942}, YYY{1977] and YYY{1988). 2 Consider the following multidimensional arrays: X(-5:5, 3:33) Y(3:10, 1:15, 10:20) (a) Find the length of each dimension and the number of elements in X and Y. (b) Suppose Base(Y) = 400 and there are w = 4 words per memory location, Find the effective indices E), E>, Ey and the address of Y[5, 10, 15] assuming (i) Y is stored in major order and (ii) Y is stored in column-major order. «3 An array A contains 25 positive integers. Write.a module which (a) Finds all pairs of elements whose sum is 25. (Lb) Finds the number EVNUM of elements of A which are even, and the number ODNUM of elements of A which are odd. 4.4 Supoose A is a linear array with n numeric values, Write a procedure MEAN(A, N, AVE)4.82 ta arivhmetic rec OF AVCTURE X Of the AS Each stud jents ta eT, Write a module 30 x 6 na class of 305 din ose the test scor is the average of the (n) Finds the average grade for test = final grade (b) Finds the fi [ Ce each student where the final & _ ie five h ehest ie scone ts who have failed. i.e. whose final grade is less than © the number NUM of st 7 . 60 (a) Finds the average of the final grades Pointer Arrays; Record Structures / dure which prints the list of clients for 400 clements, define an y cells following the list of 4.6 Consider the data in Fig, 4.26(0) (a) Write pees ae belonging to LAWYER(K]. (b) ‘Assuming CLIED : pace array FREE such that FREE(K] contains the number clients belonging to LAWYERIK]- ina file of employee records: ber), 2 Name, 2 3. MI (Middle Initial), 2 Address, 3. Street, 2 Salary, 2 Dependents with level numbers, 4,7 The following is a list of entries, 2 SSN(Social Security Num| 1 Employee(200), 3 Last, 3° First, 3 Area, 4 City, 4 State, 4 ZIP, 2 Age (a) Draw the corresponding hierarchical structure. (b) Which of the items are elementary items? (c) Describe a record structure—for example, the data. 48 Consider the data structure in Fig, 4.27. Write a procedure to carry out each of the following: a PL/I structure or a Pascal record—to store (a) Finding the number of new Oldsmobiles selling for under $10 000. (b) Finding the rumber of new automobiles selling for under $10 000. (c) Finding the number of automobiles selling for under $10 000. (d) Listing all automobiles selling for under $10 000. ) (Note: Parts (c) and (d) require only the arrays AUTO and PRICE together with the number of automobiles.) | 4.9 A class of student records is organized as follows: 1 Student(35), 2 Name, 3° Last, 3 First, 3 MI (Middle Initial), 2 Major 2 Test(4), 2 Final, 2 Grade(a) How many el @) Describe a rece ple, a PL/I structure or a Pascal record, to store the data. (e) Describe i 1 of each of the following Write statements: (i) WwW Final{ 15}. (i) Write: iti) Write: Test] 4.10 Consider the data structure in Solved Problem 4.18, Write a procedure which SPA scores (a) Finds the average of the sophomor (b) Finds the numb majors (c) Finds the number of CUM scores exceeding K Arrays Assume that the data in Table 4.1 are stored in linear arrays SSN, LAST, GIVEN, CUM and R (with space for 25 students) and that a vasiable NUM is defined which contains the actual number of students, 4.1 Write a program for each of the following: (a) Listing all students whose CUM is K or higher. (Test the program using K = 3.00.) (b) Listing all students in year L. (Test the program using L = 2, or sophomore.) 4.2, Translate the linear search algorithm into a subprogram LINEAR(ARRAY. LB; UB, ITEM, LOC) which either finds the location LOC where ITEM appears in ARRAY or returns Loc =0. 4.3 Translate the binary search and insertion algorithm into a subprogram BINARY(ARRAY, LB, UB, ITEM, LOC) which finds either the location LOC where ITEM appears in ARRAY or the location LOC where ITEM should be inserted into ARRAY. Table 4.1 * Social Security Nunbei Last Name Given Name CUM Year 21 1-58-1329 ‘Adams | Bruce | 2.55. =| 2 169-38-4248 Bailey Trene L. 3.25 a 16-48-5842 Cheng Kim 3.40 i [_1e7-52-4076 Davis Tohin C, 2.85 2 126-63-6382 Edwards Steven 175 3 135-58-9565 Fox Kenneth 2.80 2 (Contd.)