Dec1999 CA208 : 'C' Programming (Question 2)Suggested Solutions

You are to implement a task queueing system.When a task is entered into the system,it has assigned to it a priority,which is one of low,medium or high,and a name,which is a string of arbitrary length.The definition of the queue is given below,where front points to the first task in Q ,back points to the last task in Q .A task contains a link to the next task in Q .

typedef struct {
	task*front;
	task*back;
} task_queue;

Do not award half marks.Do not deduct marks for trivial syntactic errors. Alternative correct answers should be given credit,unless otherwise indicated in the marking scheme.

(a)

Define a suitable enumerated type,priority ,which can take on any one of the values low ,medium or high .

typedef enum priority {low,medium,high};

[1]

(b)

Define a suitable data structure task ,which can be used to hold the following information about a task:

•The task priority of the task;
•The name of the task;
•A pointer next ,which will point to the next task in the queue.

A sample definition of task follows:

typedef struct queue_element {
	priority task_priority; charname; int number; struct queue_elementnext;
}	task;

And the following marking scheme should be used:

•Declaring the tag queue element which can be used for the subsequent pointer definition;(1 mark)

•Declaring a member variable of type priority ;(1 mark)

•Declaring the character pointer name;(1 mark)

•Declaring the next pointer,to be of the tag type;(1 mark)

[4]

(c)

Write a function,called IsEmpty ,the signature of which is given below,which takes in a pointer to a queue x ,and returns 1 if the queue is empty,and 0 otherwise.You may assume that an empty queue will have NULL pointers for the head and the tail.

int IsEmpty(task queue*x);

A sample definition of IsEmpty is given below:

int IsEmpty(task_queue*x) {
	return (x->head==NULL &&x->tail==NULL);
}

And the following marking scheme should be used:

•Correctly referencing the front and back ;(1 mark)

•And testing that they are NULL ;(1 mark)

•Returning the anded result of these tests.(1 mark)

[3]

(d)

Write a function,called Head ,the signature of which is given below,which takes in a queue x of type task queue ,and removes the item at the head of the queue,should the queue be non empty.The item should be returned as the reference parameter y , and the function should return the number of items which have been successfully removed from the queue.

int Head(task queue*x,task*y)

A sample definition of Head follows:

*int Head(task_queuex,tasky){*
	if(IsEmpty(x))
		return 0;
	y=x->front; x->front=x->front->next; if(x->back==y){
		x->front=NULL; x->back=NULL;
	} return 1;
}

And the following marking scheme should be used:

•Ensuring the queue is non empty before attempting to remove an item;(1 mark)

•Returning 0 if the queue is empty,and consequently no items are removed; (1 mark)

•Setting the pointer y to point to the item at the head of the queue;(1 mark)

•Setting the front pointer to point to the item which is next in the queue;(1 mark)

•Checking to see of the resulting queue is empty;(1 mark)

•And resetting the front and back pointers if it is;(1 mark)

•Returning 1 at the end if an item has been removed and returned.(1 mark)

[7]