1.数据结构篇一

心已赠人 2023-07-03 06:07 13阅读 0赞

说多了也没用，先上一个脑图吧。![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2h1YWl4aWFvaGFpXzE_size_16_color_FFFFFF_t_70][]

害，啥也不说了，怎么这么多包，还可能有好多东西没整上，学计算机可真是累死个人奥。

下边一个一个整。

顺序表实现：

public class ListDemo {
    	private final int MAXSIZE = 100;
    	private Object data[];
    	int last;
    
    	int defaultLength = 20;
    
    	public ListDemo(int length) {
    		data = new Object[length];
    		last = 0;
    	}
    
    	public ListDemo() {
    		data = new Object[defaultLength];
    		last = 0;
    	}
    
    	/*
    	 * 判断是否容量是否足够，如果不够扩容（2倍）
    	 */
    	public void add(Object obj) {
    		if (last < data.length) {
    			data[last++] = obj;
    		} else {
    			data = Arrays.copyOf(data, data.length * 2, Object[].class);
    			data[last++] = obj;
    		}
    	}
    
    	/*
    	 * 判断index是否合法，删除时数组整体向左移动
    	 */
    	public void delete(int index) {
    		if (index >= 0 && index <= last) {
    			for (int i = index; i < last - 1; i++) {
    				data[i] = data[i + 1];
    			}
    			last--;
    		} else {
    			System.err.println("下标不合法");
    		}
    	}
    	
    	/*
    	 * 查找
    	 */
    	public Object search(int index) {
    		if(index<last) {
    			return data[index];
    		}else {
    			return null;
    		}
    	} 
    	
    	/*
    	 * 修改
    	 */
    	public void update(Object obj,int index) {
    		if(index<last) {
    			data[index] = obj;
    		}else {
    			System.err.println("下标不合法");
    		}
    	}
    }

单链表实现：

public class LinkNode<V> {
    	//数据
    	V data;
    	//下一个节点
    	LinkNode<V> next =null;
    	public LinkNode(V data,LinkNode<V> next) {
    		this.data=data;
    		this.next=next;
    	}
    }

public class LinkListDemo<V> {
    	// 初始化头节点
    	LinkNode<V> header = new LinkNode<V>(null, null);
    	LinkNode<V> last = header;
    	int size = 0;
    
    	/*
    	 * 添 加元素 头部插入
    	 */
    	public void addToHeader(V data) {
    		LinkNode<V> node = new LinkNode<V>(data, null);
    		// 第一次插入
    		if (header.next == null) {
    			header.next = node;
    			last = node;
    		} else {
    			node.next = header.next;
    			header.next = node;
    		}
    		size++;
    	}
    
    	/*
    	 * 添加元素 尾部插入
    	 */
    	public void addToLast(V data) {
    		LinkNode<V> node = new LinkNode<V>(data, null);
    		last.next = node;
    		last = node;
    		size++;
    	}
    
    	/*
    	 * 删除节点 通过位置删除
    	 */
    	public void removeNode(int index) {
    		if (index > size-1) {
    			System.err.println("index超出范围");
    			return;
    		}
    		LinkNode<V> node = header;
    		// 找到该节点
    		for (int i = 0; i < index; i++) {
    			node = node.next;
    		}
    		// 修改待删除节点的前一个节点指向
    		node.next = node.next.next;
    		size--;
    	}
    
    	/*
    	 * 删除节点 通过data删除
    	 */
    	public void removeNode(V data) {
    		LinkNode<V> node = header;
    		LinkNode<V> temp =null;
    		while (true) {
    			// 找到元素
    			if (node.next != null && node.next.data.equals(data)) {
    				// 删除尾元素的时调整last位置
    				if (node.next == last) {
    					last = node;
    				}
    				node.next = node.next.next;
    				size--;
    				return;
    			} else if (node.next == null) {
    				System.err.println("没有此元素");
    				return;
    			}
    			node = node.next;
    		}
    	}
    
    	/*
    	 * 查找节点
    	 */
    	public V search(int index) {
    		if (index > size-1) {
    			System.err.println("index超出范围");
    			return null;
    		}
    		LinkNode<V> node = header;
    		for (int i = 0; i < index; i++) {
    			node = node.next;
    		}
    		return node.data;
    	}
    
    	/*
    	 * 更新节点
    	 */
    	public boolean unpdata(int index, V data) {
    		if (index > size-1) {
    			System.err.println("index超出范围");
    			return false;
    		}
    		LinkNode<V> node = header;
    		for (int i = 0; i < index; i++) {
    			node = node.next;
    		}
    		node.data = data;
    		return true;
    	}
    }

顺序栈实现：

public class ListStack {
    	private final int MAXSIZE = 100;
    	private Object data[];
    	private int last=0;
    	//默认长度
    	int defaultLength = 20;
    	
    	public ListStack() {
    		data = new Object[defaultLength];
    	}
    	public ListStack(int len) {
    		data=new Object[len]; 
    	}
    	
    	public void push(Object obj) {
    		if(last>=data.length) {
    			data = Arrays.copyOf(data, data.length, Object[].class);
    		}
    		data[last++] = obj;
    	}
    	
    	public void pop() {
    		if(last==0) {
    			System.err.println("栈为空");
    			return;
    		}
    		data[last-1]=null;
    		last--;
    	}
    }

链栈实现：

public class LinkStack<V> {
    	private LinkNode<V>  header = null;
    
    	@Override
    	public String toString() {
    		return "LinkStack{" +
    				"header=" + header +
    				'}';
    	}
    
    	public void push(V v) {
    		LinkNode<V>  node = new LinkNode<V>(v, null);
    
    		//第一次插入
    		if(header==null){
    			header = node;
    		}else{
    			node.next=header;
    			header = node;
    		}
    	}
    	public void pop() {
    		if(header==null){
    			System.err.println("栈已经空了");
    		}else{
    			header=header.next;
    		}
    
    	}
    
    	public void bianli(){
    		LinkNode node = header;
    		while(node!=null){
    			System.out.println(node.data);
    			node= node.next;
    		}
    	}
    	
    }

线性队列：

public class ListQueue {
    	// 数据
    	private Object data[];
    	// 头和尾
    	private int head, last;
    	// 默认长度
    	private int default_length = 20;
    
    	// 第一次插入标识
    	private boolean flag = true;
    
    	public ListQueue() {
    		data = new Object[default_length];
    		head = 0;
    		last = 0;
    	}
    
    	public ListQueue(int length) {
    		data = new Object[length];
    		head = 0;
    		last = 0;
    
    	}
    
    	public void add(Object obj) {
    		if (last % data.length != head % data.length || flag) {
    			data[last % data.length] = obj;
    			last++;
    			flag = false;
    		} else {
    			System.out.println("队列已满");
    		}
    	}
    
    	public void remove() {
    		if (last % data.length != head % data.length) {
    			head++;
    		} else {
    			System.out.println("队列为空");
    		}
    	}
    
    	public Object getHead() {
    		if(!flag||last % data.length != head % data.length) {
    			return data[head];
    		}else {
    			System.out.println("队列为空");
    			return null;
    		}
    	}
    }

链表队列：

public class LinkedQueue<V> {
    	LinkNode queue = new LinkNode<V>(null, null);
    	LinkNode<V> last = queue;
    	
    	//第一次插入
    	private boolean flag=true;
    	public void add(V data) {
    		LinkNode<V> temp = new LinkNode<V>(data, null);
    		if(flag) {
    			queue.next=temp;
    			last=temp;
    			flag=false;
    		}else {
    			last.next=temp;
    			last=temp;
    		}
    	}
    	
    	public void remove() {
    		if(queue.next!=null) {
    			queue.next=queue.next.next;
    		}else {
    			System.out.println("队列为空");
    		}
    	}
    	
    	public V getHeader() {
    		if(queue.next!=null) {
    			return (V) queue.next.data;
    		}else {
    			System.out.println("队列为空");
    			return null;
    		}
    	}
    }

普通二叉树增删改查跟上边差不多，而且每个规则也属实不知道插得哪，先看看二叉树的遍历吧；

/**
     * @description:树节点
     * @author: CrazyChild
     * @createDate: 2020/2/2
     * @version: 1.0
     */
    public class TreeNode<V> {
        private V data;
        TreeNode lChild;
        TreeNode rChild;
    
        public boolean equals(TreeNode node) {
            if(node.data == data||node.data.equals(data)){
                return true;
            }else{
                return false;
            }
        }
    
        public TreeNode(V data) {
            this.data = data;
        }
        
        public V getData() {
            return data;
        }
    
        public void setData(V data) {
            this.data = data;
        }
    
    }

/**
     * @description:树的遍历
     * @author: CrazyChild
     * @createDate: 2020/2/2
     * @version: 1.0
     */
    public class Tree<V> {
        //深度优先  其实也是先序遍历的非递归形式
        public static void deptFirst(TreeNode root) {
            if (root == null) {
                return;
            }
            Stack<TreeNode> stack = new Stack<>();
            stack.push(root);
            while (!stack.isEmpty()) {
                TreeNode node = stack.pop();
                System.out.print(node.getData() + "  ");
                if (node.rChild != null) {
                    stack.push(node.rChild);
                }
                if (node.lChild != null) {
                    stack.push(node.lChild);
                }
            }
        }
    
        //广度优先
        public static void broadFirst(TreeNode root) {
            if (root == null) {
                return;
            }
            Deque<TreeNode> queue = new LinkedList<>();
            queue.push(root);
            while (!queue.isEmpty()) {
                TreeNode node = queue.pop();
                System.out.print(node.getData() + "  ");
                if (node.lChild != null) {
                    queue.addLast(node.lChild);
                }
                if (node.rChild != null) {
                    queue.addLast(node.rChild);
                }
            }
        }
    
        //递归先序遍历  遍历顺序：根，左，右
        public static void preOrder(TreeNode root) {
            if (root == null) {
                return;
            }
            System.out.print(root.getData() + "  ");
            preOrder(root.lChild);
            preOrder(root.rChild);
        }
    
        //递归中序遍历 遍历顺序：左 根 右
        public static void inOrder(TreeNode root) {
            if (root == null) {
                return;
            }
            inOrder(root.lChild);
            System.out.print(root.getData() + "  ");
            inOrder(root.rChild);
        }
    
        //递归后序遍历 遍历顺序：左  右 根
        public static void postOrder(TreeNode root) {
            if (root == null) {
                return;
            }
            postOrder(root.lChild);
            postOrder(root.rChild);
            System.out.print(root.getData() + "  ");
        }
    
        //非递归中序遍历
        public static void NRInOrder(TreeNode root) {
            if (root == null) {
                return;
            }
            Stack<TreeNode> stack = new Stack<>();
            stack.push(root);
            while (!stack.isEmpty()) {
                if (root != null && root.lChild != null) {
                    stack.push(root.lChild);
                    root = root.lChild;
                } else {
                    root = stack.pop();
                    System.out.print(root.getData() + "  ");
                    if (root != null && root.rChild != null) {
                        stack.push(root.rChild);
                        root = root.rChild;
                    } else {
                        root = null;
                    }
                }
            }
        }
    
        //非递归后序遍历
        public static void NRPostOrder(TreeNode root) {
            if (root != null) {
                Stack<TreeNode> stack1 = new Stack<>();
                Stack<TreeNode> stack2 = new Stack<>();
                stack1.push(root);
                while (!stack1.isEmpty()) {
                    root = stack1.pop();
                    stack2.push(root);
                    if (root.lChild != null) {
                        stack1.push(root.lChild);
                    }
                    if (root.rChild != null) {
                        stack1.push(root.rChild);
                    }
                }
                while (!stack2.isEmpty()) {
                    System.out.print(stack2.pop().getData() + "  ");
                }
            }
    
        }
    }

好了，今天先这样吧，越到后边越难，加油，奥里给。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2h1YWl4aWFvaGFpXzE_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200202225949216.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2h1YWl4aWFvaGFpXzE=,size_16,color_FFFFFF,t_70