第二章 数组  Java 中数组的基础知识  将程序划分成类  类接口  有序数组的Java 代码  对数  存储对象  大O表示法  为什么不用数组表示一切 本章重点本章重点本章重点本章重点 Array 专题专题专题专题Applet 假设你正在训练少儿棒球联盟的队伍,并希望知道 队中哪些运动员出现在训练场上,就需要在笔记本 电脑里存有一个出勤记录程序、它可以维护参加训 练的运动员的数据库。需要用一个简单的数据结构 对这些数据进行保存,还可能要执行以下这些操作:  当运动员到场时,向数据结构中插入—条记录。  通过在结构中查找运动员的号码来查看某个运动员 是否出席  当运动员退场时,从数据结构中删除一条记录。  New 按钮构建一个 新的数组。  Fill 按钮填充随机数 到数组中。  Ins 按钮插入一个新 的数据项  Find 按钮查找特定 的数据项。  Del 按钮删除特定 的数据项。 图2.1 Array 专题applet  插入插入插入插入 以缺省的设置开始程序,共中有一个大小为20 的数 组和10 个数据项,No Dups 按钮被选中。  查找查找查找查找 点击Find 按钮开始查找。程序会提示输入查找队员 的号码。  删除删除删除删除 只有在找到某一数据项后才能删除它。输入待删除 数据项的值,重复点击按钮使箭头一步步下移,直 至找到该数据项。再点击一次按钮,该数据项在数 组中的单元变空。 84 61 15 73 26 38 11 49 53 3284 61 15 73 26 38 11 49 53 32 删除算法中暗含着一个假设,即数组中不允许洞。所以当找到特定数据 项并删除后,applet 必须将随后的数据项前移一步来填补这个洞。图2.2 演示了一个例子 0 1 2 3 4 5 6 7 8 9 将删除项 1 2 3 4 0 1 2 3 4 5 6 7 8 84 61 15 73 26 11 49 53 32 前移内容 图2.2 删除数据项 重复值问题重复值问题重复值问题重复值问题 Array 专题Applet 允许对此进行选择。当使用New 按钮来创建 一个数组时,程序会提示输入它的大小和确定是否允许重复 值,使用单选按钮Dups OK 或No Dups 来作出选择。  允许重复值条件下的查找算法允许重复值条件下的查找算法允许重复值条件下的查找算法允许重复值条件下的查找算法 允许重复将会使查找算法复杂化:即使匹配上一个,它还得 继续寻找可能的匹配,直到最后一个数据项。  允许重复值条件下的插入算法允许重复值条件下的插入算法允许重复值条件下的插入算法允许重复值条件下的插入算法 这与数据项不可重复的插入算法完全一致;插入新数据项只 需一步。  允许重复值条件下的删除算法允许重复值条件下的删除算法允许重复值条件下的删除算法允许重复值条件下的删除算法 允许重复使删除算法更加复杂,这取决于“删除”是如何定义 的。如果它意味着仅删除第一个含有特定值的数据项,那么 平均只需要N/2次比较和N/2次移动。这与不允许重复时 是一样的。 表2.1 允许重复与不允许重复的比较 N次比较,多于N/2 次移动 N/2次比较,N/2 次 移动 删除 无比较,一次移动无比较,一次移动插入 N次比较N/2次比较查找 允许重复不允许重复 Java 中数组的基础知识中数组的基础知识中数组的基础知识中数组的基础知识  Java 数组定义 Java 中有两种数据类型:基本类型(如int 和double) 和对象类型。在Java 中把数组当作对象来对待,因 此在创建数组时必须使用new 操作符: int[] intArray; //defines a reference to an array //creates the array, and sets intArray to refer to it intArray = new int[100] 或使用等价的单语句声明的方法 int[] intArray =new Int[l00] ;  访问数组数据项访问数组数据项访问数组数据项访问数组数据项 数组数据项通过使用方括号中的下标数来访问。这与其他语 言类似 int temp = intArray[3]; // get contents of fourth element of array intArray[7] = 86; //insert 86 into the eighth cell  初始化初始化初始化初始化 当创建整型数组之后,如果不另行指定,那么整型数组合自 动初姑化为空。创建一个对象数组如下: autoData[] carArray = new autoData[4000]; 除非特定的值赋给数组的数据项,否则它们一直是特殊的null 对象。 用下面的语法可以对一个基本类型的数组初始化,赋入非空 值: int[] intArray= {0,3,6,9,12,15,18,21,24,27};  数组例子数组例子数组例子数组例子 清单2.1 (array.java )演示数组应用的示例程序。 class ArrayApp { public static void main(String[] args) { long[] arr; // reference to array arr = new long[100]; // make array int nElems = 0; // number of items int j; // loop counter long searchKey; // key of item to search for //-------------------------------------------------------------- arr[0] = 77; // insert 10 items arr[1] = 99; arr[2] = 44; arr[3] = 55; arr[4] = 22; arr[5] = 88; arr[6] = 11; arr[7] = 00; arr[8] = 66; arr[9] = 33; nElems = 10; // now 10 items in array //-------------------------------------------------------------- for(j=0; j upperBound) return nElems; // can't find it 数组下标最大值数组下标最大值数组下标最大值数组下标最大值 搜索的关键字搜索的关键字搜索的关键字搜索的关键字 要搜索的位置要搜索的位置要搜索的位置要搜索的位置 求得中间位置值求得中间位置值求得中间位置值求得中间位置值 王凌武 王凌武 幻灯片 幻灯片 幻灯片 幻灯片 31313131 王凌武王凌武王凌武王凌武1 1 1 1 王凌武, 2006-09-10 王凌武王凌武王凌武王凌武2 2 2 2 要搜索的值 王凌武, 2006-09-10 else // divide range { if(a[curIn] < searchKey) lowerBound = curIn + 1; // it's in upper half else upperBound = curIn - 1; // it's in lower half } // end else divide range } // end while } // end find()  OrdArray 类类类类 OrdArray.java 程序同highArray.java(清单 2.3) 类似。但主要差异在于find() 使用了二分 查找。 OrdArray 类中还有一个新的size() 方法,它 返回数组当前数据项的个数。清单2.4给出 了OrdArray.java 程序的全部代码。 class OrdArray { private long[] a; // ref to array a private int nElems; // number of data items //----------------------------------------------------------- public OrdArray(int max) // constructor { a = new long[max]; // create array nElems = 0; } //----------------------------------------------------------- public int size() { return nElems; } //----------------------------------------------------------- public int find(long searchKey) { int lowerBound = 0; int upperBound = nElems-1; int curIn; while(true) { curIn = (lowerBound + upperBound ) / 2; if(a[curIn]==searchKey) return curIn; // found it else if(lowerBound > upperBound) return nElems; // can't find it else // divide range { if(a[curIn] < searchKey) lowerBound = curIn + 1; // it's in upper half else upperBound = curIn - 1; // it's in lower half } // end else divide range } // end while } // end find() //----------------------------------------------------------- public void insert(long value )// put element into array { int j; for(j=0; j value) // (linear search) break; for(int k=nElems; k>j; k--) // move bigger ones up a[k] = a[k-1]; a[j] = value; // insert it nElems++; // increment size } // end insert() //----------------------------------------------------------- public boolean delete(long value) { int j = find(value); if(j==nElems) // can't find it return false; else // found it { for(int k=j; k
还剩50页未读

继续阅读

下载pdf到电脑,查找使用更方便

pdf的实际排版效果,会与网站的显示效果略有不同!!

需要 15 金币 [ 分享pdf获得金币 ] 0 人已下载

下载pdf

pdf贡献者

lx6451388

贡献于2011-11-10

下载需要 15 金币 [金币充值 ]
亲,您也可以通过 分享原创pdf 来获得金币奖励!
下载pdf