基于Ｃ語言的字符串處理算法研究

摘要：本文針對字符串中取出整型數(shù)據(jù)這一問題提出了更加直觀簡單的算法，并用數(shù)組法和指針法都將其實(shí)現(xiàn)。實(shí)踐證明，此算法正確且時(shí)間復(fù)雜度低，學(xué)生容易理解且能建立字符串處理的編程思想。

關(guān)鍵詞：字符串；算法；指針法；時(shí)間復(fù)雜度

中圖分類號：G642文獻(xiàn)標(biāo)識碼：B

字符串處理是程序設(shè)計(jì)中最常見的操作，掌握對字符串的處理也是學(xué)習(xí)一種語言的基礎(chǔ)，對解決實(shí)際問題是非常重要的。對C語言課程也不例外，字符串處理問題是C語言課程中的基礎(chǔ)知識，也是重點(diǎn)內(nèi)容。但歷年的教學(xué)中卻發(fā)現(xiàn)很多學(xué)生對字會(huì)串處理這方面的知識掌握的并不好，遇到對字符串處理問題時(shí)不知從何入手。究其原因主要有：(1)對字符串的特點(diǎn)不清楚；(2)對字符串的基本處理方法沒有掌握；(3)教材中的一些字符串處理算法比較復(fù)雜，不夠直觀，學(xué)生不易理解；(4)學(xué)生沒有建立字符串處理的編程思想。根據(jù)多年的教學(xué)經(jīng)驗(yàn)及對字符串處理的算法研究，下面針對一個(gè)具體的字符串處理問題進(jìn)行了分析，找到了一種既直觀又簡單算法。

1問題的提出[1]

參考文獻(xiàn)[1]中有這樣一個(gè)問題：有一個(gè)字符串，內(nèi)有數(shù)字和非數(shù)字字符(例如：a123x456 17960?234ext1234)將

其中的連續(xù)的數(shù)字作為一個(gè)整數(shù)，依次存放到數(shù)組a中(例如123存放在a[0]中，456存放在a[1]……統(tǒng)計(jì)其中有多少個(gè)整數(shù)，并輸出這些數(shù))。

對于上述問題參考文獻(xiàn)[2]給出了具體編寫的程序，采用的是指針法，但對于初學(xué)者來講理解起來非常困難，且程序語句比較長。經(jīng)過對問題的分析，我對此算法進(jìn)行了改進(jìn)，分別用數(shù)組法與指針法進(jìn)行了編寫，在給學(xué)生講解時(shí)，學(xué)生很容易理解，且算法直觀易懂，時(shí)間復(fù)雜度降低。

2改進(jìn)算法

2.1數(shù)組法

圖1為數(shù)組法算法的N-S結(jié)構(gòu)圖。

算法思想：處理字符串要一個(gè)一個(gè)字符處理，從字符串的第一個(gè)字符開始到字符串的最后一個(gè)字符，即遇到字符串結(jié)束標(biāo)志'\\0'結(jié)束循環(huán)，所以外循環(huán)為while(x[i]!='\\0')。當(dāng)字符為非數(shù)字字符時(shí)不用作任何處理，只是將循環(huán)變量的值加1讓處理的字符后移一個(gè)；當(dāng)字符為數(shù)字字符即x[i]＞='0'x[i]＜='9'時(shí)，說明一個(gè)整型數(shù)據(jù)開始，且將其存放到下標(biāo)為count的數(shù)組元素a[count]中，這個(gè)元素的初值設(shè)置為零，即a[count]=0。然后用公式x[i]-'0'將第一個(gè)數(shù)字字符變成一位整型數(shù)據(jù)，再利用公式a[count]=a[count]*

10+x[i]-'0';將其累加到數(shù)組元素a[count]中，如果后面還有連續(xù)的數(shù)字字符，則用同樣的辦法進(jìn)行轉(zhuǎn)換及累加，只到非數(shù)字字符時(shí)此整型數(shù)據(jù)計(jì)算結(jié)束。例如a123x456 17960?234ext1234的處理方法是：

第一步：取到第一個(gè)字符為’a’，因?yàn)樵撟址欠菙?shù)字字符，故對該字符不作任何處理，只是將循環(huán)變量i的值加1，開始下一次循環(huán)以獲取第下一個(gè)字符。

第二步：當(dāng)取到第二個(gè)字符’1’時(shí)，經(jīng)判斷此字符為數(shù)字字符，則說明一個(gè)整型數(shù)據(jù)開始，則將其存放在數(shù)組元素a[count]中， 此時(shí)count=0，a[count]實(shí)際上是a[0]。首先將其初始值清零即a[count]=0，然后利用公式a[count]=

a[count]*10+x[i]-'0'將當(dāng)前得到的數(shù)字字符存放于該數(shù)組元素中，即a[0]=a[0]*10+x[i]-'0'=0*10+'1'-'0'=1。將循環(huán)變量i的值加1，開始下一次循環(huán)以獲取下一個(gè)字符。

第三步：因?yàn)榭赡軙?huì)有多位連續(xù)的數(shù)字字符存在，所以要用do—while循環(huán)語句，若不符合x[i]＞='0'x[i]＜='9'，

則該整型數(shù)據(jù)結(jié)束。當(dāng)取到下一個(gè)字符’2’時(shí)，符合do—while循環(huán)語句的循環(huán)條件x[i]＞='0'x[i]＜='9'，說明要將此數(shù)字字符轉(zhuǎn)換為數(shù)值并累加a[count]中。利用的公式仍為a[count]=a[count]*10+x[i]-'0' ，即a[0]=a[0]*10+x[i]-

'0'=1*10+2=12。將循環(huán)變量i的值加1，開始下一次循環(huán)以獲取下一個(gè)字符。

第四步：當(dāng)取到下一個(gè)字符’3’時(shí)，符合do—while循環(huán)語句的循環(huán)條件x[i]＞='0'x[i]＜='9'，說明要將此數(shù)字字符轉(zhuǎn)換為數(shù)值并累加a[count]中。利用的公式仍為a[count]=a[count]*10+x[i]-'0' ，即a[0]=a[0]*10+x[i]-'0'=

12*10+3=123。將循環(huán)變量i的值加1，開始下一次循環(huán)以獲取下一個(gè)字符。

第五步：當(dāng)取到下一個(gè)字符然’x’時(shí)，不再符合do—while循環(huán)語句的循環(huán)條件x[i]＞='0'x[i]＜='9'，說明一個(gè)整型數(shù)據(jù)結(jié)束，即a[0]的值為123。然后將統(tǒng)計(jì)變量count的值加1即count++。

用同樣的方法將會(huì)使a[1]存放456，a[2]存放17960，a[3]存放234，a[4]存放1234。具體的程序如下：

#include＜stdio.h＞

#include＜string.h＞

int fun(char x[]，int a[])

{int i=0，count=0;

while(x[i]!='\\0')

{if(x[i]＞='0'x[i]＜='9')

{

a[count]=0;

do

{a[count]=a[count]*10+x[i]-'0';

i++;

} while(x[i]＞='0'x[i]＜='9');

count++;

}

else

i++;

}

return count;

}

void main()

{char x[80];

int a[80]，cnt，i;

gets(x);

cnt=fun(x，a);

printf (\"There are %d numbers in this line. They are :\\"， cnt);

for(i=0;i＜cnt;i++)

printf(\"a[%d]=%-10d \"，i，a[i]);

}

2.2指針法

圖2為指針法改進(jìn)算法的N-S結(jié)構(gòu)圖

算法思想：字符指針首先指向字符串的第一個(gè)字符，通過字符指針的移動(dòng)可指向字符串的每一個(gè)字符，即從字符串的第一個(gè)字符開始到字符串的最后一個(gè)字符，遇到字符串結(jié)束標(biāo)志'\\0'結(jié)束循環(huán)，所以外循環(huán)為while(*px!=’\\0’)。當(dāng)字符為非數(shù)字字符時(shí)不用作任何處理，只是將字符指針px后移一個(gè)，即px++；當(dāng)字符為數(shù)字字符即*px＞='0'

*px＜='9''時(shí)，說明一個(gè)整型數(shù)據(jù)開始，且將其存放到下標(biāo)為count且由pa+count所指向的數(shù)組元素*(pa+count)中，這個(gè)元素的初值設(shè)置為零，即*(pa+count)=0。然后用公式*px-'0'將第一個(gè)數(shù)字字符變成一位整型數(shù)據(jù)，再利用公式*(pa+count)=*(pa+count)*10+*px-'0';將其累加到pa+count所指的數(shù)組元素*(pa+count)中，如果后面還有連續(xù)的數(shù)字字符，則用同樣的辦法進(jìn)行轉(zhuǎn)換及累加，只到非數(shù)字字符時(shí)此整型數(shù)據(jù)計(jì)算結(jié)束。主要程序如下：

int fun(char *px，int *pa)

{ int count=0;

while(*px!='\\0')

{if(*px＞='0'*px＜='9')

{

*(pa+count)=0;

do

{*(pa+count)=*(pa+count)*10+*px-'0';

px++;

} while(*px＞='0'*px＜='9');

count++;

}

else

px++;

}

return count;

}

void main()

{char x[80]，*px=x;

int a[80]，*pa=a，cnt;

gets(px);

cnt=fun(px，pa);

printf (\"There are %d numbers in this line. They are :\\"， cnt);

for(;pa＜a+cnt;pa++)

printf(\"a[%d]=%-10d \"，pa-a，*pa);

}

3改進(jìn)算法的優(yōu)點(diǎn)

眾所周知，衡量一個(gè)算法的好壞主要從他的正確性、可讀性、健壯性、效率及低存儲(chǔ)量幾方面來考慮。正確是首要的，改進(jìn)后的算法首先經(jīng)上機(jī)調(diào)試驗(yàn)證其是正確的。其次就是任何一個(gè)算法主要是為了人的閱讀與交流，然后是機(jī)器執(zhí)行，可讀性好有助于人對算法的理解，且容易調(diào)試與修改。改進(jìn)后的算法直觀、容易理解，程序語句相對來講比較少。再者，算法的時(shí)間復(fù)雜度決定了算法的優(yōu)劣，新改進(jìn)算法的時(shí)間復(fù)雜度由原來O(n2)降為O(n)。

采用了這種算法進(jìn)行教學(xué)之后，學(xué)生們對于字符串處理方法的理解大大加強(qiáng)了，從中掌握了字符串處理的基本編程思想，學(xué)會(huì)了用數(shù)組法及指針法來處理字符串，通過數(shù)組法與指針法的對比講解，能更好的理解用指針法對字符串進(jìn)行處理的方法，收到了很好的教學(xué)效果。

參考文獻(xiàn)：

[1] 譚浩強(qiáng). C程序設(shè)計(jì)(第三版)[M]. 北京:清華大學(xué)出版社，2005.

[2] 譚浩強(qiáng). C程序設(shè)計(jì)題解與上機(jī)指導(dǎo)(第三版)[M]. 北京:清華大學(xué)出版社，2005.

[3] 嚴(yán)蔚敏. 數(shù)據(jù)結(jié)構(gòu)[M]. 北京:清華大學(xué)出版社，1997.