C語言多維數組數據結構的實現詳解

Posted on by

數據結構之多維數組

定義結構體

typedef struct {

	ElemType* base;//數組元素基址（數組基址）
	int dim;//數組維數
	int* bounds;//數組維界基址（存放各位長度信息）
	int* constants;//數組映象函數常量基址
}Array;

各基本操作函數原型說明

（1）創建數組

//若函數參數合法，則構建數組A
Status InitArray(Array* A, int dim, ...);

（2）銷毀數組

//銷毀數組
Status DestroyArray(Array* A);

（3）數組的定位

//獲取元素位置（數組定位）
Status LocateArray(Array A, va_list ap, int* offset);

（4）數組元素的賦值

//A為n維數組，e為元素變量,隨後是n個下標值
//若下標不超界，則將e的值賦給所指定的A的元素（賦值）
Status SetArray(Array* A, ElemType e, ...);

（5）獲取數組元素

//A為n維數組，e為元素變量,隨後是n個下標值
//若下標不超界，則將e賦值為所指定的A的元素（獲取）
Status GetValue(ElemType* e, Array A, ...);

各基本操作的具體實現

（1）創建數組函數實現

//創建多維數組
Status InitArray(Array* A, int dim, ...) {
	if (dim <1 || dim>MAX_ARRAY_DIM) return ERROR;//參數不合法
	A->dim = dim;
	A->bounds = (int*)malloc(sizeof(int) * dim);
	if (!A->bounds) return OVERFLOW;//分配內存失敗
	//若各維長度合法，則存入A.bounds，並求出A的元素總數elemtotal
	int elemtotal = 1;
	va_list ap;
	va_start(ap, dim);
	for (int i = 0; i < dim; ++i) {
		A->bounds[i] = va_arg(ap, int);
		if (A->bounds[i] < 0)return UNDERFLOW;
		elemtotal *= A->bounds[i];
	}
	va_end(ap);
	//為數組分配內存空間內
	A->base = (ElemType*)malloc(sizeof(ElemType) * elemtotal);
	if (!A->base) return OVERFLOW;//分配內存失敗
	//求映像函數Ci,並存入A.constants[i-1],i = 1,...,dim;
	A->constants = (int*)malloc(sizeof(int) * dim);
	if (!A->constants) return OVERFLOW;//分配內存失敗
	A->constants[dim - 1] = 1;
	for (int i = dim - 2; i >= 0; --i) {
		A->constants[i] = A->bounds[i + 1] * A->constants[i + 1];
	} 
	return OK;
}

（2）銷毀數組函數實現

//銷毀數組
Status DestroyArray(Array* A) {
	if (!A->base) return ERROR;
	free(A->base);
	A->base = NULL;
	if (!A->bounds) return ERROR;
	free(A->bounds);
	A->bounds = NULL;
	if (!A->constants) return ERROR;
	free(A->constants);
	A->constants = NULL;
	return OK;
}

（3）數組定位函數實現

//數組的定位
Status LocateArray(Array A, va_list ap, int* offset) {
	int i, instand;
	//若ap指示的元素下標合理，則求出元素相對位置，返回到offset
	*offset = 0;
	for (i = 0; i < A.dim; i++) {
		instand = va_arg(ap, int);
		if (instand < 0 || instand > A.bounds[i]) {
		//	printf("instand = %d,定位失敗\n",instand);//調試代碼
			return ERROR;
		}
		*offset += A.constants[i] * instand;
	}
	return  OK;
}

（4）數組元素賦值函數實現

//數組賦值
Status SetArray(Array *A, ElemType e, ...) {
	va_list ap;
	int offset;
	va_start(ap, e);
	if (LocateArray(*A, ap, &offset) == ERROR) return ERROR;
	va_end(ap); 
	*(A->base + offset) = e;
	return OK;
}

（5）取出數組元素函數實現

//獲取數組元素的值，並用E返回
Status GetValue(ElemType* e, Array A, ...) {
	va_list ap;
	int offset;
	va_start(ap, A);
	if (LocateArray(A, ap, &offset) == ERROR) return ERROR;
	va_end(ap);
	*e = *(A.base + offset);
	return OK;
}

測試分析

創建

創建一個二維數組，其第一維長度為4，第二維長度為3。

測試代碼：

運行結果：

銷毀

將結構體A的地址傳入到DestroyArray函數中，執行操作。

測試代碼：

運行結果：

數組元素賦值

定義二維數組B[4][3],通過SetArray函數將其值賦給數組A,通過遍歷輸出A中元素的值，則可以判斷出賦值是否準確。

測試代碼：

運行結果：

取出數組元素

測試代碼：

運行結果：

思考與小結

1、 對數組的再認識

存儲器的結構是一維線性的結構，數組是多維的結構。如果要將一個多維的結構放在一個一維的存儲單元裡，就必須先將多維的數組轉換成一個一維的線性序列，才能將其放在存儲器當中。數組的存儲方式主要有兩種：一張是以行序為主的存儲方式，另外一種是以列序為主的存儲方式。

2、調試過程中遇到的問題及解決方案

1、兩次編譯報錯

①錯誤信息：va_start argument must not have reference type and must not be parenthesized；

va_start函數的運用問題，函數原型：void va_start（va_list ap，parmN）；報錯原因為參數不正確。查看c語言開發手冊，得出原因。

ap 一個va_list類型的實例

Prmhn 第一個變量參數前的命名參數

②錯誤信息：*LNK2019 無法解析的外部符號 “int __cdecl SetArray(struct Array ,int,int,…)” (?SetArray@@YAHPAUArray@@HHZZ)，函數 _main 中引用瞭該符號

此錯誤信息為，找的到定義卻又未找到實現的函數，故需將函數實現後才能調用，同時註意參數的對應，避免出現以上問題。

2、運行時報錯

運行時報錯，數據訪問出現問題。通過檢查報錯信息的前後語句，發現在訪問數組的時候忘記i+1,導致i走到-1形成錯誤原因。

3、運行結果出錯

運行結果出現瞭地址與數值都輸出的情況，通過調試，發現第一次進入LocateArray函數之後，函數返回瞭ERROR，通過打印語句檢查，函數確實進入瞭判斷語句內，返回ERROR；

表明參數不準確或者函數判斷語句不正確，由於數值為自己控制的，故參數不準確的可能性較小，仔細分析瞭參數臨界以及函數邏輯，將判斷參數的條件改成正確判斷語句。得到正確的結果。

3、算法的時間復雜度分析

InitArray函數的時間復雜度為O(n);

DestroyArray函數的時間復雜度為O(1);

LocateArray函數的時間復雜度為O(n);

SetArray函數的時間復雜度為O(n);

GetArray函數的時間復雜度為O(n);

SetArray函數和GetArray函數的時間復雜度主要受LocateArray函數影響。

總結

到此這篇關於C語言多維數組數據結構實現的文章就介紹到這瞭,更多相關C語言多維數組數據結構內容請搜索WalkonNet以前的文章或繼續瀏覽下面的相關文章希望大傢以後多多支持WalkonNet！

推薦閱讀：