qsort 알파벳 순서로 문자열 비교

Question

stdlib.h 라이브러리와 함께 제공되는 qsort()을 사용하여 문자열 구조의 배열을 정렬합니다.

기본적으로 문자열 배열이지만 배열을 포함하는 구조입니다.

예를 들어 :

는

typedef struct node { 
    char name[MAX_SIZE + 1]; 
} Node; 

그런 다음 이름이 포함 된 노드 내 배열은 다음과 같습니다

내 질문은

Node nodes_list[MAX_SIZE + 1]; 

, 나는 내가 다음 인쇄 할 때 너무 nodes_list을 정렬 할 :

for (i = 0; i < size; i++) { 
    printf("%s\n", nodes_list[i].name); 
} 

알파벳순으로 모든 이름을 인쇄합니다.

int compare(const void *a, const void *b) { 
    const char **ia = (const char **)a; 
    const char **ib = (const char **)b; 
    return strcmp(*ia, *ib); 
} 

내가 qsort과 기능을 실행합니다 :

qsort(nodes_list, size, sizeof(Node), compare); 

내가 세그먼트 오류를 ​​얻을 수를 (코어

내가 qsort 내 비교 기능을 사용하여 목록을 정렬 할 싶습니다이있다 덤핑).

이 코드 조각으로 인해 세그먼트 화 오류가 발생한다는 것을 알고 있습니다.이 코드가 없으면 이름 목록을 인쇄 할 수 있기 때문입니다. 물론 분류되지 않았습니다.

누군가 도움을 줄 수 있습니까?

Answer 1

배열 형식에 대한 비교 기능이 잘못되었습니다.

다음은 유형을 얻기 위해 수행 할 수있는 간단한 체크리스트이고를 qsort를 사용하는 경우 바로 크기 :

1. x는 첫 번째 인수입니다 sizeof *x해야 qsort가 세 번째 인수.
2. qsort 함수의 첫 번째 것은 함수의 인수를 복사하여 초기화 된 포인터 쌍을 선언해야합니다. 캐스트가 있어서는 안됩니다. 캐스트는 void *입니다.
3. const으로 인해 캐스팅이 필요하다고 생각할 수도 있지만 그렇지 않은 경우 const을 잘못된 위치에 넣었 기 때문입니다. 캐스트없이 const void *을 성공적으로 할당하려면 const 키워드 다음에 대상 유형이 정확히 *이어야합니다. const char * 및 char const *은 OK입니다 (그리고 서로 동일합니다). const char *const *도 OK입니다. const char **이 잘못되었습니다. 그리고 만약 * 앞에 const을 넣을 수 없다면 *을 typedef'ed했기 때문에 이 그렇게하지 않아야합니다.
4. 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 정렬하는 것을 고려해야 할 이유가 될 수 있습니다.