Java数据结构和算法.docx

Java数据结构和算法.docx

《Java数据结构和算法.docx》由会员分享，可在线阅读，更多相关《Java数据结构和算法.docx（56页珍藏版）》请在冰点文库上搜索。

Java数据结构和算法

Java数据结构和算法

一、数组于简单排序1

二、栈与队列4

三、链表7

四、递归22

五、哈希表25

六、高级排序25

七、二叉树25

八、红—黑树26

九、堆36

十、带权图39

一、数组于简单排序

数组

数组（array）是相同类型变量的集合，可以使用共同的名字引用它。

数组可被定义为任何类型，可以是一维或多维。

数组中的一个特别要素是通过下标来访问它。

数组提供了一种将有联系的信息分组的便利方法。

一维数组

一维数组（one-dimensionalarray）实质上是相同类型变量列表。

要创建一个数组，你必须首先定义数组变量所需的类型。

通用的一维数组的声明格式是：

typevar-name[];

获得一个数组需要2步。

第一步，你必须定义变量所需的类型。

第二步，你必须使用运算符new来为数组所要存储的数据分配内存，并把它们分配给数组变量。

这样Java中的数组被动态地分配。

如果动态分配的概念对你陌生，别担心，它将在本书的后面详细讨论。

数组的初始化（arrayinitializer）就是包括在花括号之内用逗号分开的表达式的列表。

逗号分开了数组元素的值。

Java会自动地分配一个足够大的空间来保存你指定的初始化元素的个数，而不必使用运算符new。

Java严格地检查以保证你不会意外地去存储或引用在数组范围以外的值。

Java的运行系统会检查以确保所有的数组下标都在正确的范围以内（在这方面，Java与C/C++从根本上不同，C/C++不提供运行边界检查）。

多维数组

在Java中，多维数组（multidimensionalarrays）实际上是数组的数组。

你可能期望，这些数组形式上和行动上和一般的多维数组一样。

然而，你将看到，有一些微妙的差别。

定义多维数组变量要将每个维数放在它们各自的方括号中。

例如，下面语句定义了一个名为twoD的二维数组变量。

inttwoD[][]=newint[4][5];

简单排序

简单排序中包括了：

冒泡排序、选择排序、插入排序；

1.冒泡排序的思想：

假设有N个数据需要排序，则从第0个数开始，依次比较第0和第1个数据，如果第0个大于第1个则两者交换，否则什么动作都不做，继续比较第1个第2个…，这样依次类推，直至所有数据都“冒泡”到数据顶上。

冒泡排序的的java代码：

PublicvoidbubbleSort（）

{

intin,out;

for（out=nElems-1;out>0;out--）

for（in=0;in

{

If（a[in]>a[in+1]）

Swap（in,in+1）;

}

}

算法的不变性：

许多算法中，有些条件在算法执行过程中始终是不变的。

这些条件被称为算法的不变性，如果不变性不为真了，则标记出错了；

冒泡排序的效率O（N*N），比较N*N/2，交换N*N/4；

2.选择排序的思想：

假设有N条数据，则暂且标记第0个数据为MIN（最小），使用OUT标记最左边未排序的数据，然后使用IN标记第1个数据，依次与MIN进行比较，如果比MIN小，则将该数据标记为MIN，当第一轮比较完后，最终的MIN与OUT标记数据交换，依次类推；

选择排序的java代码：

PublicvoidselectSort（）

{

Intin,out,min;

For（out=0;out

{

Min=out;

For（in=out+1;in

If（a[in]

Min=in;

Swap（out,min）;

}

}

选择排序的效率：

O（N*N），比较N*N/2，交换

3.插入排序的思想：

插入排序是在部分数据有序的情况下，使用OUT标记第一个无序的数据，将其提取保存到一个中间变量temp中去，使用IN标记空位置，依次比较temp中的值与IN-1的值，如果IN-值大于temp的值，则后移，直到遇到第一个比temp小的值，在其下一个位置插入；

插入排序的java代码：

PublicvoidInsertionSort（）

{

Intin,out;

For（out=1;out

{

Longtemp=a[out]

In=out;

While（in>0&&a[in-1]>temp）

{

A[in]=a[in-1];

--in;

}

A[in]=temp;

}

}

插入排序的效率：

O（N*N）,比较N*N/4，复制N*N/4；插入排序在随机数的情况下，比冒泡快一倍，比选择稍快；在基本有序的数组中，插入排序几乎只需要O（N）；在逆序情况下，并不比冒泡快；

二、栈与队列

1、栈的定义

   　栈（Stack）是限制仅在表的一端进行插入和删除运算的线性表。

（1）通常称插入、删除的这一端为栈顶（Top），另一端称为栈底（Bottom）。

（2）当表中没有元素时称为空栈。

　　（3）栈为后进先出（LastInFirstOut）的线性表，简称为LIFO表。

   　栈的修改是按后进先出的原则进行。

每次删除（退栈）的总是当前栈中"最新"的元素，即最后插入（进栈）的元素，而最先插入的是被放在栈的底部，要到最后才能删除。

　　【示例】元素是以a1，a2，…，an的顺序进栈，退栈的次序却是an，an-1，…，a1。

2、栈的基本运算

（1）InitStack（S）

   　构造一个空栈S。

（2）StackEmpty（S）

   　判栈空。

若S为空栈，则返回TRUE，否则返回FALSE。

（3）StackFull（S）

   　判栈满。

若S为满栈，则返回TRUE，否则返回FALSE。

注意：

该运算只适用于栈的顺序存储结构。

（4）Push（S，x）

   　进栈。

若栈S不满，则将元素x插入S的栈顶。

（5）Pop（S）

   　退栈。

若栈S非空，则将S的栈顶元素删去，并返回该元素。

（6）StackTop（S）

   　取栈顶元素。

若栈S非空，则返回栈顶元素，但不改变栈的状态。

队列的定义及基本运算

1、定义

   　队列（Queue）是只允许在一端进行插入，而在另一端进行删除的运算受限的线性表

（1）允许删除的一端称为队头（Front）。

（2）允许插入的一端称为队尾（Rear）。

　　（3）当队列中没有元素时称为空队列。

　　（4）队列亦称作先进先出（FirstInFirstOut）的线性表，简称为FIFO表。

   　队列的修改是依先进先出的原则进行的。

新来的成员总是加入队尾（即不允许"加塞"），每次离开的成员总是队列头上的（不允许中途离队），即当前"最老的"成员离队。

　【例】在队列中依次加入元素a1，a2，…，an之后，a1是队头元素，an是队尾元素。

退出队列的次序只能是a1，a2，…，an。

2、队列的基本逻辑运算

（1）InitQueue（Q）

   　置空队。

构造一个空队列Q。

（2）QueueEmpty（Q）

   　判队空。

若队列Q为空，则返回真值，否则返回假值。

（3）QueueFull（Q）

   　判队满。

若队列Q为满，则返回真值，否则返回假值。

 注意：

此操作只适用于队列的顺序存储结构。

（4）EnQueue（Q，x）

   　若队列Q非满，则将元素x插入Q的队尾。

此操作简称入队。

（5）DeQueue（Q）

   　若队列Q非空，则删去Q的队头元素，并返回该元素。

此操作简称出队。

（6）QueueFront（Q）

   　若队列Q非空，则返回队头元素，但不改变队列Q的状态。

三、链表

1．链结点

在链表中，每个数据项都被包含在‘点“中，一个点是某个类的对象，这个类可认叫做LINK。

因为一个链表中有许多类似的链结点，所以有必要用一个不同于链表的类来表达链结点。

每个LINK对象中都包含一个对下一个点引用的字段（通常叫做next）但是本身的对象中有一个字段指向对第一个链结点的引用

单链表

用一组地址任意的存储单元存放线性表中的数据元素。

　　以元素（数据元素的映象）

　　+指针（指示后继元素存储位置）

　　=结点

　　（表示数据元素或数据元素的映象）

　　以“结点的序列”表示线性表

称作线性链表（单链表）　　

　　单链表是一种顺序存取的结构，为找第i个数据元素，必须先找到第i-1个数据元素。

　　因此，查找第i个数据元素的基本操作为：

移动指针，比较j和i

　　1、链接存储方法

　　链接方式存储的线性表简称为链表（LinkedList）。

　　链表的具体存储表示为：

　　①用一组任意的存储单元来存放线性表的结点（这组存储单元既可以是连续的，也可以是不连续的）

　　②链表中结点的逻辑次序和物理次序不一定相同。

为了能正确表示结点间的逻辑关系，在存储每个结点值的同时，还必须存储指示其后继结点的地址（或位置）信息（称为指针（pointer）或链（link））

　　注意：

　　链式存储是最常用的存储方式之一，它不仅可用来表示线性表，而且可用来表示各种非线性的数据结构。

　　2、链表的结点结构

　　┌──┬──┐

　　│data│next│

　　└──┴──┘

　　data域--存放结点值的数据域

　　next域--存放结点的直接后继的地址（位置）的指针域（链域）

　　注意：

　　①链表通过每个结点的链域将线性表的n个结点按其逻辑顺序链接在一起的。

　　②每个结点只有一个链域的链表称为单链表（SingleLinkedList）。

　　【例】线性表（bat，cat，eat，fat，hat，jat，lat，mat）的单链表示如示意图

　　3、头指针head和终端结点指针域的表示

　　单链表中每个结点的存储地址是存放在其前趋结点next域中，而开始结点无前趋，故应设头指针head指向开始结点。

　　注意：

　　链表由头指针唯一确定，单链表可以用头指针的名字来命名。

　　【例】头指针名是head的链表可称为表head。

　　终端结点无后继，故终端结点的指针域为空，即NULL。

　　4、单链表的一般图示法

　　由于我们常常只注重结点间的逻辑顺序，不关心每个结点的实际位置，可以用箭头来表示链域中的指针，线性表（bat，cat，fat，hat，jat，lat，mat）的单链表就可以表示为下图形式。

　　5、单链表类型描述

　　typedefcharDataType;//假设结点的数据域类型为字符

　　typedefstructnode{//结点类型定义

　　DataTypedata;//结点的数据域

　　structnode*next;//结点的指针域

　　}ListNode

　　typedefListNode*LinkList;

　　ListNode*p;

　　LinkListhead;

　　注意：

　　①*LinkList和ListNode是不同名字的同一个指针类型（命名的不同是为了概念上更明确）

　　②*LinkList类型的指针变量head表示它是单链表的头指针

　　③ListNode类型的指针变量p表示它是指向某一结点的指针

　　6、指针变量和结点变量

　　┌────┬────────────┬─────────────┐

　　│　│　指针变量　│　结点变量│

　　├────┼────────────┼─────────────┤

　　│定义│在变量说明部分显式定义│在程序执行时，通过标准│

　　│││函数malloc生成│

　　├────┼────────────┼─────────────┤

　　│取值│非空时，存放某类型结点│实际存放结点各域内容│

　　││的地址││

　　├────┼────────────┼─────────────┤

　　│操作方式│通过指针变量名访问│通过指针生成、访问和释放│

　　└────┴────────────┴─────────────┘

　　①生成结点变量的标准函数

　　p=（ListNode*）malloc（sizeof（ListNode））；

　　//函数malloc分配一个类型为ListNode的结点变量的空间,并将其首地址放入指针变量p中

　　②释放结点变量空间的标准函数

　　free（p）；//释放p所指的结点变量空间

　　③结点分量的访问

　　利用结点变量的名字*p访问结点分量

　　方法一：

（*p）.data和（*p）.next

　　方法二：

p-﹥data和p-﹥next

　　④指针变量p和结点变量*p的关系

　　指针变量p的值——结点地址

　　结点变量*p的值——结点内容

　　（*p）.data的值——p指针所指结点的data域的值

　　（*p）.next的值——*p后继结点的地址

　　*（（*p）.next）——*p后继结点

　　注意：

　　①若指针变量p的值为空（NULL），则它不指向任何结点。

此时，若通过*p来访问结点就意味着访问一个不存在的变量，从而引起程序的错误。

　　②有关指针类型的意义和说明方式的详细解释

　　可见，在链表中插入结点只需要修改指针。

但同时，若要在第i个结点之前插入元素，修改的是第i-1个结点的指针。

　　因此，在单链表中第i个结点之前进行插入的基本操作为:

找到线性表中第i-1个结点，然后修改其指向后继的指针。

双端链表

双端链表与传统的链表非常相似，但是它有一个新增的特性：

即对最后一个链结点的引用，就像对第一个链结点的引用一样。

对最后一个链结点的引用允许像在表头一样，在表尾直接插入一个链结点。

当然，仍然可以在普通的单链表的表尾插入一个链结点，方法是遍历整个链表直到到达表尾，但是这种方法效率很低。

对最后一个链结点的引用允许像在表头一样，在表尾直接插入一个链结点。

当然，仍然可以在普通的单链表的表尾插入一个链结点，方法是遍历整个链表直到到达表尾，但是这种方法效率很低。

像访问表头一样访问表尾的特性，使双端链表更适合于一些普通链表不方便操作的场合，队列的实现就是这样一个情况。

下面是一个双端链表的例子。

classLink3{

publiclongdData;

publicLink3next;

//............................

publicLink3（longd）{

dData=d;

}

//............................

publicvoiddisplayLink（）{

System.out.print（dData+""）;

}

}

///////////////////////////////////

classFirstLastList{

privateLink3first;

privateLink3last;

//............................

publicFirstLastList（）{

first=null;

last=null;

}

//.............................

publicbooleanisEmpty（）{

returnfirst==null;

}

//.............................

publicvoidinsertFirst（longdd）{

Link3newLink=newLink3（dd）;

if（isEmpty（））

last=newLink;

newLink.next=first;

first=newLink;

}

//...........................

publicvoidinsertLast（longdd）{

Link3newLink=newLink3（dd）;

if（isEmpty（））

first=newLink;

else

last.next=newLink;

last=newLink;

}

//...............................

publiclongdeleteFirst（）{

longtemp=first.dData;

if（first.next==null）

last=null;

first=first.next;

returntemp;

}

//.......................................

publicvoiddisplayList（）{

System.out.print（"List（first-->last）:

"）;

Link3current=first;

while（current!

=null）{

current.displayLink（）;

current=current.next;

}

System.out.println（""）;

}

}

/////////////////////////////////////

publicclassFirstLastApp{

publicstaticvoidmain（String[]args）{

FirstLastListtheList=newFirstLastList（）;

theList.insertFirst（22）;

theList.insertFirst（44）;

theList.insertFirst（66）;

theList.insertLast（11）;

theList.insertLast（33）;

theList.insertLast（55）;

theList.displayList（）;

theList.deleteFirst（）;

theList.deleteFirst（）;

theList.displayList（）;

}

}

为了简单起见，在这个程序中，把每个链结点中的数据字段个数从两个压缩到一个。

这更容易显示链结点的内容。

（记住，在一个正式的程序中，可能会有非常多的数据字段，或者对另外一个对象的引用，那个对象也包含很多数据字段。

）

这个程序在表头和表尾各插入三个链点，显示插入后的链表。

然后删除头两个链结点，再次显示。

注意在表头重复插入操作会颠倒链结点进入的顺序，而在表尾的重复插入则保持链结点进入的顺序。

双端链表类叫做FirstLastList。

它有两个项，first和last，一个指向链表中的第一个链结点，另一个指向最后一个链结点。

如果链表中只有一个链结点，first和last就都指向它，如果没有链结点，两者都为Null值。

这个类有一个新的方法insertLast（），这个方法在表尾插入一个新的链结点。

这个过程首先改变last.next，使其指向新生成的链结点，然后改变last，使其指向新的链结点。

插入和删除方法和普通链表的相应部分类似。

然而，两个插入方法都要考虑一种特殊情况，即插入前链表是空的。

如果isEmpty（）是真，那么insertFirst（）必须把last指向新的链结点，insertLast（）也必须把first指向新的链结点。

如果用insertFirst（）方法实现在表头插入，first就指向新的链结点，用insertLast（）方法实现在表尾插入，last就指向新的链结点。

如果链表只有一个链结点，那么多表头删除也是一种特殊情况：

last必须被赋值为null值。

不幸的是，用双端链表也不能有助于删除最后一个链结点，因为没有一个引用指向倒数第二个链结点。

如果最后一个链结点被删除，倒数第二个链结点的Next字段应该变成Null值。

为了方便的删除最后一个链结点，需要一个双向链表。

（当然，也可以遍历整个链表找到最后一个链结点，但是那样做效率不是很高。

）

有序链表

在有序链表中，数据是按照关键值有序排列的。

有序链表的删除常常是只限于删除在链表头部的最小链结点。

不过，有时也用Find（）方法和Delete（）方法在整个链表中搜索某一特定点。

一般，在大多数需要使用有序数组的场合也可以使用有序链表。

有序链表优于有序数组的地方是插入的速度，另外链表可以扩展到全部有效的使用内存，而数组只能局限于一个固定的大小中。

但是，有序链表实现起来比有序数组更困难一些。

后而将看到一个有序链表的应用：

为数据排序。

有序链表也可以用于实现优先级队列，尽管堆是更常用的实现方法。

在有序链表中插入一个数据项的Java代码

为了在一个有序链表中插入数据项，算法必须首先搜索链表，直到找到合适的位置：

它恰好在第一个比它大的数据项的前面。

当算法找到了要插入的位置，用通常的方式插入数据项：

把新链结点的Next字段指向下一个链结点，然后把前一个链结点的Next字段改为指向新的链结点。

然而，需要考虑一些特殊情况：

链结点有可以插在表头，或者插在表尾。

看一下这段代码：

Publicvoidinsert（longkey）{

LinknewLink=newLink（key）;

Linkprevious=null;

Linkcurrent=first;

While（current!

=null&&key>current.dData）{

Previous=current;

Current=current.next;

}

If（previous==null）

First=newLink;

Else

Previous.next=newLink;

newLink.next=current;

}

在链表上移动时，需要用一个previous引用，这样才能把前一个链结点的Next字段指向新的链结点。

创建新链结点后，把current变量设为first，准备搜索正确的插入点。

这时也把previous设为Null值，这步操作很重要，因为后面要用这个Null值判断是否仍在表头。

While循环和以前用来搜索插入点的代码类似，但是有一个附加的条件。

如果当前检查的链结点的关键值不再小于待插入的链结点的关键值，则循环结束；这是最常见的情况，即新关键值插在链表中部的某个地方。

然而，如果current为Null值，while循环也会停止。

这种情况发生在表尾，或者链表为空时。

如果current在表头或者链表为空，previous将为Null值；所以让first指向新的链结点。

否则current处在链表中部或结尾，就使previous的next字段指向新的链结点。

不论哪种情况、都让新链结点的Next字段指向current。

如果在表尾，current为Null值，则新链结点的Next字段也本应该设为这个值（Null）。

下面是有序链表的程序

SortedList.java程序实现了一个SortedList类，它拥有insert（）、remove（）和dis