数据结构之查找的概念及简单实现

ゝ一世哀愁。 2022-05-30 04:06 134阅读 0赞

**查找的概念**

**查找**是根据给定的某个值，在查找表中确定一个其关键字等于给定值的数据元素。

**查找表**是由同一类型的数据元素（或记录）构成的集合。由于集合中的数据元素之间存在着完全松散的关系，因此查找表是一种非常灵便的数据结构。

注意：从逻辑上来说，查找表中的数据元素之间没有本质的关系。查找表可以不是线性表，树结构和图结构中的任意一种。

查找的操作分为两种：静态查找和动态查找。

1.静态查找：

1.1. 查询某个特定的数据元素是否在查找表中；

1.2. 检索某个特定的数据元素的各种属性。

2. 动态查找：

2.1. 在查找表中插入一个数据元素；

2.2. 从查找表中删去某个数据元素。

查找表中的基本术语

**关键字**：数据元素中某个数据项的值，用以标识一个数据元素。  
**主关键字**：可以唯一的标识一个数据元素的关键字。

**次关键字**：可以识别不止一个数据元素的关键字。

查找的结果分为两种：成功和失败。

1.查找成功：找到满足条件的数据元素，作为结果，可返回数据元素在查找表中的位置，也可以返回该数据元素的具体信息；

2. 查找失败：无法找到满足条件的数据元素，作为结果，应该报告一些错误信息，如失败标志、失败位置。

下面我们简单的实现一下查找

静态查找

#include <stdio.h>
    #include <stdlib.h>
    #include <time.h>

#define SIZE 20
    /* run this program using the console pauser or add your own getch, system("pause") or input loop */
    // 打印数组
    void print_array(int a[], int len)
    {
    	int i = 0; 
    	for(i=0; i<len; i++)
    	{
    		 printf("%d, ", a[i]);
    	}
    	printf("\n");
    }
    // 静态查找算法
    int static_search(int a[], int len, int key)
    {
    	 int ret = -1;
    	 int i = 0; 
    	 // 依次查找 
    	 for(i=0; i<len; i++) 
    	 { 
    	 		if( a[i] == key ) 
    	 		{
    	 			 ret = i; 
    	 			 break; 
      		} 
    	 } 
    	 return ret;
    }
    // 测试代码
    int main(int argc, char *argv[]) 
    {    
    	// 创建大小为SIZE的数组 
    	int a[SIZE] = {0}; 
    	// 定义其他变量 
    	int i = 0; 
    	int key = 0; 	// 查找关键字 
    	int index = 0; 
    	srand((unsigned int)time(NULL)); // 以系统时间作为种子生成随机数
    	 // 初始化数组
    	  for(i=0; i<SIZE; i++)
    	  { 
    	  	a[i] = rand() % 100;
    	  }
    	  // 生成关键字 
    	  key = rand() % 100; 
    	  // 打印静态查找提示信息 
    	  printf("Static Search Demo\n"); 
    	  printf("Key: %d\n", key); 
    	  printf("Array: \n"); 
    	  print_array(a, SIZE); 
    	  // 调用静态查找 
    	  index = static_search(a, SIZE, key); 
    	  // 打印查找结果 
    	  if( index >= 0 ) 
    	  { 
    	  	printf("Success: a[%d] = %d\n", index, a[index]); 
    	  }
    	  else 
    	  { 
    	  	printf("Failed!\n"); 
    	  }
    	  return 0;
    }

显然，这是通过穷举法来查找，这里用来一个小技巧，通过系统时间作为种子生成随机数，这样可以保证每次查找表中的数据不一样。

成功结果如下：

![70][]

失败结果如下：

![70 1][]

动态查找

#include <stdio.h>
    #include <stdlib.h>
    #include <time.h>
    #include "SeqList.h"
    
    #define SIZE 20
    
    // 打印顺序表
    void print_list(SeqList* list)
    {
        int i = 0;
        
        for(i=0; i<SeqList_Length(list); i++)
        {
            printf("%d, ", (int)SeqList_Get(list, i));
        }
        
        printf("\n");
    }
    // 动态查找算法
    int dynamic_search(SeqList* list, int key)
    {
        int ret = -1;
        int i = 0;
        // 遍历链表
        for(i=0; i<SeqList_Length(list); i++)
        {
        	  // 查找成功，删除找到的元素
            if( (int)SeqList_Get(list, i) == key )
            {
                ret = i;
                
                SeqList_Delete(list, i);
                
                break;
            }
        }
        
        return ret;
    }
    
    // 测试代码
    int main(int argc, char *argv[]) 
    {
        // 创建大小为SIZE的顺序表
        SeqList* list = SeqList_Create(SIZE);
        // 定义其他变量
        int i = 0;
        int key = 0;       // 查找关键字
        int index = 0;
        
        srand((unsigned int)time(NULL));            // 以系统时间作为种子生成随机数
        // 初始化顺序表
        for(i=0; i<SIZE; i++)
        {
            SeqList_Insert(list, (SeqListNode*)(rand() % 100), i);
        }
        // 生成关键字
        key = rand() % 100;
      
        // 打印动态查找提示信息
        printf("Dynamic Search Demo\n");
        printf("Key: %d\n", key);
        printf("List: \n");
        // 打印查找前顺序表
        print_list(list);
        // 调用动态查找
        index = dynamic_search(list, key);
        // 打印查找结果
        if( index >= 0 )
        {
            printf("Success: list[%d] = %d\n", index, key);
        }
        else
        {
            printf("Failed!\n");
        }
        // 打印查找后顺序表
        print_list(list);
        
    	return 0;
    }

其中复用了顺序表的相关函数，顺序表相关内存参见：[数据结构之顺序表][Link 1]

运行结果基本同静态查找结果，只是提示信息有差别而已。

小结：

1. 查找是程序设计领域应用最广泛的技术之一；

2. 如何快而准的找到符合条件的数据元素是查找的技术关键；

3. 查找表中的数据元素之间没有本质关系，但要想获得较高的查找性能必须重新组织数据元素之间的关系。

[70]: /images/20220530/7c47aaf414724e9a8b9b202045e2dbaf.png
[70 1]: /images/20220530/2b7ba536ef964ca8a0ef7c25bca0aaa2.png
[Link 1]: http://blog.csdn.net/u014754841/article/details/79235694