在保持排序的情况下在单链表中插入一个新节点

Question

我是一个菜鸟，我正在努力正确地实现在单链表中插入新节点。我已经从这里和其他网站尝试了一些更容易理解的解决方案，问题肯定在我的脑海中，但我就是无法做到这一点。

所以我所拥有的是这个由 n 个节点组成的链表（其中 n 作为用户的输入给出），我试图在其中按递增顺序插入从 0 到 100 的随机数，我正在然后打印列表的内容。

我认为我的代码一点也不正确，因为我得到的输出一遍又一遍都是相同的数字，但除此之外，如果我更改代码以允许用户输入数字而不是生成数字随机地，如果我输入两个不同的数字，程序就会崩溃（如果我一遍又一遍地输入相同的数字，它就可以正常工作）。编辑：此外，除非 srand(time(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;
    }
}

Answer 1

我已经评论了我更改的部分:)

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;


    }
}

Answer 2

实际上 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;
    }
}

Answer 3

您可以使用 Python 代码，如下所示。 Python 的好处是：

--> 现在很多行业都在使用它，在你探索数据科学和机器学习领域时会有所帮助。

--> 就像实现伪代码一样简单。

我已经向你展示了python向排序双向链表插入节点的方法，尝试获取Dry-运行代码并获取逻辑，然后使用相同的方法进行推导单链表的代码。

def sortedInsert(head, data):
node = DoublyLinkedListNode(data)
status = 0
if not data>head.data:
    node.prev=head.prev
    head.prev=node
    node.next=head
    head=node
else:
    dup = head
    while(data>dup.data):
        if not dup.next:
            status = 1
            break
        else:
            dup = dup.next
    if status:
        node.prev = dup
        node.next = dup.next
        dup.next = node
    else:
        node.prev = dup.prev
        dup.prev.next = node
        node.next = dup
        dup.prev = node
return head

在保持排序的情况下在单链表中插入一个新节点

Inserting a new node in a singly-linked list while maintaining the sorting

c++

sorting

linked-list

list

singly-linked-list