資料結構基礎總結

資料的邏輯結構

資料的存儲結構

單連結清單是遞歸結構

疊代是指從目前元素獲得集合中的後繼元素。

疊代功能由Tterable可疊代接口和Tterator疊代器接口實作。

棧和隊列

是兩種特殊的線性表，特殊之處在于插入和删除操作的位置受到限制。

棧：插入和删除隻允許線上性表的一端進行，後進先出。

隊列：插入和删除分别線上性表的兩端進行，先進先出。

數組：

1.數組是随機存取結構，這是數組最大的優點。

2.數組一旦占用一片存儲空間，這片存儲空間的位址和長度就确定的，不能更改，是以數組隻能進行指派、取值兩種随機存取操作，不能進行插入、删除操作。

3.解決資料溢出的辦法是，申請一個更大容量的數組并進行數組元素的複制，這樣擴充了順序表等結構的容量。

廣義表的特性：

1.線性結構

2.多層次結構，有深度

3.可共享

4.可遞歸

廣義表的操作主要有：

建立一個廣義表

判斷廣義表是否是空表

判斷指定資料元素是否為原子

求廣義表深度

周遊廣義表

插入一個資料元素

删除一個資料元素

二叉樹的三種次序周遊

先根次序：ABCDGEFH （中左右）

中根：DGBAECHF（左中右）

後根：GDBEHFCA（左右中）

樹的周遊主要有先根周遊和後根周遊兩種。

圖的周遊一般有兩種：深度優先搜尋和廣度優先搜尋。

基于線性表的查找算法主要有：順序查找、折半查找、分塊查找，分别适用于線性表、有序順序表、索引順序表。

分塊查找：将主表元素邏輯上分成若幹塊，分塊特性為“塊内無序，塊間有序”，換而言之，每塊中元素可無序存放，前一塊中任意一個元素的關鍵字均小于後一塊中所有元素的關鍵字。索引表儲存每塊元素的起始位置。

分塊查找步驟：

（1）查找索引表：（可用順序或折半）

（2）在一塊中查找：（可用順序或折半）

散清單

散列（hash）是一種按關鍵字編址的存儲和檢索方法。

散列函數

在資料元素的噶un尖子與該元素的存儲位置之間建立一種關系，将這種關系稱為散列函數（hash function）。

排序

常用：插入排序、交換排序、選擇排序、歸并排序。

插入排序算法有三種：直接插入排序、折半插入排序、希爾排序。

交換排序有兩種：冒泡排序和快速排序。

冒泡排序：

  public  static void buttleSort(int [] table){

       boolean exchange =true;

      for(int i=1;i<table.length&&exchange;i++){

           exchange=false;

           for(int j=0;j<table.length-i;j++){

               if(table[j]>table[j+1]){

                   int temp=table[j];

                   table[j]=table[j+1];

                   table[j+1]=temp;

                   exchange=true;

               }

           }

       }

   }

快速排序

在資料序列中選擇一個值作為比較 的基準值，每趟從資料庫序列的兩端開始比較交替進行，将小于基準值額元素交換到序列前端，将大于基準值的元素交換到序列後端，介于兩者之間的位置則成為基準值的最終位置，同時，序列被劃分為兩個子序列，再用同樣的方法分别對兩個子序列進行排序。

選擇排序

兩種：直接選擇排序和堆排序

直接選擇排序：每次選一個最小放在前端，将剩下的依次選最小，放前端最小之後。

堆排序：是完全二叉樹的應用。

歸并排序：将兩個已排序的子序列合并，形成一個排序資料序列，又稱兩路歸并排序。

本文出自 “” 部落格，請務必保留此出處