ASSIGNMENT 4 SOLUTION

Assignment overview




We would like students to experience arrays, strings, structures, pointers and recursion, to understand and use user defined types in C, to use dynamic allocation of memory, and to use multiple source files.




This assignment consists of two parts.




In part one, you are required to write a C programs to implement binary search trees.




In part two, you are to wrote a C program to calculate the mathematical constant π.




Part one: 80%




1.1 Preliminaries




binary tree is a tree data structure in which each node has at most two children, called the left child and the right child. Binary trees are a very popular data-structure in computer science. We shall see in this exercise how we can encode it using C arrays. The formal recursive definition of a binary tree is as follows. A binary tree is



废话
• either empty,





or a node with two children, each of which is a binary tree. The following terminology is convenient:



A node with no children is called a leaf and a node with children is called an internal node.
废话 定义 • If a node B is a child of a node A then we say that A is the parent of B.




In a non-empty binary tree, there is one and only one node with no parent; this node
is called the root node of the tree.

重点来了 用array来装载 tree

A binary tree T can be encoded in an array A with n+1 elements. Indeed, one can always label the nodes with the integers 1, 2, . . . , n such that:




• the root has label 1,
root i


1
left child 2i
right child 2i+1



if an internal node has label i then its left child (if any) has label 2i and its right child (if any) has label 2i + 1.



Using this observation, we can store the nodes of T in A as follows:




the root of the tree is in A[1], and its left and right children are stored in A[2] and A[3] respectively,



given the index i of an internal node, different from the root, the indices of its parent Parent(i), left child Left(i), and right child Right(i) can be computed simply by:



– Parent(i) = ⌊i/2⌋




– Left(i) = 2i




– Right(i) = 2i + 1




binary search tree (BST), is a binary tree with the following properties.



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



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




Both the left and right subtrees must also be binary search trees.



There must be no nodes with duplicate keys.



Generally, the information represented by each node is of two fields such that one field is key and the other field is data. For the purpose of this exercise, key is a string and an integer pair, and data is an integer. To compare keys, we can use “int strcmp(char∗, char∗)” in string.h to compare the strings in keys.




Since we will use an array to encode a binary tree T, we also need to know if an array location is being used as a node of tree T. For this purpose, we will need another array.




1.2 Questions




The purpose of this exercise is to realize a simple C implementation of binary search trees encoded using arrays. We will use a structure with three members to implement binary search trees where one member will be an array of tree nodes, another member will be an array of unsigned char to indicate if a location is being used or not, and a third member is used to keep the size of the array. To guide you toward this goal, we provide a template program hereafter. We ask you to use this template and fill in the missing code.




分开来的一个文件
会pass in 三个量 分别是
array tree， array position 和 size
// ====== this is in data.h









声明










简单




typedef struct {char *name; int id;} Key; 为什么有id？ typedef struct {Key *key; int data;} Node;




Key *key_construct(char *in_name, int in_id); int key_comp(Key key1, Key key2);比较？ void print_key(Key *key);

void print_node(Node node);

具体的name 和id




不知道具体的内容是

是啥 2







根据上面的描述 key 里面存放了 string 和 int 创建的是两个量//每个key 有name 和 id




通俗来讲也就是在创建node之前首先得construct key




之后再把创建的 key 和 data 放在一起



正式代码

// ====== this is in data.c




需要这三个library

#include <stdio.h




#include <string.h




#include "data.h"




Input: ’in_name’: a string ends with ’\0’



’in_id’: an integer



Output: a pointer of type pointer to Key,



pointing to an allocated memory containing a Key



Effect: dynamically allocate memory to hold a Key



set Key’s id to be in_id



dynamically allocate memory for the Key’s name



so that name will contain what is in ’in_name’.



Note: may use strdup()



Key *key_construct(char *in_name, int in_id) {




这个就是创建key对象的 输入一个 name 和id 把他们弄成pair

}




首先得想key 里面存了什么 只有name和id 所以是比较啥？

// Input:
’key1’ and ’key2’ are two Keys
如果不等于直接比较大小详情
// Output: if return value < 0, then key1 < key2,
见 strcmp定义 比较字典上的顺
//
if return value = 0, then key1 = key2,
序？
//
if return value 0, then key1 key2,


// Note:
use strcmp() to compare key1.name and key2.name
//
if key1.name = key2.name, then compare key1.id with key2.id



int key_comp(Key key1, Key key2) {




输入两个key 根据上面的指示来就好了

}




Input: ’key’: a pointer to Key



Effect: ( key-name key-id ) is printed void print_key(Key *key) {



print key

}




Input: ’node’: a node



Effect: node.key is printed and then the node.data is printed void print_node(Node node) {



print data

}






















3
创建一颗树

上面是具体要求




====== this is in bst.h #include "data.h"



typedef struct {Node *tree_nodes; unsigned char *is_free; int size;} BStree_struct;




typedef BStree_struct* BStree;




BStree bstree_ini(int size);




void bstree_insert(BStree bst, Key *key, int data); void bstree_traversal(BStree bst); void bstree_free(BStree bst);
















// ====== this is in bst.c




#include <stdio.h




#include <stdlib.h




#include "bst.h"




Input: ’size’: size of an array



Output: a pointer of type BStree,



i.e. a pointer to an allocated memory of BStree_struct type



Effect: dynamically allocate memory of type BStree_struct



allocate memory for a Node array of size+1 for member tree_nodes



allocate memory for an unsigned char array of size+1 for member is_free



set all entries of is_free to 1



// set member size to ’size’; BStree bstree_ini(int size) {




}




Input: ’bst’: a binary search tree



’key’: a pointer to Key



’data’: an integer



Effect: ’data’ with ’key’ is inserted into ’bst’



if ’key’ is already in ’bst’, do nothing void bstree_insert(BStree bst, Key *key, int data) {



}

插入一个node




如果存在不插入



















4



Input: ’bst’: a binary search tree



Effect: print all the nodes in bst using in order traversal void bstree_traversal(BStree bst) {



print 出所有的node

}




Input: ’bst’: a binary search tree



Effect: all memory used by bst are freed void bstree_free(BStree bst) {



}




Binary search tree insertion and traversal should be implemented using recursion. You may need to use “helper” functions. Binary search tree insertion should check the array bound.




A sample main program is given below.




// ====== this is a sample main program


#include <stdio.h


#include "bst.h"


int main(void) {


BStree bst;


bst = bstree_ini(1000);


bstree_insert(bst, key_construct("Once", 1),
11);
bstree_insert(bst, key_construct("Upon", 22),
2);
bstree_insert(bst, key_construct("a", 3),
33);
bstree_insert(bst, key_construct("Time", 4),
44);
bstree_insert(bst, key_construct("is", 5),
55);
bstree_insert(bst, key_construct("filmed", 6),
66);
bstree_insert(bst, key_construct("in", 7),
77);



bstree_insert(bst, key_construct("Vancouver", 8), 88);




bstree_insert(bst, key_construct("!", 99),
9);
bstree_insert(bst, key_construct("Once", 5),
50);
bstree_insert(bst, key_construct("Once", 1),
10);



bstree_traversal(bst);




bstree_free(bst);




}




The output of the above sample program.




5



( !
99
)
9
( Once
1
)
11
( Once
5
)
50
( Time
4
)
44
( Upon
22
)
2
( Vancouver
8
)
88
( a
3
)
33
( filmed
6
)
66
( in
7
)
77
( is
5
)
55



Your program should read from stdin (or redirect from a file) triples of string, integer, and integer (a string followed by an int, and followed by another int, i.e. name id data), one triple per line and insert these triples, in the order they are read, into an initially empty binary search tree. You should create several test cases, i.e. binary search tree of different sizes, keys (with data) inserted with different orders, and insertion that will cause array out of bound situation.




Part two: 20%




The goal of this exercise is to implement a C program to calculate the mathematical constant




. You should consider using type double and long long for the calculation. You should consider using compute.gaul.csd.uwo.ca since this exercise is time consuming.



(1) The value of the mathematical constant π can be expressed as an infinite series:






∞






4








4


4


4
4
4








π =(−1)I+1




























=








−








+








−


+


. . .




2i − 1
1


3


5


7


9






I=1


























































(2) Write a C program that approximates π by computing the value of


N
4


4




4






4




4






4






























π ≈
(−1)(I+1)




=






−






+






−






. . . (−1)N+1




2i − 1
1
3




5


7


2n − 1


I=1


























































where n is the smallest integer such that




4










< ǫ for an user entered small (double
2(N+1)−1




precision) number ǫ.




Testing your program by inputing ǫ of the following values. 0.0001



0.0000001




0.0000000001










Testing your program




You should test your program by running it on Gaul. Capture the screen of your testing by using script command. There should be two script files, one for each part.







6