Связанный список вопросов с середины C++

Question

Я новичок в связанных списках, и теперь у меня возникла проблема с тем, как добавить узел в середину списка. Пример, как если бы я получил название списка показать ниже, и при добавлении данных по одному, как и ниже последовательности:

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

I хочу мои данные "gerik" in "безумие" место если выставляется. Я могу сортировать данные infront от «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

Мы хотим включить в наш список 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 
} 

Answer 2

Чтобы отсортировать списки, вам необходимо использовать стратегию разделения и завоевания с помощью сортировки по методу слияния.

Для того, чтобы вставить в середину, вам нужно создать 2 узла. Узлы медленные и узлы быстро. Сначала Node slow - head.next, Node fast - head.next.next, и вы продолжаете перемещать эти 2, выполняя медленные = slow.next и fast = fast.next.next, пока вы не нажмете конец узлом быстро. Если вы подумаете об этом, скорость будет двигаться в два раза быстрее, чем Node slow, поэтому в конце Node slow будет посередине. Затем вставьте после этого узла.