0

二重リンクリストを作成しました：

class doubled {
private:
  class sublink {
  private:
    char data[30];
    sublink *next_ptr;
    sublink *previous_ptr;
    friend doubled;
  };
public:
  sublink *first_ptr;
  doubled(){first_ptr = NULL;};
  void add_item(char *item);
  void rm_item(char *item);
};

問題は、リストにアイテムを追加する関数にあります。

void doubled::add_item(char *item){
  sublink *new_data;
  sublink *n_insert;
  sublink *p_insert;
  new_data = new sublink;
  n_insert = new sublink;
  p_insert = new sublink;

  if(first_ptr == NULL){
    strcpy(new_data->data, item);
    new_data->previous_ptr = NULL;
    new_data->next_ptr = first_ptr;
    first_ptr = new_data;
  } else {
    strcpy(new_data->data, item);
    n_insert = first_ptr;
    while(1){
      n_insert = n_insert->next_ptr;

      if(n_insert == NULL)
        break;

      if(strcmp(n_insert->data, new_data->data) >= 0){
        new_data->next_ptr = n_insert;
        n_insert->previous_ptr = new_data;
      }
    }
    p_insert = first_ptr;
    while(1){
      p_insert = p_insert->next_ptr;

      if(p_insert == NULL)
        break;

      if((strcmp(p_insert->data, new_data->data)) < 0){
        new_data->previous_ptr = p_insert;
        p_insert->next_ptr = new_data;
      }
    }
  }

  std::cout << first_ptr->data << '\n';
  std::cout << new_data->data << '\n';
  if(new_data->next_ptr != NULL)
    std::cout << new_data->next_ptr->data << '\n';
}

上記のコードは、特定の項目をアルファベット順にリストに挿入します。

プログラムは と を出力しfirst_ptr->dataますが、 も もnew_data->data出力しません。したがって、ステートメントは常に真であり、そうであってはなりません。new_data->next_ptr->datafirst_ptr->next_ptr->dataif(new_data->next_ptr != NULL)

誰かがこのプログラムの問題を認識していますか?

4

1 に答える 1

0

おそらく、前または次の ptr を NULL に設定するのを忘れたことが原因です。

ここで、ロジックを少し修正し、segfault を取り除きました (チェック対象の各ケースについて、できる限りコメントを付けようとしました)。

#include <iostream>
#include <string.h>

class doubled 
{
private:
    class sublink 
    {
    private:
        char data[30];
        sublink *next_ptr;
        sublink *previous_ptr;
        friend doubled;
    };

public:
    sublink *first_ptr;
    doubled(){first_ptr = NULL;};
    void add_item(char *item);
    void rm_item(char *item);
};

void doubled::add_item(char *item)
{
    sublink *new_data;
    new_data = new sublink;

    strcpy(new_data->data, item);

    // empty list case
    if(first_ptr == NULL)
    {
        // Only item in the list, I have no next or previous element
        new_data->previous_ptr = NULL;
        new_data->next_ptr = NULL;

        // Make the list point to this element
        first_ptr = new_data;
    } 
    else 
    {
        sublink* iter;
        iter = first_ptr;

        // 1 element list
        if(iter->next_ptr == NULL)
        {
            // I'm after the first and only node
            if(strcmp(iter->data, new_data->data) <= 0)
            {
                iter->next_ptr = new_data;
                new_data->previous_ptr = iter;
                new_data->next_ptr = NULL;
            }
            // I'm before the first and only node and thefore I become the new first
            else
            {
                iter->previous_ptr = new_data;
                new_data->next_ptr = iter;
                first_ptr = iter;
            }
        }
        // 2+ element list
        else
        {
            // this is never null the first time because empty list case is take care of above
            while(iter != NULL)
            {
                // Should I be inserted before the current node?
                if(strcmp(iter->data, new_data->data) >= 0)
                {
                    // first node case
                    if(iter->previous_ptr == NULL)
                    {
                        new_data->previous_ptr = NULL;
                        new_data->next_ptr = iter;
                        iter->previous_ptr = new_data;
                        first_ptr = new_data;

                    }
                    // intermediate node case
                    else if(iter->next_ptr != NULL)
                    {
                        iter->previous_ptr->next_ptr = new_data;
                        new_data->previous_ptr = iter->previous_ptr;
                        new_data->next_ptr = iter;
                        iter->previous_ptr = new_data;
                    }
                    // last node case
                    else
                    {
                        iter->next_ptr = new_data;
                        new_data->previous_ptr = iter;
                        new_data->next_ptr = NULL;
                    }

                    break;
                }

                // Move to next node
                iter = iter->next_ptr;
            }
        }
    }

    // Print the list
    std::cout << "List: " << std::endl;
    sublink* printer = first_ptr;
    while(printer != NULL)
    {
        std::cout << '\t' << printer->data << std::endl;

        printer = printer->next_ptr;
    }
    std::cout << std::endl;
}

int main(int argc, char* argv[])
{
    doubled d;

    char item[30] = "bla bla bla\0";
    char item2[30] = "meh\0";
    char item3[30] = "ahhhhhhhh\0";
    char item4[30] = "dayummmmm\0";
    d.add_item(item);
    d.add_item(item2);
    d.add_item(item3);
    d.add_item(item4);

    std::cin.get();
    return 0;
}

ここで結果を確認できます: http://ideone.com/EAzsPZ

于 2013-06-21T22:34:29.633 に答える