算法相关代码"/>
查找算法相关代码
SearchFunc.h
//
// SearchFunc.hpp
// FirstP
//
// Created by 赫赫 on 2023/11/1.
//#ifndef SearchFunc_hpp
#define SearchFunc_hpp#include <stdio.h>
#include <stdlib.h>
#include <iostream>
#include <string>
using namespace std;#endif /* SearchFunc_hpp *///顺序查找表结构
//时间复杂度O(n)
typedef struct{int *elem; //动态数组基址int TableLen; //表长度
}SSTable;//顺序查找(哨兵方式,数据从下标1开始存,下标0的位置存放查找关键字,即“哨兵”)
int Search_Seq(SSTable st,int key);//折半查找,又称二分查找,仅适用于有序顺序表
//时间复杂度O(log(n))
int Binary_Search(SSTable st,int key);
SearchFunc.cpp
//
// SearchFunc.cpp
// FirstP
//
// Created by 赫赫 on 2023/11/1.
// 查找算法代码#include "SearchFunc.hpp"//顺序查找(哨兵方式,数据从下标1开始存,下标0的位置存放查找关键字,即“哨兵”)
//时间复杂度O(n)
int Search_Seq(SSTable st,int key){st.elem[0]=key;int i;//从表尾开始向前查找for(i=st.TableLen;st.elem[i]!=key;i++);//如果i=0,那么就意味着没有查找到,否则返回数据存放下标return i;
}//折半查找,又称二分查找,仅适用于有序顺序表(默认升序)
//时间复杂度O(log(n))
int Binary_Search(SSTable st,int key){int low=0,high=st.TableLen-1,mid;while(low<=high){mid=(low+high)/2;if(st.elem[mid]==key){return mid;}else if(st.elem[mid]>key){high=mid-1;}else{low=mid+1;}}return -1;//表示没有找到元素
}
更多推荐
查找算法相关代码
发布评论