关于C中链表操作的问题

Question

关于这个练习的一些背景知识:我是一个仓库的所有者，拥有一个带有命令的文本文件，我需要实现这些命令，比如添加条目、删除条目等等。仓库包含货架，每个货架包含文本文件中给定的一定数量的单元格。货架和单元格使用链接列表相互连接(货架彼此连接，每个货架都有一个指向头单元格的指针)，每个单元格都包含一个指向结构项的指针，如果单元格不包含任何项，则为NULL。有架子和牢房的结构：

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;

如果有什么不清楚的地方，我希望我能把背景解释得足够好，让我知道。好的，至于我的问题，我成功地完成了所有必需的命令，只有一个，这个命令减少了物品，如果没有任何物品，就把它们撤下货架。我的功能看起来像自动取款机，但它只会减少每个货架上的空间，而不是书架之间的空间，如果这样做有意义的话(如果我不清楚我的英语不是很好的话)：

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;
                    }

                }
            }
            
        }
    }
}

这是在我运行我的功能之前仓库的打印：

        |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

这是在功能之后：

        |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

很难搞清楚该怎么做，想要在这方面得到一些帮助。非常感谢你抽出时间。

编辑:那是想要的表：

 |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

Answer 1

这是我的工作函数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;
        }
    }
}

我修改了您的函数，这样一旦函数找到一个空单元格，它就会搜索下一个非空单元格，然后交换两个单元格的数据。如果它找不到非空的单元格，它会移除所有空的架子。

这个程序使用一个goto标签。虽然这通常被认为是糟糕的编程实践，但在这种情况下，有必要使用goto来打破几层嵌套循环。

由于您没有为测试该函数提供任何代码，所以我编写了自己的程序来测试它：

#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 );
        }
    }
}

注意，由于您没有提供item_t的定义，所以我将其定义为const char *。

该程序具有以下输出，据我所知，这正是您想要的输出：

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