[此贴子已经被作者于2018-3-18 22:27编辑过]
[此贴子已经被作者于2018-3-19 08:04编辑过]
size_t BsearchReIndex( const void* key,const void* base,size_t num,size_t size,int (*compartor)( const void*,const void* ) ) { size_t low=0; size_t height=num-1; while (low<=height&&height!=-1) { const size_t mid=low+(height-low>>1); const int comp=compartor(key,( const char* )base+mid*size); if (comp<0) height=mid-1; else if (comp>0) low=mid+1; else return mid; } return low; }
#include<stdio.h> #include<assert.h> #include<stdlib.h> #include<string.h> #define FREE( p ) \ do \ { \ free(p); \ p=NULL; \ }while (0) typedef struct Data { int data; //保存数据 size_t mark; //上一个数据下标 }Data,*P_Data; size_t _bsearch( const void*,const void*,size_t,size_t ,int (*)( const void*,const void* )); int comp(const void* ,const void* ); void malFun( void**,size_t ); void input( const P_Data*,size_t ); void printData( const Data[],size_t ); unsigned fun( Data[],size_t ); int main( void ) { P_Data data=NULL; size_t len=0; if ( !scanf("%u",( unsigned* )&len)) exit(EXIT_FAILURE); input(&data,len); printData(data,fun(data,len)); FREE(data); return 0; } int comp(const void* p,const void* q) { const int _p=*( const int* )p; const P_Data _q=( const P_Data )q; if (_p>_q->data) return 1; if (_p<_q->data) return -1; return 0; } size_t _bsearch( const void* key,const void* base,size_t num,size_t size,int (*compartor)( const void*,const void* ) ) { size_t low=0; size_t height=num-1; while (low<=height&&height!=-1) { const size_t mid=low+(height-low>>1); const int comp=compartor(key,( const char* )base+mid*size); if (comp<0) height=mid-1; else if (comp>0) low=mid+1; else return mid; } return low; } void malFun( void** data,size_t size ) { assert(data); *data=malloc(size); assert(*data); memset(*data,0,size); } void input( const P_Data* data,size_t len) { const size_t size=len*sizeof (Data); size_t i; if (!len) exit(EXIT_FAILURE); malFun(( void** )data,size); for (i=0;i!=len;++i) if (!scanf("%d",&(*data)[i].data)) exit(EXIT_FAILURE); else (*data)[i].mark=i; } unsigned fun( Data data[],size_t len ) { P_Data road=NULL; const size_t dataSize=len*sizeof (Data); const size_t roadSize=len*sizeof (Data); size_t pos=0; size_t i; size_t j=1; malFun(( void** )&road,roadSize); road[0].data=data[0].data; road[0].mark=0; for (i=0;i!=len;++i) data[i].mark=-1; for (i=1;i<len;++i) { if (data[i].data>road[j-1].data) pos=j++; else pos=_bsearch(&data[i].data,road,j,sizeof (Data),comp); if (pos) data[i].mark=road[pos-1].mark; road[pos].data=data[i].data; road[pos].mark=i; } pos=road[j-1].mark; FREE(road); return pos; } void printData( const Data data[],size_t mark ) { int* road=NULL; size_t step; size_t t_step; size_t t_mark=mark; for (step=0;mark!=-1;++step) mark=data[mark].mark; malFun(( void** )&road,step*sizeof (int)); for (t_step=step-1,mark=t_mark;mark!=-1;--t_step) { road[t_step]=data[mark].data; mark=data[mark].mark; } printf("\n最长子序列长度为%u,具体路径为:\n",( unsigned )step); while (++t_step!=step) printf("%-8d",road[t_step]); puts(""); FREE(road); }
[此贴子已经被作者于2018-3-20 08:28编辑过]