Exercise 5 (by Mikael Eriksson, TA HT2015)


Go through exercises 5.



Talked about variable allocation and deallocation, stack vs heap, pointers, lists, trees and the idea of ADT.



Exercise 5.6 Using a queue/list structure to simulate bus traveller queue



/* Ex 5_6: Bus stop queue

151203, miker at kth.se

*/


#include <stdio.h>

#include <stdlib.h>

#define BUS_INTERVAL 10

#define PROBABILITY 0.9


// We use elementStorage to store the arrival time

// of the traveller. That is easier than storing

// waiting time directly as then we would have to

// do continuous updating every minute.


struct elementStorage {

int dataitem;

struct elementStorage * next;

} ;


typedef struct elementStorage element;


// Just copy the definitions (actual code) for

// the following functions from lab 4

// (Oh and implement size() in order to know

// how many people are in the queue at any time.)

element * AddItem (element * adt, int data);

element * RemoveItem (element * adt);

void Print (element * adt);


int main () {


printf("Starting bus simulation\n");

element *queue = NULL;

int t;

for (t = 0; t < 50; t++) {

double p = (rand() / ((double) RAND_MAX + 1));

// printf("p = %lf\n", p);

if (p < PROBABILITY) {

// Add a person to the queue

queue = AddItem(queue, t); // Why assignement necessary?

printf("A person entered the queue.\n");

}

if (t % BUS_INTERVAL == 0) {

// Bus arrived!

printf("Bus arrived! \n");

int nrOfPassengers =

(int) (5 + 10*(rand() / ((double) RAND_MAX + 1)));

int i;

for (i = 0; i < nrOfPassengers; i++) {

if (queue != NULL) {

printf("Person entering the bus ");

printf("after %d minutes\n", t - (queue -> dataitem));

queue = RemoveItem(queue);

} else {

printf("The queue is empty!\n");

break;

}

}

} // end-if bus stop

} // end-for simulation time

}/* end main */


The answer to the commented question ”Why assignement necessary?” above, is that it is needed for the first call to AddItem, as that actually gives a pointer to the new element (otherwise the list reference would remain NULL).