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

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

0 голосов
/ 07 февраля 2020

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

MAIN 

#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

Ответы [ 2 ]

0 голосов
/ 07 февраля 2020

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

while ((traverse->next != NULL)){
  if(traverse->data < newPtr->data)){
    traverse = traverse->next;
  }
  else{
    traverse->prev->next = newPtr;
    newPtr->next = traverse;
    break;
  }
}
0 голосов
/ 07 февраля 2020

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

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

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 */ }
...