【数据结构】查找与排序(一)—>“监视哨”的学习

这篇具有很好参考价值的文章主要介绍了【数据结构】查找与排序(一)—>“监视哨”的学习。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

一、前言

本篇以学生信息管理系统为背景,主要学习简单的查找与排序功能。

高级查找与排序会在接下来的文章中再做介绍,欢迎大家关注并留意博主动态。

查找主要涉及顺序查找、二分查找。

排序主要涉及直接插入排序、直接选择排序、冒泡排序。

 二、查找讲解

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、冒泡排序

冒泡排序的思想是交换,即待排序数据依次两两比较,将较大者保持在每轮的最后一个。

这样每一轮的最大值就交换到了尾部,再进行新一轮的比较,将次大值交换到最大值的钱一个位置,依次循环进行。

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);
#endif

2、功能函数文件

#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模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 二叉排序树的创建、插入、查找和删除【数据结构】

    若它的左子树不空,则左子树上所有结点的值均小于它根结点的值。 若它的右子树不空,则右子树上所有结点的值均大于它根结点的值。 它的左、右树又分为⼆叉排序树 二叉排序树也叫二叉查找树、二叉搜索树 题目描述 给出一个数据序列,建立二叉排序树,并实现插入功

    2024年01月24日
    浏览(43)
  • 数据结构07:查找[C++][平衡二叉排序树AVL]

    图源:文心一言 考研笔记整理1w+字,小白友好、代码可跑,请小伙伴放心食用~~🥝🥝 第1版:查资料、写BUG、画导图、画配图~🧩🧩 参考用书: 王道考研《2024年 数据结构考研复习指导》 参考用书配套视频: 7.3_2 平衡二叉树_哔哩哔哩_bilibili 特别感谢:  Chat GPT老师、文心

    2024年02月11日
    浏览(48)
  • 数据结构07:查找[C++][朴素二叉排序树BST]

    图源:文心一言 考研笔记整理 8k+ 字,小白友好、代码可跑,请小伙伴放心食用~~🥝🥝 第1版:查资料、写BUG、画导图、画配图~🧩🧩 参考用书: 王道考研《2024年 数据结构考研复习指导》 参考用书配套视频: 7.3_1 二叉排序树_哔哩哔哩_bilibili 特别感谢:  Chat GPT老师、文心

    2024年02月10日
    浏览(40)
  • 合肥工业大学 宣城校区 数据结构与算法实验 队列、二叉树、查找和排序

    1.实验目标 熟练掌握队列的顺序存储结构和链式存储结构。 熟练掌握队列的有关算法设计,并在循环顺序队列和链队列上实现。 根据具体给定的需求,合理设计并实现相关结构和算法。 2.实验内容和要求 循环顺序队列的实验要求 循环顺序队列结构和运算定义,算法的实现以

    2024年02月11日
    浏览(49)
  • 二叉排序树的插入删除和查找(数据结构实训)(难度系数100)

    二叉排序树的插入删除和查找 pre: 前序遍历 in: 中序遍历 post:后序遍历 insert: 插入,本题中不会出现相同的元素 delete: 删除,删除成功输出TRUE,没有该元素则输出FALSE,删除的方法是如果有左子树,以左子树中最大值作为新的树根,否则,以右子树最小值作为树根。 search:

    2024年01月25日
    浏览(50)
  • C语言数据结构二叉排序树的建立、插入、删除、查找操作(原理+完整代码)

    1、若左子树不为空,左子树上所有节点值小于 它根节点的值 2、若右子树不为空,右子树上所有节点值大于 它根节点的值 3、每个节点的左右子树也是二叉排序树 目的:提高查找、插入、删除的速度(不是为了排序) 时间复杂度:由于查找性能取决于树的形态,所以

    2024年02月09日
    浏览(49)
  • 数据结构之索引查找(分块查找)

    活动地址:CSDN21天学习挑战赛   作者简介:大家好我是小唐同学(๑؂๑),为梦想而奋斗的小唐,让我们一起加油!!! 个人主页: 小唐同学(๑؂๑)的博客主页 系列专栏:数据结构 博友们如果也是新手入门数据结构我希望大家可以多加练习 数据结构题库在牛客网就有已

    2024年02月02日
    浏览(53)
  • 数据结构算法--1 顺序查找二分查找

    顺序查找时间复杂度为O(n) 我们可以借助Python中的函数enumerate,通过enumerate遍历列表返回其索引和值 也可以通过列表长度依次遍历: 但是二分查找时间复杂度为O(logn):

    2024年02月12日
    浏览(54)
  • 数据结构10 -查找_树表查找

    二叉搜索树是有数值的了, 二叉搜索树是一个有序树 。 若它的左子树不空,则左子树上所有结点的值均 小于 它的根结点的值; 若它的右子树不空,则右子树上所有结点的值均 大于 它的根结点的值; 它的左、右子树也分别为二叉排序树 下面这两棵树都是搜索树 bstree.c(二

    2024年02月14日
    浏览(39)
  • 数据结构--》掌握数据结构中的查找算法

            当你需要从大量数据中查找某个元素时,查找算法就变得非常重要。         无论你是初学者还是进阶者,本文将为你提供简单易懂、实用可行的知识点,帮助你更好地掌握查找在数据结构和算法中的重要性,进而提升算法解题的能力。接下来让我们开启数据

    2024年02月08日
    浏览(57)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包