Want to win a PS4? Go Premium and enter to win our High-Tech Treats giveaway. Enter to Win

x
?
Solved

Help Inputting 2 Linked Lists

Posted on 2004-10-24
29
Medium Priority
?
259 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
Comment
Question by:Coconut77840
[X]
Welcome to Experts Exchange

Add your voice to the tech community where 5M+ people just like you are talking about what matters.

  • Help others & share knowledge
  • Earn cash & points
  • Learn & ask questions
  • 16
  • 7
  • 3
  • +1
29 Comments
 
LVL 3

Assisted Solution

by:HendrikTYR
HendrikTYR earned 280 total points
ID: 12395146
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
ID: 12395159
That resulted in an Error Report...
0
 
LVL 3

Expert Comment

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

Ptr = (Node *)malloc(sizeof(Node));                                          //create new node if name is not present
0
Concerto Cloud for Software Providers & ISVs

Can Concerto Cloud Services help you focus on evolving your application offerings, while delivering the best cloud experience to your customers? From DevOps to revenue models and customer support, the answer is yes!

Learn how Concerto can help you.

 

Author Comment

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

Assisted Solution

by:HendrikTYR
HendrikTYR earned 280 total points
ID: 12395236
...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
ID: 12395269
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
van_dy earned 720 total points
ID: 12395371
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
ID: 12395520
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
van_dy earned 720 total points
ID: 12395602
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
ID: 12395715

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
ID: 12395737
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
ID: 12395762
Nevermind about the "i" and the no output. Stupid mistake. :-)
0
 
LVL 5

Expert Comment

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

Author Comment

by:Coconut77840
ID: 12395854
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 46

Expert Comment

by:Kent Olsen
ID: 12395955
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
van_dy earned 720 total points
ID: 12396068
>> 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
ID: 12396113
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
ID: 12396147
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 46

Assisted Solution

by:Kent Olsen
Kent Olsen earned 200 total points
ID: 12396156
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
ID: 12396234
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
ID: 12396320
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:
van_dy earned 720 total points
ID: 12396347
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
ID: 12396367
take notice of the getchar() before 'return firstPtr' in InputSet() function. i already pointed out this earlier on.
0
 

Author Comment

by:Coconut77840
ID: 12396369
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
ID: 12396574
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 46

Assisted Solution

by:Kent Olsen
Kent Olsen earned 200 total points
ID: 12396685
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
ID: 12396738
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
ID: 12396782
Nevermind,

I got the Union to work now. Thanks.
0
 

Author Comment

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

Thank you all so much for you help!
0

Featured Post

VIDEO: THE CONCERTO CLOUD FOR HEALTHCARE

Modern healthcare requires a modern cloud. View this brief video to understand how the Concerto Cloud for Healthcare can help your organization.

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

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…
Summary: This tutorial covers some basics of pointer, pointer arithmetic and function pointer. What is a pointer: A pointer is a variable which holds an address. This address might be address of another variable/address of devices/address of fu…
The goal of this video is to provide viewers with basic examples to understand and use pointers in the C programming language.
The goal of this video is to provide viewers with basic examples to understand and use conditional statements in the C programming language.

609 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