大整數階乘精確值的動態儲存雙向鏈表算法研究＊

王世林，錢 敏，2

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

數據結構對程序設計算法優化、操作系統設計、編譯系統設計等都有重要意義，其中，鏈表存儲結構在操作系統中有重要運用[1-2]。在計算機系統中，表示不同類型的數時，由于計算單元存儲位數的限制，表示精確數據的范圍是一定的[3]，比如16位的無符號整數的表示范圍是[0—216－1]，超過這個范圍，只能采用浮點數。當然，浮點數是非精確值。假如在一定的場合，需要得到精確值時，必須采用一定的算法來實現。

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

1 編程思想

圖1所示為該雙向鏈表算法的內存分配示意圖。為了便于說明問題，這里每個結點只存儲一位十進制數。

含有數字（即結點中的double dec）和*prev、*next兩個指針變量的實線框表示鏈表的一個結點。數字框中（如圖1所示為0405，實際上是7!=5040的逆序存放；每個結點中存放一位十進制數，本文所附程序中每個結點中存放一個15位十進制數）存放的是階乘每一項后的中間結果和最終結果。虛線框為動態指針指向各結點，包括head1、head2、pl、p2；p1、p2聯合操作用來開辟、勾連、遍歷各鏈表結點，headl為鏈表起點，head2為鏈表終點；Null為0.輸出時，反向遍歷鏈表，head2為頭結點，head1為尾結點。

圖1 雙向鏈表示意圖

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

2 實現技術

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

以上算法中還可以進行一些優化。一方面，因為n!中尾部（從鏈表頭開始）存在較多的0，p1、p2在遍歷鏈表時只需從第一個非零結點處開始；另一方面，把階乘項若干項的積（＜=18 446）作為一項，減少階乘項與結點中中間數值的相乘次數。

3 源程序清單

4 測試結果及討論

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

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

5 結束語

本文對計算機數據存儲結構進行了比較細致的研究，采用雙向鏈表數據結構來實現大整數階乘的精確值的算法，對于加深鏈表在實際程序設計中的應用的理解是一個很好的例程。其特點是動態開辟內存，不需要事先開辟預設空間，當然，是以犧牲空間復雜度來實現的。至于運算效率優化的問題，并不在本例探討范疇之內，是我們下一步研究的內容。