在链表中添加列表项或节点

我尝试使用以下 C++ 代码在从键盘插入值时对链接列表项进行排序。在这里，我想使用 while 循环在一个插入函数的开头、中间和结尾处插入值。我的重点只是如何通过使用逻辑运算找到确切的位置来插入和删除。你能帮我编码一个链表，可以在 C++ 中插入项目时进行排序吗

#include <iostream>
using namespace std;

struct listItem
    {
    //creating a node
    int data;
    struct listItem *next;
    };
//function declaration
bool Initialize(listItem *head);
char menu();
void insertFirst(listItem *&head, listItem *&temp, int item);
void Insert(listItem *&head, listItem *&temp, int item);
void search(listItem *&head, listItem *&temp);
void deleteItem(listItem *&head, listItem *&temp);
void traverse(listItem *curr);

//function definition
bool Initialize(listItem *head)
    {
    //Initialize head and temp value to null
    listItem *head = NULL;
    listItem *temp = NULL;
    }

char menu()
    {
    //menus 
    char choice;
    cout<<"~~~~~~~~~~~~~~~~~~~~~~~~\n";
    cout<<"        Menu"<<endl;
    cout<<"       ........\n";
    cout<<"1. Add an Item\n";
    cout<<"2. Remove an Item\n";
    cout<<"3. Search an Item\n";
    cout<<"4. Traverse an Item\n";
    cout<<"5. Exit\n";
    cout<<"~~~~~~~~~~~~~~~~~~~~~~~~\n";

    cin>>choice;
    return choice;
    }
//function to insert items 
void Insert(listItem *&head, listItem *&temp, int item)
    {
    // check if the linked list is null
    listItem *curr = new listItem;
    if(head == NULL)
        {
        curr->data = item;
        curr->next =NULL;
        temp = curr;
        head = curr;
        }
        //check if linked list is not empty and chose the right location
        else if(head->data > item)
            {
            curr->data = item;
            curr->next = temp->next;
            temp = curr;
            }
        //check if linked list is not empty and chose the right location
        else if(head->data < item && curr->next != NULL)
            {
            while (curr->data < item)
            curr = curr->next;
            temp->next = curr;
            curr->data = item;
            curr->next = temp;
            temp = curr;
            }
        //check if linked list is not empty and chose the right location
        else if(head->data < item)
            {
            while(head->data < item && curr->next == NULL)
            curr = curr->next;
            curr->data = item;
            curr->next = NULL;
            temp = curr;
            }
        else
            cout<<item<<" is already there!!!\n";
    }

void search(listItem *&head, listItem *&temp)
    {
    cout<<"NO code for searching item"<<endl;
    }
void deleteItem(listItem *&head, listItem *&temp)
    {
    if(Initialize(head))
        cout<<"The list is already Empty\n";
    else if(head == temp)
        {
        delete head;
        head = NULL;
        temp = NULL;
        }
    else
        {
        listItem *curr = new listItem;
        head = head->next;
        delete curr;
        }
    }
void traverse(listItem *curr)
    {
    if(Initialize(curr))
        cout<<"The list is already Empty\n";
    else
        {
        cout<<"The list contains:\n";
        while(curr != NULL)
            {
            cout<<curr->data<<endl;
            curr = curr->next;
            }
        }
    }

int main()
    {

    bool Initialize(head)

    char choice;
    int item;
    do
        {
        choice = menu();
        switch(choice)
            {
            case '1': cout<<"Please enter a number :";
                    cin>>item;
                    Insert(head, temp, item);
                    break;
            case '2': //cout<<"Enter a number to delete :";
                    //cin>>item;
                    deleteItem(head, temp);
                    break;
            case '3': search(head, temp);
                    break; 
            case '4': traverse(head);
                    break;
            default: cout<<"System exit\n";
            }
        }
        while(choice != '5');
        return 0;
    }

插入节点。首先...代码！

#include <iostream>

struct listItem
    {
    //creating a node
    int data;
    struct listItem *next;
    };

//function to insert items
void Insert(listItem *&head, int item)
    {
    listItem **curr = &head; // start at head
    while (*curr != NULL // while there is a node
            && (*curr)->data <= item ) //  and the node goes before the new node
        {
        curr = &(*curr)->next; // get next node
        }
    *curr = new listItem{item, *curr}; // insert the new node
    }

int main()
    {

    listItem * head = NULL; // empty linked list head

    Insert(head, 1); // test insert to empty list
    Insert(head, 0); // insert at head
    Insert(head, 3); // insert at end
    Insert(head, 2); // insert in the middle
    }

我删除了所有不必要的代码，以专注于插入逻辑。您应该始终针对堆栈溢出问题执行此操作。为了降低问题中的噪音，请创建一个简单的程序来说明问题，而不执行其他操作。读最小可重复示例 https://stackoverflow.com/help/minimal-reproducible-example获取更多信息和灵感。

代码几乎是不言自明的：循环遍历列表，直到找到插入节点的位置，然后插入节点，但有两个小技巧。

有的是head节点并且有next节点。两者都执行相同的工作：指向列表中的下一个节点。由于它们有不同的名称，我们需要不同的代码来处理它们。但如果我们可以使head和所有的next节点具有相同的名称？然后他们就可以拥有完全相同的代码。那是curr的工作。现在没关系curr is head or a next。该函数的大部分代码都......消失了。不存在的代码就没有错误。

插入单链表的另一个问题是，如果您迭代到需要在前面插入的节点，那么您就会失去对之前节点的跟踪。要维持链接，您必须拥有前一个节点的next指针（或head）。您可以维护指向前一个节点的指针，但这不适用于head因为没有head节点，所以你破坏了第一个技巧并最终得到一些几乎重复的代码。但是如果你抽象出节点并存储地址head or the next指针将两部分信息合而为一：插入点和插入点之后的节点。和

listItem **curr;

curr指向我们想要放置新节点的位置*curr是它后面的节点。所以

while (*curr != NULL // while there is a node
        && (*curr)->data <= item ) //  and the node goes before the new node
    {
    curr = &(*curr)->next; // get next node
    }

遍历列表直到找到列表中的最后一个节点，*curr is NULL，或数据*curr走到我们要插入的节点之后，然后

*curr = new listItem{item, *curr};

创建一个链接到后面的节点的新节点，并将该新节点分配给插入点处的指针。

*curr，指向列表中下一项的指针，被设置为指向new listItem，就像任何其他使用一样new.

扭曲的是listItem是一个非常简单的数据结构，可以利用聚合初始化 https://en.cppreference.com/w/cpp/language/aggregate_initialization初始化listItem的成员。大括号包含我想要的新值listItem按照它们在结构中声明的顺序。第一个成员变量，data， 被设定为item第二个，next，设置为当前值*curr，列表中的下一项。

在一小段时间里，你将拥有*curr和next新的listItem指着同一个listItem那么=运营商更新*curr指向新创建的listItem反而。

把它画在一张纸上，你就会看到发生了什么。