배열 형식에 대한 비교 기능이 잘못되었습니다.
다음은 유형을 얻기 위해 수행 할 수있는 간단한 체크리스트이고를 qsort를 사용하는 경우 바로 크기 :
x
는 첫 번째 인수입니다 sizeof *x
해야 qsort가 세 번째 인수.
- qsort 함수의 첫 번째 것은 함수의 인수를 복사하여 초기화 된 포인터 쌍을 선언해야합니다. 캐스트가 있어서는 안됩니다. 캐스트는
void *
입니다.
const
으로 인해 캐스팅이 필요하다고 생각할 수도 있지만 그렇지 않은 경우 const
을 잘못된 위치에 넣었 기 때문입니다. 캐스트없이 const void *
을 성공적으로 할당하려면 const
키워드 다음에 대상 유형이 정확히 *
이어야합니다. const char *
및 char const *
은 OK입니다 (그리고 서로 동일합니다). const char *const *
도 OK입니다. const char **
이 잘못되었습니다. 그리고 만약 *
앞에 const
을 넣을 수 없다면 *
을 typedef'ed했기 때문에 이 그렇게하지 않아야합니다.
const
을 추가하는 것 외에도 비교 함수 시작 부분에 선언 된 포인터의 유형은 "포인터에 대한 배열 감소"규칙을 적용한 후 qsort에 대한 첫 번째 인수의 유형과 완전히 동일해야합니다. if qsort의 첫 번째 인수는 배열의 이름입니다. 귀하의 경우에는
는, qsort가 첫 번째 인수가 Node
의 배열입니다 nodes_List
을, 그래서 부패 - 투 - 포인터 규칙을 적용하고 당신이 Node *
을 얻을, 다음 const
를 추가하고 당신이 얻을 :
const Node *a_node = a;
const Node *b_node = b;
지금 제대로 입력 포인터의 좋은 쌍을 가지고 있고, 당신은 단순히 명백한 방법으로 그들을 비교 :
return strcmp(a_node->name, b_node->name);
왜 규칙 # 4 작품, 당신이 가지고 설명하기 메모리 레이아웃을 자세히 살펴보십시오. MAX_SIZE가 15이고 MAX_SIZE + 1이 멋진 라운드 16 일 경우 Node
유형에는 16 바이트의 char 배열이 포함되고 nodes_list
에는 총 16 * 16 = 256 바이트의 16 개가 포함됩니다. nodes_list가 메모리 주소 0x1000에 있다고 가정합니다. 그런 다음 레이아웃은 다음과 같습니다.
+---------------+---------------+ +---------------+
| nodes_list[0] | nodes_list[1] |...............| nodes_list[15]|
+---------------+---------------+ +---------------+
^ ^ ^ ^
0x1000 0x1010 0x10f0 0x1100
주소 0x1000에서 0x10ff까지의 주소는 실제로 개체의 일부입니다. 0x1100은 끝에서 1 바이트 뒤쪽 가장자리입니다.
Hotel Foxtrot Echo Charlie Golf Delta Bravo Alpha
및 미사용 부분은 '0'으로 채워진다 있음 :
은 (size
가 8), 그리고 이들 8 문자열 채워 배열이 반 전체라고 가정하자. 객체는 (내가 설명을 위해 공백과 줄 바꿈을 추가 한)
H o t e l \0 \0 \0 \0 \0 \0 \0 \0 \0 \0 \0
F o x t r o t \0 \0 \0 \0 \0 \0 \0 \0 \0
E c h o \0 \0 \0 \0 \0 \0 \0 \0 \0 \0 \0 \0
C h a r l i e \0 \0 \0 \0 \0 \0 \0 \0 \0
G o l f \0 \0 \0 \0 \0 \0 \0 \0 \0 \0 \0 \0
D e l t a \0 \0 \0 \0 \0 \0 \0 \0 \0 \0 \0
B r a v o \0 \0 \0 \0 \0 \0 \0 \0 \0 \0 \0
A l p h a \0 \0 \0 \0 \0 \0 \0 \0 \0 \0 \0
... 128 more \0's
지금, 당신은 (첫 번째 인수, nodes_list
가 0x1000)를 메모리의이 블록의 시작 주소를 qsort 합격이 256 바이트로 구성되어 있습니다 요소 수 (2nd arg, size
, 8)와 요소 수 (3rd arg, sizeof Node
, 16)의 내부 구조에 대한 2 가지 정보를 더한 것입니다. 이 정보를 통해 배열 요소가 주소 0x1000, 0x1010, 0x1020, ... 0x1070에 있음을 알 수 있습니다. 그것은 한 쌍을 선택합니다 - 어떤 쌍이 사용하는 정렬 알고리즘에 따라 달라집니다 - 간단하게 말해서 처음 두 요소를 비교하여 시작하는 어리석은 거품 정렬이라고 가정 해 봅시다.
qsort는 비교 함수를 0x1000 및 0x1010 요소의 주소로 호출합니다. 유형을 알지 못하지만 크기는 알고 있습니다. 각각은 16 바이트를 차지하는 배열 요소입니다.
비교 기능은 a=0x1000
및 b=0x1010
을받습니다. 이들은 16 바이트 오브젝트에 대한 포인터입니다. 구체적으로 각각 struct Node
을 가리 킵니다. 잘못된 것을 한 다음 char **
으로 전송하면 어떻게됩니까? 음, char **
의 값이 0x1000이고, char **
을 참조 해제하여 strcmp
으로 전달해야합니다. 따라서 역 참조를 수행하고 결국 포인터의 값으로 바이트 'H', 'o', 't', 'e'
을로드하게됩니다 (포인터가 4 바이트라고 가정 함). 긴). charset으로 ASCII가있는 빅 엔디안 시스템에서 이것은 strcmp
으로 전달되는 메모리 주소 0x486f7465에 대한 포인터입니다. strcmp
이 충돌합니다. 시도한 결과 struct Node **
은 기본적으로 같습니다.
또 다른 좋은 점은 qsort가 배열 순서를 재조정 할 때 멤버 크기 정보를 사용하는 방법입니다. 세 번째 인자는 비교가 수행되는 객체의 크기 일뿐만 아니라 배열을 재정렬 할 때 단위로 이동되는 객체의 크기이기도합니다. 비교 함수가 1을 반환하면 (strcmp ("Hotel", "Foxtrot")) qsort의 가상 버블 정렬 구현은 0x1000과 0x1010의 객체를 바꿔서 올바른 순서로 배치합니다. 이것은 각각 16 바이트의 일련의 3 memcpy로 수행 할 것입니다. 그것들이 쓸데 없다는 것을 모르기 때문에, 여분의 사람들은 모두 \0
을 움직여야 만합니다. 이러한 16 바이트 오브젝트는 qsort에 대해 불투명합니다. 이것은 주 배열에 매우 큰 객체가있을 때 포인터의 보조 배열을 만들고이를 주 배열 대신 q 정렬하는 것을 고려해야 할 이유가 될 수 있습니다.
와우 감사합니다. 내 코드가 성공적으로 작동합니다. – user2817240
그냥 몇 가지 간단한 점. qsort의 세 번째 인수는 실제로 qsort()의 첫 번째 인수 인 sizeof (nodes_list)가 아니라 sizeof (Node)로 가정됩니다. sizeof (nodes_list) 코어 덤프를 제공합니다 – user2817240
또한 질문이 있습니다. 왜 a_node와 b_node는 다음과 같이 선언되지 않았는가? const Node ** a_node; const 노드 ** b_node? a_node와 b_node는 메소드의 매개 변수에서 a와 b가 이미 포인터 인 포인터에 대한 포인터가 아니어야합니까? 이 점을 분명히하십시오. 고맙습니다. – user2817240