【例25.8】使用状态机将字符数组buf字串中的多余空格去除并将结果存入数组test中,然后再输出test中的内容验证是否符合要求。
【解答】在第一篇第11章例11.5中,给出使用状态机去除多余的空格的程序。这里不是在去除空格过程中打印,而是存入字符数组。打印是输出到屏幕,只要不输出多余的空格即可。但输出到字符数组则需要保证它的下标在输入多余空格时,保持不变。
第1个空格是重要的,状态要发生改变。这里把input空格定义为1,其他应为0。
对state而言,关心的是空格,所以字符对应0。第1个空格为1,第2个空格就必须与之区分,定义为2。同理,第3个空格也应为2。对字符不关心,遇到字符(包括标点符号)回到0状态,只要不是状态2,就都打印出来。
用j表示下标,用1表示下标变化,0表示不变。
buf /" How are you? Fine! thank you.ninput 1100010001110000111000001100000100000state 01200010001220000122000001200000100000 p p pppppppp ppppp ppppppppppppppppp j 01111111111100111111001111111111111111111
根据对应关系,列出如下的状态跳转表。
0 0-->0 0 1-->1 1 0-->0 1 1-->2 2 0-->0 2 1-->2
对照上述状态,可以看出,在原来程序使用
printf(/"%c/",c);
输出的地方,换为语句
test[j]=c;
即可。而在state=2,input=1并维持state=2的情况下(即2 1-->2)做j--运算,以抵消本轮循环后的j++运算,维持j不变。
下面是在该例程序中修改后的程序和运行结果,为了容易理解,仅仅将原来的printf语句注释掉而不是删除。
#include <stdio.h>int get_input(char);int main(){ char buf = /"How are you? Fine! thank you./"; char test[64]; //存入去掉空格后的单词 int input = 0, i = 0, state = 0; char c; int j=0; //test数组下标计数器 while(1) { c=buf[i]; input=get_input(c); if(c==/'/0/') break; if((state==0)&&(input==0)) { state=0; // printf(/"%c/",c); test[j]=c; } else if((state==0)&&(input==1)) { state=1; // printf(/"%c/",c); test[j]=c; } else if((state==1)&&(input==0)) { state=0; // printf(/"%c/",c); test[j]=c; } else if((state==1)&&(input==1)) { state=2; //nothing } else if((state==2)&&(input==0)) { state=0; // printf(/"%c/",c); test[j]=c; } if((state==2)&&(input==1)) { state=2; //no out; j--; //数组不能继续计数,保持原来的下标 } i++; j++; } test[j]=/'/0/'; //将数组置结束符后输出 printf(/"%sn/",test); return 0;}int get_input(char c){ if ( c== /' /') return 1; return 0;}
程序运行结果如下:
How are you? Fine! thank you.
【25.9】使用函数指针去除多余空格。
分析一下状态表:
0 0-->0 0 1-->1 1 0-->0 1 1-->2 2 0-->0 2 1-->2
假设用状态表示一个数组的下标,则转移可以作为这个数组元素的值,假设用数组a表示为:a[0][0]=1,a[0][1]=1,a[1][0]=0,a[1][1]=2,a[2][0]=0,a[2][1]=2。
由此可以造一个状态迁移表state_transition,用来作为下一个状态的返回,即
state=state_transition[state][input];int state_transition[3][2]={ {0,1}, {0,2}, {0,2}};
老的state调用函数指针:
pf=act_table[state][input];pf();
再用老的state产生新的state,即
state=state_transition=[state][input]; //符合此规律
定义函数指针:
typedef void(*PF)(void);
再定义全局二维指针数组,存6个函数指针,与状态表一一对应,即对应迁移状态表所要执行的动作表。
PF act_table[3][2]={ {act_print, act_print}, {act_print, act_null}, {act_print, act_null}};
从状态表找出状态,从动作表找出动作,这就大大简化了程序设计。
完整的程序如下。
#include <stdio.h>int get_input(char);char c;void act_print(void){ printf(/"%c/",c); return;}void act_null(void){ return;}//状态迁移表,可以作为下一个状态的返回int state_transition[3][2]={ {0,1}, {0,2}, {0,2}};typedef void(*PF)(void);//全局二维指针数组,存6个函数指针,与状态表一一对应。//对应迁移状态表所要执行的动作表PF act_table[3][2]={ {act_print,act_print}, {act_print,act_null}, {act_print,act_null}};//主程序int main(){ char buf=/"How are you? Fine! thank you./"; int input=0,i=0,state=0; while(1) { void (*pf)(void); //声明函数指针 c=buf[i]; //如果使用文件,改写#if 1 //如果使用文件删除此项 input=get_input(c); if(c==/'/0/') break;#endif#if 0 //如果使用文件选此项 if(c==EOF) break;#endif //第1次是老的state,用它调用函数指针 pf = act_table[state][input]; pf ( ); //再用老的state产生新的state,供下一次循环使用 state=state_transition[state][input]; //符合此规律 i++; } printf(/"n/"); return 0;}int get_input(char c){ if ( c== /' /') return 1; return 0;}
程序运行结果如下:
How are you? Fine! thank you.