长沙网站开发湖南微联讯点不错,买网站的域名,河南省城市建设网站,深圳前50强网站建设公司数组是应用最广泛的数据存储结构。它被植入到大部分编程语言中。大部分数据结构都有最基本的四个操作#xff1a;插入、删除、查找、修改。对于这四种操作每一种数据结构都有相应的算法。算法和数据结构因此就是非常紧密的相联系的。 1 数组例子 … 数组是应用最广泛的数据存储结构。它被植入到大部分编程语言中。大部分数据结构都有最基本的四个操作插入、删除、查找、修改。对于这四种操作每一种数据结构都有相应的算法。算法和数据结构因此就是非常紧密的相联系的。 1 数组例子 数组的每一个元素必须是连续也就是中间没有洞。就是说第一个元素和第三个元素有值但不允许第二个元素是空的。 1 package chapter2;2 3 public class Array {4 public static void main(String[] args){5 //创建一个数组6 long[] arr;7 arr new long[100];8 int nElems 0;9 int j;
10 long searchKey;
11 arr[0] 99;
12 arr[1] 11;
13 arr[2] 22;
14 arr[3] 33;
15 arr[4] 55;
16 arr[5] 66;
17 arr[6] 44;
18 arr[7] 77;
19 arr[8] 23;
20 arr[9] 88;
21 nElems 10;
22 //输出前10位数组元素
23 for(j 0; j nElems; j){
24 System.out.print(arr[j] );
25 }
26 System.out.println();
27 //查找数组的一个元素值为55的元素
28 searchKey 55;
29 for(j 0; j arr.length; j){
30 if(arr[j] searchKey){
31 break;
32 }
33 }
34 if(j nElems){
35 System.out.println(Cant find the element);
36 }else{
37 System.out.println(find the element searchKey at index (j 1) );
38 }
39 //删除指定元素
40 searchKey 66;
41 for(j 0; j arr.length; j){
42 if(arr[j] searchKey){
43 break;
44 }
45 }
46 for(int k j; k nElems; k){
47 arr[k] arr[k1];
48 }
49 nElems--;
50 //输出删除后的数组
51 for(j 0; j nElems; j){
52 System.out.print(arr[j] );
53 }
54 }
55 }
56
57 输出结果
58 99 11 22 33 55 66 44 77 23 88
59 find the element 55 at index 5
60 99 11 22 33 55 44 77 23 88 2 将程序划分成类 上面的程序包含了一个很大的方法通过将程序划分成类以后并且将其中的方法模块化这样程序看起来更加有条理。 1 package chapter2;2 class ArrayMethod{3 private long[] arr;4 private int nElems;5 public ArrayMethod(int max){6 arr new long[max];7 nElems 0;8 }9 public void insert(long value){
10 arr[nElems] value;
11 nElems;
12 }
13 public boolean find(long searchKey){
14 //查找数组的一个元素值为searchKey的元素
15 int j;
16 for(j 0; j arr.length; j){
17 if(arr[j] searchKey){
18 break;
19 }
20 }
21 if(j nElems){
22 return false;
23 }else{
24 return true;
25 }
26 }
27 //删除指定元素
28 public boolean delete(long searchKey){
29 int j;
30 for(j 0; j arr.length; j){
31 if(arr[j] searchKey){
32 break;
33 }
34 }
35 for(int k j; k nElems; k){
36 arr[k] arr[k1];
37 }
38 nElems--;
39 return true;
40 }
41 //输出数组
42 public void display(){
43 //输出前10位数组元素
44 for(int j 0; j nElems; j){
45 System.out.print(arr[j] );
46 }
47 System.out.println();
48 }
49 }
50 class HighArray {
51
52 public static void main(String[] args){
53 int maxSize 100;
54 ArrayMethod arr new ArrayMethod(maxSize);
55 arr.insert(99);
56 arr.insert(11);
57 arr.insert(22);
58 arr.insert(33);
59 arr.insert(55);
60 arr.insert(66);
61 arr.insert(44);
62 arr.insert(77);
63 arr.insert(23);
64 arr.insert(88);
65 //输出数组
66 arr.display();
67 //查找值为55的元素
68 long searchKey 55;
69 if(arr.find(searchKey)){
70 System.out.println(find the element );
71 }else{
72 System.out.println(Cant find the element);
73 }
74 //删除指定元素
75 searchKey 22;
76 if(arr.delete(searchKey)){
77 System.out.println(Delete the element successfully );
78 }else{
79 System.out.println(Cant find the element);
80 }
81 //输出删除元素后的数组
82 arr.display();
83 }
84 } 3 有序数组 假设一个数组其中的数据项按关键字升序排列即最小值在下标为0的单元上每一个单元都比前一个单元的值大。这种数组被称为有序数组。 当向这种数组中插入数据项时需要为插入操作找到正确的位置刚好在稍小值的后面稍大值的前面。然后将所有比待茶数据项的值向后移以便腾出空间。 将数据按顺序排列的好处之一就是可以通过二分法查找显著地提高查找速度。但缺点是降低了插入操作的速度。 4 线性查找 默认情况下是线性查找线性查找和未经排序的数组的查找操作相似。 5 二分查找 当使用二分查找时就体现有序数组的好处这种查找比线性查找快很多尤其是对大数组来说更为显著。 二分查找首先从要查找的范围确定一个中位数然后比较要找的数和中位数的大小关系确定更小的范围依次递归知道找到那个数。 将数目进行放大可以发现二分查找是极为优秀的 5.1 有序数组的二分搜索代码 二分查找是将数组数据项范围不断对半分隔来查找特定的数据项。方法如下所示 1 package chapter2;2 class ArrayMethod{3 private long[] arr;4 private int nElems;5 public ArrayMethod(int max){6 arr new long[max];7 nElems 0;8 }9 public void insert(long value){10 arr[nElems] value;11 nElems;12 }13 //二分查找法14 public int halfFind (long searchKey){15 int lowerBound 0;16 int upperBound nElems - 1;17 int curIn;18 while(true){19 curIn (lowerBound upperBound)/2;20 if(arr[curIn] searchKey){21 return curIn;22 }else if(lowerBound upperBound){23 return nElems;24 }else{25 if(arr[curIn] searchKey){26 upperBound curIn - 1;27 }else{28 lowerBound curIn 1;29 }30 } 31 }32 }33 public int size(){34 return nElems;35 }36 public boolean find(long searchKey){37 //查找数组的一个元素值为searchKey的元素38 int j;39 for(j 0; j arr.length; j){40 if(arr[j] searchKey){41 break;42 }43 }44 if(j nElems){45 return false;46 }else{ 47 return true;48 }49 }50 //删除指定元素51 public boolean delete(long searchKey){52 int j;53 for(j 0; j arr.length; j){54 if(arr[j] searchKey){55 break;56 }57 }58 for(int k j; k nElems; k){59 arr[k] arr[k1];60 }61 nElems--;62 return true;63 }64 //输出数组65 public void display(){66 //输出前10位数组元素67 for(int j 0; j nElems; j){68 System.out.print(arr[j] );69 }70 System.out.println();71 }72 }73 class HighArray {74 75 public static void main(String[] args){76 int maxSize 100;77 ArrayMethod arr new ArrayMethod(maxSize);78 arr.insert(99);79 arr.insert(11);80 arr.insert(22);81 arr.insert(33);82 arr.insert(55);83 arr.insert(66);84 arr.insert(44);85 arr.insert(77);86 arr.insert(23);87 arr.insert(88);88 //输出数组89 arr.display();90 //查找值为55的元素91 long searchKey 35;92 // if(arr.find(searchKey)){93 // System.out.println(find the element );94 // }else{95 // System.out.println(Cant find the element);96 // }97 //二分法查找98 if(arr.halfFind(searchKey) ! arr.size()){99 System.out.println(Find it);
100 }else{
101 System.out.println(Cant find it);
102 }
103 // //删除指定元素
104 // searchKey 22;
105 // if(arr.delete(searchKey)){
106 // System.out.println(Delete the element successfully );
107 // }else{
108 // System.out.println(Cant find the element);
109 // }
110 //输出删除元素后的数组
111 arr.display();
112 }
113 } 5.2 有序数组的优点 使用有序数组最主要的好处是查找的速度比无序数组快多了。不好的方面是在插入操作中由于所有靠后的数据都需要移动以腾开空间所以速度较慢。有序数组和无序数组中的删除操作都很慢这是因为数据项必须向前移动来填补已删除数据项的洞。有序数组在查找频繁的情况下十分有用但若是插入和删除较为频繁时则无法高效工作。 6 大O表示法 计算机科学中评价算法效率的方法称为大O表示法。比较算法时候通常会说算法A比算法B快2倍这种说法意义不大。因为数据项的变化会对排序造成一定很大影响。有可能数据项增加50%算法A就比B快了3倍或者可能只有一半的数据项A和B的速度是相同的。 6.1 无序数组的插入常数 无序数组的插入是我们到现在为止所见过的算法中唯一一个与数组项个数无关的算法。新数据项总被放在下一个有空的地方,a[nElems]然后nElems增加。无论数组中的数据项个数N有多大一次插入总是用相同的时间。我们可以说向一个无序数组中插入一个数据项的时间T是一个常数K TK 在现实情况中插入所需的实际时间与以下这些因素有关微处理器编译程序生成程序代码的效率等等。 6.2 线性查找与N成正比 在数组数据项的线性查找中我们已经发现寻找特定数据项所需的比较平均次数为数据项总数的一半。因此设N为数据项总数搜索时间T与N的一半成正比 TK*N/2 同插入一样若要得到方程中K的值首先需要对某个N值的查找进行计时然后用T来计算K。当得到K后便可以对任意N的值来计算T。将2并入K可以得到更方便的公式新K值等于原先的K除以2即 TK*N 这个方程说明平均线性查找时间与数组的大小成正比。即如果一个数组增大两倍则所花费的查找时间也会相应地增长两倍。 6.3 二分查找:与log(N)成正比 同样我们可以为二分查找指定出一个与T和N有关的公式:TK*log2(N) 实际上由于所有的对数和其他对数成比例(比如从底数2转换到底数为10需乘以3.322)也可以将这个为常数的底数也并入K。由此不必指定底数: TK*log(N) 不要常数 大O表示法同上面的公式比较类似但它省去了常数K。当比较算法时并不在乎具体的微处理器或编译器真正需要比较的是对应不同的N值T是如何变化的而不是具体的数字因此不需要常数。 大O表示法使用大写字母O可以认为其含义是order of(大约是)。我们可以使用大O表示法来描述线性查找使用了O(N)级时间二分查找使用了O(logN)级时间。向一个无序数组中的插入使用了O(1)或常数级时间。 下表总结的是讨论过的算法的运行时间 大O表示法的实质并不是对运行时间给出实际值而是表达了运行时间是如何受数据项个数所影响的。除了实际安装后真正去测量一次算法的运行时间之外这可能是对算法进行比较的最有意义的方法了。 6.4 几种算法时间复杂度的对比 7 为什么不用数组表示一切 仅使用数组似乎就可以完成所有工作为什么不用它们来进行所有数据存储呢我们已经见到了许多关于数组的缺点。在一个无序数组中可以很快进行插入(O(1))但是查找却要花费较慢的O(N)时间。在一个有序数组中可以查找得很快用O(logN)的时间但插入却花费了O(N)时间。对于这两种数组而言由于平均半数的数据项为了填补空洞必须移动所以删除操作平均需要O(N)时间。 如果有一种数据结构进行任何如插入、删除和查找的操作都很快(理想的O(1)或是O(logN)时间)那就好了。后面我们会介绍类似的数组但这是以程序的复杂度为代价的。 另外数组被创建后占用内存长度是确定的无法进行修改这样的话如果创建的长度过大但是实际需要的很少就会造成内存浪费如果创建的长度过小就会造成溢出无法弹性使用。转载于:https://www.cnblogs.com/people/p/3188437.html
