Todays headache

Trying to create a double linked list nd have the following

Code:

---

typedef struct Numbers
{

    int Num;
    struct Numbers *Next;
    struct Numbers *Previous;

} Number;

Number * GetMemory();
void CreateHead( Number *, int );
void CreateNode( Number *, int );
void AppendtoList( Number *, Number *, int );
void ReadList( Number * );
void DistroyList( Number * );

int main()
{
    Number *Head = NULL, *Tail = NULL;

    for ( int RecNum = 1, i = 0; i < 10; i++ )
    {
        AppendtoList( Head, Tail, RecNum );
        RecNum++;
    }

    ReadList( Head );
    DistroyList( Tail );

    return 0;
}

Number * GetMemory()
{
    return ( Number * ) malloc ( sizeof( Number ) );
}

void CreateHead( Number *Tmpptr, int x )
{
    Tmpptr->Num = x;
    Tmpptr->Next = NULL;
    Tmpptr->Previous = NULL;
}

void CreateNode( Number *TmpPtr, int x)
{
    TmpPtr = GetMemory();
    TmpPtr->Previous = NULL;
    TmpPtr->Next = NULL;
    TmpPtr->Num = x;
}

void AppendtoList( Number *HPtr, Number *TPtr, int x )
{
    if ( HPtr == NULL )
    {
        HPtr = GetMemory();
        if ( HPtr != NULL )
        {
            CreateHead( HPtr, x );
            TPtr = HPtr;
        }
        else
        {
            printf("error getting memory!\n");
        }
    }
    else
    {
        CreateNode( TPtr->Next, x );
        if ( TPtr->Next != NULL )
        {
            TPtr->Previous = TPtr;
            TPtr = TPtr->Next;
        }
        else
        {
            printf("error getting memory!  Record not created \n");
        }
    }
}

---

The head record is created as in i get a memory address but when it returns to the main program its back to null.

You need to use a double pointer to pass a pointer back through a parameter. Normally we would use the return value if appropriate, which seems to be the case here. I'll try to fix up your code....

Okay, something like this seems to work, but it's pretty bad:

Code:

---

#include <stdio.h>
#include <stdlib.h>
 
typedef struct Numbers {
    int Num;
    struct Numbers *Next;
    struct Numbers *Previous;
} Number;
 
Number *GetMemory() {
    Number *mem = malloc(sizeof *mem);
    if (!mem) {
        perror("GetMemory");
        exit(EXIT_FAILURE);
    }
    return mem;
}
 
void CreateHead(Number **Tmpptr, int x) {
    (*Tmpptr)->Num = x;
    (*Tmpptr)->Next = NULL;
    (*Tmpptr)->Previous = NULL;
}
 
void CreateNode(Number **TmpPtr, int x) {
    *TmpPtr = GetMemory();
    (*TmpPtr)->Previous = NULL;
    (*TmpPtr)->Next = NULL;
    (*TmpPtr)->Num = x;
}
 
void AppendtoList(Number **HPtr, Number **TPtr, int x) {
    if (!*HPtr) {
        *HPtr = GetMemory();
        CreateHead( HPtr, x );
        *TPtr = *HPtr;
    }
    else {
        CreateNode( &(*TPtr)->Next, x );
        (*TPtr)->Previous = *TPtr;
        (*TPtr) = (*TPtr)->Next;
    }
}
 
int main() {
    Number *Head = NULL, *Tail = NULL;
 
    for (int RecNum = 1; RecNum <= 10; ++RecNum)
        AppendtoList( &Head, &Tail, RecNum );
 
    for (Number *node = Head; node; node = node->Next)
        printf("%d ", node->Num);
    putchar('\n');
 
    //ReadList( Head );
    //DistroyList( Tail );
 
    return 0;
}

---

I'll try to write it up in a more usual way...

Okay, this is somewhat more normal:

Code:

---

#include <stdio.h>
#include <stdlib.h>
 
typedef struct Number {
    int num;
    struct Number *next, *prev;
} Number;
 
Number *listNewNode(int n) {
    Number *node = malloc(sizeof *node);
    if (!node) {
        perror("listNewNode");
        exit(EXIT_FAILURE);
    }
    node->num = n;
    node->next = node->prev = NULL;
    return node;
}
 
Number *listAppend(Number *head, int n) {
    if (!head)
        return listNewNode(n);
    Number *node = head;
    for ( ; node->next; node = node->next) ;
    node->next = listNewNode(n);
    node->next->prev = node;
    return head;
}
 
int main() {
    Number *head = NULL;
 
    for (int i = 0; i < 10; ++i)
        head = listAppend(head, i);
 
    // Print forwards
    for (Number *node = head; node; node = node->next)
        printf("%d ", node->num);
    putchar('\n');
 
    // Find end of list
    Number *node = head;
    for ( ; node->next; node = node->next) ;
 
    // Print backwards
    for ( ; node; node = node->prev)
        printf("%d ", node->num);
    putchar('\n');
 
    return 0;
}

---

But it's even better to have a List struct to hold a pointer to the head and tail of the list:

Code:

---

#include <stdio.h>
#include <stdlib.h>
 
#define DATATYPE int
 
typedef struct Node {
    DATATYPE data;
    struct Node *next, *prev;
} Node;
 
typedef struct List {
    Node *head, *tail;
} List;
 
Node *listNewNode(DATATYPE data) {
    Node *node = malloc(sizeof *node);
    if (!node) {
        perror("listNewNode");
        exit(EXIT_FAILURE);
    }
    node->data = data;
    node->next = node->prev = NULL;
    return node;
}

void listPrepend(List *list, DATATYPE data) {
    Node *node = listNewNode(data);
    node->next = list->head;
    if (list->head)
        list->head->prev = node;
    else
        list->tail = node;
    list->head = node;
}
 
void listAppend(List *list, DATATYPE data) {
    Node *node = listNewNode(data);
    node->prev = list->tail;
    if (list->tail)
        list->tail->next = node;
    else
        list->head = node;
    list->tail = node;
}
 
List *listNew() {
    List *list = malloc(sizeof *list);
    if (!list) {
        perror("listNew");
        exit(EXIT_FAILURE);
    }
    list->head = list->tail = NULL;
    return list;
}
 
void listEmpty(List *list) {
    for (Node *node = list->head, *next = NULL; node; node = next) {
        next = node->next;
        free(node);
    }
    list->head = list->tail = NULL;
}
 
void listFree(List **list) {
    listEmpty(*list);
    free(*list);
    *list = NULL;
}
 
int main() {
    List *list = listNew();
 
    for (int i = 0; i < 10; ++i)
        listAppend(list, i);
 
    for (Node *node = list->head; node; node = node->next)
        printf("%d ", node->data);
    putchar('\n');
 
    for (Node *node = list->tail; node; node = node->prev)
        printf("%d ", node->data);
    putchar('\n');
 
    listEmpty(list);
 
    for (int i = 0; i < 10; ++i)
        listPrepend(list, i);
 
    for (Node *node = list->head; node; node = node->next)
        printf("%d ", node->data);
    putchar('\n');
 
    for (Node *node = list->tail; node; node = node->prev)
        printf("%d ", node->data);
    putchar('\n');
 
    listFree(&list);
 
    return 0;
}

---

i remembered there was something about double pointers but couldn't make them work with a simple program so gave up and decided to use the return values. This is what i came up with

Code:

---

typedef struct Numbers
{

    int Num;
    struct Numbers *Next;
    struct Numbers *Previous;

} Number;

Number * GetMemory();
void CreateHead( Number *, int );
Number * CreateNode( Number *, Number *, int );
Number * AppendtoList( Number *, Number *, int );
void ReadList( Number * );
Number * SearchList( Number *, Number *, int, int );
void DisplayNode( Number * );
void DeleteNode( Number * ); //untested as search doesnt work
void DistroyList( Number * );

int main()
{
    int RecNum = 0;
    Number *Head = NULL, *Tail = NULL;

    for ( int i = 1; i < 11; i++ )
    {
        if ( Head == NULL )
        {
            Head = AppendtoList( Head, Tail, i );
            Tail = Head;
        }
        else
        {
            Tail = AppendtoList( Head, Tail, i );
            if ( Tail == NULL )
            {
                break;
            }
        }

        RecNum++;
    }

    ReadList( Head );
    DisplayNode( SearchList( Head, Tail, 8, RecNum ) );
    DistroyList( Tail );

    return 0;
}

Number * GetMemory()
{
    return ( Number * ) malloc ( sizeof( Number ) );
}

void CreateHead( Number *Tmpptr, int x )
{
    Tmpptr->Num = x;
    Tmpptr->Next = NULL;
    Tmpptr->Previous = NULL;
}

Number * CreateNode( Number *TmpPtr, Number *TPtr, int x )
{
    TmpPtr->Previous = TPtr;
    TPtr->Next = TmpPtr;
    TmpPtr->Next = NULL;
    TmpPtr->Num = x;

    return TmpPtr;
}

Number * AppendtoList( Number *HPtr, Number *TPtr, int x )
{
    if ( HPtr == NULL )
    {
        HPtr = GetMemory();
        if ( HPtr != NULL )
        {
            CreateHead( HPtr, x );
            TPtr = HPtr;
            return HPtr;
        }
        else
        {
            printf("error getting memory!\n");
            exit(0);//will improve this
        }
    }
    else
    {
        Number *tmpNode = NULL;

        tmpNode = GetMemory();
        if ( tmpNode != NULL )
        {
            TPtr = CreateNode(tmpNode, TPtr, x);
            return TPtr;
        }
        else
        {
            printf("error getting memory!  Record not created \n");
            return NULL;
        }
    }
}

void ReadList( Number * CurrentRecord) //passed head pointer
{
    int countrec = 0;

    while ( CurrentRecord != NULL )
    {
        printf("%d\n", CurrentRecord->Num);
        CurrentRecord = CurrentRecord->Next;
        countrec++;
    }

    printf("%d records displayed\n", countrec);
}

Number * SearchList( Number *FirstRec, Number *LastRec, int Goal, int NumRec )
{
    if ( FirstRec == NULL )
    {
        return NULL;
    }
    int NumRecNew = 0;
    Number *MidRec = NULL;

    MidRec = FirstRec;

    while ( NumRec / 2 - NumRecNew > 0 )
    {
        MidRec = MidRec->Next;
        NumRecNew += 1;
    }

    if ( MidRec->Num == Goal )
    {
        return MidRec;
    }

    return MidRec->Num < Goal
            ? SearchList( FirstRec, MidRec , Goal, NumRecNew )
            : SearchList( MidRec->Next, LastRec, Goal, NumRecNew );
}

void DisplayNode( Number *CurrentRecord )
{
    if ( CurrentRecord != NULL )
    {
        printf("%d\n", CurrentRecord->Num);
    }
    else
    {
        printf("Record not found!!\n");
    }
}

void DeleteNode( Number *CurrentRecord )
{
    if ( CurrentRecord != NULL )
    {
        Number *NextNode = NULL, *PrevNode = NULL;

        NextNode = CurrentRecord->Next;
        PrevNode = CurrentRecord->Previous;

        CurrentRecord->Next->Previous = PrevNode;
        CurrentRecord->Previous->Next = NextNode;

        free ( CurrentRecord );
    }
}

void DistroyList( Number *CurrentTail ) //passed tail pointer
{
    int countrec = 0;
    while ( CurrentTail != NULL )
    {
        Number *tmpTail =NULL;
        tmpTail = CurrentTail;
        CurrentTail = CurrentTail->Previous;
        free (tmpTail);
        countrec++;
    }

    printf("%d records distroyed\n", countrec);
}

---

However the search function doesn't work as in it remembers the addresses of head and tail rather than one of them and mid then after a few goes it crashes so i assume my first if statement doesn't work

Sorry just seen your update. That is a lot clearer than my effort I always feel that I'm just kicking the can down the road and never really making concise functions no matter how hard i try. I notice you put your functions above main rather than "pre declare" them is that best practice or personal choice.

ok there were 2 things wrong i tested if midrec->num was less than goal rather than greater than.

second issue was my escape clause at the top it wouldn't find the last entry but think i have fixed it now.

Code:

---

Number * SearchList( Number *FirstRec, Number *LastRec, int Goal, int NumRec )
{
    if ( FirstRec->Next == NULL || LastRec->Previous == NULL)
    {
        if ( FirstRec->Num == Goal )
        {
            return FirstRec;
        }

        return NULL;
    }

    int NumRecNew = 0;
    Number *MidRec = NULL;

    MidRec = FirstRec;

    while ( NumRec / 2 - NumRecNew > 0 )
    {
        MidRec = MidRec->Next;
        NumRecNew += 1;
    }

    if ( MidRec->Num == Goal )
    {
        return MidRec;
    }

    return MidRec->Num > Goal
            ? SearchList( FirstRec, MidRec , Goal, NumRecNew ) //true
            : SearchList( MidRec->Next, LastRec, Goal, NumRecNew ); //False
}

---

ok it still doesnt work if you search for a number that is in between records eg if you have 1, 3, 5, 7 and search for 4 it fails

It's not really sensible to do a binary search on a linked list. Searching for the midpoint over and over is inefficient. It's better to just do a linear search. However, this seems to work:

Code:

---

Number *SearchList( Number *FirstRec, Number *LastRec, int Goal, int NumRec )
{
    if ( NumRec == 0 )
        return NULL;
 
    int MidRecNum = 1;
    Number *MidRec = FirstRec;
    for ( ; MidRecNum < NumRec / 2; ++MidRecNum )
        MidRec = MidRec->Next;
 
    if ( MidRec->Num == Goal )
        return MidRec;
 
    return Goal < MidRec->Num
        ? SearchList( FirstRec,    MidRec->Previous, Goal, MidRecNum-1 )
        : SearchList( MidRec->Next, LastRec,          Goal, NumRec-MidRecNum );
}

---

Quote:

---

I notice you put your functions above main rather than "pre declare" them is that best practice or personal choice.

---

It's just simpler for a program that resides in a single file. Function prototypes are more for multi-file programs. They serve no real purpose in single-file programs and just add clutter.

BTW, destroy has an 'e' not an 'i'.

Quote:

---

Originally Posted by john.c

Quote:

---

I notice you put your functions above main rather than "pre declare" them is that best practice or personal choice.

---

It's just simpler for a program that resides in a single file. Function prototypes are more for multi-file programs. They serve no real purpose in single-file programs and just add clutter.

---

I would disagree with this, IMHO.

Many time a one file program will expand into a two or more file program. It avoids retrofitting the prototypes later, and helps debug function definition, and calls.

I always told my students to always use prototypes. and I always put additional function definitions after main() in a one file program.

It also avoids the possibility of a "chicken and the egg syndrome" where a() calls b() and later b() calls a(). No i have never encountered this in real life, but it is theoretically possible. (Bad programming, I agree, and would never do, or allow it!) ;^)

I disagree. It is extremely easy to "retrofit" prototypes when a single-file program (which very often do not expand to multiple files) expands to a multi-file program. It is easier to change function interfaces since you don't need to fiddle with the pointless prototype. Prototypes are just meaningless clutter in single-file programs and in no way help to "debug function definitions and calls".

"I always put additional function definitions after main() in a one file program"
So?

john.c:

We will have to agree to disagree, and let others choose for themselves.

I disagree. I've proved my point. "Others" with functioning brains will see what is obviously correct.