** WRITE IN C LANGUAGE !!! ** Problem: In this program you are to implement a da
ID: 3568607 • Letter: #
Question
** WRITE IN C LANGUAGE !!! **
Problem: In this program you are to implement a database of student records, using the binary search tree abstract data type, implemented as a linked list.
The student record will have the following format:
typedef struct studentRec{
int id;
char[] name; //the name has a maximum length of 25 letters
char[] major; //the major array has a max length of 15
int year;
}
You are required to maintain the database by providing the following functionality:
1. Search to see if a record exists in the data base
2. Add a record to the database;
3. Delete a record from the database
4. Update a record in the database
5. Print out all of the records in the database
6. Print out all of the records in the database from a given point
Objectives:
The objective of this assignment is for students to demonstrate a working
knowledge of :
Binary Search Trees
Linked list implementation of BST
BST operations
Requirements:
Your program should demonstrate the 6 functionalities described above. These
should be implemented as the following functions:
1. initBST: In this function your program should read an input file to obtain
the student records then your BST should be populated by adding each of
these records to the BST. Your function should return a pointer to the root of
the BST. Do not hardcode the name of your input file in your program. It
should be a parameter passed to main.
2. Search: This function takes a pointer to the BST, and an integer parameter. It
searches the BST for the student with that Id. If the record is found it prints
out the record and the function returns 1 otherwise it returns 0;
3. addNode: This function takes a pointer to the BST, an integer, two char
arrays and a second integer. It creates a new node and then adds that node
in place to the BST and returns a pointer to the modified BST.
4. updateStudent: This function takes a pointer to the BST and two integers. It
finds the student whose id is the first integer and updates the year value to
the second integer parameter and returns a pointer to the updated BSGT.
5. deleteStudent: This function takes a pointer to the BST, and the integer id
of a student, finds that student record, deletes it (using the predecessor
method) and returns the updated BST.
6. print: This function takes a pointer to the BST and prints out all of the
student records stored in table form
Explanation / Answer
#include<stdio.h>
#include<stdlib.h>
/* Link list node */
struct LNode
{
int data;
struct LNode* next;
};
/* A Binary Tree node */
struct TNode
{
int data;
struct TNode* left;
struct TNode* right;
};
struct TNode* newNode(int data);
int countLNodes(struct LNode *head);
struct TNode* sortedListToBSTRecur(struct LNode **head_ref, int n);
/* This function counts the number of nodes in Linked List and then calls
sortedListToBSTRecur() to construct BST */
struct TNode* sortedListToBST(struct LNode *head)
{
/*Count the number of nodes in Linked List */
int n = countLNodes(head);
/* Construct BST */
return sortedListToBSTRecur(&head, n);
}
/* The main function that constructs balanced BST and returns root of it.
head_ref --> Pointer to pointer to head node of linked list
n --> No. of nodes in Linked List */
struct TNode* sortedListToBSTRecur(struct LNode **head_ref, int n)
{
/* Base Case */
if (n <= 0)
return NULL;
/* Recursively construct the left subtree */
struct TNode *left = sortedListToBSTRecur(head_ref, n/2);
/* Allocate memory for root, and link the above constructed left
subtree with root */
struct TNode *root = newNode((*head_ref)->data);
root->left = left;
/* Change head pointer of Linked List for parent recursive calls */
*head_ref = (*head_ref)->next;
/* Recursively construct the right subtree and link it with root
The number of nodes in right subtree is total nodes - nodes in
left subtree - 1 (for root) which is n-n/2-1*/
root->right = sortedListToBSTRecur(head_ref, n-n/2-1);
return root;
}
/* UTILITY FUNCTIONS */
/* A utility function that returns count of nodes in a given Linked List */
int countLNodes(struct LNode *head)
{
int count = 0;
struct LNode *temp = head;
while(temp)
{
temp = temp->next;
count++;
}
return count;
}
/* Function to insert a node at the beginging of the linked list */
void push(struct LNode** head_ref, int new_data)
{
/* allocate node */
struct LNode* new_node =
(struct LNode*) malloc(sizeof(struct LNode));
/* put in the data */
new_node->data = new_data;
/* link the old list off the new node */
new_node->next = (*head_ref);
/* move the head to point to the new node */
(*head_ref) = new_node;
}
/* Function to print nodes in a given linked list */
void printList(struct LNode *node)
{
while(node!=NULL)
{
printf("%d ", node->data);
node = node->next;
}
}
/* Helper function that allocates a new node with the
given data and NULL left and right pointers. */
struct TNode* newNode(int data)
{
struct TNode* node = (struct TNode*)
malloc(sizeof(struct TNode));
node->data = data;
node->left = NULL;
node->right = NULL;
return node;
}
/* A utility function to print preorder traversal of BST */
void preOrder(struct TNode* node)
{
if (node == NULL)
return;
printf("%d ", node->data);
preOrder(node->left);
preOrder(node->right);
}
/* Drier program to test above functions*/
int main()
{
/* Start with the empty list */
struct LNode* head = NULL;
/* Let us create a sorted linked list to test the functions
Created linked list will be 1->2->3->4->5->6->7 */
push(&head, 7);
push(&head, 6);
push(&head, 5);
push(&head, 4);
push(&head, 3);
push(&head, 2);
push(&head, 1);
printf(" Given Linked List ");
printList(head);
/* Convert List to BST */
struct TNode *root = sortedListToBST(head);
printf(" PreOrder Traversal of constructed BST ");
preOrder(root);
return 0;
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.