数据结构(线性表、栈与队列、树、图) 桃扇骨 2022-01-20 01:19 308阅读 0赞 ## 一、线性表 ## 线性表是最常用且最简单的一种数据结构,它是n个数据元素的有限序列。 实现线性表的方式一般有两种: 1. 使用数组存储线性表的元素,即用一组连续的存储单元依次存储线性表的数据结构 2. 使用链表存储线性表的元素,即用一组任意的存储单元存储线性表的数据元素(存储单元可以是连续的,也可以是不连续的) ### 数组实现 ### 数组是一种大小固定的数据结构,对线性表的所有操作都可以通过数组来实现。虽然数组一旦创建之后它的大小就不能改变了,但是当数组不能再存储线性表中的新元素时,我们可以创建一个新的大的数组来替换当前数组。这样可以使用数组实现动态的数据结构。 示例1:创建一个更大的数组来替换当前数组 int[] oldArray=new int[10]; int[] newArray=new int[20]; for(int i=0;i<oldArray.length;i++){ newArray[i]=oldArray[i]; } //也可以使用System.arraycopy方法实现数组间的复制 System.arraycopy(oldArray,0,newArray,0,oldArray.length); oldArray=newArray; 示例2:在数组位置index上添加元素(思路:在index的位置上插入元素e,后面所有的元素向后移动一位) //oldArray 表示当前存储元素的数组 //size 表示当前元素的个数 public void add(int index ,int e){ if (index >size|| index<0){ System.out.println("位置不合法"); } //如果数组已经满了,就扩容 if (size>=oldArray.length){ //扩容代码参见,示例代码1 } for (int i=size-1;i>=index;i--){ oldArray[i+1]=oldArray[i]; } oldArray[index]=e; size++; } 说明:数组实现的线性表的优点在于可以通过下标来访问或者修改元素,比较高效;缺点是插入和删除的花费开销比较大,比如在当前第一个位置前插入一个元素,那么首先要把所有的元素靠后移动一个位置。为了提高在任意位置添加或者删除元素的效率,可以采用链式结构来实现线性表。 ### 链表 ### 链表是一种物理存储单元上非连续、非顺序的存储结构,数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表由一系列节点组成,这些节点不必在内存中相连。每个节点由数据部分Data和链部分Next,Next指向下一个节点,这样当添加或者删除时,只需要改变相关节点的Next指向,效率很高。 ![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zODY2NDIzMg_size_16_color_FFFFFF_t_70][] 链表节点示例代码: class Node<E>{ E item; Node<E> next; //构造函数 Node(E element){ this.item=element; this.next=null; } } 链表头节点和尾节点初始化: //头节点和尾节点都为空 链表为空 Node<E> head=null; Node<E> tail=null; 空链表创建一个新节点: //创建一个新的节点,并让head指向此节点 head=new Node("nodedata1"); //让尾节点也指向此节点 tail=head; 链表追加一个节点: //创建新节点 同时和最后一个节点连接起来 tail.next=new Node("node1data2"); //尾节点指向新的节点 tail=tail.next; 顺序遍历链表: Node<String> current=head; while(current != null){ System.out.println(current.item); current=current.next; } 倒序遍历链表: static void printListRev(Node<String> head){ //倒序遍历链表主要用了递归的思想 if(head != null){ printListRev(head.next); System.out.println(head.item); } } 单链表反转: //单链表反转 主要是逐一改变两个节点间的链接关系来完成 static Node<String> revList(Node<String> head){ if (head == null){ return null; } Node<String> nodeResult=null; Node<String> nodePre=null; Node<String> current=head; while(current != null){ Node<String> nodeNext=current.next; if(nodeNext == null){ nodeResult=current; } current.next=nodePre; nodePre=current; current=nodeNext; } return nodeResult; } 链表的实现还有其他的方式,常见的有循环单链表,双向链表,循环双向链表。**循环单链表**主要是链表的最后一个节点指向第一个节点,整体构成一个链环。**双向链表**主要是节点中包含两个指针部分,一个指向前驱元,一个指向后继元,JDK中LinkedList集合类的实现就是双向链表。**循环双向链表**是最后一个节点指向指向第一个节点。 ### 二、栈与队列 ### 栈和队列也是比较常见的数据结构,它们是比较特殊的线性表。对于栈来说,访问、插入和删除元素只能在栈顶进行;对于队列,元素只能从队尾插入,从队头访问和删除。 * 队列是一种特殊的线性表,特殊之处在于它只允许在表的前端(front)进行删除操作,而在表的后端(rear)进行插入操作,和栈一样,队列是一种操作受限制的线性表。进行插入操作的端称为队尾,进行删除操作的端称为队头。 * 可以使用链表来实现队列,实现代码: * public class MyQueue<E>{ private LinkedList<E> list=new LinkedList<>(); //入队 public void enqueue(E e){ list.addLast(e); } //出队 public E dequeue(){ return list.removeFirst(); } } ## 三、树与二叉树 ## 树型结构是一类非常重要的非线性数据结构,其中以树和二叉树最为常用。 ### 树 ### 树是由n(n>=1)个有限节点组成一个具有层次关系的集合。具有以下特点: 1. 每个节点有零个或多个子节点 2. 没有父节点的节点称为**根节点** 3. 每一个非根节点有且只有一个父节点 4. 除了根节点外,每个子节点可以分为多个不相交的子树 ![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zODY2NDIzMg_size_16_color_FFFFFF_t_70 1][] ### 二叉树 ### 二叉树是每个节点最多有两棵子树的树结构。通常子树被称作”左子树“和”右子树“。二叉树常被用于实现二叉查找树和二叉堆。 二叉树的性质: 1. 二叉树的节点最多有两棵子树(不存在度大于2的节点),二叉树的子树有左右之分,次序不能颠倒 2. 二叉树的第i层最多有2^(i-1)个节点;深度为k的二叉树至多有2^(k-1)个节点 3. 一棵深度为k,且有2^(k-1)个节点的二叉树称为**满二叉树** 4. 深度为k,有n个节点的二叉树,当且仅当其每一个节点都与深度为k的满二叉树中,序号为1至n的节点对应时,称为**完全二叉树**。 ![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zODY2NDIzMg_size_16_color_FFFFFF_t_70 2][] 可以看到,含有n个节点的二叉查找树的平均查找长度和树的形态有关。最坏情况下,当先后插入的关键字有序时,构成的二叉查找树蜕变为单支树,树的深度为n,其平均查找长度(n+1)/2(和顺序查找相同),最好的情况是二叉查找树的形态和折半查找的判定树相同,其平均查找长度和log2(n)成正比。平均情况下,二叉查找树的平均查找长度和logn是等数量级的,所以为了获得更好的性能,通常在二叉查找树的构建过程需要进行”平衡话处理“,之后的平衡二叉树和红黑树,这些均可以使查找树的高度为O(log(n)) 二叉树的节点: class TreeNode<E>{ E element; TreeNode<E> left; TreeNode<E> right; public TreeNode(E e){ element=e; } } 二叉查找树的三种遍历都可以直接调用递归的方法来实现: 先序遍历: protected void preorder(TreeNode<E> root){ if(root == null){ return; } System.out.println(root.element+" "); preorder(root.left); preorder(root.right); } 中序遍历: protected void inorder(TreeNode<E> root){ if(root == null) return; inorder(root.left); System.out.println(root.element+" "); inorder(root.right); } 后续遍历: protected void postorder(TreeNode<E> root){ if (root == null) return; postorder(root.left); postorder(root.right); System.out.println(root.element+" "); } 二叉查找树的简单实现: public class MyBinSearchTree<E extends Comparable<E>>{ //根 private TreeNode<E> root; //默认构造函数 public MyBinSearchTree(){} //二叉树的查找 public boolean search(E e){ TreeNode<E> current=root; while(current != null){ if(e.compareTo(current.element)<0){ current=current.left; }else if(e.compareTo(current.element)>0){ current=current.right; }else{ return true; } } return false; } //二叉树的查找 public boolean insert(E e){ //如果之前是空二叉树 插入的元素就作为根节点 if(root == null){ root=createNewNode(e); }else{ //否则就从根节点开始遍历 直到找到合适的父节点 TreeNode<E> parent=null; TreeNode<E> current=root; while (current != null) { if (e.compareTo(current.element) < 0) { parent = current; current = current.left; } else if (e.compareTo(current.element) > 0) { parent = current; current = current.right; } else { return false; } } // 插入 if (e.compareTo(parent.element) < 0) { parent.left = createNewNode(e); } else { parent.right = createNewNode(e); } } return true; } // 创建新的节点 protected TreeNode<E> createNewNode(E e) { return new TreeNode(e); } } // 二叉树的节点 class TreeNode<E extends Comparable<E>> { E element; TreeNode<E> left; TreeNode<E> right; public TreeNode(E e) { element = e; } } [watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zODY2NDIzMg_size_16_color_FFFFFF_t_70]: /images/20220120/5323578991384afaba70ee9d4eae7678.png [watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zODY2NDIzMg_size_16_color_FFFFFF_t_70 1]: /images/20220120/23141c4aec324555988a93e69855f60b.png [watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zODY2NDIzMg_size_16_color_FFFFFF_t_70 2]: /images/20220120/68b77e741cb24979b8070060d8b96123.png
还没有评论,来说两句吧...