在链接列表中添加列表项或节点 [英] adding list items or nodes in linked list
问题描述
在从键盘插入值时，我尝试使用以下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<<"~~~~~~~~~~~~~~~~~~~~~~~~\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;
}
推荐答案
插入节点.首先...代码！
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.
The twist is listItem is a very simple data structure and can take advantage of aggregate Initialization to initialize the listItem's members. The braces contain the values I want in the new listItem in the order they are declared in the structure. The first member variable, data, is set to item and the second, next, set to the current value of *curr, the next item in the list.
在很小的时间内，您将使 * curr 和新的 listItem 的 next 指向相同的listItem ，然后 = 运算符更新 * curr 来指向新创建的 listItem .
For a tiny instance of time you'll have *curr and the next of the new listItem pointing at the same listItem then the = operator updates the *curr to point at the newly created listItem instead.
将其画在一张纸上，您会看到发生了什么事.
Draw it out on a piece of paper and you'll see what's happening.
这篇关于在链接列表中添加列表项或节点的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
