引入巨大數的原因:
因爲在C語言中,例如int型別,因爲int型常數的本質是4位元組(32位元)二補數,當數值最大爲2^31 - 1,即只能表示-2147483648 ~ 2147483647,而對於更大的數例如幾十位幾百位的數,則無法用系統原有型別儲存了,此時就需要引入巨大數概念。
巨大數的儲存思考:
對於巨大數的儲存,很容易能想到用字串儲存,將每個字元換成數位進行計算,但這種方法一位一位運算過於繁瑣,效率太低。
這時可以引入萬進位制的概念。
萬進位制:
萬進位制即類似十進制,上限爲9,萬進位制上限爲9999,9999再加一則進位,理想在C語言中儲存應該表示爲1,0。
實際這種想法可以擴充套件到各種進位制,但因爲乘法進位位數特別多,當採用十萬進位制時,五位×五位數據可能超過21億,超過了int能儲存的最大數,所以用十萬進位制就不能進行計算了。
在保證計算便利和數據合理的前提下,萬進位制是最適合的。
巨大數儲存:
通過思考後,因爲巨大數是通過字串取4位元轉成數位儲存的,所以巨大數數據應該用一個int陣列存放,額外還有符號,爲了計算方便還需要記錄有效位數。
typedef struct HUGE{
boolean sign;
int *data;
int size;
}HUGE;
分別儲存正負,數據,數據有效位數
巨大數的初始化:
明確了用結構體儲存後,就該進行巨大數的獲取(巨大數初始化)的思考了。
這次巨大數的獲取是從檔案獲取的,所以包含一系列檔案操作。
首先因爲數據用陣列的形式儲存,陣列以動態申請,申請時的位數需要提前知道。
對於檔案數據位數獲取,在之前的檔案操作中有寫到,就一筆帶過就行。
boolean getsize(FILE *fp, int *size) {
fseek(fp, 0, SEEK_END);
(*size) = ftell(fp);
fseek(fp, 0, SEEK_SET);
}
得到size後,因爲可能有一位是符號,則需要對第一個字元判斷,若爲符號,size需減一併且給sign賦值
if ('-' == ch) {
sign = 1;
size--;
} else {
sign = 0;
}
在獲取到size後,陣列中一個元素用於存4位元巨大數,那麼陣列總元素個數是否是size / 4呢?
若巨大數爲4的整數倍位,直接除4即可,但當位數不足4(%4結果不足4),直接除4會造成陣列儲存空間不足。
獲取元素總數計算方法:count = (size + 3) / 4
至此,巨大數結構體的初始化所需要的基礎數據就獲取完成了,接下來是巨大數數據的獲取。
對於巨大數數據的獲取,因爲數據在檔案中是從高位存到低位,數據位數不一定是4的整數倍,這會造成數據最高位可能不足4位元,所以對於最初的一組元素需要特別獲取。
head = size % 4;
for (i = 0; i < head; i++) {
if (1 == sign) {
tmp[i] = fgetc(fp);
} else {
tmp[i] = ch;
ch = fgetc(fp);
}
}
if (0 != head){
huge->data[figure++] = atoi(tmp);
}
首先得到最高位數據是否夠4位元,若夠則不用特別獲取。
因爲我們是從檔案中獲取數據,在符號的判斷時做過一次ch = fgetc()
所以要注意第一位不要漏掉,有可能在符號判斷已經獲取了。
對於字串轉換成int數都採用atoi()
,十分方便。
剩餘數據獲取:
if (1 == sign) {
i = head + 1;
} else {
i = head;
}
if (1 == sign) {
ch = fgetc(fp);
}
while (i < size) {
for (j = 0; j < 4; j++) {
tmp[j] = ch;
ch = fgetc(fp);
i++;
}
huge->data[figure++] = atoi(tmp);
}
注:若爲負數,ch一直是負號沒有變,所以對負數剩餘數據的獲取需要額外進行一個賦值操作。
至此巨大數初始化及其獲取就完成了,完整函數如下:
boolean initHuge(HUGE *huge, int size, FILE *fp) {
int count;
int head;
char tmp[4] = {0};
int figure = 0;
int i;
int j;
char ch;
boolean sign;
ch = fgetc(fp);
if ('-' == ch) {
sign = 1;
size--;
} else {
sign = 0;
}
count = (size + 3) / 4;
head = size % 4;
huge->sign = sign;
huge->size = size;
huge->data = (int *) calloc(sizeof(int), count);
if (NULL == huge->data) {
return FALSE;
}
for (i = 0; i < head; i++) {
if (1 == sign) {
tmp[i] = fgetc(fp);
} else {
tmp[i] = ch;
ch = fgetc(fp);
}
}
if (0 != head){
huge->data[figure++] = atoi(tmp);
}
if (1 == sign) {
i = head + 1;
} else {
i = head;
}
if (1 == sign) {
ch = fgetc(fp);
}
while (i < size) {
for (j = 0; j < 4; j++) {
tmp[j] = ch;
ch = fgetc(fp);
i++;
}
huge->data[figure++] = atoi(tmp);
}
return TRUE;
}
有了獲取就可以完成巨大數的顯示和銷燬函數了:
boolean destoryData(HUGE huge) {
free(huge.data);
}
void showHuge(HUGE huge) {
int count;
int i = 0;
count = (huge.size + 3) / 4;
if (1 == huge.sign && 0 != huge.data[0]) {
printf("-");
}
printf("%d", huge.data[0]);
for (i = 1; i < count; i++) {
printf("%04d", huge.data[i]);
}
printf("\n");
}
在巨大數輸出函數中,除前四位外,其他數據空位由0填補,而前四位不需補零輸出。