C++ Сортировка односвязных списков
Эй, у меня проблема с этим проектом, который у меня есть. Я должен читать целые числа из файла и вставлять их в список. Должна быть реализована функция 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 мне кажется правильной, но я могу что-то упустить.
Когда я запускаю код, фактическое чтение файла в первый раз в порядке. Фактически вставка чего-либо в связанный список приводит к зависанию программы.
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;
}
Надеюсь, что это несколько полезно
Поскольку это выглядит как домашнее задание, я дам вам одно исправление:
менять
myList.findSpot(data);
в
spot = myList.findSpot(data);
Если присмотреться, спот используется, но никогда ничего не назначается.
Ну, есть несколько проблем с вашей программой (помимо форматирования). В функции findSpot() у вас есть:
listNode* spot;
spot = listHead;
while (spot->next != 0 && spot->next->value < data) {
spot = spot->next;
}
return spot;
Проблема здесь в том, что при первом вызове listHead имеет значение NULL, поэтому
while (spot->next
собирается потерпеть неудачу, так как пятно NULL.
Я также заметил, что нигде в вашем коде вы не вызываете new(). В listInsert вам нужно использовать new () для инициализации вашей переменной newNode.
И, наконец, у find spot есть 2 условия, при которых он может возвращать NULL. Если список пуст, он должен вернуть NULL, и вы захотите вставить его в начало списка. Если новое значение, которое вы добавляете, больше, чем все остальные, вы также вернете NULL, и вам придется добавить в конец списка.
Поскольку это домашнее задание, я не хочу писать код для вас, но, надеюсь, это поможет.