Hackety Hacking Problem Compare and copy: Difference between revisions

From OLPC
Jump to navigation Jump to search
(cat)
 
(3 intermediate revisions by one other user not shown)
Line 14: Line 14:


== Curriculum Connections ==
== Curriculum Connections ==

To be done.......
1. Rudimentary knowledge of Data Structures
2. Creating, Traversing and Deletion of Nodes of Linked list
3. Using Recursion to solve problems


== Solution ==
== Solution ==


<pre>
<pre>
/* CODE tested on Turbo C++ 3.0 Compiler
20th October 2007
*/
//Include necessary files (for defining prototypes of functions used)

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


typedef struct node // Making a structure to represent a node of Linked List.
typedef struct node // A structure representing a node of Linked List and re-naming it as node(Using typedef)
{
{
int info;
int info;
Line 30: Line 38:
node;
node;


node *sptr1=NULL, *sptr2=NULL; // Initialize the 2 Linked List pointer to header nodes with NULL.
node *sptr1=NULL, *sptr2=NULL; // Initialize the 2 Linked List pointer to header nodes with NULL(Empty Linked List)


int menu()
int menu()
Line 36: Line 44:
int ch;
int ch;
printf("\nEnter your choice\n");
printf("\nEnter your choice\n");
printf("1.add node\n2.compare lists\n3.traverse list\n4.copy link list\n5.exit\n");
printf("1.Add node\n2.Compare lists\n3.Traverse list\n4.Copy link list\n5.Exit\n");
scanf("%d",&ch); // Menu Driven Program
scanf("%d",&ch); // Menu Driven Program
return ch;
return ch;
Line 171: Line 179:


</pre>
</pre>
[[Category: Hackety Lesson Plan]]

Latest revision as of 20:05, 6 April 2008

Problem Statement

You are the coordinator of the class and you have been assigned the task of maintaining the test results of the students. You have to take marks alloted to the students as input and then compare it with the final list given to you by the teacher. Being intelligent, you try to speed up your task by making a program which can accept marks of the student and then compare it with the list given to by teacher.

You don't know the number of students in the class. Therefore you have a create a dynamic list.

HINT: Write a program to compare two linked list using recursion. And hence write a program to copy one linked list into another using recursion.

Sample Output

To be done.......

Curriculum Connections

1. Rudimentary knowledge of Data Structures 2. Creating, Traversing and Deletion of Nodes of Linked list 3. Using Recursion to solve problems

Solution

/* CODE tested on Turbo C++ 3.0 Compiler 
20th October 2007
*/
//Include necessary files (for defining prototypes of functions used)

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

typedef struct node         // A structure representing a node of Linked List and re-naming it as node(Using typedef)
{
	int info;
	struct node* ptr;
}
node;

node *sptr1=NULL, *sptr2=NULL;        // Initialize the 2 Linked List pointer to header nodes with NULL(Empty Linked List)

int menu()
{
	int ch;
	printf("\nEnter your choice\n");
	printf("1.Add node\n2.Compare lists\n3.Traverse list\n4.Copy link list\n5.Exit\n");
	scanf("%d",&ch);             // Menu Driven Program
	return ch;
}

node *addnode(node *sptr)  // When a new node is to be added in Linked List
{
 node *temp;
 temp=(node*) malloc (sizeof(node));
 temp->ptr=NULL;
 temp->info=NULL;
 printf("enter the no.");  // Asking user to enter data in node
 scanf("%d",&temp->info);
 if(sptr==NULL)            // Condition to check whether the node being added is 1st node
	sptr=temp;
 else
  {
	temp->ptr=sptr;
	sptr=temp;
  }
  return sptr;            // returns the pointer to 1st node of List.
}

int compare(node *ptr1,node *ptr2)
{

    if((ptr1->info==ptr2->info) && ptr1!=NULL && ptr2!=NULL)
    {
     ptr2=ptr2->ptr;
     ptr1=ptr1->ptr;
     compare(ptr1,ptr2); // Recursive function call.
     }
    if(ptr1==NULL && ptr2==NULL)
    {
                  printf("the link lists are equal");
                  return (0);
    }
    else if(ptr1==NULL)
    {
         printf("linklist 1 is smaller and not equal");
         return(0);
    }
    else if(ptr2==NULL)
    {
        printf("linklist 2 is smaller and not equal");
        return 0;
    }
    else 
    printf("the lists are not equal");
    return 0;
}

int copy(node *ptr1,node *ptr2)
{
    if(ptr1!=NULL && ptr2!=NULL)
    {
		  ptr2->info=ptr1->info;
		  ptr1=ptr1->ptr;
		  ptr2=ptr2->ptr;
		  copy(ptr1,ptr2);
    }

    return 0;
}

int  traverse(node *sptr)
{
 node *t;
 t=sptr;
 while(t->ptr)
	{
		printf("%d\t",t->info);
		t=t->ptr;
	}
   printf("%d",t->info);
   return 0;
}

int main()
{
     int i;
  do
  {
	switch(menu())
	{
		case 1:
	     printf("enter the link list in which u want to enter element\n");
	     printf("1.1st link lis\n2.2nd link list\n");
	     scanf("%d",&i);
	     if(i==1)
			sptr1=addnode(sptr1);
	     else if(i==2)
			sptr2=addnode(sptr2);
			else
			printf("enter correctly");
			break;
		case 2:
			compare(sptr1,sptr2);
			break;
		case 3:
	     printf("enter the list no. to be traversed\n");
	     scanf("%d",&i);
	     if(i==1)
			traverse(sptr1);
			 else if(i==2)
		    traverse(sptr2);
		    else
		    printf("enter correctly");
			break;
		case 4:
	     printf("enter the list no. u want to copy");
	     scanf("%d",&i);
	     if(i==1)
	     copy(sptr1,sptr2);
	     else if(i==2)
	     copy(sptr2,sptr1);
	     else
	     {
	     printf("enter correct no.");
	     break;
	     }
	     printf("the copied link list2 is\n");
	     traverse(sptr2);
	     break;
	case 5:
			exit(0);

	}
  }
	while(1);
 getch();
 return 0;
}