一、前言
本篇以学生信息管理系统为背景，主要学习简单的查找与排序功能。
高级查找与排序会在接下来的文章中再做介绍，欢迎大家关注并留意博主动态。
查找主要涉及顺序查找、二分查找。
排序主要涉及直接插入排序、直接选择排序、冒泡排序。
二、查找讲解
1、顺序查找
（1）普通的顺序查找
顺序查找就是依托顺序表的存储特点：顺序存储，利用其相邻的存储位置进行查找操作。
void SqSearch(SqList L)
{
int i = 0;
int flag = 0;
cout << "请输入你要查找的学生姓名>:";
char arr[10] = "\0";
scanf("%s", arr);
for (i = 0; i < L.length; i++)
{
if (strcmp(L.elem[i].name, arr) == 0)
{
flag = 1;
cout << "该学生信息如下>:" << endl;
OutList(L, i);
break;
}
}
if (flag == 0)
cout << "未找到该学生！" << endl;
}根据函数我们可以清晰地了解到，这种普通的顺序查找方式每次循环都需要进入判断i<L.length。即这一算法需要进行两次判断，一是查找位置是否合法：i<L.length，二是该位置的元素是否是我们要查找的元素：strcmp(L.elem[i].name, arr) == 0，那么我们是否可以每次进行一次判断就得到我们想要的结果呢，答案是肯定的，请看下文“监视哨”顺序查找的介绍。
（2）“监视哨”顺序查找
“监视哨”就是在顺序表中留出一个位置，不管是头部还是尾部，每次只需要将待比较的元素与“监视哨”位置的元素比较即可，这样每次都能节省一次判断，算法如下：
int SqSearch(SqList L)
{
int i = 0;
cout << "请输入你要查找的学生姓名>:";
char arr[10] = "\0";
scanf("%s", arr);
strcpy(L.elem[0].name,arr);
for (i = L.length; strcmp(L.elem[i].name, arr) != 0; i--)
{
;//空语句
}
return i;
}当返回值为0时，证明查找失败。
利用监视哨的方式进行查找，只需要留出一个顺序表中的位置，所带来的效率提升还是比较明显的，尤其是在数据庞大的时候。
2、二分查找
二分查找适用的是有序表，即原始数据必须有序，他的思想就是从表的中间记录开始，用给定值与中间值比较，如果相等，则查找成功，如果给定值大于或小于中间值，则在表中大于或小于的那一半中继续查找。
//二分查找
void binaryFld(SqList L)
{
cout << "请输入你要查找的学生学号>:";
int id = 0;
cin >> id;
int low = 0;
int high = L.length - 1;
int flag = 0;
while (low <= high)
{
int mid = (low + high) / 2;//mid的赋值位置尤为重要
if (L.elem[mid].stu_id < id)
{
low = mid + 1;
}
else if (L.elem[mid].stu_id > id)
{
high = mid - 1;
}
else
{
flag = 1;
cout << "你要查找的学生信息如下>:" << endl;
OutList(L, mid);
break;
}
}
if (flag == 0)
cout << "未找到该学生！" << endl;
}需要尤其注意的是，mid赋值的位置尤为重要，如果你不小心将mid的复制位置放在了循环外，就会引起程序错误，进入死循环。
三、排序讲解
1、直接插入排序
直接插入排序的思想是将数据分为两部分，一部分为已排序部分，另一部分为待排序部分，每次从待排序部分的第一个元素插入到已排序部分中。
//直接插入排序
void Insert_sorting(SqList &L)
{
int i = 0;
for (i = 1; i < L.length; i++)//默认单个元素为有序，所以从第二个元素开始
{
Stu t={0};
if (strcmp(L.elem[i].name,L.elem[i - 1].name)<0)比较元素大小
{
t= L.elem[i];
L.elem[i]= L.elem[i - 1];
//寻找插入位置
int j = 0;
for (j = i - 1; strcmp(L.elem[j].name,t.name)>0 ; j--)
{
L.elem[j + 1]= L.elem[j];//元素后移
}
L.elem[j + 1]= t;插入元素
}
}
}思想滤清后，我们得到以下步骤 ：
分析直接插入排序思想，我们需要解决的问题为三个，一是将待排序元素与已排序元素比较大小，二是寻找合适的插入位置，三是元素后移并插入。
2、直接选择排序
直接选择排序的思想就是每次从待排序数据中找到最小值，并从头开始替换。
//直接选择排序
void Choose_sorting(SqList& L)
{
int i = 0;
int k = 0;
int j = 0;
Stu tmp = {0};
for (i = 0; i < L.length; i++)
{
k = i;
for (j = i + 1; j < L.length; j++)//寻找最小值
{
if (L.elem[k].stru_score > L.elem[j].stru_score)
{
k = j;
}
}
if (k != i)//替换数据
{
tmp = L.elem[i];
L.elem[i] = L.elem[k];
L.elem[k] = tmp;
}
}
}分析直接选择排序思想，我们需要解决的问题为两个，一是将寻找最小值，二是逐个替换。
3、冒泡排序
冒泡排序的思想是交换，即待排序数据依次两两比较，将较大者保持在每轮的最后一个。
这样每一轮的最大值就交换到了尾部，再进行新一轮的比较，将次大值交换到最大值的钱一个位置，依次循环进行。文章来源：https://www.toymoban.com/news/detail-510062.html
void Bubbling_sorting(SqList& L)
{
int i = 0;
int m = L.length - 1;
int flag = 1;
Stu tmp = { 0 };
while (m > 0 && flag == 1)
{
flag = 0;
for (i = 0; i < m; i++)
{
if (L.elem[i].cpp_score > L.elem[i + 1].cpp_score)
{
flag = 1;
tmp = L.elem[i + 1];
L.elem[i + 1] = L.elem[i];
L.elem[i] = tmp;
}
}
--m;
}
}四、完整程序
1、头文件
#ifndef _Search_h
#define _Search_h
#include<stdio.h>
#include<iostream>
#include<string.h>
#include<stdlib.h>
using namespace std;
typedef int Status;
#define MAXSIZE 100
#define OK 1
#define ERROR 0
#define NUM 8//表长
#define OVERFLOW -1
typedef struct
{
int stu_id;
char name[10];
char class_id[10];
int cpp_score;
int stru_score;
}Stu;
typedef struct
{
Stu* elem;
int length;
}SqList;
//菜单
void menu();
//信息初始化
Status InitList(SqList &L);
//输出数据
void OutList(SqList L, int i);
//输出全部数据
void OutAllList(SqList L);
//顺序查找
void SqSearch(SqList L);
//二分查找
void binaryFld(SqList L);
//直接插入排序
void Insert_sorting(SqList &L);
//冒泡排序
void Bubbling_sorting(SqList &L);
//直接选择排序
void Choose_sorting(SqList& L);
#endif2、功能函数文件
#include"Search.h"
//菜单
void menu()
{
printf("*******************学生成绩管理系统*******************\n");
printf("* 1.信息初始化 2.顺序查找 *\n");
printf("* 3.二分查找 4.直接插入排序 *\n");
printf("* 5.冒泡排序 6.直接选择排序 *\n");
printf("* 0.退出 *\n");
printf("******************************************************\n");
}
//初始化
Status InitList(SqList& L)
{
L.elem = new Stu[MAXSIZE];
if (!L.elem)
exit(OVERFLOW);
L.length = NUM;
int i = 0;
for (i = 0; i < L.length; i++)
{
cout << "请依次输入学号，姓名，班级，C++成绩，数据结构成绩>:";
scanf("%d", &L.elem[i].stu_id);
scanf("%s", L.elem[i].name);
scanf("%s", L.elem[i].class_id);
scanf("%d", &L.elem[i].cpp_score);
scanf("%d", &L.elem[i].stru_score);
}
// L.elem[0] = { 1,"王立","03511",85,76 };
// L.elem[1] = { 2,"张秋","03511",78,88 };
// L.elem[2] = { 3,"刘丽","03511",90,79 };
// L.elem[3] = { 4,"王通","03511",75,86 };
// L.elem[4] = { 5,"赵阳","03511",60,71 };
// L.elem[5] = { 6,"李艳","03511",58,68 };
// L.elem[6] = { 7,"钱娜","03511",95,89 };
// L.elem[7] = { 8,"孙胜","03511",45,60 };
return OK;
}
//输出某一数据
void OutList(SqList L, int i)
{
cout << L.elem[i].stu_id << "\t" << L.elem[i].name << "\t" << L.elem[i].class_id << "\t"
<< L.elem[i].cpp_score << "\t" << L.elem[i].stru_score << endl;
}
//输出全部数据
void OutAllList(SqList L)
{
int i = 0;
for (i = 0; i < L.length; i++)
{
cout << L.elem[i].stu_id << "\t" << L.elem[i].name << "\t" << L.elem[i].class_id << "\t"
<< L.elem[i].cpp_score << "\t" << L.elem[i].stru_score << endl;
}
}
//顺序查找
void SqSearch(SqList L)
{
int i = 0;
int flag = 0;
cout << "请输入你要查找的学生姓名>:";
char arr[10] = "\0";
scanf("%s", arr);
for (i = 0; i < L.length; i++)
{
if (strcmp(L.elem[i].name, arr) == 0)
{
flag = 1;
cout << "该学生信息如下>:" << endl;
OutList(L, i);
break;
}
}
if (flag == 0)
cout << "未找到该学生！" << endl;
}
//二分查找
void binaryFld(SqList L)
{
cout << "请输入你要查找的学生学号>:";
int id = 0;
cin >> id;
int low = 0;
int high = L.length - 1;
int flag = 0;
while (low <= high)
{
int mid = (low + high) / 2;
if (L.elem[mid].stu_id < id)
{
low = mid + 1;
}
else if (L.elem[mid].stu_id > id)
{
high = mid - 1;
}
else
{
flag = 1;
cout << "你要查找的学生信息如下>:" << endl;
OutList(L, mid);
break;
}
}
if (flag == 0)
cout << "未找到该学生！" << endl;
}
//直接插入排序
void Insert_sorting(SqList &L)
{
int i = 0;
for (i = 1; i < L.length; i++)
{
Stu t={0};
if (strcmp(L.elem[i].name,L.elem[i - 1].name)<0)
{
t= L.elem[i];
L.elem[i]= L.elem[i - 1];
//寻找插入位置
int j = 0;
for (j = i - 1; strcmp(L.elem[j].name,t.name)>0 ; j--)
{
L.elem[j + 1]= L.elem[j];
}
L.elem[j + 1]= t;
}
}
}
//冒泡排序
void Bubbling_sorting(SqList& L)
{
int i = 0;
int m = L.length - 1;
int flag = 1;
Stu tmp = { 0 };
while (m > 0 && flag == 1)
{
flag = 0;
for (i = 0; i < m; i++)
{
if (L.elem[i].cpp_score > L.elem[i + 1].cpp_score)
{
flag = 1;
tmp = L.elem[i + 1];
L.elem[i + 1] = L.elem[i];
L.elem[i] = tmp;
}
}
--m;
}
}
//直接选择排序
void Choose_sorting(SqList& L)
{
int i = 0;
int k = 0;
int j = 0;
Stu tmp = {0};
for (i = 0; i < L.length; i++)
{
k = i;
for (j = i + 1; j < L.length; j++)
{
if (L.elem[k].stru_score > L.elem[j].stru_score)
{
k = j;
}
}
if (k != i)
{
tmp = L.elem[i];
L.elem[i] = L.elem[k];
L.elem[k] = tmp;
}
}
}3、主函数文件
#include"Search.h"
int main()
{
SqList L;
int input = 0;
do
{
menu();
printf("请选择>:");
cin >> input;
switch (input)
{
case 1:
//信息初始化
InitList(L);
break;
case 2:
//顺序查找
SqSearch(L);
break;
case 3:
//二分查找
binaryFld(L);
break;
case 4:
//直接插入排序
cout << "排序前表为>:" << endl;
OutAllList(L);
Insert_sorting(L);
cout << "排序后表为>:" << endl;
OutAllList(L);
break;
case 5:
//冒泡排序
cout << "排序前表为>:" << endl;
OutAllList(L);
Bubbling_sorting(L);
cout << "排序后表为>:" << endl;
OutAllList(L);
break;
case 6:
//直接选择排序
cout << "排序前表为>:" << endl;
OutAllList(L);
Choose_sorting(L);
cout << "排序后表为>:" << endl;
OutAllList(L);
break;
case 0:
cout << "退出系统" << endl;
break;
}
} while (input);
return 0;
}四、总结
简单的查找与排序相信大家都很容易理解，博主会持续更新查找排序算法，欢迎大家关注博主动态🔥🔥🔥文章来源地址https://www.toymoban.com/news/detail-510062.html
到了这里，关于【数据结构】查找与排序(一)—＞“监视哨”的学习的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
![数据结构07：查找[C++][朴素二叉排序树BST]](https://imgs.yssmx.com/Uploads/2024/02/498683-1.png)
![数据结构07：查找[C++][平衡二叉排序树AVL]](https://imgs.yssmx.com/Uploads/2024/02/502021-1.png)
