Laboratory: Array-Based Structures

Summary:

Prerequisites: Familiarity with arrays, stacks, and queues.

• Preparation
• Exercises
  • Exercise 1: Code Review
  • Exercise 2: Array-Based Stacks
  • Exercise 2: Array-Based Queues
  • Exercise 3: More Potential Problems
• For Those with Extra Time

Preparation

a. Create a directory for this lab. I would suggest CSC161/Labs/Linear.

b. Copy files from Examples/Linear. You can copy files individually, or just copy the tarball.

Exercises

Exercise 1: Code Review

a. Read through linear.h to make sure that you understand the basic operations we are providing in linear structures.

b. Read through the code of linear-expt.c and predict what output you should get for a stack.

c. Read through the code of linear-expt.c and predict what output you should get for a queue.

Exercise 2: Array-Based Stacks

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

b. Make and run array-stack-expt.

c. If all goes well (and I hope it will), you should see that these stacks work correctly.

Exercise 2: Array-Based Queues

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

b. Make and run array-queue-expt.

c. You are likely to observe the experiment segfault. Why? Because there's an error in add that doesn't handle the end of the array. In the standard design, if the tail has reached the end of the array, it should wrap around to the beginning. Updated add to ipmlement that strategy.

d. Review array-queue.c to note any other potential problems or errors. You may wish to correct them now.

e. Make and run array-queue-expt. If you have not fixed it already, you are likely to encounter an error because get also has the wrap-around problem. Fix it.

f. Review array-queue.c to note any other potential problems or errors. You may wish to correct them now.

g. Make and run array-queue-expt. There'also an error with clear that you may or may not have fixed. If you have not fixed it already, fix it.

h. You may have noted that is_empty and is_full were not written. If you haven't done so already, write them.

Exercise 3: More Potential Problems

There is some code that only runs if the ADDITIONAL_TESTS flag is set. Either compile with that flag set or remove the #ifdef and #endif lines.

a. What difference do you expect this change to make in each progrma?

b. Check your answer experimentally.

c. If you've found that the code revealed a new error, fix that error.

For Those with Extra Time

• Begin the next assignment.