Thread: Storing unknown array

  1. #1
    Registered User
    Join Date
    Aug 2011
    Posts
    102

    Storing unknown array

    I know how to store arrays that was initially initialize with a certain size. But what if, the size of an array is in unknown status and i wanted to store in it. The array should automatically end when "-1" is inserted into array. For this, we cant predict how much is the size of the array. So, how do u store in it?

  2. #2
    Registered User
    Join Date
    Oct 2011
    Location
    Denmark
    Posts
    80
    If you want to have something dynamic, I would suggest using a linked list.

  3. #3
    Registered User
    Join Date
    Sep 2011
    Location
    Stockholm, Sweden
    Posts
    131
    You must know the size of your array. You don't necessarily have to know how large it is going to be at compile time, it can be allocated and resized dynamically at run time using malloc/realloc, but you have to keep track of its size to avoid using memory that isn't "yours".

  4. #4
    Banned
    Join Date
    Aug 2010
    Location
    Ontario Canada
    Posts
    9,547
    Quote Originally Posted by Tibo-88 View Post
    If you want to have something dynamic, I would suggest using a linked list.
    And, in that case, how would he know the size of his linked list?

    Sorry... but that doesn't solve the problem it only makes his code more complex.

  5. #5
    Registered User
    Join Date
    Aug 2011
    Posts
    102
    thanks guy. I think my lecturer wanted something called list. Therefore, i will learn this and i will be back if problem insist. Ty

  6. #6
    Registered User
    Join Date
    Aug 2011
    Posts
    102
    he want something int r----e--a-d-I-------n-----t-o-------A--r----r---a--y-( ---i--n---t-[-----]- -l--i---s-t-)-;-

    please do remove "-". thanks. I put it bcause i dont want this to be in Google

  7. #7
    Registered User
    Join Date
    Oct 2011
    Location
    Denmark
    Posts
    80
    Quote Originally Posted by CommonTater View Post
    And, in that case, how would he know the size of his linked list?

    Sorry... but that doesn't solve the problem it only makes his code more complex.
    Well maybe I misunderstood the question, but if you want to have a dynamic array I still think a linked list is a good solution, or at least I find it more beautiful than using realloc.
    And knowing the size of a linked list is not a tedious task, you can create a structure for your list that will keep trace of the size, or just implement a simple function that will iterate through the elements and return the size.
    But again maybe i misunderstood!

  8. #8
    Banned
    Join Date
    Aug 2010
    Location
    Ontario Canada
    Posts
    9,547
    Quote Originally Posted by ncode View Post
    I know how to store arrays that was initially initialize with a certain size. But what if, the size of an array is in unknown status and i wanted to store in it. The array should automatically end when "-1" is inserted into array. For this, we cant predict how much is the size of the array. So, how do u store in it?
    There's an example file loader in this thread that could be adapted to your purposes.

    However... in your place I'd want to clarify with my teacher whether you are to use an array or a linked list before writing much code. It would suck to do something really clever then find out it's not what the guy wants.

  9. #9
    Banned
    Join Date
    Aug 2010
    Location
    Ontario Canada
    Posts
    9,547
    Quote Originally Posted by Tibo-88 View Post
    Well maybe I misunderstood the question, but if you want to have a dynamic array I still think a linked list is a good solution, or at least I find it more beautiful than using realloc.
    And knowing the size of a linked list is not a tedious task, you can create a structure for your list that will keep trace of the size, or just implement a simple function that will iterate through the elements and return the size.
    But again maybe i misunderstood!
    Yes a linked list is a good solution but somewhat inefficient when storing single values, such as ints or floats. There it's usually a lot more effective to use malloc() and realloc() and have a single array in memory. Linked lists are structs with pointers, so you have the overhead of all those pointers to consider... on a 32 bit system, storing only a single int, the array method would be half the size of a linked list.

    The line gets crossed when you are storing larger amounts of information (eg. name adderess and phone number) then a linked list makes sense, up to a certain point.

    Another line gets crossed when the list becomes significantly large (more than a few hundred entries)... Since linked lists can only be searched linearly (i.e. by looking at every entry in turn until the item is found) the bigger the list the slower and less efficient your search algorythms become. So, when the search time becomes significant, you should implement a means to use more efficient search algorythms such as the binary search with relies upon a sorted array (or sorted disk file) for it's speed... In that case, a dynamically sized array of pointers to your data structs starts making more sense.

    With apologies to the OP for complicating this, I do hope that is of some help....

  10. #10
    Registered User
    Join Date
    Oct 2011
    Location
    Denmark
    Posts
    80
    Quote Originally Posted by CommonTater View Post
    Yes a linked list is a good solution but somewhat inefficient when storing single values, such as ints or floats. There it's usually a lot more effective to use malloc() and realloc() and have a single array in memory. Linked lists are structs with pointers, so you have the overhead of all those pointers to consider... on a 32 bit system, storing only a single int, the array method would be half the size of a linked list.

    The line gets crossed when you are storing larger amounts of information (eg. name adderess and phone number) then a linked list makes sense, up to a certain point.

    Another line gets crossed when the list becomes significantly large (more than a few hundred entries)... Since linked lists can only be searched linearly (i.e. by looking at every entry in turn until the item is found) the bigger the list the slower and less efficient your search algorythms become. So, when the search time becomes significant, you should implement a means to use more efficient search algorythms such as the binary search with relies upon a sorted array (or sorted disk file) for it's speed... In that case, a dynamically sized array of pointers to your data structs starts making more sense.

    With apologies to the OP for complicating this, I do hope that is of some help....
    Totally agree with what you say! If i could just add another comment without trolling too much, the linked list has also the advantage of allowing you to remove an element really easily, while it is more complicated when using the realloc method.

    Hope I'm not disturbing too much this post!

  11. #11
    Banned
    Join Date
    Aug 2010
    Location
    Ontario Canada
    Posts
    9,547
    Quote Originally Posted by Tibo-88 View Post
    Totally agree with what you say! If i could just add another comment without trolling too much, the linked list has also the advantage of allowing you to remove an element really easily, while it is more complicated when using the realloc method.

    Hope I'm not disturbing too much this post!
    I'm sure it's fine (the mods will tell us if it's not) and I certainly wouldn't consider a good point to be trolling.

    Yes, within the useful bounds of linked lists, deletions are a lot easier.
    With an array you end up moving the rest of the array forward which is not always an easy task.

    (Sidebar: If you want a real pain sometime, try deleting a single record from a "random access" file... oi vey!)

  12. #12
    Registered User
    Join Date
    Aug 2011
    Posts
    102
    Linked list is not something covered in my current semester. Therefore, how do i do it? I try do....while, but it end up with error since the size of array is not initialize and there's no element in it! so what can i do?
    Code:
    #include<stdio.h>
    
    int main(void){
    	int arry[];
    	int count=0;
    do{
    	printf("Input value:");
    	scanf("%d", arry[count]);
    	count++;	
    }while(array[count]!=0);
    
    }

  13. #13
    Registered User
    Join Date
    Sep 2011
    Location
    Stockholm, Sweden
    Posts
    131
    A linked list cannot be represented by an array like you are trying to do, it is a different data structure. In the simplest form it is a structure containing a value and a pointer to the next element in the list. i.e.
    Code:
    struct node {
        int value;
        struct node *next;
    };
    Here is a link to a tutorial on this site.

  14. #14
    Banned
    Join Date
    Aug 2010
    Location
    Ontario Canada
    Posts
    9,547
    To make the array resizeable, you need to create it using malloc()...
    Code:
    #include<stdio.h>
    
    #define ASIZE 100
    
    int main(void)
      {
        int *arry = malloc(ASIZE * sizeof(int)); 
        int count=0;
        do
          {
            printf("Input value:");
            scanf("%d", &arry[count]);
            count++;	
          }
        while(arry[count]!=0);
     
       return 0;
    }
    You can treat this just like any other array, using indexing or pointers... it's just that it's created on the program's memory Heap rather than on it's Stack.

    Now you have some choices...
    If you are certain you will not exceed ASIZE in the example above, you're all done...

    If the operator will know the size you can ask...

    Code:
    #include<stdio.h>
    
    int main(void)
      {
        int *arry;
        int size;
        int count=0;
        
        printf("How many entries?  : ");
        scanf("%d", &size); 
        
        arry = malloc(size * sizeof(int)); 
    
        do
          {
            printf("Input value:");
            scanf("%d", &arry[count]);
            count++;	
          }
        while(arry[count]!=0);
     
       return 0;
    }
    or if the array is of a totally unknown size at runtime...

    Code:
    #include<stdio.h>
    
    #define ASIZE 10
    
    int main(void)
      {
        int *arry = malloc(ASIZE * sizeof(int)); 
        int count = 0;
        int size = ASIZE;
    
        do
          {
            printf("Input value:");
            scanf("%d", &arry[count]);
            count++;	
    
            // resize the array
            if (count >= size)
              { 
                 size += ASIZE; 
                 arry = realloc(arry, size * sizeof(int)); 
              }
    
          }
        while(arry[count]!=0);
     
       return 0;
    }
    ... which will automatically increase the size of the array in blocks of ASIZE (10 in the example) as the operator enters new data.


    Now... don't be just copy pasting the examples, you won't learn anything that way (and they are untested)... Get into your C language documentation (compiler's help files) and read up on malloc() and realloc() so you understand what is actually going on.
    Last edited by CommonTater; 11-08-2011 at 08:06 AM.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. inputting unknown array
    By Dr Saucie in forum C Programming
    Replies: 3
    Last Post: 02-08-2010, 01:03 PM
  2. unknown size array
    By archriku in forum C Programming
    Replies: 14
    Last Post: 05-07-2009, 11:29 PM
  3. array of unknown size
    By richdb in forum C Programming
    Replies: 7
    Last Post: 02-25-2006, 11:48 AM
  4. storing an unknown amount of variable
    By sreetvert83 in forum Game Programming
    Replies: 5
    Last Post: 09-17-2005, 05:42 PM
  5. Reading an unknown # of ints into array
    By jds in forum C Programming
    Replies: 3
    Last Post: 10-10-2003, 04:16 PM