数据结构（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.线性表
线性表是指由同种元素构成的有序且线性的一种数据结构，由于其有序且线性的特点，可以抽象出对其的一个操作集：
ElementType findKth(int k)//查找位序为K的元素int find(ElementType e)//查找元素e出现的第一次位置void insert(ElementType e,int i)//在位序i前面插入一个元素void delete(int i)//删除位序i的元素int length()//返回线性表的长度
线性表的实现有两种：
- 数组
- 队列
1.1.1.数组
1.逻辑简介
数组操作中要注意的操作是在中间插入或者删除，要涉及元素的位移。
在数组中间删除：
删除数组中间某个位置的元素，为了保持连续，后面的元素要挨个前移。
在数组中间插入：
在数组中间某个位置插入元素，首先要腾出位置，也就是说，该位置后面的元素要挨个后移
2.代码实现
使用代码实现顺序表：
public class Array{//数组private Object[] array;private int maxSize;//初始化一个空数组public void initArray(int maxSize){this.maxSize=maxSize;array=new Object[maxSize];}//查找位序为K的元素public Object findKth(int K){return array[K];}//查找元素X第一次出现的位置public int find(Object X){int i=0;while(!X.equals(array[i])){i++;}return i;}//查找最后一个非空元素位置的位序public int findLastTh(Object[] targetArray){int i=0;for (int j=0;j<targetArray.length;j++){if(array[j]!=null){i=j;}}return i;}//在i位序插入一个元素public void insert(Object X,int i){System.out.println("当前数组的容量:"+array.length);//判断是否存满，是否需要追加空间。if(isFull()){newSpace();}//若插入位置上没有元素则直接插入if(array[i]==null){array[i]=X;}else//若插入位置上有元素则当前位置开始顺序后移一位{for (int j = findLastTh(array); j >= i; j--) {array[j + 1] = array[j];}array[i] = X;}}//判断数组是否已经存满public boolean isFull(){return array[array.length-1]!=null ? true:false;}//为数组开辟新空间public void newSpace(){//copy原数组Object[] tempArry=this.array;//记录原数组//追加新空间,追加容量为初始化容量的一倍array=new Object[maxSize+maxSize];//将原数组元素，copy到新数组for (int i=0;i<=findLastTh(tempArry);i++){array[i]=tempArry[i];}System.out.println("扩容后数组容量:"+array.length);}//打印表中所有元素public void print() {int i=0;String s="";while (i<=findLastTh(array)) {s=s+i+":"+array[i]+"\t";i++;}System.out.println(s);}}
1.1.2.链表
1.逻辑简介
链表操作中要注意的操作是在中间插入或者删除，要涉及指针的操作。
在链表中间删除：
在链表中间删除一个元素，即将该元素前一个节点的指针指向要删除节点的下一个节点，即要删除节点的指针所指向的位置，然后将要删除的节点的指针指向空。
2.代码实现
链表中的每个节点：
public class Node{//数据域Object data;//指针域Node next;public Object getData() {return data;}public void setData(Object data) {this.data = data;}public Node getNext() {return next;}public void setNext(Node next) {this.next = next;}}
使用链表实现顺序表：
public class List {//节点public class Node{//数据域Object data;//指针域Node next;public Object getData() {return data;}public void setData(Object data) {this.data = data;}public Node getNext() {return next;}public void setNext(Node next) {this.next = next;}}//尾指针Node last;//遍历指针Node flag;//头节点Node header;//初始化头节点//初始化末尾指针public List(){this.header=new Node();this.header.setData("header");this.last=header;}//插入public void insert(Object data){Node newNode=new Node();newNode.setData(data);last.setNext(newNode);//指针后移last=newNode;}//指定位置插入//插入在指定节点的后面//header位序为0，依次类推//此方法无法实现直接挂在末尾，挂在末尾请用上面的无参insert()public void insert(int X,Object data){//遍历指针指向头节点this.flag=header;//计数器int i=0;Node newNode=new Node();newNode.setData(data);//查找动作while(i<X){flag=flag.getNext();i++;}//删除动作//后面节点挂在当前节点后newNode.setNext(flag.getNext());//当前节点挂在目标节点后flag.setNext(newNode);}//遍历打印链表public void printf(){//遍历指针指向头节点this.flag=header;//消息String message="";while (flag.getNext()!=null){message=message+flag.getData()+"—>";flag=flag.getNext();}//拼接最后一个节点message=message+flag.getData()+"—>";System.out.println(message);}//删除指定位序节点public void delete(int X){//遍历指针指向头节点this.flag=header;//计数器int i=0;//查找动作while(i<X-1){flag=flag.getNext();i++;}//删除动作flag.setNext(flag.getNext().getNext());}}
1.2.堆栈
1.2.1.逻辑简介
堆栈，一种后入先出（LIFO，last in frist out）或者叫先入后出（FILO，first in last out）的线性且有序的数据结构。
堆栈的操作集可抽象为：
Boolean isFull();//判断堆栈是否已满Boolean isEmpty();//判断堆栈是否为空void push();//入栈void pop();//出栈
1.2.2.代码实现
此处的代码实现以数组来存储数据，数组进行出入堆栈的时候会涉及位移操作，比起链表来说还更复杂一点，链表的话直接操作指针的指向即可更加方便。
public class Stack {//数据域Object[] stack;//头指针int first=0;//尾指针int last=-1;public Stack(int size){stack=new Object[size];}//判断堆栈是否已满public Boolean isFull(){return (stack.length-1)==last;}//判断堆栈是否为空public Boolean isEmpty(){return last==-1;}//入栈public void push(Object o){if(!isFull()) {stack[++last] = o;}}//出栈public Object pop(){Object data=null;if(!isEmpty()) {data=stack[last];stack[last] = null;last--;}return data;}
1.3.队列
1.3.1.逻辑简介
队列，一种先进先出（FIFO，first in first out）或者叫后进后出（LILO，last in last out）的线性且有序的数据结构。
队列的理解不难，就像我们生活中排队时的各种队列一样，就是先进先出，后进后出。
队列的操作集可抽象为：
Boolean isFull();//判断队列是否已满Boolean isEmpty();//判断队列是否为空void push();//入队void pop();//出队
1.3.2.代码实现
此处的代码实现以数组来存储数据，比起链表来说还更复杂一点，链表的话直接操作指针的指向即可更加方便。
public class Queue {//数据域Object[] stack;//头指针int first=0;//尾指针int last=-1;public Queue(int size){stack=new Object[size];}public Boolean isFull(){return (stack.length-1)==last;}public Boolean isEmpty(){return last==-1;}public void push(Object o){if(!isFull()) {stack[++last] = o;}}public Object pop(){Object o=stack[first];//删除头元素，后续元素顺序前移stack[first]=null;if(!isEmpty()) {for (int i = 1; i <=last; i++) {Object temp=stack[i];stack[i-1]=temp;}stack[last--]=null;}return o;}}
1.4.性能对比
从链表和数组的结构特点和使用过程中可以看到，数组和链表在增删改查各个场景中性能各有优劣：
- 查找和遍历时是数组性能更好，因为存储是挨在一起的。链表的话则需要通过指针来寻址。
- 增加和删除时链表性能更好，因为数组中间元素的增加删除涉及后面元素的位移，明显不如链表只动一个元素的性能。
一时失言乱红尘
我就是我
港控/mmm°
左手的ㄟ右手
还没有评论，来说两句吧...