?一、維度及長度均可任意變形的動(dòng)態(tài)數(shù)組概述 收藏
??? 近日，有同事需要設(shè)計(jì)一個(gè)可自由變形的多維數(shù)組，苦思數(shù)日，不得其解，求助于我。于是我?guī)退麑懥艘粋€(gè)可自由改變維度及長度的數(shù)組ADT。后來想，網(wǎng)上應(yīng)該也有人需要這種東西吧，何不放到博客上來，讓有此需要的朋友也一同來參考參考。于是就將開始的3個(gè)函數(shù)擴(kuò)展為20個(gè)函數(shù)。鑒于時(shí)間倉促，源碼一定有很多不完善的地方，如果遇到哪些牛人有興趣對其進(jìn)行改進(jìn)，更求之不得了。

?

??? 我將此ADT稱為Dynamic Dimensionality and Length Array，動(dòng)態(tài)維度及長度數(shù)組，簡稱DDLA。它的主要特性如下：

?

1. 超越C99的VLA可變長數(shù)組。VLA雖然每維的長度可為變量，但仍有兩個(gè)限制，一是維度不可變；二是一旦定義，長度不能再改變，即非動(dòng)態(tài)的。DDLA則無論維度、長度皆動(dòng)態(tài)，不但每維長度可為變量，維度也可為變量。

?

2. DDLA即使定義之后，仍可以根據(jù)需要在任何時(shí)候任意改變維度及長度，做到真正的完全動(dòng)態(tài)，堪稱數(shù)組中的變形金剛。而且，變形之后，原有數(shù)據(jù)仍可保留。變形方式簡單快捷。

?

3. 超越c/c++數(shù)組作為形參會(huì)隱式轉(zhuǎn)換為指針的特性。c/c++這項(xiàng)特性在提高效率的同時(shí)，也造成了在被調(diào)函數(shù)內(nèi)部無法通過sizeof運(yùn)算直接取得傳入數(shù)組大小的問題。DDLA繼續(xù)保持這個(gè)效率的同時(shí)，仍然可以在被調(diào)函數(shù)內(nèi)部直接計(jì)算出傳入數(shù)組的大小。

?

?

??? 設(shè)計(jì)DDLA類型的動(dòng)態(tài)數(shù)組，不可避免需要建立中間地址緩沖區(qū)，如何構(gòu)造這個(gè)緩沖區(qū)？通常的算法，是隨時(shí)構(gòu)造隨時(shí)分配，例如一個(gè)動(dòng)態(tài)二維數(shù)組可以這樣構(gòu)造：

?

view plaincopy to clipboardprint?
int i, m = 10, n = 20;??
int **p = ( int** )malloc( m * sizeof( int* ) );??
for( i = 0; i < m; ++i )??
??? p[i] = ( int* )malloc( n * sizeof( int ) );?
int i, m = 10, n = 20;
int **p = ( int** )malloc( m * sizeof( int* ) );
for( i = 0; i < m; ++i )
?p[i] = ( int* )malloc( n * sizeof( int ) );
?

?

??? 這種方法有一個(gè)明顯的缺點(diǎn)，就是無論元素存儲(chǔ)區(qū)還是中間地址緩沖區(qū)都是不連續(xù)的！這會(huì)造成如下這些問題：

?

1. 堆管理函數(shù)頻繁運(yùn)行，效率低下，數(shù)組越大，效率影響越明顯；

2. 如果中間某個(gè)步驟內(nèi)存分配失敗，需要對已分配的內(nèi)存重新釋放，算法復(fù)雜；

3. 數(shù)組使用完后，需要逐個(gè)內(nèi)存塊釋放，效率低；

4. 若需要?jiǎng)討B(tài)改變數(shù)組，算法復(fù)雜。

?

??? 但實(shí)際上，中間地址緩沖區(qū)和元素存儲(chǔ)區(qū)的大小是可以預(yù)先計(jì)算出來的，在此前提下，兩個(gè)存儲(chǔ)塊可以預(yù)先整體一次分配，效率有很大提高，更重要的是，這個(gè)做法使數(shù)組變形的算法大大簡化，變形過程變得非常簡單，只要改變元素存儲(chǔ)區(qū)的大小，然后重新產(chǎn)生中間地址就行了。DDLA就是基于這個(gè)原理設(shè)計(jì)的，使用的中間地址緩沖區(qū)和元素存儲(chǔ)區(qū)都是連續(xù)的。

?

本文來自CSDN博客，轉(zhuǎn)載請標(biāo)明出處：http://blog.csdn.net/supermegaboy/archive/2009/08/27/4491523.aspx

總結(jié)

以上是生活随笔為你收集整理的维度及长度均可任意变形的动态数组的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。