2

我正在研究一个基本上已经工作的链接列表，但我需要扩展我目前拥有的内容，但我遇到了问题。

我有一个存储来自电话的出站呼叫腿的结构。我将这些调用存储在一个链表中，该链表定义如下：

typedef struct CallLogSearchOutboundStruct
{
    char * target;
    float duration;
    char * cleardownCause;
    BOOL allowOverwrite;
    struct CallLogSearchOutboundStruct * nextLeg;
} callLogSearchOutboundStruct;

我有基本的代码工作，我可以使用下面的代码成功地将新的出站呼叫添加到链接列表的末尾：

void insertOutboundLegToList(callLogSearchOutboundStruct * outboundLeg, char * target, float duration, int cleardown, BOOL overwriteFirstOutboundLegs)
{
f (outboundLeg->target == NULL)
    {
        outboundLeg->target = strdup(target);
        outboundLeg->duration = duration;
        outboundLeg->cleardownCause = strdup(setCallResult(cleardown));
        outboundLeg->allowOverwrite = FALSE;
        outboundLeg->nextLeg = NULL;
    }
    else
    {    
        if (overwriteFirstOutboundLegs == FALSE)
        {
            while (outboundLeg->nextLeg != NULL)
            {
                    outboundLeg = outboundLeg->nextLeg;
            }
        }

        if (outboundLeg->nextLeg == NULL)
        {
            outboundLeg->nextLeg = (callLogSearchOutboundStruct*)malloc(sizeof(callLogSearchOutboundStruct));
            outboundLeg = outboundLeg->nextLeg;
            outboundLeg->target = strdup(target);
            outboundLeg->duration = duration;
            outboundLeg->cleardownCause = strdup(setCallResult(cleardown));
            outboundLeg->nextLeg = NULL;
        }
        else
        {
            outboundLeg->target = NULL;
            outboundLeg->duration = 0;
            outboundLeg->cleardownCause = NULL;
            outboundLeg->target = strdup(target);
            outboundLeg->duration = duration;
            outboundLeg->cleardownCause = strdup(setCallResult(cleardown));
        }
    }
}

此代码正在工作，但是我需要对其进行修改，以便如果设置了 allowOverwrite 标志，它将首先在链接列表中的第一个出站分支，覆盖它并将第一条分支的覆盖设置为 false，但所有其他分支在列表设置为允许覆盖。

因此，当需要插入新的出站呼叫时，如果覆盖第一支路设置为 false，则程序将需要循环遍历每个出站支路并检查该支路的允许覆盖是否设置为真，如果是，则覆盖那条腿，然后将覆盖标志设置为假，然后再次在下一个出站腿上，继续循环，直到它看到允许覆盖为真，覆盖并设置为假，这应该一直持续到下一个腿为空，然后它只是插入出站像往常一样将腿放在末端。

我认为我的基本逻辑是正确的，但是，当我从循环中中断时，我似乎继续对第一条腿进行 NULL 化，所以我最终没有出站腿。

下面是我如何修改代码以尝试实现我所需要的。

if (overwriteFirstOutboundLegs == TRUE)
{
    outboundLeg->target = strdup(target);
    outboundLeg->duration = duration;
    outboundLeg->cleardownCause = strdup(setCallResult(cleardown));
    outboundLeg->allowOverwrite = FALSE;

    //Loop through existing outbound legs and set overwrite flag to TRUE
    while (outboundLeg->nextLeg != NULL)
    {
        outboundLeg = outboundLeg->nextLeg;
        outboundLeg->allowOverwrite = TRUE;
    }
    outboundLeg->nextLeg = NULL;
}
else
{
    if (outboundLeg->target == NULL)
    {
        outboundLeg->target = strdup(target);
        outboundLeg->duration = duration;
        outboundLeg->cleardownCause = strdup(setCallResult(cleardown));
        outboundLeg->allowOverwrite = FALSE;
        outboundLeg->nextLeg = NULL;
    }
    else
    {
        if (outboundLeg->nextLeg == NULL)
        {
            outboundLeg->nextLeg = (callLogSearchOutboundStruct*)malloc(sizeof(callLogSearchOutboundStruct));
            outboundLeg = outboundLeg->nextLeg;
            outboundLeg->target = strdup(target);
            outboundLeg->duration = duration;
            outboundLeg->cleardownCause = strdup(setCallResult(cleardown));
            outboundLeg->allowOverwrite = FALSE;
            outboundLeg->nextLeg = NULL;
        }
        else
        {
            while (outboundLeg->nextLeg != NULL)
            {
                outboundLeg = outboundLeg->nextLeg;
                if (outboundLeg->allowOverwrite == TRUE)
                {
                    break;
                }
            }
            outboundLeg->target = strdup(target);
            outboundLeg->duration = duration;
            outboundLeg->cleardownCause = strdup(setCallResult(cleardown));
            outboundLeg->allowOverwrite = FALSE;
            outboundLeg->nextLeg = NULL;
        }
    }
}

我正在使用以下代码调用该函数：

insertOutboundLegToList(outboundCallLegStartPtr, targetBuffer, durationBuffer, atoi(rowReport[cleardownColIndex]), overwriteFirstOutboundLegs);

下面还附有一张图表，显示了我插入新腿所需的流程。

插入出站支路流程图

感谢您的任何帮助，您可以提供。

4

2 回答 2

1

outboundLeg->nextLeg = NULL;在尝试遍历链表之前，您正在设置一个问题（也许还有其他问题） 。因此，您将终止它，因此将永远无法将其余部分设置为允许覆盖。看起来像一个复制粘贴错误。

编辑：另一个潜在问题是，如果在列表中遇到overwriteFirstOutboundLegs == FALSE传入的outboundLeg->nextLeg != NULL和否outboundLeg->allowOverwrite == TRUE，那么最后一个列表项将被覆盖（即使它没有被标记为允许覆盖），而不是分配一个新的结构来追加到末尾的名单。

于 2013-09-26T15:46:09.120 回答
1

我发现用一个专门解决手头确切问题的小程序来探索实际问题很有用。

首先，我认为图表中存在错误或遗漏。我相信您希望始终清除overwrite插入或替换腿的标志。因此，这就是以下示例程序的作用：

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

typedef struct node {
    struct node *next;
    int          overwrite;
    int          value;
} node;

node *insert(node **const listptr, int value, int overwrite)
{
    /* No list specified? */
    if (!listptr) {
        errno = EINVAL;
        return NULL;
    }

    /* Empty list? */
    if (!*listptr) {
        node *newnode;

        newnode = malloc(sizeof *newnode);
        if (!newnode) {
            errno = ENOMEM;
            return NULL;
        }

        newnode->next = NULL;
        newnode->value = value;
        newnode->overwrite = 0;

        *listptr = newnode;
        return newnode;
    }

    if (overwrite) {
        node *const currnode = *listptr;
        node *temp;

        /* Overwrite contents */
        currnode->value = value;
        currnode->overwrite = 0;

        /* Set overwrite flag for all nodes that follow */
        temp = currnode->next;
        while (temp) {
            temp->overwrite = 1;
            temp = temp->next;
        }

        return currnode; 

    } else {
        node **ptr = listptr; 
        node *currnode = *listptr; /* always equal to *ptr */

        /* Find the first overwritable node */
        while (currnode && !currnode->overwrite) {
            ptr = &currnode->next;
            currnode = currnode->next;
        }

        /* Found an overwritable node? */
        if (currnode) {
            currnode->value = value;
            currnode->overwrite = 0;
            return currnode;
        }

        /* Construct a new node to be appended to the list. */
        currnode = malloc(sizeof *currnode);
        if (!currnode) {
            errno = ENOMEM;
            return NULL;
        }
        currnode->next = NULL;
        currnode->value = value;
        currnode->overwrite = 0;

        /* Append to the list. */
        *ptr = currnode;
        return currnode;
    }
}

void display(const char *const header, const node *list, const char *const footer)
{
    if (header)
        fputs(header, stdout);

    if (list) {
        do {
            if (list->overwrite)
                printf("/%d", list->value);
            else
                printf("%d", list->value);

            list = list->next;

            if (list)
                putchar(' ');

        } while (list);
    } else
        fputs("(empty)", stdout);

    if (footer)
        fputs(footer, stdout);
}

int main(int argc, char *argv[])
{
    node *list = NULL;
    int   arg, value;
    char  dummy;

    if (argc < 2 || !strcmp(argv[1], "-h") || !strcmp(argv[1], "--help")) {
        fprintf(stderr, "\n");
        fprintf(stderr, "Usage: %s [ -h | --help ]\n", argv[0]);
        fprintf(stderr, "       %s VALUE ... VALUE\n", argv[0]);
        fprintf(stderr, "Where VALUE is\n");
        fprintf(stderr, "       /INTEGER   to insert-overwrite INTEGER, or\n");
        fprintf(stderr, "       INTEGER    to insert INTEGER normally.\n");
        fprintf(stderr, "\n");
        return EXIT_FAILURE;
    }

    display("Initial list: ", list, ".\n");
    for (arg = 1; arg < argc; arg++) {

        if (sscanf(argv[arg], " /%d %c", &value, &dummy) == 1) {
            if (!insert(&list, value, 1)) {
                fflush(stdout);
                fprintf(stderr, "Cannot insert-overwrite %s: %s.\n", argv[arg], strerror(errno));
                return EXIT_FAILURE;
            } else
                printf("Inserted %d with overwrite set:\n", value);

        } else
        if (sscanf(argv[arg], " %d %c", &value, &dummy) == 1) {
            if (!insert(&list, value, 0)) {
                fflush(stdout);
                fprintf(stderr, "Cannot insert %s: %s.\n", argv[arg], strerror(errno));
                return EXIT_FAILURE;
            } else
                printf("Inserted %d:\n", value);

        } else {
            fflush(stdout);
            fprintf(stderr, "%s: Not a valid VALUE.\n", argv[arg]);
            return EXIT_FAILURE;
        }

        display("\t", list, ".\n");
    }

    display("Final list: ", list, ".\n");

    return EXIT_SUCCESS;
}

这个想法是你给一个测试序列作为命令行参数，每个值都是一个整数（大大简化了你的腿定义！）。如果应该使用覆盖集插入该值，则在该值之前使用斜线。

例如，您可以编译上述内容

gcc -W -Wall -O3 example.c -o example

让我们考虑测试序列1 2 3 /4 5 /6，这意味着我们按顺序插入前六个正整数，但是设置了覆盖标志（4并且6未设置所有其他整数）：

./example 1 2 3 /4 5 /6

哪个输出

Initial list: (empty).
Inserted 1:
        1.
Inserted 2:
        1 2.
Inserted 3:
        1 2 3.
Inserted 4 with overwrite set:
        4 /2 /3.
Inserted 5:
        4 5 /3.
Inserted 6 with overwrite set:
        6 /5 /3.
Final list: 6 /5 /3.

插入三条腿后，路径显然只是1 2 3，因为没有为其中任何一条设置覆盖标志，并且最初列表是空的。

当4使用覆盖集插入时，我的逻辑会覆盖第一个，清除它的覆盖标志（与问题中的逻辑描述相矛盾），并为路径中的其余支路设置覆盖标志。因此，路径变为4 /2 /3。

插入时5，它会替换2，因为2设置了覆盖标志。同样，与问题中的逻辑描述相矛盾，我清除 了5. 因此，路径变为4 5 /3。

当6使用覆盖集插入时，它会覆盖第一个。同样，我为它清除了覆盖标志，这与问题中描述的逻辑相矛盾，但为路径中的所有其余部分设置，因此路径变为6 /5 /3.

首先，关于节点结构的一个小说明：我将 next 指针放在节点结构的开头只是一种习惯。

（它可能有助于编译器在某些体系结构上生成更好的代码，因为next指针指向它所在的地址，next->next这可能有助于编译器或处理器在进行路径遍历时执行更简单的指令和更好的预取模式。如果你把next其他地方的指针，next->next位于该地址的固定偏移量；在某些情况下，可能需要额外的指令。在实践中是否重要？通常不是，甚至不是一个 CPU 周期。）

insert()函数实现应该非常简单：

  • 如果列表为空，则创建一个新节点，将其覆盖标志设置为 false。完毕。

    否则：

  • 如果需要覆盖，请替换第一个节点，将其覆盖标志设置为 false，并将所有其他节点的覆盖标志设置为 true。完毕。

    否则：

  • 如果存在覆盖标志为 true 的节点，则替换该节点，将其覆盖标志重置为 false。完毕。

    否则：

  • 创建一个新节点，将其覆盖标志设置为 false。将新节点附加到列表的末尾。完毕。

您可能想知道的唯一“技巧”是如何使用ptr指针。简单地说，它currnode本质上是获取指针的地址currnode = *ptr。这样，currnode->next我们无需在循环内检查，而是遍历列表直到currnode变为 NULL。然后，*ptr引用->next列表中最后一个元素中的指针，我们可以分配给它，将新创建的节点附加到列表中。

我意识到这并不能回答 OP 的问题，但那是因为我不知道如何同时解决原始问题中的两个级别的问题——我相信这两个逻辑问题都存在（覆盖flags），以及与如何管理链表有关的某种实现问题。

在调试、修复程序或编写新程序时，我总是试图将可能的问题来源限制在尽可能小的范围内。编写像上面的程序这样有限的、简化的测试用例让我一次只专注于一件事，而不必在整体逻辑和实现的细节之间切换我的大脑。简而言之，如果这是我自己的代码，这就是我解决 OP 问题的方式。

现在我有了一个实现我认为正确的逻辑的示例代码，并且我可以轻松地对逻辑进行压力测试，我可以实现更复杂的实际腿结构和腿插入功能。知道逻辑有效（如果我有任何疑问，我可以使用测试程序验证任何极端情况），我可以专注于实际实现。

显然，现在由 OP 决定使用哪种逻辑（他们的或我的），如果使用我的，看看我们的实现有何不同；我认为 OP 没有发布足够的代码（完整的插入例程）来说明实际问题出在哪里。至少我无法获得足够完整的概述来确定。

无论如何，希望这会有所帮助。问题？

于 2013-10-01T00:50:08.430 回答