數據結構 數組順序存儲詳細介紹。本站提示廣大學習愛好者：（數據結構 數組順序存儲詳細介紹）文章只能為提供參考，不一定能成為您想要的結果。以下是數據結構 數組順序存儲詳細介紹正文

數據結構 數組順序存儲詳細介紹

投稿：lqh

數據結構 數組順序存儲

     最近學習數據結構，看到數組順序存儲，很是頭昏，看不懂，很多東西，這裡在網上找了比較詳細的資料，大家好好看注釋內容：

#include<stdarg.h>  
#define MAX_ARRAY_DIM 8 //假設數組維數的最大值為8 
typedef struct {
 ElemType *base;  //數組元素基址，由InitArray分配
 int dim;  //數組維數
 int *bounds;  //數組維界基址，由InitArray分配
 int *constants;  //數組映象函數常量基址，由InitArray分配
}Array;

Status InitArray(Array &A,int dim,...){//這裡用的是“可變參”形參方式。它主要解決維數不定的問題。
//舉例：設有4維數組，各維分別是：4,5,6,7（這些數字是隨意給的），那麼，調用方式：
//InitArray(ar, 4, 4, 5, 6, 7);
//ar其中，ar也是假設的變量名稱, 4表示數組有4維, 4, 5, 6, 7這4個數是各維大小
//如果是5維的，那麼就這樣：
//InitArray(ar, 5, 第一維數，第二維數，第三維數，第四維數，第五維數);
//若維數dim和隨後的各維長度合法，則構造相應的數組A，並返回OK。
if (dim<1 ||dim>MAX_ARRAY_DIM) return ERROR;
A.dim=dim;
A.bounds=(int *)malloc(dim*sizeof(int));
if (!A.bounds) exit(OVERFLOW);
//若各維長度合法，則存入A.bounds，並求出A的元素總數elemtotal。
elemtotal=1;
va_start(ap,dim); //ap為va_list類型，是存放變長參數表信息的數組。
for (i=0;i<dim;++i){
 A.bounds[i]=va_arg(ap,int);//從這裡可以看出，A.bounds數組中，存放的是各維的大小
 if (A.bounds[i]<0) return UNDERFLOW;
 elemtotal * = A.bounds[i];//各維數之積，自然是數組中元素的總個數
}
va_end(ap);
A.base=(ElemType *)malloc(elemtotal *sizeof(ElemType));//這個就是“多維數組”的存儲本質：一維數組！
//用一維方式表示多維數組後（其實，從管理和使用的角度看，內存就只有一維這麼一種形式），存在如何按“多維”的邏輯角度定位元素的問題。再說清楚些：假設前面所講的4維數組，其元素用下標形式表示，范圍為：(0,0,0,0)到(3,4,5,6)。對於任意下標（在有效范圍內）(i1, i2, i3, i4)所對應的元素，轉換到“一維”空間後，其下標應該是什麼？這就是這個程序後面要處理的主要問題。
if (!A.base) exit (OVERFLOW):
//求映象函數的常數ci（i為下標），並存入A.constants[i-1]，i=1，...dim。
A.constants=(int *)malloc(dim *sizeof(int));
if (!A.constants)exit (OVERFLOW);
//以前面的4維數組為例子，其中A.bounds[0]=4，A.bounds[1]=5，A.bounds[2]=6，A.bounds[3]=7。
//跟蹤下面的程序：
A.constants[dim-1]=1;//A.constants[3] = 1
for (i=dim-2;i>=0;--i)//A.constants[2] = 7，A.constants[1] = 6*7，A.constants[0] = 5*6*7
 A.constants[i]=A.bounds[i+1] * A.constants[i+1];
//說到這裡，這個問題就清晰了：A.constants中的元素，是幫助定位用的。比如說：對於(2,0,0,0)這個下標的元素，應該越過前面的(0,0,0,0)~(0,4,5,6)和(1,0,0,0)~(1,4,5,6)這兩大塊，而這兩大塊中的每一塊都有5*6*7個元素，這正好就是A.constants[0]中所存放的數據啊！
//現在應該明白了吧！
return OK;
}

status Locate(Array A,va_list ap,int &off){
//若ap指示的各下標值合法，則求出該元素在A中相對地址off。
 off=0;
 for (i=0;i<A.dim;++i){
 ind=va_arg(ap,int);
 if (ind<0 || ind>=A.bounds[i]) return OVERFLOW；
 off + = A.constants[i] * ind;
 }
 return OK;

補充：為什麼A.constants[dim-1]

bounds存的就是每一維裡面的個數，constants保存的是每一個維度如果下標增加1，那個對應到內存空間的下標應該增加多少。說起來比較抽象，我們假設是3維，就比較容易說清楚了，首先把3維看作有bounds[0]那麼高，對於每一個0到bounds[0]-1的范圍內，就是一個平面，這個平面有bounds[1]那麼長，bounds[2]那麼寬。那麼，我們把高=0，長=0，寬=0對應到內存的第一個位置，高=0，長=0，寬=1的對應到第二個位置，那麼高=0，長=1，寬=0應該放在什麼位置呢？顯然就是0+bounds[2]這個位置。那麼高=1，長=0，寬=0的那個元素應該在哪個位置呢？顯然是高=0這一個平面放完了之後的那個位置，高=0這個平面有長度*寬度那麼多個元素，也就是bounds[1]*bounds[2]這麼多個元素，所以高=1，長=0，寬=0這個元素就應該在0+bounds[1]*bounds[2]這個位置，對吧。假設還有第四維度，我們假設這個維度代表時間吧，那時間=0，高=0，長=0，寬=0的元素放在內存第0個位置，那麼時間=1，高=0，長=0，寬=0的元素是不是應該放在0+bound[1]*bound[2]*bound[3]這個位置呢。這就是A.constants[i]=A.bounds[i+1] * A.constants[i+1];這個公式的來歷。當然，我只是很簡單的解釋了，很多細節需要你自己考慮，因為語言表示起來太復雜了，不知道怎麼表述。。。
其實你仔細看A.constants[i]=A.bounds[i+1] * A.constants[i+1];，這是一個遞推公式，把它展開的話，下面我就把constants[i]簡寫為coni，bounds[i]簡寫為boni那麼con i= bon[i+1]*con[i+1]=bon[i+1]*bon[i+2]*con[i+2] = bon[i+1]*bon[i+2]*bon[i+3]*con[i+3]=bon[i+1]*bon[i+2]*bon[i+3]*...*bon[dim]你看這個公式是不是就是相當於上面說的高度*長度*寬度？ 剛才那個bon[dim]應該寫成bon[dim-1]不過這個不影響理解。

然後我們看最後一維，例如上面例子的寬度，寬度+1是不是就正好內存地址+1呢？於是對應寬度這個最後的維度，每次地址只需+1就能訪問下一個元素，因此bon[dim-1]也就是最後一維的，是不是就應該等於1呢。。

感謝閱讀，希望能幫助到大家，謝謝大家對本站的支持！