DOCUMENTATION

Course project Title:
    
Implementation of Family tree Using Generalized Link List


Description: 

  In this project we have created FAMILY TREE by using Generalized link list.Also we have implemented different functions to operate the Family Tree such as to add new family members,finding the relationship between two members,searching operation,updating information of family tree,deletion operation,display operation .etc

Link For Project Report: Project Report


Topic 1: Introduction and Adding Family tree

Presenters info:
Name: Akshay Ashok Bharati
Div:TY-L
Roll no:07
video link: https://drive.google.com/open?id=1ahbFCzP_w9dA9gu51i-2AhNsq43phD9M


Topic 2: Finding Relationship between two members

Presenters info:
Name: Dayanand Haral
Div:TY-L
Roll no:24
video link: https://drive.google.com/file/d/1SBeNwVyrm1implE7Il9Bz1eGoMq6l8sP/view?usp=drivesdk



Topic 3: Searching member in Family tree
Presenters info:
Name: Aniket Kapale
Div:TY-L
Roll no:33
video link: https://drive.google.com/a/vit.edu/file/d/1K_q_LMvGHqdab7p9k2cQdPDqTyMS3Z3w/view?usp=drivesdk

Topic 4: Output Explanation
Presenters info:
Name: Atharv Joshi
Div:TY-L
Roll no:31
video link: https://drive.google.com/file/d/1Wv23HAQl6vKyLimVMX0rn6BiJrzbOOmr/view?usp=sharing

Thank you!!!

OPERATIONS ON FAMILY TREE

Now,when we complete the adding of members in Family tree,We require some operations such as:

1)Checking whether the person present in Family tree or not.

2)Finding the relationships between two members.

3)Display of Family tree

4)Destroying a Family tree 

5)Connecting Two Family Trees

6)Updating a Family Tree

etc.

We will implement a user driven Switch case,and according to the input given by user we will call that method.

 cout<<"\n\n\n\tFamily tree no = "<<n<<"\n\n\t
1. Add new person\n\t
2. Find relationship b/w two persons\n\t
3. Search\n\t
4. Destroy\n\t
5. Display\n\t
6. Change family tree\n\t
7. Connect two family trees\n\t
8. Exit\n\n\tEnter your choice = ";
        cin>>opt;
        cout<<endl;

        switch(opt)
        {

        default:
                cout<<"Invalid input";
                break;

        case 1:
                T[n].addNew();
                break;

        case 2:
                T[n].find();
                break;

        case 3:
                cout<<"Enter name of person to search: ";
                cin>>name;
                T[n].show(T[n].search(name));
                break;

        case 4:
                T[n].destroy(T[n].start);
                cout<<"Tree "<<n<<" has been destroyed sucessfully";
                break;

        case 5:
                T[n].display(T[n].start);
                break;

        case 6:
                cout<<"Enter family tree number: ";
                cin>>n;
                break;

        case 7:
               cout<<"Merge __ to __ \n";
               cin>>n2>>n1;
               connect(&T[n1],&T[n2]);
               break;

        case 8:
            return 0;

        }
        cout<<"\n\nPress any key to continue.....";
        cin>>c;
    }


This is just a overview of How the user will interact to call the methods.
In next Post We will provide you the total code for implementing each operation.

TAKING THE FAMILY TREE DATA FROM USER

Now, I think you are quiet comfortable with basics of link list.lets  start the actual coding part of our project.
As we are designing a Family tree,We need  Following two things:

1)Data of family tree
2)Functions that will process different operations on Family tree

now lets understand about how we are going to take Family tree from user.

1)We can take information for each person in family such as name,age,Gender,etc.
2)We need a two pointers for every person that will point sibling and child.

The way in which we are going to store the data is shown below:

For the above implementation we need a structure which will consist of name,age ,gender and we will require two pointers to point sibling and child.

struct node
{
    char name[50];
    short int age,x;    // x - height of node
    bool g;             // g- gender
    node* fc;           // Pointer to first child
    node* ns;           // Pointer to next sibling

    node();
    void getData();
};

void node::getData()
{
    char ch;
    cout<<"\nName of the Person: ";
    cin>>name;
    cout<<"Age of "<<name<<": ";
    cin>>age;
    cout<<name<<" is (m/f): ";
    cin>>ch;
    if(ch=='m')
        g=1;
}

Now,after taking the personal information,we need to make connection of this node in family according to relationship..
So we will ask the user to enter the relation of this person with specific person in family tree and then we will connect these two node depending on the relationship.i.e sibling or child.

Given below is  addNew() method which will add a new person according to relation with previous members in Family tree.

void familyTree::addNew()
{
    node* temp = new node;
    temp->getData();

    if(start == NULL)
    {
        start = temp;
        temp->x=0;
    }

    else
    {
        cout<<"\nEnter any relation's name: ";
        char name[50];
        cin>>name;
        cout<<"\n1. Child\n2. Sibiling\n\n"<< temp->name <<" is ____ to "<<name<<" : ";
        int opt;
        cin>>opt;
        switch(opt)
        {
            case 1:
                    addChild(search(name),temp);
                    break;
            case 2:
                    addSib(search(name),temp);
                    break;

        }
    }
    cout<<"\nPerson sucessfully added.\n";
}

Dynamic Memory Allocation in C++

C++ Dynamic Memory Allocation is different from that seen in the C. While C uses functions like malloc(), calloc(), realloc() and free() to handle operations based on DMA, C++ also uses all the 4 functions in addition to 2 different operators called new and delete to allocate memory dynamically.

These statements are indicative of the fact that DMA is implemented by the programmer itself. C++ lacks the feature of a garbage collector which automatically helps to free up unnecessary memory space occupied by stagnant garbage values.

It is important to note that the memory is dynamically allocated on the Heap. The non-static memory and local variables get memory allocated on Stack.

ABOUT GENERALIZED LINK LIST

As we are going to implement Family tree using Generalized link list,Let us understand what a generalized link list is and how we are going to implement it.

•  Generalized Linked List L, is defined as a finite sequence of elements in which  each element can be atom or group of atom.
• A linked list is a linear data structure, in which the elements are not stored at contiguous memory locations .

The elements in a linked list are linked using pointers as shown below

A generalized link list consists of some extra fields such a as Flag,down pointer.
1)Flag is used to indicate the type of information stored by the node.
2)Down pointer is used if any element in the list is sub list.
A general node structure of generalized link list is as  shown below:

we can assign values in flag as per our convenience.
e.g Flag=0 implies node consist of data
      Flag=1 implies next pointer
     Flag=2 implies down pointer

Given below is a structure of general lists consisting of sub list.

1)In above example,in list A first node is a atom variable a.hence flag is equal to 1.
The second atom of list A is sub list-((b,c). the second node will be down pointer pointing to sub list,
2)In Sub list both atom are variables(data).Hence Flag is equal to 0.

So,now from the above discussion I think that all of you are cleared with what a generalized link list looks like and how we store the data in it.
In further posts i  will give the hole idea for family tree using Generalized link list...
If anyone having doubts in the concepts dicusussed in post can comment below and if you like our posts,dont forget to share it...
        Thank you...

Structures in c++

As we are going to implement link list in our project, let us understand some basic concept
of structures in c++.
We often come around situations where we need to store a group of data whether of similar data types or non-similar data types.  Arrays in C++ which are used to store set of data of similar data types at contiguous memory locations.

                       Unlike Arrays, Structures in C++ are user defined data types which are used to store group of items of non-similar data types. A structure creates a data type that can be used to group items of possibly different types into a single type.                                            


 How to create a structure?

The ‘struct’ keyword is used to create a structure. The general syntax to create a structure is as shown below:

struct structureName

{ member1;

  member2;

  member3;

   .

   .

   .

   .

   .

   memberN;

};

Structures in C++ can contain two types of members:

• Data Member: These members are normal C++ variables. We can create a structure with variables of different data types in C++.
• Member Functions: These members are normal C++ functions. Along with variables, we can also include functions inside a structure declaration.

How to declare structure variables?
A structure variable can either be declared with structure declaration or as a separate declaration like basic types.

struct Point 

{ 

int x, y; 

} p1; // The variable p1 is declared with 'Point' 

// A variable declaration like basic data types 

struct Point 

{ 

int x, y; 

}; 

int main() 

{ 

struct Point p1; 

}

How to initialize structure members?

Structure members can be initialized using curly braces ‘{}’.

 For example,

struct Point 

{ 

int x, y; 

}; 

int main() 

{ 

struct Point p1 = {0, 1}; 

};

How to access structure elements?

Structure members are accessed using dot (.) operator.

#include <iostream> 

using namespace std; 

struct Point { 

int x, y; 

}; 

int main() 

{ 

struct Point p1 = { 0, 1 }; 

p1.x = 20; 

cout << "x = " << p1.x << ", y = " << p1.y; 

return 0; 

}

What is a structure pointer?

Like primitive types, we can have pointer to a structure. If we have a pointer to structure, members are accessed using arrow ( -> ) operator instead of the dot (.) operator.

#include <iostream> 

using namespace std; 

struct Point { 

int x, y; 

}; 

int main() 

{ 

struct Point p1 = { 1, 2 }; 

cout << p2->x << " " << p2->y; 

return 0; 

}

INTRODUCTION

Contributors:

1)Akshay Bharati

2) Dayanand Haral

3)aniket kapale

4)Atharv joshi

 In this project, you will learn the concepts of Datastructure and OOPs in c++ to write a code for making a family tree using generalized link list .The goal of this project is to get you comfortable with datastructure in C++. You've been using oops, but in this project you'll write more of them at one time than you have before.

          Before we start, we want to spend just a quick second talking about how I think about oops concepts, because I think it's a useful picture to have in your head. It helped me a lot.