(C ++) Как изменить / использовать структуры данных, чтобы мы могли использовать их снова и снова? - PullRequest
Новая
       66

(C ++) Как изменить / использовать структуры данных, чтобы мы могли использовать их снова и снова?

0 голосов
/ 11 июля 2019

У меня есть структура данных (круговой двусвязный список) из N целых чисел.Я должен изменить это, минимизируя некоторое количество.В некоторых случаях расположения чисел мне придется проверять, минимизировано ли количество, проверяя измененную структуру данных в двух или более случаях.Я хотел бы знать, достаточно ли хороша моя попытка и есть ли лучший алгоритм для этих случаев.Я не формулирую проблему в явном виде, поскольку я хотел бы решить ее самостоятельно, но для отладки мы должны взять два смежных элемента списка, которые имеют минимальную сумму, и заменить их на сумму.Мы должны рассчитать сумму сумм на каждом этапе.(От N до 1)

Я создал две функции, две функции: mod () и demod (), чтобы изменять и демодифицировать список.В этих случаях я буду модифицировать структуру () для случая 1 и сохранить количество 1, demod (), затем модифицировать ее для случая 2 и сохранить количество 2.Затем я выберу мод () для этого случая, который имеет наименьшее количество.index и temp - два указателя, где я должен оценить количество.Отредактированный код приведен ниже.

    struct Node {
      long long int data;
      struct Node * prev;
      struct Node * next;
    };
    void mod(struct Node * index, long long int val) {
      struct Node * temp1 = index -> next;
      index -> data = val;
      index -> next = (index -> next) -> next;
      ((index -> next) -> next) -> prev = index;
      //free(temp1);
    }

    void demod(struct Node * index ,long long int a){
        long long int b = index->data - a;
        index->data = a;
        struct Node * new_Node = new Node;
         new_Node->data = b;
        new_Node -> next = index -> next;
        index->next = new_Node;
        new_Node->prev = index;
        (new_Node->next)->prev = new_Node;
    }
long long int value(struct Node * start, int length) {
  long long int val; 
    struct Node * index = start->prev;
    val = f(start -> prev);
    struct Node * temp = start;
    while (temp -> next != start) {

      if (val > f(temp)) {
        index = temp;
        val = f(temp);
      }
      temp = temp -> next;
    }
    cout << "val : " << val << "--";
    temp = start;
    while (temp -> next != start) {
      if (f(temp)==val && (index -> next == temp)) {
        std::cout << "*##";
        long long int init1 = index -> data;
        //displayList(start);
       // cout << init1 << " ";
        mod(index, val, start);
        cout << "start case 1\n ";
        long long int temp1 = solve(start, length - 1);
        cout << "end case 1\n ";
        demod(index, init1);
        displayList(start);
        mod(temp, val, start);
        displayList(start);
        cout << "start case 2 \n";
        long long int temp2 = solve(start, length - 1);
        cout << "end case 2\n";
        if (temp1 > temp2) {
          mod(temp, val, start);
          return val;
        } else {
          mod(index, val, start);
          return val;
        }
        /*if ((index -> prev) -> data > ((temp -> next) -> next) -> data) {
            std::cout << "*";
          index = index -> next;
        }*/
      }
      temp = temp -> next;
    }
   // cout << "index data " << index -> data << "\n";
    mod(index, val, start);

    return val;

}

... Полный код (162 строки) https://drive.google.com/open?id=1oD1pEr3_seX6kIzErpRG-Xu3s_95UVBj В коде теперь есть несколько угловых случаев, которые мне нужно исправить, и у меня возникла основная проблема использования структуры данных снова и снова.

Ответы [ 2 ]

0 голосов
/ 12 июля 2019

Есть еще больше ошибок.

Это верно.Следующий (после того, как указал один Джон) находится в строке 

        demod(index, init1);displayList(start);  mod(temp, val); displayList(start);

, поскольку узел temp был отсоединен от списка (хотя и не delete d) до mod() ранее,на данный момент он больше не является правильно связанным членом списка и не может быть использован как таковой без повторного связывания.Один из способов сделать это - передать temp в demod() и снова вставить его в список вместо того, чтобы выделять struct Node * new_Node = new Node; там.

0 голосов
/ 11 июля 2019

Так что я немного изо всех сил стараюсь ответить на ваш вопрос, но mod должен изменить значение index и удалить следующий узел после index из списка?

Если так, тоэто ошибка 

index->next = index->next->next;
index->next->next->prev = index;

То, что вы забыли, это то, что вы изменяете это значение index->next->next в первом операторе, но затем ваш второй оператор пытается использовать значение old .

Это должно быть (мое предпочтение) 

index->next = index->next->next;
index->next->prev = index;

или это (переключение порядка двух утверждений) 

index->next->next->prev = index;
index->next = index->next->next;

У меня мало сомнений, что естьбольше ошибок в остальной части кода.Этот вид тяжелого кода указателя очень сложно получить.

Вы также закомментировали ошибочный код free(temp1);.Если вы выделяете память с помощью new, она должна быть освобождена с помощью delete.Если вы выделяете память с помощью new[], она должна быть освобождена с помощью delete[].Если вы выделяете память с помощью malloc, она должна быть освобождена с помощью free.Не путайте их, они не эквивалентны.

...