c***2 发帖数: 838 | 1 Here's another old question: | c***2 发帖数: 838 | 2 Okay. Converted it from "exposed": | j***y 发帖数: 2074 | | j***y 发帖数: 2074 | 4 老大,程序看不太懂,能否加点注释啊?
比如当i为0的时候,result[0]=0吧?因为digitsmaps[0]==""。这时候递归调用
doPrintTelephoneWords(phoneNum, 1, result)是要达成一个什么目的呢?
真是看不明白啊。 | j***y 发帖数: 2074 | 5 又看了一会儿,似乎有些明白,的确是巧妙的递推。但有些疑问:
1. char result[PHONE_NUMBER_LENGTH];应改为char result[PHONE_NUMBER_LENGTH+1]?
2. void printTelephoneWords( int phoneNum[] ){
char result[PHONE_NUMBER_LENGTH];
doPrintTelephoneWords( phoneNum, 0, result );
}似乎应该改为:
void printTelephoneWords( int phoneNum[] ){
char result[PHONE_NUMBER_LENGTH+1]; /* +1 for the string-ending 0x0
character */
for (int i = 0; i < 3; i++) {
doPrintTelephoneWords( phoneNum, 0, result );
}
}
否则出来的似乎只是da、db、dc而已。
我不太懂算法和数据结构,不对之处敬请指教。 | c***2 发帖数: 838 | 6 1) from facebook
2) result[..+1] you can do that, but not necessary since C does index from 0
, the last idx is alwasy reseved for 0.
char try[2];
Either of these are fine:
try[0]='a';
try[1]='b';
try[2]='\0';
or strcpy(try,"ab");
3) curDigit is better named currentidx (from phoneNum[]) | c***2 发帖数: 838 | 7 Ok. I play it further to get a utility program.
==================================================
/* telwords.c
Given a telephone number (or any number),
print all possible words based on
digits-letters mapping from telephone key pads.
*/
#include
#include
#include
static char *digitsmaps[]={
"0",
"1",
"ABC",
"DEF",
"GHI",
"JKL",
"MNO",
"PQRS",
"TUV",
"WXYZ",
"#",
NULL
};
void doPrintTelephoneWords( char *phoneNum, int len, int curIdx, char *
result)
{
int i;
int mapidx=phoneNum[curIdx]-'0';
if((mapidx>9)||(mapidx<0))
mapidx=10;
if( curIdx == len){
result[len]='\0';
printf("%s\n", result );
return;
}
for( i = 0; i
result[curIdx] = digitsmaps[mapidx][i];
doPrintTelephoneWords( phoneNum, len, curIdx + 1, result);
}
}
void printTelephoneWords( char *phoneNum )
{
char *result;
int len=strlen(phoneNum);
if(!phoneNum)
return;
result=(char*)malloc(len);
if(!result)
return;
doPrintTelephoneWords(phoneNum, len, 0, result);
free(result);
}
int main (int argc, char *argv[])
{
int i;
for(i=1;i
printf("Mappings of [%s]:\n",argv[i]);
printTelephoneWords(argv[i]);
printf("-------------\n");
}
return 0;
}
==================================================
A sample run:
telwords.exe 23 780
Mappings of [23]:
AD
AE
AF
BD
BE
BF
CD
CE
CF | j***y 发帖数: 2074 | 8 又琢磨了半天,你是对的。确实不需要再加一个循环,我搞错了。
就以你原来的程序为例:
doPr(p, 0, res) ->
currDigIdx=0, i=0, res[0]='d', doPr(p, 1, res) ->
currDigIdx=1, i=0, res[1]='a', doPr(p, 2, res) ->
print("da"), return ->
/* recursion-cycle finished for doPr(p, 2, res), but not finished yet for
doPr(p, 1, res) */
currDigIdx=1, i=1, res[1]='b', doPr(p, 2, res) ->
print("db"), return ->
currDigIdx=1, i=2, res[1]='c', doPr(p, 2, res) ->
print("dc"), return ->
/* now doPr(p, 1, res) is finished, return to the for-loop in doPr(p, 0,,
res) */
currDigIdx=0, i=1, res[0]='e', do(p, 1, res) ->
...
这个程序中,递归的流程保证了多重嵌套循环的依次展开,实在是很漂亮的设计。
不过,老大的程序似乎还是有些小问题的,还是拿原来的程序为例:
---
#define PHONE_NUMBER_LENGTH 2
...
if( curDigit == PHONE_NUMBER_LENGTH ){
result[2]='\0';
printf("%s\n", result );
return;
}
...
void printTelephoneWords( int phoneNum[] ){
char result[PHONE_NUMBER_LENGTH];
doPrintTelephoneWords( phoneNum, 0, result );
}
---
char result[2]定义了有效的内存访问空间是result[0]和result[1],result[2]='\0'
实质上已经是越界方位了,很危险,没有core dump只能说是幸运。
所以,我觉得应该改成char result[PHONE_NUMBER_LENGTH + 1]; |
|