• C

Help Inputting 2 Linked Lists

Hi,

I am trying to write a C program that will use a singly linked list to store two sets of words. For example, {bob, ted, carol, alice} should be stored in a linked list with 4 nodes. Each set should be input with one line where a return character comes after the last character of the last word. Also, if a word is repeated in a line, it should not be inserted twice into the singly linked list representing it.

The program should also do a few other calculations, but I seem to be having enough trouble simply inputting the same into the separate sets with the provided conditions. So far, I have written the following:

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

const int capacity=20;

struct Node {
     char name[capacity +1];
     struct Node* nextPtr;} ;
typedef struct Node Node;

void InputSet();
char peek();

int main(void)
{
     printf("Input the set x: ");
     InputSet();
     printf("Input the set y: ");
     InputSet();
     return 0;
}

char peek() {
     char c = getchar();
     ungetc(c, stdin);
     return c; }
      
void InputSet() {
     int i=0;
     char s[capacity+1];
     Node *firstPtr=NULL, *lastPtr=NULL, *Ptr, *testPtr;
     while (peek() != '\n') {
          scanf("%s", s);
          for (testPtr=firstPtr; testPtr != NULL; testPtr=testPtr->nextPtr) {         //test if name already there
               if (strcmp(s, testPtr->name)==0)
               i=2; }
          if (i=2) continue;                                                       //if name is present, input next name
          Ptr = malloc(sizeof(Node));                                          //create new node if name is not present
          strcpy(Ptr->name, s);
          Ptr->nextPtr = NULL;
          if (firstPtr == NULL)
               firstPtr=Ptr;
          else
               lastPtr->nextPtr=Ptr;
          lastPtr=Ptr;
          getchar(); }
     printf("names are: ");                                                            //check what's in the list (not working)
     Ptr=firstPtr;
     for (Ptr=firstPtr; Ptr!=NULL; Ptr=Ptr->nextPtr) {
         printf("%s ", Ptr->name);
          Ptr= Ptr->nextPtr; } }
Coconut77840Asked:
Who is Participating?
 
van_dyCommented:
ok, here is the edited program, test this

//Not tested
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define capacity 20

struct Node {
     char name[capacity +1];
     struct Node* nextPtr;} ;
typedef struct Node Node;

Node *InputSet(void);
char peek();

int main(void)
{
      Node *list1, *list2, *Ptr;
     printf("Input the set x: ");
     list1 = InputSet();
     printf("Input the set y: ");
     list2 = InputSet();
     for (Ptr=list1; Ptr!=NULL; Ptr=Ptr->nextPtr) {
         printf("%s ", Ptr->name);}
     for (Ptr=list2; Ptr!=NULL; Ptr=Ptr->nextPtr) {
         printf("%s ", Ptr->name);}
     return 0;
}

char peek() {
     char c = getchar();
     ungetc(c, stdin);
     return c; }
     
Node *InputSet(void) {
     int i=0;
     char s[capacity+1];
     Node *firstPtr=NULL, *lastPtr=NULL, *Ptr, *testPtr;
     while (peek() != '\n') {
          scanf("%s", s);
          for (testPtr=firstPtr; testPtr != NULL; testPtr=testPtr->nextPtr) {
               if (strcmp(s, testPtr->name)==0)
                    i=2; }
          if (i==2) {
               i=0;
               continue; }    
          Ptr = (Node *)malloc(sizeof(Node));
          strcpy(Ptr->name, s);
          Ptr->nextPtr = NULL;
          if (firstPtr == NULL)
               firstPtr=Ptr;
          else
          lastPtr->nextPtr=Ptr;
          lastPtr=Ptr;
          getchar(); }
     getchar();      
return firstPtr;
}
0
 
HendrikTYRCommented:
For a start you may try changing :

>> if (i=2) continue;                                                      //if name is present, input next name

to :

if (i==2) continue;                                                      //if name is present, input next name

0
 
Coconut77840Author Commented:
That resulted in an Error Report...
0
Ultimate Tool Kit for Technology Solution Provider

Broken down into practical pointers and step-by-step instructions, the IT Service Excellence Tool Kit delivers expert advice for technology solution providers. Get your free copy now.

 
HendrikTYRCommented:
You also need to cast your allocated memory address:

Ptr = (Node *)malloc(sizeof(Node));                                          //create new node if name is not present
0
 
Coconut77840Author Commented:
I have noted these changes, but the error report still comes up after the first input.
0
 
HendrikTYRCommented:
...also you print out your list:

>> for (Ptr=firstPtr; Ptr!=NULL; Ptr=Ptr->nextPtr) {
>>         printf("%s ", Ptr->name);
>>          Ptr= Ptr->nextPtr; }

You are moving your pointer twice, once in for(.......Ptr=Ptr->nextPtr)
and again as the last statement in the block

Hope this gets you going...
0
 
Coconut77840Author Commented:
Oh, thanks!! That takes care of the first set.

Now when I run the program, it asks for the first input and correctly outputs the first set with no repetitions.

But how come it won't even allow me to input the next set? The prompt is printed and immediately followed with "the names are " and nothing after that.
0
 
van_dyCommented:
simply make the following change  towards the end of
Inputset()


void InputSet() {
     int i=0;
     char s[capacity+1];
     Node *firstPtr=NULL, *lastPtr=NULL, *Ptr, *testPtr;
     while (peek() != '\n') {
   ............ // rest of you code
     Ptr=firstPtr;
     for (Ptr=firstPtr; Ptr!=NULL; Ptr=Ptr->nextPtr) {
         printf("%s ", Ptr->name);}
         getc(stdin);}

it will work fine then.
hope this helps,
van_dy
0
 
Coconut77840Author Commented:
Thank you both so much.

The inputs are working well with one exception:

If I input "bob carol bob", the output is "bob carol".
But if I input "bob bob carol", the output is only "bob".

Any ideas why? I have looked over the portion that tests for repetition and can't quite figure out why this is happening.
0
 
van_dyCommented:
thats a very silly mistake you have made.
in the function  void InputSet(), here is the problem;

 for (testPtr=firstPtr; testPtr != NULL; testPtr=testPtr->nextPtr) {         //test if name already there
               if (strcmp(s, testPtr->name)==0)
               i=2; }
          if (i==2) continue;          <----------- you should change the value of i, because it will remain 2 every time thru the loop. the correct way to do this is to replace the above line with
           if(i == 2){
                    i = 0;
                     continue;
           }
0
 
Coconut77840Author Commented:

I see what you mean and I was quite eager to give it a shot with that change, but something interesting is now happening. Neither output for any of the two lists is showing up after the input.... Why would i affect this?
0
 
Coconut77840Author Commented:
I also have a quick question about how these names are being stored. When I call the InputSet function the second time, does it overwrite the names from the first set? (i.e. Can the first set of the names be accessed after having called the InputSet a second time)
0
 
Coconut77840Author Commented:
Nevermind about the "i" and the no output. Stupid mistake. :-)
0
 
van_dyCommented:
Are you still unable to get the output ? please post ur final code, we can proceed from there
0
 
Coconut77840Author Commented:
This is my final code so far. The output portion of the program was working, and I took it out as I can only included it to make sure the input was working.

However, I have just realized that I have taken the wrong approach to the problem. The complete program requires that the names in each set be stored so that I can later access each set to find the union, intersection, and difference. With what I have written, the first set will be overwritten by the time I can the input a second time. I will now begin modifying my program by changing the Input function so that I will be able to pass pointers to it as parameters. I will probably encounter many more questions, at which point I will increaes the point value of this problem and begin asking. Thank you for all your help so far...

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

const int capacity=20;

struct Node {
     char name[capacity +1];
     struct Node* nextPtr;} ;
typedef struct Node Node;

void InputSet();
char peek();

int main(void)
{
     printf("Input the set x: ");
     InputSet();
     printf("Input the set y: ");
     InputSet();
     return 0;
}

char peek() {
     char c = getchar();
     ungetc(c, stdin);
     return c; }
      
void InputSet() {
     int i=0;
     char s[capacity+1];
     Node *firstPtr=NULL, *lastPtr=NULL, *Ptr, *testPtr;
     while (peek() != '\n') {
          scanf("%s", s);
          for (testPtr=firstPtr; testPtr != NULL; testPtr=testPtr->nextPtr) {
               if (strcmp(s, testPtr->name)==0)
                    i=2; }
          if (i==2) {
               i=0;
               continue; }      
          Ptr = (Node *)malloc(sizeof(Node));
          strcpy(Ptr->name, s);
          Ptr->nextPtr = NULL;
          if (firstPtr == NULL)
               firstPtr=Ptr;
          else
          lastPtr->nextPtr=Ptr;
          lastPtr=Ptr;
          getchar(); } }
0
 
Kent OlsenData Warehouse Architect / DBACommented:
Hi Coconut77840,

Just a hint, but I suggest that you store these items into the array in sorted (alphabetical) order.

Trust me.  :)
Kent
0
 
van_dyCommented:
>> When I call the InputSet function the second time, does it overwrite the names from the first set?

No, the names from the first set arent overwritten. u allocate new memory every time u call malloc.
it is a fairly simple matter to retreive the lists. You will only need to change the Inputset function a little bit.

consider the following prototype for it;

Node *Inputset(void)
{
........

return firstPtr;
}

int main()
{
        Node *mylist1 = Inputset();           // these two calls are going to return 2 different pointers and you can access
         Node *mylist2 = Inputset();          //  both the lists using these

hope this helps,
van_dy
0
 
Coconut77840Author Commented:
Ok, here is my modified program. I have re-included the output portions in the main program to test whether the program is inputting correctly, but after both inputs are taken an error report pops up before the output has a chance to appear. Help?

Kent, thank you for the hint, but I don't think I am allowed to use arrays for this program.

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

const int capacity=20;
     
struct Node {
     char name[capacity +1];
     struct Node* nextPtr;} ;
typedef struct Node Node;

void InputSet(Node **firstHandle, Node **lastHandle);
void InsertNode(Node **firstHandle, Node **LastHandle, Node *InsertionPtr, Node *Ptr);
Node *RandomInsertionPoint(Node *firstPtr);
char peek();

int main(void)
{
     Node *firstxPtr=NULL, *lastxPtr=NULL, *firstyPtr, *lastyPtr=NULL, *Ptr;
     printf("Input the set x: ");
     InputSet(&firstxPtr, &lastxPtr);
     printf("Input the set y: ");
     InputSet(&firstyPtr, &lastyPtr);
      
     printf("names are: ");
     Ptr=firstxPtr;
     for (Ptr=firstxPtr; Ptr!=NULL; Ptr=Ptr->nextPtr)
          printf("%s ", Ptr->name);
     getc(stdin);
      
     printf("names are: ");
     Ptr=firstyPtr;
     for (Ptr=firstyPtr; Ptr!=NULL; Ptr=Ptr->nextPtr)
          printf("%s ", Ptr->name);
     getc(stdin);
      
     return 0;
}

char peek() {
     char c = getchar();
     ungetc(c, stdin);
     return c; }
      
void InputSet(Node **firstHandle, Node **lastHandle) {
     int i=0;
     char s[capacity+1];
     Node *Ptr, *testPtr;
     while (peek() != '\n') {
          scanf("%s", s);
          for (testPtr=*firstHandle; testPtr != NULL; testPtr=testPtr->nextPtr) {
               if (strcmp(s, testPtr->name)==0)
                    i=2; }
          if (i==2) {
               i=0;
               continue; }                              /*If name present, don't create new node*/
          Ptr = (Node *)malloc(sizeof(Node));                  /*Create node if new name*/
          strcpy(Ptr->name, s);                                    
          getchar();
          InsertNode(firstHandle, lastHandle, RandomInsertionPoint(*firstHandle), Ptr);}
     getchar(); }
            
void InsertNode(Node **firstHandle, Node **lastHandle, Node *InsertionPtr, Node *Ptr) {
     if (InsertionPtr==NULL) {                                       /*Insert *Ptr after *InsertionPtr*/
          Ptr->nextPtr = *firstHandle;
          *firstHandle = Ptr; }
     else {
          Ptr->nextPtr = InsertionPtr->nextPtr;
          InsertionPtr->nextPtr = Ptr; }
     if (InsertionPtr==*lastHandle)
          *lastHandle = Ptr; }

Node *RandomInsertionPoint(Node *firstPtr) {          /*Selects random insertion point for new node*/
     Node *Ptr;
     for (Ptr=firstPtr; Ptr!=NULL; Ptr=Ptr->nextPtr)
          if(rand()%2) return Ptr;
     return NULL; }
            
0
 
Coconut77840Author Commented:
Wow...

So, van_dy, your simple change in the intial InputSet() function does the same thing as all the change I just did to the program??
0
 
Kent OlsenData Warehouse Architect / DBACommented:
Hi Coconut77840,


A typo on my part.  Store the items in the LIST in sorted (ascending) order.  It's often easier (and more efficient) to insert the items in the order that you want/need them than to sort them later.



Regarding your current work, I strongly suggest that you rework your functions just a bit to eliminate the indirection (pointer to a pointer).  There's nothing about what you've done that requires this much complication.


Kent
0
 
van_dyCommented:
Well yes.
U just need to have the pointer to your list head to traverse it. as Kdo pointed out,
you should use simpler function. try it as i suggested and lets know if u encountered
any problem.
0
 
Coconut77840Author Commented:
This is what it looks like according to van_dy's suggestion. An error report pops up after the first input is taken..

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

const int capacity=20;

struct Node {
     char name[capacity +1];
     struct Node* nextPtr;} ;
typedef struct Node Node;

Node* InputSet();
char peek();

int main(void)
{
     Node *firstxPtr, *firstyPtr, *Ptr;
     printf("Input the set x: ");
     firstxPtr = InputSet();
     printf("Input the set y: ");
     firstyPtr = InputSet();
      
     printf("names are: ");
     Ptr=firstxPtr;
     for (Ptr=firstxPtr; Ptr!=NULL; Ptr=Ptr->nextPtr)
          printf("%s ", Ptr->name);
     getc(stdin);
      
     printf("names are: ");
     Ptr=firstyPtr;
     for (Ptr=firstyPtr; Ptr!=NULL; Ptr=Ptr->nextPtr)
          printf("%s ", Ptr->name);
     getc(stdin);
      
     return 0;
}

char peek() {
     char c = getchar();
     ungetc(c, stdin);
     return c; }
      
Node* InputSet() {
     int i=0;
     char s[capacity+1];
     Node *firstPtr, *lastPtr, *Ptr, *testPtr;
     while (peek() != '\n') {
          scanf("%s", s);
          for (testPtr=firstPtr; testPtr != NULL; testPtr=testPtr->nextPtr) {
               if (strcmp(s, testPtr->name)==0)
                    i=2; }
          if (i==2) {
               i=0;
               continue; }      
          Ptr = (Node *)malloc(sizeof(Node));
          strcpy(Ptr->name, s);
          Ptr->nextPtr = NULL;
          if (firstPtr == NULL)
               firstPtr=Ptr;
          else
               lastPtr->nextPtr=Ptr;
          lastPtr=Ptr;
          getchar();}
     return firstPtr; }
0
 
van_dyCommented:
take notice of the getchar() before 'return firstPtr' in InputSet() function. i already pointed out this earlier on.
0
 
Coconut77840Author Commented:
Van_dy,

That worked perfectly, thanks a lot. I think I tried to do the same thing you did, but for some reason mine wouldn't compile correctly.

Thanks also Kent for your help.
I am going to work on finding the union and intersection now...
0
 
Coconut77840Author Commented:
Ok, so the intersection was a piece of cake.

But can someone help me develop a function for the union, such that for the sets
1) bob ted carol alice
2) carol alice jane
the union would be : jane bob ted carol alice

My intersection function is

Node *Intersection(Node *list1, Node *list2) {
     Node *Ptr, *Ptr2;
     for (Ptr=list1; Ptr != NULL; Ptr=Ptr->nextPtr) {
          for (Ptr2=list2; Ptr2 != NULL; Ptr2=Ptr2->nextPtr) {
               if (strcmp(Ptr->name, Ptr2->name)==0)
               printf("%s ", Ptr2->name); } } }

And I'm guessing the union would look close to that but a little most detailed, and I'm having trouble starting.. a few hints would be appreciated.. Thank you.
0
 
Kent OlsenData Warehouse Architect / DBACommented:
Hi Coconut77840,

Union is almost the same function.

1)  Print out all of the elements of the first list.
2)  Loop on each element of the second list.  Search the first list for the (current) element of the second list.  If found, skip.  Otherwise print it.


Kent
0
 
Coconut77840Author Commented:
Kent,

This is what I came up with after thinking about it, but it is obviously flawed since it doesn't produce the correct output :

Node *Union(Node *list1, Node *list2) {
     Node *Ptr, *Ptr2;
     for (Ptr=list1; Ptr != NULL; Ptr=Ptr->nextPtr)
          printf("%s ", Ptr->name);
     for (Ptr2=list2; Ptr2 != NULL; Ptr2=Ptr2->nextPtr) {
          for (Ptr=list1; Ptr != NULL; Ptr=Ptr->nextPtr) {
               if (strcmp(Ptr->name, Ptr2->name)==0)
                    continue;
               else
                    printf("%s ", Ptr2->name);       }}}
0
 
Coconut77840Author Commented:
Nevermind,

I got the Union to work now. Thanks.
0
 
Coconut77840Author Commented:
I have just completed the program and it's compiling perfectly.

Thank you all so much for you help!
0
Question has a verified solution.

Are you are experiencing a similar issue? Get a personalized answer when you ask a related question.

Have a better answer? Share it in a comment.

All Courses

From novice to tech pro — start learning today.