数据结构&算法 线性搜索

• 

  线性搜索

  线性搜索是一种非常简单的搜索算法。在这种类型的搜索中，对所有项目进行逐个搜索。检查每个项目，如果找到匹配项，则返回该特定项目，否则搜索将继续到数据收集结束。

  
• 

  算法

  
  Linear Search ( Array A, Value x)
  
  步骤 1: 设置 i 为 1
  步骤 2: 如果 i > n 那么跳到步骤 7
  步骤 3: 如果 A[i] = x 那么跳到步骤 6
  步骤 4: 设置 i 为 i + 1
  步骤 5: 跳到步骤 2
  步骤 6: 打印在索引i处找到的元素x并转到步骤8
  步骤 7: 打印元素未找到
  步骤 8: 退出
  

  伪代码

  
  procedure linear_search (list, value)
  
     for each item in the list
        if match item == value
           return the item's location
        end if
     end for
  
  end procedure
  

  用C编程语言实现线性搜索-

  
  #include <stdio.h>
  
  #define MAX 20
  
  // array of items on which linear search will be conducted.
  int intArray[MAX] = {1,2,3,4,6,7,9,11,12,14,15,16,17,19,33,34,43,45,55,66};
  
  void printline(int count) {
     int i;
    
     for(i = 0;i < count-1;i++) {
        printf("=");
     }
    
     printf("=\n");
  }
  
  // this method makes a linear search. 
  int find(int data) {
  
     int comparisons = 0;
     int index = -1;
     int i;
  
     // navigate through all items 
     for(i = 0;i < MAX;i++) {
    
        // count the comparisons made 
        comparisons++;
      
        // if data found, break the loop
        if(data == intArray[i]) {
           index = i;
           break;
        }
     }   
    
     printf("Total comparisons made: %d", comparisons);
     return index;
  }
  
  void display() {
     int i;
     printf("[");
    
     // navigate through all items 
     for(i = 0;i < MAX;i++) {
        printf("%d ",intArray[i]);
     }
    
     printf("]\n");
  }
  
  void main() {
     printf("Input Array: ");
     display();
     printline(50);
    
     //find location of 1
     int location = find(55);
  
     // if element was found 
     if(location != -1)
        printf("\nElement found at location: %d" ,(location+1));
     else
        printf("Element not found.");
  }
  

  尝试一下

  如果我们编译并运行上述程序，它将产生以下结果-

   
  Input Array: [1 2 3 4 6 7 9 11 12 14 15 16 17 19 33 34 43 45 55 66 ]
  ==================================================
  Total comparisons made: 19
  Element found at location: 19