Kaip rūšiuoti styginių masyvą abėcėlės tvarka (didžiosios ir mažosios raidės)

Noriu surūšiuoti kai kurias eilutes, ir noriu surinkti c kalbos kodą, ir jis turi būti jautrus didžiosios ir mažosios raidės, o mažosios raidės turi būti pirmosios . Pvz., Rūšiavimo pagal šias eilutes rezultatas:

 eggs bacon cheese Milk spinach potatoes milk spaghetti 

turėtų būti:

 bacon cheese eggs milk Milk potatoes spaghetti spinach 

Aš parašiau kodą, bet rezultatas yra:

 Milk bacon cheese eggs milk potatoes spaghetti spinach 

Aš nežinau, kaip tai pagerinti, ir aš daug ieškojau. Ar kas nors man gali tai padėti?

 #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]); } } 
15
28 сент. nustatė Brad Capehart rugsėjo 28 d 2012-09-28 23:09 '12 - 23:09 2012-09-28 23:09
@ 6 atsakymai

Palaikykite panašius žodžius kartu ...

Žodžių sąrašams dažnai yra naudinga grupuoti „tuos pačius“ žodžius (nors jie skiriasi tuo atveju). Pavyzdžiui:

 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 

Jei norite, kad žodžiai būtų išdėstyti kaip pirmasis stulpelis, siūlau tris būdus, kaip tai padaryti:

  • Naudokite strcasecmp() kartu su strcmp() .
  • Vieno leidimo įgyvendinimas, kuris seka simbolio tipą su isalpha() , tolower() ir isupper() .
  • Vieno leidimo įgyvendinimas naudojant žemėlapių lentelę.

Galų gale aptarsiu dvi alternatyvas:

  • Naudodami rūšiavimo lentelę nustatykite savavališką tvarką.
  • Vietos nustatymas vietiniam žemėlapių naudojimui.

Galimų bibliotekos funkcijų naudojimas

Jei įmanoma, venkite pakartotinio rato naudojimo. Šiuo atveju mes galime tai padaryti naudodami POSIX strcasecmp() funkciją, kad įsitikintume, jog jie yra lygūs nejautriam palyginimui ir grįžta į strcmp() kai jie yra.

 int alphaBetize (const char *a, const char *b) { int r = strcasecmp(a, b); if (r) return r;  return -strcmp(a, b);  } 

(Kai kuriose sistemose nejautrus palyginimo funkcija vadinama stricmp() arba _stricmp() Jei vienas iš jų nėra, įgyvendinimas pateikiamas toliau.)

 #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 

Venkite dviejų eilučių eilučių

Kartais esamos funkcijos neveikia pakankamai efektyviai, ir jums reikia ką nors padaryti, kad pagreitintumėte darbą. Toliau pateikta funkcija daro palyginimą maždaug vienodai per vieną leidimą ir nenaudojant strcasecmp() arba strcmp() . Bet ji neapibrėžtus simbolius laiko mažiau raidėmis.

 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); }  if (weight == 0) { weight = isupper(*a) - isupper(*b); } } ++a; ++b; } while (*a  *b);  if (*a == *b) { return weight; } return !*b - !*a; } 

Naudojant šį palyginimą rūšiavimui, milk ir milk bus laikomi vienas šalia kito, net jei sąraše yra milk-duds .

Rūšiavimo lentelės naudojimas

Čia yra būdas dinamiškai sukurti rūšiavimo lentelę iš „konfigūracijos“. Jis iliustruoja kontrasto metodą, skirtą keisti stygų palyginimą.

Galite suderinti abėcėlės raidžių palyginimą su paprasta lentele, kurioje aprašoma santykinė tvarka, kurioje norite, kad raidės (arba bet koks kitas simbolis, išskyrus „NUL“ baitą) būtų:

 const char * alphaBetical = "aAbBcCdDeEfFgGhHiIjJkKlLmMnNoOpPqQrRsStTuUvVwWxXyYzZ"; 

Iš šio užsakymo galime sukurti atskaitos lentelę, kad pamatytume, kaip dvi raidės turėtų būti lyginamos viena su kita. Ši funkcija inicijuoja lentelę, jei ji dar nebuvo įvykdyta ir kitaip ieško lentelės.

 int alphaBeta_lookup (int c) { static int initialized; static char table[CHAR_MAX+1]; if (!initialized) {  int i, j; for (i = j = 1; i < CHAR_MAX+1; ++i) { if (strchr(alphaBetical, i)) continue; table[i] = j++; }  for (i = 0; alphaBetical[i]; ++i) { table[(int)alphaBetical[i]] = j++; } initialized = 1; }  if (c < 0 || c > CHAR_MAX) return c; return table[c]; } 

Naudodami šią atskaitos lentelę, dabar galite supaprastinti „ alphaBetize() palyginimo funkcijos kilpos korpusą:

 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);  return (ax != bx) ? !bx - !ax : weight; } 

Ar galime padaryti tai lengviau?

Naudojant rūšiavimo lentelę, galite sukurti daug skirtingų užsakymų su supaprastinta lyginimo funkcija, pavyzdžiui:

 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); } 

Naudojant tą pačią funkciją ir pakeisdami alphaBetical eilutę, galite pasiekti beveik bet kokią pageidaujamą tvarką (abėcėlę, atvirkštinę abėcėlę, balsius priešaisius ir pan.). Tačiau, suderinant žodžius, reikia supainioti žodžius su mažaisiais žodžiais, ir tai galima padaryti tik lyginant, kurį atvejį ignoruoja.

Atkreipkite dėmesį, kad naudojant funkciją „ alphaBetical simple_collating() ir „ alphaBetical liniją, kurią pateikiau, „ Bacon “ pasirodys prieš milk , bet Mars eis po milk ir prieš milk .

Jei norite rūšiuoti pagal jūsų kalbą.

Jei norite naudoti rūšiavimo seką, kuri jau nustatyta jūsų vietovei, galite nustatyti lokalę ir skambinti rūšiavimo palyginimo funkcija:

  int iso_collating (const char *a, const char *b) { return strcoll(a, b); } 

Dabar, keisdami lokalę, rūšiavimo tvarka bus pagrįsta standartizuota rūšiavimo seka.

20
23 авг. atsakymas pateikiamas liepos 23 d. 2014-08-23 15:42 '14, 15:42 2014-08-23 15:42

Rūšiavimui galite parašyti pasirinktinį palyginimo funkciją.

Pirmiausia pažiūrėkite į strcmp rūšiavimo tvarką :

 #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 surūšiuotas pagal ASCII simbolių kodą; t.y. jis rūšiuoja AZ , tada AZ , todėl visas kapitalas AZ eina į bet kokį žodį su mažąja raide:

 Before sort: bacon Bacon mIlk Milk spinach MILK milk eggs After sort: Bacon MILK Milk bacon eggs mIlk milk spinach 

Mes galime rašyti savo palyginimo funkciją, naudojamą „ cmp , naudojamą „ qsort , kuri ignoruoja atvejį. Tai atrodo taip:

 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); } 

Būtinai pakeiskite „ cmp į:

 static int cmp(const void *p1, const void *p2){ return mycmp(* (char * const *) p1, * (char * const *) p2); } 

Dabar versija ignoruojama versija ignoruojama:

 Before sort: bacon Bacon mIlk Milk spinach MILK milk eggs After sort: bacon Bacon eggs Milk MILK milk mIlk spinach 

Tai tas pats rezultatas, kurį gaunate su POSIX strcasecmp funkcija.

mycmp funkcija pirmiausia lygina leksikografiją įprastu būdu [a|A]-[z|Z] . Tai reiškia, kad kartu gausite abu raidžių žodžius, bet jūs galite gauti bacon, Bacon kaip ir bacon, Bacon . Taip yra dėl to, kad „qsort“ nėra stabili , o „Bacon“ lyginama su „šonine“.

Dabar tai, ko mes norime, yra 0 palyginimas, ignoruojant atvejį (pavyzdžiui, tas pats žodis kaip „PIENAS“ ir „pienas“) dabar palygina bylą ir panaikina užsakymą:

border=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); } 

Galutinės versijos:

 Before sort: bacon Bacon mIlk Milk spinach MILK milk eggs After sort: bacon Bacon eggs Milk MILK milk mIlk spinach 

Deja, šis požiūris tampa sudėtingas UNICODE. Sudėtingiems tipams apsvarstykite galimybę naudoti kartografavimą arba daugiapakopį rūšiavimą su stabiliu rūšiavimu .

Sudėtingiems ir į vietovę orientuotiems abėcėliniams rodikliams apsvarstykite Unicode derinius . Pavyzdžiui, skirtingose ​​vietose abėcėlės raidės skiriasi:

 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 

Šių skirtumų numatytosios vertės nustatomos pagal Unicode numatytąjį lyginimo lentelę ( DUCET ), kuri pateikia numatytąjį UNICODE rūšiavimo ir styginių palyginimo žemėlapį. Galite pakeisti numatytuosius nustatymus, kad būtų galima nustatyti skirtumą tarp žodynų rūšiavimo ir telefonų knygos, skirtingų vietų arba skirtingų gydymo būdų rūšiavimo. Individualios vietos keitimo vietos aktyviai stebimos „Unicode Common Locale“ duomenų saugykloje ( CLDR ).

Rekomendacija dėl kelių lygių rūšiavimo yra kelių lygių:

 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" 

Plačiai naudojamas Unicode kodų įgyvendinimas yra ICU bibliotekoje . Numatytoji DUCET vertė keliems pavyzdžiams yra:

 b < B < bad < Bad < bäd c < C < cote < coté < côte < côté 

Galite ištirti ICU biblioteką ir keisti vietoves bei tikslus naudodami ICU Explorer

Jei norite įgyvendinti savo „DUCET“ versiją giggavimui, galite vadovautis bendruoju metodu, naudojamu šiame „ Python“ scenarijuje . Tai nėra didžiulis, bet ne trivialus.

9
23 авг. atsakymas pateikiamas 23 d. 2014-08-23 02:13 '14 at 2:13 2014-08-23 02:13

Čia, jei aš teisingai suprantu, norite kažką, kaip apibūdinčiau taip:

Reikalingas nejautrus rūšiavimas, kuriame turi būti naudojama „mažųjų raidžių pirmoji“ sąsaja.

Taip patinka:

  • earlier_letter_in_the_alphabet < later_letter_in_the_alphabet ignoruojant bylą

  • lowercase < uppercase

  • shorter_word < wider_word
    • Ji nebuvo paminėta, ją skolinau leksikografine tvarka, žodynuose
    • Galima naudoti tik lyginant '\0' kiek įmanoma mažesnę.

2 veiksmas bus atliekamas tik tuo atveju, jei 1 nieko nepadarė. 3 žingsnis jau bus patikrintas iš 1. Visa tai turi būti parašyta, o tai reiškia, kad jūs turite pereiti prie 2, kai tik gausite ryšį tarp atitinkamų simbolių, o ne tik tada, kai visos linijos yra lygios.


Darant prielaidą, kad tai buvo teisinga, viskas, ką mums reikia padaryti, yra parašyti funkciją, kuri leistų mums palyginti šį bet kurį iš dviejų linijų.

 #include <ctype.h> // for tolower and islower int my_character_compare(const char a, const char b) { int my_result; my_result = tolower(a) - tolower(b); // unless it is zero, my_result is definitely the result here // Note: if any one of them was 0, result will also properly favour that one if (my_result == 0  a != b) // if (could not be distinguished with #1, but are different) { // means that they are case-insensitively same // but different... // means that one of them are lowercase, the other one is upper if (islower(a)) return -1; // favour a else return 1; // favour b } // regardless if zero or not, my_result is definitely just the result return my_result; } int my_string_compare(const char * a, const char * b) { int my_result; my_result = my_character_compare(*a, *b); // unless it is zero, my_result is definitely the result here while (my_result == 0  *a != 0) // current characters deemed to be same // if they are not both just 0 we will have to check the next ones { my_result = my_character_compare(*++a, *++b); } // whatever the my_result has been: // whether it became != zero on the way and broke out of the loop // or it is still zero, but we have also reached the end of the road/strings return my_result; } 

Susitarimo / taisyklės palyginimo funkcija turi grąžinti neigiamą vertę, kad pirmasis parametras būtų priešais, neigiama vertė, palaikanti antrąjį parametrą, nulis, jei jis negali atskirti. Tiesiog papildoma informacija, kurią tikriausiai jau žinote, kaip naudojate strcmp .

Ir tai! Pakeitus šį strcmp kodą su „ my_string_compare čia, taip pat kuriant šias apibrėžtis, kurias sukūrėme iš viršaus, turėtų būti pateiktas teisingas rezultatas. Iš tiesų, jis pateikia tikėtiną rezultatą atitinkamam įvesties pavyzdžiui.

Žinoma, galima būtų sumažinti apibrėžtis, padariau jas ilgai, kad būtų lengviau suprasti, kas vyksta. Pavyzdžiui, galėčiau suvirinti visus šiuos dalykus:

 #include <ctype.h> int my_string_compare(const char * a, const char * b) { int my_result; while (*a || *b) { if ((my_result = tolower(*a) - tolower(*b))) return my_result; if (*a != *b) return (islower(*a)) ? -1 : 1; a++; b++; } return 0; } 

Iš esmės tas pats su kitu, galite naudoti tai, kas jums patinka; ar dar geriau, rašykite.

3
23 авг. atsakymą pateikė ThoAppelsin rugpjūčio 23 d 2014-08-23 13:49 '14 at 13:49 2014-08-23 13:49

Aš vėluojau dėl šios diskusijos ir neturiu jokių specialių lūkesčių laimėti ir laimėti nuostabų prizą, bet nematydamas sprendimo, naudodamasis idėjomis, kurias aš pirmą kartą žiūrėjau, maniau, kad paskambinsiu.

Mano pirmoji mintis skaityti problemos specifikaciją buvo tam tikra pasirinktinio rūšiavimo seka, kurią aš iš esmės aptikiau @jxh naudojant žemėlapių lentelės vaizdą . Aš nematau atvejo jautrumo kaip pagrindinės sąvokos, tik nelyginių skaičių užsakymo.

Taigi, siūlau šį kodą tik kaip alternatyvų įgyvendinimą. Tai būdinga glibc-qsort_r (3), tačiau ji yra panaši į lengvesnį požiūrį ir palaiko daugybę rūšiavimo sekų vykdymo metu. Bet tai yra šiek tiek patikrinta, ir aš, greičiausiai, nematau trūkumų. Tarp jų: ​​nematau daug dėmesio Unicode arba apskritai plataus simbolių pasauliui, o ne nepasirašytai charijai, kad būtų išvengta neigiamų neigiamų rodiklių lentelėje.

 #include <stdio.h> #include <limits.h>  int collating_init(const char *co, int *cv, size_t n) { const unsigned char *uco = (const unsigned char *) co; const unsigned char *s; size_t i; if (n <= UCHAR_MAX) { return -1; } for (i = 0; i < n; i++) {  cv[i] = UCHAR_MAX; } for (s = uco; *s; s++) {  cv[*s] = (s - uco); } return 0; } static int _collating_compare(const char *str1, const char *str2, int *ip) { const unsigned char *s1 = (const unsigned char *) str1; const unsigned char *s2 = (const unsigned char *) str2; while (*s1 != '\0'  *s2 != '\0') { int cv1 = ip[*s1++]; int cv2 = ip[*s2++]; if (cv1 < cv2) return -1; if (cv1 > cv2) return 1; } if (*s1 == '\0'  *s2 == '\0') { return 0; } else { return *s1 == '\0' ? -1 : 1; } } int collating_compare(const void *v1, const void *v2, void *p) { return _collating_compare(*(const char **) v1, *(const char **) v2, (int *) p); } 

Ankstesnis yra šalia kodo, kurį galima įdėti į atskirą modulį ar biblioteką, tačiau neturi savo antraštės failo (arba įrašų antraštės faile). Mano bandymas tiesiog sujungia kodą aukščiau ir žemiau į failą, vadinamą custom_collate_sort.c ir naudoja

 gcc -DMAIN_TEST -Wall -o custom_collate_sort custom_collate_sort.c 

... ją surinkti.

 #if defined(MAIN_TEST)  #define __USE_GNU #include <stdlib.h> #include <string.h> #define NELEM(x) (sizeof x / sizeof 0[x]) static int cmp(const void *v1, const void *v2) { return strcmp(*(const char **) v1, *(const char **) v2); } static int casecmp(const void *v1, const void *v2) { return strcasecmp(*(const char **) v1, *(const char **) v2); } int main(int ac, char *av[]) { size_t i; int cval[256], ret; int cval_rev[256], rret; char *tosort[] = { "cheeSE", "eggs", "Milk", "potatoes", "cheese", "spaghetti", "eggs", "milk", "spinach", "bacon", "egg", "apple", "PEAR", "pea", "berry" }; ret = collating_init("aAbBcCdDeEfFgGhHiIjJkKlLmMnNoOpPqQrRsStTuUvVxXyYzZ", cval, NELEM(cval)); rret = collating_init("ZzYyXxVvUuTtSsRrQqPpOoNnMmLlKkJjIiHhGgFfEeDdCcBbAa", cval_rev, NELEM(cval_rev)); if (ret == -1 || rret == -1) { fputs("collating value array must accomodate an index of UCHAR_MAX\n", stderr); return 1; } puts("Unsorted:"); for (i = 0; i < NELEM(tosort); i++) { printf(" %s\n", tosort[i]); } qsort((void *) tosort, NELEM(tosort), sizeof tosort[0], cmp); puts("Sorted w/ strcmp:"); for (i = 0; i < NELEM(tosort); i++) { printf(" %s\n", tosort[i]); } qsort((void *) tosort, NELEM(tosort), sizeof tosort[0], casecmp); puts("Sorted w/ strcasecmp:"); for (i = 0; i < NELEM(tosort); i++) { printf(" %s\n", tosort[i]); } qsort_r((void *) tosort, NELEM(tosort), sizeof tosort[0], collating_compare, (void *) cval); puts("Sorted w/ collating sequence:"); for (i = 0; i < NELEM(tosort); i++) { printf(" %s\n", tosort[i]); } qsort_r((void *) tosort, NELEM(tosort), sizeof tosort[0], collating_compare, (void *) cval_rev); puts("Sorted w/ reversed collating sequence:"); for (i = 0; i < NELEM(tosort); i++) { printf(" %s\n", tosort[i]); } return 0; } #endif  
3
28 авг. atsakymas pateikiamas sjnarv 28 rug . 2014-08-28 20:13 „14, 20:13 2014-08-28 20:13

OP kodo raktas yra naudoti strcmp() funkciją, kad palygintumėte dvi eilutes.
Taigi, pradėsiu pakeisti šią standartinę funkciją su kita, pavyzdžiui:

  // We assume that the collating sequence satisfies the following rules: // 'A' < 'B' < 'C' < ... // 'a' < 'b' < 'c' < ... // We don't make any other assumptions. #include <ctype.h> int my_strcmp(const char * s1, const char * s2) { const char *p1 = s1, *p2 = s2; while(*p1 == *p2  *p1 != '\0'  *p2 != '\0') p1++, p2++;  if (*p1 == *p2) return 0; if (*p1 == '\0') return -1; if (*p2 == '\0') return +1; char c1 = tolower(*p1), c2 = tolower(*p2); int u1 = isupper(*p1) != 0, u2 = isupper(*p2) != 0; if (c1 != c2) return c1 - c2; // <<--- Alphabetical order assumption is used here if (c1 == c2) return u1 - u2; } 

Paskutines eilutes galima suspausti taip:

  return (c1 != c2)? c1 - c2: u1 - u2; 

Dabar pakeisdami strcmp() su my_strcmp() , gausite norimą rezultatą.

Rūšiavimo algoritme rekomenduojama atskirai galvoti apie tris pagrindinius aspektus:

  • Palyginimo funkcija
  • Abstraktus rūšiavimo algoritmas, kurį naudosime.
  • Šių duomenų kelias bus „perkeltas“ į masyvą, kai jums reikės keisti du elementus.

Šie aspektai gali būti optimizuoti nepriklausomai.
Tokiu būdu, kai tik jūs turite gerai nustatytą palyginimo funkciją, kitas optimizavimo žingsnis gali būti pakeisti dvigubą rūšiavimo algoritmą efektyvesniam, pvz., Quicksort, algoritmui.
Visų pirma, standartinės bibliotekos <stdlib.h> qsort() funkcija suteikia jums tokį algoritmą, taigi jums nereikia jaudintis dėl programavimo.
Galiausiai, strategija, kurią naudojate informacijos apie masyvą saugojimui, gali turėti reikšmės.
Būtų patogu laikyti eilutes, pvz., „Rodyklių masyvą į„ char “, o ne„ šriftų masyvų masyvą “, nes apsikeitimo žymekliai yra greitesni nei pakeičiant dvi visas simbolių grupes.

Rodyklės matricos

PAPILDOMA PASTABA: pirmieji trys, if() yra iš tikrųjų nereikalingi, nes šių sakinių logika reiškia norimą rezultatą, kai *p1 arba *p2 yra 0. Tačiau, išlaikant šiuos, if() , kodas tampa aiškesnis.

3
23 авг. atsakymas pateikiamas pablo1977 23 rug . 2014-08-23 05:48 '14 ne 5:48 2014-08-23 05:48

Standartiniai antraštės failai, kurių reikalaujama programoje:

 #include <stdio.h> #include <stdlib.h> #include <string.h> 

Pagrindinė programa prasideda čia:

 //Global Variables Required //========= const char *tgt[]={"bacon", "Bacon", "mIlk", "Milk", "spinach", "MILK", "milk", "eggs"}; //Array for sorting int tgt_size=8; //Total Number of Records int SortLookupTable[128]; //Custom sorting table typedef int cmp_t (const void *, const void *); int main(int argc, char *argv[]) { printf("Before sort:\n\n"); int n=0; for(n=0; n<tgt_size; n++) printf("%s\n", tgt[n]); CreateSortTable(); myQsort(tgt, tgt_size, sizeof(char *),  printf("\n\n====\n\n"); for(n=0; n<tgt_size; n++) printf("%s\n", tgt[n]); return 0; } 

Priskirta rūšiavimo lentelė, kaip reikalaujama:

 void CreateSortTable(void){ int i; for (i = 0; i < 128; i++){ SortLookupTable[i] = 0; } char *s; s=(char *)malloc(64); memset(s, 0, 64); strcpy(s, "aAbBcCdDeEfFgGhHiIjJkKlLmMnNoOpPqQrRsStTuUvVwWxXyYzZ"); i=1; for (; *s; s++){ SortLookupTable[(int) ((unsigned char) *s)]=i; i++; } } 

Greitas algoritmas. Taip pat galite naudoti standartinę biblioteką:

 //Some important Definations required by Quick Sort ======= #define SWAPINIT(a, es) swaptype = ((char *)a - (char *)0) % sizeof(long) || \ es % sizeof(long) ? 2 : es == sizeof(long)? 0 : 1; #define swap(a, b) \ if (swaptype == 0) { \ long t = *(long *)(a); \ *(long *)(a) = *(long *)(b); \ *(long *)(b) = t; \ } else \ swapfunc(a, b, es, swaptype) #define vecswap(a, b, n) if ((n) > 0) swapfunc(a, b, n, swaptype) #define swapcode(TYPE, parmi, parmj, n) { \ long i = (n) / sizeof (TYPE); \ register TYPE *pi = (TYPE *) (parmi); \ register TYPE *pj = (TYPE *) (parmj); \ do { \ register TYPE t = *pi; \ *pi++ = *pj; \ *pj++ = t; \ } while (--i > 0); \ } #define min(a, b) (a) < (b) ? a : b //Other important function void swapfunc(char *a, char *b, int n, int swaptype){ if(swaptype <= 1) swapcode(long, a, b, n) else swapcode(char, a, b, n) } char * med3(char *a, char *b, char *c, cmp_t *cmp){ if ( cmp(a, b) < 0){ if (cmp(b, c) < 0){ return b; }else{ if ( cmp(a, c) < 0){ return c; }else{ return a; } } }else{ if (cmp(b, c) < 0){ return b; }else{ if ( cmp(a, c) < 0){ return a; }else{ return c; } } } } //Custom Quick Sort void myQsort(void *a, unsigned int n, unsigned int es, cmp_t *cmp){ char *pa, *pb, *pc, *pd, *pl, *pm, *pn; int d, r, swaptype, swap_cnt; loop: SWAPINIT(a, es); swap_cnt = 0; if (n < 7) { for (pm = (char *)a + es; pm < (char *)a + n * es; pm += es) for (pl = pm; pl > (char *)a  cmp(pl - es, pl) > 0; pl -= es){ swap(pl, pl - es); } return; } pm = (char *)a + (n / 2) * es; if (n > 7) { pl = a; pn = (char *)a + (n - 1) * es; if (n > 40) { d = (n / 8) * es; pl = med3(pl, pl + d, pl + 2 * d, cmp); pm = med3(pm - d, pm, pm + d, cmp); pn = med3(pn - 2 * d, pn - d, pn, cmp); } pm = med3(pl, pm, pn, cmp); } swap(a, pm); pa = pb = (char *)a + es; pc = pd = (char *)a + (n - 1) * es; for (;;) { while (pb <= pc  (r = cmp(pb, a)) <= 0) { if (r == 0) { swap_cnt = 1; swap(pa, pb); pa += es; } pb += es; } while (pb <= pc  (r = cmp(pc, a)) >= 0) { if (r == 0) { swap_cnt = 1; swap(pc, pd); pd -= es; } pc -= es; } if (pb > pc) break; swap(pb, pc); swap_cnt = 1; pb += es; pc -= es; } if (swap_cnt == 0) {  for (pm = (char *)a + es; pm < (char *)a + n * es; pm += es) for (pl = pm; pl > (char *)a  cmp(pl - es, pl) > 0; pl -= es) swap(pl, pl - es); return; } pn = (char *)a + n * es; r = min(pa - (char *)a, pb - pa); vecswap(a, pb - r, r); r = min(pd - pc, pn - pd - es); vecswap(pb, pn - r, r); if ((r = pb - pa) > es) myQsort(a, r / es, es, cmp); if ((r = pd - pc) > es) {  a = pn - r; n = r / es; goto loop; } }