devbox
我家小花儿
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

数据结构（1）线性结构——数组、链表、堆栈、队列（介绍和JAVA代码实现）_队列链表堆栈和数都是线性数据结构

作者：我家小花儿 | 2024-05-03 06:32:00

赞

踩

队列链表堆栈和数都是线性数据结构

目录

1.1.线性表

1.1.1.数组

1.逻辑简介

 2.代码实现

 1.1.2.链表

1.逻辑简介

 2.代码实现

1.2.堆栈

1.2.1.逻辑简介

1.2.2.代码实现

1.3.队列

1.3.1.逻辑简介

1.3.2.代码实现

1.4.性能对比

1.1.线性表

线性表是指由同种元素构成的有序且线性的一种数据结构，由于其有序且线性的特点，可以抽象出对其的一个操作集：

  1. ElementType findKth(int k)//查找位序为K的元素
  2. int find(ElementType e)//查找元素e出现的第一次位置
  3. void insert(ElementType e,int i)//在位序i前面插入一个元素
  4. void delete(int i)//删除位序i的元素
  5. int length()//返回线性表的长度

线性表的实现有两种：

  • 数组
  • 队列

1.1.1.数组

1.逻辑简介

数组操作中要注意的操作是在中间插入或者删除，要涉及元素的位移。

在数组中间删除：

删除数组中间某个位置的元素，为了保持连续，后面的元素要挨个前移。

在数组中间插入：

在数组中间某个位置插入元素，首先要腾出位置，也就是说，该位置后面的元素要挨个后移

 2.代码实现

使用代码实现顺序表：

  1. public class Array{
  2. 	//数组
  3.     private Object[] array;
  4.     private int maxSize;
  5.     //初始化一个空数组
  6.     public void initArray(int maxSize){
  7.         this.maxSize=maxSize;
  8.         array=new Object[maxSize];
  9.     }
  10.     //查找位序为K的元素
  11.     public  Object findKth(int K){
  12.         return array[K];
  13.     }
  14.     //查找元素X第一次出现的位置
  15.     public  int find(Object X){
  16.         int i=0;
  17.         while(!X.equals(array[i])){
  18.             i++;
  19.         }
  20.         return i;
  21.     }
  22.     //查找最后一个非空元素位置的位序
  23.     public int findLastTh(Object[] targetArray){
  24.         int i=0;
  25.         for (int j=0;j<targetArray.length;j++){
  26.             if(array[j]!=null){
  27.                 i=j;
  28.             }
  29.         }
  30.         return i;
  31.     }
  32.     //在i位序插入一个元素
  33.     public void insert(Object X,int i){
  34.         System.out.println("当前数组的容量:"+array.length);
  35.         //判断是否存满，是否需要追加空间。
  36.         if(isFull()){
  37.             newSpace();
  38.         }
  39.  
  40.         //若插入位置上没有元素则直接插入
  41.         if(array[i]==null){
  42.             array[i]=X;
  43.         }
  44.         else
  45.         //若插入位置上有元素则当前位置开始顺序后移一位
  46.         {
  47.             for (int j = findLastTh(array); j >= i; j--) {
  48.                 array[j + 1] = array[j];
  49.             }
  50.             array[i] = X;
  51.         }
  52.     }
  53.     //判断数组是否已经存满
  54.     public boolean isFull(){
  55.         return array[array.length-1]!=null ? true:false;
  56.     }
  57.     //为数组开辟新空间
  58.     public void newSpace(){
  59.         //copy原数组
  60.         Object[] tempArry=this.array;
  61.             //记录原数组
  62.         //追加新空间,追加容量为初始化容量的一倍
  63.         array=new Object[maxSize+maxSize];
  64.         //将原数组元素，copy到新数组
  65.         for (int i=0;i<=findLastTh(tempArry);i++){
  66.               array[i]=tempArry[i];
  67.             }
  68.         System.out.println("扩容后数组容量:"+array.length);
  69.     }
  70.  
  71.     //打印表中所有元素
  72.     public void print() {
  73.         int i=0;
  74.         String s="";
  75.         while (i<=findLastTh(array)) {
  76.             s=s+i+":"+array[i]+"\t";
  77.             i++;
  78.         }
  79.         System.out.println(s);
  80.     }
  81. }

 1.1.2.链表

1.逻辑简介

链表操作中要注意的操作是在中间插入或者删除，要涉及指针的操作。

在链表中间删除：

在链表中间删除一个元素，即将该元素前一个节点的指针指向要删除节点的下一个节点，即要删除节点的指针所指向的位置，然后将要删除的节点的指针指向空。

 2.代码实现

链表中的每个节点：

  1. public class Node{
  2.         //数据域
  3.         Object data;
  4.         //指针域
  5.         Node next;
  6.  
  7.         public Object getData() {
  8.             return data;
  9.         }
  10.  
  11.         public void setData(Object data) {
  12.             this.data = data;
  13.         }
  14.  
  15.         public Node getNext() {
  16.             return next;
  17.         }
  18.  
  19.         public void setNext(Node next) {
  20.             this.next = next;
  21.         }
  22. }

使用链表实现顺序表：

  1. public class List {
  2.     //节点
  3.     public class Node{
  4.         //数据域
  5.         Object data;
  6.         //指针域
  7.         Node next;
  8.  
  9.         public Object getData() {
  10.             return data;
  11.         }
  12.  
  13.         public void setData(Object data) {
  14.             this.data = data;
  15.         }
  16.  
  17.         public Node getNext() {
  18.             return next;
  19.         }
  20.  
  21.         public void setNext(Node next) {
  22.             this.next = next;
  23.         }
  24.     }
  25.  
  26.     //尾指针
  27.     Node last;
  28.  
  29.     //遍历指针
  30.     Node flag;
  31.  
  32.     //头节点
  33.     Node header;
  34.  
  35.     //初始化头节点
  36.     //初始化末尾指针
  37.     public List(){
  38.         this.header=new Node();
  39.         this.header.setData("header");
  40.         this.last=header;
  41.     }
  42.  
  43.     //插入
  44.     public void insert(Object data){
  45.         Node newNode=new Node();
  46.         newNode.setData(data);
  47.         last.setNext(newNode);
  48.         //指针后移
  49.         last=newNode;
  50.     }
  51.  
  52.     //指定位置插入
  53.     //插入在指定节点的后面
  54.     //header位序为0，依次类推
  55.     //此方法无法实现直接挂在末尾，挂在末尾请用上面的无参insert()
  56.     public void insert(int X,Object data){
  57.         //遍历指针指向头节点
  58.         this.flag=header;
  59.         //计数器
  60.         int i=0;
  61.  
  62.         Node newNode=new Node();
  63.         newNode.setData(data);
  64.  
  65.         //查找动作
  66.         while(i<X){
  67.             flag=flag.getNext();
  68.             i++;
  69.         }
  70.         //删除动作
  71.         //后面节点挂在当前节点后
  72.         newNode.setNext(flag.getNext());
  73.         //当前节点挂在目标节点后
  74.         flag.setNext(newNode);
  75.     }
  76.  
  77.     //遍历打印链表
  78.     public void printf(){
  79.         //遍历指针指向头节点
  80.         this.flag=header;
  81.         //消息
  82.         String message="";
  83.         while (flag.getNext()!=null){
  84.             message=message+flag.getData()+"—>";
  85.             flag=flag.getNext();
  86.         }
  87.         //拼接最后一个节点
  88.         message=message+flag.getData()+"—>";
  89.  
  90.         System.out.println(message);
  91.     }
  92.  
  93.     //删除指定位序节点
  94.     public void delete(int X){
  95.         //遍历指针指向头节点
  96.         this.flag=header;
  97.         //计数器
  98.         int i=0;
  99.  
  100.         //查找动作
  101.         while(i<X-1){
  102.             flag=flag.getNext();
  103.             i++;
  104.         }
  105.  
  106.         //删除动作
  107.         flag.setNext(flag.getNext().getNext());
  108.  
  109.     }
  110. }

1.2.堆栈

1.2.1.逻辑简介

堆栈，一种后入先出（LIFO，last in frist out）或者叫先入后出（FILO，first in last out）的线性且有序的数据结构。

堆栈的操作集可抽象为：

  1. Boolean isFull();//判断堆栈是否已满
  2. Boolean isEmpty();//判断堆栈是否为空
  3. void push();//入栈
  4. void pop();//出栈

1.2.2.代码实现

此处的代码实现以数组来存储数据，数组进行出入堆栈的时候会涉及位移操作，比起链表来说还更复杂一点，链表的话直接操作指针的指向即可更加方便。

  1. public class Stack {
  2.     //数据域
  3.     Object[] stack;
  4.     //头指针
  5.     int first=0;
  6.     //尾指针
  7.     int last=-1;
  8.  
  9.     public Stack(int size){
  10.         stack=new Object[size];
  11.     }
  12.  
  13.     //判断堆栈是否已满
  14.     public Boolean isFull(){
  15.         return (stack.length-1)==last;
  16.     }
  17.  
  18.     //判断堆栈是否为空
  19.     public Boolean isEmpty(){
  20.         return last==-1;
  21.     }
  22.  
  23.     //入栈
  24.     public void push(Object o){
  25.         if(!isFull()) {
  26.             stack[++last] = o;
  27.         }
  28.     }
  29.  
  30.     //出栈
  31.     public Object pop(){
  32.         Object data=null;
  33.         if(!isEmpty()) {
  34.             data=stack[last];
  35.             stack[last] = null;
  36.             last--;
  37.         }
  38.         return data;
  39.     }

1.3.队列

1.3.1.逻辑简介

队列，一种先进先出（FIFO，first in first out）或者叫后进后出（LILO，last in last out）的线性且有序的数据结构。

队列的理解不难，就像我们生活中排队时的各种队列一样，就是先进先出，后进后出。

 队列的操作集可抽象为：

  1. Boolean isFull();//判断队列是否已满
  2. Boolean isEmpty();//判断队列是否为空
  3. void push();//入队
  4. void pop();//出队

1.3.2.代码实现

此处的代码实现以数组来存储数据，比起链表来说还更复杂一点，链表的话直接操作指针的指向即可更加方便。

  1. public class Queue {
  2.     //数据域
  3.     Object[] stack;
  4.     //头指针
  5.     int first=0;
  6.     //尾指针
  7.     int last=-1;
  8.  
  9.     public Queue(int size){
  10.         stack=new Object[size];
  11.     }
  12.  
  13.     public Boolean isFull(){
  14.         return (stack.length-1)==last;
  15.     }
  16.  
  17.     public Boolean isEmpty(){
  18.         return last==-1;
  19.     }
  20.  
  21.     public void push(Object o){
  22.         if(!isFull()) {
  23.             stack[++last] = o;
  24.         }
  25.     }
  26.  
  27.     public Object pop(){
  28.         Object o=stack[first];
  29.         //删除头元素，后续元素顺序前移
  30.         stack[first]=null;
  31.         if(!isEmpty()) {
  32.             for (int i = 1; i <=last; i++) {
  33.                 Object temp=stack[i];
  34.                 stack[i-1]=temp;
  35.             }
  36.             stack[last--]=null;
  37.         }
  38.         return o;
  39.     }
  40. }

1.4.性能对比

从链表和数组的结构特点和使用过程中可以看到，数组和链表在增删改查各个场景中性能各有优劣：

  • 查找和遍历时是数组性能更好，因为存储是挨在一起的。链表的话则需要通过指针来寻址。
  • 增加和删除时链表性能更好，因为数组中间元素的增加删除涉及后面元素的位移，明显不如链表只动一个元素的性能。
声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/我家小花儿/article/detail/528238
推荐阅读
相关标签

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

  

闽ICP备14008679号