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!