Thread: I need help with LINKED LISTS

Announcements - General Programming Boards

Let's see your code, and what problems it's giving you.

I have a list like this, for example:

father1->son1->grandson1->grandson2->father2->son2->grandson3->NULL

I need to divide it in 3 lists like this:
father1->father2->NULL
son1->son2->NULL
grandson1->grandson2->grandson3->NULL


Structs:


Now, I need only the list of grandsons but I can only have the first one with my code. This is it:

Code:

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

typedef struct person{
    char name[20];
    char father[20];
    struct person *next;
}tPerson;

void createList(tPerson** list)
{
    int i, qFather, qSons, qGrandsons, j, k;
    char namefather[20], hisName[20];
    printf("\nHow many parents?: ");
    scanf("%d", &qFather);
    for(i=0; i<qFather; i++)
    {
        printf("\nname father %d: ", i);
        scanf("%s", hisName);
        printf("\nname of his father: ");
        scanf("%s", namefather);
        insertAtTheEnd(list, hisName, namefather);
        printf("\nHow many sons?: ");
        scanf("%d", &qSons);
        for(j=0; j<qSons; j++)
        {
            printf("\nname: ");
            scanf("%s", hisName);
            printf("\nname of his father: ");
            scanf("%s", namefather);
            insertAtTheEnd(list, hisName, namefather);
            printf("\nHow many sons?: ");
            scanf("%d", &qGrandsons);
            for(k=0; k<qGrandsons; k++)
            {
                printf("\nname: ");
                scanf("%s", hisName);
                printf("\nname of his father: ");
                scanf("%s", namefather);
                insertAtTheEnd(list, hisName, namefather);
            }
        }
    }
}

void insertAtTheEnd(tPerson** person, char name[20], char father[20])
{
    if((*person)!=NULL)
        insertAtTheEnd(&((*person)->next), name, father);
    else
    {
        (*person)=(tPerson*)malloc(sizeof(tPerson));
        strcpy((*person)->name, name);
        strcpy((*person)->father, father);
        (*person)->next=NULL;
    }
}


void printlist(tPerson* list)
{
    tPerson*aux;
    aux=list;
    while(aux!=NULL)
    {
        printf("\nname: %s", aux->name);
        printf("\nfather: %s", aux->father);
        aux=aux->next;
    }
}

tPerson* searchNodeInlist(tPerson* list, char name[20])
{
    int a;
    while(list!=NULL)
    {
        a=strcmp(list->name, name);
        if(a==0)
            return list;
        list=list->next;
    }
    return NULL;
}

int searchFather(tPerson* list, char name[20])
{
    int a, b;
    tPerson* father;
    tPerson* searched;
    tPerson* first=list;
    searched=(tPerson*)malloc(sizeof(tPerson)); // I don't know it this is necessary
    father=(tPerson*)malloc(sizeof(tPerson)); // I don't know it this is necessary
    searched=searchNodeInlist(list, name);
    while(list!=NULL)
    {
        a=strcmp(searched->father, list->name);
        if(a==0)
        {
            father=searchNodeInlist(list, searched->father);
            while(first!=NULL){
                b=strcmp(father->father, first->name);
                if(b==0)
                {
                    return 2; //has father and grandfather
                }
                first=first->next;
                return 1; //has father
            }
        }
        list=list->next;
    }
    return 0; //has no father
}


tPerson* lastNi(tPerson* ni, tPerson* actual)
{
    if((ni)!=NULL)
        lastNi(((ni)->next), actual);

    else{
        (ni)=(tPerson*)malloc(sizeof(tPerson));
        strcpy((ni)->name, actual->name);
        strcpy((ni)->father, actual->father);
        ((ni)->next)=NULL;
    }
    return ni;
}

tPerson* listgrandsons(tPerson* grandsons)
{
    int q, n=0;
    tPerson* following=NULL;
    tPerson* previous=NULL; 
    tPerson* actual=grandsons; 
    tPerson* ni=NULL;
    tPerson* niAux=NULL;
    previous=grandsons;
    actual=actual->next;
    following=actual->next;
    while(actual!=NULL)
    {
        q=searchFather(grandsons, actual->name);
        if(q==2) //if q==2, it's a grandson
        {
            previous->next=following;
            ni=lastNi(ni, actual);

            actual=actual->next;
            following=actual->next;
            printlist(ni);
        }
        else{
            if(following==NULL)
                return ni;

            previous=actual;
            actual=following;
            following=following->next;
        }
    }
    return ni;
}


int main()
{
    tPerson* list=NULL;
    tPerson* ni=NULL;
    char nameB[20];
    int qFathers;
    createList(&list);
    printlist(list);
    printf("\nname fathers to search: ");
    scanf("%s", nameB);
    qFathers=searchFather(list, nameB);

    ni=listgrandsons(list);
    printlist(ni);
    printlist(list);
    return 0;
}

I hope you can help me! I don't know what to do

If you have skype, maybe it's faster for both of us

What exactly is the goal here? Your question seemed to be about separating a singly linked list into three singly linked lists based on some property of each node. You said

I have a list like this, for example:

father1->son1->grandson1->grandson2->father2->son2->grandson3->NULL

I need to divide it in 3 lists like this:
father1->father2->NULL
son1->son2->NULL
grandson1->grandson2->grandson3->NULL

I see that a person is

Code:

typedef struct person{
    char name[20];
    char father[20];
    struct person *next;
}tPerson;

So what is it about a person that tells you whether he is a father, a son, or a grandson? Is it about the order in which they are added? Seems so, and then you can tell when you've changed generations by the fact that person.father has changed.

I'm not sure if this is what you're doing already, but it looks like you'll need to keep track of a stack of father names:

Code:

/* Nodes shown as "(name, father) -> next" */
(Bob, ___) -> (John, Bob) -> (Paul, Bob) -> (Tommy, Paul) -> (Wendy, Paul) -> (George, ___) -> (Michael, George) -> (Colby, Michael)

That's "___(Bob(John, Paul(Tommy, Wendy)), George(Michael(Colby)))" if we're saying "father(son1, son2, ...)". Then we need

Code:

Node *inputList = ...;
Node *fathersBegin = 0;
Node *fathersEnd = 0;
Node *sonsBegin = 0;
Node *sonsEnd = 0;
Node *grandsonsBegin = 0;
Node *grandsonsEnd = 0;

The nodes that fathers, sons, and grandsons will refer to already exist in inputList. We'll just reassign node.next as needed. As you walk through inputList, for each node "node":

• If fathersBegin is null, make this the first father.
• If if node->father == fathersEnd->name, add this node to sons.
• If node->father == sonsEnd->name, add this node to grandsons.
• Otherwise add this to fathers.

When you add a node to one of the lists (father, son, grandson), you first see whether begin is null. If so, then just do end = begin = node. If begin does have a value, then set end->next = node, end = node.

When you're all done you can set end->next = 0 for each of your three lists.

I hope there's something helpful in what I said.

Did you review your previous threads?
Help - Linked List
http://cboard.cprogramming.com/c-pro...7t-delete.html
http://cboard.cprogramming.com/c-pro...urgent%5D.html

You've been banging away at linked lists for 10 months, and it still hasn't sunk in.

I suggest you step away from this problem, and write yourself a nice little reference project you can keep going back to.

Code:

#include <stdio.h>
#include <stdlib.h>
typedef int data_t;

typedef struct _node {
  data_t        data;
  struct _node *next;
} node_t;

node_t *newNode(data_t data) {
  node_t *new = malloc(sizeof(new));
  if ( new ) {
    new->next = NULL;
    new->data = data;
  }
  return new;
}
node_t *insertAtFront(node_t *list, node_t *node ) {
}
node_t *insertAtEnd(node_t *list, node_t *node ) {
}
node_t *insertAtMiddle(node_t *list, node_t *node ) {
}
void printList(node_t *list) {
}
void destroyList(node_t *list) {
}

Once created, create a backup of it so you can always get back to it.

Then when you have a new linked list problem, you can modify this to test your latest idea.




It seems to me what you're trying to do is generate a family tree.

Code:

typedef struct person{
    char name[20];
    struct person *nextSibling;
    struct person *firstChild;
}tPerson;