Home > OS >  question about an exercise of linked list in C
question about an exercise of linked list in C

Time:08-08

a little background about the exercise: I'm the owner of a warehouse, getting a text file with commands and I need to implement them such as add items, remove items, and so on. the warehouse contains shelves and each shelf contains a certain amount of cells given in the text file. The shelves and the cells are connected to each other using a linked list (the shelves are connected to each other and every shelf got a pointer for the head cell), and every cell contains a pointer for a stuct item, if the cell doesn't hold any item there is NULL instead. there is the structure of the shelves and cells:

typedef struct cell_t
{
    int cellnum;
    struct item_t* itemInfo;
    struct cell_t* next;
}Cell;

typedef struct shelf_t
{
    int shelfnum;
    struct cell_t* cellhead;
    struct shelf_t* next;
}Shelf;

I hope I managed to explain the background well enough if anything is unclear let me know. ok, as for my question I managed to finish all of the required command but one, a command that reduces the items and remove shelves if there isn't any item in them. my function looks like that atm, but it only reduces the spaces on each shelf and not between shelves if it makes sense (sorry if I'm unclear my English isn't very good):

void reducespaces(Shelf* headshelf)
{
    Shelf* currS, *tempShelf;
    Cell* currC, *tempCell;

    for (currS = headshelf; currS; currS = currS->next)
    {
        
        for (currC = currS->cellhead; currC ; currC = currC->next)
        {
            if (currC->itemInfo == NULL)
            {
                for (tempCell = currC; tempCell ; tempCell = tempCell->next)
                {
                    if (tempCell->itemInfo != NULL)
                    {
                        currC->itemInfo = tempCell->itemInfo;
                        tempCell->itemInfo = NULL;
                        break;
                    }

                }
            }
            
        }
    }
}

this is the print of the warehouse before I run my function:

        |0      |1      |2      |3      |4
--------------------------------------------
0       |ALC-5  |GLO-1  |GLO-2  |GLO-3  |GLO-4
1       |WIP-6  |X      |X      |BAN-19 |BAN-20
2       |X      |X      |MAS-8  |MAS-9  |MAS-10
3       |TOI-11 |TOI-12 |X      |WIP-7  |WAT-14
4       |BAN-18 |WAT-15 |WAT-16 |WAT-17 |X
5       |EGG-22 |EGG-23 |EGG-24 |X      |X

and this is after the function:

        |0      |1      |2      |3      |4
--------------------------------------------
0       |ALC-5  |GLO-1  |GLO-2  |GLO-3  |GLO-4
1       |WIP-6  |BAN-19 |BAN-20 |X      |X
2       |MAS-8  |MAS-9  |MAS-10 |X      |X
3       |TOI-11 |TOI-12 |WIP-7  |WAT-14 |X
4       |BAN-18 |WAT-15 |WAT-16 |WAT-17 |X
5       |EGG-22 |EGG-23 |EGG-24 |X      |X

having hard time figuring out how to do it would love to get some help with that. thank you very much for your time.

edit: thats the desired table:

 |0 |1 |2 |3 |4
-------------------------------------------------------------
0 |ALC |GLO |GLO |GLO |GLO
1 |WIP |BAN |BAN |MAS |MAS
2 |MAS |TOI |TOI |WIP |WAT
3 |BAN |WAT |WAT |WAT |EGG
4 |EGG |EGG |X |X |X

CodePudding user response:

Here is my working function reducespaces:

void reducespaces(Shelf* headshelf)
{
    for ( Shelf* currS = headshelf; currS; currS = currS->next)
    {
        for ( Cell* currC = currS->cellhead; currC ; currC = currC->next)
        {
            if (currC->itemInfo == NULL)
            {
                //search for next non-empty cell
                Shelf *tempS = currS;
                Cell* tempC = currC->next;
                
                for (;;)
                {
                    for ( ; tempC != NULL; tempC = tempC->next )
                    {
                        if ( tempC->itemInfo != NULL )
                        {
                            //swap cell data
                            currC->itemInfo = tempC->itemInfo;
                            tempC->itemInfo = NULL;

                            //we cannot use "continue" here, because that 
                            //would apply to the innermost loop, but we want
                            //it to apply to the 2nd level loop
                            goto continue_level2_loop;
                        }
                    }

                    tempS = tempS->next;
                    if ( tempS == NULL )
                        break;
                    tempC = tempS->cellhead;
                }

                //we were unable to find a non-empty cell that comes after
                //currC, so we must go to the next shelf and delete all
                //shelves from that point on
                tempS = currS;
                currS = currS->next;
                tempS->next = NULL;

                while ( currS != NULL )
                {
                    //free all cells
                    currC = currS->cellhead;
                    while ( currC != NULL )
                    {
                        tempC = currC;
                        currC = currC->next;
                        free( tempC );
                    }

                    //unlink and free shelf node
                    tempS = currS;
                    currS = currS ->next;
                    free( tempS );
                }

                return;
            }

        continue_level2_loop:
            continue;
        }
    }
}

I modified your function so that as soon as the function finds an empty cell, it searches for the next non-empty cell and then swaps the data of both cells. If it is unable to find a non-empty cell, it removes all the empty shelves.

This program uses one goto label. Although this is generally considered bad programming practice, in this case, it was necessary to use goto in order to break out of several layers of nested loops.

Since you did not provide any code for testing the function, I wrote my own program for testing it:

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

#define CELLS_PER_SHELF 5

typedef struct cell_t
{
    int cellnum;
    const char* itemInfo;
    struct cell_t* next;
} Cell;

typedef struct shelf_t
{
    int shelfnum;
    struct cell_t* cellhead;
    struct shelf_t* next;
} Shelf;

void reducespaces(Shelf* headshelf)
{
    for ( Shelf* currS = headshelf; currS; currS = currS->next)
    {
        for ( Cell* currC = currS->cellhead; currC ; currC = currC->next)
        {
            if (currC->itemInfo == NULL)
            {
                //search for next non-empty cell
                Shelf *tempS = currS;
                Cell* tempC = currC->next;
                
                for (;;)
                {
                    for ( ; tempC != NULL; tempC = tempC->next )
                    {
                        if ( tempC->itemInfo != NULL )
                        {
                            //swap cell data
                            currC->itemInfo = tempC->itemInfo;
                            tempC->itemInfo = NULL;

                            //we cannot use "continue" here, because that 
                            //would apply to the innermost loop, but we want
                            //it to apply to the 2nd level loop
                            goto continue_level2_loop;
                        }
                    }

                    tempS = tempS->next;
                    if ( tempS == NULL )
                        break;
                    tempC = tempS->cellhead;
                }

                //we were unable to find a non-empty cell that comes after
                //currC, so we must go to the next shelf and delete all
                //shelves from that point on
                tempS = currS;
                currS = currS->next;
                tempS->next = NULL;

                while ( currS != NULL )
                {
                    //free all cells
                    currC = currS->cellhead;
                    while ( currC != NULL )
                    {
                        tempC = currC;
                        currC = currC->next;
                        free( tempC );
                    }

                    //unlink and free shelf node
                    tempS = currS;
                    currS = currS ->next;
                    free( tempS );
                }

                return;
            }

        continue_level2_loop:
            continue;
        }
    }
}

void print_data( Shelf* head )
{
    for ( Shelf *s = head; s != NULL; s = s->next )
    {
        for ( Cell *c = s->cellhead; c != NULL; c = c->next )
        {
            printf(
                "[%d][%d] %s\n",
                s->shelfnum,
                c->cellnum,
                c->itemInfo == NULL ? "NULL" : c->itemInfo
            );
        }
    }
}

int main()
{
    char *test_data[][CELLS_PER_SHELF] = {
        { "ALC-5" ,  "GLO-1" , "GLO-2" , "GLO-3" ,  "GLO-4"  },
        { "WIP-6" ,     NULL ,    NULL ,  "BAN-19", "BAN-20" },
        {    NULL ,     NULL , "MAS-8" ,  "MAS-9" , "MAS-10" },
        { "TOI-11",  "TOI-12",    NULL ,  "WIP-7" , "WAT-14" },
        { "BAN-18",  "WAT-15", "WAT-16",  "WAT-17",     NULL },
        { "EGG-22",  "EGG-23", "EGG-24",     NULL ,     NULL }
    };

    const int num_shelves = sizeof test_data / sizeof *test_data;

    Shelf *head;

    //allocate 6 shelf nodes and link them in
    //a linked list
    {
        //NOTE: additional code block is used to limit
        //scope of these variables, so that for example
        //no shadowing occurs
        Shelf **pp = &head, *p;

        for ( int i = 0; i < num_shelves; i  )
        {
            *pp = p = malloc( sizeof **pp );
            if ( p == NULL )
            {
                fprintf( stderr, "malloc failed!\n" );
                exit( EXIT_FAILURE );
            }

            p->shelfnum = i;

            pp = &p->next;
        }

        *pp = NULL;
    }

    //allocate cells for the shelves
    for ( Shelf *s = head; s != NULL; s = s->next )
    {
        Cell **pp = &s->cellhead;

        for ( int i = 0; i < CELLS_PER_SHELF; i   )
        {
            Cell *p;

            *pp = p = malloc( sizeof **pp );
            if ( p == NULL )
            {
                fprintf( stderr, "malloc failed!\n" );
                exit( EXIT_FAILURE );
            }

            p->cellnum = i;

            pp = &p->next;
        }

        *pp = NULL;
    }

    //fill cells with test data
    {
        Shelf *s = head;

        for ( int i = 0; i < num_shelves; i   )
        {
            Cell *c = s->cellhead;

            for ( int j = 0; j < CELLS_PER_SHELF; j   )
            {
                c->itemInfo = test_data[i][j];

                c = c->next;
            }

            s = s->next;
        }
    }

    printf( "Data BEFORE function call:\n\n" );

    print_data( head );

    printf( "\n" );

    reducespaces( head );

    printf( "Data AFTER function call:\n\n" );

    print_data( head );

    printf( "\n" );

    //cleanup
    {
        Shelf *s = head;

        while ( s != NULL )
        {
            //free all cells
            Cell *c = s->cellhead;
            while ( c != NULL )
            {
                Cell *tempC = c;
                c = c->next;
                free( tempC );
            }

            //unlink and free shelf node
            Shelf *temp = s;
            s = s->next;
            free( temp );
        }
    }
}

Note that because you did not provide the definition of item_t, I defined it as a const char *.

This program has the following output, which, as far as I can tell, is exaclty the output that you wanted:

Data BEFORE function call:

[0][0] ALC-5
[0][1] GLO-1
[0][2] GLO-2
[0][3] GLO-3
[0][4] GLO-4
[1][0] WIP-6
[1][1] NULL
[1][2] NULL
[1][3] BAN-19
[1][4] BAN-20
[2][0] NULL
[2][1] NULL
[2][2] MAS-8
[2][3] MAS-9
[2][4] MAS-10
[3][0] TOI-11
[3][1] TOI-12
[3][2] NULL
[3][3] WIP-7
[3][4] WAT-14
[4][0] BAN-18
[4][1] WAT-15
[4][2] WAT-16
[4][3] WAT-17
[4][4] NULL
[5][0] EGG-22
[5][1] EGG-23
[5][2] EGG-24
[5][3] NULL
[5][4] NULL

Data AFTER function call:

[0][0] ALC-5
[0][1] GLO-1
[0][2] GLO-2
[0][3] GLO-3
[0][4] GLO-4
[1][0] WIP-6
[1][1] BAN-19
[1][2] BAN-20
[1][3] MAS-8
[1][4] MAS-9
[2][0] MAS-10
[2][1] TOI-11
[2][2] TOI-12
[2][3] WIP-7
[2][4] WAT-14
[3][0] BAN-18
[3][1] WAT-15
[3][2] WAT-16
[3][3] WAT-17
[3][4] EGG-22
[4][0] EGG-23
[4][1] EGG-24
[4][2] NULL
[4][3] NULL
[4][4] NULL
  • Related