Title 1

Title 1

Arrays in C 1 Arrays in C An array is simply a homogeneous list of variables (all of the same type). Each variable (called an element) is at a specific position in the list. Positions are indexed, starting at 0. The number of variables an array can hold is called its dimension. The dimension of an array is fixed, set when the array is created. The number of values that are actually stored in an array is called its usage. [email protected] Computer Organization I 2005-2019 WD McQuain Arrays in C 2 Arrays in C Logically valid indices for an array range from 0 to dimension 1. There is no automatic runtime check whether an array index is valid. Accessing an invalid index may or may not result in a runtime error. Accessing an invalid index may or may not result in incorrect results. There is no way, in general, to determine the dimension or the usage of an array. The dimension and usage must be stored in separate variables and passed where needed. [email protected]

Computer Organization I 2005-2019 WD McQuain Creating an Array Statically Arrays in C 3 The first way to create an array variable involves static allocation. That is, the desired dimension is known and specified when the code is written. Creating an array statically simply involves writing an appropriate declaration: #define BUFFERSIZE 256 const int DICESUMS = 11; double X[1000]; // literal constant dimension char Buffer[BUFFERSIZE]; // defined constant dimension int DiceFreq[DICESUMS + 1]; // constant integer expression, // used as dimension As with other variables in C, the elements of an array are NOT automatically initialized. [email protected] Computer Organization I 2005-2019 WD McQuain Arrays in C 4 Creating an Array Dynamically

The second way to create an array variable involves dynamic allocation. That is, the desired dimension is unknown until the program is being executed. Creating an array dynamically requires calling a C library function and requesting the OS to allocate the desired amount of memory to the program: uint32_t *scores = malloc(numScores * sizeof(uint32_t)); double *velocities = malloc(numTrackedObjects * sizeof(double)); Notice that we must specify the number of bytes of memory we need, not the array dimension. [email protected] Computer Organization I 2005-2019 WD McQuain Arrays in C 5 Limitations There is no way to alter the dimension of an array once it is declared. However, we can create a new array of a different dimension and use that instead. When an array is passed to a function, its dimension and/or usage must generally be passed as well... otherwise the function will have to way to determine where the array ends. There are no automatic aggregate operations for arrays in C. - = does not copy the contents one array into another - == is not supported for arrays; at least not the way you'd like - arrays cannot be passed by value to a function (although array names can) [email protected]

Computer Organization I 2005-2019 WD McQuain Arrays in C 6 Accessing Array Elements Array elements are specified by stating the name of the array and the index of the element. double X[1000]; // create an array X[100] = 42; // set value of an element double Z = X[203]; // retrieve value of an alement for (int idx = 0; idx < 1000; idx++) { X[idx] = 0.0; } [email protected] Computer Organization I 2005-2019 WD McQuain Initialization via List Arrays in C 7

As with all variables in C, array cells are not automatically initialized when an array is created: int Primes[5]; // Primes[0:4] are unknown int Evens[5] = {0, 2, 4, 6, 8}; // Evens[0:4] are known int Odds[5] = {1, 3, 5}; // Odds[0:2] are as shown; // rest are 0! int Zeros[10000] = {0}; // Zeros[0:9999] are all 0 int Bads[5] = {1, 3, 5, 7, 9, 11}; // too many initializers! Of course, for arrays of interesting sizes you'll usually initialize via a loop [email protected] Computer Organization I 2005-2019 WD McQuain Arrays as Parameters Arrays in C 8

Passing the name of an array to a function allows the function to modify the elements: #define SZ 5 void fillPrimes( int Primes[] ); Note parameter declaration syntax. int main() { Pass array to fn by name. int Primes[SZ]; fillPrimes(Primes); for (int i = 0; i < SZ; i++) { printf("%3d:%5d\n", i, Primes[i]); } return 0; Fn can modify array passed to it by the caller } void fillPrimes( int Primes[] ) { for (int i = 0; i < SZ; i++) { Primes[i] = i * i + i + 41; } Note use of #define to specify the array dimension at file scope. } [email protected] Computer Organization I 2005-2019 WD McQuain

Out-of-Bounds Array Indices Arrays in C 9 What happens when a statement uses an array index that is out of bounds? First, there is no automatic checking of array index values at run-time (some languages do provide for this). Consider the C code: int A[7]; A[7] = 42; Logically A[7] does not exist. Physically A[7] refers to the int-sized chunk of memory immediately after A[6]. The effect of the assignment statement will be to store the value 42 at that location: Memory A[ 0] A[ 1] A[ 2] A[ 3] A[ 4] A[ 5]

A[ 6] ?? ?? ?? ?? ?? ?? ?? 42 Clearly this is undesirable. What actually happens as a result depends upon what this location is being used for [email protected] Computer Organization I 2005-2019 WD McQuain Arrays in C 10 A Warning You may see examples like this that purport to show a way to determine the dimension of an array: void f(int A[]) {

int dimension = sizeof(A) / sizeof(A[0]); ... } this does not work Be aware that if applied to an array passed to a function, or an array that's allocated dynamically. Try it. The sizeof() trick works if used in the same scope as the declaration of the array, in which case it is hardly needed. There are many fairly stupid discussions of this available online, and even in some C programming textbooks. [email protected] Computer Organization I 2005-2019 WD McQuain Memory Access Errors Arrays in C 11 Consider the possibilities. The memory location A[7] may: - store a variable declared in your program - store an instruction that is part of your program (unlikely on modern machines) - not be allocated for the use of your program In the first case, the error shown on the previous slide would cause the value of that variable to be altered. Since there is no statement that directly assigns a value to that variable, this effect seems very mysterious when debugging. In the second case, if the altered instruction is ever executed it will have been replaced by a nonsense instruction code. This will (if you are lucky) result in the system killing your program for attempting to execute an illegal instruction. In the third case, the result depends on the operating system you are using. Some

operating systems, such as Windows 95/98/Me do not carefully monitor memory accesses and so your program may corrupt a value that actually belongs to another program (or even the operating system itself). Other operating systems, such as Windows NT/2000/XP or UNIX, will detect that a memory access violation has been attempted and suspend or kill your program. [email protected] Computer Organization I 2005-2019 WD McQuain Example: Some Array Manipulations #include #include #include #include #define SZ 10 Arrays in C 12 // for time() // for srand(), rand() // constant for array dimension void fillArray(uint32_t List[], uint32_t Sz); void Sort(uint32_t List[] , uint32_t Usage); // fn declarations int main() { } [email protected] int A[SZ];

// allocate space for array fillArray(A, SZ); // fill array with random values for (uint32_t i = 0; i < SZ; i++) { printf("%3d:%5d\n", i, A[i]); } // print original array Sort(A, SZ); // sort the array for (uint32_t i = 0; i < SZ; i++) { printf("%3d:%5d\n", i, A[i]); } return 0; // print the sorted array // more to come . . . Computer Organization I 2005-2019 WD McQuain Example: Initializing an Array Arrays in C 13 // Writes Size random integer values in [0, 1000) into List[]

// // Pre: // List[] has dimension >= Size // Post: // List[0:Size-1] have been set to random values in // the range 0 to 999, inclusive. // void fillArray(uint32_t List[], uint32_t Size) { srand( (uint32_t) time(NULL) ); // initialize random // generator for (uint32_t pos = 0; pos < Size; pos++) { List[pos] = rand() % 1000; } } // more to come . . . [email protected] Computer Organization I 2005-2019 WD McQuain Example: Sorting an Array Arrays in C 14 // Uses InsertionSort algorithm to put elements of List[] into // ascending order.

// void Sort(uint32_t List[], uint32_t Usage) { uint32_t unsortedFront = 1; while ( unsortedFront < Usage ) { uint32_t currElement = List[unsortedFront]; uint32_t probeLocation = unsortedFront; while ( probeLocation > 0 && List[probeLocation-1] > currElement) { List[probeLocation] = List[probeLocation-1]; probeLocation--; } List[probeLocation] = currElement; unsortedFront++; } } [email protected] Computer Organization I 2005-2019 WD McQuain Example: Squeezing out Odd Values Arrays in C 15 Problem: take an array of integer values and eliminate all the odd values from the array, leaving only the even values, and keeping them in their original relative order, but leaving no "gaps" within the array For example, we would transform the first array below into the second: 484 501 122

777 484 122 24 204 29 24 543 204 Obviously, the algorithm must report the number of elements in the modified array, since that will likely be smaller than the number of elements in the original array. We also do not want to make use of a second array; that would waste memory and entail too much extra copying of data. [email protected] Computer Organization I 2005-2019 WD McQuain Example: Squeezing out Odd Values Arrays in C 16 Here's one approach. 484

501 122 Move Trailer to the first odd value. If there isn't one, we are done. 777 29 24 543 204 Set Leader to the first value after Trailer. If Leader points to an even value, copy that value to Trailer's location advance Trailer 484 122 122 777 29

24 543 204 Whether Leader points to an even value or not, step Leader ahead one spot. [email protected] Computer Organization I 2005-2019 WD McQuain Example: Squeezing out Odd Values 484 122 122 777 Arrays in C 17 29 24 543 204 Whether Leader points to an odd value, just step it forward and again 484

122 122 777 29 24 543 204 Now Leader points to an even value, so copy it and advance Trailer and Leader: 484 [email protected] 122 24 777 Computer Organization I 29 24 543 204

2005-2019 WD McQuain Example: Squeezing out Odd Values Arrays in C 18 // Takes an array of integers and removes all the odd ones, // without altering the order of any of the even values. // // Pre: // List[] has dimension >= Usage // Post: // All the even values are listed in successive cells at the // beginning of List[], in their original relative order. // Returns: // the number of even values in the list // int32_t squeezeOutOdds(int32_t List[], uint32_t Usage) { uint32_t Trailer = 0; // Move Trailer to first odd value, if any. while ( Trailer < Usage && List[Trailer] % 2 == 0 ) ++Trailer; // Check for case there are no odd values in List[] if ( Trailer == Usage ) return Trailer; // . . . [email protected] Computer Organization I

2005-2019 WD McQuain Example: Squeezing out Odd Values Arrays in C 19 uint32_t Leader = Trailer + 1; // Walk Leader to end of List[] while ( Leader < Usage ) { // If Leader is at an even value, move it forward; // advance Trailer if ( List[Leader] % 2 == 0 ) { List[Trailer] = List[Leader]; ++Trailer; } // Always advance Leader ++Leader; } // When done, Trailer is one past the final even value, // so it equals the number of even values that are left. return Trailer; } [email protected] Computer Organization I 2005-2019 WD McQuain

Recently Viewed Presentations

  • Huntsville City Schools School Accountability Including Report Cards

    Huntsville City Schools School Accountability Including Report Cards

    Alabama Association of School Boards (AASB) Business Education Alliance (BEA) Council for Leaders in Alabama Schools (CLAS) School Superintendents of Alabama (SSA) Governor's Office. Alabama State Department of Education (ALSDE) PROTOTYPE Report Card.
  • The Next Frontier in TAR: Choose Your Own Algorithm

    The Next Frontier in TAR: Choose Your Own Algorithm

    The Next Frontier in TAR: Choose Your Own Algorithm. LegalTech New York 2017. Presented by . Dr. David Grossman, Georgetown University. Tara Emory, Esq., PMP ...
  • ULTRACAPACITORS - 123seminarsonly.com

    ULTRACAPACITORS - 123seminarsonly.com

    Ultracapacitors can store . 5 percent . as much energy as a modern lithium-ion battery. 5000 farads measure about 5 centimeters by 5 cm by 15 cm, which is an amazingly . high capacitance relative to its volume. Can effectively...
  • IFSC on the Scene: An Update on Food

    IFSC on the Scene: An Update on Food

    and last but not least you will hear from our friend and guide Walter Willis, former president of IFSC, on the work being done on compost related policy. And we'll have time for Q&A at the end, so please do...
  • Format of Exam #3 5 Listening IDs: Composer,

    Format of Exam #3 5 Listening IDs: Composer,

    Sample terms to know for Exam #3 Monody Opera Caccini Basso continuo figured bass notation Stile rappresentativo concerto grosso concertino Peri Ripieno ritornello recitativo secco Recitativo accompagnato subject sonata da camera sonata da chiesa sinfonia minuet and trio Messiah Florentine...
  • Cereal Box Book Report - Mrs. Eigenman

    Cereal Box Book Report - Mrs. Eigenman

    Grading Checklist for Cereal Box Book Report Front of the Box _____ / 15 . Invented Cereal name relates to the book. Picture relates to the book. Completed neatly/shows effort Right Side _____ / 15. Describes the Main Characters using...
  • Positive and Negative Numbers

    Positive and Negative Numbers

    Tahoma MS Pゴシック Arial Wingdings Calibri Times New Roman Blends 1_Blends Grade 8 Integers! What You Will Learn Definition Definition Definition Definition Definition Negative Numbers Are Used to Measure Temperature Negative Numbers Are Used to Measure Above and Below Sea...
  • The Arminghall Henge in space and time

    The Arminghall Henge in space and time

    The Arminghall Henge in space and time Willem Beex and John Peterson Location The first view of the Henge Photographed by Wing Commander Insall, V.C on 18th June 1928 Published: Antiquity 3.2 (1929) N Neolithic and Bronze Age environment Landscape...