# Dynamic allocation of adjacency matrix and traversing a list

Tags:
1. Aug 20, 2015

### gruba

1. The problem statement, all variables and given/known data
I have a binary tree. I need to print a path of a doubly circular linked list (0 and 1) after every user input.
I have a code in which user inputs data about one person. For example, when user inputs 2 elements, the path should be 0->1. In my code, it won't print any path.
Also, how to print adjacency matrix for a graph for the given binary tree. I know to do it
for five nodes (full tree), but what if the user enters three nodes (dynamic allocation for matrix)? Then matrix is 3 x 3.

I would highly appreciate is someone could help, I am stuck on it.
2. Relevant equations
-Binary trees
-Graphs
3. The attempt at a solution
1. Definition of structures:
Code (Text):

#include<stdio.h>
#include<stdlib.h>
#include<string.h>

typedef struct
{
char name[30],surname[30],id[101];
}PERSON;

typedef struct tree_node
{
PERSON person;
struct tree_node *left,*right;
}TREE_NODE;

typedef struct list_node
{
int info;
struct list_node *next,*previous;
}LIST_NODE;

typedef struct list
{
int n;
}LIST;

2. Functions:
Code (Text):

int returnFirstElementOfList(LIST *list)
{
return -1;
else
{
}
list->n--;
int info=list_element->info;
free(list_element);
return info;
}

{
LIST_NODE *list_element=(LIST_NODE *)malloc(sizeof(LIST_NODE));
list_element->info=element;
list_element->previous=list_element->next=NULL;
else
{
list_element->previous=list->tail;
list->tail->next=list_element;
list->tail=list_element;
}
list->n++;
}

void pathToNode(LIST *list,TREE_NODE *tree_node,TREE_NODE *root,int *found)
{
if(root==NULL)
return;
if(root==tree_node)
*found=1;
pathToNode(list,tree_node,root->left,found);
if(*found==0)
{
returnFirstElementOfList(list);
pathToNode(list,tree_node,root->right,found);
}
if(*found==1)
returnFirstElementOfList(list);
}

TREE_NODE *formTreeNode(PERSON *person)
{
TREE_NODE *tree_node=(TREE_NODE *)malloc(sizeof(TREE_NODE));
tree_node->person=*person;
tree_node->left=NULL;
tree_node->right=NULL;
return tree_node;
}

{
if(root==NULL)
return person;
if(strcmp(root->person.id,person->person.id)>=0)
else
return root;
}

{
if(root==NULL)
return;
if(list->n==1)
{
int path=returnFirstElementOfList(list);
if(path==0)
root->left=tree_node;
else
root->right=tree_node;
}
int path=returnFirstElementOfList(list);
if(path==0)
{
if(root->left==NULL)
root->left=formTreeNode(NULL);
}
else
{
if(root->right==NULL)
root->right=formTreeNode(NULL);
}
}

void initList(LIST *list)
{
list->tail=NULL;
list->n=0;
}

PERSON *inputPerson()
{
PERSON *person=(PERSON *)malloc(sizeof(PERSON));
printf("name:");
scanf("%s",person->name);
printf("surname:");
scanf("%s",person->surname);
printf("ID:");
scanf("%s",person->id);
return person;
}

void deleteTree(TREE_NODE *root)
{
if(root==NULL)
return;
deleteTree(root->left);
deleteTree(root->right);
free(root);
}

void printList(LIST list)
{
int i=0;
printf("Path:");
{
i++;
}
printf("\n");
}

I think that these two functions are not well implemented:
Code (Text):

void pathToNode(LIST *list,TREE_NODE *tree_node,TREE_NODE *root,int *found)
{
if(root==NULL)
return;
if(root==tree_node)
*found=1;
pathToNode(list,tree_node,root->left,found);
if(*found==0)
{
returnFirstElementOfList(list);
pathToNode(list,tree_node,root->right,found);
}
if(*found==1)
returnFirstElementOfList(list);
}

void printList(LIST list)
{
int i=0;
printf("Path:");
{
i++;
}
printf("\n");
}

3. main()
Code (Text):

int main()
{
char option;
PERSON *person=NULL;
int n=0,c=10,found=0,i=0;
TREE_NODE *node=NULL;
TREE_NODE *root=NULL;
TREE_NODE **nperson=(TREE_NODE **)malloc(c * sizeof(TREE_NODE *));
while(1)
{
fflush(stdin);
printf("enter option:");
scanf("%c",&option);
if(option=='A')
{
LIST list;
initList(&list);
person=inputPerson();
if(n+1 > c)
nperson=realloc(nperson,(c=c+10) * sizeof(TREE_NODE *));
node=formTreeNode(person);
nperson[n]=node;
found=0;
pathToNode(&list,node,root,&found);
printList(list);
n++;
}
else if(option=='M')
{
//print adjacency matrix of a graph???
}
else if(option=='E')
{
printf("end of program.");
deleteTree(root);
free(nperson);
break;
}
}
return 0;
}

Thanks for replies.

#### Attached Files:

• ###### image.PNG
File size:
3.2 KB
Views:
52
2. Aug 25, 2015