实验报告(1)-参考

《数据结构（JAVA）》综合性、设计性实验成绩单

开设时间：2011学年第一学期

班级 10信息管理x班 学号 1.201030560xxx 姓名 2. 3. 4. 5. 实验1 xxxxxxxx 1.xxx 2. 3. 4. 5. 实验题目成绩 教师签名

《数据结构（JAVA）》

实验报告

实验题目： 指导教师：杨春

实验组长（姓名+学号）： 组员（姓名+学号）：

实验时间： 2011年x月x日

组长签名：

2011年月日

一、实验报告撰写提纲： 1、

实验目的

了解数据结构课程的目的，性质和主要内容，理解数据结构和算法的基本概念，熟悉算法的描述方法，算法时间复杂度和空间复杂度的分析和计算方法。

2、

实验内容

（1） 判断已按升序排序。

实现isSorted()方法判断整数（对象）数组元素是否已按升序排序，生命如下： Public static booleanisSorted(int[] table) //判断整数数组是否已按升序排序 Public static booleanisSorted(Comparable[] table)//判断对象数组是否已按升序排序

（2） 数组逆置。

将一个已知数组中所有元素的次序颠倒为相反次序，求算法的时间复杂度和空间复杂度。

（3） 用递归算法求两个整数的最大公因数。

设有不全为0的两个整数a和b,记gcd(a,b)为他们的最大公因数，即同时能整除a和b的公因数中的最大者。按照欧几里德（Euclid）的辗转相除法。gcd(a,b)具有如下性质：

{ 3、

gcd(a,b)=gcd(b,a) gcd(a,b)=gcd(-a,b) gcd(a,0)=|a| gcd(a,b)=gcd(b,a%b),0<=a%b

用递归算法实现gcd(a,b),并给下列调用：

1.求两个整数a，b的最小公倍数；○2求三个数a,b,c的最大公约数 ○实验步骤与结果

（1）○1审题○2接着clipse下打代码，如下：

publicclass shiyan1_1 {

publicstaticbooleanisSorted(int[] table) //判断整数数组是否已按升序排序

publicstaticvoid main(String[] args) { }

int[] a={12,21,14,15,16,17,18,19}; System.out.println(isSorted(a));

{ //若已排序返回true，否则返回false if (table==null) returnfalse;

for (int i=0; itable[i+1]) returnfalse; returntrue; }

}

3点击运行，如果有错误要调试好 ○

结果：

当把第二个数改为13时返回：第二小步以同样的方法进行。

（2）○1审题○2写出代码并调试，关键代码如下：

for(int i=0;i

}

结果：可知时间复杂度和空间复杂度均是O（n） （3）方法同（1）,结果

k=table[table.length-i-1];

table[table.length-i-1]=table[i]; table[i]=k;

4、 源码

public static booleanisSorted(int[] table) {

if (table==null) return false;

for (int i=0; itable[i+1]) return false; return true;

}

public static booleanisSorted(Comparable[] table)

{ if (table==null)

return false;

for (int i=0; i0) return false; return true; }

（2）

publicclass shiyan1_2 {

publicstaticvoid main(String[] args) { }

}

int[] table={12,13,14,15,16,17,18,19}; int k=0;

for(int i=0;i

for(int i=0;i

System.out.println(table[i]); k=table[table.length-i-1];

table[table.length-i-1]=table[i]; table[i]=k;

（3）

publicclass shiyan1_3{

publicstaticvoid main(String args[]) {

int a=6,b=10,c=18;

System.out.println(\+a+\+b+\+c+\+gcd(gcd(a,b),c)); }

publicstaticintgcd(int a, int b) //返回a,b的最大公因数，递归方法 { if(b==0) return a; if(a<0)

returngcd(-a, b); if(b<0)

returngcd(a, -b); returngcd(b, a%b); } }

5、 结论与讨论

经讨论，我们绝对所有方法都使用静态方法，则可以直接使用类名来调用方法。这样可

以方便调用，则这几个类可以在以后使用时，直接作为工具方法来使用。

对于第三题的第二个小题，经过讨论以及上网搜索资料后，得出了一种方法。此方法为：先对这三个数两两求公约数，若所有公约数为1，则得出三个数互质，直接放回1 ；若不是，则用三个数中最小值来除另外两个数，若能整除，则为公约数，若不能，则把最小的数减一，在除另外两个数，直到可以整除，或那个数为1。

以方便调用，则这几个类可以在以后使用时，直接作为工具方法来使用。

对于第三题的第二个小题，经过讨论以及上网搜索资料后，得出了一种方法。此方法为：先对这三个数两两求公约数，若所有公约数为1，则得出三个数互质，直接放回1 ；若不是，则用三个数中最小值来除另外两个数，若能整除，则为公约数，若不能，则把最小的数减一，在除另外两个数，直到可以整除，或那个数为1。