CS61C

Purpose

Information

Estimated conceptual difficulty: 4/5
Estimated temporal difficulty: 4/5

Due date: Monday, October 16, 2000 at 23:59:59 for all lab sections.

Partners: Prelabs must be turned in individually. You are allowed, but not required, to work with up to two partners, making a team of three people. Only one partner needs to submit all files, but be sure that all partners' logins appear on all of your files.

Relevant Reading: Lectures 2 (1Sep), 8 (22Sep), 12 (6Oct), K&R 5.1-.6, 6.1-.5.

This lab uses binary trees, not binary search trees and not B-trees as a medium for refining your understanding of pointers and structs in C and MIPS. Each node in the binary tree has a left child, a string as its value, and a right child.

You will complete or write two functions, NodeAdd and NodeRemove. You will write nodeAdd in MIPS only, and nodeRemove in both C and MIPS. You may also need to write additional helper functions.

1. NodeAdd takes a tree, a position, and a string as arguments. It constructs a new Node, with a pointer to the string (it does not copy the string). It inserts newNode at the specified position in the tree. It returns newNode, or NULL if an error occurs.

The root node has position 1. Nodes on the next generation (one line down) have positions 2-3, from left to right. Nodes on the next generation (another line down) have positions 4-7, from left to right. For example:
       1
      /|\
     / | \
    / "a" \
   /       \
  2         3
  |\       /|\
  | \     / | \
 "b" 5   6 "d" 7
     |   |     |
    "c" "e"   "f"
Note that position 4, although empty, is still reserved.

If there is already a Node, oldNode, at the specified position, then oldNode becomes the child of newNode. If oldNode was the left child of its parent, then oldNode becomes the right child of newNode. Otherwise, oldNode becomes the left child of newNode. For example, adding a new Node with string "g" at position 2 would result in:
        1
       /|\
      / | \
     /  |  \
    /  "a"  \
   /         \
  2           3
  |\         /|\
  | \       / | \
 "g" 5     6 "d" 7
     |\    |     |
     | \  "e"   "f"
    "b" 11
        |
       "c"
"b" was the left child of "a", so "b" becomes the right child of "g".

2. NodeRemove takes a tree and a string as arguments, and returns a Node. It searches the tree for the first occurence of the string. It removes the corresponding Node, returnNode, from the tree, and returns returnNode, or NULL if an error occurs or the string is not found. The search recursively examines the current Node, then the left branch, then the right branch.

If returnNode is not a leaf, then removal could leave orphans in the tree. For example, removal of "d" would orphan "e" and "f". This orphaning should be patched up by finding a leaf Node in returnNode's subtree, and relinking the leaf Node to replace returnNode in the tree. The leaf Node is found recursively as follows: Start with returnNode as the root of the current subtree.

If the current subtree is a leaf, use it as the replacement (this will be false in the first recursion).

Otherwise, if the current subtree is the left branch of its parent, try to find a replacement in the right branch of the current subtree. If there is no right branch, find a replacement in the left branch.

Otherwise, try to find a replacement in the left branch of the current subtree. If there is no left branch, find a replacement in the right branch.

returnNode->left and returnNode->right should NOT be set to NULL.

Prelab

Tasks

Task 1: Type

cp -r ~cs61c/lab7 ~

Task 2: Complete the functions NodeRemove in C, NodeRemove in MIPS, and NodeAdd in MIPS. You do not have to use the provided skeletons. If you wish, you may write part or all of any of the three files from scratch. Everything, you write, however, must still work with the provided tests. It is not recommended to write nodeadd.s and noderemove.s from scratch.

For nodeadd.s, there are 5 instructions which have been removed from the file. Instructions 1-4 have been removed in two places each. Instruction 5 has been removed from 3 places. So, a total of 11 lines (but only 5 unique instructions) are missing. Your job is to figure out what the 5 missing instructions are, and write them into the code. You should have the same instruction for both instances of #1, the same instruction for both instances of #2, etc. I hope these instructions are clear. You'll note that this means you only have to write 5 lines of MIPS for nodeadd.s!

For noderemove.s, you must write your own strcmp in MIPS (if you want to use the provided code). This should be a piece of cake after sprintf. Additionally, there are 3 instructions near the bottom of the file which have been removed, just like in nodeadd.s. Each one has been deleted in two places (it's the same instruction, two instances of which have been deleted). You need to figure out what the appropriate instructions are, and write them into the code. The TA strcmp is 8 lines. So, you only need to write a total of 8 + 3 + 5 = 16 lines of MIPS for this lab! You may use pseudoinstructions.

Task 3: Test it!
gmake lab7 compiles your C code
gmake lab7.s compiles your MIPS code
gmake clean removes old .o files, etc.
gmake testc runs your C code through a rigorous test
gmake tests runs your MIPS code through a rigorous test
Your test output will be in files testOutputC and testOutputS.

Task 4: To submit: In your lab7 directory, type submit lab7. The required files are noderemove.c, nodeadd.s, and noderemove.s.

Task 5: No more to come!

Feedback