Link to home
Start Free TrialLog in
Avatar of Coconut77840
Coconut77840

asked on

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; } }
SOLUTION
Avatar of HendrikTYR
HendrikTYR

Link to home
membership
This solution is only available to members.
To access this solution, you must be a member of Experts Exchange.
Start Free Trial
Avatar of Coconut77840
Coconut77840

ASKER

That resulted in an Error Report...
You also need to cast your allocated memory address:

Ptr = (Node *)malloc(sizeof(Node));                                          //create new node if name is not present
I have noted these changes, but the error report still comes up after the first input.
SOLUTION
Link to home
membership
This solution is only available to members.
To access this solution, you must be a member of Experts Exchange.
Start Free Trial
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.
SOLUTION
Link to home
membership
This solution is only available to members.
To access this solution, you must be a member of Experts Exchange.
Start Free Trial
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.
SOLUTION
Link to home
membership
This solution is only available to members.
To access this solution, you must be a member of Experts Exchange.
Start Free Trial

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?
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)
Nevermind about the "i" and the no output. Stupid mistake. :-)
Are you still unable to get the output ? please post ur final code, we can proceed from there
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(); } }
Avatar of Kent Olsen
Hi Coconut77840,

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

Trust me.  :)
Kent
SOLUTION
Link to home
membership
This solution is only available to members.
To access this solution, you must be a member of Experts Exchange.
Start Free Trial
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; }
            
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??
SOLUTION
Link to home
membership
This solution is only available to members.
To access this solution, you must be a member of Experts Exchange.
Start Free Trial
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.
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; }
ASKER CERTIFIED SOLUTION
Link to home
membership
This solution is only available to members.
To access this solution, you must be a member of Experts Exchange.
Start Free Trial
take notice of the getchar() before 'return firstPtr' in InputSet() function. i already pointed out this earlier on.
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...
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.
SOLUTION
Link to home
membership
This solution is only available to members.
To access this solution, you must be a member of Experts Exchange.
Start Free Trial
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);       }}}
Nevermind,

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

Thank you all so much for you help!