20140925 数据结构(JAVA版)实验报告

实验报告

专 业： 课程名称： 数据结构(JAVA版) 班 级： 姓 名： 学 号： 指导教师：

实验报告

实验一：JAVA包、接口

实验目的： 1. 掌握package程序包的创建和使用； 2. 掌握接口的概念，学会使用接口的定义，继承接口，实现接口； 3. 掌握使用Eclipse上机调试的基本方法。 实验内容 一、 实验内容 1、构建一个Java Application。 2、定义一个名为Stu包，在这个包中定义一个实现显示学生的学号、姓名、性别和班级的Student类；然后定义另一个引用Stu包的类，在这个类中用Stu包中的Student类生成一个对象。 3、定义接口，继承接口，实现接口的实验。 二、 实训步骤 第一：新建一个名为Exp1的工程。 第二：包的创建与使用。 算法分析： 先在两个java源文件中分别定义了两个包，并且在第1个包中定义了一个MyClass1类，在第2个包中定义了一个MyClass2类。 在第三个java源文件的主类TestPackage中分别引用前面定义的两个包，并分别将MyClass1类和MyClass2类实例化。 1、在该工程中新建一个java源文件，并输入如下代码： package Mypackage; //定义包Mypackage public class MyClass1 { //定义类MyClass1 public void show() { System.out.println(\"这是类MyClass1\"); } } 2、在该工程中再新建一个java源文件，并输入如下代码： package Mypackage.Mypackage1; //定义包Mypackage.Mypackage1 public class MyClass2 { //定义类MyClass2 public void show(){ System.out.println(\"这是类MyClass2\"); } } 第 1 页 共 18页

实验报告

3、在该工程中再新建一个java源文件，并输入如下代码： import Mypackage.*; import Mypackage.Mypackage1.*; public class TestPackage { public static void main(String[] args) { //用包Mypackage中定义的类MyClass1生成对象 MyClass1 obj1=new MyClass1(); //用包Mypackage.Mypackage1中定义的类MyClass2生成对象 MyClass2 obj2=new MyClass2(); obj1.show() ; obj2.show(); } } 4、编译运行程序，查看运行结果。 第三：定义一个名为stu包，在这个包中定义一个实现显示学生的学号、姓名、性别和班级的Student类；然后定义另一个引用stu包的类，在这个类中用stu包中的Student类生成一个对象。 第四：定义接口，继承接口，实现接口的实验。 1、在Exp1工程下再新建一个java文件InterfaceDemo.java。 2、在该文件的适当位置上定义一个接口Runner。Runner包括一个常量ID=1，和一个抽象方法run()。 3、定义一个接口Animal，继承自Runner，在Animal里增加一个抽象方法breathe()。 4、定义一个类Fish，实现接口Animal。 5、在main方法中对Fish产生实例化对象，进行运用。 参考的代码： interface Runner { int ID=1; void run(); } interface Animal extends Runner { void breathe(); } class Fish implements Animal { public void run() { 第 2 页 共 18页

实验报告

System.out.println(\"fish is swimming\"); } void breathe()//这里会出现一个错误，必须在前面加上public，想一想，为什么？ { System.out.println(\"fish is bubbling\"); } } class InterfaceDemo { public static void main(String args[]) { Fish f1=new Fish(); f1.run(); f1.breathe(); f1.ID=2; //这里也出错，想一想，为什么？ } } 实验数据记录及分析（或程序及运行结果） 第 3 页 共 18页

实验报告

评语：

第 4 页 共 18页

实验报告

实验二：线性表

实验目的： 掌握线性表的基本操作：插入、删除、查找等运算在顺序存储结构和链接存储结构上的运算。 实验内容 设计一个不带头节点的单链表，要求： （1） 不带头节点单链表类的成员函数包括取数据元素个数、插入、删除、取数据元素； （2） 设计一个测试主函数，实际运行验证所设计不带头节点地单链表类个成员函数的正确性。  提示： 1. 参照带头节点的单链表类的设计； public class LinList implements List { Node head; Node current; int size; LinList(){ } public void index(int i) throws Exception{ if(i < -1 || i > size - 1){ } if(i == -1) return; current = head.next; int j = 0; throw new Exception(\"参数错误！\"); head = current = new Node(null); 第 5 页 共 18页

实验报告

} while((current != null) && j < i){ } current=current.next; j ++; public void insert(int i,Object obj) throws Exception{ } public Object delete(int i) throws Exception{ } if(size == 0){ } if(i < 0 || i > size - 1){ } index(i - 1); Object obj = current.next.getElement(); current.setNext(current.next.next); size --; return obj; throw new Exception(\"参数错误！\"); throw new Exception(\"链表已空无元素可删！\"); if(i < 0 || i > size){ } index(i - 1); current.setNext(new Node(obj,current.next)); size ++; throw new Exception(\"参数错误！\"); 第 6 页 共 18页

实验报告

public int size(){ } public boolean isEmpty(){ } public Object getData(int i) throws Exception{ if(i < -1 || i > size - 1){ } index(i); throw new Exception(\"参数错误！\"); return size == 0; return size; return current.getElement(); } 2. 主要考虑 （1） 第一个数据元素节点前插入和删除第一个数据元素节点时的情况； （2） 在其他位置插入和删除其他位置节点时的情况。 } 实验数据记录及分析（或程序及运行结果） 第 7 页 共 18页

实验报告

评语：

第 8 页 共 18页

实验报告

实验三：栈

实验目的： 1. 掌握栈的基本操作：初始化栈、判栈为空、出栈、入栈等运算； 2. 利用堆栈解决应用问题。 实验内容  实验内容与要求： 利用堆栈将中缀表达式转换为后缀表达式，要求： （1） 编写一个借助堆栈把中缀表达式转换为后缀表达式的函数。假设：  算数表达式是正确的；  算数表达式仅由加、减、乘、除、小括号运算符组成。  算数表达式中的数值在0-9之间。 （2） 设计一个测试主函数进行测试，并给出测试结果。  提示： 1. 中缀表达式转换为后缀表达式的算法步骤是： （1） 设置一个堆栈，初始时将栈顶元素置为#； （2） 顺序读入中缀表达式，当读到的单词为操作数是将其输出，接着读入下一个单词； （3） 令x1为保存当前栈顶运算符的变量，x2为保存中缀表达式中当前读到的运算符的变量。当顺序从中缀表达式中读入的单次为运算符时就赋给x2，然后比较x1和x2的优先级，若x1的优先级高于x2的优先级，将x1退栈并作为后缀表达式的一个单词输出，然后再接着比较新的栈顶运算符x1和x2的优先级；若x1的优先级低于x2的优先级，将x2的值进栈，接着读入下一个单词；若x1的优先级等于x2的优先级且x1为“（”x2为“）”时，将x1退栈，接着读入下一个单词；若x1的优先级等于x2的优先级且x1为“#”x2为“#”时，算法结束。 2. 应设计的方法 （1）先设计一个比较各运算符优先权的方法 第 9 页 共 18页

实验报告

public int precedence(char x1,char x2){ … } （2）设计将中缀表达式转换为后缀表达式的方法 public String convert(String midExpression){ …} （3）编写main方法将中缀表达式（例如：3*(5-4)+6/2）转换为后缀表达式3642/-5*+ 3. 语句提示： （1）压入堆栈操作的参数必须是类，所以要将字符包装成字符类seqstack.push(new Character('#')); （2）获取字符串某个位置的字符char getchar=midExpression.charAt(i); （3）获取到的栈顶元素是类，所以要利用charValue或得对应的字符 char topelement=((Character)seqstack.getTop()).charValue(); 实验数据记录及分析（或程序及运行结果） 第 10 页 共 18页

实验报告

评语：

第 11 页 共 18页

实验报告

实验四：串

实验目的： 1. 掌握串的基本操作：插入、删除、查找等运算； 2. 掌握String类和Stringbuffer类的区别。 实验内容： 对照MyString类的成员函数，设计完成MyStringBuffer类型应得所有成员函数，要求： （1） 连接、插入子串和删除子串成员函数改变原对象的串值； （2） 设计一个主函数进行测试。 实验数据记录及分析（或程序及运行结果） 第 12 页 共 18页

实验报告

评语： 日期： 年 月 日 第 13 页 共 18页

实验报告

实验五：二叉树

实验目的： 1． 2． 3． 4． 掌握二叉树的存储结构； 掌握二叉树的相关操作。 掌握递归思想； 掌握二叉树的遍历思想，从而解决实际问题。 实验内容 构建如下二叉树，基于结点类，编写算法求二叉树中叶结点的个数。并设计一个主函数进行测试。 实验数据记录及分析（或程序及运行结果） 第 14 页 共 18页

实验报告

评语：

第 15 页 共 18页

实验报告

实验六：图

实验目的： 1. 掌握图的存储结构； 2. 掌握图的相关操作，从而解决实际问题。 实验内容 求邻接矩阵图类的对象G中各结点的入度。 设G如下： 40 10 B 30 50 C A D 20 E  提示： 1．对于带权图，邻接矩阵第j列中所有0实验报告

实验数据记录及分析（或程序及运行结果） 第 17 页 共 18页

实验报告

评语：

第 18 页 共 18页