Graphs

The slides related to graphs can be obtained from here.

Project Details

The project details can be found here.

Tree traversal

There are two types of traversals when we are talking about trees. You can get the notes about both from these links:

Breadth First Traversal

Depth First Traversal

Trees

Before we can study Heap Sort or any of the searching algorithms, we need to understand the concept of trees and how do we go about them.

We start our discussion from binary trees. You can get the linked list implementation of binary trees from here. Keep in mind that all the pointers in this implementation are not deallocated at the end of the program, which causes it to crash sometimes.

In order to see the results, what you can do is to put a break point just before the program finishes so that you can see the results shown by it. If time allows, I will try to fix this problem.

Radix sort

Radix Sort Algorithm

The notes for the course can be obtained here.

Psuedocode for algorithms

I am not following any book when it comes to algorithms or psuedocode.

a good resource is wikipedia to get the details about the algorithms, for example, the psuedocode for merge sort that i explained in the class is present here. You can use whatever resource you find is good for your understanding.

Till now, we have covered:

merge sort
insertion sort
selection sort and
bubble sort

Algorithm animations

A very good animation of all the sorting algorithms can be found here.

Algorithms and Complexity Analysis

A very good document about complexity analysis can be obtained from here. You must read it as it is very well written.

The slides for the first lecture are present here

Assignment 2

The assignment 2 can be obtained from here.

Assignment 1 Solution

The solution for the first assignment can be obtained from here

Priority Queue

The code for the priority queue can be obtained from here.

Recursion

The code of all the recursion functions can be obtained from here:

Converting Infix Expression to Postfix

This is a pseudocode of the program that can covert an Infix expression to postfix expression. The same pseudocode is given in your course book as well, but I have written it in a way that it is more understandable. The code has a precedence() function that returns true or false, depending on the precedence of the operators. so if it is precedence('*', '+'), it will return true and also true for precedence('*', '*'). You must keep in mind that for precedence('$', '$'), the return value is false.

Get expression from user //Say A*B+C or A+B*C$D$E
initialize operatorStack as empty //A stack for only storing operators +,-,*,/,$
initialize postfixString //The created postfix string

char Symbol;
char topSymbol;

//While loop will run till the end is reached
while(!endOfExpression())
{
Symbol = getCharacterFromExpression()
if(SymbolIsOperand())
{
add Symbol to postfixString;
}
else
{
while(!operatorStack.isEmpty() && precedance(operatorStack.getTop(), Symbol))
{
topSymbol = operatorStack.pop();
add topSymbol to postfixString;
}
operatorStack.push(Symbol);
}
}

while(!operatorStack.isEmpty())
{
topSymbol = operatorStack.pop();
add topSymbol to postfixString;
}

One of the problems that came up during the assignment was the class redefinition error as both the stack and the queue classes were using the same Car.h header file. One way of avoiding that problem is to make 2 different projects and work in them. Another way is to do a bit of programming.

You can use macros to keep check of the files that might be redefined and thus you avoid the error altogether and do not need to make two separate projects. So, you will define your car.h file like this:

#ifndef CAR_H //This checks if the header file was defined
#define CAR_H //If it was not defined, it will define it

class Car
{
private:
int milage;
int passengers;
int model;
char* name;
public:
Car();
void setmilage(int);
int getmilage();

void setpassengers(int);
int getpassengers();

void setmodel(int);
int getmodel();

void setname(char* );
char* getname();
};


#endif /* CAR Seen */

Infix, Prefix and Postfix notations

The next lecture id going to be about infix, postfix and prefix notations. After explaining the three notations, I will go and explain the algorithm for implementing and calculating postfix notation while using a stack. You can read about the postfix notation here. you can also read about it in the book, Data Structures using C and C++ by Tenenbaum on page 95. I created a working program using the pseudo code as given in the Tenenbaum book in Visual C++. You can get it from here. You should see how I have created the entire project, declared the header files, the cpp files and how I used one of the classes as static, to use its functionality. I will be explaining this in class as well. The assignments that you submit should be similarly done. I also hope that you will get to learn Visual C++ IDE and debugging as you proceed.

Lab No. 3

A stack is exactly what it means, like a stack of books, a stack of cards and in such a stack, it is known that the item that is readily available is the top most item. Thus, when we add an item, we add it to the top and when we remove an item, we remove it from the top. This way of accessing data, earns it the name of a LIFO data structure. The implementation of the stack is as follows:
#include
class Stack
{
private:
char* data; //character pointer
int head; //index counter
int maxSize; //maximum array size
public:
Stack(int);
void push(char);
char pop();
};

Stack::Stack(int num)//Constructor
{
head = -1; //setting head to -1;
maxSize = num;
data = new char[maxSize]; //declaring the stack size
for(int i = 0; i < maxSize ;i++) //initialising all values to NULL
{
data[i] = '\0'; //putting NULL values in the data array
}
}

void Stack::push(char c)//Adding a value
{
if(head == -1)
{
head++;
data[head] = c;
}
else if(head < maxSize - 1)
{
head++;
data[head] = c;
}
else
{
cout<<"Stack is full.";
}
}
char Stack::pop()
{
char c;
if(head==-1)
{
cout<<"Stack is empty.";
}
else
{
c = data[head];
head--;
}
return c;
}

Circular Queue:
In a queue, the item that is added first is removed first, thus it is commonly known as a FIFO data structure. A common example of a queue is when you join a line in front of a cinema to buy tickets. Circular queue is a bounded queue. It is better than a normal queue because in this we can effectively utilize the memory space. The implementation of the circular queue is as following:

#include
typedef int bool;
const int false = 0;
const int true = 1;

class CircularQueue
{
private:
int head;
int tail;
int maxSize;
char* data;
public:
CircularQueue(int);
~CircularQueue();
bool isFull();
void push(char);
void pop();
};


CircularQueue::CircularQueue(int num)
{
head = tail = -1;
maxSize = num;
data = new char[num];
}
CircularQueue::~CircularQueue()
{
delete[] data;
}


bool CircularQueue::isFull()
{
return(head == tail+1 || (head == 0 && tail == maxSize-1) );
}


void CircularQueue::push(char c)
{
if(!isFull())
{
if(tail == -1 || tail == maxSize-1)
{
tail = 0;
data[tail] = c;
if(head == -1)
{
head = 0;
}
}
else
{
tail++;
data[tail] = c;
}
cout<<"\nPushed " ;}
else
{
cout<<"\nQueue is Full.\n";
}
}


void CircularQueue::pop()
{
char temp;
temp = data[head];


if(head == -1 && tail == -1)
{
cout<<"\nStack is Empty\n";
}
else
{
if(head == tail)
{
head = tail = -1;
}
else if(head == maxSize-1)
{
head = 0;
}
else
{
head++;
}
cout<<"\nPopped "; }
}

Lab Tasks:

1) Write a program to create a stack of books in a library. Modify the code of stack class given in the handout so that it works for strings and verify the methods of the stack class. (Hint: You can create a structure which stores the name of the book and then create an array of that structure to implement stack)

Linked lists and Stack

This is the place where all the pointers, objects and structures come together. A pointer can be used to point towards a memory location. That memory location can hold a pointer, a variable, a structure an array of structure and so on. Once we have pointers that start pointing towards structures, the C++ starts to become both interesting and complicated. Again, if you do not forget how the pointers work, you will have no problem in understanding the concept of linked lists.

We start off by defining a very basic structure called "node" which holds the data that we want to store and a pointer that helps in pointing towards other nodes. This structure can be defined as this:

struct node

{

char data;

node* next;

};

Now, we define our interface for the stack class that we are going to create, like this:

class stack

{

private:

node* head;

public:

stack();

~stack();

void push(char c);

char pop();

};

if you remember the stack implementation through arrays, you will see that the class looks almost the same, with slight differences. The real differences come when you start to implement the various functions. In order to understand how these functions work, attending the classes should do you good. The code that lets you make a stack is as following:

stack::stack()

{

head = NULL;

}

stack::~stack()

{

}

void stack::push(char c)

{

if(head == NULL)

{

head = new node;

head->data = c;

head->next = NULL;

}

else

{

node* temp = new node;

temp->data = c;

temp->next = head;

head = temp;

temp = NULL;

}

}

char stack::pop()

{

char c = '\0';

if(head == NULL)

{

cout<<"\nStack Empty";

return c;

}

else

{

node* temp = head;

head = head->next;

c = temp->data;

delete temp;

temp = NULL;

}

return c;

}

I have made and performed this code myself, so there does not seem to be any problem. You can now try the code yourself and see how the stack works by using nodes. Once you learn this, going through queues and trees is going to be a lot of fun.

Today’s lecture is about circular queue. The problem with making a queue in an array is the right shifting of the data whenever we pop an element. One way to fix that problem is to run a for loop that shifts the elements one step back in the array after every pop.

Another way to fix this problem is to treat the array as a circular queue. In that case, The array gives the illusion of continuing in a circular way. What we actually do is that, we start using the old locations in the stack that had been popped. This brings us to the important task of finding out the conditions when the queue will be full, which is defined by the isFull() function.

bool CircularQueue::isFull()

{

return(head == tail+1 || (head == 0 && tail == maxSize-1) );

}

According to this code, there are two conditions by which a queue can be full.

1. head is greater than tail by one place. This means that the user started popping values and while doing so, as we increment head, after popping the last value, the head becomes greater than tail.

2. The second condition becomes true if head was at the zero location and the tail was at the last place possible in the array.

If any of these two conditions are met, the queue is considered to be full.

In case of pushing, we need to check first if the array is full or not. Then we push to the appropriate place:

void CircularQueue::push(char c)

{

if(!isFull())

{

if(tail == -1 || tail == maxSize-1)

{

tail = 0;

data[tail] = c;

if(head == -1)

{

head = 0;

}

}

else

{

tail++;

data[tail] = c;

}

cout<<"\nPushed "<

}

else

{

cout<<"\nQueue is Full.\n";

}

}

If you look at the code, after checking if the Queue is Full, we check if tail was either at the final position or -1. It then increments tail and puts the element to the appropriate spot. It also checks if the head was -1 or not and increments it if it was.

Otherwise, it just increments tail and puts the element at the appropriate place.

void CircularQueue::pop()

{

char temp;

temp = data[head];

if(head == -1 && tail == -1)

{

cout<<"\nStack is Empty\n";

}

else

{

if(head == tail)

{

head = tail = -1;

}

else if(head == maxSize-1)

{

head = 0;

}

else

{

head++;

}

cout<<"\nPopped "<

}

}

For popping, it first checks if both head and tail are -1, this tells the user that queue is empty. Otherwise, it first checks if the array has the last value, then if the head was at the last value of the array and if these conditions are not met, it simply increments head and puts the data at the appropriate place. The complete code for the circular queue is as following:

class CircularQueue

{

private:

int head;

int tail;

int maxSize;

char* data;

public:

CircularQueue(int);

~CircularQueue();

bool isFull();

void push(char);

void pop();

};

CircularQueue::CircularQueue(int num)

{

head = tail = -1;

maxSize = num;

data = new char[num];

}

CircularQueue::~CircularQueue()

{

delete[] data;

}

bool CircularQueue::isFull()

{

return(head == tail+1 || (head == 0 && tail == maxSize-1) );

}

void CircularQueue::push(char c)

{

if(!isFull())

{

if(tail == -1 || tail == maxSize-1)

{

tail = 0;

data[tail] = c;

if(head == -1)

{

head = 0;

}

}

else

{

tail++;

data[tail] = c;

}

cout<<"\nPushed "<

}

else

{

cout<<"\nQueue is Full.\n";

}

}

void CircularQueue::pop()

{

char temp;

temp = data[head];

if(head == -1 && tail == -1)

{

cout<<"\nStack is Empty\n";

}

else

{

if(head == tail)

{

head = tail = -1;

}

else if(head == maxSize-1)

{

head = 0;

}

else

{

head++;

}

cout<<"\nPopped "<

}

}

Lab #2

CSC-260 Data Structures
Lab No.2
Dynamic Memory Allocation and De
allocation

Need of Dynamic Memory Allocation:
We often don't know
how much space we will need to store things at "compile time". Dynamic memory
allocation is the allocation of memory at "run time". With dynamic memory
allocation, while the program is running, the program requests more memory from
the computer. If there's enough memory available, the computer will grant the
program the right to use the amount it requests. After the dynamically allocated
space has been used it must be de-allocated.

Pointers and Dynamic Memory
Allocation:
Pointers come into play when we want to allocate and de-allocate
a chunk of memory while our program is running. Look at the following code.
int *ptr= new int ;
The new operation allocates space in the free store
(sometimes called the heap), which is a special region in the main memory area
dedicated to your program. The new operation assigns the amount of space needed
by the type of variable mentioned after it, in this case an int. If the new
succeeds, it returns a pointer to the allocated space. If it fails, it returns a
value of NULL.
One then uses *ptr, anytime access is needed to the space
pointed to. When one is finished with dynamically allocated space, one should
return it to the free store by using the delete operation as shown below. This
allows the space to later be reused for something else.
delete ptr;
Although dynamically allocated space should ideally be freed up when your
program ends, this does not always happen. A program that doesn't return all of
the space that it allocates is said to suffer from memory leaks. After running
the program one has less available memory than before, at least until the
computer is restarted.
You can also use ptr (in this example) as if it were
an array, because for all practical purposes it is! (The main difference is that
an ordinary array is kept in a different place in main memory than a dynamically
allocated array.) Remember that an array name is seen as a pointer to the first
data item, and that is precisely what ptr is. Thus you can use ptr[n] to get at
the item at index n in the array.
One again uses the delete operation to
free up space when finished with the allocated memory. However, with an array
the [] brackets are given between the delete and the pointer variable as shown
below:
delete [] ptr;

Dangling Pointer:
Dangling Pointer is a
pointer pointing to either unallocated memory area or to the area that has
already been freed. Dangling pointers arise when an object is deleted or
de-allocated, without modifying the value of the pointer, so that the pointer
still points to the memory location of the de-allocated memory. As the system
may re-allocate the previously freed memory to another process, if the original
program then dereferences the (now) dangling pointer, unpredictable behavior may
result, as the memory may now contain completely different data.A straight
forward example of dangling pointer is.

char *cp = NULL;

cp =
new char;
delete cp;

/* cp is now a dangling pointer as we have not
put it to NULL*/

To avoid a pointer becoming dangling, we can use NULL
reference.

Lab Tasks:

1) Write a program named “expandable
array”. Make a function “grow” which takes the old and new size of the array as
input and return a pointer to the new array. The program should take the number
of elements in the array from the user each time and dynamically allocate enough
memory until he decides to quit. The user should input the numbers in the array
each time and display them to show that expandable array works properly.
2)
Write the following code in the main method.
int *ptr = new int;
*ptr=5;
delete ptr;
cout<<*ptr<What is the problem in the above
code and how can it be solved?

3) Read the following code.
char
*string;
string = new char[20];
string = new char[30];
delete []
string;
What is the problem in the above code and how can it be solved?


4) Write a program that declares a structure named employee as
follows.
struct employee
{
char name [20];
int age;
float
income;
};
Now make an array of the employee structure of desired length
from the user using dynamic memory allocation. Print the data of all employees
and release the memory locations. Then ask if the user wants to perform data
entry and retrieval again.

Assignment 1

A very happy Eid to everyone and as Eidi, you people are going to get the first assignment of this course. I will discuss the assignment in the class briefly but all the details are already present on the 5 page document that you will download from this link. The due date for this assignment in 16/10/2009 by 12:00 Noon.

I have given this assignment earlier for the benefit of those who visit the site regularly. You can start the assignment early if you wish. Also, do the assignment yourself as failing to do so will ensure that you will fail all the quizes as those will almost always be based on the assignments that I will be giving you.

Assignment1

Stack in Arrays

Today's lecture was about stack. In a stack, the value that is inserted in the end is given out first, hence it is caled a LIFO (Last in First Out). The code for the stack implemented in a class is given below. You must note that I am returning the character value in pop whereas I had done the pop function differently in class. The point being, you can implement it many ways, just do it the way you like, are comfortable with or asked to do in a quiz or an assignment.

class Stack
{
private:
char* data; //character pointer
int head; //index counter
int maxSize; //maximum array size
public:
Stack(int);
void push(char);
char pop();
};

Stack::Stack(int num)//Constructor
{
head = -1; //setting head to -1;
maxSize = num;
data = new char[maxSize]; //declaring the stack size
for(int i = 0; i < maxSize ;i++) //initialising all values to NULL
{
data[i] = '\0'; //putting NULL values in the data array
}
}

void Stack::push(char c)//Adding a value
{
if(head == -1)
{
head++;
data[head] = c;
}
else if(head < maxSize - 1)
{
head++;
data[head] = c;
}
else
{
cout<<"Stack is full.";
}
}
char Stack::pop()
{
char c;
if(head==-1)
{
cout<<"Stack is empty.";
}
else
{
c = data[head];
head--;
}
return c;
}

Week 01/02

Introduction to Data Structures

A data structure can be defined as a structure that holds data. Up to this point, you should know about the different types of data that are available when we program. This data is critical in performing different operations and calculations. But so far, this data had been used without allocating any structure to it. Your programs had data and it was not organized. Has there been any data that you came across that had any structure to it? The basic data, having a bit of structure to it, that you came across was an array.

An array is a continuous sequence of one type of data. That data taken as a whole is known as an array and it is used as such. If you want to declare an array of integers of size 10, you will write it as:

int data[10];

Here, we have declared an array of integers, which is of size 10. This means that in the memory location, there are 10 integers, one after another, in a sequence and that collection is collectively called data. Now if we want to initialize this array, we can write:

for(int i = 0; i<10;i++>

{

data[i] = 0;

}

This code will initialize all the integers in the data array with the value 0. You can clearly see that, due to the presence of an array, the initialization of data can be easily done in a loop by writing a few lines of code. Thus having a proper structure for the data can be beneficial in performing computations. There are many other data structures that can be created and used in different programs. Some data structures have a specific name and are commonly used in programs. Others can be created on the basis of need, thus simplifying the way a person manages the data. These types of data are commonly known as Abstract Data Types or ADTs. But before we learn about them, we should discuss a specific construct of C/C++ and other object oriented languages, which allows the making of such ADTs possible. This is commonly known as a class.

Class & Structures

A class in C++ is an encapsulation of data members and functions that manipulate the data. What that means is, it is a structure that contains data which is hidden from the users and provides appropriate functions for changing the data under predefined conditions. A class can be defined like this:

class DataManager

{

private:

int x;

int y;

public:

DataManager() //Constructor

{

x = 0;

y = 0;

}

~ DataManager() //destructor

{

}

int Add()

{

return x+y;

}

};

struct DataManager

{

private:

int x;

int y;

public:

DataManager() //Constructor

{

x = 0;

y = 0;

}

~ DataManager() //destructor

{

}

int Add()

{

return x+y;

}

};

Now to explain this class and a structure:

In this class there are two variables x, y holding the data. There is a method/operation that performs the addition of both x and y and returns their sum. This operation is class specific and cannot be used without this class. Then there is a constructor method which, as you can see, has the same name as the class and does not return anything. There is also another function which has the same name as the class but a ~ comes before the name; this is known as a destructor. Whenever a class is declared a constructor is used to initialize its variables; a destructor is used to free up memory when the class variable is destroyed (more on that later).

Here, we have actually declared our own data type, known as DataManager. We can create its variables by simply writing:

DataManager manager;

Whenever we declare a variable of our defined class, that variable is normally referred as an object. So we can say that when we declare a class, we are defining an object which we are going to use in our program. Classes are the backbone of Object Oriented Programming, but here we are going to use them for defining Abstract Data Types.

Abstract Data Types

An abstract data type (ADT) is characterized by the following properties:

1. It exports a type.

Meaning that once an ADT has been defined, then variables can be declared with that ADT as the type

2. It exports a set of operations. This set is called interface.

It contains a set of functions that are made public for the users to use.

3. Operations of the interface are the one and only access mechanism to the type's data structure.

The defined functions are the only way by which that ADT can be used and manipulated

4. Axioms and preconditions define the application domain of the type.

There is a set of preconditions which define how the type should be used and what sort of conditions would produce what sort of a data.

In a high level language, say Java, ADTs are already specified, but since we are going to work in C++, we are going to declare the ADTs ourselves. The first step in this direction is to decide what we are going to keep as the internal storage container? We are going to start off with arrays and then later, move on to structures for declaring our internal storage containers. Keep in mind that for an array, the memory that has been allocated in the beginning, remains the same. Thus, we are going to find a work around this limitation in due time.

Bag

§ items can be added, removed, accessed

§ no implied order to the items

§ duplicates allowed

Set

§ same as a bag, except duplicate elements not allowed

§ It supports operations such as union, intersection, difference, subset

Lists

Items have a proper position in a list. A list can be of two types

1. Array List

2. Linked List

There is no specific way by which the data in a list can be accessed.

Stack

A collection of data where only the last element of the inserted data can be accessed.

§ Push data

§ Pop data

§ An indicator that always points to the top most element

§ Commonly known as a LIFO (Last In First Out) ADT

Queue

In a queue, the item that has been inserted in the beginning is accessed first

§ Insert data (Enqueue)

§ Remove data (Dequeue)

§ Commonly known as a FIFO (First In First Out) ADT

§ Keeps track of the first and last added item

There are more ADTs available, but we are going to keep the focus on Stack and Queue for now. We will start off by first implementing Stack and Queue by using an array and later implement the same by using a linked list.

Arrays

An ordered data item is called an array. It is a convenient way of accumulating data of the same type. All the data can be referenced by a single name and the individual data can be accessed by the appropriate index at which that data is present.

Declaring an array

An array is declared just like any other variable, the only difference being that the name is followed by the amount of data that variable is going to store. An integer array called data of length ‘10’ can be declared as:

int data[10];

It should be noted that every array begins with the index 0 and ends with the index n-1 where n is the length of the array. So for example, if I want to access the 5^th element of the data array I will call data[4] and similarly, if I want to access the last element, I will call data[9] as the total length is 10. Calling data[10] will cause an error as it does not exist since it is referring to the 11^th value of the data array which is actually not present.

Initializing an Array

You can initialize an array with different values like this:

int data[10] = {0,1,2,3,4,5,6,7,8,9};

but this can become troublesome for arrays with thousands of data. In such a case a simple for loop can suffice:

for(int i = 0; i<10;i++>

{

data[i] = 0;

}

This array can be graphically represented as:

data[0]	0
data[1]	0
data[2]	0
data[3]	0
data[4]	0
data[5]	0
data[6]	0
data[7]	0
data[8]	0
data[9]	0

Multidimensional Arrays

Sometimes you need to store in multi-dimensions, such is the case with matrices. This can easily be done by declaring a multidimensional array:

int matrix[2][2];

this matrix can be initialized as:

int matrix[2][2] = {1,0,0,1};

to make it look clearer, we can write this as:

int matrix[2][2] = { {1,0},{0,1}};

Graphically, it can be shown like this:

matrix[0][0] = 1	matrix[0][1] = 0
matrix[1][0] = 0	matrix[1][1] = 1

Here we have declared an identity matrix. We can also use nested for loops for initializing matrices:

for(int i = 0; i<10;i++>

{

for(int j = 0; j<10;j++>

{

data[i][j] = 0;

}

}

Arrays as Pointers

So far we have discussed the usage of arrays. Now we discuss what an array really is and how it can be used as a pointer in different situations.

Using an array name as a pointer

An array name is really a pointer to the first element of the array. For example, the following is legal.

int b[100]; // b is an array of 100 ints.

int* p; // p is a pointer to an int.

p = b; // Assigns the address of first element of b to p.

p = &b[0]; // Exactly the same assignment as above.

Array name is a const pointer

When you declare an array, the name is a pointer, which cannot be altered. In the previous example, you could never make this assignment. This means that the name of the array is actually pointing towards the address of the first element of the array series.

p = b; // Legal -- p is not a constant.

b = p; // ILLEGAL because b is a constant.

Pointer arithmetic

"Meaningful" arithmetic operations are allowed on pointers.

Add or subtract integers to/from a pointer. The result is a pointer.

Subtract two pointers to the same type. The result is an int.

Multiplying, adding two pointers, etc. don't make sense.

Pointer addition and element size

When you add an integer to a pointer, the integer is multiplied by the element size of the type that the pointer points to.

// Assume sizeof(int) is 4.

int b[100]; // b is an array of 100 ints.

int* p; // p is a a pointer to an int.

p = b; // Assigns address of first element of b. i.e., &b[0]

p = p + 1; // Adds 4 to p (4 == 1 * sizeof(int)). i.e., &b[1]

Equivalence of subscription and dereference

Because of the way C/C++ uses pointers and arrays, you can reference an array element either by subscription or * (the unary dereference operator).

int b[100]; // b is an array of 100 ints.

int* p; // p is a a pointer to an int.

p = b; // Assigns address of first element of b i.e., &b[0]

*p = 14; // Same as b[0] = 14

p = p + 1; // Adds 4 to p (4 == 1 * sizeof(int)). Ie, &b[1]

*p = 22; // Same as b[1] = 22;

Note: Incrementing a pointer using the unary ++ operator, either pre- or post-, increments the address it stores by the amount sizeof(type) where "type" is the type of the object pointed to. (i.e. 4 for an int)

Array of pointers

We can also define an array of pointers like this:

int* arrayOfPointers[10];

Each element of this array can point to an integer memory location. That is, every item of this array will store an address to an integer.

Pointers and Dynamic Allocation of Memory

int* a = NULL; // Pointer to int, initialize to nothing.

int n; // Size needed for array

cin >> n; // Read in the size

a = new int[n]; // Allocate n ints and save ptr in a.

delete [] a; // When done, free memory pointed to by a.

a = NULL; // Clear a to prevent using invalid memory reference.

It must be kept in mind that the same pointer can be used to point towards a single integer value like this:

int* a = new int; //Allocating memory to the pointer

*a = 10; //Putting the value 10 at the memory location

delete a; //Deallocating memory, there are no square brackets

a = NULL; //Clearing a

Parallel Array

In computing , a parallel array is a data structure for representing arrays of records. It keeps a separate, homogeneous array for each field of the record, each having the same number of elements. Then, objects located at the same index in each array are implicitly the fields of a single record. Pointers from one object to another are replaced by array indices. This contrasts with the normal approach of storing all fields of each record together in memory. For example, one might declare an array of 100 names, each a string, and 100 ages, each an integer, associating each name with the age that has the same index.

int ages[] = {0, 17, 2, 52, 25};

char *names[] = {"None", "Mike", "Billy", "Tom", "Stan"};

int parent[] = {0 /*None*/, 3 /*Tom*/, 1 /*Mike*/, 0 /*None*/, 3 /*Tom*/};

for(i = 1; i <= 4; i++)

{

printf("Name: %s, Age: %d, Parent: %s \n", names[i], ages[i], names[parent[i]]);

}