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;
}
| 步骤 | 耗时 | 百分比 |
|---|---|---|
| 需求分析 | 90min | 16.7% |
| 代码实现 | 240min | 44.4% |
| 测试 | 150min | 27.8% |
| 分析总结 | 60min | 11.1% |