使用具有字母和数字的输入字符串计数排序[关闭]
https://stackoverflow.com//questions/20021058
-
21-12-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russian题
#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中的0x013814f5处给出了这个错误"未处理的异常。exe文件:0xC0000005:访问冲突写入位置0x33562813。".任何人都可以建议我错在哪里。
解决方案
即使代码在演示文稿中被清理:
#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;
}
GCC4.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
其他提示
当输入字符串的长度为 <= 20
当字符串长度>20时，数组访问发生在边界之外，导致未处理的异常。
不隶属于 StackOverflow
