コンパレータ-各データ構造の応用(c言語におけるqsort関数)
51673 ワード
qsort()関数はc言語ライブラリの高速配置機能を実現し,余分な空間の処理のため,自分で書くよりも最適化される.注記:自分で書いたスナップショットは、余分なスペースの冗長性のため、実際の実行時に制限を超えたエラーが発生します.
qsort呼び出しに含まれるヘッダファイル&関数プロトタイプ:
1.パラメータvoid*baseは1つの配列を入力し、2.size_t numは配列全体の大きさであり、3.size_t sizeは単一要素のサイズであり、4.int(compar)(const void,const void*)は、使用者が完了する必要がある比較関数、すなわち比較器である.
関数の戻り値を比較します.
return value
meaning
<0
The element pointed to by p1 goes before the element pointed to by p2
0
The element pointed to by p1 is equivalent to the element pointed to by p2
>0
The element pointed to by p1 goes after the element pointed to by p2
1.qsort関数int型ソートを実現
2.charタイプの配列のソート
3.doubleタイプ配列のソート(特に注意が必要)
4.構造体の一次ソート
5.機構体2段の並べ替えは、4中の構造体にとって、xに値を付与すると、x中の値が0になるので、y中の配列を比較する必要がある.
コードを次のように変更できます.
6.qsortの機能を模倣して共通のバブルソートを実現する
1つの例で解析します:要求--1つの配列を操作するつもりで、配列の各要素は1つのポインタで、2つの要素の配列を指します.要素のサイズ関係は、最初の要素を比較し、最初の要素は同じように2番目の要素を比較します.まず、 そして、各配列内の
ソートの使用方法:
qsortのcmpの書き方:パラメータは実際には配列要素のポインタであり、ここで要素は
非
たとえば、2 D配列
こうぞうたい
構造体のソートは比較的簡単です.例えば、構造体の構造:
アルゴリズムcmpを比較すると、強制転換は
qsortは多次元配列と構造体のソートqsort関数に対して様々なタイプのデータをソートする.
一、一次元
qsort呼び出しに含まれるヘッダファイル&関数プロトタイプ:
#include 1.パラメータvoid*baseは1つの配列を入力し、2.size_t numは配列全体の大きさであり、3.size_t sizeは単一要素のサイズであり、4.int(compar)(const void,const void*)は、使用者が完了する必要がある比較関数、すなわち比較器である.
関数の戻り値を比較します.
return value
meaning
<0
The element pointed to by p1 goes before the element pointed to by p2
0
The element pointed to by p1 is equivalent to the element pointed to by p2
>0
The element pointed to by p1 goes after the element pointed to by p2
1.qsort関数int型ソートを実現
int int_cmp(const void * p1, const void p2){
return (( int *)p1 - *(int *) p2);
}
2.charタイプの配列のソート
int char_cmp(const void* str1, const void* str2){
return (char)str1 - (char)str2;
}
3.doubleタイプ配列のソート(特に注意が必要)
int double_cmp(const void* arr1, const void* arr2){
return (double)arr1 > (double)arr2 ? 1 : -1;
// ，
}
4.構造体の一次ソート
1 #include<stdio.h>
2 #include<stdlib.h>
3
4 typedef struct Student
5 {
6 int x;
7 int y;
8 // x ， x y
9 }Student;
10
11 Student student[7];
12
13 int cmp(const void *a, const void *b)
14 {
15 Student* pa1 = (Student*)a;
16 Student* pa2 = (Student*)b;
17
18 return (pa1->x) > (pa2->x) ? 1 : -1;
19 }
20
21 //
22 void Display()
23 {
24 for (int i = 0; i < 7; ++i)
25 {
26 printf("%d
",student[i].x);
27 }
28 }
29
30 int main()
31 {
32 int arr[7] = {
1,3,5,2,6,9,7 };
33 for (int i = 0; i < 7; ++i)
34 {
35 // arr x
36 student[i].x = arr[i];
37 }
38 Display();
39 qsort(student, 7, sizeof(Student), cmp);
40 for (int i = 0; i < 7; ++i)
41 {
42 printf("%d", student[i].x);
43 }
44
45 return 0;
46 }
5.機構体2段の並べ替えは、4中の構造体にとって、xに値を付与すると、x中の値が0になるので、y中の配列を比較する必要がある.
コードを次のように変更できます.
1 #include<stdio.h>
2 #include<stdlib.h>
3
4 typedef struct Student
5 {
6 int x;
7 int y;
8 // x ， x y
9 }Student;
10
11 Student student[7];
12
13 int cmp(const void *a, const void *b)
14 {
15 Student* pa1 = (Student*)a;
16 Student* pa2 = (Student*)b;
17
18 if (pa1->x != pa2->x)
19 {
20 return (pa1->x) > (pa2->x) ? 1 : -1;
21 }
22 else
23 {
24 return (pa1->y) > (pa2->y) ? 1 : -1;
25 }
26 }
27
28 //
29 void Display()
30 {
31 printf("x=");
32 for (int i = 0; i < 7; ++i)
33 {
34 printf("%d", student[i].x);
35 }
36 printf("
");
37 printf("y=");
38 for (int i = 0; i < 7; ++i)
39 {
40 printf("%d", student[i].y);
41 }
42 printf("
");
43 }
44
45 int main()
46 {
47 int arr[7] = {
1,3,5,2,6,9,7 };
48 for (int i = 0; i < 7; ++i)
49 {
50 // arr x
51 student[i].y = arr[i];
52 }
53 Display();
54 printf(" y:
");
55 qsort(student, 7, sizeof(Student), cmp);
56 for (int i = 0; i < 7; ++i)
57 {
58 printf("%d", student[i].y);
59 }
60
61 return 0;
62 }
6.qsortの機能を模倣して共通のバブルソートを実現する
1 // qsort( )
2
3 #include <stdio.h>
4
5 int int_cmp(const void * p1, const void * p2)
6 {
7 return (*(int *)p1 > *(int *)p2);
8 }
9
10 void _swap(void *p1, void * p2, int size)
11 {
12 int i = 0;
13 for (i = 0; i < size; i++)
14 {
15 char tmp = *((char *)p1 + i);
16 *((char *)p1 + i) = *((char *)p2 + i);
17 *((char *)p2 + i) = tmp;
18 }
19 }
20
21 void bubble(void *base, int count, int size, int(*cmp)(void *, void *))
22 {
23 int i = 0;
24 int j = 0;
25 for (i = 0; i < count - 1; i++)
26 {
27 for (j = 0; j < count - i - 1; j++)
28 {
29 if (cmp((char *)base + j * size, (char *)base + (j + 1)*size) > 0)
30 {
31 _swap((char *)base + j * size, (char *)base + (j + 1)*size, size);
32 }
33 }
34 }
35 }
36 int main() {
37 int arr[] = {
1, 3, 5, 7, 9, 2, 4, 6, 8, 0 };
38 //char *arr[] = {"aaaa","dddd","cccc","bbbb"};
39 int i = 0;
40 bubble(arr, sizeof(arr) / sizeof(arr[0]), sizeof (int), int_cmp);
41 for (i = 0; i< sizeof(arr) / sizeof(arr[0]); i++)
42 {
43 printf( "%d ", arr[i]);
44 }
45 printf("
");
46 return 0;
47 }
二、多次元
malloc動的出願のための多次元配列(ポインタ配列)1つの例で解析します:要求--1つの配列を操作するつもりで、配列の各要素は1つのポインタで、2つの要素の配列を指します.要素のサイズ関係は、最初の要素を比較し、最初の要素は同じように2番目の要素を比較します.
mallocによってポインタ配列が割り当てられる.まず、int *を指す要素を指す1次元配列が割り当てられるので、配列タイプはint **である.int *型ポインタに対して、1次元配列が割り当てられ、配列タイプはintである.int *b,**a;
a = (int**)malloc(500000*sizeof(int*)); // int* 。
for(i=0;i<500000;i++)
{
b = malloc(2*sizeof(int));
a[i] = b;
}
// ， free(a)， ：
for(i=0;i<n;i++) {
// malloc free
free(a[i]);
}
ソートの使用方法:
qsort(a, n, sizeof(a[0]), cmp);
qsortのcmpの書き方:パラメータは実際には配列要素のポインタであり、ここで要素は
int*であるため、パラメータはint**であるべきで、比較する配列はこのポインタが指す内容である.void* aを強制的に本来の姿int **に変換し、apポインタはaの最初の要素を指す(この要素もポインタであり、int型の1次元配列を指す).int cmp(const void *a,const void *b)
{
int *ap = *(int **)a;
int *bp = *(int **)b;
if(ap[0] == bp[0])
return ap[1] - bp[1];
else
return ap[0] - bp[0];
}
非
malloc出願の多次元配列についてたとえば、2 D配列
int a[5][2];では、2 D配列の各次元の最初の要素に従ってソートする必要があります.比較アルゴリズムcmp:int cmp(const void *a, const void *b)
{
return ((int *)a)[0] - ((int *)b)[0];
}
こうぞうたい
構造体のソートは比較的簡単です.例えば、構造体の構造:
typedef struct node{
int x;
int y;
int z;
}Node;
アルゴリズムcmpを比較すると、強制転換は
->ほど優先度が高くないことを覚えておいてください.int cmp(const void *a, const void *b)
{
// return (Node *)a->x - (Node *)b->x; // ！
// return ((Node *)a)->x - ((Node *)b)->x; // 1
return (*(Node *)a).x - (*(Node *)b).x; // 2
}
リファレンス
qsortは多次元配列と構造体のソートqsort関数に対して様々なタイプのデータをソートする.