Thread: Linked list task [C]

  1. #1
    Registered User
    Join Date
    Nov 2019
    Posts
    6

    Linked list task [C]

    Repl.it - SkyblueVioletredLocation
    I have a following code. It's linked list task with multiple functions.
    I got task with structures, specific functions to finish for working with Linked list and main() function.
    I already did all of these functions, yet I'm not sure if I did it right. For first few I'm pretty sure they are OK, but for functions
    Item *list_find_name,

    Item *list_find_minid not that sure.

    Someone experienced with working in Linked list, should be able to answer.
    Any help will be good.

  2. #2
    Registered User rstanley's Avatar
    Join Date
    Jun 2014
    Location
    New York, NY
    Posts
    699
    Please post the code you have done, so far, using [ CODE ] tags, so we can comment on it and guide you for the next steps. Please don't post a link to the code.

    Please read the FAQ at the top of the page.
    Last edited by rstanley; 12-20-2019 at 07:47 AM.

  3. #3
    Registered User
    Join Date
    Nov 2019
    Posts
    6
    Code:
    /**
     *  * structure Object
     *   */
    typedef struct {
      int id;
      char *name;
    } Object;
    
    /**
     *  * Item of the list
     *   */
    typedef struct item Item;
    struct item {
      Object data;
      Item *next;
    };
    
    /**
     *  * type List
     *   */
    typedef struct {
      Item *first;
    } List;
    
    /**
     *  * List initialization. Creates empty list. 
     *   */
    List list_ctor()
    {
      List list;
      list.first = NULL;
      return list;
    }
    
    /**
     *  * Itinialise item of list. From object creates item without successor.
     *   */
    Item *item_ctor(Object data)
    {
      Item *item;
      item = malloc(sizeof(Item));
      item->next = NULL;
      item->data = data;
      return item;
    }
    
    /**
     *  * Put item to the beggining of list.
     *   */
    void list_insert_first(List * list, Item * i)
    {
      i->next = list->first;
      list->first = i->next;
    }
    
    /**
     *  * Return true, if list is empty.
     *   */
    bool list_empty(List * list)
    {
      if (list->first == NULL)
        return true;
      else
        return false;
    }
    
    /**
     *  * Remove first element in list, if it is.
     *   */
    void list_delete_first(List * list)
    {
      Item *item = list->first;
      list->first = item->next;
    
    }
    
    /**
     *  * Returns number of elements in list.
     *   */
    unsigned list_count(List * list)
    {
      int count = 0;
      List *current = list;
      while (list != NULL) {
        count++;
        list->first = current->first;
    
      }
      return count;
    
    }
    
    /**
     *  * Finds item in list with with smallest identifier(id) Returns NULL, if
     *   * list is empty
     *    */
    Item *list_find_minid(List * list)
    {
      Item *item;
    
      if (list->first != NULL) {
        int min = item->data.id;
        while (list->first != NULL) {
          if (min > item->data.id) {
            min = item->data.id;
            return item;
          }
        }
      } else
        return NULL;
    
    }
    
    /**
     *  * Find item in list with corresponding name of object. Returns NULL, if
     *   * item like that doesn't exist
     *    */
    Item *list_find_name(List * list, char *name)
    {
      Item *item;
      while (list->first != NULL) {
        if (strcmp(name, item->data.name) == 0)
          return item;
        else
          return NULL;
      }
    }
    
    /**
     *  * Free list.
     *   */
    void list_dtor(List * list)
    {
      free(list);
    }
    
    /*-----------------------------------------------*/
    int main()
    {
      printf("list_ctor...\n");
      List list = list_ctor();
    
      printf("list_empty...\n");
      printf("Seznam prazdny: %s\n", list_empty(&list) ? "ano" : "ne");
    
      Item *item;
    
      Object o1 = { 42, "Honza" };
      printf("item_ctor...\n");
      item = item_ctor(o1);
      printf("list_insert_first...\n");
      list_insert_first(&list, item);
    
      printf("Seznam prazdny: %s\n", list_empty(&list) ? "ano" : "ne");
      printf("list_count...\n");
      printf("Pocet prvku v seznamu: %d\n", list_count(&list));
    
      Object o2 = { 2, "Malem" };
      item = item_ctor(o2);
      printf("list_insert_first...\n");
      list_insert_first(&list, item);
    
      Object o3 = { 0, "Kralem" };
      item = item_ctor(o3);
      printf("list_insert_first...\n");
      list_insert_first(&list, item);
    
      printf("Pocet prvku v seznamu: %d\n", list_count(&list));
    
      printf("Odstraneni prvniho prvku ze seznamu \n");
      list_delete_first(&list);
      printf("Pocet prvku v seznamu: %d\n", list_count(&list));
    
      // opetovne vlozeni objektu o1    
      item = item_ctor(o1);
      printf("list_insert_first...\n");
      list_insert_first(&list, item);
    
      printf("list_find_minid...\n");
      item = list_find_minid(&list);
      if (item != NULL) {
        printf("Polozka s nejmensim identifikatorem: {%d, " % s "}\n",
               item->data.id, item->data.name);
      } else
        printf("Polozka s nejmensim identifikatorem nenalezena\n");
    
      printf("list_find_name...\n");
      char *name = "Honza";
      item = list_find_name(&list, name);
      if (item != NULL) {
        printf("Polozka s daty %s nalezena\n", name);
      } else
        printf("Polozka s daty %s nenalezena.\n", name);
    
      printf("list_dtor...\n");
      list_dtor(&list);
      printf("Seznam prazdny: %s\n", list_empty(&list) ? "ano" : "ne");
    
      return 0;
    }
    Last edited by Salem; 12-20-2019 at 10:55 PM. Reason: Removed crayola

  4. #4
    Registered User
    Join Date
    Aug 2019
    Location
    Inside a Singularity
    Posts
    239
    Remember to do what rstanley said next time onwards.

    Your minid function looks wrong. You must loop through your entire list to find the minimum which in your code just returns the first item->data.id. Same problem with your find name function. There's also code that is not required but I'll not make a mention of that yet.

    Edit: Actually, minid function has an infinite loop looking closely (assuming list->first is not NULL). Also, you're doing checks with uninitialised pointers to objects that'll yield you garbage value comparison. I quickly glanced through your code (I've to go for dinner) and I think a lot of other things are wrong like the destructor but I'll have to look closely to see what you're actually trying to do.
    Last edited by Zeus_; 12-20-2019 at 10:58 AM.
    "Programming today is a race between software engineers striving to build bigger and better idiot-proof programs, and the Universe trying to produce bigger and better idiots. So far, the Universe is winning." - Rick Cook, The Wizardry Compiled

  5. #5
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    37,677
    Run the code in the debugger.
    Code:
    $ gcc -g foo.c
    $ gdb -q ./a.out 
    Reading symbols from ./a.out...done.
    (gdb) run
    Starting program: ./a.out 
    list_ctor...
    list_empty...
    Seznam prazdny: ano
    item_ctor...
    list_insert_first...
    Seznam prazdny: ano
    list_count...
    ^C
    Program received signal SIGINT, Interrupt.
    0x00000000004007ab in list_count (list=0x7fffffffde00) at foo.c:92
    92	    list->first = current->first;
    (gdb) bt
    #0  0x00000000004007ab in list_count (list=0x7fffffffde00) at foo.c:92
    #1  0x0000000000400966 in main () at foo.c:162
    (gdb) list
    87	{
    88	  int count = 0;
    89	  List *current = list;
    90	  while (list != NULL) {
    91	    count++;
    92	    list->first = current->first;
    93	
    94	  }
    95	  return count;
    96	
    (gdb) print count
    $1 = 683116588
    (gdb)
    Right, so go read the code for list_count and figure out how it got a count of 683116588 without even finishing the function.

    > I already did all of these functions, yet I'm not sure if I did it right.
    Lemme guess, you wrote all the code, fixed the compile errors and then tried to run it, only to find it didn't work.

    That's the wrong approach.
    Your write / compile / test loop needs to be much shorter - like just one function at a time.
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Replies: 13
    Last Post: 09-22-2013, 10:34 PM
  2. Task list in VC 2005
    By VirtualAce in forum Tech Board
    Replies: 0
    Last Post: 05-13-2008, 08:59 PM
  3. Replies: 2
    Last Post: 12-31-2007, 11:40 AM
  4. Replies: 6
    Last Post: 03-02-2005, 02:45 AM
  5. How to get a list of programs in task bar?
    By Josh Kasten in forum Windows Programming
    Replies: 1
    Last Post: 06-03-2003, 06:00 AM

Tags for this Thread