Как я могу вставить узлы связанного списка в числовом порядке?

Я очень близок к выполнению этого школьного задания по связанному списку, но у меня проблемы с самой последней функцией. Цель этой функции — взять числа, прочитанные из текстового файла, и поместить их в связанный список в порядке номеров. Я попытался добраться до того места, где он проходит через список, и узел добавляется всякий раз, когда значение больше предыдущего числа, но достиг ошибки сегментации. Я застрял на этом в течение смущающе долгого времени и был бы признателен за чью-либо помощь. Ниже приведены файлы, с которыми я работаю, и ужасный беспорядок функции с именем insertStrategic, которая должна получить список в порядке номеров.

ГЛАВНОЕ

#include "linkedlist.h"
#include <iostream>
#include <stdio.h>
#include <stdlib.h>


using namespace std;

int main (){

    NodePtr newNode = NULL;

    // after you implemented your functions in .cpp file 
    // - use the code below for testing your linked list. 
    // Demonstrate that ALL functions are working correctly.

    // After that add code for reading data from input file.
    // Every time you read an integer, create a node and insert it
    // in the ascending order into the list.

    int num;

    FILE *fptr;

    // make sure file exists, give message and exit otherwise
        if ((fptr = fopen("input.txt","r")) == NULL){
            printf("Error! opening file");
            exit(1);
        }

    // while we still have items to read
        while( fscanf(fptr,"%d", &num) != EOF){
            newNode = makeNewNode(num);
            insertStrategic(newNode);
    }

    fclose(fptr);  // close the file  

    // At the end print the entire list to show that your code 
    // functions correctly.



    printList();

    cout << "After DeleteFromFront: " << endl; 
    deleteFromFront();
    printList();

    NodePtr seven = makeNewNode(7);     
    insertAtEnd(seven);
    cout <<"Inserting seven at END" << endl;
    printList();

    NodePtr eight = makeNewNode(8);     
    insertAtEnd(eight);
    cout <<"Inserting eight at END" << endl;
    printList();

    cout << "After deleting eight: " << endl; 
    deleteFromEnd();
    printList();

    cout << "After deleting seven:" << endl;
    deleteFromEnd();
    printList();



  return 0;
}

ФАЙЛ СВЯЗАННОГО СПИСКА

#include "linkedlist.h"
#include <stdlib.h>
#include <iostream>


using namespace std;

   NodePtr head = NULL;
   NodePtr tail = NULL;


bool isEmpty(){
   return (head == NULL);
}

NodePtr makeNewNode(int number){
   NodePtr newNode = (NodePtr) malloc(sizeof(Node));
   if(newNode != NULL){
      newNode->data = number;
      newNode->next = NULL;
   }
   return newNode;
}

void insertAtFront(const NodePtr newPtr){
    if (isEmpty()){
        head = newPtr;
        tail = newPtr;
   }
   else{ // not empty
        newPtr->next = head;
        head = newPtr;
   }

}

void insertAtEnd(const NodePtr newPtr){

    NodePtr end = head;
    newPtr->next = NULL;

        while (end->next != NULL){
            end = end->next; 
        }

        end->next = newPtr; 
}



void insertStrategic(const NodePtr newPtr){

        if (isEmpty()){
            head = newPtr;
            tail = newPtr;
        }
        else {
            NodePtr traverse = head;
            newPtr->next = NULL;

                while ((traverse->next = NULL)){
                    while ((traverse->data < newPtr->data)){
                        traverse = traverse->next;
                    }
                    traverse = traverse->prev;
                    traverse->next = newPtr;
                    break;
                }
        } 
}   

void deleteFromFront( ){

    NodePtr temp = head;
    head = head->next;

}

void deleteFromEnd( ){

    NodePtr temp = head;
    NodePtr secTemp;

        while(temp->next != NULL) {
            secTemp = temp;
            temp = temp->next;
        }

        free(secTemp->next);
        secTemp->next = NULL;  
}



void printList( ){
   if (isEmpty()){
     cout << "List is empty" << endl;
   }
   else {
     NodePtr temp = head;
     while (temp != NULL){
       cout << " The data is: " << temp->data << endl;
       temp = temp->next;
     }
   }
}

ЗАГОЛОВОЧНЫЙ ФАЙЛ

#ifndef MYLIST_H
#define MYLIST_H

#include <cstddef>

   struct listNode {
        int data;
        struct listNode* prev;
        struct listNode* next;
   };

   typedef struct listNode Node;
   typedef Node* NodePtr;


   static int nodeCount = 0;

   bool isEmpty();
   NodePtr makeNewNode(int); 

   void insertAtFront(const NodePtr);
   void insertAtEnd(const NodePtr);
   void insertStrategic(const NodePtr);

   void deleteFromFront( );
   void deleteFromEnd( );

   void printList();


#endif

ТЕКСТОВЫЙ ФАЙЛ ДЛЯ ЧТЕНИЯ

3
5
11
2
7
1
65
12
3
45
6

person Community    schedule 07.02.2020    source источник
comment
Тщательно обдумайте условие в while ((traverse->next = NULL)). (Если вы добавили круглые скобки, чтобы избавиться от предупреждения компилятора, вам следует пересмотреть этот выбор. Предупреждение было важным.)   -  person molbdnilo    schedule 07.02.2020
comment
Вероятно, вам следует инициализировать node->prev значением null (или реализовать конструктор и использовать new вместо malloc), на самом деле вы вообще никогда не устанавливаете prev   -  person Alan Birtles    schedule 07.02.2020
comment
Пожалуйста, никогда не вводите указатели typedef. Это плохая практика, все, чего вы достигаете, это сокрытие информации без какой-либо пользы; аналогично using namespace std...   -  person Aconcagua    schedule 07.02.2020
comment
Вы отметили свой вопрос C++. Почему бы вам просто не назвать свою структуру Node? Тогда вам не нужен этот typedef. struct Node { Node* prev; Node* next; }; полностью допустимо в C++ (в отличие от C, где вам нужно ключевое слово struct...).   -  person Aconcagua    schedule 07.02.2020
comment
О дизайне: вы можете подумать о добавлении хвостового указателя в свой список, тогда вам не придется перебирать весь список, чтобы добавить новые узлы. Таким образом, вы можете реализовать только один связанный список. Может быть, вы хотите сделать класс LinkedList? Тогда вы можете иметь несколько списков одновременно. Все те функции, которые у вас сейчас есть как автономные, получат функции-члены, например: class LinkedList { Node* head; Node* tail; public: void insertAtFront(Node const* ptr); /*... */ };   -  person Aconcagua    schedule 07.02.2020
comment
Между прочим, вы доставили немало проблем с указателем typedef: void insert(const NodePtr) эквивалентно void insert(Node* const), неvoid insert(Node const*), т.е. е. только указатель является константой, не объект, на который указывает (предположительно, это то, что вы на самом деле хотели...). Кроме того, было бы лучше просто передать данные (в данном случае int) и создать узлы внутри функции...   -  person Aconcagua    schedule 07.02.2020
comment
Вы должны предпочесть ключевые слова C++ (nullptr) старым (устаревшим?) макросам C (NULL).   -  person Aconcagua    schedule 07.02.2020
comment
Присоединение к @AlanBirtles (new + конструктор вместо malloc): кроме того, вы больше никогда не free свои узлы, поэтому вы ввели утечку памяти...   -  person Aconcagua    schedule 07.02.2020
comment
@Aconcagua Честно говоря, я первокурсник информатики, просто выполняю задание. Устаревшие ключевые слова, указатели typedef и недостатки пространства имен std полезно знать, но они являются лишь частью кода, который был предоставлен мне для самого задания. Мне дали около 70% кода и сказали реализовать функции, чтобы заставить программу работать. На мой взгляд, это не лучший способ учить студентов, но это то, где я нахожусь, лол.   -  person    schedule 07.02.2020
comment
'полезно знать' – и это на самом деле было единственной целью моих комментариев, так что, пожалуйста, не чувствуйте себя критикой... Я очень согласен с вашим 'не самым лучшим образом ', тем более, что код, который вам предоставили, довольно плохой C++. Больше похоже на C-код, приправленный небольшим количеством C++... И вы могли бы представить учителю мою последнюю заметку о typedef для указателя (там, где константность идет не так, как надо, и это было бы неправильно даже в C! ), потому что это очень важно.   -  person Aconcagua    schedule 07.02.2020


Ответы (2)


Ниже следует простое решение, возможно, не самое лучшее, но работающее. Эта функция будет вставлять элементы в порядке возрастания.

Обратите внимание, что мы не обновляем «хвост» списка в этой функции.

void insertOrdered(const NodePtr newPtr){
        if (isEmpty()){
            head = newPtr;
            return;
        }

        NodePtr lastNode, whereToInsert = head;

        while (whereToInsert){
            if (whereToInsert->data > newPtr->data){
                break;
            }
            lastNode = whereToInsert;
            whereToInsert = whereToInsert->next;
        }

        if (whereToInsert == head){
            newPtr->next = head;
            head->prev = newPtr;
            head = newPtr;
        }
        else if (whereToInsert) {
            newPtr->next = whereToInsert;
            whereToInsert = whereToInsert->prev;
            newPtr->prev = whereToInsert;
            whereToInsert->next = newPtr;
        }
        else {
            lastNode->next = newPtr;
            newPtr->prev = lastNode;
        }
}

Кроме того, пожалуйста, избегайте использования такого кода, как:

if ((fptr = fopen("input.txt","r")) == NULL){

Вместо этого используйте отдельные строки кода:

fptr = fopen("input.txt","r")
if (fptr == NULL){ /* your stuff */ } 
person André Caceres    schedule 07.02.2020

Вы можете написать что-то подобное в insertStrategic(); 2 раза пока не нужно

while ((traverse->next != NULL)){
  if(traverse->data < newPtr->data)){
    traverse = traverse->next;
  }
  else{
    traverse->prev->next = newPtr;
    newPtr->next = traverse;
    break;
  }
} 
person Humble_Aspirant    schedule 07.02.2020