Thread: Pointer troubles

Hello all this is my code:

Code:

#include <stdio.h>
#include <stdlib.h>
struct Node
{
    int data;
    struct Node* prev;
    struct Node* next;
};
void addDLL(struct Node** head, struct Node** tail, int temp)
{
    struct Node* newNode = malloc(sizeof(struct Node));
    newNode->data=temp;
    newNode->prev=NULL;
    newNode->next=NULL;
    if (*head==NULL && *tail==NULL)
    {
        *head=newNode;
        *tail=newNode;
    }
    else
    {
        newNode->prev=*tail;
        newNode->prev->next=newNode;
        *tail=newNode;
    }
    //printf("data %d,newnode add %p, next %p, prev %p\n", newNode->data, newNode, newNode->next, newNode->prev);
}
void deleteDLL(struct Node** max)
{
    *max->prev->next=*max->next;
    *max->next->prev=*max->prev;
    free(*max);
}
void printDLL(struct Node* head)
{
    while (head!=NULL)
    {
        printf("%d->",head->data);
        head=head->next;
    }
    printf("\n");
}
void findMax(struct Node* head, struct Node** max, int n)
{
    while (head!=NULL)
    {
        if (head->data==n)
        {
            *max=head;
            break;
        }
        else
        {
            head=head->next;
        }
    }
}
void solve(struct Node** max, int n)
{
    int result=0;
    if (*max->prev==NULL)
    {
        while (*max->next!=NULL)
        {
            if (*max->data-*max->next->data!=1)
            {
                result=1;
                break;
            }
        }
    }
    else if (*max->next==NULL)
    {
        while (*max->prev!=NULL)
        {
            if (*max->data-*max->prev->data!=1)
            {
                result=1;
                break;
            }
        }
    }
    else
    {
        n--;
        while (n!=0)
        {
            if (*max->prev->data!=NULL && *max->data-*max->prev->data==1)
            {
                n--;
                struct Node* temp = *max->prev;
                deleteDLL(max);
                *max=temp;
            }
            else if (*max->next->data!=NULL && *max->data-*max->next->data==1)
            {
                n--;
                struct Node* temp = *max->next;
                deleteDLL(max);
                *max=temp;
            }
            else
            {
                result=1;
                break;
            }
        }
    }
    if (result==0)
    {
        printf("YES\n");
    }
    else
    {
        printf("NO\n");
    }
}
int main()
{
    int i,n;
    scanf("%d", &n);
    struct Node* head=NULL;
    struct Node* tail=NULL;
    struct Node* max=NULL;
    for (i=0; i<n; i++)
    {
        int temp;
        scanf("%d",&temp);
        addDLL(&head, &tail, temp);
    }
    findMax(head, &max, n);
    solve(&max, n);
    printDLL(head);
    return 0;
}

When I do this:

Code:

    solve(&max, n);

I think I am sending address of max that is a pointer to the function solve() and then receiving it as struct Node** max in solve() So wouldn't *max mean it points to the element in my DLL?

Just so I'm clear, the acronym DLL usually means "dynamic link library", but in this context I think you're using it to refer to a double linked list. I'll assume it's a double linked list.

Let's focus on:

Code:

void solve(struct Node** max, int n)

This signature declared a Node ** as the parameter type, and thus the call to solve passes the address of a Node *. That's correct to that point.

Inside the function solve, max is a "pointer to a pointer". As such, 1 "*" dereferences only one level, meaning the result is a pointer, and in this case a pointer to a node (node *).

Code:

struct Node *np = *max;

This assigns a pointer to a node (note 1 star) to "what's stored at" max. Since max is a pointer to a pointer (2 stars), the dereference leaves us with 1 star, a pointer.

For np, this pointer can be dereferenced with ->, such that np->next would be the valid way of using the next member of the struct.

For max, however, this doesn't work. "max->next" would be an error, because the "->" will not move through both stars (a double dereference is required). For max, this is reqired: "(*max)->next". That deferences max from a "**" to a "*", which is then just 1 star, which can be derefenced with "->" correctly.

"*max" isn't the element, it is a pointer to the element.

Originally Posted by flp1969

Just now I saw @Niccolo told you this already... @Niccolo, a small correction (not related): DLL isn't an acronym. It is an abbreviation.

Merriam-Webster says:

Definition of acronym

a word (such as NATO, radar, or laser) formed from the initial letter or letters of each of the successive parts or major parts of a compound term

also : an abbreviation (such as FBI) formed from initial letters : INITIALISM

So "DLL" is an acronym. (And an acronym is an abbreviation.)

@flip1969 and @Niccolo Thanks a lot to both of you. I didn't know that -> operator had precedence over * till now. There were few logical errors in my code too but I think I cleaned it up. I was trying this problem here and it gives me a runtime error that I'm not sure at all why. The code is clearing ten test cases so I'm thinking my logic is correct in this one. Would appreciate if I could get one or two pointers where I'm getting wrong here. It's deviating a bit from my initial problem though.

Just now I saw @Niccolo told you this already

Yeah, but I didn't make it clear it was about order of precedence

Really sorry to bump it, I finally found the problem of the RTE. I did get some extra help but yeah my code for deleting a node was accessing stuff from null pointer. I'll post the correct code in here.

Code:

#include <stdio.h>#include <stdlib.h>
struct Node
{
    int data;
    struct Node* prev;
    struct Node* next;
};
void addDLL(struct Node** head, struct Node** tail, int temp)
{
    struct Node* newNode = malloc(sizeof(struct Node));
    newNode->data=temp;
    newNode->prev=NULL;
    newNode->next=NULL;
    if (*head==NULL && *tail==NULL)
    {
        *head=newNode;
        *tail=newNode;
    }
    else
    {
        newNode->prev=*tail;
        newNode->prev->next=newNode;
        *tail=newNode;
    }
    //printf("data %d,newnode add %p, next %p, prev %p\n", newNode->data, newNode, newNode->next, newNode->prev);
}
void deleteDLL(struct Node** max)
{
    //printf("deleting this data=%d ptr=%p\n",(*max)->data, *max);
    if ((*max)->prev!=NULL && (*max)->next!=NULL)
    {
        (*max)->prev->next=(*max)->next;
        (*max)->next->prev=(*max)->prev;
        //printf("linking of max prev next with max next done maxprenext data %d, maxprenext ptr %p, maxnext data %d, maxnext ptr %p\n", (*max)->prev->data, (*max)->prev, (*max)->next->data, (*max)->next);
        //printf("linking of max next prev with max prev done maxnextprev data %d, maxnextprev ptr %p, maxprev data %d, maxprev ptr %p\n", (*max)->next->data, (*max)->next, (*max)->prev->data, (*max)->prev);


    }
    else if ((*max)->prev==NULL && (*max)->next!=NULL)
    {
        (*max)->next->prev=NULL;
        //printf("null linko");
    }
    else if ((*max)->prev!=NULL && (*max)->next==NULL)
    {
        (*max)->prev->next=NULL;
        //printf("null linko");


    }
    free(*max);
    //printf("deleted\n");
}
void printDLL(struct Node* head)
{
    while (head!=NULL)
    {
        printf("%d->",head->data);
        head=head->next;
    }
    printf("\n");
}
void findMax(struct Node* head, struct Node** max, int n)
{
    while (head!=NULL)
    {
        if (head->data==n)
        {
            *max=head;
            break;
        }
        else
        {
            head=head->next;
        }
    }
}
void solve(struct Node** max, int n)
{
    int result=0;
    if ((*max)->prev==NULL)
    {
        //printf("first no. max\n");
        while ((*max)->next!=NULL)
        {
            if ((*max)->data-(*max)->next->data!=1)
            {
                result=1;
                break;
            }
            else
            {
                *max=(*max)->next;
            }
        }
    }
    else if ((*max)->next==NULL)
    {
        //printf("last no. max\n");
        while ((*max)->prev!=NULL)
        {
            if ((*max)->data-(*max)->prev->data!=1)
            {
                result=1;
                break;
            }
            else
            {
                *max=(*max)->prev;
            }
        }
    }
    else
    {
        n--;
        //printf("mid no. max\n");
        while (1)
        {
            if ((*max)->prev!=NULL && (*max)->data-(*max)->prev->data==1)
            {
                n--;
                if (n==0) break;
                //printf("N=%d prev max data=%d max ptr=%p prev data=%d prev ptr=%p\n", n, (*max)->data, *max, (*max)->prev->data, (*max)->prev);
                struct Node* temp = (*max)->prev;
                deleteDLL(max);
                *max=temp;
            }
            else if ((*max)->next!=NULL && (*max)->data-(*max)->next->data==1)
            {
                n--;
                if (n==0) break;
                //printf("N=%d next max data=%d max ptr=%p next data=%d next ptr=%p\n",n, (*max)->data, *max, (*max)->next->data, (*max)->next);
                struct Node* temp = (*max)->next;
                deleteDLL(max);
                *max=temp;
            }
            else
            {
                result=1;
                break;
            }
        }
    }
    if (result==0)
    {
        printf("YES\n");
    }
    else
    {
        printf("NO\n");
    }
}
int main()
{
    int i,n;
    scanf("%d", &n);
    struct Node* head=NULL;
    struct Node* tail=NULL;
    struct Node* max=NULL;
    for (i=0; i<n; i++)
    {
        int temp;
        scanf("%d",&temp);
        addDLL(&head, &tail, temp);
    }
    findMax(head, &max, n);
    solve(&max, n);
    //printDLL(head);
    return 0;
}

Thanks to all again!