(C++) 如何 modify/use 数据结构以便我们可以一次又一次地使用它们？

Question

我有一个N个整数的数据结构（循环双向链表）。我必须通过最小化一些数量来 mod 验证它。在某些数字排列的情况下，我将不得不在两种或多种情况下通过检查 modified 数据结构来检查数量是否最小化。我想知道我的尝试是否足够好，以及是否有更好的算法可用于这些情况。我没有明确说明问题，因为我想自己解决它，但为了调试，我们必须取列表中两个具有最小总和的相邻元素，并将它们替换为总和。我们必须计算每个阶段的总和。（N 到 1）

我创建了两个函数 2 个函数：mod() 和 demod()，以 modify 和 demodify 列表。在那些情况下，我将 mod() 结构用于案例 1 并存储数量 1，demod() 它，然后 mod() 用于案例 2，并存储数量 2。然后，我将为数量最少的那个案例 select mod() 。 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 代码现在有一些我必须更正的极端情况，我遇到了一次又一次使用数据结构的基本问题。

Answer 1

所以我有点难以理解你的问题，但是 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 释放内存。不要混淆它们，它们是不等价的。

Answer 2

There are still more mistakes.

没错。下一个（在约翰指出的那个之后）在行

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

由于节点 temp 之前已被 mod() 从列表中取消链接（虽然不是 deleted），此时它不再是正确链接的成员列表并且不能在没有被再次链接的情况下使用。一种方法是将 temp 传递给 demod() 并将其重新插入到列表中，而不是在那里分配 struct Node * new_Node = new Node;。

(C++) 如何 modify/use 数据结构以便我们可以一次又一次地使用它们？

(C++) How to modify/use data structures such that we can use them again and again?

c++

circular-list

data-structures

segment-tree