Java数据结构和算法笔记3

Java数据结构和算法

第o讲综述

参考教材:Java数据结构和算法（第二版），［美］Robertlafore

L数据结构的特性

数据结构优点缺点

数组插入快；如果知道下标，可以非常快地存取查找慢，删除慢，大小固定

有序数组比无序的数组查找快删除和插入慢，大小固定

栈提供后进先出方式的存取存取其他项很慢

队列提供先进先出方式的存取存取其他项很慢

链表插入快，删除快查找慢

二叉树查找、插入、删除都快（如果树保持平衡）删除算法复杂

红-黑树查找、插入、删除都快；树总是平衡的算法复杂

2-3-4树查找、插入、删除都快；树总是平衡的；类算法复杂

似的树对磁盘存储有用

哈希表如果关键字已知，则存储极快；插入快删除慢，如果不知道关键字则存

储很慢,对存储空间使用不充分

堆插入、删除快；对大数据项的存取很快对其他数据项存取慢

图对现实世界建模有些算法慢且复杂

2.经典算法总结

查找算法：线性查找和二分查找

排序算法：

用表展示

第一讲数组

1.Java中数组的基础知识

1）创建数组

在Java中把数组当作对象来对待，因此在创建数组时必须使用new操作符:

int[]intArr=newint[10];

一旦创建数组，数组大小便不可改变。

2)访问数组数据项

数组数据项通过方括号中的下标来访问，其中第一个数据项的下标是0：

intArr[0]=123;

3)数组的初始化

当创建数组之后，除非将特定的值赋给数组的数据项，否则它们一史是特殊的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;

2.面向对象编程方式

1)使用自定义的类封装数组

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；+",n);

}elseif(i==size-l){

System.out.printIn(arr[i]+"]**);

}else{

System.out.print(arr[i]+",H);

)

}

)

//根据值查找索引(出现该值的第一个位置)：线性杳找

publicintqueryByValue(longelement){

inti;

for(i=0;i<size;i++){//linearsearch

if(arr[i]==element)break；

}

if(i==size){

return-1;

}else{

returni;

)

}

〃根据索引查找值

publiclongqueryBylndex(intindex){

if(index>=sizeIIindex<0){

thrownewArraylndexOutOfBoundsException();

}else{

returnarr[index];

}

}

//删除数据

publicvoiddelete(intindex){

if(index>=size||index<0){

thrownewArraylndexOutOfBoundsException();

}else{

//当size=maxSize,删除最后一个数时，不会执行for

for(inti=index;i<size-l;i++){

arr[index]=arr[index+1];

System.out.printin("for");

)

size——;

)

〃更新数据

publicvoidupdate(intindex,longvalue){

if(index>=size||index<0){

thrownewArraylndexOutOfBoundsException();

}else{

arr[index]=value;

}

)

}

2)添加类方法实现数据操作

测试MyArray类方法：

publicvoidtestMyArray()throwsException{

MyArraymyArray=newMyArray();

myArray.insert(123);

myArray.insert(456);

myArray.insert(789);

niyAx£cty.show();//[123z456,789]

System.out.printIn(myArray.queryByValue(111));//-I

System.out.printin(myArray.queryBylndex(2));//789

myArray.delete(2);

myArray.show();//[123,456]

myArray.update(0,0);

myArray.show();//[0z456]

3.有序数组

1)有序数组简介以及其优点

有序数组是一种数组元素按一定的顺序排列的数组，从而方便使用二分查找来查找数组中

特定的元素。有序数组提高了查询的效率，但并没有提高删除和插入元素的效率。

2)构建有序数组

将2.1中自定义的类封装数组MyArray的insert方法改为如下：

//向有序数组中插入数据，按大小从前往后排列

publicvoidinsert(longelement)(

inti;

for(i=0;i<size;i++){//findwhereitgoes

if(element<arr[i])break；

)

for(intj=size;j>i;j-){//movebiggeronesup

arr[j]=arr[j-1];

)

arr[i]=elenent;

size++;

得到有序数组的类封装MyOrdcrcdArray类，测试该类中的insert方法：

publicvoidtestMyOrderedArray()throwsException{

MyOrderedArraymyOrderedArray=newMyOrderedArray();

myOrderedArray.insert(999);

myOrderedArray.insert(555);

myOrderedArray.insert(777);

myOrderedArray.show();//[555,777,999]

4.查找算法

1)线性查找

在查找过程中，将要查找的数一个一个地与数组中的数据项比较，直到找到要找的数。在2.1

中自定义的类封装数组MyArray的queryByValue方法，使用的就是线性查找。

2)二分查找

二分查找(又称折半查找)，即不断将有序数组进行对半分割，每次拿中间位置的数和

要查找的数进行比较：如果要杳找的数<中间数，则表明要查的数在数组的前半段；如果要

查的数>中间数，则表明该数在数组的后半段；如果要查的数二中间数，则返回中间数。

在有序数组的类封装类MyOrderedArray中添加binarySearch方法

~//根据值二分查找索引(前提：有序)

publicintbinarySearch(longvalue){

intmiddle=0;

intleft=0;

intright=size-1;

while(true)

middle=(left+right)/2;

if(arr[middle]==value){

returnmiddle;//foundit

}elseif(left>right){

return-1;//can'tfoundit

}else{//dividerange

if(arr[middle]>value){

right=middle-1;//inlowerhalf

}else{

left=middle+1;//inupperhalf

)

}

)

测试该二分查找方法：

publicvoidtestMyOrderedArray()throwsException{

MyOrderedArraymyOrderedArray=newMyOrderedArray();

myOrderedArray.insert(999);

myOrderedArray.insert(555);

myOrderedArray.insert(777);

myOrderedArray.insert(333);

System,out.printIn(myOrderedArray.bmarySearch(333));//0

第二讲简单排序

1.本讲提到的排序算法都假定了数组作为数据存储结构，本讲所有算法的时间复杂度都

是。在大多数情况下，假设当数据展比较小或基本上有序时，插入排序算法是三种简单排序

算法中最好的选择，是应用最多的。对于更大数据量的排序来说，后面讲到的快速排序通常

是最快的方法。

2.冒泡排序

1)基本思想

在要排序的一组数中，对当前还未排好序的范围内的全部数，自下而上对相邻的两个数依次

进行比较和调整，让较大的数往下沉，较小的往上冒。即：每当两相邻的数比较后发现它们

的排序与排序要求相反时.就将它们互换。

2)算法实现

冒泡排序的Java代码:

//bubblesort

publicstaticvoidbubbleSort(long[]arr){

longtemp;

for(inti=0;Karr.length-1;i++){//outerloop(forward)

for(intj=arr.length-1;j>i;j-){//innerloop(backward)

if(arr[j]<arr[j-1]){//swapthem

temp=arr[j];

arr[j]=arr[j-l];

arr[j-1]=temp;

)

)

)

}

测试冒泡排序及输出结果：

publicvoidtestBubbleSort()throwsException{

long[]arr={79,91,13,52,34);

Sort.bubbleSort(arr);

System.out.printIn(Arrays.toStringfarr));//[13,34,52,79,91]

3.选择排序

1)基本思想

在要排序的一组数中，选出最小的一个数与第一个位置的数交换；然后在剩下的数当中再找

最小的与第二个位置的数交换，如此循环到倒数第二个数和最后一个数比较为止。

与冒泡排序相比，选择排序将必要的交换次数从O(N*N)减少到0(N),但比较次数仍然保持

为O(N*N)。

2)算法实现

选择排序的Java代码:

//LauxL

publicstaticvoidselectSort(long[]arr){

longtemp;

for(inti=0;i<arr.length-1;i++){//outerloop

intk=i;//locationofminimum

for(intj=i+l;j<arr.length;j++){//innerloop

if(arr[j]<arr[k]){

k=j;//anewminimumlocation

)

1

temp=arr[i];

arr[i]=arr[k];

arr[k]=temp;

)

测试选择排序及输出结果:

publicvoidtestSelectSort()throwsException(

long[]arr={79,91,13,52,34);

Sort.selectSort(arr);

System.out.printIn(Arrays.toString(arr));//[13,34,52,79,91]

)

4.插入排序

1)基本思想

在要排序的一组数中，假设前面(n-l)[n>=21个数己经是排好顺序的(局部有序),现在要把

第n个数插到前面的有序数中，使得这n个数也是排好顺序的。如此反复循环，直到全部排

好顺序。

在插入排序中，一组数据仅仅是局部有序的；而冒泡排序和选择排序，一组数据项在某个时

刻是完全有序的。

2)算法实现

插入排序的Java代码：

//insertsort

publicstaticvoidinsertsort(long[]arr){

longtemp;

for(inti=l;i<arr.length;i++){//iismarkedlocation

temp=arr[i];//removemarkeditem

intj=i;//startshiftsati

while(j>=l&&arr[j-1]>temp){//untiloneissmaller

arr[j；=arr[j-1];//shiftitemright

j;//goleftoneposition

)

arr[j]=temp;//insertmarkeditem

)

}

测试插入排序以及输出结果：

publicvoidtestlnsertSort()throwsException{

long[]arr={79,91,13,52,34,34);

Sort.insertSort(arr);

System.out.printIn(Arrays.toString(arr));

//[13,34,34,52,79,91]

第三讲栈和队列

1.栈和队列都是抽象数据类型(abstractdautype,ADT),它们既可以用数组实现，乂可以

用链表实现。

2.栈

1)栈模型

入栈出栈

{A,B,C,D}{D,C,B,A}

栈顶D

C

B

A

栈底

栈（Slack,乂LIFO:后进先出）是一种只能在固定的一端进行插入和删除的数据结构。栈

只允许访问一个数据项：即最后插入的数据项，移除这个数据项后才能访问倒数第二个插入

的数据项，以此类推。栈可以用数组来实现，也可以用链表来实现。

2）栈的数组实现

栈的Java代码：

publicclassMyStack{

privatelong[]arr;//底层使用数组实现

privateinttop;

publicMyStack(){

arr=newlong[10];

top=-1;

}

publicMyStack(intmaxSize)(

arr=newlong[maxSize];

top=-1;

}

//putitemonLopo£stack

publicvoidpush(longvalue){

arr[++top]=value;

)

//takeitemfromtopofstack

publiclongpop(){

returnarr[top——];

//peekattopofstack

publiclongpeek(){

returnarr[top);

)

//tureifstackisempty

publicbooleanisEmpty(){

return(top==-1);

}

//tureifstackisfull

publicbooleanisFull(){

return(top==arr.length-1);

测试栈的特性：

publicvoidtestMyStack()throwsException{

MyStackmyStack=newMyStack(4);

myStack.push(12);

myStack.push(34);

myStack.push(56);

myStack.push(78);

System.out.piintin(myStack.isFull());//true

while(!myStack.isEmpty()){

System.out.print(myStack.pop());//78z56,34,12

if(!myStack.isEmpty()){

System.out.print('*,*');

)

)

System.out.printin();

System.out.printin(myStack.isFull());//false

3.队列

1）队列模型

队列（Queue,乂FIFO:先进先出）是一种插入时在一端进行而删除时在另一端进行的数据

结构。

为解决顺序队列假溢出问题，而采用循环队列：即让队头、队尾指针在达到尾端时，又绕回

到开头。

2）队列的数组实现

队列的Java代码：

pxiblicclassMyQueue{

privatelong[]arr;

privateintsize;

privateintfront;

privateintrear;

publicMyQueue(){

arr=newlong[10];

size=0;

front=0;

rear=-1;

}

publicMyQueue(intmaxSize)(

arr=newlong(maxSize];

size=0;

front=0;

rear=-1;

//putitematrearofqueue

publicvoidinsert(longvalue){

if(isEmpty()){//throv;exceptionifqueueisfull

thrownewArrayindexoutofBoundsException();

}______

if(rear==arr.length-1){//dealwithwraparound(环绕式处理)

rear=-1;

)

arr[++rear]=value;//incrementrearandinsert

size++;//incrementsize

//takeitemfromfrontofqueue

publiclongremove(){

longvalue=arr[front++];//getvalueandincrementfront

if(front==arr.length){//dealw_thwraparound

front=0;

)

size——;//onelessitem

returnvalue；

〃peekatfrontofqueue

publiclongpeek(){

returnarr[front];

)

//trueifqueueisempty

publicbooleanisEmpty(){

return(size==0);

)

//trueifqueueisfull

publicbooleanisFull(){

return(size==arr.length);

}

测试队列的特性：

publicvoidtestMyQueue()throwsException{

MyQueuemyQueue=newMyQueue(4);

myQueue.insert(12);

myQueue.insert(34);

myQueue.insert(56);

myQueue.insert(78);

System.out.println(myQueue.isFull());//true

while(!myQueue.isEmpty()){

System.out.print(myQueue.remove());//12,34z56,78

if(!myQueue.isEmpty()){

System.out.print('*,*');

)

)

System.out.printin();

System.out.printin(myQueue.isEmpty());//true

myQueue.insert(99);

System.out.printin(myQueue.peek());//99

第四讲链表

L链结点

一个链结点（Link,或称结点）是某个类的对象，该对象中包含对下一个链结点引用的字段

（通常叫next）。而链表本身的对象中有一个字段指向对第一个链结点的引用，

datanext

head----------------------------------------------------------------------

—>----->—-----►Oj----►q+i—►•••-►an-iA

Link类的定义：

publicclassLink{

publiclongdata;//dataitem

publicLinknext;//nextlinkinlist

publicLink.(longdata)(

this.data=data;

}

publicvoiddisplayLink(){//displayourself

System,out.print(data+'*);

2.单链表(LinkList)

•LinkLisi类显示了一个单链表，该链表可以进行的操作有：

在链表头插入•个数据(insertFirst):设置新添加的结点的next设为原来的头结点，再将新

添加的结点设为头结点。

在链表头删除一个数据(deleteFirst):将第二个结点设为头结点。

遍历链表显示所有数据(displayList)：使用临时指针current,从头结点开始，沿着链表先前

移动，依次遍历每个节点。

LinkList类:

publicclassLinkList{

privateLinkfirst;//referencetofirstlinkonlist

publicLinkList(){

this.first=null;

}

//insertatstartoflist

publicvoidinsertFirst(longvalue){

LinknewLink=newLink(value);

newLink.next=first;//nev/Link-->oldfirst

first=newLink;//first——>newLink

}

//deletefirstitem

publicLinkdeleteFirst(){

if(first==null){

returnnull;

)

Linktemp=first;

first=first.next;//deleteit:first-->oldnext

returntemp;//returndeletedlink

)

publicvoiddisplayList(){

Linkcurrent=first;//startatteginningoflist

while(current!=null){//untilendoflist

current.displayLink.();

current=current.next;//movelisttonextlink

}

System.out.printIn();

}

}

测试LinkLisl类的方法:

publicvoidtestLinkList()throwsException{

LinkListlinkList=newLinkList();

linkList.insertFirst(88);

linkList.insertFirst(66);

linkList.insertFirst(44);

linkList.insertFirst(22);

linkList.displayList();//22-->44-->66-->88-->

linkList.deieteFirst();

linkList.displayList();//44-->66-->88-->

3.查找和删除指定链结点

•此外，还能对指定的结点值进行查找和删除：

查找指定结点(find):类似于之前的displayLisl方法。

删除指定结点(delete)：在删除指定结点时，必须把前一个结点和后一个结点连接在

一起，所以需要一个临时指针(previous)来保存对前一个结点的引用。

向LinkList类中添加查找(find)和删除(delete)方法：

//findlinkwithgivenkey

publicLinkfind(longkey){

Linkcurrent=first;//startat1first'

while(current.data!=key){

if(current.next==null){//didn*tfindit

returnnull;

}else{//gotonextlink

current=current.next;

)

)

returncurrent;

}

//deletelinkwithgivenkey

publicLink,delete(longkey){

Linkcurrent=first;//searchforexpectedlink

Linkprevious=first;

while(current.data!=key){

if(current.next==null){

returnnull;//didn*tfindit

}else{

previous=current;

current=current.next;//gotonextlink.

)

}//findit

if(current==first){//iffirstlink,changefirst

first=first.next;

}else{//otherwise,bypassit

previous.next=current.next;

)

returncurrent;

}

测试添加的find和delete方法：

publicvoidtestLinkList()throwsException{

LinkListlinkList=newLinkList();

linkList.insertFirst(88);

linkList.insertFirst(66);

linkList.insertFirst(44);

linkList.insertFirst(22);

linkList.displayList();//22―>44—>66—>88->

linkList.find(44).displayLink();//44-->

System.out.printIn();

linkList.delete(44).displayLink();//44-->

System.out.printIn();

linkList.displayList();//22-->66-->88-->

第五讲双端链表和双向链表

1.双端链表

链表中保存着对最后一个链结点的引用

•从头部进行插入(inserlFirst):要对链表进行判断，如果链表为空，则设置尾结点为新

添加的结点。

从尾部进行插入(insertLast)：如果链表为空，则直接设置头结点为新添加的结点，否

则设置尾结点的后一个节点为新添加的结点。

从头部进行删除(deEeFirst)：判断头结点是否有二一个结点，如果没有则设置尾结点

为nullo

双端链表FirstLastList类:

publicclassFirstLastList{

privateLinkfirst;//referencetofirstlink

privateLinklast;//referencetolastlink

publicFirstLastList(){

this.first=null;

this.last=null;

}

publicbooleanisEmpty(){//trueifnolinks

returnfirst==null;

}

//insertatfrontoflist

publicvoidinsertFirst(longvalue){

LinknewLink=newLink(value);

if(isEmpty()){//ifemptylist

last=newLink;//newLink<--last

)

newLink.next=first;//newLink-->oldfirst

first=newLink;//first一一>newLink

}

//insertatendoflist

publicvoidinsertLast(longvalue){

LinknewLink=newLink(value);

if(isEmpty()){//ifemptylist

first=newLink;//first-->newLink

}else{

last.next=newLink;//oldlast——>newLink

)

last=nevzLink;//newLink<——last

}

//deletefirstlink

publicLinkdeleteFirst(){

Linktemp=first;

if(first.next——null){//ifonlyoneitem

last=null;//null<--last

)

first=first.next;//first-一>oldnext

returntemp;

}

publicvoiddisplayList(){

Linkcurrent=first;//startatteginningoflist

while(current!=null){//untilendoflist

current.displayLink.();

current=current.next;//movelisttonextlink

)

System.out.printIn();

}

}

测试FirstLastList类及输出结果:

publicvoidtestFirstLastList()throwsException{

FirstLastListlist=newFirstLastList();

list.insertLast(24);

list.insertFirst(13);

list.insertFirst(5);

list.insertLast(46);

list.displayList();//5—>13—>24->46-->

list.deleteFirst();

list.displayList();//13-->24-->46-->

2.双向链表

•双向链表既允许向后遍历，也允许向前遍历整个链表。即每个节点除了保存了对下一个

节点的引用，同时后保存了对前一个节点的引用。

•从头部进行插入(insertFirst):要对链表进行判断，如果为空，则设置尾结点为新添加

的结点；如果不为空.还需要设置头结点的前一个结点为新添加的结点。

•从尾部进行插入(insertLast):如果链表为空，则直接设置头结点为新添加的结点，否

则设置尾节点的后一个结点为新添加的结点。同时设置新添加的结点的前一个结点为尾

结点。

•从头部进行删除(deleteFirst)：判断头结点是否有人一个结点，如果没有则设置尾结点

为null；否则设置头结点的下一个结点的previous为null.

•从尾部进行删除(dclctcLast)：如果头结点后没有其他结点，则设置头结点为null。否

则设置尾结点的前一个结点的next为nulU设置尾结点为其前一个结点。

在指定结点后插入(insertAfter):

删除指定结点(deleteKey):不再需要在使用一个临时的指针域指向前一个结点。

双向链表的链接点Link类的定义:

publicclassDoubleLink{

publiclongdata;//dataitem

publicDoubleLinknext;//nextlinkinlist

publicDoubleLinkprevious;//previouslinkinlist

publicDoubleLink(longdata){

this.data=data;

}

publicvoiddisplayLink(){//displayourself

System,out.print(data+'*<==>");

}

)

双向链表DoublyLinkedList类：

publicclassDoublyLinkedList{

privateDoubleLinkfirst;//referencetofirstlink

privateDoubleLinklast;//referencetolastlink

publicDoublyLinkedList(){

this.first=null;

this.last=null;

}

publicbooleanisEmpty(){//trueifnolinks

returnfirst==null;

}

//insertatfrontoflist

publicvoidinsertFirst(longvalue){

DoubleLinknewLink=newDoubleLink(value);

if(isEmpty()){//ifemptylist

last=newLink;//newLink<——last

}else{

first.previous=newLink;//newLink<-oldfirst

)

newLink.next=first;//newLink-->oldfirst

first=newLink;//first-->newLink

)

//insertatendoflist

publicvoidinsertLast(longvalue){

DoubleLinknewLink=newDoubleLink(value);

if(isEmpty()){//ifemptylist

first=newLink;//firstnewLink

}else{

last.next=newLink;//oldlast——>newLink

newLink.previous=last;//oldlastnev/Link

)

last=newLink;//newLink<--last

)

//deletefirstlink

publicDoubleLinkdeleteFirst(){

DoubleLinktemp=first;

if(first.next==null){//ifonlyoneitem

last=null;//null<--last

}else{

first.next.previous=null;//null<--oldnext

I

first=first.next;//first-->oldnext

returntemp;

}

//deletelastlink

publicDoubleLinkdeleteLast(){

DoubleLinktemp=last;

if(first.next==null){//ifonlyoneitem

first=null;//first-->null

}else{

last.previous.next=null;//oldpreviousnull

}

last=last.previous;//oldprevious<--last

returntemp;

//insertdatajustafterkey

publicbooleaninsertAfter(longkey,longdata){

DoubleLinkcurrent=first;//startatbeginning

while(current.data!=key){//untilmatchisfound

if(current.next==null){

returnfalse;

}else(

current=current.next;

)

}//findthepositionofkey

DoubleLinknev/Link=newDoubleLink(data);//makenewlink

if(current==last)(//iflastlink,

newLink.next=null;//newLink-->null

last=newLink;//newLink<-last

}else{//notlastlink.

newLink.next=current.next;//newLink-->oldnext

current.next.previous=newLink;//newLink<一一oldnext

)

current.next=newLink;//oldcurrent-->newLink

newLink.previous=current;//oldcurrent<-newLink

returntrue;

)

//deletelinkwithgivenkey

publicDoubleLinkdeleteKey(longkey){

DoubleLinkcurrent=first;//searchforexpectedlink

while(current.data!=key){

if(current.next==null){

returnnull;//didn'tfindit

}else{

current=current.next;//gotonextlink.

)

}//findit

if(current==first){//iffirstLink,changefirst

first=first.next;//first-->oldnext

}else{//otherwise,oldprevious-->oldnext

current.previous.next=current.next;}

if(current==last){//lastitem?

last=last.previous;//oldprevious<--last

}else{//notlast:oldprevious<——oldnext

current.next.previous=current.previous;

}

returncurrent;

publicvoiddisplayForward(){

System.out.print("first—>last:");

DoubleLinkcurrent=first;//startatbeginningoflist

while(current!=null){//untilendoflist

current.displayLink();

current=current.next;//movelisttonextlink

}

System.out.printin();

)

publicvoiddisplayBackward(){

System,out.print("lasts-->first:");

DoubleLinkcurrent=last;//startatendoflist

while(current!=null){//untilstartoflist

current.displayLink();

current=current.previous;//movelisttopreviouslink

)

System.out.printIn();

}

)

测试该类的主要方法:

publicvoidtestDoublyLinkedList()throwsException{

DoublyLinkedListlist=newDoublyLinkedList();

list.insertLast(24);

list.insertFirst(13);

list.insertFirst(b);

list.i