INFORMATION & COMPUTER SCIENCE DEPARTMENT, KFUPM

ICS – 201 SECTION 55 & 56 (992 Semester)

INTRODUCTION TO COMPUTER SCIENCE

LAB #09 Dynamic Memory Allocation -Queue

Instructor: Bashir M. Ghandi

Objective: Learn how to allocate memory dynamically using malloc()

Implement the ADT-Queue using dynamic memory allocation

Problems with array implementation of ADTs?

· The problem with the array implementation of ADT is the fact that array must be declared with a fixed size at compilation. This leads to two possible problems:

• Either the size is too much, in which case the memory is being wasted or
• The size is too small, in which case stack overflow may be encountered

· In this Lab we shall develop a better way of constructing ADTs that does not have these drawbacks

Using malloc to obtain memory at run-time.

· Memory can be allocated dynamically (at run-time) using the function malloc() – accessible through <stdlib.h>

· The allocation is made from a special memory area called the heap

· The function, malloc() returns a pointer (address) to the allocated storage.

· However, malloc() does not associate any type to the pointer it returns – it is said to be void.

· For the pointer to be useful, it must be associated with a type using casting.

e.g. int *int_ptr;

int_ptr=(int *) malloc(2);

*int_ptr =17;

· The above statements reserve two bytes and returns the address of first byte, cast it to int and assigns it to integer pointer int_ptr.

· Since the bytes allocated to int is system-dependent, it is safer to use the function sizeof () to get the actual number of bytes associated with the particular type being considered.

· sizeof() is system-independent and can be used even with user-defined types.

· Thus, the above statements are better represented as follows:

int *int_ptr;

int_ptr=(int *) malloc(sizeof(int));

*int_ptr =17;

· Note that there is no name associated with the memory obtained by malloc. It can only be accessed as *int_ptr. It is sometimes called anonymous variable.

· Thus, should int_ptr be given another address, the location (returned by malloc) will be lost . It can neither be accessed by the program nor by the system. It is said to be a lost object.

· When we no longer need a dynamic variable, we can return the storage it occupies using the free() function.

E.g. free(int_ptr);

Queue Implementation

· In this implementation, we think of a queue as a sequence of nodes with each node pointing to the next except the last which points to NULL. We also have two pointers, front and rear which points to the front and rear nodes respectively.

· The following diagram illustrates this idea.

· Initially, both front and rear are set to NULL, indicating that the queue is empty.

To add an element we proceed as follows:

• We obtain a node using malloc()
• Add new_item to the item field of the new node
• Set the next field of the new node to NULL
• Connect the new node to the current rear node
• Re-direct the rear pointer to point to the new node.
• If this is the first node being added, front pointer is also re-directed to point to it.

To remove an item front the front:

• First we return the item field of the current front node
• Use a temporary pointer to point to the current front node
• Sets the next field of the current front node to be the new front and then
• free the node being pointed by the temporary pointer.
• If the queue is now empty as a result of the removal, rear is also set to NULL

See the files queue.h and queue.c which downloadable from my home page for details.

Programming Exercise:

1. The file queue.h contains the user-interface of queue implementation using dynamic memory allocation and the file queue.c contains the implementation details. The program lab9_1.c is a menu-driven program that tests the queue implementation. Copy the three files from my home page, study them to make sure you understand them, put the .C files in a project, build and test-run.

2. Notice that option 3 (Display the queue) in lab9_1.c is not implemented. Implement it adding the another function, Traverse, in the file queue.c that prints all the elements of the queue without changing the queue. Then modify the main program to make use of this function to print all elements of the queue –they should appear in order.

3. Introduce the following data types into the queue.h

typedef char STRING[50];

typedef struct { long int id_no;

STRING name;

int exam1,exam2,exam3;

float average;

} STUDENT_REC;

Now change the ITEM_TYPE from int to STUDENT_REC.

Modify the program in (2) above to handle structures of type STUDENT_REC instead of integers. Note: You should make use of the functions: get_record, get_average, and print_record from the previous labs.

4. Modify the program in (3) above by introducing and implementing another menu option, “Print Vertically”, that prints all records in the queue in column format.

Home Work:

Implement ADT stack using dynamic memory allocation. Re-write the program in (4) above to handle stack instead of queue. Add an additional menu option that allows the stack to be created by reading the records of the file exams2.dat.