Description
In this assignment you are going to implement two self-referential data structures. One is doubly linked
list. Another is binary search tree.
Problem 1 Doubly linked list in C (60 pts)
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.
2
▪ 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
3
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 %
Submit your program by issuing submit 2031ON lab2 lab2D.c
Submit your program by issuing submit 2031A a2 a2List.c
or websubmit (see end of this pdf for more info)
4
Question 2 Binary search tree in C (40 pts)
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.
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
size 1
min 10
size 3
min 5
size 6
min 4
size 9
min 4
5
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
6
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 %
Make sure your program compiles in the lab environment. The program that does not
compile in the lab environment will get 0.
In summary, for this assignment you should submit two files: a2List.c a2BST.c
At any time and from any directory, you can issue submit -l 2031A a2 to view the list of files that
you have submitted. Or check from websubmit page.
Lower case L
Submit your program by issuing submit 2031A a2 a2BST.c
or websubmit (see end of this pdf for more info)
7
Common Notes
All submitted files should contain the following header:
/***************************************
* EECS2031A – Assignment 2 *
* Author: Last name, first name *
* Email: Your email address *
* eecs_username: Your eecs login username *
* York num: Your York student number
****************************************/
Web-submit
To prepare for the coming labtest, for which you will be encouraged to work on your local computer and
submit using websumit, for this assignment you can submit using websubmit. So, in addition to
submitting from the lab, you can also submit from local machine directly. (You should still make sure
that the files compile in the lab environment)
You can submit using websubmit at https://webapp.eecs.yorku.ca/submit/
o login using EECS , not passport York. If you keep on getting prompted to login using
passport York, then clear the cookie and cache of your browser and then try again.
Eventually you should see the page below.
o Once login, select Course: 2031A and then select Assignment: a2
o Then upload files from your local computer.
See this page for more information about web-submit
https://wiki.eecs.yorku.ca/dept/tdb/services:submit:websubmit
Use EECS account
