2
\$\begingroup\$

I'm relatively new to programming as I've just started university. My assignment was to develop a program (by using a function and a linked list with pointers with integer elements) which does the following:

  • The function visits every element from the beginning. If the current element plus one is <= to the following element (e.g. if the first one is i and the second one is j, j>=i+1), you have to complete the list by adding all the values between i and j-1.
  • If the current element is followed by an element <=, it is to be removed by the list and added to an array declared in the formal parameters. You also have to put in the formal parameters a counter for the deleted elements.

I had already asked a question about this function since I couldn't get it to work, but using recursive functions I finally made it. I would now like to know how I might improve it! Sorry if I made any grammar mistakes, English is not my native language.

I left all the comments I made about how each function works.

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

// list declaration

struct list {
    int value;
    struct list * next_ptr; };

// pre_insert function.

void pre_insert(struct list ** ptrptr, int value) {

    struct list * tmp_ptr;

    tmp_ptr = *ptrptr;
    *ptrptr = malloc(sizeof(struct list));
    (*ptrptr)->value = value;
    (*ptrptr)->next_ptr = tmp_ptr;
}

// if the following item is bigger than the current one, a call to this function inserts all the items missing between the two values.
// the cost of this function is T(N) = c * (N-1) (because of the while loop).

void succ_value_bigger(struct list * ptr) {

    while (ptr->value + 1 < ptr->next_ptr->value)
        pre_insert(&ptr->next_ptr, ptr->next_ptr->value-1);
}

// if succ_value_smaller is called by complete_list_to_array, this function deletes the item following the one pointed by ptr.
// the function has linear cost as there are no iterations.

int delete_element (struct list * succ_ptr, int * V, int k) {

    V[k] = succ_ptr->value;
    free(succ_ptr);

    return k;
}

// if i value is bigger than the following one, complete_list_to_array calls this function.
// the function deletes the following element using a call to delete_element function, then increases both count and k.
// the first one counts the deleted elements, the second one is an index for the array V collecting all the deleted elements.
// the function has a recursive behaviour, calling main function complete_list_to_array for the following element to be confronted with i.
// the function has cost T(N) = c1*N + c2 (since the else guard only works for the last item).

int succ_value_smaller(struct list * ptr, int * V, int * count, int k) {

    struct list *succ_ptr = ptr->next_ptr;

    // the guard sees if the current item isn't the last one. if so, it sends the flow to else, below.
    // if it is not the case, it deletes the following element and increases the indexes.

    if (succ_ptr->next_ptr != NULL)
    {
        ptr->next_ptr = succ_ptr->next_ptr;
        delete_element(succ_ptr, V, k);
        k++;
        (*count)++;

        // after doing so, it calls recursively to complete_list_to_array,
        // so that the current item is confronted with its new following element.
        // the returned value is *count.

        (*count) = complete_list_to_array(ptr, V, count, k);
    }

    else {

        // if the flow is sent here, it means the list has arrived at its last item, after the current one.
        // the succ_ptr->next_ptr pointer will so point to NULL, indicating the list has reached its end.
        // as above, the following item is deleted and count increased. The k index, though, has no need to
        // as it's the last time an element will be inserted in the array V.

        ptr->next_ptr = NULL;
        delete_element(succ_ptr, V, k);
        (*count)++;

    }
    return (*count);
}

// complete_list_to_array is the main recursive function of the program. Getting its data directly from main(),
// it uses while both as a loop and as a guard, checking each time if the list has reached its end or its last element.
// the function has cost T(N) = c1 if N == 2 || c1*N + T(N-1) if N > 2

int complete_list_to_array(struct list * ptr, int * V, int * count, int k) {

    struct list * succ_ptr;

    while (ptr != NULL)
    {
        if(ptr->next_ptr != NULL)
        {
            succ_ptr = ptr->next_ptr;

            // if the following element is bigger than the current element plus one, it sends
            // the flow to function succ_value_bigger and slides ptr to its following pointer.

            if(ptr->value + 1 <= succ_ptr->value) {
                succ_value_bigger(ptr);
                ptr = ptr->next_ptr;
            }

            // if the following element is smaller than the current, it increases the index *count as return value
            //and sends the flow to succ_value_smaller, then slides ptr to the following pointer.

            else if (succ_ptr->value <= ptr->value)
            {
                (*count) = succ_value_smaller(ptr, V, count, k);
                if (ptr->next_ptr != NULL)
                    ptr = ptr->next_ptr;

                else
                    ptr->next_ptr = NULL;
            }
        }

        // if the list only has one item, the flow is sent here. The break instruction sends the flow to the following
        // instruction, and is widely used to change the flow in switch iterations.

        else break;
    }
    return (*count);
}


// the following function creates the list which will then be used in the function. It uses two pointers, one to the
// first item, which is the return value (so that the main() function can begin its work from the first item), and
// a general pointer which is slid each time a value is inserted, according to the number N of items in the list.


struct list * create_list(int N) {
    struct list * first_ptr, * ptr;
    int i;

    // if the list contains 0 elements (N == 0) the first pointer will point to NULL, contained in the memory.h library.

    if(N == 0) {
        first_ptr = NULL;
    }
    else {
        first_ptr = malloc(sizeof(struct list));
        printf("Insert the first value:\n");
        scanf("%d", &first_ptr->value);
        ptr = first_ptr;

        for(i = 2; i <= N; i++) {
            ptr->next_ptr = malloc(sizeof(struct list));
            ptr = ptr->next_ptr;
            printf("Insert element number %d:\n", i);
            scanf("%d", &ptr->value);
        }

        ptr->next_ptr = NULL;
    }

    return(first_ptr);
}

// this simple function prints all the items contained in the list. It uses a while loop until the list
// has reached its last element.

void visit(struct list * ptr) {
    int i = 1;
    while(ptr != NULL) {
        printf("Item number %d in the list has value %d.\n", i, ptr->value);
        ptr = ptr->next_ptr;
        i++;
    }
}

// main function

int main(void) {

    // variables declaration and dynamic allocation of the array.

    struct list * first_ptr;
    int N, k = 0;
    int i;
    int * V, count = 0;

    V = (int *)malloc(sizeof(int)*count);

    // choice of the dimension of the list.

    printf("Insert the number of elements in the list.\n");
    scanf("%d", &N);

    // call to create_list function.

    first_ptr = create_list(N);

    printf("\n----------------------------\n\n");

    // call to visit function in order to print the items initally contained in the list.

    printf("At the beginning, the list contained the following items:\n\n");
    visit(first_ptr);

    printf("\n----------------------------\n\n");

    // call to complete_list_to_array function, using first_ptr so that it begins from the first item
    // and count's address, as the list requires in its formal parameters a pointer to int.

    count = complete_list_to_array(first_ptr, V, &count, k);

    // results after the flow returns from the function to main(). It first tells the user which and how many items
    // have been removed (if count == 0 it skips the first step), then prints the modified list. 

    printf("After the function call, the following items have been removed from the list and put into the array:\n\n");

    if(count == 0) {
        printf("No item has been removed from the list.\n");
    }
    else {
    for(i = 0; i < count; i++) {
        printf("The value of V[%d] is: %d.\n", i, V[i]); }

        printf("\nThe total number of removed elements is %d.\n", count);
    }

    // using function free(void *), the memory section occupied by array V, which was first allocated with
    // library <stdlib.h>'s function malloc. This way, the allocated section for V is freed from the memory.

    free(V);

    printf("\n----------------------------\n\n");

    printf("After the function call, the list contains the following items:\n\n");
    visit(first_ptr);

    return 0;
}
\$\endgroup\$
1
\$\begingroup\$

On my computer while the program runs and gives answers it still terminates with 0xC0000005 which means the memory problem is still there but it no longer stops the program.

The type of recursion you are using, where 2 functions (int succ_value_smaller(struct list * ptr, int * V, int * count, int k) and int complete_list_to_array(struct list * ptr, int * V, int * count, int k)) call each other, is sometimes called Figure Eight recursion and was used in earlier forms of Fortran because Fortran did not support recursion directly. It is not something I would really recommend when programming in C, it is very difficult to program correctly, debug and maintain.

Self Documenting Code

Commenting code is ok, but it should be kept to a minimum. When comments are included in the code they need to be maintained as well as the code to keep the comments in sync with the code, this adds overhead to maintenance. Good comments provide very high level information about why something is done, and wouldn't comment at lower levels of the code. It's also not clear why the cost of each function is documented, but that may be required for a homework assignment. It is better to make the function names and variable names as clear as possible.

It might be better to avoid abbreviations such as succ_, since it isn't quite clear what it means. It also isn't quite clear why the function void pre_insert(struct list ** ptrptr, int value) is called pre_instert since it is in fact doing the insertion.

Variable Declarations and Initialization

In the original version of the C programming language (sometimes referred to as K&R C) all variables needed to be declared at the top of the function, this is no longer true, it is better to declare variables as they are needed, for instance in main there is int i; at the top of the function but i is only used in a for loop at the end of main(). The variable i can be declared in the for loop itself:

        for(int i = 0; i < count; i++) {
            printf("The value of V[%d] is: %d.\n", i, V[i]);
        }

The variable k can also be declared later in main()

    int k = 0;
    count = complete_list_to_array(first_ptr, V, &count, k);

The variable name k doesn't really indicate what k is used for, and it is never changed in the body of main().

When using the C programming language it is best to initialize all variables when they are declared. Some programming languages initialize variables to a default, such as setting an integer value to 0, the C programming language is not one of them and it is quite easy to use a variable without initializing it, which can lead to bugs. So rather than the following at the top of main()

int main(void) {

    // variables declaration and dynamic allocation of the array.

    struct list * first_ptr;
    int N, k = 0;
    int i;
    int * V, count = 0;

It would be better to write the code this way

int main(void) {

    // variables declaration and dynamic allocation of the array.

    struct list * first_ptr = NULL;
    int N = 0;
    int *V = NULL;
    int count = 0;

    V = (int *)malloc(sizeof(int)*count);

This shows us the first bug in the program, since count is zero the call to malloc(size_t size) fails because zero * sizeof(int) is zero. It is probably what caused the 0xC0000005 problem.

Bug

As pointed out above, the variable V is NULL and this leads to unknown behavior (bug). It might be better to use the variable N after the user has entered it.

    printf("Insert the number of elements in the list.\n");
    scanf("%d", &N);
    if (N > 0)
    {
        V = malloc(sizeof(int)*N);
        if (V == NULL)
        {
            fprintf(stderr, "Failed to allocate the memory for the integer array V\n");
            return EXIT_FAILURE;
        }
    }
    else
    {
        fprintf(stderr, "The number of elements in the list must be greater than 0.\n");
        return EXIT_FAILURE;
    }

Error Checking and Preventing Bugs

There are 2 types of error checking that need to be implemented in this program. The first is to make sure user input is valid and the second is to make sure there are not memory allocation errors.

The function scanf() can fail in a number of ways. scanf() returns an integer value that indicates the success or failure of the call, if the number is greater than zero then scanf() succeeded, if the number is EOF or zero than scanf() failed. The user can also enter an invalid value and that needs to be checked.

The memory allocation functions void *malloc(size_t size), void *calloc(size_t count, size_t size) and void *realloc( void *ptr, size_t new_size ) can also fail for various reasons, although it is rare today do to the size of RAM on computers. If these functions fail they return NULL. Access through a null pointer yields unknown behavior, the easiest to see is the program crashing, data can also be corrupted which can be harder to detect. For this reason the return value of any of these functions should be tested to prevent invalid memory access (segmentation violation and other problems).

Putting these 2 error checks together:

void scanf_failure()
{
    fprintf(stderr, "scanf() failed getting the number of elements in the list.\n");
    exit(EXIT_FAILURE);
}

int get_number_of_elements()
{
    int element_count = 0;

    printf("Insert the number of elements in the list.\n");
    int test_tnput_count = scanf("%d", &element_count);
    if (test_tnput_count != EOF && test_tnput_count > 0)
    {
        while (element_count <= 0)
        {
            fprintf(stderr, "The number of elements must be greater than zero.\n");
            test_tnput_count = scanf("%d", &element_count);
            if (test_tnput_count == EOF || test_tnput_count <= 0)
            {
                scanf_failure();
            }
        }
    }
    else
    {
        scanf_failure();
    }

    return element_count;
}

int main(void) {
    struct list * first_ptr = NULL;
    int N = 0;
    int *V = NULL;
    int count = 0;

    N = get_number_of_elements();
    V = malloc(sizeof(int)*N);
    if (V == NULL)
    {
        fprintf(stderr, "Failed to allocate the memory for the integer array V\n");
        return EXIT_FAILURE;
    }

    ...

    return EXIT_SUCCESS;
}

The rest of this review is copied from my answer to your question on Stack Overflow

Prefer calloc Over malloc for Arrays

There are 3 major allocation function in the C programming language, they are void *malloc(size_t size_to_allocate), void* calloc( size_t number_of_items, size_t item_size ) and void *realloc( void *ptr, size_t new_size ). The best for initially allocating arrays is calloc because it clearly shows that you are allocating an array, and because it zeros out the memory that is being allocated.

Functions Should Return Values

Rather than passing in a pointer to a pointer to get a new pointer value the pre_insert(struct list * ptrptr, int value) function should return the new pointer.

struct list* pre_insert(struct list * ptrptr, int value) {
    struct list * tmp_ptr;

    tmp_ptr = ptrptr;
    ptrptr = NewPtr(value);
    if (tmp_ptr)
    {
        ptrptr->next_ptr = tmp_ptr;
    }

    return ptrptr;
}

Missing Linked List Functions

There are a standard set of linked list functions that should be implemented, these are

  • create Node (shown above as *NewPtr(int value))
  • Insert Node
  • Append Node
  • Delete Node
  • Find Node

Using these common linked list functions would make it much easier to implement the larger problem solution.

Complexity

If I was going to review this on code review, the first thing that I would suggest is that the function int complete_list_array(struct list * ptr, int * V, int * count) is too complex, this means it is doing too much in a single function. It would be easier for you to write/debug this if the contents of each of the internal if's was a function.

There are 2 concepts to consider here, the first is top down design and the second is the Single Responsibility Principle. Top down design is where you keep breaking the problem into smaller and smaller pieces until each piece is very easy to implement. The Single Responsibility Principle states:

that every module, class, or function should have responsibility over a single part of the functionality provided by the software, and that responsibility should be entirely encapsulated by that module, class or function.

| improve this answer | |
\$\endgroup\$
  • 1
    \$\begingroup\$ Thank you so much for such a detailed reply. Just wanted to clarify, regarding the name 'pre_insert', the long comments and the cost of the functions. For the first one, it was a function that our professor made us call "pre_insert" and won't accept anything else, even if, i know, it just inserts values. For the long comments and the functions' costs, yes, it was all homework stuff that i had to put in my code for my exam. Thanks again! \$\endgroup\$ – Alice Dun Jan 25 at 15:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.