以排序方式在单循环链表中插入元素

Question

我想创建一个程序，它以排序的方式将数据插入单循环链表中（给定指向最后一个元素的指针）。我已经编写了代码，尝试对其进行调试，但实际上找不到问题所在。我得到的输出是 5个 6 6 7 7 7 9 9 9

#include <iostream>

using namespace std;
//structure for list
class Node{
public:
    int val;
    Node* next;
};
//function to add new node and data
Node* insertnode(Node** l,int data){
    Node *new_node, *temp;
    new_node = new Node;
    new_node->val = data;
//if list is empty
    if(*l == nullptr){
        new_node->next = new_node;
        *l = new_node;
        return *l;
    }
//if new element value is greater than last
    if(((*l)->val)<(new_node->val)){
        new_node->next = (*l)->next;
        (*l)->next = new_node;
        *l = new_node;
        return *l;
    }
    temp = (*l)->next;
//if new element value is low than last 
    if(((*l)->val)>(new_node->val)){
        while(temp!=*l){
                if(temp->val>=new_node->val){
                    break;
                }
            temp = temp->next;
        }
        new_node->next = temp->next;
        temp->next = new_node;
        }
    return (*l);
}

void displaylist(Node *l){
    Node* last = l->next;
    do{
        cout<<l->val<<" ";
        last = last->next;
    }while(last->next != l);
    cout<<endl;
}

int main()
{
    Node* last = nullptr;
    last = insertnode(&last, 5);
    displaylist(last);
    last = insertnode(&last, 6);
    displaylist(last);
    last = insertnode(&last, 7);
    displaylist(last);
    last = insertnode(&last, 5);
    displaylist(last);
    last = insertnode(&last, 9);
    displaylist(last);
}

Answer 1

让我们一起走走displaylist

void displaylist(Node *l){
    Node* last = l->next; // points at first node. Sounds OK
    do{
        cout<<l->val<<" "; // always print last node. Doesn't seem like a good idea
        last = last->next; //advance one node. Sounds OK
    }while(last->next != l); // loop until the node after the next node is back to the last node
                             // Looks past at least one node
    cout<<endl;
}

首先，我们更改了一些标识符，以便它们更能描述它们真正代表的内容

void displaylist(Node *last){ // l is the last node
    Node* current = last->next; //current is a better name for the item we're looking at
    do{
        cout<<last->val<<" "; 
        current = current->next; 
    }while(current->next != last);
    cout<<endl;
}

现在我们开始通过打印出我们正在迭代的项目而不是一遍又一遍地打印第一个项目来解决问题。

void displaylist(Node *last){
    Node* current = last->next;
    do{
        cout<<current->val<<" "; // print out the item we're iterating
        current = current->next; 
    }while(current->next != last);
    cout<<endl;
}

现在我们要做的是在下一个要打印的项目再次成为第一个时停止，即 last->next

void displaylist(Node *last){
    Node* current = last->next;
    do{
        cout<<current->val<<" "; 
        current = current->next; 
    }while(current != last->next); 
    cout<<endl;
}

应该差不多了。

以排序方式在单循环链表中插入元素

Inserting a element in a singly circular linked list in sorted manner

c++

linked-list

codeblocks

singly-linked-list