Laboratory: Linked Structures

Summary:

Prerequisites: Familiarity with pointers, linked lists, malloc, and more. The array structures lab.

• Preparation
• Exercises
  • Exercise 1: Linked Stacks
  • Exercise 2: Linked Queues
• For Those with Extra Time

Preparation

a. Make sure that you have the diretory for the previous lab. I had suggested something like CSC161/Labs/Linear.

b. To that direcectory, add linked-stack.c and linked-queue.c.

c. To that directory, add the updated Makefile.

c. To that directory, add an updated copy of linear-expt.c.

d. Review linear-expt.c to ensure that you have a sense as to what the output should be for stacks and queues. (You might find it useful to write down a summary of the expected output.)

Exercises

Exercise 1: Linked Stacks

a. Read through the code of linked-stack.c to ensure that you understand the parts. Make note of any potential problems or errors you observe.

b. Make and run linked-stack-expt.

c. As you may have noted, while linked-stack-expt gives the correct stack output, suggesting that linked-stack.c is correct, there does seem to be a memory leak in the program. Repair that leak. You will want to pay particular attention to destruct, get, and clear.

Exercise 2: Linked Queues

a. Read through the code of linked-queue.c to ensure that you understand the parts. Make note of any potential problems or errors you observe.

b. Make and run linked-queue-expt.

c. You are likely to observe the experiment segfault. Why? Because add is not defined. Define it.

d. You may also encounter another error because there is a small bug in get having to deal with deleting the last element of a list. Fix that bug.

e. Check for memory leaks.

For Those with Extra Time

• Finish the previous lab.
• Begin the next assignment.