-2 
#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;
}

我不知道问题出在哪里。我认为我做得对，但在运行时它给出了这个错误“countingsort.exe 中 0x013814f5 处的未处理异常：0xC0000005：访问冲突写入位置 0x33562813。”。谁能建议我哪里出错了。

4

2 回答 2

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()四分之一为零，其余部分包含垃圾。

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

  • 可能有符号字符的索引意味着您可以访问数组的元素 -128..-1。这就是编译器警告字符下标的原因。鉴于您的数据，这不是您的问题，

  • 第二个for循环是添加各种垃圾（因为memset()问题）。

  • 第三个循环把我吓傻了；我不知道它想做什么，但保证不会因为memset()问题而按照你的想法去做。

如图所示，在原位调试代码并修复了主要问题后，代码如下所示：

#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: 2136012360
 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
于 2013-11-16T19:04:36.623 回答
0

当输入字符串的长度 <= 20 时，给定程序运行良好

当字符串长度大于 20 时，数组访问发生在边界之外，导致未处理的异常。

于 2013-11-16T17:40:59.727 回答