April2000 CA208 : 'C' Programming (Question 3)Suggested Solutions

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

You are to implement a stack which can be used for job control.When a job is created by the system,a stack element is created which is used to store the details of the job.Jobs are always added to and removed from the top of the stack,thereby making it a first in last out data structure,and each element added to the stack also contains a ointer which is used to point to the next element down the stack.
Consider the following type definition of a Stack in C,and the definition of elements which can be placed on and removed from the stack:
typedef struct {
  stack_element* top_of_stack;
} Stack;
typedef struct node {
  node* next;
  Job JobInfo;
} stack_element;

(a)Define a suitable enumerated type,called JobType which can take on any of the values SystemJob ClientJob or ServerJob [1mark ]
typedef enum JobType = {SystemJob, ClientJob, ServerJob} [1 mark ]

(b)Give a definition of the structure Job which contains the members type which is a JobType and data which is a pointer with an undefined type.[3 marks ]
A sample definition of Job follows:
typedef struct Job {
JobType type;
void* data;
}
And the following marking scheme should be used:
•A correct struct definition;(1 mark)
•Including a JobType;(1 mark
•Including a void pointer JobData (1 mark) [3 marks ]

(c)Define a function,IsEmpty the signature of which is given below,which takes a stack s and returns 1 if the stack is empty,and zero otherwise.A stack is defined to be empty if there are no elements on the stack.
int IsEmpty(const stack* s); [2 marks ]
A sample definition of IsEmpty follows:
int IsEmpty(const stack* s) {
  if(s== NULL)
    return 1;
  else
    return 0;
}
And the following marking scheme should be used:
•Testing the s parameter for a NULL value;(1 mark)
•Returning the correct value basedon the results of the test.(1 mark)
[2 marks ]

(d)Define a procedure Push the signature of which is given below,which takes a reference to a stack s and a reference to a stack element e and will add the element to the top of the stack.Your procedure should ensure that both the stack pointer and the reference to the next item in the stack are updated,should it be necessary.
void Push(stack* s, stack element* e); [4 marks ]
A sample definition of Push follows:
void Push(stack* s, stack_element* e) {
  if(!IsEmpty(s)) {
    e->next= s;
  } else {
    e->next= NULL;
  }
  s= e;
}
And the following marking scheme shouldbe used:
•A conditional statement testing for the non empty stack condition;(1 mark)
•Setting e.next to s if the stack is non empty;(1 mark)
•And to NULL otherwise;(1 mark)
•Updating the stack ointer s to point to the new element.(1 mark)
[4 marks ]

(e)Define a procedure Pop the signature of which is given below,which takes a reference to a stack s anda stack element e The procedure should remove the to element from the stack,returning a reference to the element removed,and should return the number of items successfully removed from the stack.
int Pop(stack* s, stack element* e); [5 marks ]
A sample finition of Pop follows:
int Pop(stack* s, stack_element* e) {
  stack_element temp;
  if(IsEmpty(s) {
    e= NULL;
    return 0;
  } else {
    e= s;
    s= e->next;
    return 1;
  }
}
And the following marking scheme shouldbe used:
•A conditional statement testing for the non empty stack condition;(1 mark)
•Setting e to NULL if there is no item to return;(1 mark)
•Setting e to the item at the to of the stack (s if it is non empty;(1 mark)
•And resetting the stack pointer to oint to the net item;(1 mark)
•Returning 1 if there was an item,0 otherwise.(1 mark)
[5 marks ]