JavaSEDemo22数据结构

た入场券 2021-09-25 07:36 186阅读 0赞

### 文章目录 ###

*  简介
 *  练习题
 *   *  练习1
     *  练习2
 *  栈
 *   *  栈的特点
     *  创建栈
     *  判断栈是否为空
     *  判断栈是否满
     *  压栈(入栈)
     *  弹栈(出栈)
 *  环形队列
 *   *  环形队列的特点
     *  创建队列
     *  得到头指针和尾指针的下一个位置
     *  判断队列是否为空
     *  判断队列是否未满
     *  入队
     *  出队
 *  树
 *   *  创建树(中序遍历的二叉树)
     *  二叉树插入的方法
     *  二叉树查找结点的方法
     *  二叉树根据key得到value的方法

# 简介 #

*  本文是2021/04/20整理的笔记
 *  赘述可能有点多，还请各位朋友耐心阅读
 *  本人的内容和答案不一定是最好最正确的，欢迎各位朋友评论区指正改进

# 练习题 #

## 练习1 ##

*  题目:  
    实现 一个方法：  
    public static Object execute(String className, String methodName, Object args\[\])；  
    实现“通过类的名字、方法名字、方法参数调调用方法，返回值为该方法的返回值。” 的功能。用反射调用.
 *  答案:

1.  User类

package day0419.demo01$2;
    
    public class User { 
        public void eat(String name,Integer count){ 
            System.out.println("我吃了 " +count+"个"+name );
        }
    }

1.  Test类

package day0419.demo01$2;
    
    import java.lang.reflect.InvocationTargetException;
    import java.lang.reflect.Method;
    
    
    public class Test { 
        public static void main(String[] args) throws 
        ClassNotFoundException,
         NoSuchMethodException, 
         InvocationTargetException, 
         InstantiationException, 
         IllegalAccessException { 
            execute("day0419.demo01$2.User", "eat", new Object[]{  "炸鸡腿",5});
        }
        public static Object execute
        (String className, String methodName, Object args[]) throws 
        ClassNotFoundException, 
        IllegalAccessException, 
        InstantiationException,
         NoSuchMethodException, 
         InvocationTargetException { 
            //获取类的字节码对象
            Class<?> aClass = Class.forName(className);
            //根据newInstance创建实例对象
            Object o = aClass.newInstance();
            //创建一个Class类对象的数组,用于存储类对象。长度和args数组长度相等
            Class[] paramTypes = new Class[args.length];
            //for循环
            for (int i = 0; i < paramTypes.length; i++) { 
                paramTypes[i] = args[i].getClass();
            }
            //得到方法,根据Class类对象的数组
            Method method = aClass.getMethod(methodName, paramTypes);
            //调用Method类的invoke方法,第一个参数为对象,后续参数为方法的参数列表
            Object invoke = method.invoke(o, args);
            return invoke;
        }
    }

1.  程序运行结果  
    ![在这里插入图片描述][20210420092519352.png_pic_center]

## 练习2 ##

*  题目  
    自定义注解WebInitParam以及WebServlet，其中WebInitParam定义字符串类型属性name及value；WebServlet解定义字符串类型属性name以及displayName；int类型属性loadOnStartup ；boolean类型属性asyncSupported；String\[\]类型 属性urlPatterns；WebInitParam \[\]类型属性initParams。在类LoginServlet中使用注解。  
    答案

# 栈 #

## 栈的特点 ##

*  先进后出
 *  一端开口

## 创建栈 ##

public class MyStack{ 
    /* 数组模拟栈 栈顶 栈底 栈的大小 */
    private int[] stack;
    private int top;
    private final int bottom;
    private final int SIZE;
    public MyStack(int size){ 
    SIZE = size;
    bottom = 0;
    top = bottom;
    stack = new int[SIZE];
    }
    }

## 判断栈是否为空 ##

public void isEmpty(){ 
    return bottom == top;
    }

## 判断栈是否满 ##

public void isFull(){ 
    return top == SIZE;
    }

## 压栈(入栈) ##

public void push(int data){ 
    //先判断栈是不是满的
    if(isFull()){ 
    throw new IllegalStateException("队列已满");
    }else{ 
    stack[top++] = data;
    }
    }

## 弹栈(出栈) ##

public int pop(){ 
    //先判断栈是不是空的
    if(isFull()){ 
    throw new IllegalStateException("队列为空");
    }else{ 
    return stack[--top];
    }
    }

# 环形队列 #

## 环形队列的特点 ##

*  先进先出
 *  两端开口
 *  可存储的元素个数为长度减一

## 创建队列 ##

public class MyQueue { 
        /* 队列数组 队头 队尾 数组长度 */
        private int[] queue;
        private int head;
        private int end;
        private final int LENGTH;
        //构造器
        public MyQueue(int length) { 
            LENGTH = length;
            head = 0;
            end = 0;
            queue = new int[LENGTH];
        }
        }

## 得到头指针和尾指针的下一个位置 ##

public int next(int index){ 
    return (index + 1) % LENGTH;
    }

## 判断队列是否为空 ##

public boolean isEmpty(){ 
            return head == end;
        }

## 判断队列是否未满 ##

public boolean isFull(){ 
            return next(end) == head;
        }

## 入队 ##

public void insert(int data){ 
            if(isFull()){ 
                throw new IllegalStateException("队列已满,无法入队");
            }else { 
                queue[end] = data;
                end = next(end);
            }
        }

## 出队 ##

public int get(){ 
            if(isEmpty()){ 
                throw new IllegalStateException("队列为空,无法出队");
            }else { 
                head = next(head);
                return queue[head];
            }
        }

# 树 #

## 创建树(中序遍历的二叉树) ##

public class MyBinaryTree { 
        //成员内部类:结点
        private class Node{ 
          /* 键 值 左结点 右结点 */
            private int key;
            private int value;
            private Node left;
            private Node right;
            //构造器
            public Node(int key, int value) { 
                this.key = key;
                this.value = value;
            }
            //重写toString方法
            @Override
            public String toString() { 
                return "Node{" +
                        "key=" + key +
                        ", value=" + value +
                        ", left=" + left +
                        ", right=" + right +
                        '}';
            }
        }
        //根结点
        private Node root;
        //构造器
        public MyBinaryTree() { 
            root = null;
        }
        }

## 二叉树插入的方法 ##

//二叉树插入的方法
        public void addNode(int key,int value){ 
            Node newNode = new Node(key,value);
            //如果根结点为空,表示该树为空树;如果插入的键值和根结点的键值相同
            if(root == null || root.key == key){ 
              root = new Node(key,value);
              return;
            }
            Node current = root;
            while(true){ 
                //如果键值小于当前键值,则成为当前结点的左结点,或者当前结点左移
                if(key < current.key){ 
                    if(current.left == null) { 
                        current.left = newNode;
                        break;
                    }else { 
                       current = current.left;
                    }
                    //如果键值大于当前键值,则成为当前结点的右结点,或者当前结点右移
                }else { 
                    if(current.right == null){ 
                        current.right = newNode;
                        break;
                    }else { 
                        current = current.right;
                    }
                }
            }
        }

## 二叉树查找结点的方法 ##

//二叉树查找结点的方法
        public Node getNode(int key){ 
            //如果根结点为空,表示该树为空树
            if(root ==null){ 
                return null;
            }
            //如果要查找的结点恰好为根结点
            if(root.key == key){ 
            return  root;
            }
            //创建一个当前结点
            Node current = root;
            while(current.key != key){ 
                 if(key < current.key){ 
                     current = current.left;
                     if(current ==null){ 
                         return null;
                     }
                 }else { 
                     current = current.right;
                     if(current == null){ 
                         return null;
                     }
                 }
            }
            return current;
        }

## 二叉树根据key得到value的方法 ##

//二叉树根据key查找value的方法
        public int getValue(int key){ 
    
            if(getNode(key) != null) { 
                System.out.println("查找成功");
                return getNode(key).value;
            }else { 
                System.out.println("查找失败");
                return -404;
            }
        }

[20210420092519352.png_pic_center]: /images/20210923/49e2f3034cf74c6bafe7c97417a30114.png