数据结构JAVA实验一
- 格式：pdf
- 大小：218.40 KB
- 文档页数：6
int b=reader.nextInt(); int c=reader.nextInt(); System.out.println("gcd("+a+","+b+","+c+")="+gcd(gcd(a,b),c)); System.out.println("zxg("+a+","+b+")="+zxg(a,b)); } public static int gcd(int a, int b) { if(b==0) return a; if(a<0) return gcd(-a, b); if(b<0) return gcd(a, -b); return gcd(b, a%b); } public static int zxg(int a, int b) { return a*b/gcd(a,b); } }
return true; }
}
判断对象数组元素是否已按升序排序
public class Zuoye1_2 { public static void main(String[] args) { Integer[] a=new Integer[10]; for(int i=0;i<10;i++){ a[i]=new Integer(i); } System.out.println(isSorted(a)); } public static boolean isSorted(Comparable[] table) { if (table==null) return false; for (int i=0; i<table.length-1; i++) if (table[i].compareTo(table[i+1])>0) return false; return true; }
（2） 数组逆置。
将一个已知数组中所有元素的次序颠倒为相反次序，求算法的时间复杂度和空间复杂度。
（3） 用递归算法求两个整数的最大公因数。
设有不全为 0 的两个整数 a 和 b,记 gcd(a,b)为他们的最大公因数，即同时能整除 a 和 b 的公 因数中的最大者。按照欧几里德（Euclid）的辗转相除法。gcd(a,b)具有如下性质：
用递归算法实现 gcd(a,b),并给下列调用： ①求两个整数 a，b 的最小公倍数；②求三个数 a,b,c 的最大公约数
3、 实验步骤与结果 （3 分）
(1)○1 审题。确定题目所要求的方法是实现判断整数数组(对象数组)是否已按 升序排序的功能。
○2 编程。创建一个主类，定义一个整数数组(对象数组)，利用输出语句输 出实现该方法得到的结果。定义 isSorted()方法，先判断输入数组是否为空，若 为空，则返回 flase；然后利用一个循环语句，逐个判断第 i 个元素是否比第 i+1 个元素大，若发现这种情况，则返回 false，否则为 true。
验证结果。输入一系列数据，验证结果是否符合程序要求。
图1
(2)○1 审题。确定题目所要求的方法是实现数组逆置。 ○2 编程。创建一个主类，给出 main 方法，定义一个数组，利用输出语句
输出该方法得到的结果。定义 yizhi()方法，判断数组是否为空，若为空，则返回 flase；然后利用一个循环语句，从第一个元素和最后一个元素的逆置开始实现数 组元素的逆置。
图3
4、 源码（2 分）
（1）判断整数数组元素是否已按升序排序
public class Zuoye1_1 { public static void main(String args[]){ int a[]={1,2,3,4}; System.out.print(isSorted(a)); } public static boolean isSorted(int[] table){ int min=table[0]; for(int i=1,temp=table.length;i<temp;i++){ if(min>table[i]) return false; min=table[i]; }
了解数据结构课程的目的，性质和主要内容，理解数据结构和算法的基本概念，熟悉算法的 描述方法，算法时间复杂度和空间复杂度的分析和计算方法。
2、 实验内容（2 分）
（1） 判断已按升序排序。
实现 isSorted()方法判断整数（对象）数组元素是否已按升序排序，生命如下： Public static boolean isSorted(int[] table) //判断整数数组是否已按升序排序 Public static boolean isSorted(Comparable[] table)// 判断对象数组是否已按升序排序
5、 结论与讨论（2 分）
通过本次实验的学习，我们总结了以下几点：①在编程时，编程的方案有 很多种，但要选择尽量使语句能够简便化的方案。②编程过程用到循环语句时， 要选择正确的且能便于我们更好地完成算法的语句。③递归策略只需少量的程序 就可描述出解题过程所需要的多次重复计算，大大地减少了程序的代码量。合理 利用递归，是完成算法的关键。④合理的分配给队员任务能使工作量和工作时间 大大缩减。
}
(3) 用递归算java.util.*; public class Zuoye3_2{ public static void main(String args[]) { Scanner reader=new Scanner(System.in); int a=reader.nextInt();
验证结果。输入一系列数据，验证结果是否符合程序要求。
图2 结果可知时间复杂度和空间复杂度均是 O（n） （3）○1 审题。确定题目所要求的方法是实现利用递归算法求两个整
数的最大公因数。 ○2 编程。创建一个主类，给出 main 方法，然后定义 3 个整型变量， 利用输出语句输出实现方法所得到的结果。定义 gcd(int a,int b)方法，先判断除 数是否为 0，若为 0，则返回被除数。判断 a，b 正负，取其绝对值，在 gcd(int a,int b)方法中返回 gcd(b,a%b); .验证结果。输入一系列数据，验证结果是否符合程序要求。
}
(2) 数组逆置
public class Zuoye2_1 { public static void main(String[] args) { int[] table={1,2,3,4,5,6,7,8}; int k=0; for(int i=0;i<table.length/2;i++){ k=table[table.length-i-1]; table[table.length-i-1]=table[i]; table[i]=k; } for(int i=0;i<table.length;i++) System.out.println(table[i]); }
班级
《数据结构（JAVA）》综合性、设计性实验成绩单
学号
姓名
开设时间：
实 验 实验一 算法设计与分析 题 目
成绩
教师签名
《数据结构（JAVA）》
实验报告
实验题目：
算法设计与分析
指导教师：
实验组长（姓名+学号）：
组员（姓名+学号）：
实验时间：
年月日
组长签名：
年 月日
一、实验报告撰写提纲
1、 实验目的（1 分）
