课程名称：数据结构第_7周，第_7讲次摘要第四章数组、集合和矩阵授课题目（章、节）第一节数组第二节向量类第三节集合【目的要求】通过本讲课程的学习，了解数组的实现机制，回顾Java支持的数组功能，掌握MyVector类的实现方法，并在MyVector类的基础上了解集合类的设计和实现方法。【重点】MyVector类的设计和实现方法。【难点】MyVector类的设计和实现方法。内容【本讲课程的引入】我们通过学习前几章可以发现线性表、堆栈、队列和串它们的顺序存储都是基于数组实现的，可见数组是实现其它数据结构顺序存储的基础，所以一般的高级程序设计语言都支持数组功能，这节课我们首先来了解一下数组的实现机制，再回顾Java支持的数组功能。【本讲课程的内容】第4章数组、集合和矩阵4.1数组4.1.1数组的定义数组是n（n≥1）个相同数据类型的数据元素ao,al,a2，...，an-1构成的占用一块地址连续的内存单元的有限集合。问题：数组与线性表的区别与联系相同之处：它们都是若干个相同数据类型的数据元素a0,ala2，"，an-1构成的有限序列。不同之处：（1）数组要求其元素占用一块地址连续的内存单元空间，而线性表无此要求：(2)线性表的元素是逻辑意义上不可再分的元素，而数组中的每个元素还可以是一个数组；(3）数组的操作主要是向某个下标的数组元素中存放数据和取某个下标的数组元素，这与线性表的插入和删除操作不同。4.1.2数组的实现机制1、一维数组（n个元素）中任一元素ai的内存单元地址LOC(ai)=LOC(a0)+i*k(0≤i <n)2、→个m行n列的二维数组LOC(aij)=LOC(aoo)+(i*n+j)*k(0≤i<m，0≤j<n)
课程名称：数据结构 第 7 周，第 7 讲次 摘 要 授课题目（章、节） 第四章 数组、集合和矩阵 第一节 数组 第二节 向量类 第三节 集合 【目的要求】通过本讲课程的学习，了解数组的实现机制，回顾 Java 支持的数组功能，掌握 MyVector 类的 实现方法，并在 MyVector 类的基础上了解集合类的设计和实现方法。 【重 点】MyVector 类的设计和实现方法。 【难 点】MyVector 类的设计和实现方法。 内 容 【本讲课程的引入】我们通过学习前几章可以发现线性表、堆栈、队列和串它们的顺序存 储都是基于数组实现的，可见数组是实现其它数据结构顺序存储的基础，所以一般的高级 程序设计语言都支持数组功能，这节课我们首先来了解一下数组的实现机制，再回顾 Java 支持的数组功能。 【本讲课程的内容】 第 4 章 数组、集合和矩阵 4.1 数组 4.1.1 数组的定义 数组是 n（n≥1）个相同数据类型的数据元素 a0,a1,a2,.,an-1 构成的占用一块地 址连续的内存单元的有限集合。 问题：数组与线性表的区别与联系 相同之处： 它们都是若干个相同数据类型的数据元素 a0,a1,a2,.，an-1 构成的有限序列。 不同之处： (1)数组要求其元素占用一块地址连续的内存单元空间，而线性表无此要求； (2)线性表的元素是逻辑意义上不可再分的元素，而数组中的每个元素还可以是一个数 组； (3)数组的操作主要是向某个下标的数组元素中存放数据和取某个下标的数组元素，这 与线性表的插入和删除操作不同。 4.1.2 数组的实现机制 １、一维数组（n 个元素）中任一元素 ai 的内存单元地址 LOC(ai)=LOC(a０)+i*k (0≤i <n) ２、一个 m 行 n 列的二维数组 LOC(aij)=LOC(a00)+(i*n+j)*k (0≤i<m， 0≤j<n)
下标下标-0第1列2第1行123527345632789第2行第2列450第3列第3行8699n(a）二维数组的逻辑结构(b）行优先顺序存储结构(c）列优先顺序存储结构注：只要知道以下三要素便可随时求出任一元素的地址（意义：数组中的任一元素可随机存取）①开始结点的存放地址（即基地址）；②维数和每维的上、下界；③每个数组元素所占用的单元数例1一个二维数组A，行下标的范围是1到6，列下标的范围是0到7，每个数组元素用相个字节。邻的6个字节存储，存储器按字节编址。那么，这个数组的体积是答：Volume=m*n*L=(6-1+1)*（7-0+1)*6=48*6=288例2设数组a［060，070]的基地址为2048，每个元素占2个存储单元，若以行序为主序顺序存储，则元素a[32,58]的存储地址为答：根据行优先公式LOC（aij)=LOC(aoo)+(i*n+j）*k（≤i<m，0≤j<n）得：L0C(a32,58)=2048+(32*70+58)*2=66444.1.3数组抽象数据类型数据集合：数组的数据集合可以表示为ao，al，a2，...，an-1，且限定数组元素必须存储在地址连续的内存单元中。操作集合：（1）分配内存空间acclocate（)：为数组分配用户所需的内存空间。（2）取数组长度getLength：取数组的长度。（3）存数组元素set（i，x)：把数据元素x存入下标为i的数组中。其约束条件为：0≤i≤getLengthO-1.（4）取数组元素get（i)：取出数组中下标为i的数据元素。其约束条件为：0≤i≤getLengthO-1.4.1.4Java语言支持的数组功能1基本数据类型的数组由于数组是非常基础的程序设计语言要素，所以Java语言设计实现了数组功能。Java语言（以及大部分高级程序设计语言）支持的数组操作有：（1）分配内存空间int a[]=new int[i0];分配了10个元素的int类型数组所需的内存空间，并把该数组在内存中的首地址用对象引用a表示
注：只要知道以下三要素便可随时求出任一元素的地址（意义：数组中的任一元素可随机 存取） ①开始结点的存放地址（即基地址）； ②维数和每维的上、下界； ③每个数组元素所占用的单元数 例１一个二维数组 A，行下标的范围是 1 到 6，列下标的范围是 0 到 7，每个数组元素用相 邻的 6 个字节存储，存储器按字节编址。那么，这个数组的体积是 个字节。 答： Volume=m*n*L=(6-1+1)*(7- 0 +1)*6=48*6=288 例２ 设数组 a[０.60, ０.70]的基地址为 2048，每个元素占 2 个存储单元，若以行序 为主序顺序存储，则元素 a[32,58]的存储地址为 。 答：根据行优先公式 LOC(aij)=LOC(a00)+(i*n+j)*k (0≤i<m，0≤j<n) 得：LOC(a32,58)=2048+(32*70+58)*2＝6644 4.1.3 数组抽象数据类型 数据集合： 数组的数据集合可以表示为 a0, a1, a2, ., an-1，且限定数组元素必须存储在地 址连续的内存单元中。 操作集合： （1）分配内存空间 acclocate()：为数组分配用户所需的内存空间。 （2）取数组长度 getLength()：取数组的长度。 （3）存数组元素 set(i, x)：把数据元素 x 存入下标为 i 的数组中。其约束条件为：0≤i ≤getLength()-1。 （4）取数组元素 get(i)：取出数组中下标为 i 的数据元素。其约束条件为：0≤i≤ getLength()-1。 4.1.4 Java 语言支持的数组功能 1 基本数据类型的数组 由于数组是非常基础的程序设计语言要素，所以 Java 语言设计实现了数组功能。Java 语言（以及大部分高级程序设计语言）支持的数组操作有： （1）分配内存空间 int a[]=new int[10]; 分配了 10 个元素的 int 类型数组所需的内存空间，并把该数组在内存中的首地址用对象引 用 a 表示。 1 2 3 4 5 6 7 8 9 1 4 7 2 5 8 3 6 9 (b) 行优先顺序存储结构 (c) 列优先顺序存储结构 1 2 3 4 5 6 7 8 9 第1行 第2行 第3行 第1列 第2列 第3列 (a) 二维数组的逻辑结构 下标 0 2 8 7 6 5 4 3 1 下标 0 2 8 7 6 5 4 3 1
（2）获得数组长度int c=a.length;a.length表示了数组的长度。（3）存数组元素a[1]=5;把整数5存放在下标为1的数组元素中。（4）取数组元素int d=a[1]:取出下标为1的数组元素赋值给变量d。2对象数组除了可以定义基本数据类型的数组外，Java语言还可以定义对象数组。例如可以定义有4个对象的对象数组pOS：Position pos[]=new Position[4];对象数组也支持存操作和取操作，但和基本数据类型不同的是，所有对象名都是引用类型，所以对象数组的存操作和取操作都是把一个已经创建的对象赋值给一个对象引用，而不是新创建一个对象实体并赋值。Position p]=pos[1];Positionp2=newPosition();pos[2]=p2;plpo对象实体10对象实体1N1对象实体2对象实体2￥对象实体322对象实体3对象实体4rn对象实体4对象实体p202-(a)(b)4.2向量类Java语言只直接支持上述基本的数组操作。如果程序开始时定义的数组长度为10，且数组中已经存放了若于数据元素，要在程序运行过程中扩充数组长度为20，且把数组中原先存放的数据元素原样保存，则系统不提供直接支持，需要应用程序自已实现。为了扩充数组功能，Java类库还定义了Vector类。它提供了自动扩充数组长度、且把数组中原先存放的数据元素原样保存的功能。这里设计一个和Vector类功能类似的MyVector类：public class MyVectorfprivate Object[JelementData;private int elementCount;privatevoidensureCapacity(intminCapacity)(//扩充内存intoldCapacity=elementData.length;if(minCapacity>oldCapacity)(Object oldDatalJ =elementData;int newCapacity= oldCapacity*2;if(newCapacity<minCapacity)newCapacity=minCapacity;
（2）获得数组长度 int c=a.length; a.length 表示了数组的长度。 （3）存数组元素 a[1]=5; 把整数 5 存放在下标为 1 的数组元素中。 （4）取数组元素 int d=a[1]; 取出下标为 1 的数组元素赋值给变量 d。 2 对象数组 除了可以定义基本数据类型的数组外，Java 语言还可以定义对象数组。 例如可以定义有 4 个对象的对象数组 pos： Position pos[]=new Position[4]; 对象数组也支持存操作和取操作，但和基本数据类型不同的是，所有对象名都是引用 类型，所以对象数组的存操作和取操作都是把一个已经创建的对象赋值给一个对象引用， 而不是新创建一个对象实体并赋值。 Position p1=pos[1]; Position p2=new Position(); pos[2]=p2; 4.2 向量类 Java 语言只直接支持上述基本的数组操作。如果程序开始时定义的数组长度为 10，且 数组中已经存放了若干数据元素，要在程序运行过程中扩充数组长度为 20，且把数组中原 先存放的数据元素原样保存，则系统不提供直接支持，需要应用程序自己实现。 为了扩充数组功能，Java 类库还定义了 Vector 类。它提供了自动扩充数组长度、且 把数组中原先存放的数据元素原样保存的功能。这里设计一个和 Vector 类功能类似的 MyVector 类： public class MyVector{ private Object[] elementData; private int elementCount; private void ensureCapacity(int minCapacity){ //扩充内存 int oldCapacity = elementData.length; if (minCapacity > oldCapacity) { Object oldData[] = elementData; int newCapacity = oldCapacity * 2; if (newCapacity < minCapacity) { newCapacity = minCapacity; 对象实体1 对象实体2 对象实体3 对象实体4 0 1 2 3 pos p1 对象实体1 对象实体2 对象实体3 对象实体4 0 1 2 3 对象实体p2 p2 (a) (b)
elementData = new Object[newCapacity];System.arraycopy(oldData,O,elementData,o,elementCount);1-public MyVector O(this(10) :1public MyVector(int initialCapacity)(elementData = new Object[initialCapacity];elementCount = O:1publicvoid add(intindex,Objectelement)（//在index处添加if (index>=elementCount + 1){thrownewArrayIndexOutOfBoundsException(index+">"+elementCount);1ensureCapacity(elementCount + 1):System.arraycopy(elementData, index, elementData, index +l, elementCount-index) ;:elementData[index] = element;elementCount++;public void add(Object element)f//在最后添加add(elementCount,element);1public void set(int index, Object element){//把index处元素置为elementif (index >= elementCount) (+">="+thrownewArrayIndexOutOfBoundsException(indexelementCount):1elementData[index] = element;1public Object get(int index) f//取index处元素if (index>= elementCount)thrownewArrayIndexOutOfBoundsException(index);return elementData[index]:1public int sizeO(return elementCount;14.3集合4.3.1集合的概念
} elementData = new Object[newCapacity]; System.arraycopy(oldData, 0, elementData, 0, elementCount); } } public MyVector(){ this(10); } public MyVector(int initialCapacity){ elementData = new Object[initialCapacity]; elementCount = 0; } public void add(int index,Object element){ //在 index 处添加 if (index >= elementCount + 1) { throw new ArrayIndexOutOfBoundsException(index + " > " + elementCount); } ensureCapacity(elementCount + 1); System.arraycopy(elementData, index, elementData, index + 1, elementCount - index); elementData[index] = element; elementCount++; } public void add(Object element){ //在最后添加 add(elementCount,element); } public void set(int index,Object element){ //把 index 处元素置为 element if (index >= elementCount) { throw new ArrayIndexOutOfBoundsException(index + " >= " + elementCount); } elementData[index] = element; } public Object get(int index){ //取 index 处元素 if (index >= elementCount) throw new ArrayIndexOutOfBoundsException(index); return elementData[index]; } public int size(){ return elementCount; } } 4.3 集合 4.3.1 集合的概念
（1）集合（Set）是具有某种相似特性的事物的全体。换一种说法，也可以说，集合是某种具有相同数据类型的数据元素全体。集合通常用一对花括号表示：mySet1=(1,3,5,7,9]mySet2=(1,3,5]mySet3=()（2）如果一个数据元素x在一个集合A中，则说数据元素x属于集合A：如果一个数据元素x不在一个集合A中，就说数据元素x不属于集合A。例如，数据元素3属于集合mySet1，因为数据元素3在集合mySet1中：数据元素4不属于集合mySet1，因为数据元素4不在集合mySet1中。（3）如果集合A中的所有数据元素都在集合B中，则说集合B包含集合A。（4）集合A和集合B相等当且仅当集合A包含集合B，且集合B也包含集合A。（5）集合的运算主要有三种：两个集合的并AUB、两个集合的交ANB、两个集合的差A-B。（6）没有一个数据元素的集合称做空集合4.3.2集合抽象数据类型数据集合数据元素集合可以表示为a0，al，a2，...，an-1)，每个数据元素的数据类型可以是任意的类类型。操作集合（1）添加add(obj)：在集合中添加数据元素obj。(2）删除remove（obj)：删除集合中的数据元素obj。（3）属于contain(obj)：数据元素obj是否属于集合。是则返回true，否则返回false。（4）包含include（otherSet）：当前对象集合是否包含集合otherSet。是则返回true，否则返回false。（5）相等eqauls（otherSet)：当前对象集合是否和集合otherSet相等。是则返回true，否则返回false。（6）数据元素个数size（)：返回集合中的数据元素个数。（7）集合空否isEmptyO)：若集合空返回true，否则返回false。4.3.3集合类集合的特点是数据元素无序且不重复。集合类可以基于向量类来实现。向量类MyVector要增加四个成员函数：（1）查找indexOf（element）：如果向量中存在数据元素element，则返回其下标，否则返回-1。（2）存在contain（element）：如果向量中存在数据元素element，则返回true：否则返回false。（3）删除数据元素remove（element）：删除向量中的数据元素element。（4）删除第index个数据元素remove（index）：删除向量中下标为index的数据元素。public int indexOf(Objectelement)(if (element == null) (for (inti=o;i<elementCount;i++)if (elementData[i] ==null)return i;小else f
（1）集合（Set）是具有某种相似特性的事物的全体。换一种说法，也可以说，集合是 某种具有相同数据类型的数据元素全体。 集合通常用一对花括号表示： mySet1={1,3,5,7,9} mySet2={1,3,5} mySet3={} （2）如果一个数据元素 x 在一个集合 A 中，则说数据元素 x 属于集合 A；如果一个数据 元素 x 不在一个集合 A 中，就说数据元素 x 不属于集合 A。 例如，数据元素 3 属于集合 mySet1，因为数据元素 3 在集合 mySet1 中;数据元素 4 不 属于集合 mySet1，因为数据元素 4 不在集合 mySet1 中。 （3）如果集合 A 中的所有数据元素都在集合 B 中，则说集合 B 包含集合 A。 （4）集合 A 和集合 B 相等当且仅当集合 A 包含集合 B ，且集合 B 也包含集合 A。 （5）集合的运算主要有三种：两个集合的并 A∪B、两个集合的交 A∩B、两个集合的差 A-B。 （6）没有一个数据元素的集合称做空集合 4.3.2 集合抽象数据类型 数据集合 数据元素集合可以表示为{a0, a1, a2, ., an-1}，每个数据元素的数据类型可以是 任意的类类型。 操作集合 （1）添加 add(obj)：在集合中添加数据元素 obj。 （2）删除 remove(obj)：删除集合中的数据元素 obj。 （3）属于 contain(obj)：数据元素 obj 是否属于集合。是则返回 true,否则返回 false。 （4）包含 include(otherSet)：当前对象集合是否包含集合 otherSet。是则返回 true, 否则返回 false。 （5）相等 eqauls(otherSet)：当前对象集合是否和集合 otherSet 相等。是则返回 true, 否则返回 false。 （6）数据元素个数 size()：返回集合中的数据元素个数。 （7）集合空否 isEmpty()：若集合空返回 true，否则返回 false。 4.3.3 集合类 集合的特点是数据元素无序且不重复。集合类可以基于向量类来实现。 向量类 MyVector 要增加四个成员函数： （1）查找 indexOf(element):如果向量中存在数据元素 element，则返回其下标，否则 返回-1。 （2）存在 contain(element):如果向量中存在数据元素 element，则返回 true；否则返 回 false。 （3）删除数据元素 remove(element):删除向量中的数据元素 element。 （4）删除第 index 个数据元素 remove(index):删除向量中下标为 index 的数据元素。 public int indexOf(Object element){ if (element == null) { for (int i = 0 ; i < elementCount ; i++) if (elementData[i] == null) return i; } else {
for(inti=o;i=elementCount){thrownewArrayIndexOutofBoundsException(index+">="+elementCount):1else if (indexo) (System.arraycopy(elementData, index +l,elementData,index,j);1elementCount--;elementData[elementCount]=null;public boolean contain(Object element)(return indexOf(element)>=0;1public void remove(Object element){int i = indexOf(element);if(i>=0) (remove(i) :11在向量类的基础上设计集合类MySetpublic class MySet(private MyVector values = new MyVector()://添加public void add(Object obj)(if(obj == null)return;if(values.indexOf (obj)<0)values.add(obj);1public void remove(Object obj)(values.remove(obj) :1public boolean contain(Object obj)(return values.contain(obj):1publicboolean include(Objectobj)
for (int i = 0 ; i = elementCount) { throw new ArrayIndexOutOfBoundsException(index + " >= " + elementCount); } else if (index 0) { System.arraycopy(elementData, index + 1, elementData, index, j); } elementCount-; elementData[elementCount] = null; } public boolean contain(Object element){ return indexOf(element) >= 0; } public void remove(Object element){ int i = indexOf(element); if (i >= 0) { remove(i); } } 在向量类的基础上设计集合类 MySet public class MySet{ private MyVector values = new MyVector(); public void add(Object obj){ //添加 if(obj == null) return; if(values.indexOf(obj) < 0) values.add(obj); } public void remove(Object obj){ values.remove(obj); } public boolean contain(Object obj){ return values.contain(obj); } public boolean include(Object obj){
if(obj instanceof MySet)fMySet set = (MySet)obj:int counter=0:while(counter0;【本讲课程的小结】这一次课我们回顾了Java中的数组功能，由于数组不能在程序运行过程中自动扩充，Java类库中定义了Vector类，为了更好的理解该类，我们设计了和该类功能类似的MyVector类，这个类中核心的就是ensureCapacity成员函数，这个函数的实现方法我们应该掌握。另外在MyVector类的基础上我们设计了一个集合类，注意集合不是一种线性结构，这个不要混淆。【本讲课程的作业】设计MySet类的两个集合的并、两个集合的交和两个集合的差成员函数
if(obj instanceof MySet){ MySet set = (MySet)obj; int counter=0; while(counter 0; } } 【本讲课程的小结】这一次课我们回顾了 Java 中的数组功能，由于数组不能在程序运行 过程中自动扩充，Java 类库中定义了 Vector 类，为了更好的理解该类，我们设计了和该 类功能类似的 MyVector 类，这个类中核心的就是 ensureCapacity 成员函数，这个函数的 实现方法我们应该掌握。另外在 MyVector 类的基础上我们设计了一个集合类，注意集合不 是一种线性结构，这个不要混淆。 【本讲课程的作业】 设计 MySet 类的两个集合的并、两个集合的交和两个集合的差成员函数