EECS2031-Assignment 2 Self-Referential Structures Solved

Problem 1 Doubly linked list in C    
Subject:  Stream IO, Structures, Array of structures, memory allocation

Specification   
You have practiced in lab 6 the linked list where each node has one pointer to the next node. That kind of linked list is also called singly linked list.  Based on that experience, here you write an ANSI-C program to implement a full-fledged doubly linked list data structure. In a doubly linked list, each node has two pointers, one point to the next node in the chain and one points to the node preceding it. The first node’s pointer to previous node is NULL, as shown below. 

  

  

A doubly linked list can be traversed in both directions. At the cost of more space per node (due to the extra pointer to the preceding node), some operations can be more efficient than on singly linked list.

 

Implementation
You are provided with a partially implemented program a2List.c, and a data file data.txt. 

Study the existing code of a2List.c, which does the following:

•        Opens a data file data.txt using FILE IO in C. The file contains lines of integers, each line contains exactly two integers. (Stream and FILE IO is a topic that is usually in the syllabus but is skipped this semester.)

•        Reads the data file line by line, and store the two integers in each line into a structure of type twoInts. The structures are maintained by  arr, which is an array of pointers to struct twoInts.

The structure twoInts contains two integer data members.

▪   the structure pointed by the pointer in arr[i] gets the two values for its data members from the two integers in the i’th line of the file. For example, the structure pointed in arr[0] gets the two values for its members from the two integers in the first line of the file,  arr[1] gets the two values for its members from the two integers in the second line, and so on.

  

Based on the existing implementation, implement the following:    

•        In main, build the linked list (pointed by head) by reading in pointee structures maintained in the pointer array, adding up the two integer fields and then inserting the sum value (as a char) into the linked list.

•        Implement or complete the following functions.

o   int len(), which returns the number of nodes in the list.

o   char get(int index), which returns the data value of the node at index index. Assume the list is not empty, and index is in the range of [0,len()-1].

o   int search(char key) which searches the list for node with data key.

o   void insert(char d), which inserts at the end of the list a new node with data d. The list may or may not be empty. o void insertAfter(char d, int index), which inserts into the list a new node with data d, after the node at index index.  

Assume that the list is not empty, and index is in the range of [0,len()-1].

o   void delete (char d) which removes the node in the list that has data value d. Assume the node is not empty, and all the nodes in list have distinct data, and the node with data d exists in the list.   

Hint: the slides and the Java program for lab6 will probably help you.  Don’t add any global variables in your solution. 

 

Sample Inputs/Outputs: (download – don’t copy/paste - the input file data.txt) red 419 % gcc a2List.c red 420 % a.out arr[0]: 83 6 arr[1]: 71 8 arr[2]: 30 52 arr[3]: 26 49 arr[4]: 33 52 arr[5]: 14 62 arr[6]: 0 65 arr[7]: 1 65 arr[8]: 2 81 

 insert Y: (1)  Y    <--    Y insert O: (2)  Y  O    <--    O  Y insert R: (3)  Y  O  R    <--    R  O  Y insert K: (4)  Y  O  R  K    <--    K  R  O  Y insert U: (5)  Y  O  R  K  U    <--    U  K  R  O  Y insert L: (6)  Y  O  R  K  U  L    <--    L  U  K  R  O  Y insert A: (7)  Y  O  R  K  U  L  A    <--    A  L  U  K  R  O  Y insert B: (8)  Y  O  R  K  U  L  A  B    <--    B  A  L  U  K  R  O  Y insert S: (9)  Y  O  R  K  U  L  A  B  S    <--    S  B  A  L  U  K  R  O  Y remove B: (8)  Y  O  R  K  U  L  A  S    <--    S  A  L  U  K  R  O  Y remove S: (7)  Y  O  R  K  U  L  A    <--    A  L  U  K  R  O  Y remove A: (6)  Y  O  R  K  U  L    <--    L  U  K  R  O  Y remove O: (5)  Y  R  K  U  L    <--    L  U  K  R  Y remove R: (4)  Y  K  U  L    <--    L  U  K  Y remove K: (3)  Y  U  L    <--    L  U  Y remove Y: (2)  U  L    <--    L  U  ` remove U: (1)  L    <--    L    ` remove L: (0) 

insert Y: (1)  Y    <--    Y insert O: (2)  Y  O    <--    O  Y insert R: (3)  Y  O  R    <--    R  O  Y insert K: (4)  Y  O  R  K    <--    K  R  O  Y insert U: (5)  Y  O  R  K  U    <--    U  K  R  O  Y insert L: (6)  Y  O  R  K  U  L    <--    L  U  K  R  O  Y insert A: (7)  Y  O  R  K  U  L  A    <--    A  L  U  K  R  O  Y insert B: (8)  Y  O  R  K  U  L  A  B    <--    B  A  L  U  K  R  O  Y insert S: (9)  Y  O  R  K  U  L  A  B  S    <--    S  B  A  L  U  K  R  O  Y 

 get(0): Y get(3): K get(6): A get(7): B get(8): S  

insert x after index 2: (10) 

  Y  O  R  x  K  U  L  A  B  S    <--    S  B  A  L  U  K  x  R  O  Y insert y after index 0: (11) 

  Y  y  O  R  x  K  U  L  A  B  S    <--    S  B  A  L  U  K  x  R  O  y  Y insert z after index 6: (12) 

  Y  y  O  R  x  K  U  z  L  A  B  S    <--    S  B  A  L  z  U  K  x  R  O  y  Y 

 get(0): Y get(3): R get(6): U get(7): z get(8): L  search y ....  found search o ....  not found search r ....  not found search k ....  not found search U ....  found search x ....  found search y ....  found search Z ....  not found search A ....  found search b ....  not found red 421 % 

 

Question 2  Binary search tree in C
Subject:  Stream IO,  Structures, recursions, tree structures

Specification
Here you are going to implement another important self-referential data structure – binary search tree

(BST). (If you have not learned this data structure yet, you will learn it very soon.)

Binary Search Tree is a node-based binary tree data structure which has the following properties:

•        The left subtree of a node contains only nodes with keys lesser than the node’s key.

•        The right subtree of a node contains only nodes with keys greater than the node’s key.

•        The left and right subtree each must also be a binary search tree.  

Note that this recursive definition implies that for each node, the left child (if exists) is smaller than the node and the right child (if exists) is larger than the node.  In addition,  

•        “Inorder traversal” on the tree visits node values in ascending order

•        min value is always stored in the left most node, and max value is stored the right most node, as shown below.  

 

You can find tons of online resources about BST.  Below is an example of BST of integers after a sequence of insertions.

 size 1  size 3  min 10 min 5 

size 6  

min 4 

size 9 min 4 

 

Implementation
You are provided with a partially implemented program a2BST.c, and a data file data2.txt. Study the existing code of a2BST.c, paying attention to how the tree node struct is defined. The program opens a data file data2.txt using FILE IO in C. The file contains lines of integers. The program reads the data file line by line and inserts some integers into the tree, and then traverse and search the tree.  

Based on the existing implementation,  

•        complete the codes in main() that retrieve and print the min key in the current tree. 

•        implement or complete the following functions.

o   void createRoot(), which creates a root node with given key. In tree is initially empty, where the root is NULL. After function call,  the root node has NULL pointers. This function can be called in main, and can also be called in other functions.

o   int size(), which returns the number of nodes in the BST. Hint: you may want to use recursions.

o   int search(int key) which searches the BST for node with data key.  The key may or may not exist in the tree.  As you may know, since the data are organized in some order, you don’t need to visit every node in the tree, as you did in linked list. What you will do is that you start at the root, and then compare the value to be searched with the value of the root. If they are equal we are done with the search. If it’s lesser than the root, then you need to go to the left subtree only because in a binary search tree all the elements in the left subtree are lesser and all the elements in the right subtree are greater. Likewise, if it’s larger than the root then you go to the right subtree. At each step you go either towards left or right and hence at each step you discard one of the sub-trees. Hint, this can be done either iteratively or recursively.

o   struct node *minValueNode(), which returns the pointer of the node with the minimum key value.

o   void insert(int key), which inserts a node with value key into the BST. The tree may or may not be empty. Assume the key to be inserted does not exist in the current tree.  

You start searching the key from the root until you hit a null child of a node. Then the new node is added as a child of the node, either left or right child based on the key comparison.  Hint, this can be done either iteratively or recursively.  Note, if you do recursion on a helper function, the (recursive) helper function must also be void. 

 

Don’t add any global variables in your solution. 

 

Sample Inputs/Outputs:  (download – don’t copy/paste - the input file data2.txt)
red 305 % gcc a2BST.c red 306 % a.out 

size: 1 

Inorder traversal: 100 - 

 insert 33 size: 1 

Inorder traversal: 33 - min key: 33 search  14 ....  not found search  33 ....  found search   8 ....  not found search  83 ....  not found search 100 ....  not found search  52 ....  not found 

 insert 71 insert 30 insert 26 insert 83 size: 5 

Inorder traversal: 26 - 30 - 33 - 71 - 83 - min key: 26 search  14 ....  not found search  33 ....  found search   8 ....  not found search  83 ....  found search 100 ....  not found search  52 ....  not found 

 insert 14 insert 0 insert 1 insert 2 insert 60 insert 8 size: 11 

Inorder traversal: 0 - 1 - 2 - 8 - 14 - 26 - 30 - 33 - 60 - 71 - 83 - min key: 0 search  14 ....  found search  33 ....  found search   8 ....  found search  83 ....  found search 100 ....  not found search  52 ....  not found 

 red 307 %