10
\$\begingroup\$

I am a new programmer and I want to know if I'm inheriting the right styles. I don't want to pick up any bad/amateur habits. Any advice would be much appreciated.

This is an isUnique function I wrote in C.

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

int main()
{   
    int x;
    char s1[] = "dog hi cobe!";
    x = isUnique(s1);
    printf("%d", x);
    return 0;
}

isUnique(char* s1)
{
    char holder;
    int i;
    int j;

    if(s1 == NULL)
        return -1;

    for(i = 0; i < (strlen(s1) -1); i++)
    {
        holder = s1[i];
        for(j = i; j < (strlen(s1)-1); j++)
        {
            if(holder == s1[j+1])
            {
                if(holder == ' ')
                    continue;
                else
                    return 0;
            }
        }
    }
    return 1;
}

And I'm going to say the run time complexity is \$O(n^2)\$, would I be correct?

\$\endgroup\$
0

3 Answers 3

10
\$\begingroup\$

Missing return type

This function declaration is missing the return type:

isUnique(char* s1)

Sure, the default return type is int in C, but it would be better to just write it anyway for clarity.

Use boolean

C99 has a bool type with true and false values, which you can get from this #include:

#include <stdbool.h>

It would be better to rewrite isUnique to return a bool. Even though, this will mean giving up the special value -1 for the NULL input case. But that doesn't seem so bad. A name like "is*" is commonly expected to return a boolean. If you really need a function that can handle the NULL case, you could create a wrapper function:

/* returns -1 on NULL input, 0 if not unique, 1 if unique */
int checkUnique(char* s1) {
    if (s1 == NULL) return -1;
    return isUnique(s1);
}

Note that the bool return value of isUnique will be converted to int, so that false is 0 and true is 1.

Avoid repeated calculations

You call strlen(s1) twice:

for(i = 0; i < (strlen(s1) -1); i++)
{
    holder = s1[i];
    for(j = i; j < (strlen(s1)-1); j++)

It would be better to call it once, store in a variable and reuse.

Time complexity

As you suspected, the time complexity of your algorithm is \$O(n^2)\$: all characters are compared with all other.

You could improve that to \$O(n)\$ by using extra storage, the size of the alphabet. You could create an array of bool, representing if a character was already seen or not:

  • All values are initialized to false
  • For character in the input, check if it was seen
    • If it was seen, return false
    • If it was not seen, mark it now (set value in the bool array to true)
  • If the end of the string is reached, return true

Something like this:

bool isUnique(char * string) {
    int len = strlen(string);

    bool seen[256];
    memset(seen, false, sizeof(seen));

    int i;
    for (i = 0; i < len; i++) {
        char c = string[i];
        if (seen[c]) {
            return false;
        }
        seen[c] = true;
    }
    return true;
}

Printing the result

This will print a 0 or 1:

int x;
char s1[] = "dog hi cobe!";
x = isUnique(s1);
printf("%d", x);

It would be more informative to print the strings that was tested, and "false"/"true" instead of 0/1:

char s1[] = "dog hi cobe!";
printf("%s -> %s\n", s1, isUnique(s1) ? "true" : "false");

Usability

It would be more interesting if the program took the strings from the command line, instead of using hardcoded values, for example:

void printWithResult(char* string) {
    printf("%s -> %s\n", string, isUnique(string) ? "true" : "false");
}

int main(int argc, char ** argv) {   
    int i;
    for (i = 1; i < argc; i++) {
        printWithResult(argv[i]);
    }
}
\$\endgroup\$
4
  • \$\begingroup\$ Wow! I learned so much through that! Thank you so much!! \$\endgroup\$
    – user85591
    Dec 28, 2015 at 19:06
  • \$\begingroup\$ Also, I'm don't quite understand the time complexity reduction method you described. Can you please give me further clarification/example? \$\endgroup\$
    – user85591
    Dec 28, 2015 at 19:27
  • \$\begingroup\$ Lastly, to pass in the arguments from the command line, why are we also creating an int parameter and why is the second parameter a double pointer rather than a single pointer? \$\endgroup\$
    – user85591
    Dec 28, 2015 at 19:30
  • 1
    \$\begingroup\$ I added an example implementation of an \$O(n)\$ algorithm. As for the int main(int argc, char ** argv) signature, that's standard, you can learn about it in any C tutorial about command line argument parsing \$\endgroup\$
    – janos
    Dec 28, 2015 at 19:40
5
\$\begingroup\$

The combination of conditions

        if(holder == s1[j+1])
        {
            if(holder == ' ')
                continue;

makes the whole inner loop void if holder == ' ', so you may save scanning the string much earlier:

for(i = 0; i < (strlen(s1) -1); i++)
{
    holder = s1[i];
    if(holder == ' ')
        continue;
    for(j = i; j < (strlen(s1)-1); j++)
    {
        if(holder == s1[j+1])
        {
            return 0;
        }
    }
}

Additionally you can simplify the code a bit if you start the j loop one char ahead:

int len = strlen(s1);
for(i = 0; i < len-1; i++)
{
    holder = s1[i];
    if(holder == ' ')
        continue;
    for(j = i+1; j < len; j++)
    {
        if(holder == s1[j])
        {
            return 0;
        }
    }
}

For such a relatvely small symbol set (256 possible values of char type, max 255 of which can appear in the string) you can just arrange an array of counters:

int counter[256];

reset it to zeros:

for(i = 0; i < 256; i++)
    counter[i] = 0;

or, based on the known array of int memory layout:

memset(counter, 0, 256*sizeof(int));

and count occurences of each character (up to two)

for(i = 0; i < strlen(s1); i++)
{
    if(s1[i] != ' ')
        if(++counter[(unsigned char)s1[i]] > 1)
        {
            return 0;
        }
}
return 1;

This will test your string in linear time (plus constant time for preparing counter[] array).

\$\endgroup\$
2
  • \$\begingroup\$ by using the keyword "continue" does that make the program skip the rest of the block of code in that loop(i.e. the inner for loop)? \$\endgroup\$
    – user85591
    Dec 28, 2015 at 19:17
  • \$\begingroup\$ Yes, it forces the re-iteration of a loop. More precisely, if the body of a loop is a compound statement, that is a block enclosed in { } braces, then the continue instruction behaves as a goto to the closing brace. If the loop body is not a block, continue passes the control to evaluation of the loop controlling expression in a while loop or to the third expression in a for loop. \$\endgroup\$
    – CiaPan
    Dec 28, 2015 at 23:13
1
\$\begingroup\$

When compiling, always enable all the warnings.

(for gcc, at a minimum use: -Wall -Wextra -pedantic I also use -Wconversion -std=c99 )

the result will be:

  1. implicit declaration of function: isUnique
  2. return type defaults to 'int' for function: isUnique
  3. comparison between signed and unsigned integer expressions for line: for(i = 0; i < (strlen(s1) -1); i++)
  4. comparison between signed and unsigned integer expressions for line: for(j = i; j < (strlen(s1)-1); j++).
  5. Note: strlen() returns size_t not int
  6. there is no need to call strlen() at all! instead use something like: for(j = i; s1[j]; j++) which will exit the loop upon encountering the NUL string terminator byte.
  7. when possible, data/variables should be localized to where they are used. so these lines can be eliminated: int i; int j; by writing the loop similar to: for(size_t j = i; s1[j]; j++)
  8. there is no need for the char holder; line.
  9. the 'j' variable is being started with j = i is should be j = i+1
  10. Stopping the search because a space is encountered is not correct.
  11. do not #include headers those contents are not being used.
  12. use strategic comments so the reader, (and you in 6 months) will know what is being done in the code
  13. always use function prototypes so the compiler will not be using some 'default' values/types (and in latest C standard, the defaults are changed thereby causing the compiler to raise warnings)

Here is a suggested implementation

#include <stdio.h>

// prototypes
int isUnique(char* s1);

int main( void )
{
    int x;
    char *s1 = "dog hi cobe!";
    x = isUnique(s1);
    printf("%d", x);
    return 0;
} // end function: main

int isUnique(char* s1)
{

    if( !s1 )
    { 
        // indicate no string passed
        return -1;
    }

    for( size_t i = 0; s1[i]; i++ )
    {
        for( size_t j = i+1; s1[j]; j++ )
        {
            if( s1[i] == s1[j] )
            { 
                // indicate characters are not unique
                return 0;
            }
        }
    }
    // indicate characters are unique
    return 1;
} // end function: isUnique
\$\endgroup\$
3
  • \$\begingroup\$ Thank you for all those helpful suggestions! I had one quick question. For your 6th suggestion, how exactly is the for loop behaving by writing s1[j] as the second parameter into the for loop? I am asking this for references (b/c I do not see a conditional statement). What exactly would is the implicit condition stated there? \$\endgroup\$
    – user85591
    Dec 31, 2015 at 1:28
  • 1
    \$\begingroup\$ the second parameter of a for() statement only looks at the result as being 'true' (non zero) or 'false' (zero) so the 's1[j]' (and 's1[j]) is looking at the byte selected by the parameter: 's1[i]'. If that byte contains '\0' then the condition is 'false' otherwise it is 'true'. when the 'condition' is 'false', then the loop exits. \$\endgroup\$ Dec 31, 2015 at 8:03
  • 1
    \$\begingroup\$ here is a quick summary of the syntax for the for(expresion1; expression2; expression3) statement: expression1 - Initialisese variables. expression2 - Condtional expression, as long as this condition is true, loop will keep executing. expression3 - expression3 is the modifier which may be simple increment of a variable. \$\endgroup\$ Dec 31, 2015 at 8:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.