c++ - 在链表中添加列表项或节点

问题描述

我尝试使用以下 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;
    }

标签： c++sortingdata-structureslinked-listinsert

解决方案

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

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

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

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

有head节点，也有next节点。两者都做同样的工作：指向列表中的下一个节点。由于它们有不同的名称，我们需要不同的代码来处理它们。但是，如果我们可以使head所有next节点都具有相同的名称呢？然后他们可以拥有完全相同的代码。那curr是工作。现在无论curr是 ishead还是 a都没有关系next。大多数函数的代码只是......消失了。不存在的代码没有错误。

如果您迭代到需要提前插入的节点，则插入单链表的另一个问题是，您已经丢失了对它之前的节点的跟踪。要保持链接，您必须拥有前一个节点的next指针（或head）。您可以维护指向前一个节点的指针，但这不起作用，head因为没有head节点，因此您破坏了第一个技巧并以一些几乎重复的代码结束。但是，如果您抽象出节点并存储地址head或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
    }

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

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

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

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

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

对于一个很小的时间实例，您将拥有*curr和next新的listItem指向相同listItem的，然后=操作员更新*curr指向新创建的指向listItem。

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

c++ - 在链表中添加列表项或节点

问题描述

解决方案

推荐阅读