// 顺序表以指针形式实现(申请堆空间，可动态控制顺序表大小)--数组实现形式不可以动态控制顺序表大小
#include "./Head/PSeqSearchData.h"
#include "./Source/PSeqListFunction.cpp"
#include "./Source/SearchFunction.cpp"int 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;
}

//
// 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_H

//
// 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; // 从大到小
}

//
// 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;
}