common elements in two linked list

[akanksha]

Hello all,
As far as I have read the post here in the board and the rules ,all discussions pertain to C++ language but I want to disscuss linked list ,stacks queues in C language.Can i do so?

Below is a program to to first create two linked list and then extract the common elements in both the list and print the same.But the program is not working properly.Can anyone see?

[syntax="cpp"]

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

struct link
{
int info;
struct link *next;
};

int i,number;
struct link *start, *previous, *node,*one,*two;

void create_list(struct link *node)
{
char ch;
start->next = NULL;
node=start; /* Point to the start of the list*/

node->next = (struct link* ) malloc(sizeof(struct link));
node = node->next;
i = 0;
while(ch !='n')
{
printf("\n Input the node: %d: ", (i+1));
scanf("%d", &node->info);
node->next = NULL;

fflush(stdin);

printf("\nInput choice n for break: ");
ch=getchar();
i++;
if(ch!='n')
{
node->next = (struct link* ) malloc(sizeof(struct link));
node = node->next;
}
}
}

void display(struct link *node)
{
node=start->next;
printf("\n The list is as follows:\n");
while (node)
{
printf(" %d", node->info);
node = node->next;
}
}

void common(struct link *list_one,struct link *list_two,struct link *list_three)
{
start->next=NULL;
start->next=list_three;

for(one=list_one; one!=NULL ; one=one->next)
{
for(two=list_two ; two!=NULL ; two=two->next)
{
if(one->info == two->info)
{
list_three->info= one->info;
printf("\nthe element of list one is %d", one->info);

list_three->next=(struct link *) malloc(sizeof(struct link *));
list_three=list_three->next;
}
}
}
list_three->next=NULL;
}

void main()
{
struct link *list_one = (struct link *) malloc(sizeof(struct link));
struct link *list_two =(struct link *) malloc (sizeof(struct link));
struct link *list_three = (struct link *) malloc(sizeof(struct link));
/*list_three contains all the common elements */
clrscr();
printf("Enter the first list");
create_list(list_one);
display(list_one);

printf("\nEnter the second list");
create_list(list_two);
display(list_three);

common(list_one,list_two,list_three);
display(list_three);
getch();
}

[/syntax]

[MXP]

What is the error you're getting?

[akanksha]

The common function is not workng properly.The program is not showing the common elements.Instead it throwing two garbage values .I dont know what changes are to be made in the common function.
There is no problem in making of the two list.But its not picking the common elements.
I m using Turbo C compiler.

It could be its 'coz of some error in other function also...Dont know.

[MXP]

I think the problem is the global variable start. I dont think it's needed.

[Emery]

Do the rules erroneously say that C questions are not allowed somewhere? This is a C/C++ forum. C problems come up all the time. The sub-forum descriptions even say "C/C++".

[Alvaro]

I'll add a few comments to your code, to explain what I think is wrong with it.
[syntax="cpp"]# include <stdio.h>
/*
* malloc.h and conio.h are not standard and should be avoided.
* This program probably doesn't need conio.h, and memory
* allocation prototypes are in stdlib.h.
* I know you want to use conio.h to clear the screen and wait
* for input at the end of the program, so "the window doesn't close",
* but it makes it hard for other people to test your program.
* I recommend sticking to the parts of the language that are standard,
* at least while you are learning the basics.
*/
# include <malloc.h>
#include<conio.h>

struct link
{
int info;
struct link *next;
};

/*
* These global variables are going to get you in trouble.
* These should be local variables of the functions that use them.
* If you need some reasons why global variables are a bad idea, ask.
*/
int i,number;
struct link *start, *previous, *node,*one,*two;

/*
* This prototype is odd. You probably want this function to either
* return a link* or take as a parameter a link **.
* Another option is creating a new struct called linked_list that servers
* as a header for the list. Right now you have some confusion between
* what is a node and what is a list. You seem to be using link to mean both;
* at the very least this is not elegant.
*/
void create_list(struct link *node)
{
char ch;
/*
* The next line of code will write to a random place in memory.
* If you are lucky, it will crash. Where should start point?
*/
start->next = NULL;
node=start; /* Point to the start of the list*/

node->next = (struct link* ) malloc(sizeof(struct link));
node = node->next;
/* What is this i used for? */
i = 0;
/*
* You don't know if ch is 'n' or not the first time, since it is uninitialized.
* Use a do-while loop instead.
*/
while(ch !='n')
{
/* You need to flush stdout after a line like this. Use `fflush(stdout);'. */
printf("\n Input the node: %d: ", (i+1));
scanf("%d", &node->info);
node->next = NULL;

/* I don't think `fflush(stdin)' means anything... */
/* http://faq.cprogramming.com/cgi-bin/sma ... 1043284351 */
fflush(stdin);

printf("\nInput choice n for break: ");
/* This is a bad method to input ints. Enter '1' and you'll get 49 in your variable. */
ch=getchar();
i++;
if(ch!='n')
{
node->next = (struct link* ) malloc(sizeof(struct link));
node = node->next;
}
/* You could have done the `node->next = NULL;' in an else block here. */
}
/*
* Wait a second. Where is the line that says `node->info=...'?
* I don't know why you said "There is no problem in making of the two list."
* Did you test it? How can it possibly work?
*/
}

void display(struct link *node)
{
/* Again, using start without knowing where it points... Bad idea. */
node=start->next;
printf("\n The list is as follows:\n");
while (node)
{
printf(" %d", node->info);
node = node->next;
}
}

void common(struct link *list_one,struct link *list_two,struct link *list_three)
{
/* The next two statements are meaningless */
start->next=NULL;
start->next=list_three;

/*
* Here you get in trouble because of the confusion between link and list.
* You are using the info field of the first node of each list, which doesn't have
* a meaningful value.
*/
for(one=list_one; one!=NULL ; one=one->next)
{
for(two=list_two ; two!=NULL ; two=two->next)
{
if(one->info == two->info)
{
list_three->info= one->info;
printf("\nthe element of list one is %d", one->info);

list_three->next=(struct link *) malloc(sizeof(struct link *));
list_three=list_three->next;
}
}
}
list_three->next=NULL;
}

void main()
{
struct link *list_one = (struct link *) malloc(sizeof(struct link));
struct link *list_two =(struct link *) malloc (sizeof(struct link));
struct link *list_three = (struct link *) malloc(sizeof(struct link));
/*list_three contains all the common elements */
clrscr();
printf("Enter the first list");
create_list(list_one);
display(list_one);

printf("\nEnter the second list");
create_list(list_two);
display(list_three);

common(list_one,list_two,list_three);
display(list_three);
getch();
}

/* The program is over, and I still haven't seen a line of code giving start a value. */
[/syntax]

[akanksha]

[syntax="cpp"]
# include <stdio.h>
# include <malloc.h>
#include<conio.h>

struct link
{
int info;
struct link *next;
};

int i,number;

void create_list(struct link *node)
{
char ch='y';
start->next = NULL;
start->next = node;
/* first the memory is allocated in the main function and then start is made to point the first node.I dont now any other way to make a list start*/

i = 0; /*i is used in the printf statement */
while(ch !='n')
{
printf("\n Input the node: %d: ", (i+1));
/*Why to use fflush(stdout).I have never used that nor faced any error.what is the need to fflush out the screen?*/
scanf("%d", &node->info);
node->next = NULL;

fflush(stdin);
/*I m using turbo c compiler and many a times my programs didnt work only 'coz of the absence of this line,so I use.why a bad idea?*/
printf("\nInput choice n for break: ");
ch=getchar();
/*What is the prob with this kind of input.Yes on entering 1 you will get 49.But the variable checks for 'n' i.e 79.Neways, can use scanf also.*/
i++;
if(ch!='n')
{
node->next = (struct link* ) malloc(sizeof(struct link));
node = node->next;
}
/* node->next = null has already been done so no need of the else part */
}
/*what line are you looking for: node->info ..?the value of info part has already been take up by the user */
}


void display(struct link *node)
{
node=start->next;
/*List is created and now start points to the first node having a particular address in the memory */
printf("\n The list is as follows:\n");
while (node)
{
printf(" %d", node->info);
node = node->next;
}
}

void common(struct link *list_one,struct link *list_two,struct link *list_three)
{
start->next=NULL;
start->next=list_three;
/*start is made to point to the first node of the list.why meaningless?*/
/*Not geteing what you are saying here.Can you elaborate?I made the function what I know can you rectify?*/
for(one=list_one; one!=NULL ; one=one->next)
{
for(two=list_two ; two!=NULL ; two=two->next)
{
if(one->info == two->info)
{
list_three->info= one->info;
printf("\nthe element of list one is %d", one->info);

list_three->next=(struct link *) malloc(sizeof(struct link *));
list_three=list_three->next;
}
}
}
list_three->next=NULL;
}

void main()
{
struct link *list_one = (struct link *) malloc(sizeof(struct link));
struct link *list_two =(struct link *) malloc (sizeof(struct link));
struct link *list_three = (struct link *) malloc(sizeof(struct link));
/*list_three contains all the common elements */
clrscr();
printf("Enter the first list");
create_list(list_one);
display(list_one);

printf("\nEnter the second list");
create_list(list_two);
display(list_three);

common(list_one,list_two,list_three);
display(list_three);
getch();
}

[/syntax]
About the confusion......
Linked list is a data structure used to maintain a dynamic series of data
Node is a part of the linked list and linked list is the chain of the nodes wherein each node contain a data field(some value) and a pointer type variable pointing to the next node in the series.Each node points to the next node of its type.The link exits in between the nodes.

[Alvaro]

Start at main and try to simulate what the computer will do trying to execute your program. First it will allocate three blocks of memory of the correct size to hold a `struct link' and make list_one, list_two and list_three point to them. So far, so good. Then it will clear the screen and print "Enter the first list" into a buffer that will eventually go to the screen (but you should fflush(stdout) to make sure that this actually happens; many compilers will not flush out the output until you print the next '\n'). Then it will go into create_list, passing it a pointer to the `struct link' list_one.

Now the real trouble begins. ch is set to 'y' (fine), and then we store a pointer to NULL into an unknown place called "start->next". If I were the compiler, I would be very confused.

I recommend you start with a tiny, tiny program where you can make sure that you can follow every step and verify that it is doing the right thing.

First of all, how do you represent an empty list? Is it a pointer to NULL? Or is it a pointer to a link that points to NULL? This has to be decided. If you pick the first option, then there is something wrong with the prototypes, and you should be passing around double pointers to `struct link'. If it is the second, it's kind of ugly that the first node (the one that acts as the header of the list) has a unused `info' field. Something about this design smells bad, and I think you should replace the first node with a struct of a different type, which represents the header of a list (which you can identify with the list itself).

Here's some working code for option1:
[syntax="c"]#include <stdio.h>
#include <stdlib.h>

/* Using typedef like this lets you not say `struct' everywhere */
typedef struct node_s {
int info;
struct node_s *next; /* this is the only place where you have to use `struct' */
} node;

/* Passing a double pointer allows you to change the value of the pointer */
void push_node_at_the_head(node **list, int data){
node *new_node = (node *) malloc(sizeof(node));

new_node->info = data;
new_node->next = *list;
*list = new_node;
}

/* We could pass a double pointer here for uniformity, and it could be a const pointer in that case */
void print_list_content(node *list){
node *it;

printf("( ");
for(it = list; it!=NULL; it=it->next)
printf("%d ",it->info);
printf(")\n");
}

void destroy_list(node **list){
node *next_node, *it;

for(it = *list; it!=NULL; it=next_node){
next_node = it->next;
free(it);
}

*list = NULL;
}

int main(){
node *list=NULL;
print_list_content(list); /* prints an empty list */
push_node_at_the_head(&list, 1);
push_node_at_the_head(&list, 2);
push_node_at_the_head(&list, 3);
print_list_content(list); /* prints "( 3 2 1 )" */
destroy_list(&list);
print_list_content(list); /* prints an empty list */
}

[/syntax]

[akanksha]

Hello Alvaro,
Thanx for the reply.But i have some doubts,plz clear them.

1. Why global variables should be avoided.
2. I am using turbo c compiler and I have'nt faced any such situation where the printf statement does'nt work if'\n' is not appended. In any case,it works good.Should I use then too(fflush(stdout). I am an Indian and not even a single book author has recommended this. Can you tel why they dont think this is neccesary.

3. Plz explain me your words-
(a) ''First of all, how do you represent an empty list? Is it a pointer to NULL? Or is it a pointer to a link that points to NULL? This has to be decided. If you pick the first option, then there is something wrong with the prototypes, and you should be passing around double pointers to `struct link''.

-----This as you did in the sample program.You passed the address of the pointer and then used double pointers.This is how we should access the list?

(b)If it is the second, it's kind of ugly that the first node (the one that acts as the header of the list) has a unused `info' field. Something about this design smells bad, and I think you should replace the first node with a struct of a different type, which represents the header of a list (which you can identify with the list itself).

-------How can we replace the first node with the different type of struct?All the variables creating the list has to be of the similiar types! Not understood ?. Plz make a function illustrating this.

4.In your sample program-
push_node_at_the_head(node **list, int data)

If I do-------push_node_at_the_head(node *list, int data) and in main-
push_node_at_the_head(list, 1);
Then if this also a bad idea?I mean this you have also used in the print function,so why don't you think it good?

[MXP]

1. Global variables can lead to confusing program flow, as they do in your program. Using locals and passing variables as arguments allows you to better keep track of what is happening to the data used by your program.

2. The key is "most compilers". It might work for you but it might not work for us.

[Alvaro]

3. Plz explain me your words-
(a) ''First of all, how do you represent an empty list? Is it a pointer to NULL? Or is it a pointer to a link that points to NULL? This has to be decided. If you pick the first option, then there is something wrong with the prototypes, and you should be passing around double pointers to `struct link''.

-----This as you did in the sample program.You passed the address of the pointer and then used double pointers.This is how we should access the list?

The double pointer allows you to modify the value of the pointer. That way you can insert a new node at the head, and change who the first node is.

(b)If it is the second, it's kind of ugly that the first node (the one that acts as the header of the list) has a unused `info' field. Something about this design smells bad, and I think you should replace the first node with a struct of a different type, which represents the header of a list (which you can identify with the list itself).

-------How can we replace the first node with the different type of struct?All the variables creating the list has to be of the similiar types! Not understood ?. Plz make a function illustrating this.

[syntax="c"]typedef struct {
node *head;
node *tail;
unsigned size;
} linked_list;
[/syntax]
Now there is a clear distinction between what a list is and what a node is. Most functions will pass a pointer to the linked_list as a first parameter.

4.In your sample program-
push_node_at_the_head(node **list, int data)

If I do-------push_node_at_the_head(node *list, int data) and in main-
push_node_at_the_head(list, 1);
Then if this also a bad idea?I mean this you have also used in the print function,so why don't you think it good?

If you do that, then the function gets the pointer by value, and it can't change where the list points. In the case of my program, the pointer will always point to NULL.

I think it is not clear to you that a function gets copies of its parameters, and therefore it cannot change the value of a variable in the calling code. For instance
[syntax="c"]#include <stdio.h>

void multiply_by_three(int x){
x *= 3;
}

int main(void){
int n=5;

multiply_by_three(n);
printf("%d\n",n); // Will print 5
}
[/syntax]

If you want the function to modify a variable in the calling code, you need to pass a pointer to the variable, like this:
[syntax="c"]#include <stdio.h>

void multiply_by_three(int *x){
*x *= 3;
}

int main(void){
int n=5;

multiply_by_three(&n);
printf("%d\n",n); // Will print 15
}
[/syntax]

Once this is clear, imagine that the variable we need to change is not of type `int', but of type `node *', and you'll see why I used double pointers.

[akanksha]

Thanx Alvaro. i know the concept of calling function by value and by refernce. But i m doing structures for the first time so facing problem and it seems difficult for me to understand this all at once. actually what you are saying and what our books says are little bit different.

Neways thanx again. Here i m posting the previous program but only the creation and display function of the program, which is not running proprely.I want to confirm that in your program there is no 'start' node (which has only the addess of the first node, and not any data filed).

[syntax="cpp"]
#include<stdio.h>
#include<stdlib.h>
typedef struct link
{
int info;
struct link *next;
}NODE;

void create_list(NODE **list)
{
int i=0;
char ch='y';
NODE *node =(NODE *) malloc(sizeof(NODE));

while(ch !='n')
{
printf("\n Input the node: %d: ", (i+1));
fflush(stdout);
scanf("%d", &node->info);

node->next = *list;
*list=node;

printf("\nInput choice n for break: ");
fflush(stdout);
scanf("%c",&ch);
i++;
if(ch!='n')
{
node->next = (NODE* ) malloc(sizeof(NODE));
node = node->next;
}
}
}

void display(NODE *node)
{
printf("\n the list is as follows");
while (node)
{
printf(" %d", node->info);
fflush(stdout);
node = node->next;
}
}

void main()
{
NODE *list_one=NULL, *list_two=NULL, *list_three=NULL;

printf("Enter the first list");
create_list(&list_one);
display(list_one);

printf("\nEnter the second list");
create_list(&list_two);
display(list_two);
}

[/syntax]

[Alvaro]

[...]Here i m posting the previous program but only the creation and display function of the program, which is not running proprely.

What do you mean by that? What input are you using, what happens and what did you expect to happen?

I want to confirm that in your program there is no 'start' node (which has only the addess of the first node, and not any data filed).

That's correct. And as I said before, it might be a good idea to have a header for the linked list, but it would be of a different type.

In the code that I posted, there was a function to push nodes at the head of the list. It's probably a good idea if you try to keep the details of how the list works as isolated as possible, by using functions like that one to perform all the basic operations on nodes. For instance, the function that gets the data from the user shouldn't have to deal with re-arranging pointers. That way it's easier to test that the basic functions are working correctly, and then if you are having trouble with the input, you know that it is unlikely that the problem has anything to do with the linked list.

The problems you are having probably have to do with the input. scanf() is a tricky function to use. The first call works fine, but the second call (when you try to get a single character) just reads the '\n' character, the end of line which was not consumed by the previous call to scanf() and which is still waiting in the input buffer.

The first thing you should do is write a program that just does the input, without using a linked list at all. You just ask for a list of integers and you just print each integer back as you read it (to make sure that you are reading them correctly), and then you ask if the user wants to continue. Once you get that working, you can try to write the function that you really want.

The best way I know to do robust input is to read entire lines of input with fgets() and then parse the line of text that you obtained (for instance, using sscanf()).

If you still have trouble with the input, post a little program that only does input and say exactly what behaviour you were trying to get and what behaviour you are getting instead.

[akanksha]

What do you mean by that? What input are you using, what happens and what did you expect to happen?

That program is not working properly. I mean,it is taking the inputs but at the time of printing it goes in indefinite loop. For eg. If I input two values i.e 11 and 22, Then it prints these values again and again. I cant detect the errors. While it should only print 11 and 22.

The first thing you should do is write a program that just does the input, without using a linked list at all. You just ask for a list of integers and you just print each integer back as you read it (to make sure that you are reading them correctly), and then you ask if the user wants to continue. Once you get that working, you can try to write the function that you really want.

Alvaro ,Are you talking about the basic program of taking in the integers and printing back what is taken? I know this little program. If still you wanna see then I ll upload......Also I dont know how to use fgets.I mean I have read about this but only the defination and its working. It inolves opening of a file, so how should I do that. Also I know Alvaro that it is always better to use good input functions(like fgets,sscanf) but for the time being ,if only it is possible, do with scanf , I m comfortable with that. Once the basic program is made I ll try to switch over to these functions.

That's correct. And as I said before, it might be a good idea to have a header for the linked list, but it would be of a different type.

Sorry Alvaro, im still not getting how to attach that header. you took 'unsigned size'. I mean, to have a header which will contain the address.it should be a pointer! Plz give a small code explaining this. Hope you wont mind that.

[Alvaro]

Alvaro ,Are you talking about the basic program of taking in the integers and printing back what is taken?

Yes, the program that takes integers, prints them back and allows you to say that there are no more integers in some way (like the 'y'/'n' thing).

I know this little program. If still you wanna see then I ll upload......

Yes, please. That part of your code didn't work well.

Also I dont know how to use fgets.I mean I have read about this but only the defination and its working. It inolves opening of a file, so how should I do that. Also I know Alvaro that it is always better to use good input functions(like fgets,sscanf) but for the time being ,if only it is possible, do with scanf , I m comfortable with that. Once the basic program is made I ll try to switch over to these functions.

That's fine. Let's try to make it work with scanf. I just mentioned it for future reference, when you want to do it the right way. You don't need to open a file, since `stdin' is a "file" that refers to the user's input. You can just pass that to fgets().

That's correct. And as I said before, it might be a good idea to have a header for the linked list, but it would be of a different type.

Sorry Alvaro, im still not getting how to attach that header. you took 'unsigned size'. I mean, to have a header which will contain the address.it should be a pointer! Plz give a small code explaining this. Hope you wont mind that.

Well, this is the header I proposed:

Code: Select all

typedef struct {
  node *head;
  node *tail;
  unsigned size;
} linked_list;

`head' is the only thing that you really need to implement a basic linked list. Keeping `tail' and `size' allow you to implement certain common operations much much faster: inserting at the end and counting the number of elements in the list can be done in constant time when you have those field, and they are cheap to keep updated.

If you use this structure then the function to insert a node at the head is like this:
[syntax="c"]
void push_node_at_the_head(linked_list *list, int data){
node *new_node = (node *) malloc(sizeof(node));

new_node->info = data;
new_node->next = list->head;
list->head = new_node;
if(list->size==0)
list->tail = new_node;
list->size++;
}
[/syntax]

If you find this confusing, use the double pointer. If you find double pointers confusing, use this. At this point I think you should use whatever feels more natural to you.