C++에서 int의 링크 된 목록 정렬

Question

int를 가장 작은 순서에서 가장 큰 순서로 저장하는 linked-list 유형을 만들어야합니다. 링크드 목록을 정렬하는 방법을 알고 있거나 알고있는 분이라면 여기에서 나와 있는지 알려주십시오. C++로 코딩하는 법을 가르쳐주세요.

Answer 1

우리가 코드를 보여 주면 큰 실책이 생길 것입니다. 대신에 두 가지 접근 방식을 제공하고 원하는 방식을 구현할 수 있습니다.

는

첫 번째 방법은이 "종류"삽입과 같이 당신이 값, 말, (7)를 삽입 할 때, 당신은 당신의 목록의 첫 번째 항목부터 시작하여이 절차를 수행하면 노드에서 실행까지 :

검사중인 노드의 값이 7보다 크면 검사하고 반환 할 노드 앞에 새 노드를 삽입합니다. 그렇지 않으면 다음 노드를 보게됩니다. 다음 노드가 없으면. 목록의 끝 부분에 새 노드를 삽입합니다. 그 이유는 7이 목록의 다른 항목보다 크고 반환된다는 것을 의미하기 때문입니다.

두 번째 대안은 많은 정렬 알고리즘 중 하나를 사용하여 전체 목록을 정렬하는 것입니다. 이해하고 구현하기 쉽기 때문에 BubbleSort를 사용하는 것이 좋습니다. Wikipedia에서 bubblesort (다른 많은 정렬 알고리즘과 관련이 있음)에 대해 더 많이 읽을 수 있습니다.

Answer 2

색인 목록을 통해 연결된 목록을 정렬하는 경우가 많습니다. 노드를 만들려면 노드 수 (N) * 노드 포인터의 크기에 해당하는 메모리 할당이 필요합니다. 개념은 충분히 간단합니다.

참고 : 나는 OP는 C++ 질문으로 수업이 의미하는 경우 완전히 확신하지 못했습니다으로이 알고리즘은 C에합니다 (지옥는 당신의 처리에 표준 컨테이너와 C++에서 링크리스트를 사용합니다 ??)

1. 목록
2. N 노드 포인터 하는 포인터 배열을 할당의 노드 수 (N)를 결정한다.
3. 목록의 모든 노드 포인터로 포인터 배열을로드하십시오. 나는. 리스트를 걸어 포인터 배열의 각 슬롯에 포인터를 놓습니다.
4. 이 노드 포인터 배열을 정렬 알고리즘에 보냅니다. 표준 라이브러리는 런타임 라이브러리 qsort()을 좋아합니다.
5. 정렬 후 전체 포인터 배열 (하나는 적음)을 걷고 각 노드의 "다음"포인터가 뒤 따르는 포인터를 가리 키도록 설정합니다. 마지막 포인터는 "next"포인터를 NULL로 설정합니다.
6. 헤드 포인터를 포인터 배열의 첫 번째 포인터 [0]로 설정하십시오. 포인터 배열

의

무료 메모리가 연결된 목록이 정렬됩니다.

struct node 
{ 
    ..data fields.. 
    int keyField; // << determines sort order 
    struct node *next; 
}; 

이 목록에 노드의 수를 결정합니다

---

는 노드를 가정하면이 같은 것입니다.

size_t list_count(struct node* head) 
{ 
    size_t count = 0; 
    while (head) 
    { 
     ++count; 
     head = head->next; 
    } 
    return count; 
} 

하는 포인터 배열을 NITEMS 목록 노드와 귀찮게에 1보다 큰 (더 의미가 계산되지 않은 목록의 크기를 할당 : 난 당신이 사소한이 작업을 수행 할 수있는 PROC를 가지고 있으리라 믿고있어 길이가 0 또는 1) 목록 :

struct node *ptr = head; 
size_t i=0; 
for (;i<nItems;++i,ptr = ptr->next) 
    ptrs[i] = ptr; 

는 이제 appropria와 qsort()이를 보내

struct node **ptrs = malloc(sizeof(*ptrs)*nItems); 

목록에있는 모든 항목에 포인터 배열을 채 웁니다 비교 기능. 우리의 구조에서 keyField에 따라 정렬합니다 예 비교 기능은 다음과 같습니다 :

int compare_node_ptrs(const void* left, const void* right) 
{ 
    struct node *l = *(struct node**)left; 
    struct node *r = *(struct node**)right; 
    return l->keyField - r->keyField; 
} 

호출를 qsort()는 다음과 같습니다

qsort(ptrs, nItems, sizeof(*ptrs), compare_node_ptrs); 

지금 전체 목록을 걷는다. "다음"포인터 재배 선 :

for (i=0;i<(nItems-2);++i) 
    ptrs[i]->next = ptrs[i+1]; 
ptrs[nItems-1] = NULL; 

헤드 포인터를 다시 감습니다.

head = ptrs[0]; 

그리고 마지막으로 포인터 배열을 비 웁니다.

free(ptrs); 

귀하의 연결된 목록이 정렬됩니다.

---

사이드 바 병합 - 일종의없이 추가 공간 요구 사항에 링크 된 목록을 정렬 할 수 있습니다, 필자가 아는 유일한 O (nlogn) 알고리즘이다. 다음에 프로토 타입 일반적인 솔루션은 고추 식사가 될 것입니다 :

이

mergesort_list(void **head, size_t offset_ptr, int(*comp)(void*,void*)) 

head: address of the head pointer. 
offset_ptr: offset in bytes from a node ptr where the 'link' pointer can be found. 
comp: comparison function. 

Answer 3

오래된 quicksort는 (C++ 03 친화적) 트릭을 할 것입니다 좋은 :

이

#include <algorithm> 
#include <functional> 
#include <iostream> 
#include <iterator> 
#include <list> 

using namespace std; 

void qsort(list<int>::iterator first, list<int>::iterator last) 
{ 
    if (distance(first, last) < 2) 
     return; 
    int pivot = *first; 

    list<int>::iterator it = partition(first, last, bind2nd(less<int>(), pivot)); 

    qsort(first, it); 
    qsort(it, last); 
} 

int main() 
{ 
    std::list<int> l; 
    l.push_back(5); 
    l.push_back(4); 
    l.push_back(1); 
    l.push_back(10); 
    l.push_back(3); 
    l.push_back(6); 
    l.push_back(7); 

    cout << "List:"; 
    copy(l.begin(), l.end(), std::ostream_iterator<int>(std::cout, " ")); 
    cout << endl; 

    qsort(l.begin(), l.end()); 

    cout << "Sorted list:"; 
    copy(l.begin(), l.end(), std::ostream_iterator<int>(std::cout, " ")); 
    cout << endl; 
    return 0; 
} 

체크인 : http://ideone.com/OOGXSp