《数据结构与算法——C语言和Java语言描述 ppt及答案和其他资源05数组与矩阵》由会员分享，可在线阅读，更多相关《数据结构与算法——C语言和Java语言描述 ppt及答案和其他资源05数组与矩阵（41页珍藏版）》请在金锄头文库上搜索。
1、数组 集合 矩阵,2019年5月18日星期六,第五章,目录,Contents,数组的基本概念,动态数组（向量类）,集合的概念和集合类的设计,矩阵类的设计,特殊矩阵,稀疏矩阵, 数组定义, 实现机制, 抽象数据类型, JAVA语言支持的数组功能,01,PART,数组的基本概念, 数组定义,数组是n(n1)个相同数据类型的数据元素a0,a1,a2,.,an-1构成的占用一块地址连续的内存单元的有限序列。,数组中任意一个元素可以用该元素在数组中的位置来表示，数组元素的位置通常称作数组的下标。,数组, 数组线性表,数组要求其元素占用一块地址连续的内存单元空间，而线性表无此要求； 线性表的元素是逻辑意义
2、上不可再分的元素，而数组中的每个元素还可以是一个数组； 数组的操作主要是向某个下标的数组元素中存数据和取某个下标的数组元素，这和线性表的插入、删除操作不同。,不同点,相同点,它们都是若干个相同数据类型的数据元素a0,a1,a2,.,a0-1构成的有限序列。, 数组的定义,数组,数组符合线性结构的定义。 线性结构（包括线性表、堆栈、队列、串）的顺序存储结构实际就是使用数组来存储。可见，数组是其他数据结构实现顺序存储结构的基础，是软件设计中最基础的数据结构。, 数组的实现机制,()、一维数组（n个元素）中任一元素ai的内存单元地址 Loc(ai)=LOC(a)+i*k (0i n) ()、一个m行
3、n列的二维数组 LOC(aij)=LOC(a00)+(i*n+j)*k (0im，0jn),a的内存单元地址,每个元素所需的字节个数,a0的内存单元地址,每个元素所需的字节个数, 数组的实现机制,一个mn的二维数组可以看成是m行的一维数组，或者n列的一维数组。,数组抽象数据类型,数组的数据集合可以表示为a0, a1, a2, ., an-1，每个数据元素的数据类型可以是任意类类型或基本数据类型。,1）分配内存空间acclocate() 2）取数组长度getLength() 3）存数组元素set(i, x) 4） 取数组元素get(i),数据集合 操作集合,JAVA语言支持的数组功能,01,02
4、,03,int a = new int10;,int c = a.length;,a1 = 5;,04,int d = a1;,JAVA语言支持的数组功能,Java语言可以定义对象数组。 public class Position private int x; private int y; public Position() x = y = 0; 则可以定义如下4个对象的对象数组pos： Position pos = new Position4; 要注意的是，对于对象数组来说，其中的每个数组元素都需要通过new运算符单独创建。例如： Position pos = new Position4;
5、for(int i = 1; i 4; i+) pos i = new Position ();,对象数组, 向量类定义, 程序实例, 设计说明,02,PART,动态数组（向量类）,向量类定义,向量类,Java语言只直接支持上述基本的数组操作。如果程序开始时定义的数组长度为10，且数组中已经存放了若干数据元素，要在程序运行过程中扩充数组长度为20，且把数组中原先存放的数据元素原样保存，则系统不提供直接支持，需要应用程序自己实现。 向量类Vector扩充了数组的功能，提供了自动扩充数组长度、且把数组中原先存放的数据元素原样保存的功能。Vector类在java.util包中。 这里我们设计一个和V
6、ector类功能类同的MyVector类。,程序实例 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 (
7、newCapacity minCapacity) newCapacity = minCapacity; elementData = new ObjectnewCapacity; System.arraycopy(oldData, 0, elementData, 0, elementCount); public MyVector()/构造函数 this(10); public MyVector(int initialCapacity) /构造函数 elementData = new ObjectinitialCapacity; elementCount = 0; ,public void add
8、(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); elementDataindex = element; elementCount+; p
9、ublic void add(Object element) /在最后添加 add(elementCount,element); public void set(int index,Object element) /重置元素 if (index = elementCount) throw new ArrayIndexOutOfBoundsException(index + “ = “ + elementCount); elementDataindex = element; public Object get(int index) /取index处元素 if (index = elementCo
10、unt) throw new ArrayIndexOutOfBoundsException(index); return elementDataindex; public int size() /取元素个数 return elementCount; ,设计说明,（1）MyVector类只支持对象数组，不支持基本数据类型数组。基本数据类型（如int）要用相应的包装类（如Integer类）包装。 （2）MyVector类提供的自动扩充数组长度的功能，是由成员函数ensureCapacity(minCapacity)实现的。 实现过程是：首先，保存原数组长度和原数组元素；然后，让新数组长度newCa
11、pacity为原数组长度的2倍或参数minCapacity的较大者；最后，重新创建长度为newCapacity的数组，并把原来的数组元素复制到新数组的开始位置。 （3）添加成员函数add(index,element)的实现过程：首先，用elementCount+1为参数调用ensureCapacity()成员函数，确保一定有足够的数组空间添加新的数据元素；然后，调用System类的数组拷贝成员函数arraycopy()，把数组elementData中从下标index至最后共计elementCount-index个数组元素后移一个位置。最后，把数据元素element添加到下标为index的数组中
12、。,MyVector类 ensureCapacity(minCapacity),设计说明,（1）MyVector类只支持对象数组，不支持基本数据类型数组。基本数据类型（如int）要用相应的包装类（如Integer类）包装。 （2）MyVector类提供的自动扩充数组长度的功能，是由成员函数ensureCapacity(minCapacity)实现的。 实现过程是：首先，保存原数组长度和原数组元素；然后，让新数组长度newCapacity为原数组长度的2倍或参数minCapacity的较大者；最后，重新创建长度为newCapacity的数组，并把原来的数组元素复制到新数组的开始位置。 （3）添加
13、成员函数add(index,element)的实现过程：首先，用elementCount+1为参数调用ensureCapacity()成员函数，确保一定有足够的数组空间添加新的数据元素；然后，调用System类的数组拷贝成员函数arraycopy()，把数组elementData中从下标index至最后共计elementCount-index个数组元素后移一个位置。最后，把数据元素element添加到下标为index的数组中。,MyVector类 add(index,element), 集合的概念, 集合数据抽象类型, 集合类,03,PART,集合的概念和集合类的设计,集合的概念,集合,集合（
14、Set）是具有某种相似特性的事物的全体。换一种说法，也可以说，集合是某种具有相同数据类型的数据元素全体。 集合的一个重要特点是其中的数据元素无序且不重复。 集合通常用一对花括号表示。例如，如下都是集合的例子： mySet1 = true, false mySet2 = 1, 3, 5, 7, 9 mySet3 = 5, 3, 1, 9, 7 mySet4 = 1, 3, 5, 7 mySet5 = 如果一个数据元素x在一个集合A中，则说数据元素x属于集合A； 如果一个数据元素x不在一个集合A中，就说数据元素x不属于集合A。,集合的概念,集合,如果集合A中的所有数据元素都在集合B中，则说集合B包
15、含集合A。 集合A和集合B相等当且仅当集合A包含集合B，且集合B也包含集合A。 没有一个数据元素的集合称做空集合。 集合的运算主要有三种： 两个集合的并AB 两个集合的交AB 两个集合的差A-B AB是一个集合，其数据元素或者属于集合A，或者属于集合B（或者同时属于集合A和集合B）。 AB是一个集合，其数据元素同时属于集合A和集合B。 A-B是一个集合，其数据元素由属于集合A而不属于集合B的所有数据元素组成。,集合数据抽象类型,数据 集合,数据元素集合可以表示为a0, a1, a2, , an-1，数据类型可是任意的类型。 操作集合： （1）添加add(obj)：在集合中添加数据元素obj。
16、（2）删除remove(obj)：删除集合中的数据元素obj。 （3）属于contain(obj)：数据元素obj是否属于集合。 （4）包含include(otherSet)：当前对象集合是否包含集合otherSet。 （5）相等eqauls(otherSet)：当前对象集合是否和集合otherSet相等。 （6）数据元素个数size()：返回集合中的数据元素个数。 （7）集合空否isEmpty()： 另外，还有前面讨论过的集合的并、交、差运算。,集合类,集合类,集合的特点是数据元素无序且不重复。 集合类既可以基于向量类来实现，也可以用其他方法实现。常用的另一种实现方法是基于哈希表来实现。这里讨论基于向量类的集合类实现
