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

因爲這看起來像一個家庭作業，我想給你一個修復：

變化

myList.findSpot(data); 

到

spot = myList.findSpot(data); 

如果你仔細觀察，用點，但從未分配過任何東西。

Answer 2

那麼，你的程序有幾個問題（格式除外）。在功能findSpot（），您可以：

listNode* spot; 
spot = listHead; 

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

這裏的問題是，你第一次調用該方法，從ListHead是空的，所以

while (spot->next 

是要失敗的，因爲斑空值。

我還注意到，你的代碼中沒有地方叫new（）。在listInsert中，你需要使用new（）來初始化你的newNode變量。

最後，發現點有2個條件，它可以返回NULL。如果列表爲空，則它應該返回NULL，並且您希望在列表的開始處插入。如果您添加的新值大於其他值，則您也將返回NULL，並且您必須將其添加到列表的末尾。

由於這是一項家庭作業，我不想爲你編寫代碼，但希望這有助於。

Answer 3

好的，讓我們再試一次。我實際上會包含一些代碼，但請嘗試將此用作學習點，而不是僅僅複製粘貼。我知道你說過你在複製你的老師算法，但是他們給你的東西可能就是這個算法。這是你的工作，真正落實在工作代碼，檢查錯誤條件等。總之，在這裏我們去：

對於功能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-> value，而不檢查newNode-> next是否爲NULL。這裏是什麼，我認爲你正在嘗試做的...請注意，我甚至都不需要在現場通過一個簡單的例子，只是數據點補充說：

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; 
} 

希望這是有點用