数据结构是计算机存储、组织数据的方式。数据结构是指相互之间存在一种或多种特定关系的数据元素的集合。通常情况下，精心选择的数据结构可以带来更高的运行或者存储效率。数据结构往往同高效的检索
算法和索引技术有关。
百度百科如是说。。
至于我之前对数据结构的看法，也就是用来存储数据的一个载体，那么与专业这么一比也就太浅薄了。。
不管怎样，至少懂得怎么来用是基础吧。
废话不多说，先写数组的
队列，数组队列的优势在于查找快，缺点是增删慢。
1. 数组队列
构造方法（设定初始数组长度）：
class="java" name="code"> /**
* 有参构造
* @param initlength
*/
public MyArray(int initlength){
this.initlength = initlength;
}
/**
* 无脑无参构造
*/
public MyArray(){
this(50);
}
然后写方法之前先些
注解，要实现点什么功能：
/**
* 往数组里面添加元素的方法
* 通过新建一个原数组大小+1大小的数组实现添加
* @param s
*/
public void add(String s) {
}
/**
* 从数组里面取出元素的方法
* @param index
*/
public String get(int index){
}
/**
* 获取数组的大小的方法
* @return arr.length
*/
public int size(){
}
/**
* 删除数组指定元素
* 按照指定的数组下标删除,并返回被删除的元素
* @param index
*/
public String delete(int index){
}
/**
* 清空数组，使得数组初始化为一个空数组
*/
public void init(){
}
/**
* 删除数组指定元素
* 按照指定的元素数据删除，并返回被删除的元素
* @param s
*/
public String delete(String s){
}
/**
* 将一个指定元素插入指定下标的数组位置中
* @param s,index
*/
public void jump(String s,int index){
}
然后才是具体的实现：
/**
* 往数组里面添加元素的方法
* 通过新建一个原数组大小+1大小的数组实现添加
* @param s
*/
public void add(String s) {
String temp [] = new String [arr.length+1];
for(int i=0;i<arr.length;i++)
temp[i] = arr[i];
temp[arr.length] = s;
arr = temp;
}
/**
* 从数组里面取出元素的方法
* @param index
*/
public String get(int index){
if(index < arr.length)
return arr[index];
else
return null;
}
/**
* 获取数组的大小的方法
* @return arr.length
*/
public int size(){
return arr.length;
}
/**
* 删除数组指定元素
* 按照指定的数组下标删除,并返回被删除的元素
* @param index
*/
public String delete(int index){
String del = arr[index];
String [] temp = new String[arr.length-1];
for(int i=0;i<temp.length;i++){
if(i<index)
temp[i] = arr[i];
else
temp[i] = arr[i+1];
}
arr = temp;
return del;
}
/**
* 清空数组，使得数组初始化为一个空数组
*/
public void init(){
arr = new String [] {};
}
/**
* 删除数组指定元素
* 按照指定的元素数据删除，并返回被删除的元素
* @param s
*/
public String delete(String s){
String del = null;
int j=0,num=0;
for(int i=0;i<arr.length;i++){
if(arr[i].equals(s))
num++;
}
String [] temp = new String[arr.length-num];
for(int i=0;i<temp.length;i++){
if(arr[j].equals(s)){
del = arr[j];
j++;
temp[i] = arr[j];
j++;
}
else{
temp[i] = arr[j];
j++;
}
}
arr = temp;
return del;
}
/**
* 将一个指定元素插入指定下标的数组位置中
* @param s,index
*/
public void jump(String s,int index){
String temp [] = new String [arr.length+1];
for(int i=0;i<temp.length;i++){
if(i<index)
temp[i] = arr[i];
else if(i==index)
temp[i] = s;
else
temp[i] = arr[i-1];
System.out.println(temp[i]);
}
arr = temp;
}
关于数组队列这一块，为了给用户提供更好更便利的
接口，使用
泛型的话会更好，省去改变量类型的工作，然后还可以做的优化的就是每次扩充的数组长度。
2. 链表队列
链表队列的优势是增删快，查找慢
链表队列的数据存储方式是离散的，而非数组队列的连续的物理空间存储。
下面是队列的建立：
首先是节点类：
public class Node {
public Object o;
public Node next;
}
随着对编程的规范化，对程序的优化，考虑到的情况也对了，所以对于链表为空，索引值越界之类的情况也做出了处理。
public class nodeQuene {
private Node root;
private Node end;
private int count;
/**
* 在链表尾追加节点
* */
public void add(Object o){
//节点个数增加
count++;
Node next = new Node();
if(root == null){//若根节点为空
root = new Node();
root.o = o;
end = root;
System.out.println(root.o+"已经添加");
}else{//若根节点不为空
next.o = o;
end.next = next;
end = end.next;
System.out.println(next.o+"已经添加");
}
}
/**
* 非追加，在表的指定位置增加一个节点,若为空表则为追加
* */
public void add(int index,Object o){
if(root == null)//如果为空表
add(o);
//如果指定的位置比表尾还长，则不能添加
if(index > count+1)
return;
Node newo = new Node();
newo.o = o;
Node temp = root;
while(index > 2){
temp = temp.next;
index--;
}
newo.next = temp.next;
temp.next = newo;
count++;
}
/**
* 删除表的指定位置的节点
* */
public void delete(int index){
if(index == 1){//则为删除表头
delete();
return;
}
if(root == null)//如果为空表
return;
//如果指定的位置比表尾还长，则不能删除
if(index > count)
return;
Node temp = root;
while(index > 2){
temp = temp.next;
index--;
}
temp.next = temp.next.next;
count--;
}
/**
* 删除指定数据的节点
* */
public void delete(Object o){
if(root == null)//如果为空表
return;
Node temp = root;
if(temp.o.equals(o))//则为删除表头
delete();
for(int i=count;i>1;i--){
if(temp.next.o.equals(o))
temp.next = temp.next.next;
else
temp = temp.next;
}
count--;
}
/**
* 删除表头
* */
private void delete(){
if(root == null)//如果表头本为空
return;
root = root.next;
count--;
}
/**
* 清空链表
* */
public void empty(){
root = null;
}
/**
* 获得链表节点个数
*/
public int size(){
return count;
}
/**
* 遍历链表
* */
public void travel(){
int Size = 0;
Node no = root;
while(Size < size()){
System.out.println(no.o+"已经遍历");
no = no.next;
Size++;
}
}
/**
* 获得和索引值相等的标号的节点
* */
public Node get(int index){
//若搜引值大于节点个数
if(index > size())
return null;
//若传入的根节点为空
if(root == null)
return null;
Node no = root;
for(int i=1;i<=size();i++){
if(i==index){
return no;
}
else
no = no.next;
}
return null;
}
/**
* 获得根节点
* */
public Node getRoot(){
return root;
}
}
在这里，由于删除或者添加会有一些特殊的位置，所以在这里用
重载做了些处理。
3. hashu.html" target="_blank">二叉树
上面讲了两个线性的队列，现在看下非线性的树（二叉树）：
首先是二叉树的节点类：
public class Node {
public int data;
public Node leftchild;
public Node rightchild;
public Node(int data){
this.data = data;
}
}
这里由于只实现了增和查的功能，所以这个二叉树还需完善。
public class Tree {
private Node root;
/**
* 添加树节点
*/
public void add(int data){
Node newNode = new Node(data);
if(root == null){//如果根节点为空
root = newNode;
}
else
addRecursion(root,data);
}
/**
* 递归寻找添加节点位置，并添加
*/
private void addRecursion(Node fatherNode,int data){
//如果传入的节点为空
if(fatherNode == null)
return;
Node newNode = new Node(data);
//先判断应挂在左枝还是右枝
if(data <= fatherNode.data ){//挂在左边
if(fatherNode.leftchild == null)//判断左枝是否为空，若是则直接挂上
fatherNode.leftchild = newNode;
else//如果不为空，则递归
addRecursion(fatherNode.leftchild,data);
}
else{//挂在右边
if(fatherNode.rightchild == null)//判断右枝是否为空，若是则直接挂上
fatherNode.rightchild = newNode;
else//如果不为空，则递归
addRecursion(fatherNode.rightchild,data);
}
}
/**
* 先序遍历树
*/
public void pretravel(){
//如果根节点为空，不能遍历
if(root == null)
return;
//传入根节点递归调用先序遍历
Dpretravel(root);
}
/**
* 递归先序遍历
*/
public void Dpretravel(Node nowNode){
if(nowNode == null)
return;
//遍历当前节点
System.out.println("这个节点已经遍历,data ="+nowNode.data);
if(nowNode.leftchild != null)
Dpretravel(nowNode.leftchild);
Dpretravel(nowNode.rightchild);
}
/**
* 后序遍历
*/
public void postravel(){
//如果根节点为空，不能遍历
if(root == null)
return;
//传入根节点递归调用后序遍历
Dpostravel(root);
}
/**
* 递归后序遍历
*/
public void Dpostravel(Node nowNode){
if(nowNode == null)
return;
if(nowNode.leftchild != null)
Dpostravel(nowNode.leftchild);
if(nowNode.rightchild != null)
Dpostravel(nowNode.rightchild);
//遍历当前节点
System.out.println("这个节点已经遍历,data ="+nowNode.data);
}
/**
* 中序遍历
*/
public void midtravel(){
//如果根节点为空，不能遍历
if(root == null)
return;
//传入根节点递归调用中序遍历
Dmidtravel(root);
}
/**
* 递归中序遍历
*/
public void Dmidtravel(Node nowNode){
if(nowNode == null)
return;
if(nowNode.leftchild != null){
Dpostravel(nowNode.leftchild);
//遍历当前节点
System.out.println("这个节点已经遍历,data ="+nowNode.data);}
if(nowNode.rightchild != null)
Dpostravel(nowNode.rightchild);
}
}
可以看到，我用的每个方法都用了递归，开始
打算只是写增和三种遍历一共四个方法而已的，但是好像递归起来有些乱，所以我每个方法都写了个入口方法，然后才是递归。
当然，上面的队列都用泛型的话会更好。对于数据结构这一块才算刚刚入门，还有更多精妙的设计方式有待探讨，使这个队列能应对更多种情况的发生仍然能正常发挥作用。
相关文章
