Поиск структуры, подлежащей перезаписыванию в связанном списке

Question

Я работаю над связанным списком, который у меня в основном работает, но мне нужно расширить то, что у меня есть сейчас, но у меня возникла проблема.

У меня есть структура, которая хранит исходящие звонки от телефонных звонков. Я храню эти вызовы в виде связанного списка, который определяется следующим образом:

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, тогда программе необходимо будет пройти через каждую исходящую ногу и проверить, разрешено ли разрешить перезаписывать для этой ноги значение true и если это так переписать эту ногу, а затем установить флаг перезаписи на false, а затем снова на следующей исходящей ноге, продолжайте цикл до тех пор, пока он не увидит, чтобы разрешить переписывать true, переписать и установить значение false, это должно продолжаться до тех пор, пока следующий ног не будет равен NULL, затем просто вставляет исходящую ногу на конец, как обычно.

Я думаю, что у меня есть базовая логика, однако я, кажется, продолжаю 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); 

Прикрепленного ниже, также диаграмма, показывающая поток, что мне нужно для вставки новой ноги.

Спасибо за любую помощь вы можете предоставить.

Answer 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 имеет флаг перезаписи. Опять же, в противоречие с логическим описанием в вопросе, 0 удалить флаг перезаписи для 5. Следовательно, путь становится 4 5 /3.

Когда 6 вставлен с набором перезаписи, он перезаписывает первый. Опять же, я очищаю флаг перезаписи для него, в противоречие с логикой, описанной в вопросе, но заданный для всех остальных ног в пути, поэтому путь становится 6 /5 /3.

---

Во-первых, небольшая заметка о структуре узла: Тот факт, что я поставил следующий указатель на начало структуры узла просто привычка.

(Это может помочь компилятор генерировать лучший код на некоторых архитектурах, поскольку next указатель затем указывает на адрес, где next->next есть, и что может помочь компилятор или процессор делать простые инструкции и более предварительной выборкой шаблонов при выполнении Если вы поместите указатель next в другое место, next->next находится на фиксированном смещении этого адреса, в некоторые случаях, которые может требуют дополнительной инструкции. Имеет ли это значение на практике? Обычно это не так, CPU cycle.)

insert() функция реализация должно быть довольно простым:

• Если список пуст, создайте новый узел, установив его флаг перезаписи на false. Готово.

  В противном случае:

• Если перезапись желательно заменить первый узел, установив его перезапись флаг в ложь, и перезапись флаг для всех остальных узлов в действительности. Готово.

  В противном случае:

• Если узел с перезаписью флагом верно, замените этот узел, сбрасывая его перезапись флаг ложной. Готово.

  В противном случае:

• Создать новый узел, установив его перезапись флаг ложной. Добавьте новый узел в конец списка. Готово.

только «трюк» вы могли бы задаться вопросом о том, как используется ptr указатель. Проще говоря, это адрес, где указатель currnode был получен, по существу, currnode = *ptr. Таким образом, вместо проверки на currnode->next в цикле мы просто переходим список до тех пор, пока currnode не станет NULL. Затем *ptr ссылается на указатель ->next в конечном элементе в списке, и мы можем просто назначить ему, чтобы добавить вновь созданный узел в список.

Я понимаю, что это не отвечает на вопрос ОП, но это потому, что я не знаю, как решать два уровня вопросов в исходном вопросе одновременно - я считаю, что существует и эта логическая проблема (с флагами перезаписи) и какой-то проблемой реализации, связанной с управлением связанным списком.

При отладке, фиксации программ или создании новых программ я всегда стараюсь ограничить возможные источники проблем наименьшим возможным набором. Написание ограниченных, упрощенных тестовых примеров, таких как вышеупомянутая программа, позволяет мне сосредоточиться на одной вещи одновременно, без необходимости переключать мой мозг между общей логикой и подробными деталями реализации. Проще говоря, так я работаю над проблемой OP, если это мой собственный код.

Теперь, когда у меня есть пример кода, который реализует логику, я верю, и я могу легко стресс-протестировать логику, я могу реализовать более сложную фактическую структуру ноги и функцию вставки ног. Знание логики работает (и я могу проверить любой угловой случай с использованием тестовой программы, если у меня возникнут какие-либо сомнения), я могу сосредоточиться на фактической реализации.

Очевидно, что до OP необходимо решить, какую логику (свою или мою) использовать, а если использовать мою, чтобы увидеть, как наши реализации отличаются; Я не думаю, что OP разместил достаточно кода (полную процедуру вставки), чтобы определить, где находятся реальные проблемы. По крайней мере, я не могу получить достаточно полный обзор, чтобы быть уверенным.

В любом случае, надеюсь, что это поможет. Вопросов?

Answer 2

Одна из проблем (возможно, есть другие) показывает, что вы устанавливаете outboundLeg->nextLeg = NULL;, прежде чем пытаться перебирать связанный список. Таким образом, вы завершаете его и, следовательно, никогда не сможете установить остальные, чтобы разрешить перезапись. Похож на ошибку копирования-вставки.

Edit: Еще одна потенциальная проблема заключается в том, что если overwriteFirstOutboundLegs == FALSE и переданное в outboundLeg->nextLeg != NULL и не outboundLeg->allowOverwrite == TRUE не встречается в списке, то последний элемент списка будет перезаписан (даже если он не помечен, чтобы перезаписать) вместо выделения новая структура для добавления в конец списка.