Thread: radix sort strings in c (errors) how to solve?

  1. #1
    Registered User
    Join Date
    Jun 2020
    Posts
    7

    Question radix sort strings in c (errors) how to solve?

    This coding is found on a website. But occuring the errors below:
    [Error] invalid conversion from 'void*' to 'bucket_entry*' [-fpermissive]
    [Error] invalid conversion from 'void*' to 'bucket*' [-fpermissive]

    tried many times already still could not solve.

    Code:
    #include<stdio.h>
    #include<string.h>
    #include<stdlib.h>
    
    struct bucket_entry
    {
        char *str;
        size_t len;
        struct bucket_entry *next;
    };
    typedef struct bucket_entry bucket_entry;
     
    /* A linked list */
    struct bucket
    {
        bucket_entry *head;
        bucket_entry *tail;
    };
    typedef struct bucket bucket;
     
    /* Initialise buckets */
    static void init_buckets(bucket *buckets)
    {
        unsigned int b;
        for (b = 0; b < 256; b++) {
            buckets[b].head = NULL;
            buckets[b].tail = NULL;
        }
    }
     
    /*
     * Turn entries into a linked list of words with their lengths
     * Return the length of the longest word
     */
    static size_t init_entries(char **strings, size_t len, bucket_entry *entries)
    {
        unsigned int s;
        size_t maxlen = 0;
        for (s = 0; s < len; s++) {
            entries[s].str = strings[s];
            entries[s].len = strlen(strings[s]);
            if (entries[s].len > maxlen) {
                maxlen = entries[s].len;
            }
            if (s < len - 1) {
                entries[s].next = &entries[s + 1];
            }
            else {
                entries[s].next = NULL;
            }
        }
        return maxlen;
    }
     
    /* Put strings into buckets according to the character c from the right */
    void bucket_strings(bucket_entry *head, bucket *buckets, unsigned int c)
    {
        bucket_entry *current = head;
        while (current != NULL) {
            bucket_entry * next = current->next;
            current->next = NULL;
            int pos = current->len - 1 - c;
            unsigned char ch;
            if (pos < 0) {
                ch = 0;
            }
            else {
                ch = current->str[pos];
            }
            if (buckets[ch].head == NULL) {
                buckets[ch].head = current;
                buckets[ch].tail = current;
            }
            else {
                buckets[ch].tail->next = current;
                buckets[ch].tail = buckets[ch].tail->next;
            }
            current = next;
        }
    }
     
    /* Merge buckets into a single linked list */
    bucket_entry *merge_buckets(bucket *buckets)
    {
        bucket_entry *head = NULL;
        bucket_entry *tail;
        unsigned int b;
        for (b = 0; b < 256; b++) {
            if (buckets[b].head != NULL) {
                if (head == NULL) {
                    head = buckets[b].head;
                    tail = buckets[b].tail;
                }
                else {
                    tail->next = buckets[b].head;
                    tail = buckets[b].tail;
                }
            }
        }
        return head;
    }
     
    void print_buckets(const bucket *buckets)
    {
        unsigned int b;
        for (b = 0; b < 256; b++) {
            if (buckets[b].head != NULL) {
                const bucket_entry *entry;
                printf("[%d] ", b);
                for (entry = buckets[b].head; entry != NULL; entry = entry->next) {
                    printf("%s", entry->str);
                    if (entry->next) {
                        printf(" -> ");
                    }
                }
                putchar('\n');
            }
        }
        putchar('\n');
    }
     
    void print_list(const bucket_entry *head)
    {
        const bucket_entry *current;
        for (current = head; current != NULL; current = current->next) {
            printf("%s", current->str);
            if (current->next != NULL) {
                printf(" -> ");
            }
        }
        printf("\n");
    }
     
    void copy_list(const bucket_entry *head, char **strings)
    {
        const bucket_entry *current;
        unsigned int s;
        for (current = head, s = 0; current != NULL; current = current->next, s++) {
            strings[s] = current->str;
        }
    }
     
    void radix_sort_string(char **strings, size_t len)
    {
        size_t maxlen;
        unsigned int c;
        bucket_entry *head;
        bucket_entry *entries = malloc(len * sizeof(bucket_entry)8);
        bucket *buckets = malloc(256 * sizeof(bucket));
        if (!entries || !buckets) {
            free(entries);
            free(buckets);
            return;
        }
        init_buckets(buckets);
        maxlen = init_entries(strings, len, entries);
        head = &entries[0];
        /* Main loop */
        for (c = 0; c < maxlen; c++) {
            printf("Bucketing on char %d from the right\n", c);
            bucket_strings(head, buckets, c);
            print_buckets(buckets);
            head = merge_buckets(buckets);
            print_list(head);
            init_buckets(buckets);
        }
        /* Copy back into array */
        copy_list(head, strings);
        free(buckets);
        free(entries);
    
    int main(void)
    {
        char *strings[] = {"The", "quick", "brown", "fox", "jumps", "over", "the", "lazy", "dog"};
        const size_t len = sizeof(strings) / sizeof(char*);
        unsigned int s;
        radix_sort_string(strings, len);
        for (s = 0; s < len; s++) {
            printf("%s\n", strings[s]);
        }
        return 0;
    }

  2. #2
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    27,839
    That error doesn't make sense in C since bucket_entry and bucket are typedefs for struct types, and hence object types, and there is always a valid conversion from void* to a pointer to object type.

    What you could be doing is trying to compile this as C++, and if so, the correct solution is to compile this as C instead.
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  3. #3
    Registered User
    Join Date
    Jun 2020
    Posts
    7
    Thank you for your replied. Is it possible let it work in C programming if change some part of this coding?

  4. #4
    Registered User
    Join Date
    Jun 2020
    Posts
    7
    whats the meaning of [Warning] deprecated conversion from string constant to 'char*' [-Wwrite-strings] ?

    Code:
    #include<stdio.h>
    #include<stdlib.h>
    #include<string.h>
    
    typedef struct list_entry//typedef:replace old data types into new data types
    {
        char *strings;
        size_t len;//represent size of variable in bytes,
                   //big enough to represent size of biggest object that system can handle
        list_entry *next;
    }list_entry;
    
    typedef struct list
    {
        list_entry *head;
        list_entry *tail;
    }list;
    
    /*static*/ void initiate(list *lists) //static: if restrict access, then make static, eg: no other file can access this function except file is declared
    {
        unsigned int n;//unsigned: no negative number (in ASCII table)
        
        for (n = 0; n < 256; n++)//256 represent all characters in ASCII tables
        {
            lists[n].head = NULL;
            lists[n].tail = NULL;
        }
    }
    
    /*static*/ size_t init_entries(char **strings, size_t len, list_entry *entries)//double pointer, address of strings
    {
        unsigned int i;//unsigned: no negative number (in ASCII table)
        size_t maxlen = 0;//initialize max length as 0
        
        for (i = 0; i < len; i++)//looping
        {
            entries[i].strings = strings[i];
            entries[i].len = strlen(strings[i]);//size of string [strlen()]
            if (entries[i].len > maxlen)//if entries length more than max length
            {
                maxlen = entries[i].len;//curr max length will replace by curr entries length
            }
            if (i < len - 1)// assume i=0 and len=8, 0<7
            {
                entries[i].next = &entries[i + 1];//0 linked list add next will be 1 linked list add
            }
            else//if > 7,[8],
            {
                entries[i].next = NULL;//8 linked list add will be NULL, cause only total 8 elements
            }
        }
        return maxlen;// for 1st if statement, if didn't match, then max len will not be replaced, and return the original max
    }
    
    void list_strings(list_entry *head, list *lists, unsigned int c)
    {
        int position;
        unsigned char a;
        list_entry *curr = head;
        
        while (curr != NULL)//if current is not equal to NULL
        {
            list_entry * next = curr->next;
            curr->next = NULL;
            position = curr -> len - c;
            if (position < 0) 
            {
                a = 0;
            }
            else
            {
                a = curr->strings[position];
            }
            if (lists[a].head == NULL)
            {
                lists[a].head = curr;
                lists[a].tail = curr;
            }
            else
            {
                lists[a].tail->next = curr;
                lists[a].tail = lists[a].tail->next;
            }
            curr = next;
        }
    }
    
    list_entry *merge_lists(list *lists)
    {
        list_entry *head = NULL;
        list_entry *tail;
        unsigned int n;
        for (n=0; n<256; n++)
        {
            if (lists[n].head != NULL)
            {
                if (head == NULL)
                {
                    head = lists[n].head;
                    tail = lists[n].tail;
                }
                else
                {
                    tail->next = lists[n].head;
                    tail = lists[n].tail;
                }
            }
        }
        return head;
    }
     
    void print_list(const list_entry *head)
    {
        const list_entry *current;
        for (current = head; current != NULL; current = current->next)
        {
            printf("%s", current->strings);
            if (current->next != NULL)
            {
                printf("\t");
            }
        }
        printf("\n\n");
    }
     
    void copy_list(const list_entry *head, char **strings)
    {
        const list_entry *current;
        unsigned int s;
        for (current = head, s = 0; current != NULL; current = current->next, s++)
        {
            strings[s] = current->strings;
        }
    }
     
    void radix_sort_string(char **strings, size_t len)
    {
        size_t maxlen;
        unsigned int c;
        list_entry *head;
        list_entry *entries = (list_entry*)malloc(sizeof(list_entry) * len);
        list *lists = (list*)malloc(sizeof(list) * 256);
        if (!entries || !lists)
        {
            free(entries);
            free(lists);
            return;
        }
        initiate(lists);
        maxlen = init_entries(strings, len, entries);
        head = &entries[0];
        
        for (c = 1; c <= maxlen; c++)
        {
            printf("Sorting on char %d from the right:\n", c);
            list_strings(head, lists, c);
            head = merge_lists(lists);
            print_list(head);
            initiate(lists);
        }
        copy_list(head, strings);
        free(lists);
        free(entries);
    }
    
    int main()
    {    
        char *strings[]={"kitten","puppy","sheep","birds","mouse","snake","ants"};
        const size_t len = sizeof(strings) / sizeof(char*);
        size_t maxlen;
        
        radix_sort_string(strings, len);
        return 0;
    }

  5. #5
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    38,111
    > Is it possible let it work in C programming if change some part of this coding?
    Normally, you rename your prog.cpp file to be prog.c
    Then the compiler will automatically know it's a C program.

    Then you can get rid of the casts on your malloc return values.

    > whats the meaning of [Warning] deprecated conversion from string constant to 'char*' [-Wwrite-strings] ?
    Then change to this
    const char *strings[]=...

    and propagate the const-correctness through all your functions and other pointers.
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.

  6. #6
    Registered User
    Join Date
    Jun 2020
    Posts
    7
    Thank you !

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Radix Sort ( + counting sort) does not stable sort.
    By siepet in forum C Programming
    Replies: 6
    Last Post: 11-26-2013, 12:04 PM
  2. radix sort
    By rcgldr in forum C Programming
    Replies: 9
    Last Post: 08-20-2013, 05:44 PM
  3. radix sort and radix exchange sort.
    By whatman in forum C Programming
    Replies: 1
    Last Post: 07-31-2003, 12:24 PM
  4. Radix Sort, Strings, and Linked Lists
    By dark paladin in forum C++ Programming
    Replies: 2
    Last Post: 04-24-2003, 03:24 PM
  5. Radix Sort
    By Trauts in forum C++ Programming
    Replies: 15
    Last Post: 03-06-2003, 04:46 PM

Tags for this Thread