Solved

Help Inputting 2 Linked Lists

Posted on 2004-10-24
253 Views
Last Modified: 2010-04-15
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; } }
0
Question by:Coconut77840
    29 Comments
     
    LVL 3

    Assisted Solution

    by:HendrikTYR
    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
     

    Author Comment

    by:Coconut77840
    That resulted in an Error Report...
    0
     
    LVL 3

    Expert Comment

    by:HendrikTYR
    You also need to cast your allocated memory address:

    Ptr = (Node *)malloc(sizeof(Node));                                          //create new node if name is not present
    0
     

    Author Comment

    by:Coconut77840
    I have noted these changes, but the error report still comes up after the first input.
    0
     
    LVL 3

    Assisted Solution

    by:HendrikTYR
    ...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
     

    Author Comment

    by:Coconut77840
    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
     
    LVL 5

    Assisted Solution

    by:van_dy
    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
     

    Author Comment

    by:Coconut77840
    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
     
    LVL 5

    Assisted Solution

    by:van_dy
    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
     

    Author Comment

    by:Coconut77840

    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
     

    Author Comment

    by:Coconut77840
    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
     

    Author Comment

    by:Coconut77840
    Nevermind about the "i" and the no output. Stupid mistake. :-)
    0
     
    LVL 5

    Expert Comment

    by:van_dy
    Are you still unable to get the output ? please post ur final code, we can proceed from there
    0
     

    Author Comment

    by:Coconut77840
    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
     
    LVL 45

    Expert Comment

    by:Kdo
    Hi Coconut77840,

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

    Trust me.  :)
    Kent
    0
     
    LVL 5

    Assisted Solution

    by:van_dy
    >> 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
     

    Author Comment

    by:Coconut77840
    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
     

    Author Comment

    by:Coconut77840
    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
     
    LVL 45

    Assisted Solution

    by:Kdo
    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
     
    LVL 5

    Expert Comment

    by:van_dy
    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
     

    Author Comment

    by:Coconut77840
    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
     
    LVL 5

    Accepted Solution

    by:
    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
     
    LVL 5

    Expert Comment

    by:van_dy
    take notice of the getchar() before 'return firstPtr' in InputSet() function. i already pointed out this earlier on.
    0
     

    Author Comment

    by:Coconut77840
    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
     

    Author Comment

    by:Coconut77840
    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
     
    LVL 45

    Assisted Solution

    by:Kdo
    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
     

    Author Comment

    by:Coconut77840
    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
     

    Author Comment

    by:Coconut77840
    Nevermind,

    I got the Union to work now. Thanks.
    0
     

    Author Comment

    by:Coconut77840
    I have just completed the program and it's compiling perfectly.

    Thank you all so much for you help!
    0

    Write Comment

    Please enter a first name

    Please enter a last name

    We will never share this with anyone.

    Featured Post

    Do You Know the 4 Main Threat Actor Types?

    Do you know the main threat actor types? Most attackers fall into one of four categories, each with their own favored tactics, techniques, and procedures.

    Suggested Solutions

    Have you thought about creating an iPhone application (app), but didn't even know where to get started? Here's how: ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ Important pre-programming comments: I’ve never tri…
    This is a short and sweet, but (hopefully) to the point article. There seems to be some fundamental misunderstanding about the function prototype for the "main" function in C and C++, more specifically what type this function should return. I see so…
    The goal of this video is to provide viewers with basic examples to understand and use pointers in the C programming language.
    Video by: Grant
    The goal of this video is to provide viewers with basic examples to understand and use nested-loops in the C programming language.

    856 members asked questions and received personalized solutions in the past 7 days.

    Join the community of 500,000 technology professionals and ask your questions.

    Join & Ask a Question

    Need Help in Real-Time?

    Connect with top rated Experts

    12 Experts available now in Live!

    Get 1:1 Help Now