List of List Program

arpit.jh001's Avatar, Join Date: Feb 2012
Go4Expert Member
/* In this program I have used an array of pointers and try to link every element of that with the node of same type but can't able to get the desired output....This program was written with the intention of storing a graph without using array for storing adjacency matrix.......but cant find a proper solution ..kindly help*/
Code:
#include<malloc.h>
#include<iostream.h>

struct node
{ int vertex;
  node *link;

};

int nodes;

void display(struct node *a)
{ struct node *temp;
  for(int i=0;i<nodes;i++)
  { cout<<a[i].vertex;
     temp = &a[i];
     while(temp->link!=NULL)
     { temp = temp->link;
        cout<<"->"<<temp->vertex;
     }
    cout<<"\n";
  }
}
void main()
{
  char ch;
  struct node *temp,*t1;
  cout<<"\n Enter the number of vertices : ";
  cin>>nodes;
  node *a= (struct node*)malloc((sizeof(struct node))*nodes);
  for(int i=1;i<=nodes;i++)
  {   a[i-1].vertex = i;
        cout<<"Is node "<<i<<" is connected to some other node(y/n):";
        cin>>ch;
        if((ch == 'y') || (ch == 'Y'))
        {
          temp = &a[i-1] ;
          cout<<"node no."<<i<<" is connected to :";
          while(ch=='Y' || ch=='y')
          { t1 = (struct node*)malloc(sizeof(struct node));
             cout<<"\nEnter vertex no.";
             cin>>t1->vertex;
             temp->link = t1;
             t1=temp;
             cout<<"\nAny other node(y/n):";
             cin>>ch;
          }
          t1->link=NULL;
        }
  }
  display(a);
}

Last edited by shabbir; 15Feb2012 at 15:32.. Reason: Code blocks
0
xpi0t0s's Avatar, Join Date: Aug 2004
Mentor
What input did you give the program?
What output did you get?
What output did you expect?
arpit.jh001 like this
0
arpit.jh001's Avatar, Join Date: Feb 2012
Go4Expert Member
Code:
//I found the solution....Thanks for your reply:nice:
#include<malloc.h>
#include<iostream.h>

struct node
{ int vertex;
  struct node *link;
};

int nodes;

void display(struct node *a)
{ struct node *temp;
  for(int i=0;i<nodes;i++)
  { cout<<a[i].vertex;
     temp = &a[i];
     while(temp->link!=NULL)
     { temp = temp->link;
        cout<<"->"<<temp->vertex;
     }
    cout<<"\n";
  }
}
void main()
{
  char ch;
  struct node *temp,*t1;
  cout<<"\n Enter the number of vertices : ";
  cin>>nodes;
  node *a= (struct node*)malloc(nodes*(sizeof(struct node)));
  for(int i=1;i<=nodes;i++)
  {   a[i-1].vertex = i;
        cout<<"Is node "<<i<<" is connected to some other node(y/n):";
        cin>>ch;
        if((ch == 'y') || (ch == 'Y'))
        {
          temp = &a[i-1] ;
          cout<<"node no."<<i<<" is connected to :";
          while(ch=='Y' || ch=='y')
          { t1 = (struct node*)malloc(sizeof(struct node));
             cout<<"\nEnter vertex no.";
             cin>>t1->vertex;
             temp->link = t1;
             temp=t1;
             cout<<"\nAny other node(y/n):";
             cin>>ch;
          }
        }
        temp->link=NULL;
  }
  display(a);
}
//There was few silly mistakes in my program.But now it is fully correct....This Program is used for storing graph using Link List..First it asks for the number of vertices you want to store in the graph...then for each vertex(starting with vertex 1) it asks whether it is connected to some other vertex..if yes then it asks for the vertex number...few more corrections need to be done to make it more efficient and able to handle invalid inputs......

Last edited by shabbir; 18Feb2012 at 09:22.. Reason: Code blocks
0
arpit.jh001's Avatar, Join Date: Feb 2012
Go4Expert Member
Code:
//This has more functionalities.....it can search whether two vertices are connected or  not :smug::D
#include<malloc.h>
#include<conio.h>
#include<stdlib.h>
#include<iostream.h>

struct node
{ int vertex;
  struct node *link;
};

int nodes;

void display(struct node *a)
{ struct node *temp;
  for(int i=0;i<nodes;i++)
  { cout<<a[i].vertex;
     temp = &a[i];
     while(temp->link!=NULL)
     { temp = temp->link;
        cout<<"->"<<temp->vertex;
     }
     cout<<"\n";
  }
}
void search_connec(struct node *a ,int x,int y)
{  struct node *temp;
    temp = &a[x-1];
     while(temp->link!=NULL)
     { temp = temp->link;
        if(temp->vertex == y)
        { cout<<"\nVertex "<<x<<" is connected to vertex "<<y<<"\n";
          return;
        }
     }
     cout<<"\nNot connected";

}
void main()
{ int x,y,choice;
  char ch;
  struct node *temp,*t1;
  cout<<"\n Enter the number of vertices : ";
  cin>>nodes;
  node *a= (struct node*)malloc(nodes*(sizeof(struct node)));
  for(int i=1;i<=nodes;i++)
  {   a[i-1].vertex = i;
        cout<<"Is node "<<i<<" is connected to some other node(y/n):";
        cin>>ch;
        if((ch == 'y') || (ch == 'Y'))
        {
          temp = &a[i-1] ;
          cout<<"node no."<<i<<" is connected to :";
          while(ch=='Y' || ch=='y')
          { t1 = (struct node*)malloc(sizeof(struct node));
             cout<<"\nEnter vertex no.";
             cin>>t1->vertex;
             while(!((t1->vertex) <= nodes))
             { cout<<"\nInvalid node! Please re-enter correct node :";
                cin>>t1->vertex;
             }
             temp->link = t1;
             temp=t1;
             cout<<"\nAny other node(y/n):";
             cin>>ch;
          }
        temp->link=NULL;
        }
        else
        a[i-1].link=NULL;
  }
  do{
        cout<<"\n -------------------------- \n";
        cout<<"              MENU            \n";
        cout<<"\n -------------------------- \n";
        cout<<"      1.Display Graph         \n";
        cout<<"      2.Search Connection     \n";
        cout<<"\n    Enter your choice :       ";
        cin>>choice;
        switch(choice)
        {
         case 1: display(a);
                    break;
         case 2: clrscr();
                    cout<<"\n Enter source vertex :";
                    cin>>x;
                    cout<<"\n Enter destination vertex :";
                    cin>>y;
                    search_connec(a,x,y);
                    break;
         default : cout<<"\n Invalid choice";
                    break;
        }
     }while(choice==1 ||choice==2);
}

Last edited by shabbir; 18Feb2012 at 09:24.. Reason: Code blocks
0
xpi0t0s's Avatar, Join Date: Aug 2004
Mentor
Please use code blocks when posting code; it retains the formatting and makes it a lot easier to read.