| （详解）数据结构线性表的查找 | 您所在的位置：网站首页 › 折半查找中间值 › （详解）数据结构线性表的查找 |
（详解）数据结构线性表的查找
|
目录 引言： 一、顺序查找（Sequential Search） 1.概要 2.查找过程 3.算法实现 (1).以顺序表作为存储结构，实现顺序查找算法 数据元素类型定义： 顺序表的定义： 实现主函数： 哨兵函数： 完整代码示例： (2).以链表作为存储结构，实现顺序查找算法 链表节点的定义: 初始化链表： 实现顺序查找算法： 完整代码示例： 4.算法分析 5.顺序查找优缺点总结 二、折半查找（二分查找）（Binary Search） 1.概要 2.查找过程 3.算法实现 (1).递归实现折半查找 (2).迭代实现折半查找 (3).完整代码示例 4.例题演示 5.算法分析（含判定树概念） 6.折半查找优缺点总结 三、分块查找（索引顺序查找）（Blocking Search） 1.概要 2.查找过程 3.例题演示 4.算法分析 5.分块查找的优缺点总结 四、总结 引言：线性表是最基础的数据结构，它由一系列具有相同数据类型的元素组成，这些元素在内存中连续存放。在线性表中查找特定的元素，通常有以下几种方法： 1、顺序查找（Sequential Search） 2、折半查找（二分查找）（Binary Search） 3、分块查找（索引顺序查找）（Blocking Search） 一、顺序查找（Sequential Search） 1.概要顺序查找又称线性查找，适用于顺序表和链表。对于顺序表，可通过数组下标递增顺序扫描每个元素；对于链表，可通过指针next来依次扫描每个元素。 2.查找过程从线性表的一端开始，依次将记录的关键字与给定值进行比较，也就是逐个检查关键字是否满足给定的条件。 若查找到某个记录的关键字和给定值相等，则查找成功；反之，查找失败。 3.算法实现 (1).以顺序表作为存储结构，实现顺序查找算法 数据元素类型定义： typedef struct { KeyType key; //关键字域 InfoType otherinfo; //其他域 }ElemType; 顺序表的定义： typedef struct { ElemType* R; //存储空间基地址 int length; //当前长度 }; 实现主函数： int Search_Seq(SSTable ST, KeyType key) { //在顺序表ST中顺序查找其关键字等于key的数据元素。若找到，则函数值为该元素在表中的位置否则为0 int i = 0; for (i = ST.length; i >= 1; --i) { if (ST.R[i].key == key) { return i; } } return 0; }在查找过程中，每执行一次for循环内的代码都要检查i是否＞＝1，也就是判断整个表是否检查完毕，从而增加了程序执行的时间及任务量。 对此将ST.elem[0]设为哨兵，引用它的目的是使得Search_Seq内的循环不必判断数组是否会越界。 因此将原来算法每执行一次for循环内的代码，需要判断两次（i＞＝1）（ST.R[i]key==key），变为了每执行一次for循环内的代码仅需判断一次（ST.R[i]key！=key） 即将上面的实现主函数代码替换为下面的哨兵函数代码。 哨兵函数： int Search_Seq(SSTable ST, KeyType key) { //在顺序表ST中顺序查找其关键字等于key的数据元素。若找到，则函数值为该元素在表中的位置否则为0 int i = 0; ST.R[0].key = key;//“监视哨” for (i = ST.length; ST.R[i].key != key; --i);//从后往前查找 return i; }在程序中引入“哨兵”并不是这个算法独有的，引入“哨兵”可以避免很多不必要的判断语句，从而提高程序效率。 完整代码示例： #include #include typedef char InfoType; typedef int KeyType; // 定义结构体ElemType，包含关键字域和其他域 typedef struct { KeyType key; // 关键字域 InfoType otherinfo; // 其他域 } ElemType; // 定义结构体SSTable，表示顺序表 typedef struct { ElemType* R; // 存储空间基地址 int length; // 当前长度 } SSTable; // 函数Search_Seq在顺序表ST中顺序查找关键字等于key的数据元素 int Search_Seq(SSTable ST, KeyType key) { int i = 0; ST.R[0].key = key; for (i = ST.length; ST.R[i].key != key; --i); // 从后往前查找 return i; } int main() { // 假设KeyType是int，InfoType是char typedef int KeyType; typedef char InfoType; // 创建一个顺序表 SSTable ST; ST.R = (ElemType*)malloc(10 * sizeof(ElemType)); // 假设分配10个元素的空间 ST.length = 0; // 向顺序表中添加元素 ST.R[1].key = 1; ST.R[1].otherinfo = 'A'; ST.R[2].key = 2; ST.R[2].otherinfo = 'B'; ST.length = 3; // 调用Search_Seq函数查找关键字为2的元素 int position = Search_Seq(ST,2); if (position != 0) { printf("Element found at position %d\n", position); printf("%d", ST.R[position].otherinfo); putchar(ST.R[position].otherinfo);//将ASCII码转换为字符 } else { printf("Element not found\n"); } // 释放顺序表空间 free(ST.R); return 0; } (2).以链表作为存储结构，实现顺序查找算法 链表节点的定义:该个链表节点包含两部分：数据域和指针域。 数据域用于存储节点的数据，指针域用于存储指向下一个节点的指针。 typedef struct ListNode { int data; // 数据域 struct ListNode* next; // 指针域，指向下一个节点 } ListNode; 初始化链表：初始化链表时，我们需要创建一个头节点，并设置指针域为NULL，表示链表为空。 ListNode* InitializeList() { ListNode* head = (ListNode*)malloc(sizeof(ListNode)); if (head != NULL) { head->data = 0; // 头节点数据域初始化为0或其他特殊值 head->next = NULL; // 头节点指针域初始化为NULL } return head; } 实现顺序查找算法：我们对本文顺序查找算法通过对链表进行遍历来实现。 给定一个目标值，我们从链表的头节点开始遍历，逐个检查每个节点的数据域，直到找到目标值或遍历完所有节点。 ListNode* SequentialSearch(ListNode* head, int value) { ListNode* current = head; // 从头节点开始 while (current != NULL) { if (current->data == value) { // 检查当前节点的数据域是否等于目标值 return current; // 如果是，返回当前节点 } current = current->next; // 否则，移动到下一个节点 } return NULL; // 如果没有找到，返回NULL } 完整代码示例： #include #include typedef struct ListNode { int data; struct ListNode* next; } ListNode; ListNode* InitializeList() { ListNode* head = (ListNode*)malloc(sizeof(ListNode)); if (head != NULL) { head->data = 0; head->next = NULL; } return head; } ListNode* SequentialSearch(ListNode* head, int value) { ListNode* current = head; while (current != NULL) { if (current->data == value) { return current; } current = current->next; } return NULL; } int main() { ListNode* head = InitializeList(); ListNode* node1 = (ListNode*)malloc(sizeof(ListNode)); ListNode* node2 = (ListNode*)malloc(sizeof(ListNode)); head->next = node1; node1->data = 1; node1->next = node2; node2->data = 2; node2->next = NULL; ListNode* result = SequentialSearch(head, 2); if (result != NULL) { printf("Found node with value %d\n", result->data); } else { printf("Node with value %d not found\n", 2); } // 释放链表内存等操作... return 0; } 4.算法分析 对于有n个元素的表，给定值key与表中第i个元素相等，即定位第i个元素时，需进行n-i+1次关键字的比较，即 查找成功时，顺序查找的平均长度为：
当每个元素的查找概率相等，即
查找不成功时，与表中各个关键字的比较次数是n+1次，即
因此监视哨函数时间复杂度为O(n)。 空间复杂度为O(1)，因为监视哨利用了一个额外的辅助存储空间。 5.顺序查找优缺点总结优点：算法简单，对表结构无任何要求，顺序存储或链式存储皆可。同时对表中记录的有序性也没有要求，无论记录是否按关键字有序，均可应用。需注意的是，对线性的链表只能进行顺序查找。 缺点：平均查找长度较大，查找效率较低，当n较大时，不适合采用顺序查找。 二、折半查找（二分查找）（Binary Search） 1.概要折半查找（Binary Search）也称二分查找，它要求线性表必须采用顺序存储结构，即有序的顺序表。 2.查找过程从表中间记录开始，如果给定值key和中间记录的关键字相等，则查找成功；如果给定值key比中间记录的关键字大或小，则在表中大或小的中间记录的那一半中继续查找，重复这样的操作，直至查找成功，或确定表中没有所需要查找的元素，则查找失败，返回失败信息。 3.算法实现 (1).递归实现折半查找 // 递归实现折半查找 int binarySearchRecursive(int arr[], int left, int right, int target) { if (left > right) { return -1; // 搜索失败，返回-1 } int mid = (left + right) / 2; // 计算中间位置 if (arr[mid] == target) { return mid; // 搜索成功，返回目标元素的位置 } else if (arr[mid] < target) { return binarySearchRecursive(arr, mid + 1, right, target); // 在右半部分继续查找 } else { return binarySearchRecursive(arr, left, mid - 1, target); // 在左半部分继续查找 } } (2).迭代实现折半查找 // 迭代实现折半查找 int binarySearchIterative(int arr[], int target) { int left = 0, right = sizeof(arr) - 1; while (left right) { return -1; // 搜索失败，返回-1 } int mid = (left + right) / 2; // 计算中间位置 if (arr[mid] == target) { return mid; // 搜索成功，返回目标元素的位置 } else if (arr[mid] < target) { return binarySearchRecursive(arr, mid + 1, right, target); // 在右半部分继续查找 } else { return binarySearchRecursive(arr, left, mid - 1, target); // 在左半部分继续查找 } } // 迭代实现折半查找 int binarySearchIterative(int arr[], int target) { int left = 0, right = sizeof(arr) - 1; while (left |
.
时，有
【本文地址】
| 今日新闻 |
| 推荐新闻 |
| 专题文章 |