赞
踩
目录
简单地说,数据结构是以某种特定的布局方式存储数据的容器。这种“布局方式”决定了数据结构对于某些操作是高效的,而对于其他操作则是低效的。所以我们需要理解各种数据结构,才能在处理实际问题时选取最合适的数据结构。
数据结构=逻辑结构+物理结构(顺序、链式、索引、散列)
逻辑结构:数据元素间抽象化的相互关系
物理结构:(存储结构),在计算机存储器中的存储形式
栈是一种只能从一端存取数据且遵循"后进先出(LIFO)"原则的线性存储结构。
- package studyweek6数据结构;
-
- import java.util.Arrays;
- import java.util.EmptyStackException;
-
- /**
- * 自定义栈容器
- */
- public class MyStack<E> {
- private Object[] arr;//存放元素的物理结构
-
- private int stackLength=4;//数组的默认长度
-
- private int size; //记录栈容器的元素个数
-
- private int index=-1; //操作数组下标位置的指针
-
- /**判断栈容器是否为空
- *
- * @return
- */
- public boolean empty(){
- return this.size==0;
- }
-
- /**
- * 获取栈顶元素
- * @return
- */
- public E pop(){
- //如果栈容器中没有元素,则抛出异常
- if(this.index==-1){
- throw new EmptyStackException();
- }
-
- //拿出元素后要记录元素个数
- this.size--;
- //如果有元素,则返回栈顶元素
- return (E)this.arr[index--];
- }
-
- /**
- * 向栈容器中添加元素
- * @param item
- * @return
- */
- public E push(E item){
- //初始化数组
- this.capacity();
-
- //向数组中添加元素
- this.arr[++index]=item;//index先+1得到下标0,再添加
-
- //记录元素个数
- this.size++;
- return item;
- }
-
- /**
- * 数组初始化或者以1.5倍容量对数组扩容
- */
- private void capacity(){
- //数组初始化
- if(this.arr==null){
- this.arr=new Object[this.stackLength];
- }
-
- //以1.5倍对数组扩容
- if(this.size-(this.stackLength-1)>=0){
- this.stackLength=this.stackLength+(this.stackLength>>1);
- this.arr= Arrays.copyOf(this.arr,this.stackLength);//扩容操作是创建新的数组,并且把原数组拷贝到更大的数组里,copyOf()可以一次性实现,第一个参数是要扩容的原数组,第二哥参数是要扩容的长度
- }
-
- }
-
- //自定义栈容器的测试
- public static void main(String[] args) {
- //实例化容器哦
- MyStack<String> myStack=new MyStack<>();
- myStack.push("a");
- myStack.push("b");
- myStack.push("c");
- myStack.push("d");
- myStack.push("e");
- myStack.push("f");
- System.out.println(myStack.size);
- System.out.println(myStack.pop());
- System.out.println(myStack.pop());
- System.out.println(myStack.pop());
-
- }
-
- }

创建链表接口:
- package studyweek6数据结构;
-
- /**
- * 创建链表结构,让单向链表和双向链表实现该接口即可
- *基于链表结构存取元素的方法API定义
- * @param <E>
- */
- public interface MyList<E> {
- void add(E element);
- E get(int index);
- int size();
- E remove(int index);
- }
- package studyweek6数据结构;
-
-
- /**
- * 基于单向链表实现元素存取的容器
- * @param <E>
- */
-
- public class MySinglyLinkedList<E> implements MyList<E> {
-
- /**
- * 定于单向链表的节点对象(使用节点内部类来实现)
- */
- class Node<E>{
- private E item;//存储元素
- private Node next;//存储下一个节点对象的成员变量的的地址
-
- Node(E item,Node next){
- this.item=item;
- this.next=next;
- }
- }
-
- private Node head;//存放链表中的头节点(第一个节点)
- private int size;//记录元素的个数
-
- /**
- * 向链表中添加元素
- * @param element
- */
- @Override
- public void add(E element) {
- //创建节点
- Node<E> node=new Node<>(element,null);
- //找到尾节点
- Node tail=getTail();
- //节点的挂接
- if(tail==null){
- this.head=node;
- }else{
- tail.next=node;
- }
- //记录元素个数
- this.size++;
- }
-
- /**
- * 找尾节点
- */
- private Node getTail(){
- //判断头节点是否存在
- if(this.head==null){
- return null;
- }
-
- //查找尾节点
- Node node=this.head;
- while(true){
- if(node.next==null)break;
- node=node.next;
- }
- return node;
- }
-
-
-
- /**
- * 根据元素的位置获取元素
- * @param index
- * @return
- */
- @Override
- public E get(int index) {
- //校验Index的合法性
- this.checkIndex(index);
- //根据位置获取指定字节
- Node<E> node=this.getNode(index);
- //返回该节点中的元素
- return node.item;
- }
- /**
- * 对index合法性进行校验
- */
- private void checkIndex(int index){
- if(!(index>=0&&index<this.size)){
- throw new IndexOutOfBoundsException("Index:"+index+"Size"+this.size);
- }
- }
- /**
- * 根据位置获取节点
- */
- private Node getNode(int index){
- Node<E> node=this.head;
- for(int i=0;i<index;i++){
- node=node.next;
- }
- return node;
- }
-
-
-
- /**
- * 获取元素个数的方法
- * @return
- */
- @Override
- public int size() {
- return this.size;
- }
-
-
- /**
- * 根据元素的位置删除元素
- * @param index
- * @return
- */
- @Override
- public E remove(int index) {
- //校验Index的合法性
- this.checkIndex(index);
- //根据位置找到该节点对象
- Node<E> node=this.getNode(index);
- //获取该节点对象的元素
- E item=node.item;
- //删除该节点对象
- //判断当前删除的节点是否为头节点
- if(this.head==node){
- this.head=node.next;
- }else{
- Node<E> temp=this.head;
- for(int i=0;i<index-1;i++){
- temp=temp.next;//temp会循环到node前一个节点
- }
- temp.next=node.next;//node前一个节点的下一个节点指向node的下一个节点,这样就可以跳过node节点
- }
- node.next=null;
- //记录元素个数
- this.size--;
- //将被删除的元素返回
- return item;
- }
-
- public static void main(String[] args) {
- MySinglyLinkedList<String> mySinglyLinkedList=new MySinglyLinkedList<>();
- mySinglyLinkedList.add("a");
- mySinglyLinkedList.add("b");
- mySinglyLinkedList.add("c");
- mySinglyLinkedList.add("d");
- System.out.println(mySinglyLinkedList.size());
- System.out.println(mySinglyLinkedList.remove(0));
- for(int i=0;i< mySinglyLinkedList.size;i++){
- System.out.println(mySinglyLinkedList.get(i));
- }
-
- }
- }

- package studyweek6数据结构;
-
- public class MyDoublyLinkedLIst<E> implements MyList<E>{
- /**
- * 定义双向链表的节点对象
- */
- class Node<E>{
- E item;//记录元素
- Node<E> prev;//记录前一个节点对象
- Node<E> next;//记录下一个节点对象
- Node(Node<E> prev,E item,Node<E> next){
- this.item=item;
- this.next=next;
- this.prev=prev;
- }
- }
-
-
- private Node head;//记录头节点
- private Node tail;//记录尾节点
- private int size;//记录元素个数
- /**
- * 向双向链表中添加元素
- * @param element
- */
- @Override
- public void add(E element) {
- this.linkLast(element);
- }
- /**
- * 将节点对象添加到双向链表的尾部
- */
- private void linkLast(E element){
- //获取尾节点
- Node t=this.tail;
- //创建节点对象
- Node<E> node=new Node<>(t,element,null);
- //将新节点定义为尾节点
- this.tail=node;
- if(t==null){
- this.head=node;
- }else{
- t.next=node;
- }
- this.size++;
- }
-
-
-
- /**
- * 根据指定位置获取元素
- * @param index
- * @return
- */
- @Override
- public E get(int index) {
- //Index合法性检验
- this.checkIndex(index);
- //根据位置获取指定节点对象
- Node<E> node=this.getNode(index);
- return node.item;
- }
- /**
- * 校验Index的合法性
- */
- private void checkIndex(int index){
- if(!(index>=0&&index<this.size)){
- throw new IndexOutOfBoundsException("Index"+index+"Size"+size);
- }
- }
- /**
- * 根据位置获取指定节点对象
- */
- private Node getNode(int index){
- //由于双向链表可以往任意一边开始查找,因此可以先判断当前位置距离头或者尾节点哪个更近
- if(index<(this.size>>1)){
- Node node=this.head;
- for(int i=0;i<index;i++){
- node=node.next;//移动node指针
- }
- return node;
- }else{
- Node node=this.tail;
- for(int i=this.size-1;i>index;i--){
- node=node.prev;
- }
- return node;
- }
- }
-
-
- /**
- * 返回元素个数
- * @return
- */
- @Override
- public int size() {
- return this.size;
- }
-
-
- /**
- * 根据指定位置删除元素
- * @param index
- * @return
- */
- @Override
- public E remove(int index) {
- //对index进行合法性校验
- this.checkIndex(index);
- //根据指定位置获取节点对象
- Node<E> node=this.getNode(index);
- //获取节点对象中的元素
- E item=node.item;
- //判断当前节点是否为头节点
- if(node.prev==null){//头节点的prev为空
- this.head=node.next;
- }else{
- //完成当前节点的直接前驱节点与当前节点的直接后继节点的挂接
- node.prev.next=node.next;
- }
- //判断当前节点是否为尾节点
- if(node.next==null){
- this.tail=node.prev;
- }else{
- //完成当前节点的直接后继节点与当前节点的直接前驱节点的挂接
- node.next.prev=node.prev;
- }
-
- //移除出链表
- node.prev=null;
- node.next=null;
- node.item=null;
- this.size--;
- return item;
- }
-
- /**
- * 在双向链表的头添加元素
- */
- public void addFirst(E element){
- this.linkFirst(element);
- }
- private void linkFirst(E element){
- Node head=this.head;
- Node node=new Node<>(null,element,head);
- //将新节点定义为头节点
- this.head=node;
- //判断当前链表中是否有节点,如果没有,那么该节点既是头也是尾节点
- if(head==null){
- this.tail=node;
- }else{
- head.prev=node;
- }
- this.size++;
- }
-
- /**
- * 在双向链表的尾添加元素
- */
- public void addLast(E element){
- this.linkLast(element);
- }
-
-
-
- //测试
- public static void main(String[] args) {
- /*MyList<String> myList=new MyDoublyLinkedLIst<>();
- myList.add("a");
- myList.add("b");
- myList.add("c");
- myList.add("d");
- System.out.println(myList.remove(2));
- System.out.println(myList.size());
- for(int i=0;i<myList.size();i++){
- System.out.println(myList.get(i));
- }*/
-
- //由于新建的addFirst和addLast方法没有在接口里定义,因此想要使用,引用必须是 MyDoublyLinkedLIst类型
- MyDoublyLinkedLIst<String> list=new MyDoublyLinkedLIst<>();
- list.add("a");
- list.addFirst("A");
- list.addLast("B");
- for(int i=0;i<list.size();i++){
- System.out.println(list.get(i));
- }
- }
- }

二叉树(BinaryTree)是树形结构的一个重要类型。许多实际问题抽象出来的数据结构往往是二叉树形式,即使是一般的树也能简单地转换为二叉树,而且二叉树的存储结构及其算法都较为简单,因此二叉树显得特别重要。二叉树特点是每个结点最多只能有两棵子树,且有左右之分。
满二叉树:满二叉树指除最后一层外,每一层上的所有节点都有两个子节点。
完全二叉树:完全二叉树,除最后一层可能不满以外,其他各层都达到该层节点的最大数,最后一层如果不满,该层所有节点都全部靠左排。
二叉树遍历的方式:
前序遍历:根-左-右
中序遍历:左-根-右
后序遍历:左-右-根
层序遍历:从上至下逐层遍历
- package studyweek6数据结构;
-
- /**
- * 基于二叉树结构实现元素排序处理
- */
- public class BinaryTreeSort<E extends Integer>{//目前先实现整数的排序处理
- /**
- * 定义结点类
- */
- class Node<E extends Integer> {
- private E item;//存放元素
- private Node left;//存放左子树地址
- private Node right;//存放右子树地址
- Node(E item){
- this.item=item;
- }
- /**
- * 添加结点
- */
- public void addNode(Node node) {
- //完成新结点中的元素与当前结点中的元素的判断
- //如果新结点中的元素小于当前结点中的元素,那么新结点则放到当前结点的左子树中
- if (node.item.intValue() < this.item.intValue()) {
- if (this.left == null) {
- this.left = node;
- } else {
- this.left.addNode(node);//递归判断
- }
-
- }
- //如果新结点中的元素小于当前结点中的元素,那么新结点则放到当前结点的左子树中
- else {
- if(this.right==null){
- this.right=node;
- }
- else{
- this.right.addNode(node);
- }
- }
- }
-
- /**
- * 使用中序遍历二叉树
- */
- public void inorderTraversal(){
- //找到最左侧的那个结点
- if(this.left!=null){
- this.left.inorderTraversal();
- }
- System.out.println(this.item);
- if(this.right!=null){
- this.right.inorderTraversal();
- }
-
- }
- }
-
-
-
- /**
- * 将元素添加到排序器中
- */
- private Node root;//存放数的根结点的地址
- public void add(E element){
- //实例化结点对象
- Node<E> node=new Node<>(element);
- //判断当前二叉树中是否有根结点。如果没有那么新结点就是根结点
- if(this.root==null){
- this.root=node;
- }else{
- this.root.addNode(node);
- }
-
- }
-
-
- /**
- * 对元素进行排序
- */
- public void sort(){
- //判断根结点是否为空
- if(this.root==null)return;
- this.root.inorderTraversal();
- }
-
-
- //测试
- public static void main(String[] args) {
- BinaryTreeSort<Integer> sort=new BinaryTreeSort<>();
- //8,1,3,9,4,5
- sort.add(8);
- sort.add(1);
- sort.add(3);
- sort.add(9);
- sort.add(4);
- sort.add(5);
- sort.sort();
- }
- }

- package studyweek6数据结构;
-
- import java.util.ArrayList;
- import java.util.HashMap;
- import java.util.List;
- import java.util.Map;
-
- /**
- * 基于树形结构实现元素的储存器
- */
-
- public class MyTree <E>{
- private Map<E,E> map=new HashMap<>();//String->String
- private Map<E,List<E>> map2=new HashMap<>(); //String->List
-
- /**
- * 向容器中添加元素
- */
- public void add(E parent,E item){
- //完成单结点之间的映射
- this.map.put(item,parent);
- //完成多结点之间的映射
- List<E> list =this.map2.get(parent);
- if(list==null){
- list=new ArrayList<>();
- this.map2.put(parent,list);
- }
- list.add(item);
- }
-
-
- /**
- * 获取当前结点的父结点
- */
- public E getParent(E item){
- return this.map.get(item);
- }
-
-
- /**
- * 获取当前结点的子结点
- */
- public List<E> getChild(E item){
- return this.map2.get(item);
- }
-
-
- /**
- * 获取当前结点的兄弟结点
- */
- public List<E> getBrother(E item){
- //获取当前结点的父结点
- E parent=this.getParent(item);
- //获取当前父结点的所有子结点
- List<E> list=this.getChild(parent);
- List<E> brother=new ArrayList<>();//不能直接删除list里面的该结点,不然下面所有的子结点会丢失
- if(list!=null){
- brother.addAll(list);
- brother.remove(item);
- }
- return brother;
- }
-
-
- /**
- * 获取当前结点的祖先结点
- */
- public List<E> getForefathers(E item){
- //获取当前结点的父结点
- E parent=this.getParent(item);
- //结束递归的边界条件
- if(parent==null){
- return new ArrayList<>();
- }
- //递归调用,再次获取当前结点的父结点的父结点
- List <E> list=this.getForefathers(parent);//这里的list是当递归结束后会创建一个List去接受所得到的父节点的返回值
- //将递归到的所有结点元素添加到返回的List中
- list.add(parent);//弹栈时再执行
- return list;
- }
-
-
- /**
- * 获取当前结点的子孙结点
- */
- public List<E> getGrandChildren(E item){
- //存放所有子孙结点中的元素
- List<E> list=new ArrayList<>();
- //获取当前结点的子结点
- List<E> child=this.getChild(item);
- //结束递归的边界条件
- if(child==null){
- return list;
- }
- //遍历子结点
- for(int i=0;i<child.size();i++){
- //获取结点中的元素
- E ele=child.get(i);
- //递归调用
- List<E> temp=this.getGrandChildren(ele);
- list.add(ele);
- list.addAll(temp);
- }
- return list;
- }
-
-
- public static void main(String[] args) {
- //实例化容器
- MyTree<String> myTree=new MyTree<>();
- //添加元素
- myTree.add("root","生物");
- myTree.add("生物","植物");
- myTree.add("生物","动物");
- myTree.add("生物","菌类");
- myTree.add("动物","脊椎动物");
- myTree.add("动物","脊索动物");
- myTree.add("动物","腔肠动物");
- myTree.add("脊椎动物","哺乳动物");
- myTree.add("脊椎动物","鱼类");
- myTree.add("哺乳动物","猫");
- myTree.add("哺乳动物","牛");
- myTree.add("哺乳动物","人");
- System.out.println("-----------获取父结点-----------");
- String parent= myTree.getParent("鱼类");
- System.out.println(parent);
- System.out.println("-----------获取子结点-----------");
- List<String> child=myTree.getChild("动物");
- for (int i=0;i<child.size();i++){
- System.out.println(child.get(i));
- }
- System.out.println("-----------获取兄弟结点-----------");
- List<String> brother=myTree.getBrother("脊椎动物");
- for (int i=0;i<brother.size();i++){
- System.out.println(child.get(i));
- }
- System.out.println("-----------获取祖先结点-----------");
- List<String> foreFathers=myTree.getForefathers("人");
- for (int i=0;i<foreFathers.size();i++){
- System.out.println(foreFathers.get(i));
- }
- System.out.println("-----------h获取子孙结点-----------");
- List<String> grandChildren=myTree.getGrandChildren("root");
- for (int i=0;i<grandChildren.size();i++){
- System.out.println(grandChildren.get(i));
- }
- }
- }

Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。