подсчет сортировки со строкой ввода, имеющей алфавиты и цифры

Question

#include<stdio.h> 
#include<conio.h> 
#include<string.h> 
#include<stdlib.h> 
void countingsort(char *str) 
{ 
int count[256]; 
int i; 
char output[20]; 
memset(count,0,256); 
for(i=0;str[i];i++) 
    ++count[str[i]]; 
for(i=1;i<256;i++) 
    count[i]+=count[i-1]; 
for(i=0;str[i];i++) 
    output[--count[str[i]]]=str[i]; 
for(i=0;str[i];i++) 
    str[i]=output[i]; 
} 
int main() 
{ 
char str[]="123ab78bj45ui"; 
countingsort(str); 
printf("%s",str); 
getch(); 
return 0; 
} 

Я не знаю, где проблема. Я думаю, что я прав, но во время выполнения он дает эту ошибку: «Необработанное исключение в 0x013814f5 в countingsort.exe: 0xC0000005: место записи нарушения прав доступа 0x33562813». Может кто подскажет, где я иду не так.

Answer 1

Даже если код будет очищен в презентации:

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

void countingsort(char *str); 

void countingsort(char *str) 
{ 
    int count[256]; 
    int i; 
    char output[20]; 
    memset(count, 0, 256); 
    for (i = 0; str[i]; i++) 
     ++count[str[i]]; 
    for (i = 1; i < 256; i++) 
     count[i] += count[i-1]; 
    for (i = 0; str[i]; i++) 
     output[--count[str[i]]] = str[i]; 
    for (i = 0; str[i]; i++) 
     str[i] = output[i]; 
} 

int main(void) 
{ 
    char str[] = "123ab78bj45ui"; 
    countingsort(str); 
    printf("%s\n", str); 
    return 0; 
} 

GCC 4.8.1 дает предупреждения, которые вариант -Werror превращается в ошибки:

$ gcc -O3 -g -std=c11 -Wall -Wextra -Wmissing-prototypes -Wstrict-prototypes -Wold-style-definition -Werror cs.c -o cs 
cs.c: In function ‘countingsort’: 
cs.c:13:9: error: array subscript has type ‘char’ [-Werror=char-subscripts] 
     ++count[str[i]]; 
     ^
cs.c:17:9: error: array subscript has type ‘char’ [-Werror=char-subscripts] 
     output[--count[str[i]]] = str[i]; 
     ^
cc1: all warnings being treated as errors 
$ 

Однако, что только начинает охватывать проблемы :

• memset() 0 0 четверть массива, оставив остальную часть мусора.

  memset(count, '\0', sizeof(count)); 
  

• Индексация по возможности подписанных символов означает, что вы могли бы быть доступом к элементам -128 ..- 1 из массива. Вот почему компилятор предупреждает о символьных индексах. Учитывая ваши данные, это не ваша проблема,

• Вторая петля for объединяет все виды мусора (из-за проблемы).

• Третий цикл пугает меня безмолвным; Я понятия не имею, что он пытается сделать, но гарантированно не будет делать то, что вы думаете из-за проблем с .

С отладки кода на месте, как показано и основные проблемы фиксирована, код выглядит следующим образом:

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

void countingsort(char *str); 

void countingsort(char *str) 
{ 
    int count[256]; 
    int i; 
    char output[20]; 
    memset(count, '\0', sizeof(count)); 
    for (i = 0; str[i]; i++) 
     ++count[(unsigned char)str[i]]; 
    for (i = 1; i < 256; i++) 
     count[i] += count[i-1]; 
    /* Debug */ 
    for (i = 0; i < 256; i++) 
    { 
     printf(" %3d: %2d", i, count[i]); 
     if (i % 8 == 7) 
      putchar('\n'); 
    } 

    for (i = 0; str[i]; i++) 
     output[--count[(unsigned char)str[i]]] = str[i]; 
    for (i = 0; str[i]; i++) 
     str[i] = output[i]; 
} 

int main(void) 
{ 
    char str[] = "123ab78bj45ui"; 
    printf("Before: <<%s>>\n", str); 
    countingsort(str); 
    printf("%s\n", str); 
    return 0; 
} 

И выход, по-видимому, находится под полным контролем, является:

Before: <<123ab78bj45ui>> 
    0: 0 1: 0 2: 0 3: 0 4: 0 5: 0 6: 0 7: 0 
    8: 0 9: 0 10: 0 11: 0 12: 0 13: 0 14: 0 15: 0 
    16: 0 17: 0 18: 0 19: 0 20: 0 21: 0 22: 0 23: 0 
    24: 0 25: 0 26: 0 27: 0 28: 0 29: 0 30: 0 31: 0 
    32: 0 33: 0 34: 0 35: 0 36: 0 37: 0 38: 0 39: 0 
    40: 0 41: 0 42: 0 43: 0 44: 0 45: 0 46: 0 47: 0 
    48: 0 49: 1 50: 2 51: 3 52: 4 53: 5 54: 5 55: 6 
    56: 7 57: 7 58: 7 59: 7 60: 7 61: 7 62: 7 63: 7 
    64: 7 65: 7 66: 7 67: 7 68: 7 69: 7 70: 7 71: 7 
    72: 7 73: 7 74: 7 75: 7 76: 7 77: 7 78: 7 79: 7 
    80: 7 81: 7 82: 7 83: 7 84: 7 85: 7 86: 7 87: 7 
    88: 7 89: 7 90: 7 91: 7 92: 7 93: 7 94: 7 95: 7 
    96: 7 97: 8 98: 10 99: 10 100: 10 101: 10 102: 10 103: 10 
104: 10 105: 11 106: 12 107: 12 108: 12 109: 12 110: 12 111: 12 
112: 12 113: 12 114: 12 115: 12 116: 12 117: 13 118: 13 119: 13 
120: 13 121: 13 122: 13 123: 13 124: 13 125: 13 126: 13 127: 13 
128: 13 129: 13 130: 13 131: 13 132: 13 133: 13 134: 13 135: 13 
136: 13 137: 13 138: 13 139: 13 140: 13 141: 13 142: 13 143: 13 
144: 13 145: 13 146: 13 147: 13 148: 13 149: 13 150: 13 151: 13 
152: 13 153: 13 154: 13 155: 13 156: 13 157: 13 158: 13 159: 13 
160: 13 161: 13 162: 13 163: 13 164: 13 165: 13 166: 13 167: 13 
168: 13 169: 13 170: 13 171: 13 172: 13 173: 13 174: 13 175: 13 
176: 13 177: 13 178: 13 179: 13 180: 13 181: 13 182: 13 183: 13 
184: 13 185: 13 186: 13 187: 13 188: 13 189: 13 190: 13 191: 13 
192: 13 193: 13 194: 13 195: 13 196: 13 197: 13 198: 13 199: 13 
200: 13 201: 13 202: 13 203: 13 204: 13 205: 13 206: 13 207: 13 
208: 13 209: 13 210: 13 211: 13 212: 13 213: 13 214: 13 215: 13 
216: 13 217: 13 218: 13 219: 13 220: 13 221: 13 222: 13 223: 13 
224: 13 225: 13 226: 13 227: 13 228: 13 229: 13 230: 13 231: 13 
232: 13 233: 13 234: 13 235: 13 236: 13 237: 13 238: 13 239: 13 
240: 13 241: 13 242: 13 243: 13 244: 13 245: 13 246: 13 247: 13 
248: 13 249: 13 250: 13 251: 13 252: 13 253: 13 254: 13 255: 13 
1234578abbiju 

Обратите внимание, как я добавил отладочную печать. Если бы вы сделали это с оригинальным кодом, вы могли видеть проблему с номерами:

Before: <<123ab78bj45ui>> 
    0: 0 1: 0 2: 0 3: 0 4: 0 5: 0 6: 0 7: 0 
    8: 0 9: 0 10: 0 11: 0 12: 0 13: 0 14: 0 15: 0 
    16: 0 17: 0 18: 0 19: 0 20: 0 21: 0 22: 0 23: 0 
    24: 0 25: 0 26: 0 27: 0 28: 0 29: 0 30: 0 31: 0 
    32: 0 33: 0 34: 0 35: 0 36: 0 37: 0 38: 0 39: 0 
    40: 0 41: 0 42: 0 43: 0 44: 0 45: 0 46: 0 47: 0 
    48: 0 49: 1 50: 2 51: 3 52: 4 53: 5 54: 5 55: 6 
    56: 7 57: 7 58: 7 59: 7 60: 7 61: 7 62: 7 63: 7 
    64: 8 65: 8 66: 176754732 67: 176754733 68: 1606423245 69: 1606456012 70: -843336874 71: -843304107 
    72: 586364677 73: 586364678 74: -1863248202 75: -1863215435 76: -17897627 77: -17864860 78: 1827489556 79: 1827522323 
    80: -622127165 81: -622094398 82: -622094397 83: -622094397 84: 1223223411 85: 1223256178 86: -1226364830 87: -1226332063 
    88: 203336529 89: 203369296 90: 2048543985 91: 2048576752 92: -401072736 93: -401039969 94: 1444306319 95: 1444339086 
    96: -1005310402 97: -1005277634 98: -1005277631 99: -1005277631 100: -828522907 101: -828522906 102: 601145878 103: 601178645 
104: 2030847317 105: 2030880085 106: -418887751 107: -418854984 108: 1010813800 109: 1010846567 110: 1010846567 111: 1010846567 
112: 1010846567 113: 1010846568 114: 1010846569 115: 1010846569 116: 1187601337 117: 1187601339 118: 1364356072 119: 1364356073 
120: 1541106681 121: 1541106682 122: -908514326 123: -908481559 124: 521187273 125: 521220040 126: -1508757392 127: -1508724625 
128: -658678769 129: -658678769 130: -658678747 131: -658678747 132: 770990005 133: 771022772 134: -1258953635 135: -1258920868 
136: -1258920868 137: -1258920868 138: 170748016 139: 170780783 140: 1600449663 141: 1600482430 142: 1600482430 143: 1600482430 
144: -1264815990 145: -1264783223 146: 655242917 147: 655275684 148: 659367534 149: 659367534 150: 659367534 151: 659367790 
152: -1715573370 153: -1715540603 154: -1699052283 155: -1699043995 156: 220982117 157: 221014884 158: 2141040460 159: 2141073227 
160: -233871253 161: -233838486 162: -233838486 163: -233838486 164: 1686187626 165: 1686220393 166: 1686220393 167: 1686220393 
168: -1179077991 169: -1179045224 170: 1085946763 171: 1085979530 172: 970946174 173: 215978496 174: 2136004072 175: 2136
176: 2136012616 177: 2136012872 178: -238928848 179: -238896081 180: -238896055 181: -238896055 182: -62145647 183: -62145646 
184: 1367523314 185: 1367556081 186: -580781114 187: -580748347 188: 1339277229 189: 1339309996 190: 1339309996 191: 1339309996 
192: 1516060404 193: 1516060405 194: -858852619 195: -858819852 196: 570849364 197: 570882131 198: -1377463709 199: -1377430942 
200: -1377430942 201: -1377430942 202: 52238290 203: 52271057 204: 1481940361 205: 1481973128 206: -1383324432 207: -1383291665 
208: -1383291665 209: -1383291665 210: 46373871 211: 46406638 212: 46406638 213: 46406638 214: 46406638 215: 46406638 
216: 871518564 217: 1663205276 218: -1651447554 219: 268721709 220: 268721709 221: 268721709 222: 268721709 223: 268721709 
224: 1936968284 225: -710723907 226: 81634598 227: 877664411 228: 877664411 229: 877664411 230: 877664411 231: 877664411 
232: -1649260597 233: 316768825 234: 2131817644 235: -344827877 236: -344827877 237: -344827877 238: -344827877 239: -344827877 
240: 1507572298 241: -850335356 242: 917706998 243: -1729997980 244: -1729997964 245: -1729997916 246: -300328684 247: -300295917 
248: 1129373059 249: 1129405826 250: 1925630953 251: -1389021877 252: -1504055233 253: 2035944385 254: 2035944385 255: 2035944385 
Segmentation fault: 11 

Answer 2

Данная программа работает нормально, когда длина входной строки является < = 20

Когда длина строки> 20, доступ к массиву происходит за пределами границ, что приводит к необработанному исключению.