【摘 要】基于等距抽樣法，討論了運(yùn)用雙向鏈表實(shí)現(xiàn)求和運(yùn)算問(wèn)題，給出了算法思想、程序流程。通過(guò)運(yùn)用Turbo c語(yǔ)言編程實(shí)現(xiàn)并對(duì)相關(guān)數(shù)據(jù)進(jìn)行測(cè)試，驗(yàn)證了算法的正確性和有效性。

【關(guān)鍵詞】等距抽樣 大數(shù)求和 雙向鏈表 算法

在教育技術(shù)研究中運(yùn)用調(diào)查研究時(shí)，當(dāng)研究對(duì)象是一個(gè)范圍極為廣大的總體時(shí)，要直接研究總體的情況根本無(wú)法實(shí)現(xiàn)，故人們常使用系統(tǒng)抽樣（等距抽樣）法，從一個(gè)大的總體中抽取部分單位作為研究的樣本，再?gòu)臉颖镜那闆r來(lái)推斷總體的情況，并且能夠極大地降低調(diào)查的費(fèi)用。等距抽樣法，是把總體中所有個(gè)體按一定順序編號(hào)，然后依固定間隔取樣，間隔的大小視所需樣本容量與總體中個(gè)體數(shù)目的比率而定，起始數(shù)字必須是隨機(jī)決定的。等距抽樣的步驟如下：

⑴設(shè)總體共有N個(gè)單位，現(xiàn)需要從中抽出n個(gè)單位作為樣本。先將總體的N個(gè)單位按與總體特征標(biāo)志無(wú)關(guān)的標(biāo)志進(jìn)行排隊(duì)。

⑵確定取樣間隔，將N 劃分為n個(gè)單位相等的部分，每部分間隔為：K = N/n；

⑶決定起點(diǎn)。通常是在第一部分順序?yàn)?，2，3，…，i，…，K個(gè)單位中隨機(jī)取一個(gè)單位i作為抽樣的起點(diǎn)。

⑷在第一部分中，隨機(jī)以i為起點(diǎn)抽出第一個(gè)樣本后，繼續(xù)在第二部分中抽出第i+k單位為樣本；如此類(lèi)推，在第n部分則抽出第i+（n-1）K單位為樣本。

這樣一共抽出了n個(gè)單位組成樣本，而且每個(gè)樣本的間隔都是K。

但是，當(dāng)總體很大時(shí)，樣本號(hào)單位會(huì)逐漸增大到很大，那么在用Turbo c 語(yǔ)言編寫(xiě)程序過(guò)程中可能會(huì)遇到?jīng)]有適當(dāng)?shù)臄?shù)據(jù)類(lèi)型變量能夠存儲(chǔ)這樣的大數(shù)，這使等距抽樣法的應(yīng)用受到極大的限制。為此，筆者編寫(xiě)了一個(gè)前n項(xiàng)大數(shù)求和的算法，可以根本上解決此類(lèi)求和的算法問(wèn)題。

一、算法分析及設(shè)計(jì)

用Turbo c語(yǔ)言進(jìn)行運(yùn)算時(shí)，c語(yǔ)言中沒(méi)有適當(dāng)?shù)臄?shù)據(jù)類(lèi)型變量能夠存儲(chǔ)足夠大的值，同樣前n項(xiàng)和Sum的值也無(wú)法利用已有的數(shù)據(jù)類(lèi)型通過(guò)定義變量來(lái)存儲(chǔ)這樣大的值。開(kāi)辟動(dòng)態(tài)存儲(chǔ)單元雖可以用數(shù)組，但是用數(shù)組往往要求開(kāi)辟存儲(chǔ)單元之前就必須確定要開(kāi)辟存儲(chǔ)單元的字節(jié)數(shù)，若n值是不確定時(shí)，從而Sum值也是不確定的，可見(jiàn)用開(kāi)辟動(dòng)態(tài)數(shù)組的方法并不能徹底解決這一求解問(wèn)題，因此筆者嘗試采用雙向鏈表來(lái)建立動(dòng)態(tài)存儲(chǔ)單元接受輸入n值及前n項(xiàng)和Sum值的數(shù)據(jù)。

（一）數(shù)據(jù)接受

采用雙向鏈表建立存儲(chǔ)單元來(lái)接受用戶(hù)從鍵盤(pán)輸入的n值。

1.建立的雙向鏈表[1]，指針n_head指向其頭結(jié)點(diǎn)，如圖1所示：（例如輸入n值為512，其他值有類(lèi)似圖1樣式，其中每一格代表一個(gè)字節(jié) ）

圖1 存放鍵盤(pán)輸入n值及標(biāo)志的雙向鏈表

說(shuō)明：將n值從高位到低位分別存放在鏈表各個(gè)結(jié)點(diǎn)的數(shù)據(jù)域中，并將n值最低位的標(biāo)志域置1（為下一步讓鏈表里的數(shù)據(jù)自減做準(zhǔn)備），其他位的標(biāo)志域置0。

2.程序流程圖（函數(shù)名為build（無(wú)參數(shù)），函數(shù)返回值為頭結(jié)點(diǎn)的地址）如圖2所示：

圖2 存放鍵盤(pán)輸入n值的算法流程圖

（二）新建雙向鏈表存放累加前n項(xiàng)和i的值，即。

1.（1）首先存放第n項(xiàng)的值（此時(shí)新鏈表里的初始值為512）。即拷貝n_head指針指向的鏈表的數(shù)據(jù)域，并使s_head指針指向這個(gè)新建的雙向鏈表，注意并不拷貝n_head指向鏈表的標(biāo)志域，而是使新建鏈表的標(biāo)志域值均為零。指針s指向鏈表尾結(jié)點(diǎn)。

圖3 向新建雙向鏈表累加第n項(xiàng)的值

（2）流程圖[2]（函數(shù)名為copy （參數(shù)為結(jié)構(gòu)體指針head） ，該函數(shù)返回其頭結(jié)點(diǎn)地址）如圖4所示：

圖4 向新建雙向鏈表累加第n項(xiàng)的值算法流程圖

2.（1）將存放n值鏈表里的值自減1（即n_head指向鏈表里的值變?yōu)?11）。q指針指向鏈表的最后一個(gè)結(jié)點(diǎn)。

圖5 存放n值鏈表里的值自減

（2）流程圖如圖6所示（函數(shù)名為dec_n（參數(shù)為指針q ））：

圖6 存放n值鏈表里的值自減

3. （1）將s_head鏈表里的值和n_head鏈表里的值按位相加（由低位到高位），若有進(jìn)位則存放到s_head鏈表的標(biāo)志域里。

圖7 第n-1按位相加到存放Sum的鏈表中

在按位相加時(shí)可分為兩大部分：

第一部分：只進(jìn)行除了最高位以外的其他位的按位相加。流程圖（屬主函數(shù)部分）如圖8所示：

圖8 除高位外各位的按位相加

第二部分：指針q和指針s移到高位時(shí)，進(jìn)行相加時(shí)有兩種情況。

一種情況是s指針指向結(jié)點(diǎn)沒(méi)有前驅(qū)結(jié)點(diǎn)。在這種情況下，如果有進(jìn)位，需要重新開(kāi)辟存儲(chǔ)單元（新結(jié)點(diǎn)）來(lái)存放進(jìn)位值，并使該新結(jié)點(diǎn)成為存放累加和Sum鏈表的頭結(jié)點(diǎn)連接到鏈表中。以n值減到511而Sum值為512進(jìn)行按位相加為例來(lái)說(shuō)明。

圖9 高位處無(wú)前驅(qū)結(jié)點(diǎn)的按位相加

另一種情況是s指針指向結(jié)點(diǎn)有前驅(qū)結(jié)點(diǎn)。在這種情況下，如果有進(jìn)位，需要判斷其前驅(qū)結(jié)點(diǎn)加1是否有進(jìn)位，若無(wú)則將進(jìn)位累加到前驅(qū)結(jié)點(diǎn)數(shù)據(jù)域中，若有進(jìn)位，則還應(yīng)繼續(xù)開(kāi)辟新結(jié)點(diǎn)存放進(jìn)位，依次進(jìn)行，直到?jīng)]有進(jìn)位為止。

先以n值減到509從而Sum值累加到1533為例來(lái)說(shuō)明前驅(qū)結(jié)點(diǎn)加1無(wú)進(jìn)位的處理。

圖10 高位處有前驅(qū)結(jié)點(diǎn)無(wú)進(jìn)位的按位相加

再以n值減到493從而Sum值累加到9557為例來(lái)說(shuō)明前驅(qū)結(jié)點(diǎn)加1有進(jìn)位的處理。

圖11 高位處有前驅(qū)結(jié)點(diǎn)有進(jìn)位的按位相加

開(kāi)辟新結(jié)點(diǎn)并連接到鏈表中的流程圖如下（函數(shù)名為start（指針s為參數(shù)））：

圖12 開(kāi)辟新結(jié)點(diǎn)為存放高位的進(jìn)位算法流程

向結(jié)點(diǎn)中累加進(jìn)位的流程圖如下（函數(shù)名為kpjw（r參數(shù)），函數(shù)返回值為r結(jié)點(diǎn)的地址）：

圖13 高位處的按位相加算法流程圖

第二部分算法總的流程圖（屬于主函數(shù)部分，其中調(diào)用以上圖12和圖13的函數(shù)）如下：

圖14 高位處進(jìn)行相加

（三）結(jié)果輸出

用指針指向存放Sum值的鏈表的頭結(jié)點(diǎn)從而將每個(gè)結(jié)點(diǎn)里的值即Sum值的每一位由高位到低位全部輸出。

二、結(jié)束語(yǔ)

依據(jù)上述累加和算法，用Turbo C語(yǔ)言編寫(xiě)程序，并選取大量數(shù)據(jù)對(duì)程序進(jìn)行了測(cè)試和驗(yàn)證，結(jié)果表明，程序輸出結(jié)果正確。在算法設(shè)計(jì)中是將求和大數(shù)當(dāng)作字符串進(jìn)行處理，亦即將大數(shù)用十進(jìn)制字符鏈表加以表示， 然后模擬人們手工進(jìn)行“豎式計(jì)算”的過(guò)程編寫(xiě)其加減函數(shù)。應(yīng)該看到，這一算法效率不是很高， 因?yàn)?024位的大數(shù)其十進(jìn)制數(shù)字個(gè)數(shù)就有數(shù)百個(gè)，對(duì)于任何一種運(yùn)算，都需要在兩個(gè)有數(shù)百個(gè)元素的鏈表空間上做多重循環(huán)，另還需要許多額外的空間存放計(jì)算的進(jìn)位退位標(biāo)志。當(dāng)然其優(yōu)點(diǎn)是算法符合人們熟知的算術(shù)求和規(guī)則，易于表述理解，能從根本上解決大數(shù)求和問(wèn)題。可以推定，在不同的機(jī)型和語(yǔ)言環(huán)境中，這個(gè)算法的程序編寫(xiě)語(yǔ)句會(huì)有所不同，但算法思想是通用的或可借鑒的。不難推定，求和算法可以推廣到類(lèi)似的求和問(wèn)題中，例如，…等等。只要逐次累加值的變化規(guī)律明晰可循，就不難編寫(xiě)出其相應(yīng)的求和程序來(lái)。

參考文獻(xiàn)：

[1] 嚴(yán)蔚敏. 數(shù)據(jù)結(jié)構(gòu)（C語(yǔ)言版） [M]. 北京：清華大學(xué)出版社，2003.

[2] 譚浩強(qiáng). C程序設(shè)計(jì)（第二版） [M]. 北京：清華大學(xué)出版社，1999.

[3]田振清，葉曉玲. 匯編語(yǔ)言中求解任意十進(jìn)制整數(shù)除法的一個(gè)算法[J]. 內(nèi)蒙古師范大學(xué)學(xué)報(bào)：自然科學(xué)漢文版，2006年12月第35卷第4期.

作者簡(jiǎn)介：

殷文輝（1981—），女，滿(mǎn)，講師，內(nèi)蒙古科左后旗人。