有序顺序表的查找

一、
1.初始化一个顺序表
2.对顺序表进行顺序查找
3.建立一个有序顺序表
4.对有序顺序表进行折半查找

二、
1.首先建立一个结构体以便顺序表的使用，利用顺序查找算法的思想，我们把要查找的数存在List->data[0]，从顺序表的后面依次向前便利直到我们找到与List->data[0]里面的元素一样的时候做好标记，返回1表示查找成功；若直到第0个元素仍未查找到，则返回0表示未查找到该元素。
2.我们首先建立一个顺序表，我们可以利用随机函数rand()随机生成自己想要所在区间的数字，然后利用一个排序算法将它们做成一个有序顺序表（这样也就快速生成了一个有序顺序表），或是自己一个一个输入有序顺序表。再利用折半查找算法，对指定元素进行查找：首先将要查找的元素存进orderlist->data[0]里面，若该元素==orderlist->data[mid]则为找到，做好下标的标记返回一；
若该元素大于orderlist->data[mid]，则在右半部分进行查找；若该元素小于orderlist->data[mid]，则在左半部分进行查找。反复进行直到当low大于high仍是未找到指定元素则返回0。

三、具体代码如下：
头文件如下：

#include<stdio.h>
#include<stdlib.h>
#include<time.h>#define MAX 31typedef struct list{int data[MAX];
}ArrayList;ArrayList* Init_list(void);
void SelectionSort_list(ArrayList* l);
void SequentialSearch_list(ArrayList* l);
void putNumber_list(ArrayList* l, int a);
int JudgeOrder_list(ArrayList* l);
void BinarySearch_list(ArrayList* l);

主函数及自定义函数如下：

#include"header.h"
int main()
{ArrayList* arraylist = NULL;arraylist = Init_list();ArrayList* orderlist = NULL;orderlist = Init_list();srand(time(0));for (int i = 1; i <= MAX-1; i++)arraylist->data[i] = rand()%100+1;for (int i = 1; i <= MAX-1; i++)printf("%5d", arraylist->data[i]);printf("\n请输入你要在顺序表中查找的元素: ");int number;scanf("%d", &number);putNumber_list(arraylist, number);SequentialSearch_list(arraylist);printf("=====================================================\n");printf("你是否想快速生成一个有序顺序表(Y or !Y): ");char y;setbuf(stdin, NULL);scanf("%c", &y);if (y == 'y' || y == 'Y'){printf("\n有序顺序表如下: ");for (int i = 1; i <= MAX - 1; i++)orderlist->data[i] = rand() % 100 + 1;SelectionSort_list(orderlist);for (int i = 1; i <= MAX - 1; i++)printf("%5d", orderlist->data[i]);putchar('\n');}else{printf("请输入你的有序顺序表(30个正序):\n");setbuf(stdin, NULL);for (int i = 1; i < MAX; i++)scanf("%d", &orderlist->data[i]);printf("您输入的有序顺序表为: ");for (int i = 1; i < MAX; i++)printf("%5d", orderlist->data[i]);putchar('\n');if (!JudgeOrder_list(orderlist)){printf("该有序顺序表并非有序！小编以为你转换为有序顺序表:\n");SelectionSort_list(orderlist);for (int i = 1; i < MAX; i++)printf("%5d", orderlist->data[i]);putchar('\n');}}setbuf(stdin, NULL);printf("请输入你要采用折半查找的元素: ");scanf("%d", &number);putNumber_list(orderlist, number);BinarySearch_list(orderlist);return 0;
}
ArrayList* Init_list(void)		//初始化一个顺序表
{ArrayList* list = (ArrayList*)malloc(sizeof(ArrayList));return list;
}
void SelectionSort_list(ArrayList* l)		//选择排序
{for (int i = 1; i < MAX - 1; i++){int min=i;for (int j = i+1; j < MAX; j++){if (l->data[j] < l->data[min])min = j;}int temp = l->data[i];l->data[i] = l->data[min];l->data[min] = temp;}
}
void SequentialSearch_list(ArrayList* l)		//顺序查找
{int i;int k = 0;printf("该顺序表");for ( i = MAX - 1; i > 0; i--){if (l->data[i] == l->data[0]){printf("第%d个\t", i);k++;}}if (k != 0)printf("为查找到的元素！\n该顺序表一共含有%d个该元素\n", k);elseprintf("未找到该元素！！！\n");
}
void putNumber_list(ArrayList* l, int a)		//存入要查找的元素
{l->data[0] = a;
}
int JudgeOrder_list(ArrayList* l)		//判断是否有序
{int min = 1;for (int i = 2; i < MAX; i++){if (l->data[i] < l->data[min])return 0;}return 1;
}
void BinarySearch_list(ArrayList* l)		//折半查找
{if (!JudgeOrder_list(l)){printf("您所要执行折半查找的元素并非有序！！！\n");return;}int low,high;low = 1;high = MAX - 1;printf("该顺序表");while (high >= low){int mid = (high + low) / 2;if (l->data[mid] == l->data[0]){printf("第%d个元素为查找内容\n", mid);return;}else if (l->data[0] < l->data[mid])high--;elselow++;}printf("未找到该元素！！！\n");
}