Java编程导论实验报告.doc

院 系： 计算机科学学院 专 业： 软件工程 年 级： 课程名称： Java编程导论 学 号： 姓 名： 指导教师： 2014年 6 月 18 日年级2012班号  学号 专业  姓名 实验名称 线性表运算实验类型设计型综合型创新型实验目的或要求一、 实验目的二、 实验题目练习5.36：给出dataStructures.list.MyArrayList的length()、isEmpty()、getAt(int index)、index()f(int element)和setint index,int element()方法的实现。实验原理（算法流程）三：源代码如下：  package dataStructures.list;/* * ArrayList.java. * LinearList接口的可变长顺序存储实现。 * author yqj2065 * version 2011.11 */public class MyArrayList implements LinearList private int elements; /-/ / 创建一个可变长顺序存储结构ArrayList对象。/ /-/ public MyArrayList() /空的数组列表。即elementsnull /* * 创建元素个数n的数组列表。每个结点保存一个int随机值。 * param size : 数组列表的元素个数.size大于0。size为0请使用无参数构造器。 */ public MyArrayList(int size) if(size <= 0) throw new IllegalArgumentException(); assert size>0; elements = new intsize; for(int i =0; i < elements.length; i+) elementsi= (int)(Math.random()*100); /* * 打印本数组列表的各元素 * toString() */ public void print() System.out.println("本数组列表包含元素: "); int index = 0; for(int e : elements ) System.out.print(""+e + ""); index+; if( index<elements.length )System.out.print(" "); System.out.println(); /end print() /* * 延迟方法的实现 * */ /* * 返回线性表的长度，即元素的个数。 * size() */ Override public int length() return elements=null? 0 : elements.length; /* * 判断线性表是否为空 */ Override public boolean isEmpty() /判断线性表是否为空 return elements=null; /boolean isFull(); /判断线性表是否已满 /* * 查找功能.是否包含给定数据元素. * */ Override public boolean contains(int element) int index = 0; for(int x: elements) if(x = element) return true; return false; /* * 返回基于0的index位置的数据元素。 * get() * param index : 单向链表的第index个元素。取值0length()-1. * return 指定位置index的数据元素 */ Override public int getAt(int index) return elementsindex; /* * 对于数据元素element，返回它首次出现的位置。如果没有这样的元素，则返回 -1。 */ Override public int indexOf(int element) int index = 0; for(int x: elements) if(x = element) return index; index+; return -1; /按照基于0的指定位置index，将指定位置设置数据元素 Override public void set(int index,int element) elementsindex = element; /* * 插入和删除 */ /* * 尾插入 * 在表的尾部添加一个数据元素 * add()、append() */ Override public void add(int element) if(elements=null) elements = new intelement; return; int newArr = new intelements.length+1 ; int index = 0; for(int x: elements) newArrindex+ = x; newArrnewArr.length-1 = element; elements = newArr; /* * 按照基于0的指定位置index，将数据元素插入指定位置 * param index : 将插入的位置。取值0length()-1. * param element : 将保存元素值。 */ Override public void add(int index, int element) if(index<0 | index >= elements.length) throw new IllegalArgumentException(); int newArr = new intelements.length+1 ; /1、传统for /* for(int i=0 ; i< newArr.length; i+) if(i<index) newArri=elementsi; else if(i=index) newArri=element; else newArri=elementsi-1; */ /2、传统for之 ? : /* for(int i=0 ; i< newArr.length; i+) newArri = (i<index) ? elementsi: (i=index)? element:elementsi-1; */ /3、for each,每次循环x必须作为赋值右值，被使用一次 int i = 0; /* for(int x: elements) if(i<index) newArri =x; else if (i = index) newArri =element; newArri+1 =x; else newArri+1 =x; i+; */ /4、+i for(int x: elements) if (i = index) newArri =element; newArr+i =x; else newArri =x; i+; elements = newArr; /* * 删除指定位置的结点 */ public void remove(int index) if(index<0 | index >= elements.length) throw new IllegalArgumentException(); int newArr = new intelements.length-1 ; for(int i=0 ; i< newArr.length; i+) newArri = i< index?elementsi:elementsi+1; elements = newArr; /void remove(int element); /删除首次出现的给定数据元素 Override public void clear() elements = null; /§迭代器 添加的代码/ /public Iterator iterator() Override public java.util.Iterator<Integer> iterator() return null; 执行结果如下： 执行前： 知识点总结： 1、单向链表与静态数组 链表的特性是在中间任意位置添加删除元素的都非常的快，不需要移动其它的元素。通常链表每一个元素都要保存一个指向下一个元素的指针（单链表）。双链表的化每个元素即要保存到下一个元素的指针，还要保存一个上一个元素的指针。循环链表则把最后一个元素中保存下一个元素指针指向第一个元素。 数组是一组具有相同类型和名称的变量的集合。这些变量称为数组的元素,每个数组元素都有一个编号,这个编号叫做下标,我们可以通过下标来区别这些元素。数组元素的个数有时也称之为数组的长度。 相同点;链表和数组都可用来存放指定的数据类型。不同点：（1）从逻辑结构来看 数组必须事先定义固定的长度（元素个数），不能适应数据动态地增减的情况。当数据增加时，可能超出原先定义的元素个数，出现溢出现象；当数据减少时，造成内存浪费。数组中插入、删除数据项时，需要移动其它数据项。 链表动态地进行存储分配，可以适应数据动态地增减的情况，且可以方便地插入、删除数据项。（2） 从内存存储来看 . (静态)数组从栈中分配空间, 对于程序员方便快速,但是自由度小 . 链表从堆中分配空间, 自由度大但是申请管理比较麻烦. 2、双向链表和动态数组。动态数组就是一个长度可以根据实际情况改变的数组。 双向链表存放的除了本来的数据外，还有其前驱和后驱结点。在动态数组中，如果我们要在某一个位置添加或者删除一个元素，剩下的每个元素都要相应地往前或往后移动。如果该动态数组中的元素很多，那么，每当我们添加或删除一个元素后，需要移动的元素就非常多，因此，效率就比较低。双向链表效率较高：如果我们要在某一个位置添加一个元素，例如，要在1,3之间插入5。本来1是指向3，3也指向1的。现在，只需要将5放到1和3之间，同时让5向前指向1，向后指向3，并且让1从3指向5，让3从1指向5就可以了。如果该链表中元素非常多，我们只需做这个操作就可以了，并不需要移动剩下的元素。所以，双向链表在添加和删除元素上的效率要比动态数组高：java中系统同时提供了双向链表（LinkedList）和动态数组（ArrayList）两种机制。并且，Java中有一个叫ListIterator的迭代器。该迭代器不仅可以向后迭代元素，还能向前迭代，而且还有add()来在某一位置添加元素，十分方便。不过就查找效率而言，是动态数组的效率比双向链表的效率高，因为只需提供元素的下标即可。 3、数组的定义与初始化： 一 维 数 组 的 定 义 方 式 为 :type arrayName;其 中 类 型 (type)可 以 为 Java中 任 意 的 数 据 类 型 ,包 括 简 单类 型 和 组 合 类 型 (见 2.1),数 组 名arrayName为 一 个 合 法 的 标 识 符 ,指 明 该 变 量 是 一 个 数组 类 型 变 量 。 例 如 :int intArray;声 明 了 一 个 整 型 数 组 ,数 组 中 的 每 个 元 素 为 整 型 数 据。 与 C 、 C+不 同 ,Java在 数组 的 定义 中 并 不 为 数 组 元 素 分 配 内 存 ,因 此 中 不 用 指 出 数组 中 元 素 的 个 数 ,即 数 组 长度 ,而 且 对 于如 上 定 义 的 一 个 数 组 是 不 能 访 问 它 的 任 何 元 素 的 。我 们 必 须 为 它 分 配 内 存 空 间 ,这 时 要 用到 运 算 符 new,其 格 式 如 下 :arrayName = new typearraySize;其 中 ,arraySize指 明 数 组 的 长 度 。 如 :intArray = new int3;为 一 个 整 型 数 组 分 配 3个 int型 整 数 所 占 据 的 内 存 空 间。通 常 ,这 两 部 分 可 以 合 在 一 起 ,格 式 如 下 :type arrayName = new type arraySize;例 如 :int intArray = new int3;二 、 一 维 数 组 元 素 的 引 用定 义 了 一 个 数 组 ,并 用 运 算 符 new为 它 分 配 了 内 存 空 间后 ,就 可 以 引 用 数 组 中 的 每一 个元 素 了 。 数 组 元 素 的 引 用 方 式 为 :arrayNameindex其 中 :index为 数 组 下 标 ,它 可 以 为 整 型 常 数 或 表 达 式 。如 a3 ,bi(i为 整 型 ),c6*I等 。 下 标从 0开 始 ,一 直 到 数 组 的 长 度 减 1。 对 于 上 面 例 子 中 的 in- tArray数 组 来 说 ,它 有 3个 元 素 ,分 别 为 :intArray0,intArray1, intArray2。 注 意 :没 有 intArray3。另 外 ,与 C、 C+中 不 同 ,Java对 数 组 元 素 要 进 行 越 界 检 查以 保 证 安 全 性 。 同 时 ,对于 每 个数 组 都 有 一 个 属 性 length指 明 它 的 长 度 ,例 如 :intArray.length指 明 数 组 intArray的 长 度 。三 、 一 维 数 组 的 初 始 化对数组元素可以按照上述的例子进行赋值，也可以在定义数组的同时进行初始化 。例 如 :int a = 1,2,3,4,5;用 逗 号 (,)分 隔 数 组 的 各 个 元 素 ,系 统 自 动 为 数 组 分 配一 定 的 空 间 。与 C中 不 同 ,这 时 Java不 要 求 数 组 为 静 态 (static)。java中数组的使用：1. Java中的数组作为对象带来的好处1.1 越界检查1.2 length field：与传统的C+中的数组相比，length字段可以方便的得到数组的大小；但要注意，仅仅可以得到数组的大小，不能得到数组中实际包含多少个元素，因为length 只会告诉我们最多可将多少元素置入那个数组。1.3 初始化：对象数组在创建之初会自动初始化成null，由原始数据类型构成的数组会自动初始化成零（针对数值类型），(Char)0 （针对字符类型）或者false （针对布尔类型）。1.4 数组作为返回值：首先，既然数组是对象，那么就可以把这个对象作为返回值；而且，不必担心那个数组的是否可用只要需要它就会自动存在而且垃圾收集器会在我们完成后自动将其清除2. 通用算法2.1 在java.util 中的Arrays 数组类容纳着一系列静态方法可简化我们对数组的操作，总共有四个函数。equals()用于比较两个数组是否相等、fill()可将一个值填入数组、sort()可对数组排序、而binarySearch()用于在排好序的数组中查找一个元素。所有这些方法都已为全部原始数据类型及对象重载使用。除此以外还有一个asList()方法可用它获取任意数组然后把数组转变成一个List 容器。2.2 sort和binarySearch的使用：在Java 2 中有两个办法可提供比较功能。第一个办法是用自然比较方法,这是通过实现java.lang.Comparable 接口来实现。Java 2 提供的第二个办法来进行对象的比较，单独创建一个类实现名为Comparator 的一个接口。接口提供了两个方法分别是compare()和equals() 。不过除非考虑到一些特殊的性能方面的因素，否则我们用不着实现equals() ，因为每次创建一个类的时候它都会默认从Object 继承，而Object 已经有了一个equals()。Comparator可以作为sort和binarySearch方法的参数。3. 需要注意的问题3.1 Java中的数组中既可以存储基本的值类型，也可以存储对象。对象数组和原始数据类型数组在使用方法上几乎是完全一致的，唯一的差别在于对象数组容纳的是引用而原始数据类型数组容纳的是具体的数值。这一点要特别注意，在讨论关于数组的问题时，一定要先确定数组中存储的是基本值类型还是对象。特别是在调试程序时，要注意这方面。例如：Arrays提供了一个fill()方法将一个值复制到一个位置，如果是对象数组则将引用复制到每一个位置。Java 标准库提供了一个静态方法名为System.arraycopy() 专门用于数组的复制它复制数组的速度比自己亲自动手写一个for 循环来复制快得多System.arraycopy()已进行了重载可对所有类型进行控制。无论原始数据类型数组还是对象数组我们都可对它们进行复制。但是假如复制的对象数组，那么真正复制的只是引用对象本身可不会复制。3.2 为什么使用数组而不使用ArrayList等容器类？效率和类型。3.2.1 效率：对于Java 来说要想保存和随机访问一系列对象实际是对象引用效率最高的方法莫过于数组。3.2.2 类型：Java标准库中的容器类都把对象当作没有具体类型那样对待，换言之它们将其当作Object 类型处理。Object 类型是Java 中所有类的根类，从某种角度看这种处理方法是非常合理的，我们只需构建一个容器然后所有Java 对象都可进入那个容器。原始数据类型除外，可用Java 的基类型封装器类将其作为常数置入容器或自建一个类把它们封装到里面当作可变值进行对待。这再一次体现出数组相较于普通容器的优越性，创建一个数组时可让它容纳一种特定的类型。这意味着可进行编译时间的类型检查防范自己设置了错误的类型或者错误地提取了一种类型，而不是运行时的Exception。 总结：在你想容纳一组对象的时候第一个也是最有效的一个选择便是数组。数组的一些使用技巧：1关于数组的特点 1）在Java中，无论使用数组或容器，都有边界检查。如果越界操作就会得到一个RuntimeException异常。 2）数组只能保存特定类型。数组可以保存基本类型，容器则不能。容器不以具体的类型来处理对象，它们将所有对象都按Object类型处理。 3）容器类只能保存对象的引用。而数组既可以创建为直接保存基本类型，也可以保存对象的引用。在容器中可以使用包装类，如Integer、Double等来实现保存基本数据类型值。 4）对象数组和基本类型数组在使用上几乎是相同的；唯一的区别是对象数组保存的是引用，基本类型数组保存基本类型的值。2关于数组定义1）数组在定义时，不能分配空间。只有定义完后，可以给数组分配空间。int num; num=new int3; 或 int num=new int3;注意 int num=new int1,2,3; /ok int num=new int31,2,3; /error; 2）可以这样定义二维数组。int num; /or num=new int3;num0=new int5; num1=new int3; num2=new int2;3）二维数组赋初值。int num=new int1,2,3,4,5,5; /error int num=new int1,2,3,4,5,5; /ok int num=new int21,2,3,4,5,5; /error int num=1,2,3,4,5,6; /ok3关于数组初始化对象数组在创建之初会自动初始化成null，由原始数据类型构成的数组会自动初始化成零（针对数值类型），(Char)0 （针对字符类型）或者false （针对布尔类型）。4数组有关引用的问题 int a1 = 1, 2, 3, 4, 5 ;int a2; a2 = a1;/这里只是复制了一个引用 看以下代码：public class Arrays public static void main(String args) int a1 = 1, 2, 3, 4, 5 ;for (int i = 0; i < a1.length; i+)System.out.println("a1" + i + " = " + a1i); int a2; a2 = a1; for (int i = 0; i < a2.length; i+) a2i+;System.out.println("-after change a2-");for (int i = 0; i < a1.length; i+)System.out.println("a1" + i + " = " + a1i); System.out.println("-after change a20-");a20 = 333; System.out.println("a20=" + a20);System.out.println("a10=" + a10); System.out.println("- a2-"); for (int i = 0; i < a2.length; i+) System.out.println("a2" + i + " = " + a2i); 结果： a10 = 1 a11 = 2 a12 = 3 a13 = 4 a14 = 5 -after change a2- a10 = 2 a11 = 3 a12 = 4 a13 = 5 a14 = 6 -after change a20- a20=333 a10=333 - a2- a20 = 333 a21 = 3 a22 = 4 a23 = 5 a24 = 6 数组a1和a2始终在操作同一个对象。 5关于数组的相关操作1）在Java中，所有的数组都有一个缺省的属性length，用于获取数组中元素的个数。2）数组的复制：System.arraycopy()。3）数组的排序：Arrays.sort()。4）在已排序的数组中查找某个元素：Arrays.binarySearch()。 6关于数组的排序操作 1）对象数组排序，必须实现Comparable接口。 import java.util.Arrays; class Student implements Comparable int num; String name; Student(int num, String name) this.num = num; this.name = name; public String toString()/ 重写toString()方法，以便main:System.out.println(ssi); return "number=" + num + "," + "name=" + name; public int compareTo(Object o) Student s = (Student) o; return num > s.num ? 1 : (num = s.num ? 0 : -1); class ArrayTest public static void main(String args) Student ss = new Student new Student(1, "zhangsan"), new Student(2, "lisi"), new Student(3, "wangwu") ; Arrays.sort(ss); for (int i = 0; i < ss.length; i+) System.out.println(ssi); 结果： number=1,name=zhangsan number=2,name=lisi number=3,name=wangwu2）以num为第一关键字，name为第二关键字排序 import java.util.Arrays; class Student implements Comparable int num; String name; Student(int num, String name) this.num = num; this.name = name; public String toString() return "number=" + num + "," + "name=" + name; public int compareTo(Object o) Student s = (Student) o; int result = num > s.num ? 1 : (num = s.num ? 0 : -1); if (0 = result) result = pareTo(s.name); return result; class ArrayTest public static void main(String args) Student ss = new Student new Student(1, "zhangsan"), new Student(2, "lisi"), new Student(3, "wangwu"), new Student(3, "mybole") ; Arrays.sort(ss); for (int i = 0; i < ss.length; i+) System.out.println(ssi); 结果： number=1,name=zhangsan number=2,name=lisi number=3,name=mybole number=3,name=wangwu7关于java.util.Arrays1）java.util.Class Arrayss architecture java.lang.Object | +-java.util.Arrays2）说明这个类提供的基本上都是静态方法，用户进行数组操作，binarySearch()：数组中特定元素的寻找，equals()：比较两个数组是否相等（在相同位置上的元素是否相等）,fill()：数组填充，sort()：数组排序          组内分工（可选）实验结果分析及心得体会成绩评定教师签名： 年 月 日备注：源代码附后，源代码要求有注释说明