做视频投稿赚钱的网站,建设银行手机银行官方网站,wordpress 简介,台州市建设项目规划网站目录
前言
已完成内容
二分查找实现
01-开发环境
02-文件布局
03-代码
01-主函数
02-头文件
03-PSeqListFunction.cpp
04-SearchFunction.cpp
结语 前言 此专栏包含408考研数据结构全部内容#xff0c;除其中使用到C引用外#xff0c;全为C语言代码。使用C引用主要…目录
前言
已完成内容
二分查找实现
01-开发环境
02-文件布局
03-代码
01-主函数
02-头文件
03-PSeqListFunction.cpp
04-SearchFunction.cpp
结语 前言 此专栏包含408考研数据结构全部内容除其中使用到C引用外全为C语言代码。使用C引用主要是为了简化指针的使用避免二重指针的出现。 二分查找仅适用于有序的顺序表对于如链表等不可采用二分查找。
已完成内容
[数据结构]01-顺序表C语言实现_Chandni.的博客-CSDN博客
[数据结构]02-单链表C语言实现_Chandni.的博客-CSDN博客
[数据结构]03-栈C语言实现_Chandni.的博客-CSDN博客
[数据结构]04-循环队列数组C语言实现_Chandni.的博客-CSDN博客
[数据结构]05-循环队列链表C语言实现_Chandni.的博客-CSDN博客
[数据结构]06-队列链表带头结点C语言实现_Chandni.的博客-CSDN博客
[数据结构]07-二叉树无头结点C语言实现_Chandni.的博客-CSDN博客
[数据结构]08-顺序查找顺序表指针实现形式C语言实现_Chandni.的博客-CSDN博客
二分查找实现
01-开发环境 语言C/C14 编译器MinGW64 集成开发环境CLion2022.1.3
02-文件布局 请在CLion集成开发环境中创建C可执行程序否则无法运行原因上面已解释。
03-代码
01-主函数 用于测试顺序查找初始化形式为随机数生成。 // 顺序表以指针形式实现(申请堆空间可动态控制顺序表大小)--数组实现形式不可以动态控制顺序表大小
#include ./Head/PSeqSearchData.h
#include ./Source/PSeqListFunction.cpp
#include ./Source/SearchFunction.cppint main() {// 初始化PSeqList PSList;int Length 10; // 实际所存元素个数PSeqListCreate(PSList, Length);PSeqListPrint(PSList);// 顺序查找ElemType Value;int pos;scanf(%d, Value);pos SequenceSearch(PSList, Value);if (pos ! -1) {printf(Search Success.\n%d at position %d\n, Value, pos);} else {printf(Search False.\n);}// 二分查找// 排序函数qsort(PSList.data, PSList.ListLength, sizeof(ElemType), compare);PSeqListPrint(PSList);scanf(%d, Value);pos HalfSearch(PSList, Value);if (pos ! -1) {printf(Search Success.\n%d at position %d\n, Value, pos);} else {printf(Search False.\n);}return 0;
}02-头文件 用于存储结构体和常量等。 //
// Created by 24955 on 2023-03-02.
// 顺序表以指针形式实现(申请堆空间可动态控制顺序表大小)-数组实现形式不可以动态控制顺序表大小
//#ifndef INC_01_SEQUENCESEARCH_PSEQSEARCHDATA_H
#define INC_01_SEQUENCESEARCH_PSEQSEARCHDATA_H
// 头文件
#include stdio.h
#include stdlib.h
#include time.h// 常量
typedef int ElemType;// 结构体
// 顺序表结构体(以指针形式实现)
typedef struct {ElemType *data;int ListLength;
}PSeqList;
#endif //INC_01_SEQUENCESEARCH_PSEQSEARCHDATA_H03-PSeqListFunction.cpp 用于存储顺序表指针形式创建、打印等函数。 //
// Created by 24955 on 2023-03-02.
// 顺序表以指针形式实现(申请堆空间可动态控制顺序表大小)--数组实现形式不可以动态控制顺序表大小
// 不使用哨兵
//
// 顺序表初始化
void PSeqListCreate(PSeqList PSList, int Length) {/** 1. 为顺序表申请堆空间* 2. 根据Length大小设置顺序表长度* 3. 随机数初始化顺序表*/PSList.ListLength Length;PSList.data (ElemType *) malloc((PSList.ListLength) * sizeof(ElemType));srand(time(NULL));for (int i 0; i PSList.ListLength; i) {PSList.data[i] rand() % 100;}
}// 顺序表打印输出
void PSeqListPrint(PSeqList PSList) {/** 1. 0号元素为哨兵因此从1号元素开始打印输出*/for (int i 0; i PSList.ListLength; i) {printf(%3d, PSList.data[i]);}printf(\n);
}// 比较-用于qsort函数
int compare(const void *left, const void *right) {/** 1. 函数名字中存储的为函数的入口地址* 2. qsort函数规定若left指针所指向的值大于right指针指向的值返回正值小于返回负值等于返回0* 3. left right 是任意两个元素的地址值*/return *(ElemType *) left - *(ElemType *) right; // 从小到大//return *(ElemType*)right - *(ElemType*)left; // 从大到小
} 04-SearchFunction.cpp 用于存储查找函数。 //
// Created by 24955 on 2023-03-02.
// 顺序表以指针形式实现(申请堆空间可动态控制顺序表大小)--数组实现形式不可以动态控制顺序表大小
// 不使用哨兵
//
// 顺序表查找
int SequenceSearch(PSeqList PSList, ElemType Value) {/** 1. 若查找到返回元素当前位置* 2. 若存在多个相同元素则返回第一个匹配元素的所在位置* 3. 未查找到返回-1*/for (int pos 0; pos PSList.ListLength; pos) {if (PSList.data[pos] Value) {return pos 1;}}// 未查到返回 -1return -1;
}// 折半查找(二分查找)
int HalfSearch(PSeqList PSList, ElemType Value) {/** 1. 初始化low,high标识位* 2. 比较元素值大小进行二分查找* 3. 查到返回元素位置未查到返回-1*/int low 0, high PSList.ListLength - 1, mid;while (low high) {mid (low high) / 2;if (PSList.data[mid] Value) {return mid 1;} else if (PSList.data[mid] Value) {high mid - 1;} else {low mid 1;}}// 未查到返回 -1return -1;
} 结语 此博客主要用于408考研数据结构C语言实现记录内有不足可留言可讨论。
