December 1998
CA208: 'C' PROGRAMMING

QUESTION 5

Total Marks: 20 Marks

 Click here to access other questions

SUGGESTED SOLUTIONS
Solutions and allocated marks are indicated in green.
Return to Question 5

 
(a) Give the following definition of a linear linked-list type as the representation of the elements of a stack,

typedef struct stack_element {
    int data;
    struct stack_element *next;
} StackElement;

typedef struct {
    StackElement *pop_of_strack:
} StackType;

The following questions require the definition of a series of functions that form an interface to a stack. You can assume that the stack argumnet to each of the functions is a non-null pointer, and points to a valid StackType.

 

 [2]
(a) Write a function isempty, that has the function prototype shown below, that returns a one if stack is empt, and zero otherwise.

int isempty(StackType *stack);

 

 [2]
A definition of  isempty follows:

int isempty(StackType *stack) {
   return (stack->top_of_stack==NULL);
}

and the following marking scheme should be used:

  • one mark for returning one when the stack is empty
  • one mark for returning zero when the stack is non-empty
  • no marks should be deducted for trivial syntactic errors.

 
(b) Write a procedure push, that has the procedure prototype shown below, that pushes the element x x onto the stack stack. You assume that stack will always be a non-null pointer to a valid StackType.

void push(StackType *stack, int x);

 

 [4]
A definition of  push follows:

void push(StackType *stack, int x) {
   StackElement *temp;

   temp = (StackElement*)
          malloc(sizeof(StackElement));
    temp->data=x;
    temp->next=stack->top_of_stack;
    stack->top_of_stack=temp;
}

and the following marking scheme should be used:

  • one mark for creating a fresh StackElement.
  • one mark for assigning data into the stack element.
  • one mark for making the next field what is currently at the top of the stack.
  • one mark for changing the top of the stack to the new node.
  • no marks should be deducted for trivial syntactic errors.

 
(c) Write a function pop, that has the function prototype shown below, that returns and then removes the top element from the stack stack. You should call the functino error (with prototype below), if it is not possible to remove an element from the stack.

int pop(StackType *stack);
void error(void);

 

 [5]
A definition of pop follows:

int pop(StackType *stack) {
   int result;
   StackElement *ptr;
   if (stack->top_of_stack == NULL) error();
  else {
      ptr=stack->top_of_stack;
      result=ptr->data;
      stack->top_of_stack = ptr->next;
      free(ptr):
      return result;
  }
}

and the following marking scheme should be used:

  • two marks for raising an error when the stack is empty.
  • one mark returning the data held at the top of the stack.
  • one mark changing the top of stack pointer to point to the second element in the stack.
  • one mark for freeing the node at the top of the stack.
  • no marks should be deducted for trivial syntactic errors.

 
(d) Write a function concatenate, that has the function prototype shown below, that joins the two stacks left and right together. i.e., if left contained the sequence [1,2,3] and right [4,5], then the function should alter left so that it represents the sequence [1,2,3,4,5].

void concatenate(StackType *left, StackType *right)

 

 [5]
A definition of concatenate follows:

void concatenate(StackType *left, StackType *right) {
   StackElement *ptr;

   ptr=left->top_of_stack;
   if(ptr==NULL) *left=*right;
   else {
      while (ptr->next!=NULL) {
         ptr=ptr->next;
      }
      ptr->next=right->top_of_stack;
   }
}

and the following marking scheme should be used:

  • two marks for assigning *right to *left in the left stack is empty.
  • one mark for iterating down the left hand stack...
  • ...one mark for stopping on the last entry in the stack.
  • one mark for joining the null field in the last entry in the left stack, to the top of the right stack.
  • no marks should be deducted for trivial syntactic errors.

 
(e) Using the function pop and isempty defined below, define a procedure popmany, that has the functino prototype shown below, that removes the top n items from the stack, if the stack contains at least n items; otherwise all items are removed from the stack.

void popmany(StackType *stack, int n)

 

 [4]
Two possible definitions of popmany follows:

void popmany(StackType *stack, int n) {
   if (!isempty(stack) && n>0) {
     pop(stack);
     popmany(stack,n-1);
}

void popmany(StackType *stack, int n) {
   int i;

   for(i=0;i<n;i++)
      if (!isempty(stack))
        pop(stack);
}

and the following marking scheme should be used:

  • two mark for not popping the stack if it is empty.
  • one mark for repeatedly poping the stack with pop,...
  • ... until n items have been deleted (1 mark) returning the data held at the top of stack.
  • no marks should be deducted for trivial syntactic errors.