在错误条目上运行的链接列表函数中删除条目和插入条目

Question

下午好。我正在从 Stephen G. Kochan 的一本名为 Programming in C Third Edition 的书中学习 C 语言。我写了一些应该在列表中插入和删除某些条目的代码，它确实这样做了，问题是，它没有删除正确的条目，也没有完全在正确的位置插入条目。代码如下。任何帮助将不胜感激！

//Insert and Remove entry functions using doubly linked lists
#include <stdio.h>

struct Entry
{
    int Value;
    struct Entry *Previous;
    struct Entry *Next;
};


int main()
{
    void InsertEntry (struct Entry *InsertPosition, struct Entry EntryToInsert);
    void RemoveEntry (struct Entry *EntryToRemove);
    struct Entry N1, N2, N3, N4, N5, Insert, *Start = &N1;

//set initial values
    N1.Value = 10;
    N2.Value = 20;
    N3.Value = 20;
    N4.Value = 30;
    N5.Value = 40;
    Insert.Value = 35;

//link the list

    N1.Next = &N2;
    N2.Next = &N3;
    N3.Next = &N4;
    N4.Next = &N5;
    N5.Next = (struct Entry *) 0;
//Link again

    N1.Previous = &N1;
    N2.Previous = &N1;
    N3.Previous = &N2;
    N4.Previous = &N3;
    N5.Previous = &N4;

    InsertEntry(&N4, Insert);
    RemoveEntry(&N2);

//Display the Lists
    while (Start->Next != (struct Entry *) 0)
    {
        printf("Previous: %i, Current: %i, Next: %i\n",         Start->Previous->Value, Start->Value, Start->Next->Value);
        Start = Start->Next;
    }

    return 0;
}

void InsertEntry (struct Entry *InsertPosition, struct Entry EntryToInsert)
{

    EntryToInsert.Previous = InsertPosition->Previous;
    EntryToInsert.Next = InsertPosition;
    InsertPosition->Previous->Next = &EntryToInsert;

}

void RemoveEntry (struct Entry *EntryToRemove)
{
    EntryToRemove->Previous->Next = EntryToRemove->Next;
}

Answer 1

你的 InsertEntry 函数有几个问题。

首先，您需要传入指向、InsertPosition 和EntryToInsert 的指针。这样做的原因是因为在 C 中，一切都是按值传递。这意味着当您将值传递给函数时，该函数将看到该值的 copy，而不是原始值。一旦该功能完成 - 副本将永远消失。所以如果你想修改函数内部的某些东西，并且在函数完成后让修改可见，你必须传递一个指向那个东西的指针。 C 中的指针指向内存中的某个位置 - 因此即使函数获得该指针的副本，它指向的位置也是相同的。

这意味着第一步是将函数定义为：

void InsertEntry (struct Entry *InsertPosition*, struct Entry *EntryToInsert)

其次，您插入 EntryToInsert 的顺序对于您想要完成的是错误的 - 您想要在 InsertPosition 之后插入此值，不在它之前。这是带有注释的更正函数：

void InsertEntry (struct Entry *InsertPosition, struct Entry *EntryToInsert)
{
    //Goal is to insert EntryToInsert *before* InsertPosition
    //  so that it will look like:
    //  ??? --> EntryToInsert --> InsertPosition
    //Step 1: ??? <-- EntryToInsert
    EntryToInsert->Prev = InsertPosition->Prev;
    //Step 2: EntryToInsert --> InsertPosition
    EntryToInsert->Next = InsertPosition;
    //Step 3: ??? --> EntryToInsert
    EntryToInsert->Prev->Next = EntryToInsert;
    //Step 4: EntryToInsert <-- InsertPosition
    InsertPosition->Prev = EntryToInsert;
}

最后 - 您当前在 main 函数内部的函数声明通常位于函数外部（之前）。

解决这个问题应该可以解决您的 RemoveEntry 函数的任何问题 - 同样，我认为没有问题。

Answer 2

代码中有几个问题。

将 InsertEntry 和 RemoveEntry 的声明移到 main() 之前。

初始化Previous字段时，列表头需要Previous = NULL。

打印列表时，需要避免分别打印出列表头和尾的Previous->Value和Next->Value。

在 InsertEntry() 函数中，代码按值传递 EntryToInsert 结构，将副本插入列表。我猜你打算通过将原始结构插入列表的指针传递。

在InsertEntry()函数中，还需要设置InsertPosition->Next->Previous

在InsertEntry()函数中设置InsertPosition->Previous->Next和InsertPosition->Next->Previous之前，需要分别检查自己不在列表的头部和尾部。

在RemoveEntry()函数中，还需要设置EntryToRemove->Next->Previous

在RemoveEntry()函数中设置EntryToRemove->Previous->Next和EntryToRemove->Next->Previous之前，需要分别检查你不在列表的头部和尾部。

在RemoveEntry()函数中，还需要设置EntryToRemove->Previous = NULL和EntryToRemove->Next = NULL。

我建议您尝试自行解决上述每个问题。如果您运行在解决给定问题时遇到问题，我已经包含了完整的代码和我建议的修复程序供您查看。

struct Entry
{
    int Value;
    struct Entry *Previous;
    struct Entry *Next;
};

void InsertEntry(struct Entry *InsertPosition, struct Entry *EntryToInsert);
void RemoveEntry(struct Entry *EntryToRemove);

int main()
{
    struct Entry N1, N2, N3, N4, N5, Insert, *Start = &N1;

    //set initial values
    N1.Value = 10;
    N2.Value = 20;
    N3.Value = 20;
    N4.Value = 30;
    N5.Value = 40;
    Insert.Value = 35;

    //link the list

    N1.Next = &N2;
    N2.Next = &N3;
    N3.Next = &N4;
    N4.Next = &N5;
    N5.Next = NULL;
    //Link again

    N1.Previous = NULL;
    N2.Previous = &N1;
    N3.Previous = &N2;
    N4.Previous = &N3;
    N5.Previous = &N4;

    InsertEntry(&N4, &Insert);
    RemoveEntry(&N2);

    //Display the Lists
    while (Start != (struct Entry *) 0)
    {
        printf("Previous: ");
        if (Start->Previous != NULL)
        {
            printf("%i", Start->Previous->Value);
        }
        else
        {
            printf("NULL");
        }
        printf(", Current: %i, Next: ", Start->Value);
        if (Start->Next != NULL)
        {
            printf("%i", Start->Next->Value);
        }
        else
        {
            printf("NULL");
        }
        printf("\n");
        Start = Start->Next;
    }

    return 0;
}

void InsertEntry(struct Entry *InsertPosition, struct Entry *EntryToInsert)
{
    EntryToInsert->Previous = InsertPosition->Previous;
    EntryToInsert->Next = InsertPosition;
    if (InsertPosition->Previous != NULL)
    {
        InsertPosition->Previous->Next = EntryToInsert;
    }
    InsertPosition->Previous = EntryToInsert;

}

void RemoveEntry(struct Entry *EntryToRemove)
{
    if (EntryToRemove->Previous != NULL)
    {
        EntryToRemove->Previous->Next = EntryToRemove->Next;
    }
    if (EntryToRemove->Next != NULL)
    {
        EntryToRemove->Next->Previous = EntryToRemove->Previous;
    }
    EntryToRemove->Previous = NULL;
    EntryToRemove->Next = NULL;
}

在错误条目上运行的链接列表函数中删除条目和插入条目

Remove entry and Insert Entry in Linked Lists functions operating on the wrong entries

c

struct

linked-list