Thread: Linked List Help

  1. #1
    Registered User
    Join Date
    Mar 2004
    Posts
    14

    Linked List Help

    First off, I am new to C. Only been using for 5 weeks or so, so bare with me please My stupid prof insists that we program in C as well as java. I am pretty sure this is the last program I will have to write in C so I am just trying to get it over with...here we go.

    I have a few things left to do to this program I am writing that modifies a linked list of strings.

    1. I misread the instructions and I have to have the program read a list of strings from a file and store them one by one in the list. I wrote a function to do this, but it keeps crashing my program. Check it out and tell me whats the deal.

    2. I have to search for a desired string, and remove it from the list. Not really sure where to start on this one. See below for my efforts, heh.

    3. I have to make a deep copy of the list. I know this is easy, I just dont know how to code it. I am not eactly sure what I am supposed to do with the copied list. I think it just needs to be a temporary list that needs to just be printed to the screen to prove that it copied, but thats about it. Any info on how to code this would be helpful.

    4. And lastly, I have to concatinate two strings. Combine two lists together...eek! No clue where to start here.

    Code:
    #include <stdio.h>
    #include <stdlib.h>
    #include <string.h>
    
    typedef struct
    {
        char *str;
        int len;
    } String;
    
    struct Node 
    {
        struct Node * next;
        String str;
    };
    
    
    struct Node * AllocNode(String string)
    {
        struct Node * node = (struct Node *)malloc(sizeof(struct Node));
     
        if(node != NULL)
        { 
             node->next = 0;
             node->str.len = strlen ( string.str );
             node->str.str = malloc ( node->str.len + 1 );
             if ( node->str.str != NULL )
             strcpy ( node->str.str, string.str );
        }
        
        return node;    
    }
    
    
    void DestroyList(struct Node ** st)
    {
        struct Node * next, * prev = *st;
     
        while(prev != NULL)
        {
             next = prev->next;
             free(prev);
             prev = next;
        } 
        
        *st = 0;   
    }
    
    struct Node * AddNodeIF(struct Node ** st) //this has some problems.
    {
        FILE *ifp;
        String string;
        char buff[BUFSIZ];
        string.str = buff;
      
        ifp = fopen("input.txt", "r");
      
        do
        {
            fscanf(ifp, "%s", &string.str);
                AddNode(&st, string);
        }
        while (!feof(ifp));   
    
        return st;
        fclose(ifp);  
    }
    
    struct Node * AddNode(struct Node ** st, String string)
    {
        struct Node * next = *st;
        struct Node * node = AllocNode(string);
     
        if(*st != NULL)
        {
            while(next->next != NULL)
            {
                      next = next->next;
            }
            
            next->next = node;     
        } 
        else
        {
            *st = node;
        }  
        
         return node;
    }
    
    struct Node * RemoveNode(struct Node ** st, String string) 
    {
        //seach for the string in the list;
        //if found, remove it;
        //if not found, print "string not found in list;
    }
    
    int Search(struct Node ** st, String string) 
    {
        struct Node * next = *st;
        int c = 0;
        
        if (*st != NULL)
        {
             //if string in list, c = 1; return c;
             //else, c = 2; return c;
        }
    }
    
    struct Node * CopyList(struct Node * st) 
    (
        //struct Node * tempst;
        //then copy all nodes in st to tempst;
        //print tempst;
    )
    
    struct Node * Concatinate(struct Node * st1, struct Node * st2) 
    {
        //struct Node * tempst;
        //then copy all nodes in st1;
        //then copy all nodes in st2;
        //print tempst;
    }
         
    void PrintList(struct Node * st)
    {
        struct Node * next = st;
     
        while(next != NULL)
        {
            printf("%s\n", next->str.str);
         
            next = next->next;
        } 
    }
    
    int MainMenu(void)
    { 
     int c = 0;
     printf("\n%s\n%s\n%s\n%s\n%s\n%s\n%s\n%s\n%s\n%s",
     "-MAIN MENU-",
     "1. Initialize the list by reading in strings from the input and adding one by one to the linked list.",
     "2. Print all the strings in the list.",
     "3. Remove a string from a list (interactively).",
     "4. Add a string to the list (interactively).",
     "5. Search for a string in the list.",
     "6. Make a deep copy of the list.",
     "7. Concatenate two lists.",
     "8. Destory the list. A new list can be created by selecting 1.",
     "9. Quit.\n");
     
     scanf("%d", &c);
     
     return c;
    }
    
     int main()
    {
     struct Node * st1 = NULL;
     struct Node * st2 = NULL;
     String string;
     int choice = 0;
     int listchoice = 0;
     int yon = 0;
     char buff[BUFSIZ];
     string.str = buff;
    
     choice = MainMenu();
     
     do
     {
         if (choice == 1)
         {
              printf("%s", "Which list would you like to add strings to? 1 or 2?");
              scanf("%d", listchoice);
              
              if (listchoice == 1)
              {
    		  st1 = AddNodeIF();
    		  AddNode(&st1, string);
              choice = MainMenu();
              }
              else 
              {
              st2 = AddNodeIF();
    		  AddNode(&st2, string);
              choice = MainMenu();
              }
         }
      
     else if (choice == 2) 
     {
    	 printf("%s", "Which list would you like to print? 1 or 2?");
         scanf("%d", listchoice);
         
         if (listchoice == 1)
         {
         printf("%s", "List 1 contains:\n");
         PrintList(st1);
    	 choice = MainMenu();
    	 }
    	 else
    	 {
    	 printf("%s", "List 2 contains:\n");
         PrintList(st2);
    	 choice = MainMenu();
    	 }
     }
     
     else if (choice == 3) 
     {
         printf("%s", "Which list would you like to remove a string from? 1 or 2?");
         scanf("%d", listchoice);
         
         if (listchoice == 1)
         {
         printf("%s", "Please enter the string you wish to remove from list 1: \n");
         scanf("%s", string.str);
         RemoveNode(&st1, string);
    	 choice = MainMenu();
    	 }
    	 else
    	 {
         printf("%s", "Please enter the string you wish to remove from list 2: \n");
         scanf("%s", string.str);
         RemoveNode(&st2, string);
    	 choice = MainMenu();
    	 }
     }
     else if (choice == 4) 
     {
         printf("%s", "Which list would you like to add a string to? 1 or 2?");
         scanf("%d", listchoice);
         
         if (listchoice == 1)
         {
    	 printf("%s", "Please enter the string you wish to add to list 1: \n");
         scanf("%s", string.str);
         AddNode(&st1, string);
    	 choice = MainMenu();
    	 }
    	 else
         {
    	 printf("%s", "Please enter the string you wish to add to list 2: \n");
         scanf("%s", string.str);
         AddNode(&st2, string);
    	 choice = MainMenu();
    	 }
     }
     
     else if (choice == 5) 
     {
         printf("%s", "Which list would you like to search in? 1 or 2?");
         scanf("%d", listchoice);
         
         if (listchoice == 1)
         {
              yon = Search(st1, string);
         
                   if (yon == 1)
                   {
                        printf("%s", "Yes, the string entered exists in list 1.\n");
                   }
                   else
                   {
                        printf("%s", "No, the string entered does not exist in list 1.\n");
                   }
         else
         {
              yon = Search(st2, string);
         
                   if (yon == 1)
                   {
                        printf("%s", "Yes, the string entered exists in list 1.\n");
                   }
                   else
                   {
                        printf("%s", "No, the string entered does not exist in list 1.\n");
                   }
         }
     }
     
     else if (choice == 6) 
     {
         printf("%s", "Which list would you like to copy? 1 or 2?");
         scanf("%d", listchoice);
         
         if (listchoice == 1)
         {
              CopyList(st1);
         }
         else
         {
              CopyList(st2);
         }
     }
     
     else if (choice == 7) 
     {
         Concatinate(st1, st2);
     } 
     
     else if (choice == 8) 
     {
         printf("%s", "Which list would you like to destroy? 1 or 2?");
         scanf("%d", listchoice);
         
         if (listchoice == 1)
         {
    	      DestroyList(&st1);
    	      printf("%s", "List 1 has been destroyed. To create another, simply chose choice 1.\n"); 
    	      choice = MainMenu();
    	 }
    	 else
    	 {
    	     DestroyList(&st2);
             printf("%s", "List 2 has been destroyed. To create another, simply chose choice 1.\n"); 
             choice = MainMenu();
    	 }
     }
     }
     while (choice != 9);
     return 0;
    }
    Ugh...just want to get this overwith, please help

  2. #2
    Obsessed with C chrismiceli's Avatar
    Join Date
    Jan 2003
    Posts
    501
    Usually people don't post this big of code you should really cut it down to you know where the problems is, at a glance I saw this
    Code:
    scanf("%d", listchoice);
    it needs to be
    Code:
    scanf("%d",& listchoice);
    if it isn't a string it needs the &
    also to concatenate strings
    Code:
    char *strcat(char *dest, const char *src);
    Last edited by chrismiceli; 03-10-2004 at 07:17 PM.
    Help populate a c/c++ help irc channel
    server: irc://irc.efnet.net
    channel: #c

  3. #3
    Registered User
    Join Date
    Mar 2004
    Posts
    14
    i know, sorry for posting so much code. it is just that last time i posted a little bit of code, i was asked to post all of it...so i just tried to save some time.

    thanks for those fixes, I have made some changes.

    also, how does that concat method you posted work?

    -B

  4. #4
    ... kermit's Avatar
    Join Date
    Jan 2003
    Posts
    1,534
    strcat() appends the source string to the destination string, and in the process gets rid of the '\0' at the end of the destination string and appends a terminating '\0' at the end of the new concatenated string.

    so the prototype, as chrismiceli already wrote, is like this:

    char *strcat(char *dest, const char *src);

    call the function, feed it two strings, the first is the destination string, and the second is the source string. In other words, if you had two strings, string_1 and string_2, it would work like this:

    strcat(string_1, string_2);

    strcat takes string_2, adds it to the end of string_1, and deals with the '\0' appropriately.

    Make sense?

    ~/

  5. #5
    Registered User
    Join Date
    Mar 2004
    Posts
    14
    I think so, but I am not sure that is what I am supposed to do. I am supposed to concatinate two linked lists full of strings. I think that would mean to combine them into one list, but I may be interpreting it wrong. What you guys think?

    -B

  6. #6
    Code Goddess Prelude's Avatar
    Join Date
    Sep 2001
    Posts
    9,897
    >What you guys think?
    It means take the second list and tack it onto the first list:
    Code:
    first_list = add_end ( first_list, second_list );
    Don't get confused with operations on the list structure and operations on the data contained within the list structure. The two are quite different.
    My best code is written with the delete key.

  7. #7
    Registered User
    Join Date
    Mar 2004
    Posts
    14
    ok, with the search and remove node method. I cant get it to remove the node. I am trying to manipulate the addnode method to get it to work, but I am having no luck. Here is what I have...

    Code:
    struct Node * RemoveNode(struct Node ** st, String string) 
    {
        struct Node * next = *st; 
        struct Node * node = AllocNode(string);
     
        if(*st != NULL) 
        {     
            while(next != string.str) <---this is the problem, dont know how to search for the node.
            {
                 next = next->next;
            }     
        } 
        else
        {
            node = NULL;
        }  
        
         return node;
    }
    -B

  8. #8
    Code Goddess Prelude's Avatar
    Join Date
    Sep 2001
    Posts
    9,897
    >while(next != string.str)
    Strings cannot be compared with relational operators. Use strcmp or strncmp (or memcmp) instead:
    Code:
    /* Work on your naming scheme! */
    if ( strcmp ( (*st)->str.str, string.str ) == 0 ) {
      /* Remove the first node */
      node = *st;
      *st = (*st)->next;
    }
    else {
      /* Remove everything else */
      while ( strcmp ( next->next->str.str, string.str ) != 0 )
        next = next->next;
      node = next->next;
      next->next = next->next->next;
    }
    Okay, now my head is spinning from all of those str's and next's. Hopefully I wasn't too disoriented to give you a correct algorithm.
    My best code is written with the delete key.

  9. #9
    Guest Sebastiani's Avatar
    Join Date
    Aug 2001
    Location
    Waterloo, Texas
    Posts
    5,708
    Hmm...that code looks awful familiar...looks like you're just trying to get other people to fill in the blanks for you. What a loser.
    Code:
    #include <cmath>
    #include <complex>
    bool euler_flip(bool value)
    {
        return std::pow
        (
            std::complex<float>(std::exp(1.0)), 
            std::complex<float>(0, 1) 
            * std::complex<float>(std::atan(1.0)
            *(1 << (value + 2)))
        ).real() < 0;
    }

  10. #10
    Registered User
    Join Date
    Mar 2004
    Posts
    14
    Hey, now thats not very nice. Yes, I have used some examples from these forums, but most of it is my own making. Like I said I am learning as I go here, and I am having to figure a lot on my own. Give me a damn break.

    Prelude, thanks once again for your advice. Could you please explain some of your code to me so I have a clearer picture?

    Thanks,

    -B

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. C++ Linked list program need help !!!
    By dcoll025 in forum C++ Programming
    Replies: 1
    Last Post: 04-20-2009, 10:03 AM
  2. Following CTools
    By EstateMatt in forum C Programming
    Replies: 5
    Last Post: 06-26-2008, 10:10 AM
  3. Reverse function for linked list
    By Brigs76 in forum C++ Programming
    Replies: 1
    Last Post: 10-25-2006, 10:01 AM
  4. Template Class for Linked List
    By pecymanski in forum C++ Programming
    Replies: 2
    Last Post: 12-04-2001, 09:07 PM
  5. singly linked list
    By clarinetster in forum C Programming
    Replies: 2
    Last Post: 08-26-2001, 10:21 PM