The main aim of this
project is to store the information of movie in Binary Search Tree. In this we
should arrange movie database in Binary search tree order, in binary search
tree we can add movie record to movie database or can delete record from movie
database , we can search movie record
from movie database by actor name, rating , time period , year. The new
cast member name also we can add it or we can delete if it present in the
binary search tree. In this project we will use the application linked list ADT (doubly linked list)and
sorted list ADT(circular linked list),movie database application (linked list,
iterator, queue ADT, sorted circular linked list)
By the applications of all these finally
the movies should
be in the Binary
search tree sorted order.
The program can be run properly
without any errors. The final output of this project is the movies record in
the movie database should be print in the Binary Search Tree sorted order. BST Data
–the object to be stored in
the tree. It is assumed by the templates
that a BST Data type will implement a function called get key()
that returns an object of type Data Key (explained below). In addition,
the BST Data data-type must overload the relational operators =
=, !=, <,
<=, >, >=. In this project you will use classes Name and
Movie in this role of BST Data. These classes are explained below. Data
Key –represents an identifier for the object stored in the tree. It
should be returned from the a call to method get_ key().The Binary Search Tree
class container has two private data fields: Root - a pointer
to the root of the
Binary Search Tree (Recall
that the root node
stores data!!!).Size – the number of elements in the tree. Each node N
in the tree has three fields: Data- the data in each node is stored in this
field. Left child – pointer to the node
that is the left child of the node N, and hence, the root of the left sub tree
of N. Right child – pointer to the node that is the right child of the node ,
and hence, the root of the right sub tree of N When new nodes are
inserted, they must be inserted so as to maintain the BST order. Likewise, when
nodes are deleted from the BST, they must be removed so as to maintain the BST
order.
1.INTRODUCTION
1.1 Introduction
In computer
science, a data structure is a
way of organizing data in a
computer so that it can be used efficiently. Different kinds of data
structures are suited to different kinds of
applications, and some are highly specialized to specific tasks.
Data structures provide a means to manage large amounts of
data efficiently, such as large databases and internet
indexing services. Usually, efficient data structures
are a key in designing efficient algorithms.
Some formal design methods and programming
languages emphasize data structures, rather than algorithms, as
the key organizing factor in software design.
Storing and retrieving can be carried out on data stored in both main
memory and
in secondary
memory. Data
structures are generally based on the ability of a computer to fetch and store
data at any place in its memory, specified by a pointer-a
bit string, representing a memory address that can be itself
stored in memory and manipulated by the program.
1.2 Project Description
Implement
and test an application that acts as main-memory database containing
information about movies. All the records with movie information will be stored
in a Binary Search Tree (BST). The insertion of each movie record will be based
on the movie title. For simplicity we will assume movie titles consisting of
either one word, or multiple words separated by a dash - .
For
example: Jurassic-Park, Titanic,
Border, Jurassic-Park-2
2.REQUIREMENTS
Hardware/Software
|
Hardware / Software
element
|
Specification
/version
|
Hardware
|
Processor
|
Intel core to duo
|
RAM
|
1 GB
|
|
Hard Disk
|
100 GB
|
|
Software
|
OS
|
Windows
2000/NT/Xp/Vista
|
TURBO C++S
|
Tab 2.1. Platform Requirements
2.2 Module Description
In this project we have four submodules
which are listed below.
Module-1 Linked List ADT:
1. Create the interface for the doubly
linked list.
2. Implement and test various Insertion
Operation on doubly linked list
3. Implement and test various Deletion
Operation on doubly linked list
4. Implement and test Searching Operation
on doubly linked list
5. Implement and test various Travsering
Operation on doubly linked list
6. Integrate all the above
functions/methods. You Must Implement The Methods To Appear In This File.
Module-2 Sorted List ADT:
1. Create the interface for the Sorted
Circular doubly linked list.
2. Implement and test various Insertion
Operation on Sorted Circular doubly linked list.
3. Implement and test various Deletion
Operation on Sorted Circular doubly linked list.
4. Implement and test Searching Operation
on Sorted Circular doubly linked list.
5. Implement and test various Travsering
Operation on Sorted Circular doubly linked list.
6. Integrate all the above
functions/methods. You Must Implement The Methods To Appear In This File.
Module-3 & 4 Movie Database
Application :
1. Create the interface for the linked
list.
2. Create the interface for the circular
doubly linked list
3. Create the interface for the iterator
4. Implement the List as a sorted circular
doubly linked list.
5. Create the interface of the queue ADT
6.Implement of the queue class container.
You will need this class to keep track of tree nodes during in-order and
pre-order tree traversals.
7. Create the interface for the Binary
Search Tree
8. Implement of the Binary Search Tree
9. Create the interface for a room
information record
10. Implement of a room record
11. Create the interface for an actor name
12. Implement of the implementation of an
actor name
13. Create the interface for a list of
actor names.
14. Implement of the list of actor names
15. Create the interface of the data
management program for the movie database.
16. Implement of the data management for
the movie database
17. Create the interface for a movie
information record.
18. Implement of a movie record.
19. Create the interface for the movie
database application.
20.Implementation of the movie database
application.
21.Integrate all the above
functions/methods. You Must Implement The Methods To Appear In This File.
3.ANALYSIS
Linked List ADT:
1.
Create the interface for the doubly linked list: To create the interface for doubly linked list
is to store the movie record with the address of next node and previous node in
the list. we can perform many applications in the doubly linked list.The operations are
insertion, deletion ,searching , traversing in the linked list.
2. Implement and test various Insertion
Operation on doubly linked list: The operation insertion can be implemented in
the doubly linked list. There are two types of insertions can be performed in
the doubly linked list. They are Beginning and Ending insertions of the linked list. The beginning
insertion is implemented to insert the value at the first of the linked list.The
ending operation is implemented to
insert the at the end of the linked list.
3. Implement and test various Deletion
Operation on doubly linkedlist :The operation deletion can be implemented in
the doubly linked list.There are two types of deletions can be performed in the
doubly linked list. They are Beginning and Ending deletions of the linked list.
The beginning deletion is implemented to delete the value in first position of the linked list . The ending deletion is implemented to delete the
value in last position of the linkedlist.
4. Implement and test Searching Operation
on doubly linked list:The operation
searching can be implemented in the doubly linked list.The value in the linked list can be search by the
searching operation. The position
address can be find .
5.
Implement and test various Travsering Operation on doubly linked list: The traversing
operation is used to travel the node
from head node to next node. It is implemented till the node reached to last
node of the doubly linkedlist.
SOURCE CODE:
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <stdbool.h>
struct node {
int data;
int key;
struct node *next;
struct node *prev;
};
//this link always point to first Link
struct node *head = NULL;
//this link always point to last Link
struct node *last = NULL;
struct node *current = NULL;
//is list empty
bool isEmpty() {
return head == NULL;
}
int length() {
int length = 0;
struct node *current;
for(current = head; current != NULL; current = current->next){
length++;
}
return length;
}
//display the list in from first to last
void displayForward() {
//start from the beginning
struct node *ptr = head;
//navigate till the end of the list
printf("\n[ ");
while(ptr != NULL) {
printf("(%d,%d) ",ptr->key,ptr->data);
ptr = ptr->next;
}
printf(" ]");
}
//display the list from last to first
void displayBackward() {
//start from the last
struct node *ptr = last;
//navigate till the start of the list
printf("\n[ ");
while(ptr != NULL) {
//print data
printf("(%d,%d) ",ptr->key,ptr->data);
//move to next item
ptr = ptr ->prev;
}
}
//insert link at the first location
void insertFirst(int key, int data) {
//create a link
struct node *link = (struct node*) malloc(sizeof(struct node));
link->key = key;
link->data = data;
if(isEmpty()) {
//make it the last link
last = link;
}
else {
//update first prev link
head->prev = link;
}
//point it to old first link
link->next = head;
//point first to new first link
head = link;
}
//insert link at the last location
void insertLast(int key, int data) {
//create a link
struct node *link = (struct node*) malloc(sizeof(struct node));
link->key = key;
link->data = data;
if(isEmpty()) {
//make it the last link
last = link;
}
else {
//make link a new last link
last->next = link;
//mark old last node as prev of new link
link->prev = last;
}
//point last to new last node
last = link;
}
//delete first item
struct node* deleteFirst() {
//save reference to first link
struct node *tempLink = head;
//if only one link
if(head->next == NULL){
last = NULL;
}
else {
head->next->prev = NULL;
}
head = head->next;
//return the deleted link
return tempLink;
}
//delete link at the last location
struct node* deleteLast() {
//save reference to last link
struct node *tempLink = last;
//if only one link
if(head->next == NULL) {
head = NULL;
}
else {
last->prev->next = NULL;
}
last = last->prev;
//return the deleted link
return tempLink;
}
//delete a link with given key
struct node* delete(int key) {
//start from the first link
struct node* current = head;
struct node* previous = NULL;
//if list is empty
if(head == NULL) {
return NULL;
}
//navigate through list
while(current->key != key) {
//if it is last node
if(current->next == NULL) {
return NULL;
} else {
//store reference to current link
previous = current;
//move to next link
current = current->next;
}
}
//found a match, update the link
if(current == head) {
//change first to point to next link
head = head->next;
}
else {
//bypass the current link
current->prev->next = current->next;
}
if(current == last) {
//change last to point to prev link
last = current->prev;
}
else {
current->next->prev = current->prev;
}
return current;
}
bool insertAfter(int key, int newKey, int
data) {
//start from the first link
struct node *current = head;
//if list is empty
if(head == NULL) {
return false;
}
//navigate through list
while(current->key != key) {
//if it is last node
if(current->next == NULL) {
return false;
} else {
//move to next link
current = current->next;
}
}
//create a link
struct node *newLink = (struct node*) malloc(sizeof(struct node));
newLink->key = newKey;
newLink->data = data;
if(current == last) {
newLink->next = NULL;
last = newLink;
}
else {
newLink->next = current->next;
current->next->prev = newLink;
}
newLink->prev = current;
current->next = newLink;
return true;
}
void main() {
insertFirst(1,10);
insertFirst(2,20);
insertFirst(3,30);
insertFirst(4,1);
insertFirst(5,40);
insertFirst(6,56);
printf("\nList (First to Last): ");
displayForward();
printf("\n");
printf("\nList (Last to first): ");
displayBackward();
printf("\nList , after deleting first record: ");
deleteFirst();
displayForward();
printf("\nList , after deleting last record: ");
deleteLast();
displayForward();
printf("\nList , insert after key(4) : ");
insertAfter(4,7, 13);
displayForward();
printf("\nList , after
delete key(4) : ");
delete(4);
displayForward();
}
Sorted List ADT:
1. Create the interface for the Sorted Circular doubly linked list: To create the interface for circular linked list
is to store the movie record with the address of next node and previous node in
the list. we can perform many applications in the circular linked list.The operations are
insertion, deletion ,searching , traversing in the linked list.In
circular linked list the last node
consists of first node address. The circular linked list sorted.
2. Implement and test various Insertion
Operation on Sorted Circular doubly linked list: The operation insertion can be implemented in
the sorted circular linked list. There are two types of insertions can be
performed in the sorted circular linked list. They are Beginning and
Ending insertions of the linked list.
The beginning insertion is implemented to insert the value at the first of the
linked list.The ending insertion operation is implemented to insert the at the end of the linked list. The
specific position insertion operation is implemented to insert the at the end of the linked list.
3. Implement and test various Deletion
Operation on sorted circular doubly linked list :The operation deletion can be
implemented in the sorted circular doubly
linked list. There are three types of deletions can be performed in the
doubly linked list. They are Beginning ,specific position and Ending deletions of the linked list. The beginning
deletion is implemented to delete the value
in first position of the linked
list . The ending deletion is
implemented to delete the value in last position of the linked list. The specific position deletion is implemented to delete the value
in last position of the linked list.
4. Implement and test Searching Operation
on sorted circular doubly linked list: The operation searching can be implemented in the sorted
circular linked list.The value in the
linked list can be search by the searching operation. The position
address can be find in the sorted
circular doubly linked list.
5. Implement and test various Travsering
Operation on sorted circular doubly linked list: The travsering operation is
used to travel the node from head node
to next node. It is implemented till the node reached to last node of the
sorted circular doubly linked list.
CODE: #include<stdio.h>
#include<stdlib.h>
struct linked_list
{
int number;
struct linked_list *next;
};
typedef struct linked_list node;
node *head=NULL, *last=NULL;
void create_linked_list();
void print_linked_list();
void insert_at_last(int value);
void insert_at_first(int value);
void insert_after(int key, int value);
void delete_item(int value);
void search_item(int value);
int main()
{
int key, value;
//Create a linked list
printf("Create Linked List\n");
create_linked_list();
print_linked_list();
//Insert value at last position to existing Linked List
printf("\nInsert new item at last\n");
scanf("%d", &value);
insert_at_last(value);
print_linked_list();
//Insert value at first position to existing Linked List
printf("\nInsert new item at first\n");
scanf("%d", &value);
insert_at_first(value);
print_linked_list();
//Insert value after a defined value to existing Linked List
printf("\nEnter a KEY (existing item of List), after that you want
to insert a value\n");
scanf("%d", &key);
printf("\nInsert new item after %d KEY\n", key);
scanf("%d", &value);
insert_after(key, value);
print_linked_list();
//Search an item from Linked List
printf("\nEnter an item to search it from List\n");
scanf("%d", &value);
search_item(value);
//Delete value from List
printf("\nEnter a value, which you want to delete from
list\n");
scanf("%d", &value);
delete_item(value);
print_linked_list();
return 0;
}
/*
User Defined Functions
*/
void create_linked_list()
{
int val;
while(1)
{
printf("Input a number. (Enter -1 to exit)\n");
scanf("%d", &val);
if(val==-1)
break;
insert_at_last(val);
}
}
void insert_at_last(int value)
{
node *temp_node;
temp_node = (node *) malloc(sizeof(node));
temp_node->number=value;
temp_node->next=NULL;
//For the 1st element
if(head==NULL)
{
head=temp_node;
last=temp_node;
}
else
{
last->next=temp_node;
last=temp_node;
}
}
void insert_at_first(int value)
{
node *temp_node = (node *) malloc(sizeof(node));
temp_node->number=value;
temp_node->next = head;
head = temp_node;
}
void insert_after(int key, int value)
{
node *myNode = head;
int flag = 0;
while(myNode!=NULL)
{
if(myNode->number==key)
{
node *newNode = (node *) malloc(sizeof(node));
newNode->number = value;
newNode->next = myNode->next;
myNode->next = newNode;
printf("%d is inserted after %d\n", value, key);
flag = 1;
break;
}
else
myNode = myNode->next;
}
if(flag==0)
printf("Key not found!\n");
}
void delete_item(int value)
{
node *myNode = head, *previous=NULL;
int flag = 0;
while(myNode!=NULL)
{
if(myNode->number==value)
{
if(previous==NULL)
head = myNode->next;
else
previous->next =
myNode->next;
printf("%d is deleted from list\n", value);
flag = 1;
free(myNode); //need to free up the memory to prevent memory leak
break;
}
previous = myNode;
myNode = myNode->next;
}
if(flag==0)
printf("Key not found!\n");
}
void search_item(int value)
{
node *searchNode = head;
int flag = 0;
while(searchNode!=NULL)
{
if(searchNode->number==value)
{
printf("%d is present in this list. Memory address is %d\n",
value, searchNode);
flag = 1;
break;
}
else
searchNode = searchNode->next;
}
if(flag==0)
printf("Item not found\n");
}
void print_linked_list()
{
printf("\nYour full linked list is\n");
node *myList;
myList = head;
while(myList!=NULL)
{
printf("%d ", myList->number);
myList = myList->next;
}
puts("");
}
CONCLUSION:
The program has been
successfully executed and useful for further applications and sequence of
operations.
It can be successfully
modified for further modifications and features.
Comments
Post a Comment