数据结构（1）线性结构——数组、链表、堆栈、队列（介绍和JAVA代码实现）
详细介绍、数组、链表、堆栈、队列，包含JAVA版代码实现
·
目录
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.性能对比
从链表和数组的结构特点和使用过程中可以看到，数组和链表在增删改查各个场景中性能各有优劣：
- 查找和遍历时是数组性能更好，因为存储是挨在一起的。链表的话则需要通过指针来寻址。
- 增加和删除时链表性能更好，因为数组中间元素的增加删除涉及后面元素的位移，明显不如链表只动一个元素的性能。
魔乐社区（Modelers.cn) 是一个中立、公益的人工智能社区，提供人工智能工具、模型、数据的托管、展示与应用协同服务，为人工智能开发及爱好者搭建开放的学习交流平台。社区通过理事会方式运作，由全产业链共同建设、共同运营、共同享有，推动国产AI生态繁荣发展。
更多推荐
0
0- 0
已为社区贡献4条内容
所有评论(0)