问题描述

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

I try the following c++ code to sort linked list Items while inserting value from the keyboard. Here I want to insert values at the beginning, somewhere in the middle and at the end in one Insertion function using while loop. my focus is only on how to insert and delete by finding the exact position using logical operations. Could you please help me in coding a linked list that can sort while inserting an item in 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<<"~~~~~~~~~~~~~~~~~~~~~~~~
";
    cout<<"        Menu"<<endl;
    cout<<"       ........
";
    cout<<"1. Add an Item
";
    cout<<"2. Remove an Item
";
    cout<<"3. Search an Item
";
    cout<<"4. Traverse an Item
";
    cout<<"5. Exit
";
    cout<<"~~~~~~~~~~~~~~~~~~~~~~~~
";

    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!!!
";
    }

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
";
    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
";
    else
        {
        cout<<"The list contains:
";
        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
";
            }
        }
        while(choice != '5');
        return 0;
    }

推荐答案

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

Inserting nodes. First... The code!

#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
    }

我删除了所有不必要的代码，专注于插入逻辑.您应该始终使用堆栈溢出问题来执行此操作.为了减少问题中的噪音，创建一个简单的程序来说明问题而不做其他事情.阅读最小可重现示例以获取更多信息和灵感.

I've removed all of the unnecessary code to focus on the insertion logic. You should always do this with a stack overflow question. To keep the noise in the question down, create a simple program that illustrates the problem and does nothing else. Read minimal reproducible example for more information and inspiration.

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

The code is almost self explanatory: Loop through the list until we find where to insert the node and then insert the node, but there are two little tricks.

有 head 节点和 next 节点.两者都做同样的工作:指向列表中的下一个节点.由于它们有不同的名称，我们需要不同的代码来处理它们.但是，如果我们可以让 head 和所有 next 节点具有相同的名称呢?然后他们可以拥有完全相同的代码.那是 curr 的工作.现在，curr 是 head 还是 next 并不重要.该函数的大部分代码只是......消失了.不存在的代码没有错误.

There's the head node and there are next nodes. Both do the same job: Point to the next node in the list. Since they have different names, we need different code to deal with them. But what if we could make head and all of the next nodes have the same name? Then they can have the exact same code. That's curr's job. Now it doesn't matter if curr is head or a next. Most of the function's code just... goes away. And code that doesn't exist has no bugs.

插入单向链表的另一个问题是，如果您迭代到需要提前插入的节点，您将失去对它之前的节点的跟踪.要保持链接，您必须拥有前一个节点的next 指针(或head).您可以维护一个指向前一个节点的指针，但这不适用于 head，因为没有 head 节点，因此您破坏了第一个技巧并以一些几乎重复的代码.但是，如果您抽象出节点并存储 head 或 next 指针的地址，您将获得两条信息合二为一:插入点和插入后的节点观点.随着

The other problem with inserting into a singly linked list if you iterate to the node you need to insert ahead of, you've lost track of the node before it. To maintain the linkage you have to have the previous node's next pointer (or the head). You can maintain a pointer to the previous node, but this doesn't work with head since there is no head node, so you ruin the first trick and wind up with some nearly duplicated code. But if you abstract away the node and and store the address of head or the next pointer you have two pieces of information in one: The insertion point and the node after the insertion point. With

listItem **curr;

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

curr points to where we want to place the new node and *curr is the node after it. So

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 是 NULL，或者 *curr 处的数据在我们要插入的节点之后，然后

Works through the list until we find either the last node in the list, *curr is NULL, or the data at *curr goes after the node we want to insert, and then

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

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

creates a new node that is linked to the node that goes after and this new node is assigned to the pointer at the insertion point.

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

*curr, the pointer to the next item in the list, is set to point at a new listItem, just like any other use of new.

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