Fall 2004
Monday 3:00 - 4:00 Rm 343, Friday 2:00 - 4:00 Rm 343
This topic covers slightly more advanced concepts, or at least concepts associated with slightly more advanced programming techniques than topic #1. We use C to cover these concepts, but they are all concepts related to most common high-level programming languages (although different languages may have different names for structures, and some languages hide pointers from the programmer). The programs we will examine to help understand the concepts include a palindrome detector, a simple text formatter, and a simple phone book program.
A pointer is a variable whose value is a memory address (typically a memory address of another variable or the beginning of a region of dynamically allocated memory). If the pointer is pointing to an entity that takes up multiple bytes in memory, the actual value of the pointer is the address of the first byte. The type of the pointer is used by the compiler to determine how many bytes are used when the pointer is dereferenced (using the indirection operator), and also to determine which other pointers (or memory addresses) may be assigned to the pointer. A pointer to void can be assigned (or assigned to) any other pointer type, but it can not be dereferenced.
We cover three reasons pointers are useful. One is to create functions that can change values of variables in other functions. If a parameter of a function is a pointer, and a calling function passes the called function the address of a variable, the calling function will "see the change" if the called function changes the "pointed to" value, but it will not see the change if the called function changes the memory address of the pointer itself.
A second reason pointers are useful is that it provides another way to deal with arrays, treating them as pointers instead of arrays. The name of an array is actually a pointer to the first element (or byte) of the array. Sometimes treating arrays as pointers is more efficient; e.g. incrementing a pointer through the bytes of a string instead of manipulating an index, since that requires doing an extra addition to access each character.
A third reason is that pointers, along with provided functions (in C, malloc and free are often used) provide a way to use dynamically allocated memory from the heap. This is necessary for programs that do not know how much memory will be needed at compile time, and it will become even more important when we cover linked lists.
A string is a sequence of characters. They are often stored in an array or are pointed to by a pointer (or both). Sometimes the characters are stored in dynamically allocated memory. In C, provided functions that manipulate strings assume that every string is delimited by a null character '\0', and it is highly recommended that a programmer sticks to this convention for strings. The length of a string (as returned by strlen) does not include the null character, so the number of bytes of memory needed (assuming that each character takes up one byte, as is true in C which represents characters using ASCII) is one more than the length of the string.
Structures provide a way for a user to define new data types that allow the programmer to declare variables with multiple parts of different types with different names. The member operator "." is used to access a field of a structure variable, and the selection operator "->" is used to access a field of a structure pointed to by a pointer. Structures are important when a program needs to organize data including objects with multiple related parts, especially if these objects need to stay sorted according to a particular field. A few simple sorting algorithms will be mentioned during discussion of this topic, one of which is implemented in the simple phone book example. Structures will also be used for linked lists.