COMP 1917 Computing 1
Session 2, 2016

Tutorial - Week 11

Presentation Topic for Week 11

Describe positives and negatives of arrays and linked lists. When would you use a linked list over an array?

We will now get some hands on experience with those differences. One of the core data structures in computer science is a queue. Queue is often referred to as FIFO, meaning that the first element added to the queue is the first one to be removed. There are several ways to implement a queue. We will now investigate 2 of them.

Firstly, we will build a linked list based queue. Using the following struct definition 

    typedef struct node* Lnode;

    struct node{
      int val;
      Lnode next;  
    };

    typedef struct _queue* Queue;

    struct _queue{
        Lnode head;
        int num_nodes;
    };
implement the function below.
  1. Write a function Queue createQueue(void) that creates a new Queue.

  2. Write a function void enqueue(Queue q, int val) that adds an item to the queue.

  3. Write a function void dequeue(Queue q) that removes an item from the queue.

  4. Create a separate file called testQueue.c and test the above functions.

    Now we will build an array based queue. Use the following struct definition 

    typedef struct _queue* Queue;

struct _queue{
    int *array; // make it 10 elements initially
    int num_nodes;
};
  5. Are there any disadvantages of this implementation in comparison to linked list one.

  6. How would you change your tests if you use this representation?

  7. Write whitebox tests for both implementations.

  8. If time allows use your valgrind and gdb skills to debug the following code

Presentation Topic for Week 12

Explain Type Conversion in C. In what situations does type conversion occur?