14.對象數(shù)組以及myvector類實(shí)現(xiàn)

1、算法分析與設(shè)計(jì)（JAVA版）講師：牛牧數(shù)組向量類集合 Lesson14數(shù)組向量類集合 數(shù)組的定義數(shù)組是n（n1）個(gè)相同數(shù)據(jù)類型的數(shù)據(jù)元素a0,a1,a2,.,an-1構(gòu)成的占用一塊地址連續(xù)的內(nèi)存單元的有限集合。數(shù)組的實(shí)現(xiàn)數(shù)組通常以字節(jié)為內(nèi)部計(jì)數(shù)單位。對一個(gè)有n個(gè)數(shù)據(jù)元素的一維數(shù)組，設(shè)a0是下標(biāo)為0的數(shù)組元素，Loc(a0)是a0的內(nèi)存單元地址，k是每個(gè)數(shù)據(jù)元素所需的字節(jié)個(gè)數(shù)，則數(shù)組中任一數(shù)據(jù)元素ai的內(nèi)存單元地址Loc(ai)可由下面公式求出： Loc(ai) = Loc(a0) + i k ( 0in ) 數(shù)組的實(shí)現(xiàn)對一個(gè)m行n列的二維數(shù)組，設(shè)a00是行下標(biāo)和列下標(biāo)均為0的數(shù)組元素，Loc(

2、a00)是a00的存儲地址，k是每個(gè)數(shù)據(jù)元素所需的字節(jié)個(gè)數(shù)，則數(shù)組中任一數(shù)據(jù)元素aij的內(nèi)存單元地址Loc(aij)可由下面公式求出： Loc(aij) = Loc(a00) + (i n + j) k ( 0im, 0jn）二維數(shù)組的順序存儲結(jié)構(gòu)數(shù)組抽象數(shù)據(jù)類型數(shù)據(jù)集合：數(shù)組的數(shù)據(jù)集合可以表示為a0, a1, a2, ., an-1，且限定數(shù)組元素必須存儲在地址連續(xù)的內(nèi)存單元中。操作集合：（1）分配內(nèi)存空間acclocate()：為數(shù)組分配用戶所需的內(nèi)存空間。（2）取數(shù)組長度getLength()：取數(shù)組的長度。（3）存數(shù)組元素set(i, x)：把數(shù)據(jù)元素x存入下標(biāo)為i的數(shù)組中。其約束條件

3、為：0igetLength()-1。（4）取數(shù)組元素get(i)：取出數(shù)組中下標(biāo)為i的數(shù)據(jù)元素。其約束條件為：0igetLength()-1。Java語言支持的數(shù)組功能基本數(shù)據(jù)類型的數(shù)組 由于數(shù)組是非?；A(chǔ)的程序設(shè)計(jì)語言要素，所以Java語言設(shè)計(jì)實(shí)現(xiàn)了數(shù)組功能。Java語言（以及大部分高級程序設(shè)計(jì)語言）支持的數(shù)組操作有：（1）分配內(nèi)存空間 （2）獲得數(shù)組長度 （3）存數(shù)組元素 （4）取數(shù)組元素 Java語言支持的數(shù)組功能對象數(shù)組 除了可以定義基本數(shù)據(jù)類型的數(shù)組外，Java語言還可以定義對象數(shù)組。向量類Java語言只直接支持上述基本的數(shù)組操作。如果程序開始時(shí)定義的數(shù)組長度為10，且數(shù)組中已經(jīng)存放

4、了若干數(shù)據(jù)元素，要在程序運(yùn)行過程中擴(kuò)充數(shù)組長度為20，且把數(shù)組中原先存放的數(shù)據(jù)元素原樣保存，則系統(tǒng)不提供直接支持，需要應(yīng)用程序自己實(shí)現(xiàn)。為了擴(kuò)充數(shù)組功能，Java類庫還定義了Vector類。要說明的是，國內(nèi)的大部分教材和科技書籍都把Vector類翻譯為向量類，但這里的向量和數(shù)學(xué)上的向量概念完全不同。向量類Vector擴(kuò)充了數(shù)組的功能，提供了自動(dòng)擴(kuò)充數(shù)組長度、且把數(shù)組中原先存放的數(shù)據(jù)元素原樣保存的功能。Vector類在java.util包中。集合集合（Set）是具有某種相似特性的事物的全體。換一種說法，也可以說，集合是某種具有相同數(shù)據(jù)類型的數(shù)據(jù)元素全體。如果一個(gè)數(shù)據(jù)元素x在一個(gè)集合A中，則說數(shù)據(jù)

5、元素x屬于集合A；如果一個(gè)數(shù)據(jù)元素x不在一個(gè)集合A中，就說數(shù)據(jù)元素x不屬于集合A。集合如果集合A中的所有數(shù)據(jù)元素都在集合B中，則說集合B包含集合A。 集合的運(yùn)算主要有三種：兩個(gè)集合的并AB、兩個(gè)集合的交AB、兩個(gè)集合的差A(yù)-B。沒有一個(gè)數(shù)據(jù)元素的集合稱做空集合。集合抽象數(shù)據(jù)類型 數(shù)據(jù)集合：數(shù)據(jù)元素集合可以表示為a0, a1, a2, ., an-1，每個(gè)數(shù)據(jù)元素的數(shù)據(jù)類型可以是任意的類類型。操作集合：（1）添加add(obj)：在集合中添加數(shù)據(jù)元素obj。（2）刪除remove(obj)：刪除集合中的數(shù)據(jù)元素obj。（3）屬于contain(obj)：數(shù)據(jù)元素obj是否屬于集合。是則返回true,否則返回false。（4）包含include(otherSet)：當(dāng)前對象集合是否包含集合otherSet。是則返回true,否則返回false。（5）相等eqauls(otherSet)：當(dāng)前對象集合是否和集合otherSet相等。是則返回true,否則返回false。（6）數(shù)據(jù)元素個(gè)數(shù)size()：返回集合中的數(shù)據(jù)元素個(gè)數(shù)。（7）集合空否isEmpty()：若集合空返回true，否則返回false。集合類集合的特點(diǎn)是數(shù)據(jù)元素?zé)o序且不重復(fù)。集合類既可以基于向量類來實(shí)現(xiàn)，也可以用其他方法