从中间 C++ 链接列表问题插入

Question

我是链表的新手，现在我遇到了一个问题，如何将节点添加到链表的中间。例如，如果我在下面显示了一个名单，当我像下面的顺序一样一个一个地添加数据时：

1.andrew
2.eric
3.madness
4.gerik

我希望我的数据“gerik”出现在“madness”的地方。我能够对“eric”前面的数据进行排序，但在“eric”之后我不知道。我希望我的输出如下所示：

1.andrew
2.eric
3.gerik
4.madness

下面是我的示例代码，请给我建议或代码示例来帮助我：

#include <iostream>
#include <string>
#include <cstdlib>
#include <cstring>

using namespace std;

struct node
{
    char f_name[20];
    char l_name[20];
    char u_id[10];
    node *next;
};

node *head;
node *curr;

//prototype
void display();
void add();
void search_name();
void insert_data(node *tempnode);
void insert_before_head(node *tempnode);
void menu(char choice);
char pause;

//function start...
void search_name()
{
    char name[20];
    curr = head;
    cin.ignore(30,'\n');
    cout<<"Key In Last Name :"<<endl;
    cin.get(name, 20);
    cin.ignore(30,'\n');

    while((curr->next != NULL) && (strcmp(curr->l_name, name) != 0))
    {
        curr = curr->next;
    }
    if(curr != NULL)
    {
        cout<<"Record Found !"<<endl;
        cout<<"First Name"<<setw(16)<<"Last Name"<<setw(16)<<"User ID"<<endl;
        cout<<"--------------------------------------------------------------"<<endl;
        cout<<curr->f_name<<setw(20)<<curr->l_name<<setw(16)<<curr->u_id<<endl<<endl;

    }
    else
    {
        cout<<"No Match !"<<endl;
        cout<<"Press 'Enter' To Continue"<<endl;
        cin.get(pause = getch());
        system("cls");
    }
};
void display()
{
    curr = head;
    if(head != NULL)
    {
        cout<<"First Name"<<setw(16)<<"Last Name"<<setw(16)<<"User ID"<<endl;
        cout<<"--------------------------------------------------------------"<<endl;
        while(curr != NULL)
        {
            cout<<curr->f_name<<setw(20)<<curr->l_name<<setw(16)<<curr->u_id<<endl;
            curr = curr->next;
        }
    }
    else
    {
        cout<<"No Data. File storage Empty!"<<endl;
    }
};
void add()
{
    node *temp;
    temp = new node;
    cin.ignore(30, '\n');
    cout<<"Key In First Name:"<<endl;
    cin.get(temp->f_name, 20);
    cin.ignore(30, '\n');
    cout<<"Key In Last Name:"<<endl;
    cin.get(temp->l_name, 20);
    cin.ignore(30, '\n');
    cout<<"Key In Your ID:"<<endl;
    cin.get(temp->u_id, 10);
    insert_data(temp);
};

void insert_data(node *tempnode)
{
    node *temp;

    if(head == NULL)
    {
        node *temp;
        temp = new node;
        temp = head;
        tempnode->next = NULL;
        head = tempnode;
    }
    else if(strcmp(tempnode->l_name, head->l_name) < 0)
    {
            insert_before_head(tempnode);
    }
    else
    {
        temp = new node;
        curr = head;

        while(curr->next != NULL)
        {
            curr = curr->next;
        }
            temp = tempnode;
            curr->next = tempnode;
            tempnode->next = NULL;
    }

};
void insert_before_head(node *tempnode)
{
    node *temp;

    if(head != NULL)
    {
       temp = new node;
       temp = tempnode;
       tempnode->next = head;
       head = tempnode;
    }
};

void menu(int choice)
{
    switch (choice)
    {
    case 1 :
        add();
        break;
    case 2:
        display();
        break;
    case 3:
        search_name();
        break;
    case 4:
        cout<<"Exit Program !"<<endl;
        break;
    default :
        cout<<"Error! Program Terminate !"<<endl;
    }
};

int main()
{
    int choice;
    node *temp;
    head = NULL;
    curr = NULL;

    cout << "Data Stack Head And Any Position !" << endl;
    system("cls");
    do{
            cout<<"1. Add Data."<<endl;
            cout<<"2. Show Data. "<<endl;
            cout<<"3. Search Last Name "<<endl;
            cout<<"4. Exit. "<<endl;
            cin >>choice;
            menu(choice);

       }while(choice != 4);

 return 0;
}

Answer 1

要对链表进行排序，您需要使用合并排序的分而治之策略。

为了在中间插入，您需要创建 2 个节点 Node slow 和 Node fast。一开始 Node slow 是 head.next，Node fast 是 head.next.next 然后你通过 slow = slow.next 和 fast = fast.next.next 继续移动这 2 个，直到你到达终点节点快速。如果你考虑一下，fast 的移动速度是 Node slow 的两倍，所以最后 Node slow 会在中间。然后在该节点后插入。

Answer 2

我们想在我们的列表中插入 newNode。
设节点 X 为节点，之后应插入 newNode 以保持排序顺序。

您可以像我的示例一样重新编写 insert_data(...) 函数。
我采用了 WhozCraug 推荐的代码并重写了它以使其更加明显。

void insert_data(node *newNode)
{
    node **pointerToTheNextPtr = &head;
    // find position to insert new node
    while (*pointerToTheNextPtr && strcmp((*pointerToTheNextPtr)->l_name, newNode->l_name) < 0)
        pointerToTheNextPtr = &((*pointerToTheNextPtr)->next);

    // here pointerToTheNextPtr stores the pointer to the X->next field

    // insert new node between X and *(X->next)
    newNode->next = *pointerToTheNextPtr; // set newNode->next = X->next
    *pointerToTheNextPtr = newNode; // set X->next = newNode 
}

从中间 C++ 链接列表问题插入

Linked List issue insert from middle C++

c++

linked-list