0

自周日以来，我一直在使用这个迭代函数，但没有成功，我想为排序插入创建迭代函数，但经过一小时的节点绘图，我想我需要一些关于该函数的帮助：

结构声明：

  typedef struct E_Type * List;

  struct E_Type
  {
      int data;
      struct E_Type* next;
  };

功能：

bool insert(List & l, int data) {
    while (l != 0) {
        for (List p = l; p; p = p->next) {
            if (p->data == data)
                return false;
        }

        if (l->data > data) {
            List new_list = new E_Type;
            new_list->data = data;
            new_list->next = l;
            l = new_list;
            return true;
        } else if (l->data < data) {

            List new_list = new E_Type;
            new_list->data = data;
            l->next = new_list;
            l = new_list;
            return true;
        }
    }

    if (l == 0) {
        List new_list = new E_Type;
        new_list->data = data;
        new_list->next = l;
        l = new_list;
        return true;
    }
}

顺便说一句：这个功能甚至可能......关于这个插入的所有教程、信息等都带有对下一个数据的递归调用

4

4 回答 4

1 
//find the closest Node that is not > data and return it
List* find(List* l, int data) {
    // l != NULL
    List* current = l;
    List* previous = NULL;

    while(current != NULL && current->data > data) {
        previous = current;
        current = current->next;
    }

    return previous;
}

List* insert(List* l, int data) {
    //l != NULL
    List* current = new List();
    current->data = data;

    if(l->data > data) {
        List* insert_position = find(l, data);
        current->next = insert_position->next;
        insert_position->next = current;
    } else {
        current->next = l;
        return current;
    }
    return l;
}

struct List
{
    int data;
    List* next;
};

您实际上并不需要typedefor struct关键字。

上面的示例应该与您要查找的内容接近。正如您所指出的，您的内容存在一些问题。

于 2012-12-11T17:00:51.727 回答
1

结构看起来不错。我试图让insert's 的结构尽可能接近你的结构。我希望评论可以帮助您了解您做错了什么。

bool insert( List & l, int data ) {
    // We have to look sequentially at all members in the *ordered* list
    while ( l != 0 ) {
         // We already have this data, we exit
         if ( l->data == data ) return false;
         // If this element's data is bigger we shift it by one spot
         // so we can insert the new one
         else if ( l->data > data ) {
              List new_element = new E_Type;
              // Save current element in the new one ( that will shift )
              new_element->data = l->data;
              new_element->next = l->next;
              // "Insert" our new element
              l->data = data;
              l->next = new_element;
              return true;
         }
         // If we didn't return before, we skip to the next element
         // but only if it's not the end
         if ( l->next )
             l = l->next;
         else
             break;
    }
    if ( l ) {
        // If we are here it means that all elements are lower than the new data.
        // l currently holds the last element of the list, so we only need to add
        // a new element to the list
        List new_element = new E_Type;
        new_element->data = data;
        new_element->next = 0;
        l->next = new_element;
        return true;
   }
   else {
        // If we are here it means that there was no list to begin with.
        // Thus, we have to create a first element.
        l = new E_Type;
        l->data = data;
        l->next = 0;
        return true;
   }
}
于 2012-12-11T17:06:42.710 回答
1

有很多错误：

l->next = new_list;

这一行擦除了指针的先前值l->next。

没有代码可以寻找合适的元素在之前或之后插入新元素。

您的 while 没有任何意义，因为您的l指针不会随着迭代而变化。

你最好只在纸上写下你的函数应该做的基本步骤，并且只有在用 C++ 对它们进行编码之后。

（或者只是使用来自邻居答案的工作样本;-)）

于 2012-12-11T16:57:15.487 回答
0

我可以看到你是如何陷入困境的。您的insert函数尝试执行多项任务（检查重复项，找到插入新元素的位置并进行实际插入），并且每个任务所需的步骤都变得混乱。

我最好的建议是退后一步，编写三个函数：

  1. 制作检查元素是否已经存在的函数（让我们调用它bool find_element(List l, int data)）。
  2. 创建一个函数，在现有列表的前面插入一个新元素并返回新列表 ( List insert_front(List l, int data))。该函数可以利用 a 的每个元素List也可以被视为列表的头部这一事实。
  3. 创建一个函数来确定在哪里插入一个新元素 ( List locate_insertion_point(List l, int data))。

  4. 根据三个新函数编写你insert的函数。

    bool insert(List& l, int data)
{
    if (find_element(l, data))
        return false;

    List insert = locate_insertion_point(l, data);
    if (insert == NULL)
    { /* Can't insert after any point. Insert at the front */
        List new_list = new E_Type;
        new_list->data = data;
        new_list->next = l;
        l = new_list;
    }
    else
    { /* insert after insert */
        List next = insert->next;
        insert->next = insert_front(next, data);
    }
    return true;
}
于 2012-12-11T17:08:31.807 回答