package package1;
public interface LList<T> { /** * 判断线性表是否空 * @return */ boolean isEmpty(); /** * 返回线性表长度 * @return */ int length(); /** * 返回第i（i≥0）个元素 * @param i * @return */ T get(int i); /** * 设置第i个元素值为x * @param i * @param x */ void set(int i, T x); /** * 插入x作为第i个元素 * @param i * @param x */ void insert(int i, T x); /** * 在线性表最后插入x元素 * @param x */ void append(T x); /** * 删除第i个元素并返回被删除对象 * @param i * @return */ T remove(int i); /** * 删除线性表所有元素 */ void removeAll(); /** * 查找，返回首次出现的关键字为key元素 * @param key * @return */ T search(T key); }
-------------------------------------------------
package package1;
public class Node<T> { /** * 数据域，保存数据元素 */ public T data; /** * 地址域，引用后继结点 */ public Node<T> next;
/** * 构造结点，data指定数据元素，next指定后继结点 * * @param data * @param next */ public Node(T data, Node<T> next) { this.data = data; this.next = next; }
/** * 构造节点 */ public Node() { this(null, null); }
/** * 返回结点元素值对应的字符串 */ @Override public String toString() { return this.data.toString(); }
/** * 比较两个结点值是否相等，覆盖Object类的equals(obj)方法 */ @SuppressWarnings("unchecked") @Override public boolean equals(Object obj) { return obj == this || obj instanceof Node && this.data.equals(((Node<T>)obj).data); } }
--------------------------------------------------------------------
package package1;
public class SinglyLinkedList<T> implements LList<T> { /** * 头指针，指向单链表的头结点 */ public Node<T> head;
/** * 默认构造方法，构造空单链表 */ public SinglyLinkedList() { // 创建头结点，data和next值均为null this.head = new Node<T>(); }
/** * 由指定数组中的多个对象构造单链表。采用尾插入构造单链表 * 若element==null，Java将抛出空对象异常；若element.length==0，构造空链表 * * @param element */ public SinglyLinkedList(T[] element) { // 创建空单链表，只有头结点 this(); // rear指向单链表最后一个结点 Node<T> rear = this.head; for (int i = 0; i < element.length; i++) { rear.next = new Node<T>(element[i], null); rear = rear.next; } }
/** * 判断单链表是否空，O(1) */ @Override public boolean isEmpty() { return this.head.next == null; }
/** * 返回单链表长度，O(n), 基于单链表遍历算法 */ @Override public int length() { int i = 0; // p从单链表第一个结点开始 Node<T> p = this.head.next; // 若单链表未结束 while (p != null) { i++; // p到达后继结点 p = p.next; } return i; }
/** * 返回第i（≥0）个元素，若i<0或大于表长则返回null，O(n) */ @Override public T get(int i) { if (i >= 0) { Node<T> p = this.head.next; for (int j = 0; p != null && j < i; j++) { p = p.next; }
// p指向第i个结点 if (p != null) { return p.data; } } return null; }
/** * 设置第i（≥0）个元素值为x。若i<0或大于表长则抛出序号越界异常；若x==null，不操作。O(n) */ @Override public void set(int i, T x) { if (x == null) return;
Node<T> p = this.head.next; for (int j = 0; p != null && j < i; j++) { p = p.next; }
if (i >= 0 && p != null) { p.data = x; } else { throw new IndexOutOfBoundsException(i + ""); } }
/** * 插入第i（≥0）个元素值为x。若x==null，不插入。 若i<0，插入x作为第0个元素；若i大于表长，插入x作为最后一个元素。O(n) */ @Override public void insert(int i, T x) { // 不能插入空对象 if (x == null) { return; }
// p指向头结点 Node<T> p = this.head; // 寻找插入位置 for (int j = 0; p.next != null && j < i; j++) { // 循环停止时，p指向第i-1结点或最后一个结点 p = p.next; } // 插入x作为p结点的后继结点，包括头插入（i<=0）、中间/尾插入（i>0） p.next = new Node<T>(x, p.next); }
/** * 在单链表最后添加x对象，O(n) */ @Override public void append(T x) { insert(Integer.MAX_VALUE, x); }
/** * 删除第i（≥0）个元素，返回被删除对象。若i<0或i大于表长，不删除，返回null。O(n) */ @Override public T remove(int i) { if (i >= 0) { Node<T> p = this.head; for (int j = 0; p.next != null && j < i; j++) { p = p.next; }
if (p != null) { // 获得原对象 T old = p.next.data; // 删除p的后继结点 p.next = p.next.next; return old; } } return null; }
/** * 删除单链表所有元素 Java将自动收回各结点所占用的内存空间 */ @Override public void removeAll() { this.head.next = null; }
/** * 顺序查找关键字为key元素，返回首次出现的元素，若查找不成功返回null * key可以只包含关键字数据项，由T类的equals()方法提供比较对象相等的依据 */ @Override public T search(T key) { if (key == null) return null; for (Node<T> p = this.head.next; p != null; p = p.next) if (p.data.equals(key)) return p.data; return null; }
/** * 返回单链表所有元素的描述字符串，形式为“(,)”，覆盖Object类的toString()方法，O(n) */ @Override public String toString() { String str = "("; for (Node<T> p = this.head.next; p != null; p = p.next) { str += p.data.toString(); if (p.next != null) str += ","; // 不是最后一个结点时后加分隔符 } return str + ")"; // 空表返回() }
/** * 比较两条单链表是否相等 */ @SuppressWarnings("unchecked") @Override public boolean equals(Object obj) { if (obj == this) return true;
if (obj instanceof SinglyLinkedList) { SinglyLinkedList<T> list = (SinglyLinkedList<T>) obj; return equals(this.head.next, list.head.next); } return false; }
/** * 比较两条单链表是否相等，递归方法 * * @param p * @param q * @return */ private boolean equals(Node<T> p, Node<T> q) { return p == null && q == null || p != null && q != null && p.data.equals(q.data) && equals(p.next, q.next); } }
----------------------------------------------------------
package package1;
// 文档的分割与合并， 基于大文档 public class test {
public static void main(String[] args) { SinglyLinkedList<String> lista = new SinglyLinkedList<String>(); for (int i = 0; i <= 5; i++) lista.insert(i, new String((char) ('A' + i) + "")); System.out.println("本案例中链表的初始位置是0，即 元素是从第0个位置开始数的\n "); System.out.println("数组lista的所有元素值依次插入到单链表中，数据分别是：\n " + lista.toString());
System.out.println("单链表的长度是length()="+ lista.length()); System.out.println("返回第0个链表节点值lista.get(0):"+ lista.get(0) ); System.out.println("返回最后一个链表节点值lista.get(5):"+ lista.get(5) ); lista.set(0, new String((char) (lista.get(0).charAt(0) + 32) + "")); System.out.println("修改 链表的第0个数据值 数据后，新的链表元素值分别是：\n" + lista.toString());
String x="x"; lista.insert(2, x); System.out.println("单链表第二个位置插入x后，数据分别是:\n"+ lista.toString() );
lista.remove(6); System.out.println("单链表 删除 第6个位置数据后，数据分别是:\n"+ lista.toString() ); System.out.println("search链表元素值是：\n" + lista.search("x")); }
}
==============================================
顺序栈
package package1;
public class SeqStack { private static final int MAXSIZE = 100; private int top; private String[] data;
SeqStack() { Init_SeqStack(MAXSIZE); }
private void Init_SeqStack(int size) { data = new String[size]; top = -1; }
public int Empty_SeqStack() { if (top == -1) return 1; else return 0; }
public int Full_SeqStack() { if (top == MAXSIZE - 1) return 1; else return 0; }
public int Push_SeqStack(String x) { if (Full_SeqStack() == 1) return 0; else { top++; data[top] = x; return 1; } }
public String Pop_SeqStack() { if (Empty_SeqStack() == 1) return null; else return data[top--]; }
public String Top_SeqStack() { if (Empty_SeqStack() == 1) return null; else return data[top]; }
}
===========下列转载的文章，谢谢合作！知识共享！
http://blog.csdn.net/yaoweijq/article/details/7183937 Java中栈的最大递归深度http://blog.chinaunix.net/uid-20384806-id-1954176.html 递归的本质：使用 栈 来实现，
http://blog.csdn.net/jiutianhe/article/details/18605999
===========
二叉树
递归 全排列：
123 213 231 321 312 132
===========
二叉树
案例一：
package com.cxl.algorithm;
// 二叉树接口的ADT public interface IBiTree {
}
---------------------------
package com.cxl.algorithm;
// 二叉树的 链式 结点 的结构 public class LinkBiTNode { public int data; public LinkBiTNode lchild; public LinkBiTNode rchild;
public void LinkBiTNode(LinkBiTNode lchildval, LinkBiTNode rchildval) { lchild = lchildval; rchild = rchildval; }
public LinkBiTNode(int elem, LinkBiTNode lchildval, LinkBiTNode rchildval) { data = elem; LinkBiTNode(lchildval,rchildval); }
}
---------------------------------
package com.cxl.algorithm;
public class LinkBiTree implements IBiTree { private LinkBiTNode root; // 用于指示二叉树的根节点
public LinkBiTNode getRoot() { return root; }
public void setRoot(LinkBiTNode root) { this.root = root; }
public void insert(int value) { LinkBiTNode newNode = new LinkBiTNode(value, null, null);
if (root == null) { root = newNode; } else { LinkBiTNode currentNode = root; LinkBiTNode parentNode; while (true) { parentNode = currentNode; // 往右放 if (newNode.data > currentNode.data) { currentNode = currentNode.rchild; if (currentNode == null) { parentNode.rchild = newNode; return; } } else { // 往左放 currentNode = currentNode.lchild; if (currentNode == null) { parentNode.lchild = newNode; return; }
} }
} }
LinkBiTree() { root = null; } } /* * public LinkBiTree initiate() { // 初始建立一颗带有头节点的二叉树； * * LinkBiTNode bt = new LinkBiTNode(null, null); * * LinkBiTree T = new LinkBiTree(); * * T.root = bt; * * return T; } * * public LinkBiTree create(String x, LinkBiTree lbt, LinkBiTree rbt) { // * 初始建立一颗以X为根节点的二叉树； LinkBiTree T = new LinkBiTree(); LinkBiTNode bt = new * LinkBiTNode(x, null, null); * * T.root = bt; // T.bt.lchild = lbt; // T.bt.rchild = rbt; return T; } * * public LinkBiTree createBiTree(String x, LinkBiTree lbt, LinkBiTree rbt) { // * 初始建立一颗以X为根节点的二叉树； LinkBiTNode temp = null ; if(root == null) { temp = new * LinkBiTNode(x,null,null); root = temp ; } else { while(temp) { if( x < * root.data ) temp = root.lchild ; root = temp ; else temp = root.rchild ; root * = temp } * * } * * * * LinkBiTree T = new LinkBiTree(); LinkBiTNode bt = new LinkBiTNode(x, null, * null); * * T.root = bt; // T.bt.lchild = lbt; // T.bt.rchild = rbt; return T; } * * } */
--------------------------------
package com.cxl.algorithm; public class test {
public static void main(String[] args) { LinkBiTree tree = new LinkBiTree(); tree.insert(10); tree.insert(40); tree.insert(20); tree.insert(3); tree.insert(49); tree.insert(13); tree.insert(123); System.out.println("root=" + tree.getRoot().data);
System.out.println("================================ ");
===========
上述案例代码更新：
package package1;
//二叉树的 链式 结点 的结构 public class LinkBiTNode {
public int data; public LinkBiTNode lchild; public LinkBiTNode rchild;
public void LinkBiTNode(LinkBiTNode lchildval, LinkBiTNode rchildval) { lchild = lchildval; rchild = rchildval; }
public LinkBiTNode(int elem, LinkBiTNode lchildval, LinkBiTNode rchildval) { data = elem; LinkBiTNode(lchildval,rchildval); }
}
------------------------
package package1;
public class LinkBiTree implements IBiTree { //LinkBiTNode p = null;
private LinkBiTNode root; // 用于指示二叉树的根节点
public LinkBiTNode getRoot() { return root; }
public void setRoot(LinkBiTNode root) { this.root = root; }
public void insertLTree(int value) { LinkBiTNode newNode = new LinkBiTNode(value, null, null); if (root == null) root = newNode; else { LinkBiTNode parentNode = root; while (parentNode.lchild != null)//找到左叶子结点 { parentNode = parentNode.lchild; } parentNode.lchild = newNode; }
}
public LinkBiTNode search(LinkBiTNode bt ,int x ) //返回指定元素值得对象内存空间 { LinkBiTNode p = null; if( bt != null) { if( bt.data == x ) return bt ; if(bt.lchild != null) p = search(bt.lchild, x); if(p != null ) return p; if(bt.rchild != null) p = search(bt.rchild, x); if(p != null) return p; } return null; } public int countLeaf( LinkBiTNode bt )//统计二叉树的叶子结点个数 { if(bt == null) return 0 ; if(bt.lchild ==null && bt.rchild ==null) return 1; return ( countLeaf(bt.lchild)+countLeaf(bt.rchild)); } public void insert(int value) { LinkBiTNode newNode = new LinkBiTNode(value, null, null);
if (root == null) { root = newNode; } else { LinkBiTNode currentNode = root; LinkBiTNode parentNode; while (true) { parentNode = currentNode; // 往右放 if (newNode.data > currentNode.data) { currentNode = currentNode.rchild; if (currentNode == null) { parentNode.rchild = newNode; return; } } else { // 往左放 currentNode = currentNode.lchild; if (currentNode == null) { parentNode.lchild = newNode; return; }
} }
} }
LinkBiTree() { root = null; }
public void PreOrder(LinkBiTNode bt) { if (bt == null) return; System.out.print(bt.data + "-"); PreOrder(bt.lchild); PreOrder(bt.rchild); }
}
--------------------------------------
package package1;
// 文档的分割与合并， 基于大文档 public class test {
public static void main(String[] args) { LinkBiTree tree = new LinkBiTree(); tree.insert(10); tree.insert(40); tree.insert(20); tree.insert(3); tree.insert(49); tree.insert(13); tree.insert(123); tree.insertLTree(55); System.out.println("root=" + tree.getRoot().data);
System.out.println("================================ "); tree.PreOrder(tree.getRoot() ); System.out.println(tree.search(tree.getRoot(), 13)); System.out.println("叶子结点个数是："+tree.countLeaf(tree.getRoot()));
}
}
========================================================
package queue;
//自己定义的 队列
public class MyQueue {
private int [] data;//存储元素的 数组空间 private int num;//用于存储队列的元素 当前总的个数 private int front ; // 对头 private int end ; // 对尾 public MyQueue(){ data = new int[10]; num =0; front =0; end =-1; }
/** * 带参数的构造方法 */ public MyQueue(int maxsize){ data = new int[maxsize]; num =0; front =0; end =-1; }
// 添加队列元素 public void insert(int value){
data[++end] = value; num++; } public long remove(){
num--; return data[front++]; } //查看数据 public long peek(){ return data[front]; }
//判断是否为空 public boolean isEmpty(){ return num == 0 ; } public boolean isFull(){ return num == data.length ; } }
------------------------------------------------------------
package queue;
public class TestMyQueue {
public static void main(String[] args) { MyQueue myQueue = new MyQueue(); myQueue.insert(100); myQueue.insert(200); myQueue.insert(300); myQueue.insert(400); myQueue.insert(500); System.out.println("队列的头元素是："+myQueue.peek()); System.out.print("队列中的每一个元素是："); while (!myQueue.isEmpty()) { System.out.print( myQueue.remove() + " "); } System.out.println();
}
}
队列的头元素是：100 队列中的每一个元素是：100 200 300 400 500 ==============================================================================
package queue;
//自己定义的 改进后 的 循环 队列
public class MyQueue {
private int MAXSIZE = 5; private int[] data;// 存储元素的 数组空间 private int num;// 用于存储队列的元素 当前总的个数 private int front; // 对头 private int end; // 对尾
public MyQueue() { data = new int[MAXSIZE]; num = 0; front = 0; end = -1; System.out.println( "默认队列的信息是：队列的总容量是： " + MAXSIZE + "；\n已经存储的元素个数是： " + num + " ; \n队首指针是：" + front + ";\n队尾指针是：" + end); }
/** * 带参数的构造方法 */ public MyQueue(int maxsize) { MAXSIZE = maxsize; data = new int[maxsize]; num = 0; front = 0; end = -1; System.out.println("自己制定的队列的信息是：队列的总容量是： " + MAXSIZE + "；\n已经存储的元素个数是： " + num + " ; \n队首指针是：" + front + ";\n队尾指针是：" + end);
}
// 添加队列元素 public void insert(int value) {
//if (end == data.length - 1) //{ // end = -1; //} if (num == MAXSIZE) { System.out.println("队列已满，无法再插入新元素了！"); } else { end = (end + 1) % MAXSIZE; data[end] = value; num++; System.out.println("你往队列中插入了一个新元素：" + value + " ；队列存储的元素个数 是："+num +" ;front is "+ front +" ; end is :"+ end);
} }
public long remove() {
if (num == 0) { System.out.print("队列 已空 ，无法再 删除 元素了！ 返回的 0 代表的是 空元素---"); return 0; } else { num--; long i = data[front];
front = (front + 1) % MAXSIZE; System.out.println("你从队列中 删除了队首 头元素：" + i + " ；队列存储的元素个数 是："+num +" ;front is "+ front +" ; end is :"+ end +"；"); return i; }
}
// 查看数据 public long peek() { System.out.print("队列首元素front指针是："+front+" ；你 现在 从队列中 查看 队首 头元素："); return data[front]; }
// 判断是否为空 public boolean isEmpty() { // System.out.print("当前队列 包含的元素 是 空的 。"); return num == 0; }
public boolean isFull() { System.out.print("当前队列 包含的元素 是 满的 。"); return num == data.length; }
}
------------------------------------------------
package queue;
public class TestMyQueue {
public static void main(String[] args) { MyQueue myQueue = new MyQueue(); myQueue.insert(100); myQueue.insert(200); myQueue.insert(300); myQueue.insert(400); myQueue.insert(500); myQueue.insert(1500); System.out.println("队列的头元素是："+myQueue.peek());
myQueue.remove(); myQueue.remove(); myQueue.remove(); myQueue.insert(1500); myQueue.insert(1500); System.out.println("队列中的每一个元素是："); while (!myQueue.isEmpty()) { System.out.print( myQueue.remove() + " "); } System.out.println(); myQueue.remove(); }
}
-----------------------------------------
默认队列的信息是：队列的总容量是： 5； 已经存储的元素个数是： 0 ; 队首指针是：0; 队尾指针是：-1 你往队列中插入了一个新元素：100 ；队列存储的元素个数 是：1 ;front is 0 ; end is :0 你往队列中插入了一个新元素：200 ；队列存储的元素个数 是：2 ;front is 0 ; end is :1 你往队列中插入了一个新元素：300 ；队列存储的元素个数 是：3 ;front is 0 ; end is :2 你往队列中插入了一个新元素：400 ；队列存储的元素个数 是：4 ;front is 0 ; end is :3 你往队列中插入了一个新元素：500 ；队列存储的元素个数 是：5 ;front is 0 ; end is :4 队列已满，无法再插入新元素了！ 队列首元素front指针是：0 ；你 现在 从队列中 查看 队首 头元素：队列的头元素是：100 你从队列中 删除了队首 头元素：100 ；队列存储的元素个数 是：4 ;front is 1 ; end is :4； 你从队列中 删除了队首 头元素：200 ；队列存储的元素个数 是：3 ;front is 2 ; end is :4； 你从队列中 删除了队首 头元素：300 ；队列存储的元素个数 是：2 ;front is 3 ; end is :4； 你往队列中插入了一个新元素：1500 ；队列存储的元素个数 是：3 ;front is 3 ; end is :0 你往队列中插入了一个新元素：1500 ；队列存储的元素个数 是：4 ;front is 3 ; end is :1 队列中的每一个元素是： 你从队列中 删除了队首 头元素：400 ；队列存储的元素个数 是：3 ;front is 4 ; end is :1； 400 你从队列中 删除了队首 头元素：500 ；队列存储的元素个数 是：2 ;front is 0 ; end is :1； 500 你从队列中 删除了队首 头元素：1500 ；队列存储的元素个数 是：1 ;front is 1 ; end is :1； 1500 你从队列中 删除了队首 头元素：1500 ；队列存储的元素个数 是：0 ;front is 2 ; end is :1； 1500 队列 已空 ，无法再 删除 元素了！ 返回的 0 代表的是 空元素---
====================
