Programming I EECS 168
Popular in Course
Popular in Elect Engr & Computer Science
verified elite notetaker
This 32 page Class Notes was uploaded by Melissa Metz on Monday September 7, 2015. The Class Notes belongs to EECS 168 at Kansas taught by Staff in Fall. Since its upload, it has received 11 views. For similar materials see /class/186804/eecs-168-kansas in Elect Engr & Computer Science at Kansas.
Reviews for Programming I
Report this Material
What is Karma?
Karma is the currency of StudySoup.
Date Created: 09/07/15
L8Arrays Read Chpt 7 Suppose Prof LazyCrazy decides 0 There needs to be 104 homework assignments and 57 tests for EEC8168 O From time to time we may increase or decrease the numbers so your code needs to be written very generally 0 You need to implement a program to compute the average of homeworks and tests 0 You need to carefully format output reports so that we can have say 10 scores per line in regular labeled columns Rather than using variables hwl hw2 hw3 of int type we need a way to de ne and organize large numbers of objects of the same type Solution Use arrays Array It is an ordered collection of data of the same type organized in such a way that its elements data can be accessed through indexing Some Advantages in using Array 0 Used to store and organize large number of data objects 0 Allow repeated execution of the same data 0 Allow random accessing of data through indexing Array declaration Syntax typename arraynamesizeOfArray Base type gt typename Array name gt arrayname Array size gt sizeOfArray Examples int homework 104 char grade5 double arrayExample8 int numStudents examScores3 thcoreslO Consider the declaration int homework104 homework 0 l 2 103 Remarks 0 104 independent integer variables are allocated 0 Rather than each variable having its own name all variables share the same array name and use integer offsets called an index from the start to identify each one o homework0 is the rst integer variable homeworkl is the second homework103 is the 104th and the last Storage Array elements are stored contiguously in memory although you don t normally have to think about that Properties 0 O O O The size of an array is given in square brackets when the array name is rst declared Once declared the size of an array cannot be changed The size of the array must be known at compile time It can also involve an expression const int numBeansPerPod 20 const int maXNumPods 30 int podHoldernumBeansPerPodmaXNumPods When we study dynamic memory allocation later we will see that arrays can be created with a size computed at run time but even then once allocated its size can not be changed Do not confuse the use of brackets at declaration time om their meaning at access time double weights20 20 is size of array weights3 13 3 refers to the 4th element Indices may be integer variablesexpressions int which 7 weightswhich 13 weights2which3 21 Referencing an Array arraynameindeX indexed variable Array index 0 S index S sizeOfArray 1 Warning Watch out for index outofrange in array index S O or index 2 sizeOfArray 1 Example The array examScores has indexed variables examScoresO examScores l examScoresZ Accessing an Array Element Each element in an array can be used exactly as a normal variable of the base type h0mew0rkl l 97 h0meworkl3 76 int averageOfl lAndl3 05 h0mew0rkl l h0mew0rkl3 Manipulating Array with ForLoop for int index 0 index lt sizeOfArray index statementl statement2 Example Program using an Array Reads in 5 scores and shows how much each score differs om the highest score include lti0streamgt int main using namespace std int i score5 max cout ltlt quotEnter 5 scoresnquot cin gtgt score0 max score0 for i 1 i lt 5 i cin gtgt scorei if scorei gt max max scorei max is the largest of the values score0 scorei read in array var cout ltlt quotThe highest score is quot ltlt max ltlt endl ltlt quotThe scores and theirnquot ltlt quotdifferences from the highest arenquot for i O i lt 5 i output array var cout ltlt scorei ltlt quot off by quot ltlt max scorei ltlt endl return 0 Initializing Array Variables 0 Recall that a simple variable can be initialized in one statement Example int sum 0 o A variable of array struct or class type is a compound variable A compound variable can also be initialized with one statement Example struct initexample 1nt a int b initexample X 1 2 0 An array can be initialized like we initialize a struct int children3 2 12 1 o The compiler can also count for you int b 168 268 368 This is equivalent to int b3 168 268 368 Q What if we have the following declaration int alO 5 5 It Will create an array a With 10 elements and initialize a0 to 5 al to 5 and a2 through a9 to 0 InitializeProcess Arrays with forloops const int numBuckets 10 int bucketCountnumBuckets for int i0 i lt numBuckets i bucketCounti 0 initialize array elts to 039s double score cin gtgt score assume 0ltscorelt100 double threshhold 900 for int j numBuckets l j gt 0 j Be careful of array indices if score gt threshhold bucketCountj break threshhold 100 Data Storage in Memory A computer s memory is like a long list of numbered locations called bytes The numbers are called addresses and the information written there is either some program s instructions or data Every variable Whether the type is builtin or constructed by the programmer enum class struct or array has a location Where the variable starts and a number of bytes necessary to hold the variable that is determined by the type of the variable Every variable has an address and a type Array variables are represented the same way except they must be stored in consecutive locations When an array is declared the compiler will decide Where in memory to put the array The size of an array is the DeclaredSize sizeofArrayType Consider an array a of int type int a6 Display 93 An Array in Memory int a6 driveu 6 aEO 1022 1023 31 Ma 656M1er gasz 1024 aO MW payi 1025 1 2W ma3 e 1026 a quot W 1027 2x3 6 ZM a m 1028 am t ema aml 18 am 1031 1032 3 71322 a ma Maiafad 1033 1034 am gamut a6 5 41 01116 variabl named stuff omc YuriubIC named more Mme WZE W of W11 e eza lt 7 394 m 1449er mm a 7 w 4 Mia mewe awe 15 Arrays in Functions An indexed variable is just a variable Whose type is the base type of the array and may be used anywhere any other variable Whose type is the base type of the array might be used int i n alO void myfunctionint n myfunctionn myfunctiona3 Passing Array Elements t0 Function void doWeirdThingsint a int b intamp c a2ab b2b a cab2 void callWeird int X 7 int myArray3 10 20 30 doWeirdThingsX myArrayO myArray2 Array as Function Arguments It is possible to use an entire array as a formal parameter for a function A function can have a formal parameter for an entire array that is neither a callbyvalue nor a callbyreference parameter This is a new parameter type called an array parameter This is not callbyvalue because we can change the array when passed this way This is not callbyreference because we cannot change the complete array by a single assignment when passed this way While this is not callbyreference the behavior is like callbyreference since we can change individual array elements by the called function Passing Array to Function Computing the average of our 104 homework scores Q void myGrader int h0mew0rk 104 double avg averageh0mew0rk How do we implement the function average Consider double averageint gradeslO4 double sum 00 for int i O i lt 104 i sum gradesi return sum104 It works but what happens when we have 107 or 93 homeworks Q Do we have to write a separate average routine for each array size Good News 0 No you don t have to write separate average routines 0 C doesn t pay any attention to the size that you declare for the array in the formal parameter It just assumes you know what you re doing This will be a little different when we get to multiply dimensioned arrays but let s not think about that right now The prototype would normally be written instead as double averageint grades D In other words we just tell the compiler that an array of integers of some size will be passed Q But how do we implement the general average routine if we don t know the size A common convention is to pass the size as a parameter immediately following the array double averageint grades int nGrades Then we would use this as void myGrader int homeworklO4 int exams5 7 int ages32 double angW averagehomework 104 double angxam averageexams57 double angge averageages32 Remarks 0 Arrays can never be passed by value They are effectively passed by reference although the CC terminology is to say it is passed by address In the book this is also described as array argumentparameter passing 0 The elements of array arguments changed inside a function will also change the array arguments in the calling environment just like pass by reference parameters const Modi er for Array 0 One way to prevent unintended array modi cation or really to declare that a function promises not to modify an array is to use the const modi er 0 An array parameter that has been modi ed With const is a constant array parameter Example double averagec0nst int grades D o If const is used to modify an array parameter 1 const is used in both the function declaration and definition to modify the array parameter 2 The compiler will issue an error if you write code that changes the values stored in the array parameter 0 If a function With a constant array parameter calls another function using the const array parameter as an argument 1 The called function must use a constant array parameter as a placeholder for the array 2 The compiler Will issue an error if a function is called that does not have a const array parameter to accept the array argument Example void showthewor1d const int a int sizeofa cout ltlt quotArray values arenquot for int i O i lt sizeofa ai Error cout ltlt ai ltlt quot quot cout ltlt endl More Example Suppose I m debugging my average routine and I want to use a display function for arrays void displayostreamamp os int nums int size os ltlt for int i O i lt size i os ltlt numsi if i lt size1 os ltlt 0s Cn77 double averageconst int values int nValues displayos values nValues double sum 00 for int i 0 i lt nValues i sum valuesi return sumnValues Q What Will happen Since the int array nums is not a constant array parameter in the display function When called by the average function using a constant array parameter value an error message Will be generated because display could possibly change the array parameter Warning When passing arrays through several layers of functions be sure that const arrays are only passed on Where a const array parameter has been declared More Warning Even though a function may return a value of primitive class type functions can not return array Parameter Passing and Type Conversion An implication of no pass by value means type conversion rules on parameter passing are a little different for array parameters Example The following code is fine With simple primitive type parameters void funcint a double b int c void caller mm 10 y 20 double q 11 funcX y staticcastltintgtq Q What if the function prototype uses passby reference Consider void funcintamp a doubleamp b intamp c void caller int X 10 y 20 double q 11 funcX y staticcastltintgtq Problem Since arrays are passed by address we have similar problems void funcint a double b int c void caller int X10 y20 double q4 funcX y staticcastltintgtq Problem Searching Given a partially lled array a of integers and an integer key target Returns the smallest index such that aindex target if exists otherwise returns 1 Sequential Search Algorithm a l 2 sizel l l O l l target int searchconst int a int numberused int target int index O bool found false While lfound ampamp index lt numberused if target aindex found true else index if found return index else return l 20 Sorting Given a partially lled array a of integers Rearrange the elements in a such that aO S al S a2 S S asizel Selection Sort Pseudocode for index 0 to size2 do select smallest element among aindeX asizel swap smallest element found With aindex endfor Example NNNNW wwwoooo mmaocx oxoooobolx oooxulmu 21 Implementation Se1ecti0n sort include lti0streamgt void llarrayint a int size intamp numberused Fill the array om aO through anumberusedl With nonnegative integers read from the keyboard size is the declared size of the array and numberused is the number of values stored in a void sortint a int numberused Sort a such that aO lt al lt lt anumberusedl void swapvaluesintamp v1 intamp v2 Interchanges the values of VI and v2 int indexofsmallestconst int a int startindex int numberused Returns index i such that ai is the smallest of the values astartindeX astartindex1 anumberused l 22 void s0rtint a int numberused int indexofnextsma11est for int index 0 index lt numberused 1 index indexofnextsma11est indexofsma11esta index numberused swapva1uesaindex aindex0fnextsma11est void swapva1uesintamp V1 intamp V2 int temp temp V1 V1 V2 V2 temp 23 int indexofsma11estconst int a int startindex int numberused int min astartindex indexofmin startindex for int index startindex 1 index lt numberused index if aindex lt min min aindex index0fmin index return index0fmin Insertion Sort Pseudocode for index 1 to size1 d0 insert aindex into a0 aindex1 endfor Example 1100000 OOONNN OOUIKJIKJIKJI NNUJUJUJ wwooooo 24 Bubble Sort Pseudocode for i 1 to size1 do for index 1 to sizei do if aindex lt aindeX1 swapaindex aindex 1 endfor Example MWWMNNNGOOOOOOOO UIUIUIUIUIUIGNNNNOOOO NNNNMWWWMWWWWM GNOGNGNGNGUIUIUIUIQONNN OOOOOOOOOOOOOOOOOOOOUIUIUIU 25 Searching an Ordered sorted Array Given a sorted array a10whigh and a key X Return array index k low E k S high such that ak X Otherwise return 1 Binary Search a 10W mid high mid 10W high2 if X lt amid search X in a10wmid1 if X gt amid search X in amid1high if X amid return mid if notf0und return 1 26 int binarySearchconst int a int 10W int high int X int mid int notf0und 1 while low lt high mid 10W high 2 if X lt amid high mid 1 else if X gt amid 10W mid 1 else return mid return n0tf0und 27 MultiDimensional Array C allows arrays to be declared With multiple index values Syntax typename arraynamedim l dim2 dimk Example int A2 4 array With 8 elements char grades5lO 3 array With 150 eleemnts Remarks 0 The above declaration declares a 2dim array A of int type 0 The array A has two index values The rst index ranges from 0 to l and the second index ranges from 0 to 3 0 Each index must be enclosed in its own brackets o The array A can be visualized as an array of 2 rows and 4 columns With 24 8 elements 0 The indexed variables for scores are A00 Alolllla Alollzla A03 A10A11A12A13 28 MultiDimensional Array Parameters 0 Recall that the size of an array is not needed When declaring a formal parameter Example void displaylineconst char a int size 0 The size of the rst dim of a multidimensional array needs not be speci ed but the remaining dimension sizes must be completely speci ed in the parameter declaration Example void display pageconst char page 100 int sizediml Using Multi Dimensional Array Consider we need to read in the quiz scores of a number of students compute the average of the student s quiz scores compute the average of each quiz among all the students and then output all these information Use a 2dim array int grade numberstudents numberquizzes to store the quiz scores of each student 29 TwoDimensional Array part I of 3 Reads quiz scores for each student into the twodimensiona7 array grade but the input code is not shown in this disp7ay Computes the average score for each student and the average score for each quiz Disp7ays the quiz scores and the averages inc39lude ltiostreamgt 139nc1ude ltiomanipgt const int NUMBERSTUDENTS 4 NUMBERQUIZZES 3 void computestaveconst int grade NUMBERQUIZZES doub7e staveEJ Precondition C7oba7 constants NUMBEILSTUDENTS and NUMBERgQUIZZES are the dimensions of the array grade Each of the indexed variab7es gradestnum 1 quiznum l contains the score for student stnum on quiz quiznum Postcondition Each stavestnum l contains the average for student number stunum void computequizaveconst int grade NUMBERWQUIZZES doub7e quizave Precondition C7oba7 constants NUMBER5TUDENTS and NUMBERQUIZZE5 are the dimensions of the array grade Each of the indexed variab7es gradestnum 1 quiznum l contains the score for student stnum on quiz quiznum Postcondition Each quizavequiznum l contains the average for quiz number quiznum void di Sp1ayconst int grade NUMBERQUIZZES const doub7e stave const doub7e qui zave Precondition Global constants NUMBERSTUDENT5 and NUMBER0UIZZES are the dimensions of the array grade Each of the indexed variab7es gradestnum 1 quiznum 1 contains the score for student stnum on quiz quiznum Each stavestnum 1 contains the average for student stunum Each quizavequiznum 1 contains the average for quiz number quiznum Postcondition A77 the data in grade stave and quizave has been output int main using namespace std int gradeNUMBERSTUDENTS NUMBERJJUIZZES doub7e staveNUMBERSTUDENTS doub7e quizaveNUMBERQUIZZES ltThe code For fiHing the array grade goes here but is not showngt TwoDimensional Array part 2 of 3 computestavegrade stave computequizavegrade quizave disp1aygrade stave quizave return 0 void computestaveconst int gradeNUMBERQUIZZES doub7e stave for int stnum 1 stnum lt NUMBERSTUDENTS stnum Process one st num doub7e sum 0 for int quizinum 1 quizinum lt NUMBER QUIZZES quizinum sum sum gradestnum lquiznum l sum contains the sum of the quiz scores for student number stinum st avestvnum1 sumNUMBER QUIZZES Average for student stnum is the va7ue of stavestnum 1 void computequizaveconst int gradeNUMBERQUIZZES doub7e quizave for int quiznum 1 quiznum lt NUMBERQUIZZES quiznum Process one quiz for a7 students doub7e sum 0 for int stnum 1 stnum lt NUMBERSTUDENTS stnum sum sum gradestnum lquizinumel sum contains the sum of a1 student scores on quiz number quiznum quizavequiznum 1 sumNUMBERSTUDENTS Average for quiz quizinum is the value of quizavequiznuml TwoDimensional Array part 3 of 3 Uses iostream and iomanip void dispiayCconst int gradeNUMBERQUIZZES const doub7estfave const doubiequizave using namespace std coutsetfiosfixed coutsetfiosshowpoint coutprecisionl cout ltlt setwlO ltlt quotStudentquot ltlt setw5 ltlt quotAvequot ltlt setwlS ltlt quotQuizzesnquot For int stinum 1 stinum lt NUMBER75TUDENTS stinum Di5p7ay for one stnum cout ltlt setwlO ltlt stnum ltlt setw5 ltlt stavestnum1 ltlt quot quot fbr int quizinum l quizinum lt NUMBERiQUIZZES quizfnum cout ltlt setw5 ltlt grade5tnum 1quiznum 1 cout ltlt endi cout ltlt quotQuiz averages quot for int quizinum l quizinum lt NUMBERiQUIZZES quiznum cout ltlt setw5 ltlt quiziavequizinum l cout ltlt endi Sample Dialogue ltThe dialogue for filling the array grade is not showngt Student Ave Quizzes 1 100 10 10 10 2 10 2 O 1 3 77 8 6 9 4 73 8 4 10 Quiz averages 70 50 75