Вставка нового узла в односвязный список при сохранении сортировки - PullRequest
Новая
       23

Вставка нового узла в односвязный список при сохранении сортировки

0 голосов
/ 31 января 2019

Я очень нуб и изо всех сил пытаюсь правильно внедрить вставку нового узла в односвязный список.Я попробовал некоторые из более простых для понимания решений как здесь, так и с других сайтов, и проблема определенно у меня в голове, но я просто не могу понять, как это правильно.

Так что яИмеется ли этот связанный список, состоящий из n узлов (где n задается пользователем как ввод), где я пытаюсь вставить случайные числа от 0 до 100 в возрастающем порядке, а затем я печатаю содержимое списка.

Я думаю, что мой код не совсем правильный, хотя, потому что вывод, который я получаю, это просто одно и то же число снова и снова, но кроме этого, если я изменю код, чтобы позволить пользователю вводить числа вместо генерациислучайным образом происходит сбой программы, если я ввожу два разных числа (это работает нормально, если я ввожу одно и то же число снова и снова).РЕДАКТИРОВАТЬ: Кроме того, если только srand (время (NULL));записывается внутри цикла, программа компилируется, но завершается сбоем, как только я ввожу количество элементов в моем списке.

Я действительно не могу понять, что я делаю не так.

Код выглядит так: 

/*The program inserts n elements generated randomly in a linked list sorted increasingly, and prints the result.*/

#include <iostream>
#include <cstdlib>
#include <ctime>

using namespace std;

struct node {
    int num;
    node *next;
};
node *top=NULL,*nodenew;

void sortedinsert();
void printlist();

int main() {
    int n;
    do {
        cout<<"Insert the amount of elements in your list: ";
        cin>>n;
        if (n<2) {
            cout<<"The list needs to contain at least 2 nodes."<<endl;
        }
    }
    while (n<2);
    for (int i=0;i<n;i++) {
        srand(time(NULL));
        sortedinsert();
    }
    printlist();
}

void sortedinsert() {
    int gen=rand()%101;
    nodenew=new node;
    nodenew->num=gen;
    nodenew->next=NULL;
    if (top==NULL or top->num>=gen) {
        nodenew->next=top;
        top=nodenew;
        return;
    }
    else if (top->next!=NULL and top->next->num>=gen){
        node *temp=top->next;
        nodenew->next=temp;
        top->next=nodenew;
        return;
    }
    else {
        node *left;
        node *right=top;
        while (right!=NULL and right->next->num<=gen) {
            left=right;
            right=right->next;
        }
        left->next=nodenew;
        nodenew->next=right;
    }
}
void printlist() {
    cout<<"The sorted list is shown below: "<<endl;
    for (nodenew=top;nodenew!=NULL;nodenew=nodenew->next) {
        cout<<nodenew->num<<endl;
    }
}

Ответы [ 2 ]

0 голосов
/ 31 января 2019

На самом деле srand (time (NULL)) вы должны объявить его перед циклом for, потому что так он дает одинаковое число.И у вас есть проблема при вставке нового узла.

И вот я исправил ваш код, и он хорошо работает: 

#include <iostream>
#include <cstdlib>
#include <ctime>

using namespace std;

struct node {
    int num;
    node *next;
};
node *top = NULL, *nodenew;

void sortedinsert();
void printlist();

int main() {
    int n;

    do {
        cout << "Insert the amount of elements in your list: ";
        cin >> n;
        if (n<2) {
            cout << "The list needs to contain at least 2 nodes." << endl;
        }
    } while (n<2);

    srand(time(NULL));
    for (int i = 0; i<n; i++) {


        sortedinsert();
    }
    printlist();

    system("pause");
}

void sortedinsert() {


    int gen = rand() % 101;
    cout << gen << endl;
    nodenew = new node;
    nodenew->num = gen;
    nodenew->next = NULL;
    if (top == NULL || top->num >= gen) {
        nodenew->next = top;
        top = nodenew;

    }
    else
    {
        node *A = top;
        node *B = top->next;
        while (B != NULL)
        {
            if (B->num > gen)
            {
                nodenew->next = B;
                A->next = nodenew;
                return;
            }
            else
            {

                A = B;
                B = B->next;
            }
        }
        A->next = nodenew;
        nodenew->next = NULL;
        return;
    }
}
void printlist() {
    cout << "The sorted list is shown below: " << endl;
    nodenew = top;

    for (nodenew = top; nodenew != NULL; nodenew = nodenew->next) {
        cout << nodenew->num << endl;
    }
}
0 голосов
/ 31 января 2019

Я прокомментировал части, которые я изменил :) 

int main() {
    int n; // as mentioned in top srand initialized at the begining 
    srand(time(NULL));

    do {
        cout << "Insert the amount of elements in your list: ";
        cin >> n;
        if (n < 2) {
            cout << "The list needs to contain at least 2 nodes." << endl;
        }
    } while (n < 2);
    for (int i = 0;i < n;i++) {
        sortedinsert();
    }
    printlist();
}

void sortedinsert() {
    int gen = rand() % 101;
    nodenew = new node;
    nodenew->num = gen;
    nodenew->next = NULL;
    // split the top part
    if (top == NULL) {

        top = nodenew;
        return;
    }
    if( top->num >= gen) {
        nodenew->next = top;
        top = nodenew;
        return;
    }

    else if (top->next != NULL and top->next->num >= gen) {
        node *temp = top->next;
        nodenew->next = temp;
        top->next = nodenew;
        return;
    }
    else {
        // left was uninitialized so if it doesn't go into the loop you are going to call left->next  Undefined behavior
       //right->next->num<=gen you don't test this until you test right->next is not null otherwise Undefined behavior as well
        node *left=top;
        node *right = top->next;

        while (right != NULL and right->num <= gen) {
            left = right;
            right = right->next;
        }       


            left->next = nodenew;
            nodenew->next = right;


    }
}
...