常见数据结构

小鱼儿 2022-05-16 10:13 179阅读 0赞

### 数据结构的使用 ###

在我们的日常学习中，经常会使用系统定义的数据类型（基本数据类型），也会根据需要而去自定义数据类型，从而更加灵活方便地处理计算机的数据和内存。一旦变量中有数据，相应的就需要一些操纵数据的方法来求解实际问题，而数据结构就是计算机中存储和组织数据的一种特定方式，它将使得数据处理更加有效。

### 类型 ###

线性数据结构：链表，栈和队列

非线性数据结构：树和图

### 栈 ###

定义：

栈(stack)是一个有序线性表，只能在表的一端（栈顶，top）执行插入和删除操作，最后插入的元素将第一个被删除。即后进先出（LIFO)或者先进先出（FIFO）线性表

![70][]

主要操作：

void push(int data) ：将data(数据)插入栈

int pop()：删除并返回最后一个插入栈的元素

辅助操作

int top()：返回最后一个插入栈的元素，但不删除

int size()：返回存储在栈中元素的个数

int isEmpty()：判断栈中是否有元素

int isStackFull()：判断栈中是否存满元素

//基于数组实现栈
    public class ArrayStack {
        private int top;
        private int capacity;
        private int[] array;
        public ArrayStack(){
            capacity = 1;
            array = new int[capacity];
            top = -1;
        }
        public boolean isEmpty(){
            return top == -1;
        }
        public boolean isStackFull(){
            return (top == capacity-1);
        }
        public  void push(int data){
            if(isStackFull()){
                System.out.println("Stack Overflow");
            }else{
                array[++top] = data;
            }
        }
        public int pop(){
            if(isEmpty()){
                System.out.println("Stack isEmpty");
                return 0;
            }else{
                return array[top--];
            }
        }
    
        public void deleteStack(){
            top = -1;
        }
    }

### 队列 ###

定义:

队列（queue）是一种只能咋一端插入（队尾），在另一端删除（队首）的有序线性表。队列中第一个插入的元素也是第一个被删除的元素，即先进先出（FIFO）或后进后出（LILO）线性表

![70 1][]

主要操作：  
enQueue(int data)：在队列的队尾插入一个元素

int deQueue()：删除并返回队首的元素

辅助操作：  
int Front()：返回队首的元素，但不删除

int QueueSize()：返回队列中存储的元素个数

int isEmpty()：指明队列是否存储了元素

//基于简单循环数组实现队列
    public class ArrayQueue {
        private int front;
        private int rear;
        private int capacity;
        private int[] array;
        private ArrayQueue(int size){
            capacity = size;
            front = -1;
            rear = -1;
            array = new int[size];
        }
    
        public static ArrayQueue createQueue(int size){
            return new ArrayQueue(size);
        }
        public boolean isEmpty(){
            return front == -1;
        }
        public boolean isFull(){
            return ((rear+1)%capacity == front);
        }
        public int getQueueSize(){
            return ((capacity-front+rear+1)%capacity);
        }
    
        //在队列的队尾插入一个元素
        public void enQueue(int data){
            if(isFull()){
                System.out.println("Queue overflow");
            }else{
                rear = (rear+1)%capacity;
                array[rear] = data;
                if(front == -1){
                    front = rear;
                }
            }
        }
    
        //删除并返回队首的元素
        public int deQueue(){
            int data = 0;
            if(isEmpty()){
                System.out.println("Queue Empty");
            }else{
                data = array[front];
                    if(front == rear) {
                        front = rear - 1;
                    }else{
                        front = (front+1)%capacity;
                    }
            }
            return data;
        }
    
    }

### 链表 ###

定义：

相邻元素之间通过指针连接；

最后一个元素的后继指针值为null;

在程序执行过程中，链表的长度可以增加或缩小

链表的空间能够按需分配（直到系统内存耗尽）

没有内存空间的浪费（但是链表中的指针需要一些额外的内存开销）

![70 2][]

主要操作：

插入：插入一个元素到链表中

删除：移除并返回链表中指定位置的元素

辅助操作：  
删除链表：移除链表中的所有元素（清空链表）

计数：返回链表中元素的个数

查找：寻找从链表表尾开始的第n个结点（node）

//单向链表
    public class ListNode {
        private int data;
        private ListNode next;
        public ListNode(int data){
            this.data = data;
        }
        public void setData(int data){
            this.data = data;
        }
        public int getData(){
            return data;
        }
        public void setNext(ListNode next){
            this.next = next;
        }
        public ListNode getNext(){
            return next;
        }
    }

// 双向链表
    public class DLLNode {
        private int data;
        private DLLNode next;
        private DLLNode previous;
        public DLLNode(int data){
            this.data = data;
        }
        public void setData(int data){
            this.data = data;
        }
        public int getData(){
            return data;
        }
        public void setNext(DLLNode next){
            this.next = next;
        }
    
        public DLLNode getNext() {
             return this.next;
        }
        public void setPrevious(DLLNode previous){
            this.previous = previous;
        }
    
        public DLLNode getPrevious() {
            return previous;
        }
        
    }

// 单向链表操作
    public class ListNodeFun {
    
        //统计链表中节点个数
        public int listLength(ListNode headNode){
            int length = 0;
            ListNode currentNode = headNode;
            while(headNode.getNext() != null){
                length++;
                currentNode = currentNode.getNext();
            }
            return length;
        }
    
        //向链表中插入一个节点
        ListNode insertInLinkedList(ListNode headNode,ListNode nodeToInsert,int position){
            if(headNode == null){   //若链表为空，则插入
                return nodeToInsert;
            }
            int size = listLength(headNode);
            if(position>size+1 || position<1){
                System.out.println("Position of node to insert is invaild, the valid inputs are 1 to"+(size+1));
                return headNode;
            }
    
            if(position == 1){      //在链表开头插入
                nodeToInsert.setNext(headNode);
                return nodeToInsert;
            }else{
                //在链表中间或是结尾插入
                ListNode previousNode = headNode;
                int count = 0;
                while(count<position-1){
                    previousNode = previousNode.getNext();
                    count++;
                }
                ListNode currentNode = previousNode.getNext();
                nodeToInsert.setNext(currentNode);
                previousNode.setNext(nodeToInsert);
               //headNode = previousNode;
            }
            return headNode;
        }
    
        //从链表中删除一个节点
        public ListNode deleteNodeFormLinkedList(ListNode headNode,int position){
            int size = listLength(headNode);
            if(position>size || position<1){
                System.out.println("Position of node to insert is invaild, the valid inputs are 1 to"+(size+1));
                return headNode;
            }
            if(position == 1){    //删除单链表的表头结点
                ListNode currentNode = headNode.getNext();
                headNode = null;
                return currentNode;
            }else{              //删除中间或表尾节点
                ListNode previousNode = headNode;
                int count = 1;
                while(count<position){
                    previousNode = previousNode.getNext();
                    count++;
                }
                ListNode currentNode = previousNode.getNext();
                headNode.setNext(currentNode.getNext());
                currentNode = null;
            }
            return headNode;
        }
    
        //删除单向链表
        public void deleteLinkedList(ListNode head){
            ListNode auxilaryNode;
            ListNode iterator = head;
            while(iterator != null){
                auxilaryNode = iterator.getNext();
                iterator = null;     //在Java中，垃圾回收期将自动处理
                iterator = auxilaryNode;  //在实际应用中，不需要实现该内容
            }
        }
    }

后续数据结构待补充

[70]: /images/20220516/307a9dd3cec54d8fa5393b1d5e5e0028.png
[70 1]: /images/20220516/61ddaeb7cca04ee78701c166ec12b8ac.png
[70 2]: /images/20220516/0b56149c7f6343659dd3e00076961722.png