天天看點
傳回

查找概述

靜态查找表：隻作查找操作的查找表（順序查找、折半查找）

動态查找表：在查找過程中，同時插入新元素或删除舊元素（二叉排序樹）

1.順序查找表

     
  1.  int SequentialSearch(int *a,int n,int key){         
    2.       
  2.      int i;         
    3.       
  3.      for(i=1;i<=n;i++){//從1開始          
    4.       
  4.          if(a[i] == key){         
    5.       
  5.              return i;         
    6.       
  6.          }         
    7.       
  7.      }         
    8.       
  8.      return 0;         
    9.       
  9.  }        
    10.      
    
     
  1.  int SequentialSearch(int *a,int n,int key){         
    2.       
  2.      int i;         
    3.       
  3.      a[0] = key;//a[0]當做哨兵 ，不用每次都檢查越界問題          
    4.       
  4.      i = n;//循環從尾部開始          
    5.       
  5.      while(a[i] == key){         
    6.       
  6.          i--;         
    7.       
  7.      }         
    8.       
  8.      return i;         
    9.       
  9.  }         
    10.

2.有序查找表

     
  1.  int BinarySearch(int *a,int n,int key){//折半查找時間複雜度O(logn)          
    2.       
  2.      int mid,high,low;//需要有序表順序存儲，适合靜态查找表          
    3.       
  3.      low = 1;         
    4.       
  4.      high = n;         
    5.       
  5.      while(low<=high){//主循環          
    6.       
  6.          mid = (low + high)/2;         
    7.       
  7.          if(key>a[mid]){         
    8.       
  8.              low = mid + 1;         
    9.       
  9.          }         
    10.       
  10.          else if(key<a[mid]){         
    11.       
  11.              high = mid -1;         
    12.       
  12.          }         
    13.       
  13.          else{         
    14.       
  14.              return mid;         
    15.       
  15.          }         
    16.       
  16.      }         
    17.       
  17.      return 0;         
    18.       
  18.  }         
    19.      
    
     
  1.  int BinarySearch(int *a,int n,int key){//插值查找時間複雜度O(logn)          
    2.       
  2.      int mid,high,low;//核心是根據要查找的關鍵字key與查找表中最大最小記錄的關鍵字比較後的查找方法          
    3.       
  3.      low = 1;         
    4.       
  4.      high = n;         
    5.       
  5.      while(low<=high){//主循環          
    6.       
  6.          mid = low + (high - low) * (key - a[low])/(a[high] - a[low]);//關鍵步驟！          
    7.       
  7.          if(key>a[mid]){         
    8.       
  8.              low = mid + 1;         
    9.       
  9.          }         
    10.       
  10.          else if(key<a[mid]){         
    11.       
  11.              high = mid -1;         
    12.       
  12.          }         
    13.       
  13.          else{         
    14.       
  14.              return mid;         
    15.       
  15.          }         
    16.       
  16.      }         
    17.       
  17.      return 0;         
    18.       
  18.  }         
    19.

3.線性索引查找

索引：把一個關鍵字和與它對應的記錄相關聯的過程

1)稠密索引：将資料集中的每一個記錄對應一個索引項，索引項一定是按照關鍵碼有序排列的

2)分塊索引：把資料集分成若幹塊，塊内無序塊間有序。

索引結構為最大關鍵碼是存儲每一塊中的最大關鍵字，下一塊中的最小關鍵字也能比這一塊最大的關鍵字要大；塊數是記錄塊中的記錄個數；塊首指針是指向塊首資料元素的指針

步驟是在分塊索引中查找關鍵字所在的塊

表 動态 元素 叉
上一篇: 結構和其他資料形式 函數和指針
下一篇: 結構和其他資料形式 聯合簡介

繼續閱讀