数据结构第一轮复习--第七章查找（包罗课程代码）
基于数组实现次序查找代码//顺序查找的实现
typedef struct{ //查找表的数据结构（顺序表）
ElemType *elem; //指向开辟的动态数组基址 （起始地址）
int TableLen; //表的长度
}SSTable;
//顺序查找
int Search_Seq(SSTable ST,ElemType key){
int i;
for(i=0;i<ST.TableLen && ST.elem!=key;++i);
//查找成功，则返回元素下标；查找失败，则返回-1
return i==SSTable? -1 : i;
} 基于链表实现次序查找代码
#include <stdio.h>
#include <stdlib.h>
// 定义链表节点的数据类型
typedef int ElemType;
// 定义链表节点结构
typedef struct Node {
ElemType data; // 数据域，存储节点的值
struct Node* next; // 指针域，指向下一个节点
} Node;
// 定义链表结构
typedef struct {
Node* head; // 指向链表的头节点
} LinkedList;
// 创建链表（假设链表是带头节点的单链表）
LinkedList* CreateLinkedList() {
// 分配内存空间给链表结构
LinkedList* list = (LinkedList*)malloc(sizeof(LinkedList));
if (list == NULL) {
printf("Memory allocation failed for LinkedList.\n");
return NULL; // 如果分配失败，返回NULL
}
// 分配内存空间给头节点
list->head = (Node*)malloc(sizeof(Node));
if (list->head == NULL) {
free(list); // 如果头节点分配失败，释放之前分配的链表结构内存
printf("Memory allocation failed for head node.\n");
return NULL;
}
// 初始化头节点，头节点不存储实际数据，其next指针初始化为NULL
list->head->next = NULL;
return list; // 返回创建好的链表
}
// 向链表中插入节点（在链表尾部插入）
void InsertNode(LinkedList* list, ElemType value) {
// 分配内存空间给新节点
Node* newNode = (Node*)malloc(sizeof(Node));
if (newNode == NULL) {
printf("Memory allocation failed for new node.\n");
return; // 如果分配失败，直接返回
}
// 设置新节点的数据域和指针域
newNode->data = value;
newNode->next = NULL;
// 从头节点开始，找到链表的尾部节点
Node* current = list->head;
while (current->next != NULL) { // 当前节点的next不为NULL，说明不是尾部节点
current = current->next; // 移动到下一个节点
}
// 将新节点链接到链表尾部
current->next = newNode;
}
// 顺序查找（基于链表）
int Search_Seq(LinkedList* list, ElemType key) {
// 从头节点的下一个节点开始（跳过头节点，从第一个实际节点开始）
Node* current = list->head->next;
int index = 0; // 用于记录当前节点的索引，从0开始
// 遍历链表
while (current != NULL) {
if (current->data == key) { // 如果当前节点的数据等于目标值
return index; // 返回当前节点的索引
}
current = current->next; // 移动到下一个节点
index++; // 索引加1
}
// 如果遍历完整个链表都没有找到目标值，返回-1
return -1;
}
// 释放链表内存
void FreeLinkedList(LinkedList* list) {
// 从头节点开始释放链表内存
Node* current = list->head;
while (current != NULL) {
Node* temp = current; // 保存当前节点
current = current->next; // 移动到下一个节点
free(temp); // 释放当前节点的内存
}
free(list); // 最后释放链表结构的内存
}
// 测试代码
int main() {
// 创建链表
LinkedList* list = CreateLinkedList();
if (list == NULL) {
return -1; // 如果链表创建失败，退出程序
}
// 向链表中插入一些数据
InsertNode(list, 10);
InsertNode(list, 20);
InsertNode(list, 30);
InsertNode(list, 40);
// 测试顺序查找
int key = 30; // 要查找的目标值
int result = Search_Seq(list, key); // 调用顺序查找函数
if (result != -1) {
printf("Element %d found at index %d.\n", key, result); // 找到目标值，输出索引
} else {
printf("Element %d not found.\n", key); // 没有找到目标值
}
// 释放链表内存
FreeLinkedList(list);
return 0; // 程序正常结束
} 次序查找的实现（哨兵）
//顺序查找（哨兵）
typedef struct{ //查找表的数据结构（顺序表）
ElemType *elem; //指向开辟的动态数组基址 （起始地址）
int TableLen; //表的长度
}SSTable;
//顺序查找
int Search_Seq(SSTable ST,ElemType key){
ST.elem=key; //哨兵
int i;
for(i=ST.TableLen; ST.elem!=key;--i); //从后往前找
//查找成功，则返回元素下标；查找失败，则返回0
return i；
} https://i-blog.csdnimg.cn/direct/0f074c7c23e74d4eac594b6689bdcab3.png
折半查找的实现（二分查找）
//折半查找的实现（二分查找）
typedef struct{ //查找表的数据结构（顺序表）
ElemType *elem; //指向开辟的动态数组基址 （起始地址）
int TableLen; //表的长度
}SSTable;
//折半查找
int Binary_Search(SSTable L,ElemType key){
int low=0,high=L.TableLen-1,mid;
while(low<=high){
mid=(low+high)/2; //取中间位置
if(L.elem==key)
return mid; //查找成功则返回所在位置
else if(L.elem>key)
high=mid-1; //从前半部分继续查找
else
low=mid+1; //从后半部分继续查找
}
return -1; //查找失败，返回-1
}
https://i-blog.csdnimg.cn/direct/b50d8982421742b68b8b0f4c19c576c8.png
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。
页:
[1]