Thread: Dynamic List Char Array & Double Linked List

  1. #1
    Registered User
    Join Date
    Oct 2013
    Posts
    75

    Dynamic List Char Array & Double Linked List

    Hello, and thank you in advance for any help. I have written and completed a dynamic list of strings and feel as though I understand the structure and all. I now am writing a double linked list, using dynamic lists of characters for each node. How would I go about linking the two together, so that each node will point to a char array until a \0 appears.

    Such that:

    char[0] = d
    char[1] = o
    char[3] = g
    char[4] = \0
    char[5] = c
    char[6] = a
    char[7] = t
    char[8] = \0

    And to where the first node in my doubly linked list will read dog and the second node will be cat.

    Thank you again for any help sent my way.

  2. #2
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,336
    What exactly is your concern? The only possible change to your list is changing char[80] (for some suitable value of "80") to char * if you weren't using char* in the first place.

    You will have some extra maintenance to do in terms of this giant pool of chars that you are using as a storage mechanism, but that's not actually related to lists, but to using a giant pool of chars as a data buffer. (In a more traditional, for lack of a better word, scenario you would offload that bookkeeping onto malloc/free. Now, instead of calling malloc, you'll deal with reserving space out of the giant pool of chars; and instead of calling free, you'll release that space.) That maintenance would happen for any kind of data structure you use, not just lists.

  3. #3
    Registered User
    Join Date
    Oct 2013
    Posts
    75
    Where are you talking about that I would change that? Very sorry for the late reply.

  4. #4
    Registered User
    Join Date
    Oct 2013
    Posts
    75
    I have a dynamic list that is set up for strings to be put in, I'm not too sure on everything that I would need to change for it to just put the characters of each string into an array rather than the whole string itself. I've been playing around with it but can't seem to find the right piece.

  5. #5
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,336
    Quote Originally Posted by Roadrunner2015 View Post
    Where are you talking about that I would change that? Very sorry for the late reply.
    Presumably you defined your data structure somewhere like
    Code:
    struct list_node {
        char datafield[80];
        struct list_node *prev, *next;
    }
    Now your stored info isn't an array of char, but just a pointer to those chars in memory.

  6. #6
    Registered User
    Join Date
    Oct 2013
    Posts
    75
    That would be for my doubly linked list, correct? My node is currently defined as

    Code:
    struct lnode {
            char item[1024];
            struct lnode *next, *prev;
    };
    Which I think I will have to change the char item[1024] to char item[1]? But I'm struggling on the dynamic list part of it. For strings my dynamic list is defined as

    Code:
    struct dlist {
            int sz;
            int maxsz;
            char item[1][1024];
    };
    I don't want the straight answer, because I want to be able to understand exactly what I'm doing. Would I need to change the [1024] to [1] for characters? Or would something need to be changed inside my insert function or fgets method?
    Last edited by Roadrunner2015; 10-17-2013 at 09:01 PM.

  7. #7
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,336
    To be blunt, I can't imagine a reason why "char item[1][1024]" should exist. If you have it in your program, that is a crying shame. Your first struct is correct for a doubly-linked list; you'll just need to change the type of item.

    You can't use char[1] as a pseudonym for char* -- char[1] is not a pointer that can be reassigned, it will always point at the same one (consequently not useful) byte. If you aren't up on pointers. and given that this is pretty much the opposite of dynamic (ie a fixed-forever 1024-character buffer), I suppose you could store instead the index the string starts in this 1024-byte buffer.

  8. #8
    Registered User
    Join Date
    Oct 2013
    Posts
    75
    I can't imagine a reason why "char item[1][1024]" should exist.
    That is because in my dynamic list I had strings being read in, the max characters I expected was 1024.

    You can't use char[1] as a pseudonym for char* -- char[1] is not a pointer that can be reassigned, it will always point at the same one
    So what exactly should my header for the dlist say about the item? char *item? or char *item[1]? It is supposed to be an array of characters, such as

    char[1] = c
    char[2] = a
    char[3] = t

    As of right now, (and excuse me if I am behind, I am trying to read on all of this and understand. Using this forum board as a place to ask questions I don't understand) I am more concerned about getting the array set up. I can focus on the entering of the characters from a string after.

  9. #9
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,336
    Quote Originally Posted by Roadrunner2015 View Post
    It is supposed to be an array of characters
    This is inconsistent with what you posted earlier, which is that it was supposed to be a pointer to an array stored elsewhere.

    In any event, there is never(*) a reason to put [1] in an array declaration (as you just then have a single variable anyway), so that is simply not an option.

    (*There used to be a reason, in pre-1999 code, as a way to get a start on a variable-length "array". We now have actual variable-length arrays and flexible struct members, so it isn't really needed any longer, and certainly not here.)

  10. #10
    Registered User
    Join Date
    Oct 2013
    Posts
    75
    So i've been working on this non-stop and I got to where i can insert the characters into the dlist character by character. The problem I am now facing, and I think i might have to re-do some of my code to get this to work, is inserting the characters up to a null terminator into my doubly linked list.


    Code:
    while ( (x = fgetc(fp)) != EOF){
                    if (x == '\n')
                            x = '\0';
                    fprintf(stderr, "       x is %c.\n", x);
                    data += ins_dlist(x, &p);
                    fprintf(stderr, "Inserting %c into data.\nData is %s.\n", x, data);
                    if (x == '\n'){
                            ins_dlist('\0', &p);
                            fprintf(stderr, "Data is %s before going into the ins_llist loop.\n", data);
                    }
            }
    Is what I am using right now to read into the dlist. The part that is in red is what im trying to use as the strings to insert into the llist, but its coming up as garbage when i print out what it is. The return of a char is fine, and i know the x is the character it needs to be... but its somewhere after i cat it with data that its getting messed up. Is there another way to do this that is alot easier or am i just blowing this big time?

  11. #11
    Registered User
    Join Date
    Oct 2013
    Posts
    75
    Code:
    char *data;
    Is what I'm initializing data as.

    When say

    Code:
                    fprintf(stderr, "Inserting %c into data.\nData is %s.\n", x, data);
    Its correct in what is BEING ENTERED, but when data is printed out its just garbage.

    Dynamic List Char Array & Double Linked List-untitled-png

  12. #12
    Hurry Slowly vart's Avatar
    Join Date
    Oct 2006
    Location
    Rishon LeZion, Israel
    Posts
    6,793
    in C you cannot concatenate strings using +=

    Your data is uninitialized pointer which is moved by some number of addresses returned by your function (from random location).

    So resulting pointer points to some random garbage
    All problems in computer science can be solved by another level of indirection,
    except for the problem of too many layers of indirection.
    David J. Wheeler

  13. #13
    Registered User
    Join Date
    Oct 2013
    Posts
    75
    How would i go about fixing that? Ive tried strcat but i get errors about making pointer from int.

  14. #14
    Hurry Slowly vart's Avatar
    Join Date
    Oct 2006
    Location
    Rishon LeZion, Israel
    Posts
    6,793
    Show more code - where you initialize the data, what does your ins_dlist function does...

    But mostly - to append one char to string you could do

    Code:
    char str[100] ="Hello, world";
    
    size_t len = strlen(str);
    
    str[len] = '!';
    len++;
    str[len] = 0;
    And since you incremented len - you do not need to call strlen next time...

    But of course you need to check that you do not overrun your array length
    All problems in computer science can be solved by another level of indirection,
    except for the problem of too many layers of indirection.
    David J. Wheeler

  15. #15
    Registered User
    Join Date
    Oct 2013
    Posts
    75
    data is initialized as

    Code:
    char *data;
    my ins_dlist function is

    Code:
    char ins_dlist(char data, struct dlist **p){
            struct dlist *q;
    
            if( (*p)->sz == (*p)->maxsz ){
              q = realloc(*p, DLISTSZ((*p)->maxsz + INCRSZ));
              q->maxsz += INCRSZ;
              *p = q;
            }
    
            fprintf(stderr, "       Now going to copy %c to p->item[%i].\n", data, (*p)->sz);
            (*p)->item[(*p)->sz] = data;
            (*p)->sz++;
            fprintf(stderr, "       Just inserted %c\n", data);
            return(data);
    };
    I am reading in from strings from a file and putting them in a dlist. So would the correct way to do this be to use fgets() to get string from file, then to get strlen(), and use data as an array to build my string? Would i then be able to use those strings to insert into a doubly linked list? And thinking ahead, how would i manage to set a pointer to the start of each of the strings, which would end on the null terminator?

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Which do you prefer, dynamic array or double linked list?
    By ITAmember in forum C Programming
    Replies: 14
    Last Post: 06-03-2009, 01:46 AM
  2. single linked list to double linked list (help)
    By Countfog in forum C Programming
    Replies: 8
    Last Post: 04-29-2008, 08:04 PM
  3. Linked list and dynamic array
    By jk1998 in forum C++ Programming
    Replies: 3
    Last Post: 04-04-2007, 12:03 PM
  4. linked list with char array HELP!
    By littlepiggy in forum C++ Programming
    Replies: 4
    Last Post: 10-18-2005, 02:45 PM
  5. help for linked list(double)
    By Ausandy in forum C Programming
    Replies: 4
    Last Post: 08-19-2002, 03:58 AM