数组、栈 、队列、链表、树、堆 、图、散列表 。
1:数组是计算机编程语言上,对于“Array”的中文称呼,是用于储存多个相同类型数据的集合。
2:栈是限定仅在表尾进行插入和删除操作的线性表,栈者,存储货物或供旅客住宿的地方,可引申为仓库、中转站,引入到计算机领域里,就是指数据暂时存储的地方,所以才有进栈、出栈的说法。
3:一种特殊的线性表,它只允许在表的前端进行删除操作,而在表的后端进行插入操作。
4:链表,一种物理存储单元上非连续、非顺序的存储结构,数据元素的逻辑顺序是通过链表中的指针链接次序实现的。
5:哈希表,是根据关键码值而直接进行访问的数据结构。也就是说,它通过把关键码值映射到表中一个位置来访问记录,以加快查找的速度。
JAVA数据结构有以下几种:
1、List:
List是有序的Collection,使用此接口能够精确的控制每个元素插入的位置。用户能够使用索引(元素在List中的位置,类似于数组下 >标)来访问List中的元素,这类似于Java的数组。
2、Vector:
基于数组(Array)的List,其实就是封装了数组所不具备的一些功能方便我们使用,所以它难易避免数组的限制,同时性能也不可能超越数组。
另外很重要的一点就是Vector是线程同步的(sychronized)的,这也是Vector和ArrayList 的一个的重要区别。
3、ArrayList:
同Vector一样是一个基于数组上的链表,但是不同的是ArrayList不是同步的。所以在性能上要比Vector好一些,但是当运行到多线程环境中时,可需要自己在管理线程的同步问题。
4、LinkedList:
LinkedList不同于前面两种List,它不是基于数组的,所以不受数组性能的限制。 它每一个节点(Node)都包含两方面的内容:节点本身的数据(data),下一个节点的信息(nextNode)。
所以当对LinkedList做添加,删除动作的时候就不用像基于数组的ArrayList一样,必须进行大量的数据移动。只要更改nextNode的相关信息就可以实现了,这是LinkedList的优势。
5、HashSet:
虽然Set同List都实现了Collection接口,但是他们的实现方式却大不一样。List基本上都是以Array为基础。
但是Set则是在 HashMap的基础上来实现的,这就是Set和List的根本区别。HashSet的存储方式是把HashMap中的Key作为Set的对应存储项。
6、HashMap:
基于哈希表的 Map 接口的实现。此实现提供所有可选的映射操作,并允许使用 null 值和 null 键。(除了不同步和允许使用 null 之外,HashMap 类与 Hashtable 大致相同。)此类不保证映射的顺序,特别是它不保证该顺序恒久不变。
7、HashTable:
Hashtable 是一个散列表,它存储的内容是键值对(key-value)映射。Hashtable 继承于Dictionary,实现了Map、Cloneable、java.io.Serializable接口。
Hashtable 的函数都是同步的,这意味着它是线程安全的。它的key、value都不可以为nul
package tree
import java.util.LinkedList
import java.util.List
/**
* 功能:把一个数组的值存入二叉树中,然后进行3种方式的遍历
*
* 参考资料0:数据结构(C语言版)严蔚敏
*
* 参考资料1:http://zhidao.baidu.com/question/81938912.html
*
* 参考资料2:http://cslibrary.stanford.edu/110/BinaryTrees.html#java
*
* @author [email protected] @date: 2011-5-17
*
*/
public class BinTreeTraverse2 {
private int[] array = { 1, 2, 3, 4, 5, 6, 7, 8, 9 }
private static List<Node>nodeList = null
/**
* 内部类:节点
*
* @author [email protected] @date: 2011-5-17
*
*/
private static class Node {
Node leftChild
Node rightChild
int data
Node(int newData) {
leftChild = null
rightChild = null
data = newData
}
}
public void createBinTree() {
nodeList = new LinkedList<Node>()
// 将一个数组的值依次转换为Node节点
for (int nodeIndex = 0nodeIndex <array.lengthnodeIndex++) {
nodeList.add(new Node(array[nodeIndex]))
}
// 对前lastParentIndex-1个父节点按照父节点与孩子节点的数字关系建立二叉树
for (int parentIndex = 0parentIndex <array.length / 2 - 1parentIndex++) {
// 左孩子
nodeList.get(parentIndex).leftChild = nodeList
.get(parentIndex * 2 + 1)
// 右孩子
nodeList.get(parentIndex).rightChild = nodeList
.get(parentIndex * 2 + 2)
}
// 最后一个父节点:因为最后一个父节点可能没有右孩子,所以单独拿出来处理
int lastParentIndex = array.length / 2 - 1
// 左孩子
nodeList.get(lastParentIndex).leftChild = nodeList
.get(lastParentIndex * 2 + 1)
// 右孩子,如果数组的长度为奇数才建立右孩子
if (array.length % 2 == 1) {
nodeList.get(lastParentIndex).rightChild = nodeList
.get(lastParentIndex * 2 + 2)
}
}
/**
* 先序遍历
*
* 这三种不同的遍历结构都是一样的,只是先后顺序不一样而已
*
* @param node
*遍历的节点
*/
public static void preOrderTraverse(Node node) {
if (node == null)
return
System.out.print(node.data + " ")
preOrderTraverse(node.leftChild)
preOrderTraverse(node.rightChild)
}
/**
* 中序遍历
*
* 这三种不同的遍历结构都是一样的,只是先后顺序不一样而已
*
* @param node
*遍历的节点
*/
public static void inOrderTraverse(Node node) {
if (node == null)
return
inOrderTraverse(node.leftChild)
System.out.print(node.data + " ")
inOrderTraverse(node.rightChild)
}
/**
* 后序遍历
*
* 这三种不同的遍历结构都是一样的,只是先后顺序不一样而已
*
* @param node
*遍历的节点
*/
public static void postOrderTraverse(Node node) {
if (node == null)
return
postOrderTraverse(node.leftChild)
postOrderTraverse(node.rightChild)
System.out.print(node.data + " ")
}
public static void main(String[] args) {
BinTreeTraverse2 binTree = new BinTreeTraverse2()
binTree.createBinTree()
// nodeList中第0个索引处的值即为根节点
Node root = nodeList.get(0)
System.out.println("先序遍历:")
preOrderTraverse(root)
System.out.println()
System.out.println("中序遍历:")
inOrderTraverse(root)
System.out.println()
System.out.println("后序遍历:")
postOrderTraverse(root)
}
}