sorting input in lexicographical order with dynamic array

Question

I try to write a program which reads in single signs from a keyboard. If they are not already present they should be stored in a array.

After that, all signs get sorted and all already occurring signs are printed.

edit: if the entered sign already exists it is not added. The array should only contain unique elements.

The array starts with a size of 0 and should double its capacity every time it is full when a new character arrives.

Unfortunately it doesn't seem to work correctly. If I look via the debugger it looks like the values get stored one after another, but as soon as the second sign arrives the program crashes in print / qsort.

Am I doing something wrong in the allocation?

Also if you have other recommendations for improve this code please let me know.

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

void reserve_space(char **c, int *capacity);
void print_signs(char **signs, const int max_size);
int cmp(void const *lhs, void const *rhs);

// allocates factor 2 of the current capacity
void reserve_space(char **c, int *capacity) {
    char *new_c;

    if (*capacity == 0) {       // allocate the first time
        *capacity = 1;
        *c = malloc(sizeof(char) * ((*capacity)));
    } else {
        *capacity *= 2;     // double the new capacity
        new_c = realloc(*c, sizeof(char) * (*capacity));
        *c = new_c;
    }
    return;
}

void print_signs(char **signs, const int sz) {
    int i = 0;

    for (i = 0; i < sz; ++i) {
        printf("%i %c\n", *signs[i], *signs[i]);            // crash in read after array has 2 signs???
    }
    printf("\n");
}

int cmp(void const *lhs, void const *rhs) {
    char left = *((char *)lhs);
    char right = *((char *)rhs);

    if (left < right) return -1;
    if (left > right) return  1;

    return 0;  /* left == right */
}

int main() {
    int capacity = 0;       // allocated space 
    int sz = 0;             // space currently "filled" with signs
    char *signs = 0;

    char ch = 0;
    int pos = 0;

    while ((ch = getc(stdin)) != EOF) {
        int pos = 0;

        if (sz == capacity)
            reserve_space(&signs, &capacity);

        for (pos = 0; pos < sz; ++pos) {
            if (signs[pos] == ch)
                continue;   /* indicating element exists already */
        }

        if (pos == capacity - 1)    // -1 because last sign must be terminating '\0'
            reserve_space(&signs, &capacity);

        signs[pos] = ch;    //adding new sign at pos of "old" \0
        ++sz;
        ++pos;
        signs[pos] = '\0';  //adding new terminating \0

        qsort(&signs, sz - 1, sizeof(char), cmp);

        print_signs(&signs, sz);
    }
    getchar();
}

I want to say thank you for actually using a debugger and adding the information you did. You should get a good answer pretty quickly. — Michael Dorgan
– Michael Dorgan, Commented Jun 14, 2018 at 19:52
Quickly - if your size is "1" and you set the \0' to ++sz, you have written to bad memory. You need to track the \0 character in your size for the array. — Michael Dorgan
– Michael Dorgan, Commented Jun 14, 2018 at 19:53
qsort(&signs, sz-1, sizeof(char), cmp); is suspicious, I'd expect qsort(signs, ... — chux
– chux, Commented Jun 14, 2018 at 20:20

chqrlie · Accepted Answer · 2018-06-19 16:42:31Z

3

There is a bug in print_sign: the order of precedence between * and [] is such that *signs[i] is parsed as *(signs[i]) instead of (*signs)[i] as you assume.

Here is a corrected version:

void print_signs(char **signs, const int sz) {
    int i = 0;

    for (i = 0; i < sz; ++i) {
        printf("%i %c\n", (*signs)[i], (*signs)[i]);
    }
    printf("\n");
}

There is actually no reason to pass the address of the pointer to this function. It can be simplified into:

void print_signs(char *signs, const int sz) {
    int i = 0;

    for (i = 0; i < sz; ++i) {
        printf("%i %c\n", signs[i], signs[i]);
    }
    printf("\n");
}

And called as print_signs(signs, sz);

There are many other issues in your code:

ch should be defined as int.

the continue statement in the lookup loop is moot, you should instead write the loop as

for (pos = 0; pos < sz; ++pos) {
    if (signs[pos] != ch)
        break;   /* indicating element exists already */
}
if (pos < sz)
    continue;

there are off by 1 errors in the rest if the main function
the comparison function is broken too.

Here is a corrected version:

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

void reserve_space(char **c, int *capacity);
void print_signs(const char *signs, int max_size);
int cmp(void const *lhs, void const *rhs);

// allocates factor 2 of the current capacity
void reserve_space(char **c, int *capacity) {
    if (*capacity == 0) {   // allocate the first time
        *capacity = 1;
        *c = malloc(sizeof(char) * ((*capacity)));
    } else {
        *capacity *= 2;     // double the new capacity
        *c = realloc(*c, sizeof(char) * (*capacity));
    }
}

void print_signs(const char *signs, int sz) {
    int i = 0;

    for (i = 0; i < sz; ++i) {
        printf("%i %c\n", signs[i], signs[i]);
    }
    printf("\n");
}

int cmp(void const *lhs, void const *rhs) {
    unsigned char left = *(const unsigned char *)lhs;
    unsigned char right = *(const unsigned char *)rhs;

    if (left < right) return -1;
    if (left > right) return  1;
    return 0;  /* left == right */
}

int main() {
    int sz = 0;             // space currently "filled" with signs
    int capacity = 0;       // allocated space 
    char *signs = NULL;
    int ch;

    while ((ch = getc(stdin)) != EOF) {
        int pos = 0;

        for (pos = 0; pos < sz; ++pos) {
            if (signs[pos] == ch)
                break;
        }
        if (pos < sz)
            continue;  // character is already in the array

        if (sz == capacity)
            reserve_space(&signs, &capacity);

        signs[sz] = ch;    // append the sign in the array
        sz++;
        // '\0' terminator is not needed as array is not used as a string
    }
    qsort(signs, sz, sizeof(char), cmp);
    print_signs(signs, sz);
    free(signs);

    getchar();
    return 0;
}

edited Jun 19, 2018 at 16:42

answered Jun 14, 2018 at 20:28

chqrlie

152k12 gold badges145 silver badges231 bronze badges

Sign up to request clarification or add additional context in comments.

5 Comments

Sandro4912 Over a year ago

if the statement gets changed to break it would still add the sign already existing or not? it should be unique. no sign shouldnt be twice. i think i forgot to mention it i will edit the question

Sandro4912 Over a year ago

ok i didnt saw that statement at first. now it makes sense. just one thing shouldnt it be [code] free(size); [/code] ?

chux Over a year ago

Good and correct use of unsigned char and const in const unsigned char * in cmp().

Sandro4912 Over a year ago

unfortunately youre code seems to be still buggy. i tested it with input hello 1234 and terminated with strg + z (windows) to simulate EOF. all it puts is the hello. in the debugger it looks like it only adds the first h.

Sandro4912 Over a year ago

@chqrlie it looks like only the first time it enters the assign with youre logic. I included 'stdbool.h' and changed the logic to bool is_already_in = false;

for (pos = 0; pos < sz; ++pos) { 			if (signs[pos] == ch) { 				is_already_in = true; 				break; 			} 		} 		if (is_already_in) 			continue;  // character is already in the array

Collectives™ on Stack Overflow

sorting input in lexicographical order with dynamic array

1 Answer 1

5 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

5 Comments

Your Answer

Sign up or log in

Post as a guest

Related