Programming - Arrays & Pointers(8)

Administrivia

Practice Web Page - http://www.cs.tau.ac.il/~efif/courses/Programming_Fall_04

Crystal Balls

You have b identical crystal balls. There is a high rise with a f floors. One of the floors could be critical. When a crystal ball is dropped from the critical floor or from a higher floor the ball breaks. You need to find the critical floor with the minimum number of experiments in the worst case. Each drop is counted as one experiment regardless of whether the ball breaks or not. If you have only one ball, you must start your experiments from the first floor. In the worst case you will end up performing an experiment every floor just to find out that there is no critical floor. Given one ball the minimum number of experiments required in the worst case is f.
First count the maximum number of floors that can be covered, given an allowed number of experiments e.
f(e,0) = 0
f(0,b) = 0
f(e,b) = f(e-1,b) + f(e-1,b-1) + 1

A program that reads the number of floors f and the number of b balls, and prints out the minimum number of experiments required.

#include <stdio.h>

int comp_floors(int exprs, int balls)
{
  if (balls == 0)
    return 0;
  if (exprs == 0)
    return 0;
  return comp_floors(exprs - 1, balls) + comp_floors(exprs - 1, balls - 1) + 1;
}

int main()
{
  int floors, exprs, balls;
  printf("Enter number of floors followed by number of balls: ");
  if (scanf("%d %d", &floors, &balls) != 2) {
    printf("ERROR: cannot read input!\n");
    return -1;
  }
  for (exprs = 0; 1; exprs++) {
    if (comp_floors(exprs, balls) >= floors)
      break;
  }
  printf("Required %d exprs\n", exprs);
  return 0;
}

crystal.c

Arrays

a variable that can hold several elements (values)
not limited to any particular type
- can have arrays of int, char, double, etc.
int a[10]; float temperatures[10];
You specify which of the several values you're referring to by using a numeric subscript
the subscript is an integer expression in square brackets

arrays are zero-based array

a[0] = 10;
a[1] = 20;
a[2] = a[0] + a[1];

cannot set all elements of an array at once
a = 0; /* WRONG */
cannot assign one array to another
int b[10]; b = a;/* WRONG */

one by one

int b[10];

for(i = 0; i < 10; i++)
  b[i] = a[i];

Initialization

as with other declarations, array declarations can include an optional initialization
- scalar variables are initialized with a single value
- arrays are initialized with a list of values
  - the list is enclosed in curly braces
  int array [8] = {2, 4, 6, 8, 10, 12, 14, 16};
the number of initializers cannot be more than the number of elements in the array
- but it can be less
- in which case, the remaining elements are initialized to 0
if you like, the array size can be inferred from the number of initializers
- by leaving the square brackets empty
- so these are identical declarations
  int array1 [8] = {2, 4, 6, 8, 10, 12, 14, 16}; int array2 [] = {2, 4, 6, 8, 10, 12, 14, 16};

Simple array

A program that reads 10 characters into an array and prints them out in reverse order.

#include <stdio.h>

int main()
{
  int i;
  char a[10];
  for (i = 0; i < 10; i++)
    scanf("%c",&a[i]);
  for (i = 9;i >= 0; i--)
    printf("%c",a[i]);
  printf("\n");
  return 0;
}

sarr.c

random number generator

int rand() - returns a pseudo-random integer between 0 and RAND_MAX
srand(unsigned int seed) - sets seed as the seed for a new sequence of pseudo-random integers to be returned by rand(). These sequences are repeatable by calling srand() with the same seed value.

dice.c

/*
 * The behavior of rolling a pair of dice.
 *
 * The total roll can be anywhere from 2 to. We want to count how often each
 * roll comes up. We use an array to keep track of the counts: a[2] will count
 * how many times we've rolled 2, etc.
 *
 * We simulate the roll of a die by calling C's random number generation
 * function, rand(). Each time rand() is called, it returns a different,
 * pseudo-random integer. The values that rand() returns typically span a large
 * range. We use C's modulus (or ``remainder'') operator % to produce random
 * numbers in the range we want. The expression rand() % 6 produces random
 * numbers in the range 0 to 5, and rand() % 6 + 1 produces random numbers in
 * the range 1 to 6.
 */

#include <stdio.h>
#include <stdlib.h>

main ()
{
  int i;
  int d1, d2;
  int a[13];			/* uses [2..12] */

  /* Initialize: */
  for (i = 2; i <= 12; i++)
    a[i] = 0;

  /* Compute: */
  for (i = 0; i < 1000; i++) {
    d1 = rand() % 6 + 1;
    d2 = rand() % 6 + 1;
    a[d1 + d2] = a[d1 + d2] + 1;
  }

  /* Print out: */
  for (i = 2; i <= 12; i++)
    printf ("%2d: %3d\n", i, a[i]);

  return 0;
}

dice.c

The nature of memory

it's a bunch of bytes
each byte can hold 256 values
"adjacent" bytes can be combined to hold larger values
- usually grouped in powers of 2 (2, 4, 8, 16, )
bytes in memory are numbered sequentially
- like a long line of lockers
- each locker is given a number
- C lets us use that number

Addresses

in C, we call these "locker numbers" addresses
- an address is the number of the byte we want
  - or if we're talking about a grouped byte, it's the first byte of the group
when a variable contains an address, we call it a pointer
- because it "points" to some other data in memory

It's like a treasure hunt

up to now, we've dealt only with straightforward variables
- they hold the data we care about
- just like a locker holding something for me
  - I can put my book in my locker and get it again later
pointers introduce a level of indirection
- instead of holding the data, they hold information about where to find the data
- so now my locker would only hold a piece of paper, telling me which locker to look in for my book

Just more numbers

like every other kind of data we use, addresses are numbers
- up to now, though, our data has been numbers we care about
  - temperatures
  - dates
  - results of calculations
- addresses are numbers too, but ones that only are useful to the program while it's running

Data types

a pointer isn't a new data type
- it's just kind of a modification, because the pointer should point to a data type
  - or another pointer, that must eventually find a data type

Declaring a pointer

we declare a pointer using a *
- this declaration creates a variable named ptr
  int * ptr;
  - ptr is a variable whose value is an address
  - the thing we expect to find at that address is an int
  - since an int is 4 bytes (on our computers, at least), this is the address of the first byte of a group of 4 bytes
- but ptr has not yet had its value set, so it does not yet contain a valid address of anything

The address-of (&) operator

the unary operator & is used to find an object's address
- its operand is an object
  - remember that an object is something with memory associated with it
- the value of the expression (operator and operand) is the address in memory of the operand

Example

int i = 1;
int *ptr = &i;

the first line defines a variable named i
- it is an int, and thus has 4 bytes of memory reserved for it
- its value is set to 1

Example

int i = 1;
int *ptr = &i;

the second line defines a variable named ptr
- it is a pointer to an int
- it is initialized to the address of i
  - thus, it contains a number which is an address
  - if you look at the 4 bytes starting at that address, you will find the value 1

The contents-of (*) operator

the unary operator * is used to access whatever is at a given address
- its operand is an address
- the value of the expression is an lvalue
  - remember that an lvalue is an expression that refers to an object
  - and an object is something with memory associated with it
  - an address is supposed to refer to a location in memory
  - so an expression using the * operator refers to an object, and thus is an lvalue
- that means we can assign its value as well as look at it

Example

what does this print?
int i = 1; int *ptr = &i; *ptr = 2; printf ("%d\n", i);
- i is an int, containing the value 1
- ptr is a pointer, containing the address of i

Example

what does this print?
int i = 1; int *ptr = &i; *ptr = 2; printf ("%d\n", i);
- *ptr refers to the thing that ptr points to
- ptr points to the memory that stores the value of i
- so this line assigns the value 2 to i

Example

int i = 1;
int *ptr = &i;

*ptr = 2;
printf ("%d\n", i);

what does this print?
- it just prints the value of i
- which is now 2

Example

we have 2 values now:
- the value of the pointer
  - which determines what the pointer points to
- and the value in the location the pointer points to

we can change the value of the pointer:

int i = 42;
int j = 17;
int *ptr = &i;

*ptr = 1;
ptr = &j;
*ptr = 2;

What does this do?

Example

what does this do?
- this declaration creates the variable i
  - i is an int, containing the value 42

Example

what does this do?
- this declaration creates the variable j
  - j is an int, containing the value 17

Example

what does this do?
- this declaration creates the variable ptr
  - ptr is pointer
  - initially, it points to i

Example

what does this do?
- this statement assigns the value 1 to whatever ptr points to
  - which, as we already know, is i

Example

what does this do?
- this statement reassigns the value of ptr
  - so it now points to j instead of i

Example

what does this do?
- and finally, we assign the value 2 to whatever ptr points to
  - which is now j

Operations on pointers

what we've seen so far:
- assignment (=)
- dereferencing (*)
- address (&)

Pointer assignment

as with arithmetic assignment:
- the object on the left side must be an lvalue
- therefore, this is not valid:
  &j = &i
both operands must be pointers to the same data type
- valid:
  int i; int *ptr = &i;
- invalid
  double d; int *ptr = &d;

Pointer dereferencing

single operand, must be a pointer
the data type of the expression is the data type of whatever the pointer points to
- thus, given this declaration,
  int * ptr;
- the data type of the expression *ptr is int

The address-of operator (&)

operand must be something with memory associated
- so the expression &(i+j) is invalid
the data type of the expression is "pointer to T"
- where T is whatever the data type of the operand is

NULL

This is the canonical "invalid" value
- A non-valid address
- Can be used to indicate when a pointer variable is not set to an address
- Useful for initializing pointer variables before they are actually set to their resp. values
- Used in a lot of other situations too
Don't confuse this with the nul character. The name for ASCII code 0, also '\0'

Changes to parameters don't "pass back"

in C, arguments are passed by value

When an expression is specified as an argument to a function call, the value of that expression is copied into the parameter in the function
- A variable name is a simple expression
When the value of a function parameter is changed, only a copy is changed, and the change doesn't affect the variable used to call the function

#include 

#define MAX 10

int square(int x)
{
  return x * x;
}

int main(void)
{
  int i;
  for (i = 0; i < MAX; ++i) {
    int isquared = square(i);
    printf ("%d squared is %d\n", i, isquared);
  }
  return 0;
}

Example

If the variable passed into a function is a pointer,
- We still can't change the parameter inside the function and expect the change to affect anything outside the function
- We can change the thing the pointer points to
#include #define MAX 10 int swap(int * a, int * b) { int tmp; tmp = *a; *a = *b; *b = tmp; } int main(void) { int i = 3, j = 5; swap(&i, &j); printf ("%d %d\n", i, j); return 0; }

Example

#include 

#define MAX 10

int swap(int * a, int * b)
{
  int tmp;
  tmp = *a;
  *a = *b;
  *b = tmp;
}

int main(void)
{
  int i = 3, j = 5;
  swap(&i, &j);
  printf ("%d %d\n", i, j);
}

Example

#include 

#define MAX 10

int swap(int * a, int * b)
{
  int tmp;
  tmp = *a;
  *a = *b;
  *b = tmp;
}

int main(void)
{
  int i = 3, j = 5;
  swap(&i, &j);
  printf ("%d %d\n", i, j);
  return 0;
}

Example

#include 

#define MAX 10

int swap(int * a, int * b)
{
  int tmp;
  tmp = *a;
  *a = *b;
  *b = tmp;
}

int main(void)
{
  int i = 3, j = 5;
  swap(&i, &j);
  printf ("%d %d\n", i, j);
  return 0;
}

Example

#include 

#define MAX 10

int swap(int * a, int * b)
{
  int tmp;
  tmp = *a;
  *a = *b;
  *b = tmp;
}

int main(void)
{
  int i = 3, j = 5;
  swap(&i, &j);
  printf ("%d %d\n", i, j);
  return 0;
}

Example

#include 

#define MAX 10

int swap(int * a, int * b)
{
  int tmp;
  tmp = *a;
  *a = *b;
  *b = tmp;
}

int main(void)
{
  int i = 3, j = 5;
  swap(&i, &j);
  printf ("%d %d\n", i, j);
  return 0;
}

Example

#include 

#define MAX 10

int swap(int * a, int * b)
{
  int tmp;
  tmp = *a;
  *a = *b;
  *b = tmp;
}

int main(void)
{
  int i = 3, j = 5;
  swap(&i, &j);
  printf ("%d %d\n", i, j);
  return 0;
}

Example

#include 

#define MAX 10

int swap(int * a, int * b)
{
  int tmp;
  tmp = *a;
  *a = *b;
  *b = tmp;
}

int main(void)
{
  int i = 3, j = 5;
  swap(&i, &j);
  printf ("%d %d\n", i, j);
  return 0;
}

Example

#include 

#define MAX 10

int swap(int * a, int * b)
{
  int tmp;
  tmp = *a;
  *a = *b;
  *b = tmp;
}

int main(void)
{
  int i = 3, j = 5;
  swap(&i, &j);
  printf ("%d %d\n", i, j);
  return 0;
}

Scope

Determines where a variable can be seen from within the program
You can "return" more values from a function than just the return value, by passing in pointers to other variables. The function can then use the pointer to change the value of the variable
This circumvents the "scope" rules
- In our example, i and j were not in the scope of the function swap(), but we changed their values anyway
We manipulated variable values from outside their scope
- In that case, the variables still existed somewhere in memory
- scope says whether we can use the name, not whether the variable will exist or not
void swap (int *a, int *b) { int tmp; tmp = *a; *a = *b; *b = tmp; }
The variable tmp is declared at the beginning of this function
- Its scope is the entire body of the function
- We can use the name tmp only within the function

Extent

Extent determines how long the variable exists while the program is running
The lifetime of the variable is its extent
- at some point, the computer reserves the memory for that variable
  - before that point, the variable doesn't exist
- at some later point, the compter releases the memory for that variable, so it can be used for something else
  - after that point, the variable doesn't exist either
  - if we still have a pointer to that memory, it's no longer valid
- to use that locker analogy, it would be like someone still having a slip of paper with my locker number on it, even though my locker has been given to someone else

Scope vs. Extent

Each type of scope has its own extent rules
Scope is a static property: it applies to the code
Extent is a dynamic property: it applies to the running program
- Extent and scope are often mixed together, but they're really separate concepts

swap() again

void swap (int *a, int *b)
{
  int tmp;
  tmp = *a;
  *a = *b;
  *b = tmp;
}

In swap(), we declare the variable tmp
- and it's a definition: it reserves some memory
- but up to now, we haven't looked at when that memory is reserved, and when it's released.

Extent of tmp

the extent of tmp in this case pretty much mirrors its scope
- it's created when we enter the function
- it's destroyed when we leave the function
- that means that every time we call the function, the expression &tmp may have a different value

Extent of i and j

similarly i and j exist from the beginning of the block in which they're declared until we leave it
- which is really from the beginning of the program until it ends
- so they exist while swap() is being called

Extent is important!

Returning an invalid pointer

(don't ask why; this is a contrived example)
but product's extent ends at the return statement
so this function always returns an invalid pointer

/*
 * power: calculate m to the nth power
 */
long *power (int m, int n)
{
  int i;
  int product = 1;

  for (i = 1; i <= n; ++i)
    product *= m;
  return &product;
}

Maintained by Efi Fogel. Last modified: December 22 2003.