Optional Textbook Readings: CP:AMA 8.1, 9.3, 12.1, 12.2, 12.3
The primary goal of this section is to be able to use arrays.
CS 136 Winter 2022 07: Arrays 1
Copyright By PowCoder代写加微信 assignmentchef
C only has two built-in types of “compound” data storage: • structures
int my_array[6] = {4, 8, 15, 16, 23, 42};
An array is a data structure that contains a fixed number of
elements that all have the same type.
Because arrays are built-in to C, they are used for many tasks where lists are used in Racket, but arrays and lists are very different. In Section 11 we construct Racket-like lists in C.
CS 136 Winter 2022 07: Arrays 2
int my_array[6] = {4, 8, 15, 16, 23, 42};
To define an array we must know the length of the array in advance
(we address this limitation in Section 10).
Each individual value in the array is known as an element. To
access an element, its index is required.
The first element of my_array is at index 0, and it is written as
my_array[0].
The second element is my_array[1] and the last is my_array[5].
In computer science we often start counting at 0.
CS 136 Winter 2022 07: Arrays 3
example: accessing array elements
Each individual array element can be used in an expression as if it was a variable.
In addition, the index of the array can be an expression.
int a[6] = {4, 8, 15, 16, 23, 42};
int j = a[0];
int *p = &a[j – 1];
a[2] = a[a[0]];
// p points at a[3]
// a[2] is now 23
// a[1] is now 9
CS 136 Winter 2022
07: Arrays 4
example: arrays & iteration
Arrays and iteration are a powerful combination.
int a[6] = {4, 8, 15, 16, 23, 42};
int sum = 0;
for (int i = 0; i < 6; ++i) {printf(“a[%d] = %d
“, i, a[i]);sum += a[i];printf(“sum = %d
“, sum); CS 136 Winter 202207: Arrays 5Array initializationArrays can only be initialized with braces ({}).int a[6] = {4, 8, 15, 16, 23, 42};a = {0, 0, 0, 0, 0, 0}; // INVALIDa = ??? ; // INVALIDOnce defined, the entire array cannot be mutated at once, and thelength cannot change. Only individual elements can be mutated.If there are not enough elements in the initialization braces, the remaining values are initialized to zero.int b[5] = {1, 2, 3};int c[5] = {0};// b[3] & b[4] = 0// c[0]…c[4] = 0 CS 136 Winter 202207: Arrays 6Character arrays can be initialized with double quotes (“) for convenience.The following two definitions are equivalent:char a[3] = {‘c’, ‘a’, ‘t’};char b[3] = “cat”; In this example, a and b are character arrays and are not valid strings. This will be revisited in Section 09. CS 136 Winter 2022 07: Arrays 7Like variables, the value of an uninitialized array depends on the scope of the array:int a[5]; // uninitialized• uninitialized global arrays are zero-filled.• uninitialized local arrays are filled with arbitrary (“garbage”) values from the stack. CS 136 Winter 2022 07: Arrays 8Array lengthC does not explicitly keep track of the array length as part of thearray data structure.You must keep track of the array length separately.To improve readability, the array length is often stored in a separate variable.int a[6] = {4, 8, 15, 16, 23, 42};const int a_len = 6;CS 136 Winter 2022 07: Arrays 9It might seem better to use a constant to specify the length of an array.const int a_len = 6;int a[a_len] = {4, 8, 15, 16, 23, 42}; // NOT IN CS136This would appear to be a “better style”.However, the syntax to do this properly is outside of the scope of this course (see following slide).In this course, always define arrays using numbers. It is okay to have these “magic numbers” appear in your assignments.int a[6] = …;CS 136 Winter 2022 07: Arrays 10 Many programming guides recommend using the unsigned integer type size_t instead of an int to loop through an array.for (size_t i = 0; i < a_len; ++i) { … }For example, array lengths may be greater than INT_MAX.Because size_t is unsigned, you have to be careful when looping backwards through an array:for (size_t i = a_len – 1; i >= 0; –i) { … } // infinite loop: i will never be negative
In this course we are not going to use advanced int types, including size_t.
CS 136 Winter 2022 07: Arrays 11
A preferred syntax to specify the length of an array is to define a macro.
#define A_LEN 6
int main(void) {
int a[A_LEN] = {4, 8, 15, 16, 23, 42};
In this example, A_LEN is not a constant or even a variable. A_LEN is a preprocessor macro. Every occurrence of A_LEN in
the code is replaced with 6 before the program is run.
CS 136 Winter 2022 07: Arrays 12
C99 supports Variable Length Arrays (VLAs), where the length of an uninitialized local array can be specified by a variable (or a function parameter) not known in advance. The size of the stack frame is increased accordingly.
int some_function(int n) {
int m = n * 2;
int a[m];// length determined at run time
This approach has many disadvantages and in more recent versions of C, this feature was removed (made optional). You are not allowed to use VLAs in this course. In Section 10 we see a better approach.
CS 136 Winter 2022 07: Arrays 13
Theoretically, in some circumstances sizeof can be used to determine the length of an array.
int len = sizeof(a) / sizeof(a[0]);
The CP:AMA textbook uses this on occasion.
However, in practice (and in this course) this should be avoided, as the sizeof operator only properly reports the array size in very specific circumstances.
CS 136 Winter 2022 07: Arrays 14
Array size
The length of an array is the number of elements in the array.
The size of an array is the number of bytes it occupies in memory. An array of k elements, each of size s, requires exactly k × s bytes.
In the C memory model, array elements are adjacent to each other. Each element of an array is placed in memory immediately after the previous element.
If a is an integer array with six elements (int a[6]) the size of a is: (6×sizeof(int)) = 6×4 = 24.
Not everyone uses the same terminology for length and size.
CS 136 Winter 2022 07: Arrays 15
example: array in memory
int a[6] = {4, 8, 15, 16, 23, 42};
printf(“&a[0] = %p … &a[5] = %p
”, &a[0], &a[5]);
&a[0] = 0x5000 … &a[5] = 0x5014
contents (4 bytes)
0x5000 …0x5003
0x5004 …0x5007
0x5008 …0x500B
0x500C …0x500F
0x5010 …0x5013
0x5014 …0x5017
CS 136 Winter 2022 07: Arrays 16
The array identifier
An array does not have a “value” in C. When an array is used by itself in an expression, it evaluates (“decays”) to the address of the array (&a), which is also the address of the first element (&a[0]).
int a[6] = {4, 8, 15, 16, 23, 42};
trace_ptr(a);
trace_ptr(&a);
trace_ptr(&a[0]);
a => 0x5000
&a => 0x5000
&a[0] => 0x5000
Even though a and &a have the same value, they have different types, and cannot always be used interchangeably.
CS 136 Winter 2022 07: Arrays 17
Dereferencing the array (*a) is equivalent to referencing the first element (a[0]).
int a[6] = {4, 8, 15, 16, 23, 42};
trace_int(a[0]);
trace_int(*a);
CS 136 Winter 2022 07: Arrays 18
Passing arrays to functions
When an array is passed to a function, only the address of the array
is copied into the stack frame.
This is more efficient than copying the entire array to the stack.
Typically, the length of the array is unknown to the function, and is a separate parameter.
There is no method of “enforcing” that the length passed to a function is valid.
Functions should require that the length is valid, but there is no way for a function to assert that requirement.
CS 136 Winter 2022 07: Arrays 19
example: array parameters
int sum_array(int a[], int len) {
int sum = 0;
for (int i = 0; i < len; ++i) {sum += a[i]; }return sum; } int main(void) { int my_array[6] = {4, 8, 15, 16, 23, 42}; trace_int(sum_array(my_array, 6)); sum_array(my_array, 6) => 108
Note the parameter syntax: int a[]
and the calling syntax: sum_array(my_array, 6).
CS 136 Winter 2022 07: Arrays 20
example: “pretty” print an array
// pretty prints an array with commas, ending with a period
// requires: len > 0
void print_array(int a[], int len) {
assert(len > 0);
for (int i = 0; i < len; ++i) { printf(“, “); printf(“%d”, a[i]); printf(“.
“); int main(void) { int a[6] = {4, 8, 15, 16, 23, 42}; print_array(a, 6); 4, 8, 15, 16, 23, 42. CS 136 Winter 2022 07: Arrays 21 C allows you to specify the intended length of the array in the parameter, but it is ignored.void calendar(int days_per_month[12]) {In this example, the 12 is ignored. The function may be passedan array of arbitrary length.Similarly, some prefer to pass the length of the array first:void f(int len, int a[len]) {But since the [len] is ignored (and not enforced) it is morecommon to pass the array first. CS 136 Winter 2022 07: Arrays 22As we have seen before, passing an address to a function allows the function to change (mutate) the contents at that address.void array_negate(int a[], int len) {for (int i = 0; i < len; ++i) {a[i] = -a[i];It’s good style to use the const keyword to both prevent mutation and communicate that no mutation occurs.int sum_array(const int a[], int len) {int sum = 0;for (int i = 0; i < len; ++i) {sum += a[i]; }return sum; } CS 136 Winter 2022 07: Arrays 23Array within a structureBecause a structure can contain an array:struct mystruct {int big[10000];It is especially important to pass a pointer to such a structure, otherwise, the entire array is copied to the stack frame.int very_slow(struct mystruct s) {int much_faster(struct mystruct *s) { CS 136 Winter 2022 07: Arrays 24Pointer arithmeticWe have not yet discussed any pointer arithmetic.C allows an integer to be added to a pointer, but the result may notbe what you expect.If p is a pointer, the value of (p+1) depends on the type of thepointer p.(p+1) adds the sizeof whatever p points at.According to the official C standard, pointer arithmetic is only valid within an array (or a structure) context. This becomes clearer later.CS 136 Winter 2022 07: Arrays 25Pointer arithmetic rules• When adding an integer i to a pointer p, the address computed by (p + i) in C is given in “normal” arithmetic by:p + i × sizeof(∗p).• Subtracting an integer from a pointer (p – i) works in the• Mutable pointers can be incremented (or decremented).++pisequivalenttop = p + 1. CS 136 Winter 2022 07: Arrays 26• You cannot add two pointers.• A pointer q can be subtracted from another pointer p if the pointers are the same type (point to the same type). The value of (p-q) in C is given in “normal” arithmetic by:(p − q)/sizeof(∗p). Inotherwords,ifp = q + itheni = p – q.• Pointers (of the same type) can be compared with the comparison operators: <, <=, ==, !=, >=, >
(e.g., if (p < q) …). CS 136 Winter 2022 07: Arrays 27Pointer arithmetic and arraysPointer arithmetic is useful when working with arrays.Recall that for an array a, the value of a is the address of the first element (&a[0]).Using pointer arithmetic, the address of the second element &a[1] is (a + 1), and it can be referenced as *(a + 1).The array indexing syntax ([]) is an operator that performs pointer arithmetic.a[i] is equivalent to *(a + i).CS 136 Winter 2022 07: Arrays 28 C does not perform any array “bounds checking”.For a given array a of length l, C does not verify that a[j] isvalid(0≤j
loops from 1 … len-1 and represents the
“next” element to be replaced
loops from i … 1 and is “inserting”
the element that was at a[i] until it
reaches the correct position
CS 136 Winter 2022 07: Arrays 40
is an example of a “divide & conquer“ algorithm. First, an element is selected as a “pivot” element.
The list is then partitioned (divided) into two sub-groups: elements less than (or equal to) the pivot and those greater than the pivot.
Finally, each sub-group is then sorted (conquered).
Quicksort is also known as partition-exchange sort or Hoare’s quicksort (named after the author).
CS 136 Winter 2022 07: Arrays 41
We have already seen the implementation of quick sort in
(define (quick-sort lon)
(cond [(empty? lon) empty]
[else (define pivot (first lon))
(define less (filter (lambda (x)
(<= x pivot)) (rest lon)))(define greater (filter (lambda (x)(> x pivot)) (rest lon)))
(append (quick-sort less)
(list pivot)
(quick-sort greater))]))
For simplicity, we select the first element as the “pivot”. A more in-depth discussion of pivot selection occurs in CS 240.
CS 136 Winter 2022 07: Arrays 42
In our C implementation of quick sort, we:
• select the first element of the array as our “pivot”
• move all elements that are larger than the pivot to the back of
• move (“swap”) the pivot into the correct position
• recursively sort the “smaller than” sub-array and the “larger than” sub-array
The core quick sort function quick_sort_range has parameters for the range of elements (first and last) to be sorted, so a wrapper function is required.
CS 136 Winter 2022 07: Arrays 43
void quick_sort_range(int a[], int first, int last) {
if (last <= first) return;// length is <= 1int pivot = a[first]; // first element is the pivot int pos = last; // where to put next largerfor (int i = last; i > first; –i) {
if (a[i] > pivot) {
swap(&a[pos], &a[i]);
swap(&a[first], &a[pos]);
quick_sort_range(a, first, pos – 1);
quick_sort_range(a, pos + 1, last);
void quick_sort(int a[], int len) {
quick_sort_range(a, 0, len – 1);
// put pivot in correct place
CS 136 Winter 2022 07: Arrays 44
Linear search
In Racket, the built-in function member can be used to determine if a list contains an element.
We can write a similar function in C that finds the index of an element in an array:
// find(item, a, len) finds the index of item in a,
// or returns -1 if it does not exist
int find(int item, const int a[], int len) {
for (int i = 0; i < len; ++i) {if (a[i] == item) {return -1; } CS 136 Winter 202207: Arrays 45Binary searchIf the array is sorted, we can use binary search:// requires: a is sorted in ascending order [not asserted]int find_sorted(int item, const int a[], int len) {int low = 0;int high = len – 1;while (low <= high) {int mid = (low + high) / 2;if (a[mid] == item) {return mid;} else if (a[mid] < item) {low = mid + 1;high = mid – 1;return -1; }In Section 08 we will see this is more efficient than linear search. CS 136 Winter 2022 07: Arrays 46 Multi-dimensional dataAll of the arrays seen so far have been one-dimensional (1D) arrays.We can represent multi-dimensional data by “mapping” the higher dimensions down to one.For example, consider a 2D array with 2程序代写 CS代考加微信: assignmentchef QQ: 1823890830 Email: [email protected]
Reviews
There are no reviews yet.