Flyingis

Talking and thinking freely !
Flying in the world of GIS !
随笔 - 156, 文章 - 16, 评论 - 589, 引用 - 0
数据加载中……

理解数组和链表的最基本特性

作者:Flyingis

 

数组和链表是数据结构中老生常谈的问题,在指针或是引用这些概念出来之前,数组就能用来实现链表的功能。这里所说的链表指的就是用指针或对象的引用来设计的链表。

在实际的应用开发中,数组由于它天生的种种特性(参考Java容器分析数组》),更多的会被开发人员所想到用到,但所有的数据结构都有它特定的适用场合。众所周知,数组和链表最大的区别在于,使用数组能够快速访问数组中的每个元素,而使用链表可以方便的操纵每个数据项。下面通过两个很有趣的例子说明了它们各自的区别与优势。

虽然在JDKJava提供了List接口及其接口的实现(ArrayList/LinkedList)对链表数据结构提供了有力的支持,具体可以参考Java容器分析—List和Set但下面数学上关于Josephus问题的实现仅使用了自定义的最简单的链表结构。

/**

 * 根据命令行输入的N值,计算出所有小于N的素数

 * 是素数将数组元素值设为true,否则设为false

 */

class ArrayApp {

  public static void main(String[] args) {

int N = Integer.parseInt(args[0]);

boolean[] a = new boolean[N];

for (int i = 2; i < N; i++)

  a[i] = true;

for (int i = 2; i < N; i++)

  if (a[i] != false)

    for (int j = i; j*i < N; j++)

      a[i*j] = false;

for (int i = 2; i < N; j++)

  if (a[i])

    System.out.println(“” + i);

}

}

/**

 * N个有编号的小球围成一圈,每个M-1个就拿去一个小球,计算最后剩下的球的位置

 */

class LinkApp {

  static class Node {

int value;

Node next;

Node (int v) { v = value; }

}

public static void main(String[] args) {

  int N = Integer.parseInt(args[0]);

  int M = Integer.parseInt(args[1]);

  Node first = new Node(1);

  Node x = first;

  for (int i = 2; i <= N; i++)

    x = (x.next = new Node(i));

  x.next = first;

  while (x != x.next) {

    for (int i = 1; i < M; i++)

      x = x.next;

    x.next = x.next.next;

}

System.out.println(“最后剩下的小球:” + x.value);

}

}

posted on 2006-01-24 23:42 Flyingis 阅读(2125) 评论(0)  编辑  收藏 所属分类: Algorithm


只有注册用户登录后才能发表评论。


网站导航: