Java数据结构和算法笔记

《Java数据结构和算法笔记》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、Java数据结构和算法第0讲综述参考教材：Java数据结构和算法（第二版），[美]Robertlafore1.数据结构的特性数据结构优点缺点数组插入快；如果知道下标，可以非常快地存取查找慢，删除慢，大小固定有序数组比无序的数组查找快删除和插入慢，大小固定栈提供后进先出方式的存取存取其他项很慢队列提供先进先出方式的存取存取其他项很慢链表插入快，删除快查找慢二叉树查找、插入、删除都快（如果树保持平衡）删除算法复杂红-黑树查找、插入、删除都快；树总是平衡的算法复杂2-3-4树查找、插入、删除都快；树总是平

2、衡的；类似的树对磁盘存储有用算法复杂哈希表如果关键字已知，则存储极快；插入快删除慢，如果不知道关键字则存储很慢，对存储空间使用不充分堆插入、删除快；对大数据项的存取很快对其他数据项存取慢图对现实世界建模有些算法慢且复杂2.经典算法总结查找算法：线性查找和二分查找排序算法：用表展示第一讲数组1.Java中数组的基础知识1）创建数组在Java中把数组当作对象来对待，因此在创建数组时必须使用new操作符：int[]intArr=newint[10];一旦创建数组，数组大小便不可改变。2）访问数组数据项数组

3、数据项通过方括号中的下标来访问，其中第一个数据项的下标是0：intArr[0]=123;1）数组的初始化当创建数组之后，除非将特定的值赋给数组的数据项，否则它们一直是特殊的null对象。int[]intArr={1,2,3,4,5};等效于下面使用new来创建数组并初始化：int[]intArr=newint[5];intArr[0]=1;intArr[1]=2;intArr[2]=3;intArr[3]=4;intArr[4]=5;1.面向对象编程方式1）使用自定义的类封装数组MyArray类：p

4、ublicclassMyArray{privatelong[]arr;privateintsize;//记录数组的有效长度publicMyArray(){arr=newlong[10];}publicMyArray(intmaxSize){arr=newlong[maxSize];}//向数组中插入数据publicvoidinsert(longelement){arr[size]=element;size++;}//显示数组中的数据publicvoidshow(){for(inti=0;i

5、;i++){if(i==0){System.out.print("["+arr[i]+",");}elseif(i==size-1){System.out.println(arr[i]+"]");}else{System.out.print(arr[i]+",");}}}//根据值查找索引（出现该值的第一个位置）：线性查找publicintqueryByValue(longelement){inti;for(i=0;i

6、nt)break;}if(i==size){return-1;}else{returni;}}//根据索引查找值publiclongqueryByIndex(intindex){if(index>=size

7、

8、index<0){thrownewArrayIndexOutOfBoundsException();}else{returnarr[index];}}//删除数据publicvoiddelete(intindex){if(index>=size

9、

10、index<0){thrownewArrayI

11、ndexOutOfBoundsException();}else{//当size=maxSize，删除最后一个数时，不会执行forfor(inti=index;i=size

12、

13、index<0){thrownewArrayIndexOutOfBoundsE

14、xception();}else{arr[index]=value;}}}1）添加类方法实现数据操作测试MyArray类方法：publicvoidtestMyArray()throwsException{MyArraymyArray=newMyArray();myArray.insert(123);myArray.insert(456);myArray.insert(789);myArray.show();//[123,456,789]System.out.print