巨大數的原理解釋和初始化獲取

2020-08-11 18:01:24

引入巨大數的原因:
因爲在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填補,而前四位不需補零輸出。