Java数据结构之链表、栈、队列、树的实现方法示例

网友投稿 235 2023-01-12


Java数据结构之链表、栈、队列、树的实现方法示例

本文实例讲述了java数据结构之链表、栈、队列、树的实现方法。分享给大家供大家参考,具体如下:

最近无意中翻到一本书,闲来无事写几行代码,实现几种常用的数据结构,以备后查。

一、线性表(链表)

1、节点定义

/**链表节点定义

* @author colonel

*

*/

class Node {

public int data;

Node next=null;

public Node(int data){

this.data=data;

}

}

2、链表操作类

/**链表操作类

* @author colonel

*

*/

public class operateClass {

public Node headNode=null;

/*给链表添加界节点

* @param data 链表节点数据

*/

public Node addNode(int data){

Node newNode=new Node(data);

if (headNode==null) {

headNode=newNode;

newNode.next=null;

return headNode;

}

Node tempNode=headNode;

while (tempNode.next!=null) {

//tempNode=headNode;

tempNode=tempNode.next;

}

tempNode.next=newNode;

return headNode;

}

/**删除节点

* @param 删除节点的位置

*

*/

public boolean delNode(int index){

if (index<1||index>length()) {

return false;

}

if (index==1) {

headNode=headNode.next;

return true;

}

Node preNode=headNode;

Node curNode=preNode.next;

int count=2;

while (curNode!=null) {

if (count==index) {

preNode.next=curNode.next;

return true;

}

preNode=curNode;

curNode=curNode.next;

count++;

}

return true;

}

/**取链表的长度

* @return返回链表的长度

*/

public int length(){

int length=0;

Node temp=headNode;

while (temp!=null) {

length++;

temp=temp.next;

}

return length;

}

/**按照值域对链表数据排序

* @return 返回排序后的链表头节点

*/

public Node orderList(){

Node nextNode=null;

int temp=0;

Node curNode=headNode;

while (curNode.next!=null) {

nextNode=curNode.next;

while (nextNode!=null) {

if (curNode.data>nextNode.data) {

temp=curNode.data;

curNode.data=nextNode.data;

nextNode.data=temp;

}

nextNode=nextNode.next;

}

curNode=curNode.next;

}

return headNode;

}

/**

* 去除链表中值域重复的元素

*/

public void redRepeat(){

if (length()<=1) {

return;

}

Node curNode=headNode;

while (curNode!=null) {

Node insidNode=curNode.next;

Node insidPreNode=insidNode;

while (insidNode!=null) {

if (insidNode.data==curNode.data) {

insidPreNode.next=insidNode.next;

//return;

}

insidPreNode=insidNode;

insidNode=insidNode.next;

}

curNode=curNode.next;

}

}

/**倒序输出链表中所有的数据

* @param hNode 链表头节点

*/

public void reversePrint(Node hNode){

if (hNode!=null) {

reversePrint(hNode.next);

System.out.println(hNode.data);

}

}

/**

* 从头节点开始到为节点结尾打印出值

*/

public void printList(){

Node tmpNode=headNode;

while (tmpNode!=null) {

System.out.println(tmpNode.data);

tmpNode=tmpNode.next;

}

}

}

二、栈

1、该栈使用数XlKQcrraZ组实现,具体的栈操作类

class MyStack{

private Object[] stack;

int top=-1;

public MyStack(){

stack=new Object[10];

}

public boolean isEmpty(){

return top==0;

}

/**弹出栈顶元素(不删除)

* @return

*/

public E peek(){

if (isEmpty()) {

return null;

}

return (E) stack[top];

}

/**出栈站顶元素

* @return 栈顶元素

*/

public E pop(){

E e=peek();

stack[top]=null;

top--;

return e;

}

/**压栈

* @param item 待压元素

* @http://return 返回待压元素

*/

public E push(E item){

//ensureCapacity(top+1);

stack[++top]=item;

return item;

}

/**栈满扩容

* @param size

*/

public void ensureCapacity(int size){

int len=stack.length;

if (size>len) {

int newLen=10;

stack=Arrays.copyOf(stack, newLen);

}

}

/**返回栈顶元素

* @return

*/

public E getTop(){

if (top==-1) {

return null;

}

return (E) stack[top];

}

}

三、队列

该队列使用链式实现

1、队节点定义

/**

* @author colonel

*队节点定义

* @param

*/

class queueNode{

queueNode nextNode=null;

Elem data;

public queueNode(Elem data){

this.data=data;

}

}

2、队列操作类

/**

* @author colonel

*队列操作类

* @param

*/

class MyQueue{

private queueNode headNode=null;

private queueNode tailNode=null;

private queueNode lastNode=null;

/**判断该队列是否为空

* @return 返回true or false

*/

public boolean isEmpty(){

return headNode==tailNode;

}

/**入队操作

* @param data 节点元素值

*/

public void put(Elem data){

queueNode newNode=new queueNode(data);

if (headNode==null&&tailNode==null) {

headNode=tailNode=newNode;

//tailNode=headNode.nextNode;

lastNode=tailNode.nextNode;

return;

}

tailNode.nextNode=newNode;

tailNode=newNode;

lastNode=tailNode.nextNode;

//tailNode=tailNode.nextNode;

}

/**出队操作

* @return 返回出队元素

*/

public Elem pop(){

if (headNode==lastNode) {

return null;

}

queueNode tempNode=headNode;

Elem statElem=tempNode.data;

headNode=tempNode.nextNode;

return statElem;

}

/**返回队列长度

* @return 长度

*/

public int size(){

if (isEmpty()) {

return 0;

}

int length=0;

queueNode temp=headNode;

while (temp!=null) {

length++;

temp=temp.nextNode;

}

return length;

}

}

四、二叉树

1、节点定义

/**树节点定义

* @author colonel

*

*/

class TreeNode{

public int data;

public TreeNode leftNode;

public TreeNode rightNode;

public TreeNode(int data){

this.data=data;

this.leftNode=null;

this.rightNode=null;

}

}

2、二叉树操作类

/**二叉排序树操作类

* @author colonel

*

*/

class OperateTree{

public TreeNode rootNode;

public OperateTree(){

rootNode=null;

}

/**元素插入二叉排序树

* @param data 待插节点数据

*/

public void insert(int data){

TreeNode newNode=new TreeNode(data);

if (rootNode==null) {

rootNode=newNode;

}else {

TreeNode current=rootNode;

TreeNode parent;

while (true) {

parent=current;

if (data

current=current.leftNode;

if (current==null) {

parent.leftNode=newNode;

return;

}

} else {

current=current.rightNode;

if (current==null) {

parent.rightNode=newNode;

return;

}

}

}

}

}

/**构建二叉排序树

* @param item 元素数组

*/

public void buildTree(int[] item){

for (int i = 0; i < item.length; i++) {

insert(item[i]);

}

}

/**

* 先序遍历二叉树

*/

public void preOrder(TreeNode root){

if (root!=null) {

System.out.println(root.data);

preOrder(root.leftNode);

preOrder(root.rightNode);

}

}

/**中序遍历

* @param root

*/

public void inOrder(TreeNode root){

if (root!=null) {

inOrder(root.leftNode);

System.out.println(root.data);

inOrder(root.rightNode);

}

}

/**后序遍历

* @param root

*/

public void afterOrder(TreeNode root){

if (root!=null) {

afterOrder(root.leftNode);

afterOrder(root.rightNode);

System.out.println(root.data);

}

}

/**

* 层序遍历二叉排序树

*/

public void layerTrave(){

if (this.rootNode==null) {

return;

}

Queue myQueue=new LinkedList<>();

myQueue.add(rootNode);

while (!myQueue.isEmpty()) {

TreeNode tempNode=myQueue.poll();

System.out.println(tempNode.data);

if (tempNode.leftNode!=null) {

myQueue.add(tempNode.leftNode);

}

if (tempNode.rightNode!=null) {

myQueue.add(tempNode.rightNode);

}

}

}

五、总结

更好的理解数据结构为何物,还需继续探索,谨记。by:colonel

更多关于java算法相关内容感兴趣的读者可查看本站专题:《Java数据结构与算法教程》、《Java操作DOM节点技巧总结》、《Java文件与目录操作技巧汇总》和《Java缓存操作技巧汇总》

希望本文所述对大家java程序设计有所帮助。

current=current.leftNode;

if (current==null) {

parent.leftNode=newNode;

return;

}

} else {

current=current.rightNode;

if (current==null) {

parent.rightNode=newNode;

return;

}

}

}

}

}

/**构建二叉排序树

* @param item 元素数组

*/

public void buildTree(int[] item){

for (int i = 0; i < item.length; i++) {

insert(item[i]);

}

}

/**

* 先序遍历二叉树

*/

public void preOrder(TreeNode root){

if (root!=null) {

System.out.println(root.data);

preOrder(root.leftNode);

preOrder(root.rightNode);

}

}

/**中序遍历

* @param root

*/

public void inOrder(TreeNode root){

if (root!=null) {

inOrder(root.leftNode);

System.out.println(root.data);

inOrder(root.rightNode);

}

}

/**后序遍历

* @param root

*/

public void afterOrder(TreeNode root){

if (root!=null) {

afterOrder(root.leftNode);

afterOrder(root.rightNode);

System.out.println(root.data);

}

}

/**

* 层序遍历二叉排序树

*/

public void layerTrave(){

if (this.rootNode==null) {

return;

}

Queue myQueue=new LinkedList<>();

myQueue.add(rootNode);

while (!myQueue.isEmpty()) {

TreeNode tempNode=myQueue.poll();

System.out.println(tempNode.data);

if (tempNode.leftNode!=null) {

myQueue.add(tempNode.leftNode);

}

if (tempNode.rightNode!=null) {

myQueue.add(tempNode.rightNode);

}

}

}

五、总结

更好的理解数据结构为何物,还需继续探索,谨记。by:colonel

更多关于java算法相关内容感兴趣的读者可查看本站专题:《Java数据结构与算法教程》、《Java操作DOM节点技巧总结》、《Java文件与目录操作技巧汇总》和《Java缓存操作技巧汇总》

希望本文所述对大家java程序设计有所帮助。


版权声明:本文内容由网络用户投稿,版权归原作者所有,本站不拥有其著作权,亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容,请联系我们jiasou666@gmail.com 处理,核实后本网站将在24小时内删除侵权内容。

上一篇:接口测试用例有哪些要点(接口测试用例设计思路)
下一篇:抓包对接口测试的意义(抓包和接口测试有什么区别)
相关文章

 发表评论

暂时没有评论,来抢沙发吧~