Home Previous Next

CSC100 :: Lecture Note :: Week 13
Assignments | Code | Handouts | Resources | Email Thurman {Twitter::@compufoo Facebook::CSzero}
{GDT::Bits:: Time  |  Weather  |  Populations  |  Special Dates}

Overview
Assignment(s): All assignments have been assigned.

Code: arrays2.cpp | BingoCard.cpp | factorial.cpp (recursion) | arrays3.cpp (binary search)
arrays4.cpp | pointer0.cpp | arrays5.cpp | arrays6.cpp | RandomInts.cpp | BingoCard.cpp
bingo.cpp | LotteryTickets.cpp | StructStudent.cpp | Dog.cpp | Time.cpp

### Arrays

An array is a collection of individual data values with two characteristics: it is ordered and homogeneous.

The following are some terms commonly used when talking about arrays:

• an element of an array is a single data value
• the type of an array is the data type of its elements
• the location of an array is the location of its first element
• the length of an array is the number of elements in the array
• the size of an array is it's length times the size of an element

An array is homogeneous because each element must be of the same type. For example, an array of int's, an array of float's, an array of char's.

An array is ordered -- it has a 1st element, a 2nd element, a 3rd element, and so on. Array elements are stored in contiguous memory locations.

Just like any other variable, an array must be defined before it is used.

```   Syntax:  element-data-type array-name [ length ];

int intArray[10];
name:  intArray
type:  int
length:  10
size:  10 * sizeof(int)

char someString[32];
name:  someString
type: char
length: 32
size:  32 * sizeof(char)
```

Each element of the array is identified by a numeric value called its index (index numbers always start at 0).

When defining an array, its length must be specified at compile-time. In addition, the specification of the length must be a constant integral EXPR.

```
int i = 10;
/* double salaries[i];   // illegal (not a constant) */
/* char name[15.5];      // illegal (not an integral type) */
const int MAX_ELEMENTS = 10;
short scores[MAX_ELEMENTS];  /* okay in C++, not C */
#define LENGTH 5
float someArrayOfFloats[LENGTH];

```

Typically, array lengths are defined to be manifest constants.

##### Array Initialization

Arrays can be initialized at the time they are defined.

```   int evenNumbers[5] = { 2, 4, 6, 8, 10 };

note:  it is a syntax error if the # of initializers is
greater than the array length (i.e. # of elements)

The elements of the initializer list must be constant
EXPRs.  If the number of initializers is less than the
array length, then remaining elements are set to zero.
```

If an array is initialized when defined, then the length is not needed -- the compiler will set the length depending on the number of initializers. If the length of the array needs to be greater than the number of initializers specified, then the length must be specified.

```   float radioStations[] = { 103.1, 93.3, 100.7 };

radioStations  has a length of 3; to figure out the length
of the array using code:

sizeof(radiostations)  evaluates to the size of the array
and  sizeof(radioStations[0])  evaluates to the size of a
single element of the array (recall, an array size is equal
to the length of the array times the size of the array type)

the following EXPR also works to determine the length of
an array    sizeof(radioStations) / sizeof(float)    but could
result in the defect if the type of the array is changed and
the EXPR is not
```

There is not a convenient mechanism for initializing all elements of an array to a single value (exception: it is easy to set all elements of an array to zero -- `int a[10] = { 0 };`).

For efficiency, locally declared arrays that are initialized at definition may be declared to be `static`.

```   static short tvStations[99] = { 3, 10, 12, 61 };

tvStations  is an array of length 99; elements 0, 1, 2, 3
have non-zero values, whereas elements 4 through 98 equal 0;
the array is initialized once -- at program load time
```

Once an array has been defined, its length (i.e. number of elements) cannot be altered.

Elements of the array are accessed using the unary array operator `[]`.

```   const int LEN = 10;
int a[LEN];

a[3] = 150;  /* set element #4 to 150 */
a[1] = 200;  /* assign the value 200 to element #2 */

if (a[1] == a[3]) /* compare the value of element #2 with element #4*/
```

Array indicies must be integral values, but they are not restricted to being constants.

```   int i, j, k;

a[0] = 100;
a[i] = 150;
a[i * j - k] = 210;
a[a[a[i]]] = 250;
a[rand() % LEN] = 178;
```

The language does not protect against indexing beyond the ends of an array. Typically, if this happens, then a run-time error is encountered.

```   a[-1] = 100;
a[sizeof(a)/sizeof(a[0]) + 2] = 200;
```

Array 'a' cannot be copied to array 'b' using simple assignment.

```   #define LEN 5
int a[LEN] = { 100, 200, 210, 120, 240 }, b[LEN];

/* b = a;   //syntax error -- array name not a lvalue */
for (int i = 0; i < LEN; i++)
b[i] = a[i];
```
##### Arrays and Functions

Arrays are passed to functions "by reference." (Think about the overhead if arrays were passed by value.)

A function that receives an array as a parameter, obtains a constant pointer to the first element of the array.

Unless specifically qualified to be `const`, the function can modify the content of the array.

When a function receives an array as a parameter, it does not know, nor can it figure out, the length or size of the array. In many cases, the caller passes the array length (`size_t`) to the function.

```   void func1(int[]);         //do *not* specify the array length
void func2(const int[]);   //func2() not allowed to modify the array
void func3(int [], int);
#define A_LEN 10
int a[A_LEN];

func1(a);  //using array name w/o [] operator "decays" into a
//constant pointer to the 1st element of the array
func2(a);
func3(a, A_LEN);  //pass the array length to the function
...

void func1(int i[]) {  //again, array length not specified
int len = sizeof(i) / sizeof(i[0]);
// does not work -- sizeof(i) evaluates to the size
// allocated for pointer variables, which is typically
// the sizeof(int)...
...
}

void func2(const int i[]) {
//! i[0] = 100;    //use of  const  implies the content of the
//array cannot be changed...
}

void func3(int i[], int len) {
for (int i = 0; i < len; i++)
//loop through each element of the array
...
}
```

Pointer notation can be used when prototyping and defining functions that receive arrays as parameters.

```   void func1(int*);  //this syntax indicates that the function receives
//a pointer to an array
void func2(const int*);  //array content cannot be modified
```

{TopOfPage} {Tutorial} {online IDEs: CodingGround | CPP.sh | jdoodle} {C at MIT} {GDT::C/C++ Resource}

### Pointers

A pointer is a variable whose value is an address of another variable.

• pointers are referred to as derived data types
• a pointer is a variable (it has a name, and it points to a particular type of data)
• the amount of space allocated for a pointer variable is typically the size allocated for an `int`
• pointer variables are assigned address values obtained using the address-of operator `&`
• local pointer variables are uninitialized
##### Defining and Initializing Pointer Variables
When defining a variable, prefixing the variable's name with an asterik `*` causes the variable to be a pointer.

```   int* iptr;   /*define variable iptr that will point to an int variable*/
float * fptr; /*define variable fptr that will point to a float variable*/
char *cptr;  /*define variable cptr that will point to a character*/
int i, j;
float f;
char c;

iptr = &i;  /*assign the address-of variable 'i' to iptr*/
fptr = &f;  /*assign the address-of variable 'f' to fptr*/
cptr = &c;  /*assign the address-of variable 'c' to cptr*/
int* iptr2 = &j; /*define and initialize an int pointer*/
iptr = iptr2;  /*now iptr points to the variable 'j'*/

note:  Placement of the  *  when defining a pointer variable is
a matter of style -- I like to place the  *  next to the
data type, but others prefer to place it next to the
variable name.  Placing it next to the data type does
require caution when multiple variables are defined on
the same declaration statement.  Example:

int* ip1, ip2;
// ip1  is a pointer to an  int  , but  ip2  is a
regular  int

int* ip1, *ip2;
// ip1  and  ip2  are both pointers to an  int
```

The address-of operator only applies to objects in memory: variables and array elements.

Locally defined non-static pointers, unless explicitly initialized, are garbage and using them without initialization can cause a program to execute incorrectly (or abort).

Global and statically defined pointers are initialized to the `NULL` pointer.

##### Accessing Data Using Pointers

The unary operator `*` is the indirection or dereferencing operator; when applied to a pointer, it accesses the object the pointer points to.

```   int i = 200;
int* iptr = &i;

cout << *iptr;    /*prints 200 -- the value of 'i' which is the object
iptr points to*/
```
##### Pointers and Function Arguments

Since C passes arguments to functions by value, there is no way for the called function to alter a variable in the calling function. A way to obtain the desired effect is for the calling program to pass pointers to the values to be changed.

```   void swap(int*, int*);

int i, j;

swap(&i, &j);

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

Using pointers is similar to using reference variables; however, reference variables are part of C++ and they are not part of C.

Advantage of using reference variables over pointers.

• cleaner syntax

##### Introduction to Pointers and Arrays

There is a strong relationship between pointers and arrays.

When an array name is used by itself, it evaluates to a constant pointer to the first element of the array.

Everywhere you use `arrayName[index]` you can use `*(ptr + index)` (assuming `ptr` points to some part of the array).

```   int scores[10];

scores[0] = 2;      // or  *scores = 2
scores[1] = 3;      // or  *(scores + 1) = 3
*(scores + 2) = 5;  // or  scores[2] = 5
```

{TopOfPage} {Tutorial} {online IDEs: CodingGround | CPP.sh | jdoodle} {C at MIT} {GDT::C/C++ Resource}

### Structures

A `struct` (structure) is an aggregate of elements of arbitary types. (An array is an aggregate of elements of the same type.)

An example of a structure.

```   struct Grade {
float points;
char letter;
};  /* the semicolon after the  }  is required */
```

Structures are sometimes referred to as records.

A `struct` consists of zero or more fields (or members).

• variables of type `struct` can be defined and declared exactly as other variables
```     struct Grade grade1;  /*keyword  struct  required in C*/
```
• it is possible to define variables immediately after declaring a structure
• ```     enum { STREET_LEN = 32, CITY_LEN = 32, STATE_LEN = 4 };

char street[STREET_LEN];
char city[CITY_LEN];
char state[STATE_LEN];
long zipcode;
short int zipcodePlus4;
};

#define LEN_NAME 64

struct Person {
char name[LEN_NAME];
int age;
char* datafile;
} bob, ted, carol, alice;

note: structure members can contain arrays, pointers, and
other structures
```
• individual members are accessed using the member-of (or dot) operator
```     grade1.points = 99.3;

bob.age = 21;
```
• notation used to initialize arrays can also be used to initialize structure variables (initialization can occur only at the time of definition)
```     struct Grade grade2 = { 83.7, 'B' };
struct Grade grades[] = { 99.3, 'A', 45.7, 'F', 76.2, 'C' };
/* compiler creates a 3 element array */
/* elements 1-4 are initialized to 0 */
/*! grade2 = { 99.1, 'A' };   // illegal */

```
• structure objects are often accessed through pointers using the `->` operator
```     printGrade(&grade1);

g->points = 88.0;
g->letter = 'B';
}

the  ->  operator was added to the language for convience;
when  p  is a pointer,  p->m  equivalent to  (*p).m

note:  when making a function call, passing a pointer to a
structure variable is more efficient than passing by value
```
• operations such as `==` and `!=` are not defined on structure variables
```     if (grade1 == grade2)  /* is not legal */
```
• one structure variable can be copied to another structure variable using the assignment operator, but only if they are of the same type (e.g. `grade1 = grade2`)
• the size of a `struct` is not necessarily the sum of the sizes of its members; always use the ``` sizeof()``` operator (for efficiency reason, the compiler may want integral values to begin on an even word boundary, etc. -- usually this behavior can be altered by using `#pragma` compiler directives)
• the `offsetof` macro is used to determine the offset in bytes of a member from the start of the structure that contains it
```     #include <stddef.h>

struct xyz { int a, b, c; };

size_t offset = offsetof(struct xyz, b);
/* on a 4-byte int system,  offset  will probably be equal to 4 */
```
• a `struct` is a simple form of a `class`
• the name of a type becomes available for use immediately after it has has been encountered
```     struct Link {
};
```
• it is not possible to declare new objects of a structure type until the complete declaration has been seen
```     struct Node {
Node n; /*illegal -- recursive definition*/
};

The following is allowed.

struct List;   /*this is an incomplete type */

struct List* listItem;
};

struct List {
};
```
• two structures are different types even when they have the same members
• it is possible to declare a struct and a non-struct with the same name in the same scope (be careful in C++)
```     struct abc { ... };
int abc;
struct def { ..., int def, ... } def;

def: def.def = 100;
```

{TopOfPage} {Tutorial} {online IDEs: CodingGround | CPP.sh | jdoodle} {C at MIT} {GDT::C/C++ Resource}

### Introduction to Classes

We could spend weeks on the topic of class design. When developing a large program or a system (i.e. a collection of programs that work together to provide a specific application), class design is one of the most critical steps in the software development cycle.

In this course sequence we get an introduction to what classes are and how to create and use them using the C++ programming language.

A class is a blueprint from which objects are instantiated (i.e. created). [Classes are also referred to as models or patterns or templates -- although you should avoid using the term template.]

Objects are instances of a class. Objects have memory allocated for them and are usually considered system resources. Memory is allocated from the heap (or free store).]

Object-oriented programs require you to think of programs as being a collection of objects that work together to provide an application.

Object-oriented design is a software design methodology that models the characteristics of abstract or real objects using classes and objects.

The class declares data the defines the state that objects of the class can take on, and methods that define the behavior that the objects can exhibit or be subjected to.

An object is a software "capsule" containing variables and related methods. The values of the variables define an object's state, and the methods define the behavior an object can be subjected to.

A method is a function defined in a class. C++ classes can contain instance methods and class methods. Class methods are defined to be `static`.

The `public` methods of a class defines the API or Application Programmer Interface for the class.

The data that is specific to a particular instance of an object is called instance data. Ideally, clients should not have to beware of the instance data in order to use objects of your class.

A class declaration has the following syntax.

```   class SomeClassName {
private:
0_or_more_data_members;
0_or_more_method_members;
public:
0_or_more_data_members;
0_or_more_method_members;
};

// class, private and public are C++ keywords
```

Once an object instantiated (created), messages can be sent to it as follows:

```   SomeClassName objectVariable;

objectVariable.methodName(...)
```

Where `objectVariable` is the name of a variable that stores the data contained within an object, and `methodName` is the name of a method defined in the class `SomeClassName`.

`objectVariable` is referred to as the recipient object. Or here it described as: `methodName()` is invoked on behalf of `objectVariable`. Or the `methodName` message is sent to `objectVariable`.

The `methodName()` method is called. If arguments are supplied, then the value of those arguments are passed to the method (the method receives them as parameters). Implicitly, every method that is invoked on behalf of an object (referred to as an instance method), receives a parameter that has the name `this`. `this` is an `objectVariable` that points to the recipient object.

[class example: Time.cpp | Dog.cpp]

When defining instance variables, you should use `private` as much as possible. Private instance data members can be accessed only by the methods defined in the class.

Making data private provides the following benefits:

• controls who can and cannot access the data
• prevents the data from being set to invalid values
• allows you to change the underlying representation of the data

By convention, mutator methods begin with the word `set`. In many cases, `set` is followed with the name of instance variable.

When you want the client to be able to access private data, then an accessor or getter method is provided.

By convention, accessor methods begin with the word `get` which it then often following by the name of the instance variable.

Accessor methods are often covert the value of instance variables from their internal representation to types that are usable by the client.

Accessor methods are usually short methods.

{TopOfPage} {Tutorial} {online IDEs: CodingGround | CPP.sh | jdoodle} {C at MIT} {GDT::C/C++ Resource}

Home Previous Next