Basic C Question

[Cethin]

I'm fairly new to programming, so this is a fairly simple problem. Writing a function that takes two strings, and removes all the letters in one that match the other (ex: 'testing' and 'test', resulting string would be 'ing').

I have written it so it works, but I was wondering if anyone had advice on how to make it more efficient, or perhaps (I'm sure there is) a way to make it better.

Here is the code:

Code: Select all

void squeeze(char s[], char d[])
{
   int x, y;
   for (x = 0; x < 100; ++x)                   /*100 is the size of my arrays*/
      for (y = 0; y < 100; ++y)           /*this sets every matching letter in the*/
         if (s[x] == d[y])                /*first string to '  ' which i remove later*/
            s[x] = ' ';
   
   char f[100];
   int m = 0;
   for (x = 0; x < 100; ++x)                  /*this part of the code goes through*/
      f[x] = s[x];                             /*and removes all the ' ' chars*/
   for (x = 0; x < 100; ++x)
      if (f[x] != ' ')
         s[m++] = f[x];
   
   s[m] = '\0';
}


Thank you in advance for taking the time to read this.

[Arameus]

Use typecasting on the characters to compare them to something you know you'll never encounter in a string. Your current setup removes spaces from the string even if they are supposed to be there. Try something like this:

Code: Select all

void remove(char *string, char remove) {
void squeeze(char s[], char d[])
{
   int x, y;
   for (x = 0; x < 100; ++x)                   /*100 is the size of my arrays*/
      for (y = 0; y < 100; ++y)           /*this sets every matching letter in the*/
         if (s[x] == d[y])                /*first string to '  ' which i remove later*/
            (int)s[x] = -1;
   
   char f[100];
   int m = 0;
   for (x = 0; x < 100; ++x)                  /*this part of the code goes through*/
      f[x] = s[x];                             /*and removes all the ' ' chars*/
   for (x = 0; x < 100; ++x)
      if ((int)f[x] != -1)
         s[m++] = f[x];
   
   s[m] = '\0';
}

[thetan]

You algolrithm at the moment is always O(10,200), which is to say for every call it has to perform 10,200 iterations, with 10,000 comparison operations and 100 assignments and an additional 100 comparisons.

You can instead write this algorithm much cleaner and have it be O(n*k) where n is the length of the string and k is the length of the exclusion list.

I'd write it like this:

Code: Select all

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

void squeeze(char *s, int s_size, char *e, int e_size)
{
  int i, j, gap = 0;

  // itterate over all characters in the string
  for (i = 0; i < s_size; i++)
  {
    // for each character, compare it against
    // all characters in the exclusion string.
    for (j = 0; j < e_size; j++)
    {
      // if the current char of the string
      // matches the current char of the exclusion
      // list then we widen the gap set and goto
      // the end of the upper loop.
      if (s[i] == e[j])
      {
   gap++;
   goto skip_char;
      }
    }

    // if this section of code is being executed it means
    // that the current charecter was not in the exclusion list
    // so we throw it over the gap and keep it.

    s[i - gap] = s[i];

    skip_char:
    continue;
  }

  // chop off chars dangling off the edge
  s[s_size - gap] = '\0';
}

int main(int argc, char **argv)
{
  char str[] = "this is a super awesome string";
  int s_len = 30;
  char exc[] = "aeiou";
  int e_len = 5;

  printf("String before: %s\n", str);
  squeeze(str, s_len, exc, e_len);
  printf("String after: %s\n", str);

  return 0;
}


http://codepad.org/vSs4pNK5

[Cethin]

Thetan, thank you for that code example. I learned some things from it, however I have not yet learned anything about pointers, so I'll have to go read up on those and come back to that.

Arameus, thank you for pointing that out, I hadn't thought of that. I was using a blank because I wasn't allowed to use ''. For example, this following line would give me an error:

Code: Select all

char s[x] = '';


Why is that? And also, is there a way to set an array element to nothing like that?

[thetan]

a pointer is the same thing as an array.

Notice how the strings in my function are passed in as pointers (as is the standard paradigm in C) while the elements in the pointer get used via array syntax.

for instance:
char *ptr = "some string";
char arr[] = "some string";

to the compiler they are the same exact thing from a data access perspective. The main difference being that one is allocated on the local scopes stack while the other is in immutable memory.

[Arameus]

a pointer is the same thing as an array.

Notice how the strings in my function are passed in as pointers (as is the standard paradigm in C) while the elements in the pointer get used via array syntax.

for instance:
char *ptr = "some string";
char arr[] = "some string";

to the compiler they are the same exact thing from a data access perspective. The main difference being that one is allocated on the local scopes stack while the other is in immutable memory.

Pointers and arrays are not the same. Arrays are sections of contiguous memory which can be accessed via a pointer to the first spot in the section. While pointers can point to such spots, they don't always.

Code: Select all

//this pointer points to an array of pointers that point to arrays of chars
char **words;
//this pointer points to an int
int *hithere;
//this declares and allocates an array of 10 chars
char *array = malloc(sizeof(char) * 10);


[Goatboy]

/me prepares for an epic technicality-down

[Reason7194]

Arameus, thank you for pointing that out

Did he mean to do that? In any case it made giggle.

[thetan]

Phone post so i apologize for typos in advance.

Pointer and arrays are the same thing from a data access point of view. the only way in which a pointer and an array vary is the memory allocation scheme which I alluded to in my previous post with the mention of one allocating space on the stack and the other in immutable memory.

Saying that a pointer simply references a point in memory and an array references a segment of continuos memory is saying the same thing in terms of c implementations. All memory is Contigous in each given section. Or seemingly continuos while sparse in reality thanks to super awesome virtual memory implementations in use by all major operating systems.

arrays are references to points in memory just as pointers are the same. Square bracket element access for referencing elements In arrays are syntactic sugar for pointer arithmetic.

C enforces no bounds checking on arrays because to the compiler once the memory has been allocated on the stack or the heap all that's left is a pointer to the beginning of that chunk of memory. This is why things like buffer overflows exist.

I'll be offline starting today till monday, taking a mini vacation to take my kids to Disney land

[tgoe]

This can be done better with some hashing. Take advantage of the fact that each character is already represented by a unique number and you can simulate an associative array with an array of integers large enough to contain all values. The integer representation corresponds with the index value (the "key"). Something like this:

Code: Select all

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

char * squeeze(char s[], int len, int t[]) {
    int i;
    char *squeezed = s;

    for(i = 0; i < len; i++) {
        if(t[(int)s[i]] != 1) { // If the char isn't marked in the table, copy
            *squeezed++ = s[i];
        }
    }

    *squeezed = '\0';

    return s;
}

int main(int argc, char *argv[]) {
    int table[128] = { 0 }; // ASCII table, all initialized to 0 (unmarked)
    char *squeezed;
    int len;
    int i;

    if(argc != 3) {
        printf("%s \"Characters to filter out\" \"The string\"\n", argv[0]);
        exit(0);
    }

    len = strlen(argv[1]);
    for(i = 0; i < len; i++) {
        table[(int)argv[1][i]] = 1; // Mark each filter char in the table
    }

    printf("before: %s\n", argv[2]);
    squeezed = squeeze(argv[2], strlen(argv[2]), table);
    printf("after: %s\n", squeezed);

    return 0;
}