Thread: Insert value into array

  1. #1
    C noobie
    Join Date
    Jun 2006
    Location
    MI
    Posts
    25

    Insert value into array

    I was curious what the most effective way was for inserting a value into an array. I literally mean inserting a value into an array, as in between two values, not just replacing an item at a specific index. Example,

    psuedoish code,
    Code:
    example[4] = {1,2,3,4};
    insert(9,2,example);
    example[4] == {1,2,9,3};

    I need to insert several large strings into an array several thousand characters long. (similar to how a text editor would do it)
    Last edited by Salgat; 02-26-2009 at 08:22 PM.

  2. #2
    Registered User
    Join Date
    Oct 2008
    Location
    TX
    Posts
    2,059
    Do the characters that cannot fit inside the array simply fall off the right end? At least that's what I got out of your example.

  3. #3
    C noobie
    Join Date
    Jun 2006
    Location
    MI
    Posts
    25
    Yes.

  4. #4
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,336
    That means you need to start at the right, replacing element n by element n-1, going back until you reach the insertion point.

  5. #5
    Registered User
    Join Date
    Sep 2006
    Posts
    8,868
    For small strings you can "worm" the char's over, index by index, from right to left, and that's ok.

    But that's also inefficient - much like bubblesort, actually. Because the char's may need to move many spaces over to the right, and a naive algorithm will really slow things down.

    A better algorithm would be:

    get the length of the string to be added, a[1], make that length1.

    get the length of the string (the char array) that's to be adjusted (a2[]), and make that length2

    Now choose the index that is length2 - length1. Start there, and move that char in a2[] to a2[length2-1].

    Continue moving char's until the index = (length2 - length1) - length1. That is, if a1[] is 100 char's long, and a2[] = 1,000 char's in length, then you want to start at index 1,000 , and continue until you get to index 900. (Just remember to -1 from these index numbers for zero based arrays)

    This is a naive implementation. If you run it step by step, you'll see that the char's are moved over and over again. The move itself is fast, but with a long string, I'd use the better algorithm described above. I don't have an example of it to show.

    Code:
    /*edit_str.c Overwrites or inserts a string into an array of char, Adak
    Status: ok
    */
    
    #include <stdio.h>
    #include <string.h>
    
    int insert(void);
    int overwrite(void);
    
    char a1[] = { "When you spit, upon a star" }; //apologies to Disney :)
    char a2[] = { "you wish," };
    char a3[] = {"Now is the time for all good men to come to the aid of their country."}; 
    char a4[] = {" and wise"};  
    
    int main(void)  {
       overwrite();
       insert();
       return 0;
    }
    
    int insert(void) {
       int i, j, left, right, length3, length4;
       length3 = strlen(a3);
       length4 = strlen(a4);
    
       left = 27;  //where I want to insert the a2 string
       for(j = length4 - 1; j > -1; j--)  {
          for(i = length3 - 2; i > left; i--)  {
             a3[i+1] = a3[i];
             if(i < 0 || i > length3-1)
                return 1;
          }                  //the a4 string is fed into a3, from right to 
          ++i;               //left. Each inserted char is then moved to the
          a3[i] = a4[j];     //right in a3, appropriately.
          if(j < 0 || j > length4-1)
             return 1;
       }
       printf("%s\n", a3);
      
       i = getchar();
       return 0;
    }
    int overwrite(void) {
       int i, j, left, right, length1;
    
       left = 5;
       right = strlen(a2);
       length1 = strlen(a1);
    
       for(i = left, j = 0; j < right; i++)  {
          a1[i] = a2[j++];
          if(i > length1-1)
             return 1;
       }
       printf("%s\n", a1);
       i = getchar();
       
       return 0;
    }

  6. #6
    Registered User
    Join Date
    Sep 2007
    Posts
    1,012
    If this is truly the best way to approach your problem, I'd think that memmove() + memcpy() would be the solution (assuming I didn't make a mistake here):
    Code:
    #include <stdio.h>
    #include <string.h>
    #include <assert.h>
    
    static void insert(const char *to_insert, char *string, size_t offset)
    {
      size_t slen = strlen(string);
      size_t ilen = strlen(to_insert);
    
      assert(ilen + offset <= slen);
    
      memmove(&string[offset + ilen], &string[offset], slen - ilen - offset);
      memcpy(&string[offset], to_insert, ilen);
    }
    
    int main(void)
    {
      char s[] = "string for replacement";
    
      insert("is ", s, 7);
    
      puts(s);
    
      return 0;
    }

  7. #7
    Registered User
    Join Date
    Oct 2008
    Location
    TX
    Posts
    2,059
    Before writing code what have you tried as far as designing the algorithm is concerned.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Code: An auto expanding array (or how to use gets() safely).
    By anonytmouse in forum Windows Programming
    Replies: 0
    Last Post: 08-10-2004, 12:13 AM
  2. insert a value into an array! Help
    By letdoit in forum C++ Programming
    Replies: 3
    Last Post: 05-29-2004, 09:41 PM
  3. Merge sort please
    By vasanth in forum C Programming
    Replies: 2
    Last Post: 11-09-2003, 12:09 PM
  4. insert an element i array
    By planet_abhi in forum C Programming
    Replies: 6
    Last Post: 02-22-2003, 07:04 PM
  5. Creating 2D arrays on heap
    By sundeeptuteja in forum C++ Programming
    Replies: 6
    Last Post: 08-16-2002, 11:44 AM