數(shù)據(jù)結(jié)構(gòu)之多維數(shù)組

定義結(jié)構(gòu)體

typedef struct {

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

各基本操作函數(shù)原型說(shuō)明

（1）創(chuàng)建數(shù)組

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

（2）銷(xiāo)毀數(shù)組

//銷(xiāo)毀數(shù)組
Status DestroyArray(Array* A);

（3）數(shù)組的定位

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

（4）數(shù)組元素的賦值

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

（5）獲取數(shù)組元素

//A為n維數(shù)組，e為元素變量,隨后是n個(gè)下標(biāo)值
//若下標(biāo)不超界，則將e賦值為所指定的A的元素（獲?。?
Status GetValue(ElemType* e, Array A, ...);

各基本操作的具體實(shí)現(xiàn)

（1）創(chuàng)建數(shù)組函數(shù)實(shí)現(xiàn)

//創(chuàng)建多維數(shù)組
Status InitArray(Array* A, int dim, ...) {
	if (dim <1 || dim>MAX_ARRAY_DIM) return ERROR;//參數(shù)不合法
	A->dim = dim;
	A->bounds = (int*)malloc(sizeof(int) * dim);
	if (!A->bounds) return OVERFLOW;//分配內(nèi)存失敗
	//若各維長(zhǎng)度合法，則存入A.bounds，并求出A的元素總數(shù)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);
	//為數(shù)組分配內(nèi)存空間內(nèi)
	A->base = (ElemType*)malloc(sizeof(ElemType) * elemtotal);
	if (!A->base) return OVERFLOW;//分配內(nèi)存失敗
	//求映像函數(shù)Ci,并存入A.constants[i-1],i = 1,...,dim;
	A->constants = (int*)malloc(sizeof(int) * dim);
	if (!A->constants) return OVERFLOW;//分配內(nèi)存失敗
	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）銷(xiāo)毀數(shù)組函數(shù)實(shí)現(xiàn)

//銷(xiāo)毀數(shù)組
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）數(shù)組定位函數(shù)實(shí)現(xiàn)

//數(shù)組的定位
Status LocateArray(Array A, va_list ap, int* offset) {
	int i, instand;
	//若ap指示的元素下標(biāo)合理，則求出元素相對(duì)位置，返回到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);//調(diào)試代碼
			return ERROR;
		}
		*offset += A.constants[i] * instand;
	}
	return  OK;
}

（4）數(shù)組元素賦值函數(shù)實(shí)現(xiàn)

//數(shù)組賦值
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）取出數(shù)組元素函數(shù)實(shí)現(xiàn)

//獲取數(shù)組元素的值，并用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;
}

測(cè)試分析

創(chuàng)建

創(chuàng)建一個(gè)二維數(shù)組，其第一維長(zhǎng)度為4，第二維長(zhǎng)度為3。

測(cè)試代碼：

運(yùn)行結(jié)果：

銷(xiāo)毀

將結(jié)構(gòu)體A的地址傳入到DestroyArray函數(shù)中，執(zhí)行操作。

測(cè)試代碼：

運(yùn)行結(jié)果：

數(shù)組元素賦值

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

測(cè)試代碼：

運(yùn)行結(jié)果：

取出數(shù)組元素

測(cè)試代碼：

運(yùn)行結(jié)果：

思考與小結(jié)

1、 對(duì)數(shù)組的再認(rèn)識(shí)

存儲(chǔ)器的結(jié)構(gòu)是一維線(xiàn)性的結(jié)構(gòu)，數(shù)組是多維的結(jié)構(gòu)。如果要將一個(gè)多維的結(jié)構(gòu)放在一個(gè)一維的存儲(chǔ)單元里，就必須先將多維的數(shù)組轉(zhuǎn)換成一個(gè)一維的線(xiàn)性序列，才能將其放在存儲(chǔ)器當(dāng)中。數(shù)組的存儲(chǔ)方式主要有兩種：一張是以行序?yàn)橹鞯拇鎯?chǔ)方式，另外一種是以列序?yàn)橹鞯拇鎯?chǔ)方式。

2、調(diào)試過(guò)程中遇到的問(wèn)題及解決方案

1、兩次編譯報(bào)錯(cuò)

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

va_start函數(shù)的運(yùn)用問(wèn)題，函數(shù)原型：void va_start（va_list ap，parmN）；報(bào)錯(cuò)原因?yàn)閰?shù)不正確。查看c語(yǔ)言開(kāi)發(fā)手冊(cè)，得出原因。

ap 一個(gè)va_list類(lèi)型的實(shí)例

Prmhn 第一個(gè)變量參數(shù)前的命名參數(shù)

②錯(cuò)誤信息：*LNK2019 無(wú)法解析的外部符號(hào) "int __cdecl SetArray(struct Array ,int,int,…)" (?SetArray@@YAHPAUArray@@HHZZ)，函數(shù) _main 中引用了該符號(hào)

此錯(cuò)誤信息為，找的到定義卻又未找到實(shí)現(xiàn)的函數(shù)，故需將函數(shù)實(shí)現(xiàn)后才能調(diào)用，同時(shí)注意參數(shù)的對(duì)應(yīng)，避免出現(xiàn)以上問(wèn)題。

2、運(yùn)行時(shí)報(bào)錯(cuò)

運(yùn)行時(shí)報(bào)錯(cuò)，數(shù)據(jù)訪(fǎng)問(wèn)出現(xiàn)問(wèn)題。通過(guò)檢查報(bào)錯(cuò)信息的前后語(yǔ)句，發(fā)現(xiàn)在訪(fǎng)問(wèn)數(shù)組的時(shí)候忘記i+1,導(dǎo)致i走到-1形成錯(cuò)誤原因。

3、運(yùn)行結(jié)果出錯(cuò)

運(yùn)行結(jié)果出現(xiàn)了地址與數(shù)值都輸出的情況，通過(guò)調(diào)試，發(fā)現(xiàn)第一次進(jìn)入LocateArray函數(shù)之后，函數(shù)返回了ERROR，通過(guò)打印語(yǔ)句檢查，函數(shù)確實(shí)進(jìn)入了判斷語(yǔ)句內(nèi)，返回ERROR；

表明參數(shù)不準(zhǔn)確或者函數(shù)判斷語(yǔ)句不正確，由于數(shù)值為自己控制的，故參數(shù)不準(zhǔn)確的可能性較小，仔細(xì)分析了參數(shù)臨界以及函數(shù)邏輯，將判斷參數(shù)的條件改成正確判斷語(yǔ)句。得到正確的結(jié)果。

3、算法的時(shí)間復(fù)雜度分析

InitArray函數(shù)的時(shí)間復(fù)雜度為O(n);

DestroyArray函數(shù)的時(shí)間復(fù)雜度為O(1);

LocateArray函數(shù)的時(shí)間復(fù)雜度為O(n);

SetArray函數(shù)的時(shí)間復(fù)雜度為O(n);

GetArray函數(shù)的時(shí)間復(fù)雜度為O(n);

SetArray函數(shù)和GetArray函數(shù)的時(shí)間復(fù)雜度主要受LocateArray函數(shù)影響。

總結(jié)

到此這篇關(guān)于C語(yǔ)言多維數(shù)組數(shù)據(jù)結(jié)構(gòu)實(shí)現(xiàn)的文章就介紹到這了,更多相關(guān)C語(yǔ)言多維數(shù)組數(shù)據(jù)結(jié)構(gòu)內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

最新評(píng)論