20162307 实验一 线性表的应用，实现和分析

北京电子科技学院（BESTI）

实 验 报 告

课程：程序设计与数据结构

班级：1623

姓名：张韵琪

学号：20162307

指导教师：娄佳鹏老师、王志强老师

实验日期：2017年9月22号

实验密级：非密级

实验时间：一周

必修/选修：必修

实验名称：线性表的应用，实现和分析

实验仪器：电脑

实验目的与要求：

目的：

学习线性表的应用，实现和分析

要求：

1.没有Linux基础的同学建议先学习《Linux基础入门（新版）》《Vim编辑器》 课程 2.完成实验、撰写实验报告，实验报告以博客方式发表在博客园，注意实验报告重点是运行结果，遇到的问题(工具查找，安装，使用，程序的编辑，调试，运行等)、解决办法（空洞的方法如“查网络”、“问同学”、“看书”等一律得0分）以及分析（从中可以得到什么启示，有什么收获，教训等）。报告可以参考范飞龙老师的指导 3. 严禁抄袭，有该行为者实验成绩归零，并附加其他惩罚措施。

实验内容、步骤

实验内容1

ArrayList和LinkedList测试： 查看ArrayList和LinkedList的Java API帮助文档，参考http://www.cnblogs.com/rocedu/p/4837092.html 用Junit对ArrayList和LinkedList的方法进行测试，要尽量覆盖正常情况，异常情况，边界情况

提交单元测试运行截图，要全屏，包含学号信息

实验步骤1

1.按照娄老师所给的博客， 博客链接：http://www.cnblogs.com/rocedu/p/4837092.html 2.用Junit对ArrayList和LinkedList的方法进行测试

实验结果1

实验内容2

分别用Java的ArrayList和LinkedList实现有序线性表的合并： aList，bList都是非递减线性表，合并后也是非递减 public static List<？ extends Comparable> mergeSortedList(List<？ extends Comparable> aList, List<？ extends Comparable> bList) 测试mergeSortedList的正确性,要尽量覆盖正常情况，异常情况，边界情况，提交测试代码运行截图，包含学号信息 课下把代码推送到代码托管平台

实验步骤2

1.上课的时候老师讲了如何合并的答题思路，试着写 2.调试代码，不成功，参考同学的代码进行学习 3.mergeSortedList代码： package Experiment1; /** * Created by zhangyunqi on 2017/9/26. */ import java.util.ArrayList; import java.util.List; public class MergeList { private static List list = new ArrayList(); public static List<? extends Comparable> mergeSortedList(List<? extends Comparable> aList, List<? extends Comparable> bList){ if(aList.isEmpty() && bList.isEmpty()) { return list; }else if(!aList.isEmpty() && bList.isEmpty()) { list.addAll(aList); }else if(aList.isEmpty() && !bList.isEmpty()) { list.addAll(bList); }else if(aList.get(0).compareTo(bList.get(0))==0) { list.add(aList.remove(0)); list.add(bList.remove(0)); mergeSortedList(aList,bList); }else if(aList.get(0).compareTo(bList.get(0))>0) { list.add(bList.remove(0)); mergeSortedList(aList,bList); }else if(aList.get(0).compareTo(bList.get(0))<0) { list.add(aList.remove(0)); mergeSortedList(aList,bList); } return list; } }

实验结果2

实验内容3

参考Java Foundation 3rd 第15.6节，用数组实现线性表List 用JUnit或自己编写驱动类对自己实现的ArrayList进行测试，提交测试代码运行截图，要全屏，包含自己的学号信息 课下把代码推送到代码托管平台

实验步骤3

ArrayList代码：

package Experiment1; /** * Created by zhangyunqi on 2017/9/25. */ import java.util.*; public class ArrayListDemo { private Object[] obj; private int num; public boolean isEmpty(int o) { if (obj == null) { return true; } return false; } public void add(int index, Object element) { Object ob = null; for (int i = 0; i < obj.length; i++) { if (i == index) { ob = obj[i]; obj[i] = element; for (int j = i + 1; j < obj.length + 1; j++) { obj[j + 1] = obj[j]; obj[j] = ob; } } } } public boolean remove(Object o) { for (int i = 0; i < obj.length; i++) { if (obj[i].equals ( o )) { String str = obj.toString (); StringBuilder bd = new StringBuilder ( str ); bd.deleteCharAt ( i ); return true; } } return false; } public Object remove(int index) { for (int i = 0; i < obj.length; i++) { if (i == index) { StringBuilder bb = new StringBuilder ( obj.toString () ); bb.deleteCharAt ( i ); } } return obj; } }

实验结果3

实验内容4

参考Java Foundation 3rd 第15.7节，用链表实现线性表List 用JUnit或自己编写驱动类对自己实现的LinkedList进行测试，提交测试代码运行截图，要全屏，包含自己的学号信息 课下把代码推送到代码托管平台

实验步骤4

package Experiment1; import org.junit.jupiter.api.Test; import static org.junit.jupiter.api.Assertions.*; import java.util.ArrayList; /** * Created by zhangyunqi on 2017/9/26. */ class LinkedListDemoTest1 { ArrayList list = new ArrayList (); @Test void isEmpty() { assertEquals ( true, list.isEmpty () ); list.add ( "07shiyan4" ); assertEquals ( false, list.isEmpty () ); list.remove ( "07shiyan4" ); assertEquals ( true, list.isEmpty () ); list.add ( "07shiyan4" ); } @Test void add() { list.add ( "20162307shiyan4" ); assertEquals ( "20162307shiyan4", list.get (0) ); } @Test void contains() { list.add ( 123456); assertEquals ( true, list.contains ( 123456) ); } }

实验结果4:

实验内容5

参考http://www.cnblogs.com/rocedu/p/7483915.html对Java的ArrayList，LinkedList按要求进行源码分析，并在实验报告中体现分析结果

实验结果5

LinkedList： add：

public boolean add(E e) { addBefore(e, header); return true; }

contains：

public boolean contains(Object o) { return indexOf(o) != -1; } public int indexOf(Object o) { int index = 0; if (o==null) { for (Entry e = header.next; e != header; e = e.next) { if (e.element==null) return index; index++; } } else { for (Entry e = header.next; e != header; e = e.next) { if (o.equals(e.element)) return index; index++; } } return -1;

}

remove：

public boolean remove(Object o) { if (o==null) { for (Entry<E> e = header.next; e != header; e = e.next) { if (e.element==null) { remove(e); return true; } } } else { for (Entry<E> e = header.next; e != header; e = e.next) { if (o.equals(e.element)) { remove(e); return true; } } } return false; }

ArrayList： add：

public boolean add(E e) { ensureCapacity(size + 1); elementData[size++] = e; return true; }

isEmpty：

public boolean isEmpty(int o) { if (obj == null) { return true; } return false; }

remove：

public boolean remove(Object o) { if (o == null) { for (int index = 0; index < size; index++) if (elementData[index] == null) { fastRemove(index); return true; } } else { for (int index = 0; index < size; index++) if (o.equals(elementData[index])) { fastRemove(index); return true; } } return false; } 步骤耗时百分比需求分析90min16.7%代码实现240min44.4%测试150min27.8%分析总结60min11.1%

此次实验链接

我的链接

转载于:https://www.cnblogs.com/Tiffany23/p/7615974.html

相关资源：线性表的基本操作实现及其应用实验报告