Bra*_*art 18 c sorting case-sensitive alphabetical
我需要交流语言代码来排序一些字符串,它应该区分大小写,对于大写和小写的相同字母,小写必须首先出现.例如,以下字符串的排序结果:
eggs
bacon
cheese
Milk
spinach
potatoes
milk
spaghetti
应该:
bacon
cheese
eggs
milk
Milk
potatoes
spaghetti
spinach
我写了一段代码,但结果是:
Milk
bacon
cheese
eggs
milk
potatoes
spaghetti
spinach
我不知道如何改进这个,我已经搜索了很多.任何人都可以帮我这个吗？
#include <stdio.h>
#include <string.h>
int main(){
char c;
char name[20][10], temp[10];
int count_name = 0;
int name_index = 0;
int i, j;
while ((c = getchar()) != EOF){
if (c == 10){
name[count_name][name_index] = '\0';
count_name++;
name_index = 0;
} else {
name[count_name][name_index] = c;
name_index++;
}
}
for(i=0; i < count_name-1 ; i++){
for(j=i+1; j< count_name; j++)
{
if(strcmp(name[i],name[j]) > 0)
{
strcpy(temp,name[i]);
strcpy(name[i],name[j]);
strcpy(name[j],temp);
}
}
}
for (i = 0; i < count_name; i++){
printf("%s\n", name[i]);
}
}
jxh*_*jxh 21
对于单词列表,将"相同"单词组合在一起通常更有用(即使它们在大小写上有所不同).例如:
Keeping things together: Simple "M after m":
------------------------ -------------------
mars mars
mars bar mars bar
Mars bar milk
milk milk-duds
Milk milky-way
milk-duds Mars bar
milky-way Milk
Milky-way Milky-way
如果您想要像第一列那样排列的单词,我提出了三种方法:
strcasecmp()联合strcmp().isalpha(),tolower()和isupper().最后,我讨论了两种选择:
如果可以这样做,请避免重新发明轮子.在这种情况下,我们可以通过使用POSIX函数strcasecmp()来查看它们是否与不区分大小写的比较相等,并strcmp()在它们出现时重新开始.
int alphaBetize (const char *a, const char *b) {
int r = strcasecmp(a, b);
if (r) return r;
/* if equal ignoring case, use opposite of strcmp() result to get
* lower before upper */
return -strcmp(a, b); /* aka: return strcmp(b, a); */
}
(在某些系统上,会调用不区分大小写的比较函数stricmp()或_stricmp().如果您无法使用,则会在下面提供实现.)
#ifdef I_DONT_HAVE_STRCASECMP
int strcasecmp (const char *a, const char *b) {
while (*a && *b) {
if (tolower(*a) != tolower(*b)) {
break;
}
++a;
++b;
}
return tolower(*a) - tolower(*b);
}
#endif
有时候,现有功能的表现不够好,你必须做些其他事情来加快速度.以下函数在单次传递中以大致相同的方式进行比较,并且不使用任何一个strcasecmp()或strcmp().但是,它将所有非字母字符视为小于字母.
int alphaBetize (const char *a, const char *b) {
int weight = 0;
do {
if (*a != *b) {
if (!(isalpha(*a) && isalpha(*b))) {
if (isalpha(*a) || isalpha(*b)) {
return isalpha(*a) - isalpha(*b);
}
return *a - *b;
}
if (tolower(*a) != tolower(*b)) {
return tolower(*a) - tolower(*b);
}
/* treat as equal, but mark the weight if not set */
if (weight == 0) {
weight = isupper(*a) - isupper(*b);
}
}
++a;
++b;
} while (*a && *b);
/* if the words compared equal, use the weight as tie breaker */
if (*a == *b) {
return weight;
}
return !*b - !*a;
}
即使列表包含,使用此比较进行排序也将保持milk并且Milk彼此相邻milk-duds.
这是一种从"配置"动态创建整理表的方法.它用于说明一种改变字符串比较方式的对比技术.
您可以映射字母表的字母与一种简单表格的比较,该表格描述了您希望字母(或除NUL字节之外的任何字符)的相对顺序:
const char * alphaBetical =
"aAbBcCdDeEfFgGhHiIjJkKlLmMnNoOpPqQrRsStTuUvVwWxXyYzZ";
从这个排序中,我们可以创建一个查找表来查看两个字母应该如何相互比较.如果表尚未完成,则以下函数初始化表,否则执行表查找.
int alphaBeta_lookup (int c) {
static int initialized;
static char table[CHAR_MAX+1];
if (!initialized) {
/* leave all non-alphaBeticals in their relative order, but below
alphaBeticals */
int i, j;
for (i = j = 1; i < CHAR_MAX+1; ++i) {
if (strchr(alphaBetical, i)) continue;
table[i] = j++;
}
/* now run through the alphaBeticals */
for (i = 0; alphaBetical[i]; ++i) {
table[(int)alphaBetical[i]] = j++;
}
initialized = 1;
}
/* return the computed ordinal of the provided character */
if (c < 0 || c > CHAR_MAX) return c;
return table[c];
}
使用这个查找表,我们现在可以简化alphaBetize()比较函数的循环体:
int alphaBetize (const char *a, const char *b) {
int ax = alphaBeta_lookup(*a);
int bx = alphaBeta_lookup(*b);
int weight = 0;
do {
char al = tolower(*a);
char bl = tolower(*b);
if (ax != bx) {
if (al != bl) {
return alphaBeta_lookup(al) - alphaBeta_lookup(bl);
}
if (weight == 0) {
weight = ax - bx;
}
}
ax = alphaBeta_lookup(*++a);
bx = alphaBeta_lookup(*++b);
} while (ax && bx);
/* if the words compared equal, use the weight as tie breaker */
return (ax != bx) ? !bx - !ax : weight;
}
使用整理表,您可以使用简化的比较功能创建许多不同的顺序,例如:
int simple_collating (const char *a, const char *b) {
while (alphaBeta_lookup(*a) == alphaBeta_lookup(*b)) {
if (*a == '\0') break;
++a, ++b;
}
return alphaBeta_lookup(*a) - alphaBeta_lookup(*b);
}
使用相同的功能并通过修改alphaBetical字符串,您几乎可以实现任何所需的顺序(按字母顺序排列,反向字母顺序,辅音之前的元音等).然而,将类似单词保持在一起的安排需要在大写字母中加入大写单词,这只能通过进行忽略大小写的比较来完成.
请注意,使用simple_collating()上面的函数和alphaBetical我提供的字符串,Bacon将在之前milk,但Mars将在milk之前和之后Milk.
如果要使用已为区域设置定义的整理顺序,可以设置区域设置并调用整理比较功能:
/*
* To change the collating locale, use (for example):
setlocale(LC_COLLATE, "en.US");
*/
int iso_collating (const char *a, const char *b) {
return strcoll(a, b);
}
现在,通过更改区域设置,排序顺序将基于标准化的整理顺序.
daw*_*awg 10
您可以编写自定义比较函数进行排序.
首先,查看默认的strcmp排序顺序:
#include <stdio.h>
#include <stdlib.h>
#include <ctype.h>
#include <string.h>
const char *tgt[]={
"bacon", "Bacon", "mIlk", "Milk", "spinach", "MILK", "milk", "eggs"
};
int tgt_size=8;
static int cmp(const void *p1, const void *p2){
return strcmp(* (char * const *) p1, * (char * const *) p2);
}
int main(int argc, char *argv[]) {
printf("Before sort:\n\t");
for(int n=0; n<tgt_size; n++)
printf("%s ", tgt[n]);
qsort(tgt, tgt_size, sizeof(char *), cmp);
printf("\nAfter sort:\n\t");
for(int n=0; n<tgt_size; n++)
printf("%s ", tgt[n]);
return 0;
}
strcmp按ASCII字符代码排序; 即,它排序A-Z然后a-z所有资本AZ来到任何带小写字母的单词之前:
Before sort:
bacon Bacon mIlk Milk spinach MILK milk eggs
After sort:
Bacon MILK Milk bacon eggs mIlk milk spinach
我们可以写在使用我们自己的比较函数cmp用于qsort忽略的情况.看起来像这样:
int mycmp(const char *a, const char *b) {
const char *cp1 = a, *cp2 = b;
for (; toupper(*cp1) == toupper(*cp2); cp1++, cp2++)
if (*cp1 == '\0')
return 0;
return ((toupper(*cp1) < toupper(*cp2)) ? -1 : +1);
}
一定要cmp改为:
static int cmp(const void *p1, const void *p2){
return mycmp(* (char * const *) p1, * (char * const *) p2);
}
忽略版本的案例现在打印:
Before sort:
bacon Bacon mIlk Milk spinach MILK milk eggs
After sort:
bacon Bacon eggs Milk MILK milk mIlk spinach
这与POSIX函数strcasecmp的输出相同.
该函数mycmp首先按正常顺序按字典顺序进行比较[a|A]-[z|Z].这意味着你会得到像字母一样的字母,但你可能得到bacon, Bacon的可能性Bacon, bacon.这是因为qsort不是一个稳定的排序,'培根'比较等于'培根'.
现在我们想要的是如果比较为0而忽略大小写(即,像"牛奶"和"牛奶"这样的同一个词)现在比较包括大小写并反转顺序:
int mycmp(const char *a, const char *b) {
const char *cp1 = a, *cp2 = b;
int sccmp=1;
for (; toupper(*cp1) == toupper(*cp2); cp1++, cp2++)
if (*cp1 == '\0')
sccmp = 0;
if (sccmp) return ((toupper(*cp1) < toupper(*cp2)) ? -1 : +1);
for (; *a == *b; a++, b++)
if (*a == '\0')
return 0;
return ((*a < *b) ? +1 : -1);
}
最终版本打印:
Before sort:
bacon Bacon mIlk Milk spinach MILK milk eggs
After sort:
bacon Bacon eggs milk mIlk Milk MILK spinach
不幸的是,这种方法对于UNICODE来说变得难以处理.对于复杂排序,请考虑使用具有稳定排序的映射或多步排序.
对于复杂和位置感知的字母排序规则,请考虑Unicode排序规则.例如,在不同的位置,字母按字母顺序排列:
Swedish z < ö
y == w
German ö < z
Danish Z < Å
Lithuanian i < y < k
Tr German ä == æ
Tr Spanish c < ch < d
German Dictionary Sort: of < öf
German Phonebook Sort: öf < of
这些区别的默认值在默认Unicode排序规则元素表(DUCET)中捕获,该表为UNICODE排序规则和字符串比较提供默认映射.您可以修改默认值以捕获字典排序和电话簿排序,不同位置或案例的不同处理之间的区别.在Unicode公共区域设置数据存储库(CLDR)中主动跟踪各个位置变体.
多级排序的推荐是分层的:
Level Description Examples
L1 Base characters role < roles < rule
L2 Accents role < rôle < roles
L3 Case/Variants role < Role < rôle
L4 Punctuation role < “role” < Role
Ln Identical role < ro?le < “role”
ICU库中广泛使用的Unicode排序规则实现.几个示例的默认DUCET排序规则是:
b < B < bad < Bad < bäd
c < C < cote < coté < côte < côté
您可以使用ICU Explorer浏览 ICU库并更改位置和目标
如果您想为giggles实现自己的DUCET版本,可以按照此Python脚本中使用的常规方法进行操作.这不是压倒性的,但不是微不足道的.