C++ Singly Linked List Insertion Сортировка

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 является NULL, поэтому

while (spot->next 

собирается на провал, так как пятно НОЛЬ.

Я также замечаю, что нигде в коде вы не называете new(). В спискеInsert вам нужно использовать 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; 
    } 
} 

Глядя на вашу функцию печати, у нее будут свои проблемы.Похоже, вы хотите распечатать весь список, но кажется, что вы начинаете печатать с «пятна». Все это очень смутно. У него также есть проблема с использованием 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; 
} 

Надежда, что несколько полезно