Java数据结构和算法笔记.docx

Java数据结构和算法

第0讲综述
参考教材：Java数据结构和算法（第二版），[美]Robertlafore

1.数据结构的特性

数据结构优点缺点数组插入快；如果知道下标，可以非常快地存取查找慢，删除慢，大小固定有序数组比无序的数组查找快删除和插入慢，大小固定栈提供后进先出方式的存取存取其他项很慢队列提供先进先出方式的存取存取其他项很慢链表插入快，删除快查找慢二叉树查找、插入、删除都快（如果树保持平衡）删除算法复杂红-黑树查找、插入、删除都快；树总是平衡的算法复杂2-3-4树查找、插入、删除都快；树总是平衡的；类似的树对磁盘存储有用算法复杂哈希表如果关键字已知，则存储极快；插入快删除慢，如果不知道关键字则存储很慢，对存储空间使用不充分堆插入、删除快；对大数据项的存取很快对其他数据项存取慢图对现实世界建模有些算法慢且复杂
2.经典算法总结
查找算法：线性查找和二分查找
排序算法：
用表展示

第一讲数组

Java中数组的基础知识
创建数组
在Java中把数组当作对象来对待，因此在创建数组时必须使用new操作符：
int[]intArr=newint[10];一旦创建数组，数组大小便不可改变。

访问数组数据项
数组数据项通过方括号中的下标来访问，其中第一个数据项的下标是0：
intArr[0]=123;
数组的初始化
当创建数组之后，除非将特定的值赋给数组的数据项，否则它们一直是特殊的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;
面向对象编程方式
使用自定义的类封装数组
MyArray类：
publicclassMyArray{
privatelong[]arr;
privateintsize; //记录数组的有效长度

publicMyArray(){
arr=newlong[10];
}
publicMyArray(intmaxSize){
arr=newlong[maxSize];
}

//向数组中插入数据
publicvoidinsert(longelement){
arr[size]=element;
size++;
}

//显示数组中的数据
publicvoidshow(){
for(inti=0;i<size;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<size;i++){//linearsearch
if(arr[i]==element)break;
}
if(i==size){
return-1;
}else{
returni;
}
}

//根据索引查找值
publiclongqueryByIndex(intindex){
if(index>=size||index<0){
thrownewArrayIndexOutOfBoundsException();
}else{
returnarr[index];
}
}

//删除数据
publicvoiddelete(intindex){
if(index>=size||index<0){
thrownewArrayIndexOutOfBoundsException();
}else{
//当size=maxSize，删除最后一个数时，不会执行for
for(inti=index;i<size-1;i++){
arr[index]=arr[index+1];
System.out.println("for");
}
size--;
}
}

//更新数据
publicvoidupdate(intindex,longvalue){
if(index>=size||index<0){
thrownewArrayIndexOutOfBoundsExcept