用分治计数对字符串进行排序~
正常来说字符串排序都是通过strcmp来比较的,那能不能不以字符串为单位而是以单个字符为单位进行排序呢~对于某字符串可以这样,先对所有字符串的第一个字符进行排序,相等的就分成一组,那一组里面再对第二个字符进行排序……直到所有字符串都能独立分成一组(包括全等)为止~
那用分治法就是把那一行字符都相等的分成一组,剩下的部分分成另外一组,这样不断细分直到每一个字符串都是独立的一组(包括相等)为止~
就有如下代码~
不能保证说完全没有bug,但基本就是这个样子了可以看看
~
程序代码：
#include<stdio.h>
typedef struct Load
{
const char* p;
size_t index;
}Load;
void nodeMal( void** ,size_t );
void nodeFree( void** );
int comp( const void*,const void* );
char* input( char* ,size_t );
void fun( const char* [],size_t,int (*)( const void*,const void* ) );
void _sort( Load* ,size_t,size_t,int (*)( const void*,const void* ) );
int main( void )
{
#define __ARR_LEN( s ) \
(sizeof (s)/sizeof (*s))
char str[5][100];
const char* p[__ARR_LEN(str)];
size_t i;
puts("Input 5 strings:");
for (i=0;i!=__ARR_LEN(str);++i)
{
input(str[i],sizeof (str));
p[i]=str[i];
}
fun(p,__ARR_LEN(str),comp);
puts("--------------------");
for (i=0;i!=__ARR_LEN(str);++i)
puts(p[i]);
return 0;
#undef __ARR_LEN
}
#include<stdlib.h>
#include<string.h>
#include<assert.h>
void nodeMal( void** p,size_t size )
{
assert(p);
*p=malloc(size);
assert(*p);
memset(*p,0,size);
}
void nodeFree( void** p )
{
assert(p);
free(*p);
*p=NULL;
}
int comp( const void* p,const void* q )
{
const char* const _p=(( Load* )p)->p;
const char* const _q=(( Load* )q)->p;
const size_t index=(( Load* )p)->index;
return _p[index]-_q[index];
}
char* input( char* s,size_t size )
{
char* p=NULL;
fgets(s,size,stdin);
if ((p=strchr(s,'\n'))!=NULL)
*p='\0';
else
scanf("%*[^\n]%*c");
return s;
}
void fun( const char* str[],size_t n,int (*comp)( const void*,const void* ) )
{
Load* load=NULL;
size_t i;
nodeMal(( void** )&load,n*sizeof (*load));
for (i=0;i!=n;++i)
{
load[i].p=str[i];
load[i].index=0;
}
qsort(load,n,sizeof (*load),comp);
_sort(load,0,n,comp);
for (i=0;i!=n;++i)
str[i]=load[i].p;
nodeFree(( void** )&load);
}
void _sort( Load* load,size_t low,size_t height,int (*comp)( const void*,const void* ) )
{
if (low>=height)
return ;
{
const Load key=load[low];
int flag=0;
size_t i=low;
for (;(i!=height)&&(comp(&key,&load[i])==0);++i)
if (load[i].p[load[i].index])
++load[i].index;
else
flag=1;
if (i-low>1)
qsort(&load[low],i-low,sizeof (*load),comp);
if (height-low<2)
return ;
if (flag==0)
_sort(load,low,i,comp);
_sort(load,i,height,comp);
}
}
[此贴子已经被作者于2018-5-2 22:12编辑过]
