C言語qsortアルゴリズムのポインタ実装
3443 ワード
最近Linux Cプログラミングなどの勉強で再び頭の痛いポインタに遭遇したので、ここでポインタとC++のオブジェクト向けプログラミングに関する知識を改めて学び、以前はできなかったことに気づいた今はeasyと理解しています.
qsort関数プロトタイプ(C言語標準ライブラリ関数)機能:クイックソートルーチンを用いたソート用法:void*base,int nelem,int width,int(*fcmp)(const void*,const void*)パラメータ:1ソート対象配列ヘッダアドレス2配列中のソート対象要素数3各要素の占有空間サイズ4は関数のポインタを指し、ソートの順序を決定する
ここではポインタを用い,void*個人的にはJavaの中のObject,int(*fcmp)(const void*,const void*):関数ポインタ,constは後のパラメータが変えられないことを説明し,プログラムの頑丈性を高める.
ソートには交換が必要です.つまり、頭が痛いswap関数です.
1、最も簡単な実現
2、ポインタパラメータ
3、参照パラメータ
QSORTソース:
このqsortの性能は検出されず、対応する何らかのデータ型の自己書き込みqsortよりも遅い可能性があり、乗算が多すぎる原因であるはずだが、利点は各種データ型を適用できることである.
qsortライブラリ関数を深く分析する(一)http://www.programfan.com/blog/article.asp?id=14298qsortライブラリ関数を深く分析する(二)http://blog.pfan.cn/accelerator/14363.htmlqsortライブラリ関数を深く分析する(三)http://blog.pfan.cn/accelerator/14463.html
ある人はC言語がとても簡単だと言って、すべてのIT人材はすべてできて、だからC環境の下で工事のプロジェクトをすることを学んで役に立たないで、私はみんなの意見を聞きたいです.
qsort関数プロトタイプ(C言語標準ライブラリ関数)機能:クイックソートルーチンを用いたソート用法:void*base,int nelem,int width,int(*fcmp)(const void*,const void*)パラメータ:1ソート対象配列ヘッダアドレス2配列中のソート対象要素数3各要素の占有空間サイズ4は関数のポインタを指し、ソートの順序を決定する
ここではポインタを用い,void*個人的にはJavaの中のObject,int(*fcmp)(const void*,const void*):関数ポインタ,constは後のパラメータが変えられないことを説明し,プログラムの頑丈性を高める.
ソートには交換が必要です.つまり、頭が痛いswap関数です.
1、最も簡単な実現
void swap(int a,int b){
int temp;
temp = a;a = b; b = temp;
}
この方法は様々なC/C++教科書でaとbの交換が実現できないと言われていますが、ここでは説明しません.2、ポインタパラメータ
void swap(int&,int&);
void swap(int *a,int *b){
int temp;
temp = *a;*a = *b; *b = temp;
}
これはきっと交換を実現することができて、&直接アドレス、*間接アドレス3、参照パラメータ
void swap(int&,int&);
void swap(int &a,int &b){
int temp;
temp = a;a = b; b = temp;
}
4、排他的論理和演算a ^= b;
b ^= a;
a ^= b;
//a^b^a = b
5、qsortソースコード使用のvoid swap(char *a,char* b,int width){
char temp;
while(width --){
temp = *a,*a++ = *b,*b++ = temp;
}
}
width:交換対象元素の占有空間の大きさ、この方法は第3の方法と同じ原理である.QSORTソース:
#include <iostream>
#include <cstring>
using namespace std;
struct Node{
char *word;
int cnt;
};
void qsort(void *base,int nleft, int nright,int(*fcmp)(void*,void*));
int cmp(void* a,void* b){//(int*) , *
return *(int *)a - *(int *)b;
}
int cmp2(void* a,void* b){
Node pa = *(Node *)a;
Node pb = *(Node *)b;
return strcmp(pa.word,pb.word);
}
void swap(char *a,char* b,int width){
char temp;
while(width --){
temp = *a,*a++ = *b,*b++ = temp;
}
}
void qsort(void* base,int nleft,int nright,int width,int (*fcmp)(void*,void*)){
if(nleft >= nright) return;
char *lo = (char*)base + width*nleft;
char *hi = (char*)base + width*((nleft + nright)/2);
swap(lo,hi,width);
int x = nleft;
lo = (char*)base + width * nleft;//standard
//cout<<"St: "<<(*(Node*)lo).word<<endl;
for(int i = nleft + 1 ; i <= nright ; i ++){
hi = (char*)base + width * i;
if(fcmp(lo,hi) < 0){
x ++;
char *ll = (char*)base + width * x;
swap(ll,hi,width);
}
}
hi = (char*)base + width * x;
swap(lo,hi,width);
qsort(base,nleft,x - 1,width,fcmp);
qsort(base,x + 1,nright,width,fcmp);
}
int main(){
int a[10] = {1,2,3,4,5,6,7,8,9,10};
qsort(a,0,9,sizeof(int),cmp);
for(int i = 0 ; i < 10 ; i ++) cout<<a[i]<<endl;
Node node[5] = {{"xkey",10},{"color",3},{"void",4},{"static",5},{"while",2}};
qsort(node,0,4,sizeof(node[0]),cmp2);
for(int i = 0 ; i < 5 ; i ++){
cout<<node[i].word<<" "<<node[i].cnt<<endl;
}
return 0;
}
このqsortの性能は検出されず、対応する何らかのデータ型の自己書き込みqsortよりも遅い可能性があり、乗算が多すぎる原因であるはずだが、利点は各種データ型を適用できることである.
qsortライブラリ関数を深く分析する(一)http://www.programfan.com/blog/article.asp?id=14298qsortライブラリ関数を深く分析する(二)http://blog.pfan.cn/accelerator/14363.htmlqsortライブラリ関数を深く分析する(三)http://blog.pfan.cn/accelerator/14463.html
ある人はC言語がとても簡単だと言って、すべてのIT人材はすべてできて、だからC環境の下で工事のプロジェクトをすることを学んで役に立たないで、私はみんなの意見を聞きたいです.