Linked list problem

[zaxo311]

I have following problem:
I have 2 structures: Clients and items
for example structure clients would have name and list of items from another structure asigned to this specific name I have to do this with singly linked lists. I simply have no idea how to do this would be great if somebody could explain to me how to do this and give example of how this should look aswell.

[Ancient Dragon]

Were those two structures given to you or can you make them up yourself?

There are two linked lists -- Client and within each client node is a Items linked list.

To add a new client node you have to search the Client linked list to see if it is already there. If not, then add a new Client node to the end of the Client linked list.

To add a new Items node to a Client node, first find the Client node, as above. Once found, search it's Items linked list to make sure there isn't already an Items node in the list. If not, then add a new Items node to the tail of the Items linked list.

[zaxo311]

The structures which I used were just to present my problem so those doesnt really matter all I want is example of how it can be done in c and possibly answer to further questions if I dont understand something thanks.

[Ancient Dragon]

Here is an example

[zaxo311]

Um, well it doesn't explain much to me seems like normal linked list for me. From what I understand mine should look like:

 client->client
      |       |
    item     item
      |       |
    item     item

So I think it should be list of items under each client node I have idea how it should be I think at least but i have no idea how it should look in code :/. Thank you for your time.. :x

So I think that those structures should look like this but how would I allocate memory when creating list here?

 struct client{
    char name[30];
    char last_name[30];
    struct item *d;
    struct client *next;
    }
    struct item{
    char item_name[30];
    struct item *next;
    }

[Ancient Dragon]

seems like normal linked list for me.

Yes -- what you want is just two nested normal linked lists.

Once you understand simple linked list it is just slightly more complicated to do nested linked lists. I would do it like this: The last function AddItem() shows how to allocate memory for the item linked list.

    struct item{
    char item_name[30];
    struct item *next;
    }

struct client{
    char name[30];
    char last_name[30];
    struct item *d;
    struct client *next;
}


struct client* FindClient(struct client* head, const char* name)
{
    while(head->next != NULL)
    {
        if( strcmp(head->name,name) == 0)
        {
          return head;
        }
        head = head->next;
    }
    return NULL;
}


struct item* FindItem(struct item* head, const char* item_name)
{
    while(head->next != NULL)
    {
        if( strcmp(head->item_name,item_named) == 0)
            return head;
    }
    return NULL;
}

struct item* FindTail(struct item* head)
{
    while( head->next != NULL)
       head = head->next;
    return head;    
}

struct item* AddItem(struct item** head, const char* item_name)
{
    struct item* newnode = malloc(sizeof(struct item));
    newnode->next = NULL;
    strcpy(newnode->item_name,item_name);
    if( *head == NULL)
    {
        *head = newnode;        
    }
    else
    {
        strict item* node = FindTail(*head);
        node->next = newnode;
    }
    return newnode;
}

[zaxo311]

Could you explain me why in every function you use something like: struct item* AddItem what does it change, and is there need for strcpy function in AddItem or it could be done different way as I'm not that familiar with it.
Also would like to know why in function AddItem there's struct item** head while function FindTail has struct item* head .

Sorry for such questions but I'm lacking in knowledge regarding Linked lists.. and pointers trying to catch up right now while I'm free.

Back to your code, what I understood(not sure if im right..) is that the function AddItem everytime adds new node at end of the linked list kinda like that I think:

item->item->item

Based on functions which you gave with the AddItem code my guess is that I have to set head to specific client and use the AddItem function so I add 1 item to specific client and function AddItem works like it always adds another item at end of list so the links are like i written 1 post ago. Though still not sure how exactly I could link both client with list of items :/

[Ancient Dragon]

Could you explain me why in every function you use something like: struct item*

Yes, because that parameter is the head of the linked list to be used. How else do you think those functions are going to know where the top of the linked list is, and which linked list the function is supposed to use?

what does it change, and is there need for strcpy function in AddItem

AddItem creages a new node of type struct item, copies the value of item_name into the structure, and finally inserts the new node at the tail end of the linked list.

as I'm not that familiar with it.

You should already be familiar with strcpy() function, its one of the very basic string functions you learn. Since you are studying linked lists you most likely have already learned about strcpy(). If not, look it up in your textbook or google for it online.

Also would like to know why in function AddItem there's struct item** head while function FindTail has struct item* head .

Because AddItem() is going to change the caller's linked list, while the other functions such as FindTail() does not. The only way AddItem can change the value of the pointer passed by the calling function is to pass a pointer to the original pointer. I know, pointers can get confusing, but that will become clearer after you study and test it yourself.

Your thoughts at the end of your post are correct -- AddItem() works only with one specific item and appends it to the end of a specific Client linked list. What I didn't post is exactly how all that goes together -- I assume that given the example I posted you should be able to fingure out how to find a specific Client node and pass the pointer to it's item structure to AddItem(). I think I have given you enough information and examples to accomplish that.

[zaxo311]

Was busy lately with other subjects and now found time to get back to this not sure if you'r still watching this topic though. With help of code parts which you provided and overall looking throught internet I somehow wrote a bit of code on my own and it appears to be partialy working. It seems that it's adding items to client, but only the first one which I provide second one doesnt seem to work, and the display function aswell doesnt show second name. So if possible I would love to hear what exactly should I do to make it work propely.

`
#include<stdio.h>
#include<stdlib.h>
struct item{
char item_name[30];
struct item *next;
};
struct client{
    struct client *NextClient;
    char name[30];
    struct item *FirstItem;
};

struct client *head = NULL;
struct client *newnode = NULL;
struct client *ItemHead = NULL;
struct client* FindTailClient(struct client* head)
{
    while( head->NextClient != NULL)
    {

       head = head->NextClient;
    }
    return head;
}
struct client* AddClient(struct client** head,char name[])
{
    struct client* newnode = (struct client*)malloc(sizeof(struct client));
     if (newnode == NULL) {
    fprintf(stderr, "failed to allocate memory.\n");
    return -1;
}
       newnode->NextClient = NULL;
    strcpy(newnode->name,name);
    if(*head == NULL)
    {
        *head = newnode;
    }
      else
    {
        struct client* node = FindTailClient(*head);
        node->NextClient = newnode;
    }
    return newnode;
}
void Display(struct client *head)
{
    struct client *current = head;
    struct item *ItemCurrent;
        for(current=head;current;current=current->NextClient) {
        printf("name: %s\n", current->name);
        for(ItemCurrent=current->FirstItem;ItemCurrent;ItemCurrent=ItemCurrent->next) {
            printf("item name: %s\n",ItemCurrent->item_name);
        }
    }

    }
struct client *find(struct client *head, char name[])
{
struct client *temp = head;
    while (temp->NextClient != NULL )
    {
        if (strcmp(temp->name,name) == 0)
        {
            printf("Target found");
            return temp;
        }
        temp = temp->NextClient;
    }
    printf("target not found");
    return NULL;
}
struct item *FindTail(struct client *head)
{
    struct item *temp=head->FirstItem;

    while(temp->next != NULL)
    {
        temp=temp->next;
    }
    return temp;
}
void AddItemToClient(struct client *head, char item[])
 {
    struct item *temp = malloc(sizeof(struct item));
    struct client *clienttemp=head;
    temp->next = NULL;
    strcpy(temp->item_name,item);
        temp->next=clienttemp->FirstItem;
        clienttemp->FirstItem=temp;
}
int main()
{
 int i;
 struct item *item;
struct client *client;
char to_find[30];
    char data[30];
    char name[30];
    //
    for (i = 0; i < 2; i++)
    {
        printf("Person nr. %d:",i);
        scanf("%s",name);
        AddClient(client,name);
    }
    //
printf("Name of person to find:\n");
    scanf("%s",to_find);
client = find(client,to_find);
printf("Item name:\n");
for (i = 0; i < 2; i++)
    {
scanf("%s",data);
AddItemToClient(client, data);
    }
    //
    printf("Name of person to find:\n");
    scanf("%s",to_find);
client = find(client,to_find);
    for (i = 0; i < 2; i++)
    {
scanf("%s",data);
AddItemToClient(client, data);
    }
Display(client);
}
`

[Ancient Dragon]

AddClient() and AddItemToClient() should both be coded similarly because they both add a new node to the tail of a linked list. The only difference is that AddClient() adds a new node to the Client linked list while AddItemToClient() adds a new node to the Client's item linked list. Otherwise both functions should be the same.

what is the purpose of FirstItem in the item struct?

line 105: you need to pass a pointer to client pointer. Your compiler should have complained about that.

AddClient(&client,name);

[zaxo311]

Could you explain what exactly do you mean by coded similairy ? Uh and about a Firsitem, don't I need pointer to item struct in client, just left it named like that. While attempting to make what I wanted I tried to make it similar way to how your additem was but didnt work even a bit was smth like this:

struct item* AddItemToClient(struct client **head, char item[])
 {
    struct item *temp = malloc(sizeof(struct item));
    struct client *clienttemp= *head;
    temp->next = NULL;
    strcpy(temp->item_name,item);
    if(clienttemp->FirstItem != NULL)
    {
        clienttemp->FirstItem=temp;
    }
    else
    {
        struct item* nodeitem = FindTail(*head);
        nodeitem->next = temp;
    }
        return temp;
}

Most likely this attempt was totaly failed :p.
Um I'm using code blocks and there werent any problems during compiling, mb should I use different program?
Tried adding & but when I do it program instantly crashes after first input

[anas.man]

In computer science, a linked list is a data structure consisting of a group of nodes which together represent a sequence. Under the simplest form, each node is composed of a datum and a reference (in other words, a link) to the next node in the sequence; more complex variants add additional links.

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

struct node {
  int x;
  struct node *next;
};

int main()
{
    /* This won't change, or we would lose the list in memory */
    struct node *root;       
    /* This will point to each node as it traverses the list */
    struct node *conductor;  

    root = malloc( sizeof(struct node) );  
    root->next = 0;   
    root->x = 12;
    conductor = root; 
    if ( conductor != 0 ) {
        while ( conductor->next != 0)
        {
            conductor = conductor->next;
        }
    }
    /* Creates a node at the end of the list */
    conductor->next = malloc( sizeof(struct node) );  

    conductor = conductor->next; 

    if ( conductor == 0 )
    {
        printf( "Out of memory" );
        return 0;
    }
    /* initialize the new memory */
    conductor->next = 0;         
    conductor->x = 42;

    return 0;
}

[Ancient Dragon]

Ok, I see what FirstItem refers to -- the head of the item linked list.

When I said the two functions were identical I meant the code within the functions, not the parameters. The first parameter to AddItemToClient() is just a single pointer because it is the node in the Client linked list that you want to add items to. You don't want a double pointer for this because, unlike the other function, this function will not modify it's address.

struct item* AddItemToClient(struct client *client_head, char item[])
 {
    struct item *temp = malloc(sizeof(struct item));
    temp->next = NULL;
    strcpy(temp->item_name,item);
    if( client_head->FirstItem == NULL)
        head->FirstItem = temp;
    else
    {
        struct item *t = FindTail(client_head->FirstItem);
        t->next = temp;
    }
    return temp;
}

[zaxo311]

I tried even more to do it but still can't understand what's breaking while i try to add item into inner list. I'm so bad at it.. but deadline for my project is closing right now so have to do something.

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

    typedef struct lista lista;
    typedef struct item item;
    struct item
    {
        char item_name[30];
        item *next;
    };
    struct lista
    {
        int liczba;
        item *data;
        char napis[10];
        lista *next;
    };
    lista* find(lista *l,char name[61])
    {
        lista *current = l;
            int i;
            for(i=1;current!=NULL;i++)
            {
                if(strcmp(current->napis,name) == 0)
                {
                    printf("[%d] %d %s\n",i ,current->liczba,current->napis);
                    return current;
                }
                current=current->next;
        }
        return (NULL);
    }
    lista *dodajprzedmiot(lista *temp, char *item_named)
    {
          if(temp->data == NULL)
        {
            temp = (lista*)malloc(sizeof(lista));
            strcpy(temp->data->item_name, item_named);
            temp->data->next = NULL;
        }
        else
        {
            lista *pom;
            pom = temp;

            while(pom->data->next) pom->data=pom->data->next;

            pom->next=(lista*)malloc(sizeof(lista));
            strcpy(pom->data->next->item_name, item_named);
            pom->data->next->next=NULL;
        }
        return (NULL);
    }
    lista* kasuj(lista *list)
    {
       lista *pom=NULL;

        while(list)
        {
            pom=list->next;
            free(list);
            list=pom;
        }
        return NULL;
    }

    void dodaj(lista **l, int n, char tab[100])
    {
        if((*l)==NULL)
        {
            *l = (lista*)malloc(sizeof(lista));
            (*l)->liczba=n;
            strcpy((*l)->napis, tab);
            (*l)->next = NULL;
        }
        else
        {
            lista *pom;
            pom=(*l);

            while(pom->next) pom=pom->next;

            pom->next=(lista*)malloc(sizeof(lista));
            pom->next->liczba=n;
            strcpy(pom->next->napis, tab);
            pom->next->next=NULL;
        }
    }

    void dodajmiejsce(lista **l, int n, char tab[100])
    {
        if((*l)==NULL)
        {
            *l = (lista*)malloc(sizeof(lista));
            (*l)->liczba=n;
            strcpy((*l)->napis, tab);
            (*l)->next =NULL;
            return;
        }

        if( n<(*l)->liczba)
        {
            lista *pom=NULL;
            lista *pom2=NULL;

            pom=(lista*)malloc(sizeof(lista));
            pom->liczba=n;
            strcpy(pom->napis, tab);
            pom2=pom;
            pom->next=(*l);
            (*l)=pom2;
            return;
        }
        else
        {
            lista *pom;
            lista *pom2;
            pom=(*l);

            while((pom->next!= NULL) && (n>pom->next->liczba)) pom=pom->next;

            pom2=pom->next;

            pom->next=(lista*)malloc(sizeof(lista));
            pom->next->liczba=n;
            strcpy(pom->next->napis, tab);
            pom->next->next=pom2;
        }
    }

    void wypiszliste(lista *lis)
    {
      for( ; lis; lis=lis->next)
      {
        printf("%d %s \n", lis->liczba, lis->napis);
      }
    }

    lista* usun(lista *l, int us)
    {
        if(l==NULL)
        return l;

        if(l->liczba == us)
        {
            lista *pom=l->next;
            free(l);
            return pom;
        }
        else
        {
            lista *zwrot=l;

             lista *pom=NULL;

            while(( l->next->liczba != us) && (l->next->next!=NULL))  l=l->next;

            if(l->next->liczba==us)
            {
            pom=l->next;

            l->next=l->next->next;
            free(pom);
            }

            return zwrot;
        }
    }


    int licz(lista* p)
    {
    int l=0;
    for(;p;p=p->next)
    l++;
    return l;
    }


    int main()
    {
        int wybur, l;
        char ss[100];

        srand(time(0));
        lista *pocz=NULL;

        dodaj(&pocz, 1, "jeden");
        dodaj(&pocz, 2, "dwa");
        dodaj(&pocz, 3, "trzy");
        dodaj(&pocz, 4, "cztery");
        dodaj(&pocz, 5, "piec");
        dodaj(&pocz, 6, "szesc");
        dodaj(&pocz, 7, "siedem");
        dodaj(&pocz, 8, "osiem");
        dodaj(&pocz, 9, "dziewiec");
        while(1)
        {
                wypiszliste(pocz);
                printf("\n\nElementow: %d, \nOPCJE:\n1 dodaj \n 2 usun\n 3 usun wszystkie\n", licz(pocz));
                scanf("%d", &wybur);
                if (wybur==1)
                {
                        printf(" podaj liczbe\n");
                        scanf("%d", &l);
                        printf(" podaj opis\n");
                        scanf("%s", ss);
                        dodajmiejsce(&pocz, l, ss);
                }
                if(wybur==2)
                {
                     printf(" podaj liczbe do usuniecia\n");
                     scanf("%d", &l);
                     pocz=usun(pocz, l);
                }
                if(wybur==3)
                {
                    pocz=kasuj(pocz);
                 }
                 if(wybur==4)
                {
                      char namec[30];
                     printf("podaj imie");
                     scanf("%s",namec);
                     find(pocz,namec);
                 }
                 if(wybur==5)
                    {
                        char nameo[30];
                        char namec[30];
                        lista *temporal = NULL;
                        printf("name of client to add");
                        scanf("%s",namec);
                        printf("name of item");
                        scanf("%s",nameo);
                        temporal = find(pocz,namec);
                        dodajprzedmiot(temporal,nameo);
                    }
        }
        return 0;
}

[Ancient Dragon]

You are using way to many unnecessary parentheses and duplicate code For example dodaj() can be simplified like below, where the allocation is only done once at the beginning of the function. No need to repeat the lines within the function.

void dodaj(lista **l, int n, char tab[])
{
    lista* newnode = (lista*) malloc(sizeof(lista));
    newnode->liczba = n;
    newnode->data = NULL;
    strcpy(newnode->napis, tab);
    newnode->next = NULL;
    if (*l == NULL)
    {
        *l = newnode;
    }
    else
    {
        lista *pom = *l;

        while (pom->next) pom = pom->next;

        pom->next = newnode;
    }
}

Since your program is not in English I have no idea what those function names mean -- they are just meaningless to me. For example what is dodajmiejsce() supposed to do?

[zaxo311]

Ah sorry, this function is not neccessary. Just posted whole code on which I have been working. Only important functions are dodajprzedmiot,dodaj,find and wypisz liste. Sorry for writting it all in polish and posting here :x.

[zaxo311]

Well thanks to your help and my programming teacher figured how to do it ,thanks.