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

Question

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

1.安德鲁
2.埃里克
3.疯狂
4.格力克

我希望我的数据“gerik”出现在“ma​​dness”位置。我能够对“eric”前面的数据进行排序，但在“eric”之后我不知道。我希望我的输出如下所示:

1.安德鲁
2.埃里克
3.格瑞克
4.疯狂

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

#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 继续移动这两个，直到你用 Node fast 结束。如果你考虑一下，fast 的移动速度是 Node slow 的两倍，所以最后 Node slow 会在中间。然后在该节点之后插入。