Crash with 0xC0000005 on my list-based program

Question

I'm relatively new to programming as I've just started university. My assignment is 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 (eg. 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.

Added from comments:
If program is run with the second element being bigger than the first one[,] it usually crashes.

i have absolutely no clue what i'm doing wrong. sorry if i made any grammar mistakes, English is not my native language.

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

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

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

    struct list * tmp_ptr;

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

int complete_list_array(struct list * ptr, int * V, int * count) {

    struct list * succ_ptr;
    int i, k = 0;

    while (ptr != NULL) {  
        if (ptr->next_ptr != NULL) { 
            succ_ptr = ptr->next_ptr; 
            if (ptr->value + 1 <= succ_ptr->value) { 
                for(i = 1; ptr->value + i <= succ_ptr->value; i++) { //
                    succ_ptr = succ_ptr->next_ptr;
                    ptr = ptr->next_ptr;
                    pre_insert(&ptr, ptr->value+ i);
                 } 
                 ptr = ptr->next_ptr;
            }
            else if (ptr->value >= succ_ptr->value) { 
                ptr->next_ptr = succ_ptr->next_ptr; 
                V[k] = succ_ptr->value;
                free(succ_ptr);
                k++;
                (*count)++;
                ptr = ptr->next_ptr;
            }
        }
    }

    return (*count);
}

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

    if(N == 0) {
        first_ptr = NULL;
    }
    else {
        first_ptr = (struct list *)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 = (struct list *)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);
}

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

int main() {

    struct list * first_ptr;
    int N;

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

    first_ptr = create_list(N);

    printf("Elements of the list.\n");
    visit(first_ptr);

    int * V, count = 0;
    V = (int *)malloc(sizeof(int)* N);

    count = complete_list_array(first_ptr, V, &count);

    printf("count = %d", count);
}

Answer 1

This

succ_ptr = succ_ptr->next_ptr;

can set succ_ptr to NULL. So in the next iteration you get a crash in

for(i = 1; ptr->value + i <= succ_ptr->value; i++)

I think you could replace the whole for-loop by:

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

Answer 2

4 suggestions:

1) Regarding your comment: ... i tried to do as you said, but the program still doesn't work. it stops after printing all the elements... There needs to be an explicit method to exit the loop. Add a break; statement at the end of the while statement. (See example at bottom of post:

2) For each and every malloc/calloc, call a free(...); statement

3) Do not cast the return of malloc()/calloc()
i.e. change: *ptrptr = (struct list*)malloc(sizeof(struct list));
to: *ptrptr = malloc(sizeof(struct list));

4) Signature to main functions should at a minimum be int main(void){...return 0;} (Note the return statement at the end of the function.)

Code example for item 1) :

while (ptr != NULL)
{
    if (ptr->next_ptr != NULL)
    {
        succ_ptr = ptr->next_ptr;
        if (ptr->value + 1 <= succ_ptr->value)
        {
             while (ptr->value + 1 < ptr->next_ptr->value)
             {
                pre_insert(&ptr->next_ptr, ptr->next_ptr->value-1);
             }
             ptr = ptr->next_ptr;
        }
        else if (ptr->value >= succ_ptr->value)
        {
            ptr->next_ptr = succ_ptr->next_ptr;
            V[k] = succ_ptr->value;
            free(succ_ptr);
            k++;
            (*count)++;
            ptr = ptr->next_ptr;
        }
    }
    else break;  //...Here...
}

Answer 3

This is more of a code review than a problem solving answer. This question was also asked on Code Review, since the code doesn't work as expected it was off-topic for code review. https://codereview.stackexchange.com/questions/235786/adding-or-deleting-elements-from-a-linked-list

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.

Checking for Memory Allocation Errors

When you call malloc(), calloc() or realloc() you should always check to see if memory was actually allocated before using the mempory. If any of these functions fail to allocate memory then it returns NULL. Reference through a null pointer results in unknown behavior, which is usually a bug.

struct list *NewPtr(int value)
{
    struct list *tmp_ptr = malloc(sizeof(*tmp_ptr));
    if (tmp_ptr == NULL)
    {
        fprintf(stderr, "malloc failed in allocation of new struct list");
        return NULL;
    }

    tmp_ptr->value = value;
    tmp_ptr->next_ptr = NULL;

    return tmp_ptr;
}

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 woulld 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.