编程经验谈JAVA Web第11章细说Java Web常用算法20例

编程经验谈JAVA Web第11章细说Java Web常用算法20例

第11章细说Java Web常用算法20例

算法01 单线联系——单向链表算法

链表是一种线性数据结构，使用它能动态的存储一种结构数据。链表是n个数据元素的有限序列，其元素需要自己定义，既可以是一个整数或一个字符串，也可以是一个复杂的记录类型。在计算机程序设计中，经常会使用到链表算法，本节将详细介绍单向链表的相关知识。

算法点拨

链表是一种重要的数据结构，该结构由节点组成。每个节点包含两部分数据，第一部分是节点本身的数据，第二部分是指向下一个节点的指针。对于单向链表，链表中存在两个特殊的节点，分别为“头节点”和“尾节点”。头节点本身没有数据，只存储下一个节点的指针，尾节点只存储数据。单向链表结构如图11.01所示。

编程经验谈JAVA Web第11章细说Java Web常用算法20例

Head

5471

4512

5674

8778

图11.01 单向链表结构

实现链表首先需要实现一个节点类，关键代码如下：

public

编程经验谈JAVA Web第11章细说Java Web常用算法20例

class ListNode {

public ListNode Next; //指向下一节点的指针与域 public int Value; //值 public ListNode(int NewValue) { Value=NewValue; } }

说明：

上述代码中，公共成员Value用于储存节点本身的数据，Next用于存储下一个节点的指针。对于链表的操作，无非是进行节点的查找、插入和删除操作。

1．查找节点

在进行节点查找时，通常根据节点的数据查找节点。要实现节点的查找，首先需要解决的问题就是遍历链表中的所有节点。可以从链表头节点开始，利用循环的方式向下查找，如果当前节点指向的下一个节点不为空，则将下一个节点设置为当前节点。

2．插入节点

插入节点需要考虑两种情况。第一种情况是在链表尾节点处插入节点，这种情况比较简单，只要将当前尾节点的FNextNode（指向下一个节点的指针）指向新插入的节点就可以了。第二种情况是在链表的中间位置插入节点，首先需要确定在哪个节点后插入新的节点，这就应该由用户来确定了，本例中为了演示的需要，笔者将树视图控件中的当前选项设置为当前节点。然后需要记录当前节点的下一个节点（避免发生“脱节”），可以定义一个临时的节点进行记录。

387