단일 삽입 목록에 단순 삽입 정렬 C++

Question

현재로서는 효율성에 대해 걱정하지 않고 인스턴트 메신저 만 배우고 있습니다. 나는 누군가가 단 하나 연결된 목록을위한 간단한 삽입 정렬을 배우면서 나를 도울 수 있는지 궁금해했다. 이것은 숙제를위한 것이므로 이해하고 싶습니다. .

char c[13]; 
    r >> c; 
    r >> NumberOfInts; 

    Node *node = new Node; 
    head = node; //start of linked list 

    for(int i = 0; i < NumberOfInts; i++) //this reads from the file and works 
    { 
     r >> node->data; 
     cout << node->data << endl; 
     node ->next = new Node; //creates a new node 
     node = node->next; 

     if(_sortRead) //true 
     { 
      for(int k = 0; k < i; k++) 
      { 
         //insertion sort 
      } 
     } 
    } 

지금까지 나는 그것이 내가 그것을 읽을 도착으로 정렬 할 필요가 노드가 BTW 구조체 인 IStream을로 읽을 수 있습니다 여기에 코드입니다. 누구든지 제발 도와 주실 수 있습니까?

Answer 1

목록 끝에 추가 노드가 하나 더 추가 된 것처럼 보입니다. 나는 당신이 마지막 노드에서 초기화되지 않은 데이터로 끝날 것으로 생각합니다.

현재 새 노드를 목록 끝에 추가하는 것뿐입니다.

각 노드를 목록 끝에 추가하는 대신 정면에서 전체 목록을 반복하고 올바른 정렬 된 위치를 찾아야합니다. 그런 다음 노드를 마지막 위치가 아닌 정렬 된 위치에 삽입하십시오 (귀하의 //insertion sort 루프에서 구현하려고 시도한 논리라고 생각합니다.)

Answer 2

STL을 기반으로 효과적인 빌드를 시도하십시오. LOWER_BOUND으로 좋은 장소를 찾습니다. 기본적으로 (이해할 수없는 여전히하지만) 약간 다른 형태의 같은 질문은 지금까지 당신을 얻을하지 않을

template<class T> std::list<T>::iterator insert(std::list<T> &my_list, const T &value) 
{ 
    return my_list.insert(std::lower_bound(my_list.begin(), my_list.begin(), value), value); 
}