Introduction to Pointers

  1. To learn about pointers in C++
  2. To implement a simple sorted linked list.

POINTERS

Every byte in the computers memory has an address. Addresses are numbers just as they are for our homes on a street. When a program is loaded into the memory, depending on its size, it occupies a certain range of these addresses. Suppose the following variables are declared in our program. Each one of them takes up some space in the memory as described in the table: (This assumes ints are 2 bytes long).

Memory Addresses

Variables (type & name)

123000

int num

123001

123002

char c

123003

int count

123004

123005

float salary

123006

123007

123008

123009

The address of the first variable, integer variable num, is 123000. Note that two bytes are allocated to store num, but the top location is what we refer to as the address of num. The address of the second variable, character variable c, is 123002. Similarly, we can determine the addresses of other variables. In C++, you can find the address of a variable by using the "address of" operator, &. Consider the following program segment:

int num ; 
cout << &num;

The above cout statement prints out 123000, i.e. the address of the variable num. Note that the address of a variable is NOT the same as its content. Consider the following statements in a C++ program:

Declaration:

int num; 
char c; 
int count; 
float salary;

Assignment:

num = 7777; 
c = 'z'; 
count = 999; 
salary = 6920.77;

By assigning a value to a variable, we change the content in the memory location that is assigned to the variable. The following table shows how the assignments are made.

Memory Address

Contents of Memory

Variable Name

123000

7777

num

123001

123002

z

c

123003

999

count

123004

123005

6920.77

salary

123006

123007

123008

We've seen variable types that store characters, integers and floating point numbers. In a very similar fashion, addresses themselves can be are stored. A variable that stores an address value is called a pointer variable, or simply a pointer.

Let's take a look at an example.

//Pointers1.cpp. This program defines pointer variables 
#include<iostream>
using namespace std;
int main ()
{
int num;
char c;
int count;
float salary;

// Declaring bunch of pointers that point to nothing (point to null)
int *numptr; // declare a pointer variable to an integer
char *cptr; // declare a pointer variable to a character
int *countptr; // declare a pointer variable to an integer
float *salaryptr; // declare a pointer variable to a float

// Making them point somewhere
numptr = &num; //numptr is pointing to num
cptr = &c; //cptr is pointing to c
countptr = &count; //countptr is pointing to count
salaryptr = &salary; //salaryptr is pointing to salary

// Assign values to the locations where the pointers point
*numptr = 2;
*cptr = 'A';
*countptr = 100;
*salaryptr = 3200.00;

// Display the addresses of the memory locations
cout << (long) numptr << " , " << (long) &num << endl;
cout << (long) cptr << " , " <<  (long) &c << endl;
cout << (long) countptr << " , " << (long) &count << endl;
cout << (long) salaryptr << " , " << (long) &salary << endl;

// Display the contents of those memory locations
cout << num << endl;
cout << c << endl;
cout << count << endl;
cout << salary << endl;
return 0;

}

This program defines 4 pointer variables. The asterisk (*) before the variable name implies pointer to. The * is called the dereferencing operator. Thus,

int *numptr; 

defines the variable numptr as a pointer variable to an integer value, i.e. numptr can hold addresses of integer variables. Note that the above pointers are not pointing at anything when they are declared.

int *numptr; // declare a pointer variable to an integer 
char *cptr; // declare a pointer variable to a character
 int *countptr; // declare a pointer variable to an integer 
float *salaryptr; // declare a pointer variable to a float

It is said that they are pointing to null. We have only defined pointers that can point to variables of different types, but they don't point to anything yet. In order to make use of them, they have to point to something of their types.

That what we did in the following 4 lines: 
numptr = &num; //numptr is pointing to num 
cptr = &c; //cptr is pointing to c 
countptr = &count; //countptr is pointing to count
salaryptr = &salary; //salaryptr is pointing to salary

These pointers are pointing to some memory locations, we can used these pointers to assign values to those locations:

*numptr = 2; 
 *cptr = 'A'; 
*countptr = 100; 
*salaryptr = 3200.00;

Finally, we displayed the contents of those locations:

cout << num << endl; 
cout << c << endl; 
cout << count << endl; 
 cout << salary << endl;

As you may have noticed, we did not directly assign anything to num, c, count, and salary. Instead, we used the pointers to assign values to where those pointers were pointing.

Note that

int *numptr; and 
int* numptr;

are equivalent. It is the same to the compiler whether you define it one way or the other. However, you must be careful when you make multiple definitions in one line.

int* ptr1, ptr2;

defines ptr1 as a pointer variable that can hold addresses of integer variables, but ptr2 is simply an integer and NOT a pointer variable. i.e.

int* ptr1, ptr2; and 
int *ptr1, *ptr2;

are NOT equivalent. The first statement defines ptr1 as a pointer variable but ptr2 as an integer variable, while the second statement defines both ptr1 and ptr2 as pointer variables to integers. Thus, if you define more than one pointer variable of the same type on one line, you need only insert the type pointed to once, but you need to place the * before EACH variable name.

As we just saw, a pointer can be used to refer to a variable. Your program can manipulate variables even if they have no identifiers to name them. These "nameless" variables are referred to solely by pointers, and are called "dynamic variables". Let's look at Pointers2.cpp to see how this is done.

//Pointers2.cpp . This program illustrates dynamic variables 
#include <iostream> 
using namespace std;

int main () 
{ 
    int *p1;
    p1 = new int; // Variables created using the new operator are called dynamic variables
    cout << "Enter an integer \n";
    cin >> *p1; 
    *p1 = *p1 + 7; 
    cout << "Your input + 7 = " << *p1 << endl;
    delete p1; // Delete the dynamic variable p1 and return the memory occupied by p1 to the freestore to be reused.
    return 0; 
}

The new operator produces a new nameless variable and returns a pointer that points to this new variable. This type of variable is called a dynamic variable. Dynamic variables are stored in a special area of memory called the freestore or the heap. Any new dynamic variable created by a program consumes some of the memory in the freestore. If your program creates too many dynamic variables, it will consume all of the memory in the freestore. If this happens, any additional calls to the new operator will fail.

If your program no longer needs a dynamic variable, the memory used by that dynamic variable can be returned to the freestore to be reused. The delete operator eliminates a dynamic variable and returns the memory that the dynamic variable occupied to the freestore.

Exercise 1

Type in Pointers1.cpp and get it running. See if you can figure out a way to determine the length of an integer by modifying the program. What is the length? Call you new program Pointers1-len.cpp and turn in the source code.

Exercise 2

Define a struct Area that has two private variable members; units of type string and area_value of type float. Modify the Pointer2.cpp program to create a dynamic variable of type Area.
1) Input from the keyboard the area_value and its units. Compute one-half and one-quarter of the area and display the results
2) Destroy the dynamic variable at the end

Call your new program Pointer2-area.cpp.

LINKED LISTS

Consider how a pointer can pointer to a structure in exercise 2. Now consider the following code:

typedef int ItemType;
struct NodeType
{
  ItemType item ;
  NodeType* next;
};

We now have a struct with an integer, and a pointer to a node. This will allow us to have a struct that points to another struct, e.g.:
linked_list.gif
Of course we need to anchor the chain of structs somhow with a pointer, called the head or root of the list. And we need to terminate the list. The slash represents null, essentially a zero pointer.

Now consider some code to input and create a simple linked list. It inputs a list and returns a pointer to the first element:

// Pointers3.cpp - a simple linked list demonstration.
#include<iostream>
using namespace std;

typedef int ItemType;
struct NodeType
{
   ItemType item;
   NodeType* next;
};

NodeType* makeList(); // Forward Reference

int main ()
{
    NodeType* Head = makeList();
    NodeType* next = Head;

    while (next != NULL) {
        cout << next->item << endl;
        next = next->next;
    }
}

NodeType* makeList()
{

    NodeType* listHead = NULL; // List is empty
    NodeType* newNodePtr;

    ItemType tempValue;
    cin >> tempValue;

    while (tempValue != 0) // Read until a zero value is entered
    {
    newNodePtr = new NodeType; // Create a new node
    newNodePtr -> item = tempValue; // Put in the valw
    newNodePtr -> next = listHead; // Insert at the beginning
    listHead = newNodePtr;
    cin >> tempValue;
    }
    return listHead;
}

Exercise 3

This example puts the new element at the beginning of the list. Thus the printed list is always in reverse order of what is entered.

Consider what you would need to do to get the list to be in the same order as entered. Modify the program to do this.

Call your new program Pointer3-inorder.cpp.

Exercise 4

Now consider how the code scan through the list, and always put the next item in exactly where it should be to maintain sorted order. Modify the code to do this.

Call your new program Pointer3-sorted.cpp.

-- JimSkon - 2011-02-14

  • linked List:
Topic attachments
I Attachment Action Size Date Who Comment
Gifgif linked_list.gif manage 6.1 K 2011-04-07 - 19:57 JimSkon linked List
Topic revision: r5 - 2011-04-15 - JimSkon
 
This site is powered by the TWiki collaboration platformCopyright &© by the contributing authors. All material on this collaboration platform is the property of the contributing authors.
Ideas, requests, problems regarding TWiki? Send feedback