天天看點
傳回

資料結構和算法資料結構和算法基本的概念和專業術語資料的邏輯結構資料的存儲結構常見的資料結構

資料結構和算法

程式設計好比是一台筆記本電腦，資料結構和算法就是電腦的内部的CPU，記憶體。

學習資料結構，可以讓我們明白資料在計算機中的存儲的方式，進而可以選擇更加合理的結構來存儲資料，進而提高程式的執行效率，節約資源。

資料結構和算法的重要性

  1. 算法是程式的靈魂，優秀的程式可以在海量資料計算時，依然保持高速計算
  2. 一般來說，程式會使用記憶體計算架構和緩存技術來優化程式。核心架構的主要功能是通過算法來實作

資料結構和算法的關系

資料結構是一門研究組織資料方式的學科，在程式設計語言中，使用良好的結構可以大幅度提升程式的效率

要學好資料結構 就需要多考慮如何将生活中遇到問題 用程式思維區解決解決

程式= 資料結構 + 算法

資料結構是算法的基礎

public static void main(String[] args) {
        String str = "Java ,Java   ,hello , world";
        String newStr = str.replaceAll("Java","中國");//算法
        System.out.println(newStr);
    }

基本的概念和專業術語

  1. 資料(data):所有能輸入到計算機中的描述客觀事物的符号
  2. 資料元素（data element） 資料的基本機關也稱為結點或記錄
  3. 資料項（data item） 有獨立含義的資料的最小機關 也稱為域

三者之間的關系： 資料> 資料元素> 資料項

  1. 資料對象 相同特性的資料元素的集合 是資料的一個子集

整數資料對象 N = {0,1,2,3,4，…}

學生資料對象 學生記錄的集合 ：學生表 > 個人記錄>學号 姓名，年齡

  1. 資料結構（data Structure） 是互相存在的資料元素之間通過一種或多種特定關系組織在一起的集合

資料結構是帶“結構”的資料元素的集合，“結構”就是值資料元素之間存在的關系

資料的邏輯結構

資料元素間的這種抽象關系，是與存儲無關的 是從具體問題抽象出來的數學模型

劃分方法一：

​ 1. 線性結構

​ 線性結構作為最常見一種資料結構，特點是資料元素之間存在一對一的線性關系

​ 線性結構有兩種不同的存儲結構：

  • 順序的存儲結構：順序表 存儲的元素是連續的
  • 鍊式存儲結構：連結清單 連結清單中的元素不一定是連續的。元素結點中存放資料元素和相鄰元素的位址資訊

​ 線性結構常見：數組 棧 隊列 連結清單

​ 2. 非線性結構

​ 二維數組 多元數組 樹結構 圖結構

資料的存儲結構

存儲結構就是實體結構，資料元素以及互相的關系在計算機中存儲的方式

順序存儲結構-- 借助于元素在存儲容器中的相對位置來表示元素間的邏輯關系

鍊式存儲結構–借助于元素存儲位址的指針表示元素間的邏輯關系

常見的資料結構

線性結構

數組

數組:Array,是有序的元素序列，數組是在記憶體中開辟一段連續的空間，并在此空間存放元素。

特點：

  • 查找元素快：通過索引，可以快速通路指定位置的元素
  • 增删元素慢
  • 指定索引位置增加元素：需要建立一個新數組，将指定新元素存儲在指定索引位置，再把原數組元素根據索引，複制到新數組對應索引的位置。如下圖
    資料結構和算法資料結構和算法基本的概念和專業術語資料的邏輯結構資料的存儲結構常見的資料結構
  • 指定索引位置删除元素：需要建立一個新數組，把原數組元素根據索引，複制到新數組對應索引的位置，原數組中指定索引位置元素不複制到新數組中。如下圖
    資料結構和算法資料結構和算法基本的概念和專業術語資料的邏輯結構資料的存儲結構常見的資料結構

棧（stack）

  • 棧：stack,又稱堆棧，它是運算受限的線性表，其限制是僅允許在标的一端進行插入和删除操作，不允許在其他任何位置進行添加、查找、删除等操作。

棧結構的特點：

  1. 對于元素的操作隻能從一端開始
  2. 先進後出，後進先出
資料結構和算法資料結構和算法基本的概念和專業術語資料的邏輯結構資料的存儲結構常見的資料結構
  • 壓棧：就是存元素。即，把元素存儲到棧的頂端位置，棧中已有元素依次向棧底方向移動一個位置。
  • 彈棧：就是取元素。即，把棧的頂端位置元素取出，棧中已有元素依次向棧頂方向移動一個位置。

棧的常見操作：以下 方法也是棧操作的規範

  1. 入棧
  2. 出棧
  3. 判斷棧是否為空
  4. 判斷棧是否已滿
  5. 傳回棧頂元素
  6. 傳回元素在棧中的位置
  7. 傳回棧的實際長度
  8. 傳回棧的容量
  9. 列印棧

棧接口

public interface IStack {
    //1 入棧
     boolean  push(Object obj);
    //	2 出棧
    Object pop();
    //	3 判斷棧是否為空
     boolean isEmpty();
    //	4 判斷棧是否已滿
     boolean isFull();
    //	5 傳回棧頂元素
     Object peek();
    //	6 傳回元素在棧中的位置
    int getIndex(Object obj);
    //	7 傳回棧的實際長度
    int size();
    //	8 傳回棧的容量
    int getStatckSize();
    //	9  列印棧
    void  display();
}

棧的實作：

用數組模拟棧的結構

public class StackImpl  implements IStack {
    //定義棧的屬性
    private  Object[] data = null;
    private int top = -1;// 棧頂
    private int maxSize = 0 ;// 表示棧的容量
    public StackImpl(){// 預設初始化一個容量為10的棧
        this(10);
    }
    // 建立一個棧結構 并對棧進行初始化
    public StackImpl(int initialSize){
        if(initialSize >= 0){
            this.data = new Object[initialSize];
            this.maxSize = initialSize;
            this.top=-1;
        }
    }
    @Override
    public boolean push(Object obj) {
        if(isFull()){//如果棧已滿
            System.out.println("棧已滿，入棧失敗！");
            return  false;
        }
        top++;// 更新棧頂指針
        data[top] = obj;//将元素儲存到棧中
        return true;
    }

    @Override
    public Object pop() {
        if(isEmpty()){
            System.out.println("棧為空，沒有可出棧的元素");
            return null;
        }
       Object topObj =  data[top];// 擷取棧頂元素
        top--;
        return topObj;
    }

    @Override
    public boolean isEmpty() {
        return top == -1 ? true:false;
    }

    @Override
    public boolean isFull() {
        return  top >= maxSize -1? true:false;
    }

    @Override
    public Object peek() {
        if(isEmpty()){
            System.out.println("棧為空，沒有可出棧的元素");
            return null;
        }
        return data[top];
    }

    @Override
    public int getIndex(Object obj) {
        // 需要不斷的擷取棧頂和目标元素進行比較
        while(top != -1){
            if( peek().equals(obj)){
                return  top;
            }
            top--;
        }
        return -1;// 表示元素不存在
    }

    @Override
    public int size() {
        return 0;
    }

    @Override
    public int getStatckSize() {
        return this.top +1;
    }

    @Override
    public void display() {
        while(top != -1){
            System.out.println(data[top]);
            top--;
        }
    }

    public static void main(String[] args) {
        // 建立一個棧
        IStack stack = new StackImpl();
        // 入棧
        for(int i = 0 ; i < 10 ;i++){
            stack.push(i);
        }
        stack.push("aa");
        stack.display();
    }
}

練習：利用棧實作字元串逆序

思路：将字元串轉換為字元數組 在将字元數組中的字元逐個入棧， 然後再出棧

隊列

  • 隊列：queue,簡稱隊，它同堆棧一樣，也是一種運算受限的線性表，其限制是僅允許在表的一端進行插入，而在表的另一端進行删除。
  • 先進先出（即，存進去的元素，要在後它前面的元素依次取出後，才能取出該元素）。例如，小火車過山洞，車頭先進去，車尾後進去；車頭先出來，車尾後出來。
  • 隊列的入口、出口各占一側。例如，下圖中的左側為入口，右側為出口。

實作：

資料結構和算法資料結構和算法基本的概念和專業術語資料的邏輯結構資料的存儲結構常見的資料結構

解決假溢出：

資料結構和算法資料結構和算法基本的概念和專業術語資料的邏輯結構資料的存儲結構常見的資料結構

這種隊列稱為循環隊列。

如何判斷循環隊列究竟是空還是滿：

方法一：

​ 設定一個标志flag 初始的時候 falg = 0 ；每當入隊一次 就讓flage =1；每當出隊一次 就讓flag = 0；則隊列為空的判斷條件：flag == 0 && front == rear；隊列為滿的條件： flag ==1 && front == rear

方法二： 預留一個元素的存儲空間，此時 隊列未滿的判斷條件 （rear + 1 ）% maxSize == front

隊列為空 front == rear

方法三： 設計一個計數器 count 統計隊列中元素的個數

​ 隊列滿的條件 cout > 0 && front==rear

​ 隊列為空的條件： count == 0

入隊：rear = （rear +1） % maxSize

出隊 ： front = （front + 1） % maxSize

使用方式三實作循環隊列

public interface IQueue {
    //入隊
     void  append(Object obj);
    // 出隊
    Object delete();
    //獲得對頭元素
    Object getFront();
    // 判斷隊列是否為空
    boolean isEmpty();
}
           
public class CircleQueue  implements IQueue {
    // 定義隊列相關的成員屬性
    int  front;//對頭
    int rear;//隊尾
    int count;//統計元素個數
    int maxSize;//隊列的最大長度
    Object[] queue;//隊列
    public CircleQueue(int initalSize){
        front=rear=0;
        count = 0;
        maxSize = initalSize;
        queue = new Object[initalSize];
    }
    public CircleQueue(){
        this(10);
    }
    @Override
    public void append(Object obj) throws Exception {
        if(count>0 && front == rear){
            throw  new Exception("隊列已滿  ，入隊失敗");
        }
        queue[rear] = obj;
        rear = (rear +1 )% maxSize;
        count++;
    }

    @Override
    public Object delete() throws Exception {
        if(isEmpty()){
            throw  new Exception("隊列為空 ，入隊失敗");
        }
        Object obj = queue[front];
        front = (front+1)%maxSize;
        count--;
        return obj;
    }

    @Override
    public Object getFront() throws Exception {
        if(!isEmpty()){
            Object obj = queue[front];
            return  obj;
        }else{
            return  null;
        }
    }

    @Override
    public boolean isEmpty() {
        return count==0;
    }
}

測試

public static void main(String[] args) throws Exception {
        CircleQueue queue = new CircleQueue(5);
        queue.append("a");
        queue.append("b");
        queue.append("c");
        queue.append("d");
        queue.append("e");
        //queue.append("f");
      Object o1=   queue.delete();
        Object o2=   queue.delete();
//        Object o3=   queue.delete();
//        Object o4=   queue.delete();
        System.out.println(o1);
        System.out.println(o2);
        queue.append("g");
        System.out.println("---------------");
        while(!queue.isEmpty()){
            System.out.println(queue.delete());
        }
    }

連結清單

連結清單:linked list,由一系列結點node（連結清單中每一個元素稱為結點）組成，結點可以在運作時動态生成。每個結點包括兩個部分：一個是存儲資料元素的資料域，另一個是存儲下一個結點位址的指針域。

資料結構和算法資料結構和算法基本的概念和專業術語資料的邏輯結構資料的存儲結構常見的資料結構

連結清單是一種線性表，但是并不會按照線性的順序存儲資料，而是在每一個結點裡存放下一個結點的指針。

特點：

  • 多個結點之間，通過位址進行連接配接。例如，多個人手拉手，每個人使用自己的右手拉住下個人的左手，依次類推，這樣多個人就連在一起了。
    資料結構和算法資料結構和算法基本的概念和專業術語資料的邏輯結構資料的存儲結構常見的資料結構
  • 查找元素慢：想查找某個元素，需要通過連接配接的節點，依次向後查找指定元素
  • 增删元素快：
    • 增加元素：隻需要修改連接配接下個元素的位址即可。
資料結構和算法資料結構和算法基本的概念和專業術語資料的邏輯結構資料的存儲結構常見的資料結構
  • 删除元素：隻需要修改連接配接下個元素的位址即可。
資料結構和算法資料結構和算法基本的概念和專業術語資料的邏輯結構資料的存儲結構常見的資料結構

單向連結清單

單向連結清單 一個單連結清單的結點分為兩部分，第一部分儲存結點的資料，第二部分儲存下一個結點的位址。最後一個節點存儲位址的部分指向空值。

單向連結清單隻可以向一個方向周遊，查找一個結點的時候，都需要從一個節點開始每次通路下一個結點，一直到需要的位置

資料結構和算法資料結構和算法基本的概念和專業術語資料的邏輯結構資料的存儲結構常見的資料結構
public class SingleLinkedList {
    // 連結清單的結點的個數
    private int size;
    //頭結點
    private Node head;
    public  SingleLinkedList(){
        size = 0;a
        head= null;
    }
    // 連結清單的結點類
    private class Node{
        private Object data;//結點的資料域
        private Node next;//下一個結點的指針
        public Node(Object data){
            this.data = data;
        }
    }
    // 給連結清單添加元素  C->B->A
    public Object addHead(Object data){
        Node newHead = new Node(data);// 建立一個新的結點
        if(size == 0 ){
            head = newHead;
        }else{
            newHead.next = head;//新結點的指針指向原來的頭結點
            head = newHead;//頭結點指向新的結點
        }
        size++;
        return data;
    }
    // 删除結點  在連結清單頭不删除結點
    public  Object deleteHead(){
        Object obj = head.data;
        head = head.next;
        size--;
        return obj;
    }
    //在連結清單中查找指定的元素，找到了傳回結點Node，沒找到則傳回null
    public Node find(Object data){
        Node current = head;//定義一個指針，指向目前比較的結點
        int tempSize = size;// 擷取目前連結清單中元素的個數
        while(tempSize > 0 ){
            if(data.equals(current.data)){
                return  current;
            }else{
                current = current.next;
            }
            tempSize--;
        }
        return  null;
    }
    // 删除指定的元素  删除成功傳回true   否則傳回false
    public  boolean delete(Object data){
        if(size == 0 ){
            return  false;
        }
        // 擷取删除結點的前一個結點和他的後一個結點
        Node current = head;
        Node previous = head;
        while(!current.data.equals(data)){
            if (current.next == null){// 判斷是否到達連結清單的結尾
                return  false;
            }else{// 目前結點不是我們要删除的結點 并且沒有到達結點的末尾
                previous = current;//移動前一個結點的指針
                current = current.next;//移動目前結點的指針指向下一個
            }
        }
        // 此時表明找到了要删除的結點， 判斷 删除的結點是否是頭結點
        if(current == head){
            head = current.next;
            size--;
        }else{//不是頭結點
            previous.next =current.next;
            size--;
        }
        return  true;
    }
    // 判斷結點是否為空
    public  boolean isEmpty(){
        return  size==0;
    }
    // 周遊連結清單
    public  void  display(){
        if(size > 0 ){
            Node node = head;
            int tempSize = size;
            if(tempSize == 1){// 如果目前連結清單隻有一個頭結點
                System.out.println("[" + node.data+"]");
                return;
            }
            while(tempSize >0 ){
                if(node.equals(head)){
                    System.out.print("[" + node.data+"->");
                }else if(node.next == null){
                    System.out.print( node.data+"]");
                }else{
                    System.out.print(node.data+"->");
                }
                node= node.next;
                tempSize--;
            }
            System.out.println();
        }else{// 連結清單沒有結點
            System.out.println("[]");
        }
    }
}

測試

public class SingleLinkListTest {
    public static void main(String[] args) {
        SingleLinkedList sls = new SingleLinkedList();
        sls.addHead("A");
        sls.addHead("B");
        sls.addHead("C");
        sls.addHead("D");
        sls.display();
        //測試删除元素 删除C
        sls.delete("C");
        sls.display();
        //查找B
        System.out.println(sls.find("C"));
    }
}

雙向連結清單

雙向連結清單的

資料結構和算法資料結構和算法基本的概念和專業術語資料的邏輯結構資料的存儲結構常見的資料結構

循環連結清單：

棧 隊列 連結清單的差別

棧 隊列是線性表，操作受限。

差別：在于運算規則不同

連結清單和數組：

  1. 占用的記憶體空間：連結清單存放的記憶體空間可以是連續的，也可以是不連續的，數組一定是連續的。
  2. 長度的可變性：連結清單的長度可以根據實際需要 自定伸縮。數組長度一旦定義 則不能改變。

  3. 資料的通路：

    連結清單的通路：需要移動通路，通路不便捷

    數組的通路：數組方問更加便捷

  4. 使用場景：

    數組更加适合資料量大 ，而且需要進行頻繁的通路元素

    連結清單更加适合删除，插入等操作

棧的特點：

  • 邏輯結構：一對一
  • 存儲結果：順序棧 鍊棧
  • 運算規則：後進先出 先進後出

隊列的特點：

  • 邏輯結構：一對一
  • 存儲結果：順序隊 鍊隊
  • 運算規則：先進先出

連結清單的特點：

  • 邏輯結構：一對一
  • 存儲結果：順序表 連結清單
  • 運算規則：随機 順序存放

非線性結構

樹結構

二叉樹

  • 二叉樹：binary tree ,是每個結點不超過2的有序樹（tree） 。
資料結構和算法資料結構和算法基本的概念和專業術語資料的邏輯結構資料的存儲結構常見的資料結構

每一個元素稱為結點

A 根節點

B C D 父節點

葉子結點： 沒有子節點的節點（H E F G）

樹的高度：最大的層數

子樹

森林 多顆子樹構成森林

每個結點最多隻有兩個子節點的形式的樹稱為二叉樹

如果所有的二叉樹的葉子結點都在最後一次。節點數 = 2^n - 1 n就是他的層數 将這樣的二叉樹稱為滿二叉樹

二叉樹的周遊

前序周遊：先輸出父節點 再周遊左子樹和右子樹

中序周遊：先周遊左子樹 在輸出父節點 最後周遊右子樹

後序周遊：先周遊左子樹 再周遊右子樹 最後輸出父節點

層序周遊：按照層級逐層周遊

資料結構和算法資料結構和算法基本的概念和專業術語資料的邏輯結構資料的存儲結構常見的資料結構

紅黑樹

紅黑樹本身就是一顆二叉查找樹，将結點插入後，該樹仍然是一顆二叉查找樹。也就意味着，樹的鍵值仍然是有序的。

紅黑樹是一種含有紅黑結點并能自平衡的二叉樹。他必須滿足一下的性質：

紅黑樹的限制:

  1. 節點可以是紅色的或者黑色的
  2. 根節點是黑色的
  3. 葉子節點(特指空節點)是黑色的
  4. 每個紅色節點的子節點都是黑色的
  5. 任何一個節點到其每一個葉子節點的所有路徑上黑色節點數相同
資料結構和算法資料結構和算法基本的概念和專業術語資料的邏輯結構資料的存儲結構常見的資料結構

紅黑樹的特點:

速度特别快,趨近平衡樹,查找葉子元素最少和最多次數不多于二倍

上一篇: MySQL學習小結（一）常用的查詢語句
下一篇: jsp--1.配置