402
JAVA数据结构与算法-第二章-数组
写在前面：
用典型的网页浏览器运行applet脱机工作：
1.在MS-DOS中使用cd命令移至所需的子目录下
2.使用SDK中的appletviewer工具运行applet的.html文件
示例：
Microsoft Windows [版本 6.1.7600] 版权所有 (c) 2009 Microsoft Corporation。保留所有权利。 C:\Windows\system32>D: D:\>cd data D:\data>cd Array D:\data\Array>appletviewer Array.html 警告：不能读取 AppletViewer 的属性文件： C:\Users\zhuzhengke \.hotjava\properties 使用默认值。 D:\data\Array>appletviewer Array.html
终止程序：
ctrl+c
（顺序表的插入、查找、删除）小DEMO告诉我的：
插入算法
插入算法很快，只要一步。这是由于新的数据项总是插在数组中第一个空位上，并且由于插入过程是很快的，它只需要一步即可完成。这是由于新的数据项总是插在数组中第一个空位上，并且由于数组中已有数据项个数已知，所以算法知道这个空位的具体位置。新的数据项只是简单地插入到下一个可用的空间中。然而查找和删除却没有这么快。
查找算法
查找算法（假设不允许重复数据项值）必须平均搜索一半得数据项来查找特定数据值。找数组头部的数据项快，找数组尾部的数据项慢。设数据项个数为N，则一个数据项的平均查找长度为N/2。在最坏的情况下，待查得数据项在数组的最后，这需要N步才能找到。
执行算法的时间长度与执行步数成正比，所以查找算法的时间（N/2步）要比插入算法（一步）长得多。
删除算法
删除算法中暗含着一个假设，即数组中不允许有洞。洞指的是一个或几个空单元，它们后面还有非空数据项（在更高的下标处还有数据项）。如果扇窗户算法中允许有洞，那么所有其他的算法都将变得更加复杂，因为在查看某一单元的数据项之前还需判断它是否为空。同样，算法会由于需要找到非空数据项而变得效率很低。因此，非空数据项必须连续存储，不能有洞。
所以当找到特定的数据项并将其删除后，必须将随后的数据项都向前移一步来填补这个洞。
删除需要（假设不允许数据项重复）查找平均N/2个数据项并平均移动剩下的N/2个数据项来填充删除而带来的洞。总共是N步。
允许重复值：
允许重复值条件下的查找算法：
需要找到所有与查找关键字匹配的数据项，由于该算法需要一直执行至数组的最后，所以它通常需要执行N步。
允许重复值条件下的插入算法：
这与数据项不可重复的插入算法完全一致：插入更新数据项只需一步。
但请注意，即使不允许重复，用户也有可能输入相同的关键字，因此在插入之前需要先检查已有的数据项。
允许重复值条件下的删除算法：
允许重复会使删除算法更加复杂，这取决于“删除”是如何定义的。
1.如果它意味着仅删除第一个含有特定值的数据项，那么平均只需要N/2次比较和N/2次移动。这与不允许重复时是一样的。
2.但是如果删除 意味着删掉每一个含有特定值的数据项的话，那么同样地操作可能需要多次。这需要检查N个数据项和（可能）移动多于N/2个数据项。这个操作的平均时间依赖于重复数据项在整个数组中的分布情况。
面向过程的数组例子：
package com.zzk.cn;
/*
* 演示数组应用的示例程序
* 面向过程的老式版本
*
*/
class array {
public static void main(String[] args) {
long[] arr;//long型表示数据
arr = new long[100];
int nElems = 0;
int j;//int型表示下标
long searchKey;//保存待查找的值
/*插入数组元素*/
arr[0] = 77;
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;
/* 输出数组元素 */
for (j = 0; j < nElems; j++)
System.out.print(arr[j] + " ");
System.out.println("");// 输出结束所有数组元素再进行换行
/* 查找 */
searchKey = 66;
for (j = 0; j < nElems; j++)
if (arr[j] == searchKey)
break;
if (j == nElems)
System.out.println("Can't find " + searchKey);
else
System.out.println("Found " + searchKey);
/* 删除 */
//找到删除数据项后，向前移动所有下标比它大的数据项来填补删除后留下的 “洞”并将nElems减一
searchKey = 55;
for (j = 0; j < nElems; j++)
if (arr[j] == searchKey)
break;
for (int k = j; k < nElems; k++)
arr[k] = arr[k + 1];
nElems--;//如果不--输出结果就是77 99 44 22 88 11 0 66 33 0，多一位0，而不是77 99 44 22 88 11 0 66 33
for (j = 0; j < nElems; j++)
System.out.print(arr[j] + " ");
System.out.println();
}
}
输出：
77 99 44 55 22 88 11 0 66 33
Found 66
77 99 44 22 88 11 0 66 33
面向对象的改写
package com.zzk.cn;
/**
*
* 面向对象的写法
*
*/
class LowArray
{
private long[] a;
public LowArray(int size)
{
a=new long[size];
}
public void setElem(int index,long value)//index是数组索引，value是value值
{
a[index]=value;
}
public long getElem(int index)
{
return a[index];
}
}
class LowArrayApp
{
public static void main(String[] args)
{
LowArray arr;
arr=new LowArray(100);
int nElems=0;
int j;
arr.setElem(0, 77);//插入十项
arr.setElem(1, 99);
arr.setElem(2, 44);
arr.setElem(3, 55);
arr.setElem(4, 22);
arr.setElem(5, 88);
arr.setElem(6, 11);
arr.setElem(7, 00);
arr.setElem(8, 66);
arr.setElem(9, 33);
nElems=10;
//显示数组内容
for(j=0;j<nElems;j++)
System.out.print(arr.getElem(j)+" ");
System.out.println("");
//查找26
int searchKey=26;
for(j=0;j<nElems;j++)
if(arr.getElem(j)==searchKey)
break;
if(j==nElems)
System.out.println("Can't find "+searchKey);
else
System.out.println("Founde "+searchKey);
//删除55
for(j=0;j<nElems;j++)
if(arr.getElem(j)==55)
break;
for(int k=j;k<nElems;k++)
arr.setElem(k, arr.getElem(k+1));
nElems--;
for(j=0;j<nElems;j++)
System.out.print(arr.getElem(j)+" ");
System.out.println("");
}
}输出：
77 99 44 55 22 88 11 0 66 33
Can't find 26
77 99 44 22 88 11 0 66 33
再次修缮为类接口
package com.zzk.cn;
class HighArray
{
private long[] a;
private int nElems;
public HighArray(int max)
{
a=new long[max];
nElems=0;
}
//find方法用数据项的值作为参数传递，依次查找数组中的每个数据项
//它的返回值是true或者false，取决于是否找到该数据项
public boolean find(long searchKey)
{
int j;
for(j=0;j<nElems;j++)
if(a[j]==searchKey)
break;
if(j==nElems)
return false;
else
return true;
}
//insert方法向数组下一个空位置上放置一个新的数据项
//一个名为nElem的字段跟踪记录着数组中实际已有的数据项个数
public void insert(long value)
{
a[nElems]=value;
nElems++;
}
//delete方法查找相应的数据项，当它找到该数据项后，
//便将所有后面的数据项前移，从而覆盖了待删除的数据项,然后nElems减1
public boolean delete(long value)
{
int j;
for(j=0;j<nElems;j++)
if(value==a[j])
break;
if(j==nElems)
return false;
else
{
for(int k=j;k<nElems;k++)
a[k]=a[k+1];
nElems--;
return true;
}
}
//显示所有数据项的值
public void display()
{
for(int j=0;j<nElems;j++)
System.out.print(a[j]+" ");
System.out.println("");
}
}
public class HighArrayApp
{
public static void main(String[] args)
{
int maxSize=100;
HighArray arr;
arr=new HighArray(maxSize);
//插入
arr.insert(77);
arr.insert(99);
arr.insert(44);
arr.insert(55);
arr.insert(22);
arr.insert(88);
arr.insert(11);
arr.insert(00);
arr.insert(66);
arr.insert(33);
arr.display();
//查找
int searchKey=35;
if(arr.find(searchKey))
System.out.println("Found "+searchKey);
else
System.out.println("Can't find "+searchKey);
arr.delete(00);
arr.delete(55);
arr.delete(99);
arr.display();
}
}
输出：
77 99 44 55 22 88 11 0 66 33
Can't find 35
77 44 22 88 11 66 33
最后更新：2017-04-02 06:52:18
上一篇：
福建省新机动车号牌号码网上自编自选系统使用指南之菜鸟篇
下一篇： 怎样把一个long型的数据转换为数组
- Oracle 12c多租户特性详解：从Schema到PDB的变化与隔离
- Oracle安装在64位系统中报“程序异常终止。发生内部错误”
- TensorFlow教程之完整教程 2.6 卷积神经网络
- HDU4813-Hard Code
- J2EE中EL和JSTL结合运用
- 从CCObject看cocos2d-x的内存管理机制
- Oracle 常用函数
- Action Bar示例代码 (一)
- 调试MVC源代码时"[A]System.Web.WebPages.Razor.Configuration.HostSection 无法强制转换为 ..."解决办法
- Never store the password unhased directly on the server!