本文格式為Word版，下載可任意編輯——第4講數(shù)組和廣義表

Chapter4ArrayGeneralList

Section1Array

ADTArray{D={aj1,j2,...,,ji,jn|ji=0,...,bi-1,i=1,2,..,n}(n稱數(shù)組的維數(shù)，bi是數(shù)組第i維的長度，ji是數(shù)組元素的第i維下標(biāo))

數(shù)組的抽象數(shù)據(jù)類型定義

基本操作

R={R1,R2,...,Rn}Ri={aj1,...ji,...jn,aj1,...ji+1,...jn|0jkbk-1,1kn且ki,0jibi-2,i=2,...,n}

}ADTArray

二維數(shù)組的定義數(shù)據(jù)對象:D={aij|0≤i≤b1-1,0≤j≤b2-1}

數(shù)據(jù)關(guān)系:R={ROW,COL}

COL={ai,j,ai+1,j|0≤i≤b1-2,0≤j≤b2-1}ROW={ai,j,ai,j+1|0≤i≤b1-1,0≤j≤b2-2}

基本操作InitArray(A,n,bound1,...,boundn)DestroyArray(A)Value(A,x,index1,...,indexn)Assign(A,x,index1,...,indexn)

InitArray(A,n,bound1,...,boundn)操作結(jié)果：若維數(shù)n和各維長度合法，則構(gòu)造相應(yīng)的數(shù)組A,并返回OK。

DestroyArray(A)操作結(jié)果：銷毀數(shù)組A。

Value(A,x,index1,...,indexn)初始條件：A是n維數(shù)組，x為元素變

量，隨后是n個(gè)下標(biāo)值。操作結(jié)果：若各下標(biāo)不超界，則x賦值為所指定的A的元素值，并

返回OK。

Assign(A,x,index1,...,indexn)初始條件：A是n維數(shù)組，x為元素變量，隨后是n個(gè)下標(biāo)值。操作結(jié)果：若下標(biāo)不超界，則將x的值賦給所指定的A的元素，并返回OK。

一維數(shù)組

定義一致類型的數(shù)據(jù)元素的集合。一維數(shù)組的例如012345678935274918605477834102

與順序表的不同在于數(shù)組可以按元素的下標(biāo)直接存儲和訪問數(shù)組元素。

一維數(shù)組(Array)類的定義

templateclassTypeclassArray{Type*elements;//數(shù)組存放空間intArraySize;//當(dāng)前長度voidgetArray();//建立數(shù)組空間public:Array(intSize=DefaultSize);Array(constArrayTypex);

~Array(){delete[]elements;}ArrayTypeoperator=//數(shù)組賦值(constArrayTypeA);Typeoperator[](inti);//取元素值intLength()const{returnArraySize;}//取數(shù)組長度voidReSize(intsz);//擴(kuò)展數(shù)組}

一維數(shù)組公共操作的實(shí)現(xiàn)

templateclassTypevoidArrayType::getArray(){//私有函數(shù)：創(chuàng)立數(shù)組存儲空間elements=newType[ArraySize];}

templateclassTypeArrayType::Array(intsz){ArraySize=sz;getArray();}

templateclassTypeArrayType::Array(ArrayTypex){intn=ArraySize=x.ArraySize;elements=newType[n];Type*srcptr=x.elements;Type*destptr=elements;while(n--)*destptr++=*srcptr++;}

templateclassTypeArrayType::Array(ArrayTypex){intSize=x.ArraySize;elements=newType[Size];for(inti=0;iSize;i++)elements[i]=x.elements[i];}

templateclassTypeTypeArrayType::operator[](inti){if(i0||iArraySize-1){cerr“數(shù)組下標(biāo)超界〞endl;returnNULL;}returnelements[i];}

templateclassTypevoidArrayType::Resize(intsz){if(sz=0

sz!=Ar