Monash University > CSSE > CSE1303 > Part A > Tutorials > Tutorial A4

CSE1303 Computer Science
Semester 2, 2003
Part A
Tutorial A4 : Linked Structures

This tute covers material from lectures A07 to A09.

There may not be time in the tutorial to cover all of these questions. Attempt at least the ones marked with an asterisk before the tutorial; these are the ones that will be focussed on during the class. If you have specific questions about unmarked questions, you can ask the tutor about them during the tutorial. If you want further revision questions, suggestions of questions from the textbooks are provided at the end of the tutorial sheet.

---

Note: The purpose of tutorials is not simply to give you the answers to these questions! (Solutions will be released in about a week online, so if all you want is the answers, there are easier ways.)

---

* Exercise 1

1. Write a C function int stackSum(const Stack* stackPtr)which returns the total of the items in a Linked Stack.
   Assume the stack is declared as follows:

   typedef struct NodeRec {
      int value;
      struct NodeRec* nextPtr;
   } Node;
   
   typedef struct StackRec {
      Node* topPtr;
   } Stack;
   

2. Write a C function void clearStack() which deletes all the items in the linked stack.

* Exercise 2

Consider the following code, where linkQueue.his defined as it is in the lecture notes.

#include "linkQueue.h"

float item;
Queue theQueue;

Assume at some stage the Linked Queue associated with theQueue can be represented as in the following diagram:



Now assume that the following function call is then made:

item = serve(&theQueue);

1. What is now the value of theQueue.frontPtr?
2. What is now the value of theQueue.rearPtr?
3. What is the value of item ?
4. What is the value of (theQueue.frontPtr)->nextPtr ?

* Exercise 3

Assume that the Linked Queue is defined as it is in the lecture notes to hold items of type float. Write a C function void countQueue(Queue* queuePtr) which counts the items in the Linked Queue without using the internal counter.

Exercise 4

1. Change the function Node* setPosition(List* listPtr, int position) given in the lectures notes so that it returns NULL if position corresponds to an invalid position in the list.

2. Now change the function void insertItem(List* listPtr, float item, int position) given in lectures notes so that it works correctly using the new version of setPosition for all possible inputs.

* Exercise 5

Assume the function char* strdup(const char* s), (which makes a copy of the string s and returns the address of the copy), is defined and suppose

struct DoubleLinkNodeRec
{
   char* str;
   struct DoubleLinkNodeRec* nextPtr;
   struct DoubleLinkNodeRec* previousPtr;
};
typedef struct DoubleLinkNodeRec Node;

1. Write a C function Node* makeNode(const char* s)which allocates memory for a new Node and also:
   • returns NULL if the memory cannot be allocated,
   • assigns the member str, of the new node, the address of a copy of s, and
   • assigns both the members nextPtr and previousPtr, of the new node, the value NULL.

2. Write a C function void killNode(Node* nodePtr) which deallocates all the memory associated with the node pointed to by nodePtr.

* Exercise 6

(Preparation for Prac A04)

Write a C function that reads a string from the user that could be in any of the following formats, and outputs the correct output as shown below:

number p	Print "Line number to be printed is number-1"
$r string	Print "Reading from filename: string"
d number	Print "Deleting line number: number"

Where number is an integer, string is a character string. The other characters there: $r, p, and d are to be read literally.
Make sure you deal with invalid input.

ADDITIONAL EXERCISES

Kruse et al. 2e
    Exercises 3.1: E9 a-b
    Exercises 4.6: E2 a-d, E4 a-b, E5 a-c, E6
    Exercises 5.1: E1, E2, E3, E4, E5, E6, E8, E9, E10
    Exercises 5.3: E2 a-d
    Review Questions: 1, 2, 3, 8

Deitel & Deitel 2e
    Self Review Exercises 12.1 c, h, 12.2, 12.3, 12.4 a-e
    Exercises: 12.6, 12.7

[ Top | Home ]

Last modified 2002-07-03