王世林，錢 敏，2

（1.蘇州大學(xué)文正學(xué)院，江蘇 蘇州 215104；2.蘇州大學(xué)電子信息學(xué)院，江蘇 蘇州 215006）

數(shù)據(jù)結(jié)構(gòu)對(duì)程序設(shè)計(jì)算法優(yōu)化、操作系統(tǒng)設(shè)計(jì)、編譯系統(tǒng)設(shè)計(jì)等都有重要意義，其中，鏈表存儲(chǔ)結(jié)構(gòu)在操作系統(tǒng)中有重要運(yùn)用[1-2]。在計(jì)算機(jī)系統(tǒng)中，表示不同類型的數(shù)時(shí)，由于計(jì)算單元存儲(chǔ)位數(shù)的限制，表示精確數(shù)據(jù)的范圍是一定的[3]，比如16位的無(wú)符號(hào)整數(shù)的表示范圍是[0—216－1]，超過這個(gè)范圍，只能采用浮點(diǎn)數(shù)。當(dāng)然，浮點(diǎn)數(shù)是非精確值。假如在一定的場(chǎng)合，需要得到精確值時(shí)，必須采用一定的算法來實(shí)現(xiàn)。

高精度大整數(shù)運(yùn)算在計(jì)算機(jī)數(shù)據(jù)加密技術(shù)中有重要應(yīng)用，限于一般程序設(shè)計(jì)語(yǔ)言編譯系統(tǒng)并不提供直接的運(yùn)算支持，所以人們提出了各種運(yùn)算方法。有關(guān)大整數(shù)階乘精確值的計(jì)算方法已有若干文獻(xiàn)報(bào)道[4-5]，其算法一般采用數(shù)組技術(shù)，其編程思想是：用數(shù)組存放階乘項(xiàng)每一項(xiàng)相乘后的中間結(jié)果和最終結(jié)果，每一單元存放一個(gè)若干位數(shù)；采用循環(huán)，階乘項(xiàng)每一項(xiàng)對(duì)數(shù)組元素進(jìn)行相乘，同時(shí)進(jìn)行進(jìn)位處理，直到所有項(xiàng)均乘完為止。文獻(xiàn)[5]采用了動(dòng)態(tài)數(shù)組和一些優(yōu)化技術(shù)，有效地提高了該算法的運(yùn)算速度，但需要一些數(shù)學(xué)技巧。本文提供了一種利用動(dòng)態(tài)分配內(nèi)存的鏈表技術(shù)，其算法不同于其他方法：用鏈表的結(jié)點(diǎn)存放每一項(xiàng)相乘后的中間結(jié)果和最后結(jié)果，每個(gè)結(jié)點(diǎn)存放一個(gè)若干位數(shù)；循環(huán)相乘時(shí)同時(shí)處理進(jìn)位，末尾結(jié)點(diǎn)相乘時(shí)若有進(jìn)位，則動(dòng)態(tài)分配內(nèi)存空間開辟新的結(jié)點(diǎn)。結(jié)點(diǎn)中數(shù)值的存儲(chǔ)順序是從階乘值的低位到高位；采用雙向鏈表，可將該鏈整串輸出（即最終階乘結(jié)果）。

1 編程思想

圖1所示為該雙向鏈表算法的內(nèi)存分配示意圖。為了便于說明問題，這里每個(gè)結(jié)點(diǎn)只存儲(chǔ)一位十進(jìn)制數(shù)。

含有數(shù)字（即結(jié)點(diǎn)中的double dec）和*prev、*next兩個(gè)指針變量的實(shí)線框表示鏈表的一個(gè)結(jié)點(diǎn)。數(shù)字框中（如圖1所示為0405，實(shí)際上是7!=5040的逆序存放；每個(gè)結(jié)點(diǎn)中存放一位十進(jìn)制數(shù)，本文所附程序中每個(gè)結(jié)點(diǎn)中存放一個(gè)15位十進(jìn)制數(shù)）存放的是階乘每一項(xiàng)后的中間結(jié)果和最終結(jié)果。虛線框?yàn)閯?dòng)態(tài)指針指向各結(jié)點(diǎn)，包括head1、head2、pl、p2；p1、p2聯(lián)合操作用來開辟、勾連、遍歷各鏈表結(jié)點(diǎn)，headl為鏈表起點(diǎn)，head2為鏈表終點(diǎn)；Null為0.輸出時(shí)，反向遍歷鏈表，head2為頭結(jié)點(diǎn)，head1為尾結(jié)點(diǎn)。

圖1 雙向鏈表示意圖

求解n!時(shí)，每階乘一項(xiàng)，讓pl、p2指針遍歷（n-1）!所建立的鏈表，階乘項(xiàng)與每一鏈表開始結(jié)點(diǎn)中的中間結(jié)果相乘，得到部分積，以一定的權(quán)值為基，處理部分積得到余數(shù)和進(jìn)位，余數(shù)取代原先的中間結(jié)果作為新的中間結(jié)果，同時(shí)p1指針指向下一結(jié)點(diǎn)，繼續(xù)進(jìn)行相乘并與前一結(jié)點(diǎn)相乘時(shí)所得的進(jìn)位相加，再得到部分積，繼續(xù)處理余數(shù)和進(jìn)位。處理到最后的結(jié)點(diǎn)時(shí)，如有進(jìn)位，則開辟新的若干個(gè)結(jié)點(diǎn)并作勾連。如此往復(fù)，將所有的項(xiàng)都階乘完，記下head2。輸出時(shí)，只要得到head2即可將鏈表整串輸出。

2 實(shí)現(xiàn)技術(shù)

動(dòng)態(tài)分配內(nèi)存使用函數(shù)malloc（LEN）。本文所列程序中，為了節(jié)省內(nèi)存，權(quán)值采用1×1015。結(jié)點(diǎn)中存放的數(shù)采用八字節(jié)的雙精度型（double），其精度可達(dá)15位有效數(shù)字；用十字節(jié)的長(zhǎng)雙精度型數(shù)（long double）保存部分積，其精度可達(dá)19位有效數(shù)字，可表示的最大精度整數(shù)的精確值為264-1=18 446 744 073 709 551 615，約為18 446×1015，所以理論上能精確計(jì)算的最大階乘數(shù)是18446!。為求得更大數(shù)的階乘，可采用較小字節(jié)的結(jié)點(diǎn)數(shù)值類型和較小的權(quán)值，當(dāng)然以上兩者還受內(nèi)存分配的限制。

以上算法中還可以進(jìn)行一些優(yōu)化。一方面，因?yàn)閚!中尾部（從鏈表頭開始）存在較多的0，p1、p2在遍歷鏈表時(shí)只需從第一個(gè)非零結(jié)點(diǎn)處開始；另一方面，把階乘項(xiàng)若干項(xiàng)的積（＜=18 446）作為一項(xiàng)，減少階乘項(xiàng)與結(jié)點(diǎn)中中間數(shù)值的相乘次數(shù)。

3 源程序清單

4 測(cè)試結(jié)果及討論

本程序在Dell VOSTRO1200筆記本電腦上運(yùn)行，WIN7命令行DOS狀態(tài)下，VC6.0環(huán)境small模式下調(diào)試編譯通過。本程序可以很方便地知道可分配的內(nèi)存是否用完，共分配了多少個(gè)結(jié)點(diǎn)（計(jì)數(shù)器m）。由于內(nèi)存分配機(jī)制所限，可以計(jì)算最大階乘為15 566!。由于本程序是真正意義上的動(dòng)態(tài)分配內(nèi)存，所以比較耗時(shí)，運(yùn)算速度差于文獻(xiàn)[5]，但它不需要事先知道要開辟的內(nèi)存大小或數(shù)組大小，仍不失為一種構(gòu)思巧妙的算法。由于權(quán)值較大，結(jié)點(diǎn)數(shù)值采用八字節(jié)double型，優(yōu)化技術(shù)效果并不明顯，權(quán)值小些，效果較為明顯。若結(jié)點(diǎn)數(shù)值采用十字節(jié)long double型，能計(jì)算的最大階乘數(shù)則為14 005!。輸出鏈表時(shí)，為美觀起見，如果想每15位一組分組輸出，可在格式FORMAT中f后面加一個(gè)空格。

如果想保存輸出結(jié)果，可使用fopen()和fprintf()函數(shù)將結(jié)果存入文件中。以下給出30！的計(jì)算結(jié)果：n！=30!=265252859812191040636308480000000.

5 結(jié)束語(yǔ)

本文對(duì)計(jì)算機(jī)數(shù)據(jù)存儲(chǔ)結(jié)構(gòu)進(jìn)行了比較細(xì)致的研究，采用雙向鏈表數(shù)據(jù)結(jié)構(gòu)來實(shí)現(xiàn)大整數(shù)階乘的精確值的算法，對(duì)于加深鏈表在實(shí)際程序設(shè)計(jì)中的應(yīng)用的理解是一個(gè)很好的例程。其特點(diǎn)是動(dòng)態(tài)開辟內(nèi)存，不需要事先開辟預(yù)設(shè)空間，當(dāng)然，是以犧牲空間復(fù)雜度來實(shí)現(xiàn)的。至于運(yùn)算效率優(yōu)化的問題，并不在本例探討范疇之內(nèi)，是我們下一步研究的內(nèi)容。