C++单链表插入排序

Question

所以，嘿，我对我的这个项目有个问题。我应该从文件中读取整数并将它们插入到列表中。有一个findSpot函数需要实现，它遍历链表，如果下一个节点的值大于正在检查的值，它将返回当前的“点”。然后我们将链表输出到一个单独的文件。

这是代码。

#include <iostream>
#include <fstream>
using namespace std;

class listNode {

public:
    int value;
    listNode* next;
    friend class linkedList;

    listNode()
        : value(0)
        , next(NULL)
    {
    }

public:
    ~listNode(){

    };
};

class linkedList {
    listNode* listHead;

public:
    linkedList()
        : listHead(NULL)
    {
    }

    bool isEmpty()
    {
        return (listHead == 0);
    }

    void listInsert(int data, listNode* spot)
    {

        listNode* newNode;
        newNode->value = data;
        newNode->next = NULL;

        if (isEmpty()) {
            listHead = newNode;
        }

        else {
            newNode->next = spot->next;
            spot->next = newNode;
            cout << newNode;
        }
    }

    /*void listDelete ()
    {

    }*/

    listNode* findSpot(int data)
    {
        listNode* spot;
        spot = listHead;

        while (spot->next != 0 && spot->next->value < data) {
            spot = spot->next;
        }

        return spot;
    }

    void printList(listNode* spot)
    {
        listNode* newNode = spot;

        while (newNode != NULL) {
            cout << "Inserting " << newNode->value << ": "
                 << "listHead-->(" << newNode->value << "," << newNode->next->value << ")-->(";
            newNode = newNode->next;
        }

        cout << endl;
    }

    /*~linkedList()
    {
        listNode* temp = spot->next;
        spot->next = spot->next->next;
        delete temp;

    }*/
};

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

    int data;
    listNode* spot;

    ifstream infile;
    infile.open(argv[1]);
    ofstream outfile(argv[2]);

    cout << "Reading Data from the file" << endl;

    while (infile >> data) {
        cout << data << endl;
    }

    infile.close();

    linkedList myList;
    infile.open(argv[1]);

    while (infile >> data) {
        myList.findSpot(data);
        myList.listInsert(data, spot);
        myList.printList(spot);
    }

    cout << "Printing your linked list to the output file.";

    /*while (outfile.is_open())
    {
        myList.printList();

    }*/

    infile.close();
    outfile.close();

    return 0;
}

我不知道问题主要出在insertList函数还是findSpot函数。findSpot函数对我来说似乎是正确的，但我可能只是遗漏了一些东西。

当我运行代码时，第一次实际读取文件是正常的。实际上，在链表中插入任何内容都会导致程序挂起。

Answer 1

好的，让我们再试一次。我实际上会包含一些代码，但请尝试将其作为一个学习点，而不仅仅是复制粘贴的内容。我知道你说你在抄袭你的老师的算法，但他们给你的可能只是一个算法。你的工作是在工作代码中实际实现它，检查错误条件等。

对于函数findSpot：

listNode* linkedList::findSpot(int data) {
  listNode* spot = listHead;  // Initialize spot to start of list

  if ( isEmpty() )    // if list is empty, return NULL
    return NULL;

  // now we know listHead isn't null, so look through the list and
  // find the entry that has a value greater than the one provided
  // return the list item BEFORE the one with the greater value
  while (spot->next != 0 && spot->next->value < data) {
    spot = spot->next;
  }

  // return the one we found;  This could be the same as listHead
  // (start of list), something in the middle, or the last item on the
  // list.  If we return from here, it will not be NULL
  return spot;
}

现在我们可以执行插入函数了：

void linkedList::listInsert(int data, listNode* spot) {

  // We need a new item to put on the list, so create it
  listNode* newNode = new listNode();
  newNode->value = data;
  newNode->next = NULL;

  // If the list is empty, update the head to point at our new object
  if ( isEmpty() ) {
    listHead = newNode;

  // otherwise point spot to new item, and new item to the one spot
  // pointed to
  } else {
    newNode->next = spot->next;
    spot->next = newNode;
  }
}

看看你的打印函数，它会有它自己的问题。看起来你想打印整个列表，但似乎你是从"spot“开始打印的。这一切都很混乱。它在使用newNode->next ->值时也有问题，不检查newNode->next是否为空。这里有一个简短的例子，我认为你正在尝试做什么……注意，我甚至不需要传入spot，只需要添加数据点：

void linkedList::printList(int data) {

  // if some huckleberry called this before calling insert,
  // list will be empty... always a good idea to check
  if ( isEmpty())
    return;

  // first line of output... just print out the data point
  // added and start of output text
  cout << "Inserted " << data << ": " << "listHead-->(";

  // start at start of list
  listNode* newNode = listHead;

  // loop through until we find the end
  while (newNode != NULL) {

    cout << newNode->value;       // print the value
    newNode = newNode->next;      // move to the next item on the list

    // We moved to the next node;  It might be NULL and the loop will end
    // if not, we want to print an open bracket since we know another one
    // is going to be printed
    if ( newNode != NULL )
      cout << ")-->(";
  }

  // last item was just printed, so close off the last bracket
  cout << ")" << endl;
}

希望这能对你有所帮助

Answer 2

由于这看起来像是一项家庭作业，我将给你一个解决方案：

变化

myList.findSpot(data);

至

spot = myList.findSpot(data);

如果你仔细观察，spot会被使用，但从来没有分配过任何东西。

Answer 3

嗯，你的程序有几个问题(除了格式化)。在函数findSpot()中，您有：

listNode* spot;
spot = listHead;

while (spot->next != 0 && spot->next->value < data) {
   spot = spot->next;
}
return spot;

这里的问题是，第一次调用它时，listHead为NULL，因此

while (spot->next

将会失败，因为spot为空。

我还注意到，在您的代码中没有调用new()。在listInsert中，需要使用new()来初始化newNode变量。

最后，find spot有两个条件可以返回NULL。如果列表为空，则应返回NULL，并且您可能希望在列表的开头插入。如果您添加的新值大于所有其他值，则还将返回NULL，并且必须添加到列表的末尾。

由于这是一个家庭作业，我不想为你写代码，但希望这会有帮助。