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

    目录

    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
    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
    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(i1){
    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.性能对比

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

    • 查找和遍历时是数组性能更好，因为存储是挨在一起的。链表的话则需要通过指针来寻址。
    • 增加和删除时链表性能更好，因为数组中间元素的增加删除涉及后面元素的位移，明显不如链表只动一个元素的性能。
  • 相关阅读:
    计算机组成原理平时作业四
    Linux 中如何使用 id 命令
    C#&Winform&ListView实现缺陷图片浏览器
    apply()拦截proxy
    服务器环境搭建
    自动化测试类型有哪些？是怎么分类的
    javaEE -8（9000字详解网络编程）
    JDK多版本切换
    笔试强训第16天
    使用QT制作QQ登录界面
  • 原文地址：https://blog.csdn.net/Joker_ZJN/article/details/127797131