查找:线性表的C语言代码实现(顺序查找、折半查找)

这篇具有很好参考价值的文章主要介绍了查找:线性表的C语言代码实现(顺序查找、折半查找)。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

目录

一、线性表结构 两个类的定义

二、线性表的初始化以及根据输入的元素建立线性表

1.线性表的初始化,初始化一个空的线性表

2.根据用户需求,向线性表中添加元素 

三、顺序查找  Search1函数(没有设置哨兵,需要比较两次)

四、顺序查找(设置哨兵,不用再比较是否会越界,只用比较一次)Search2函数

五、折半查找(非递归)Search3函数

六、折半查找(递归)Search4函数

七、显示输出函数  Show函数

八、为了能在程序中一次实现以上函数,我们建立了一个Menu函数,根据用户选择,进行不同操作

九、完整代码

运行截图:

功能1创建: 

功能2:顺序查找无哨兵

功能3:顺序查找有哨兵

 功能4:折半查找非递归

  功能4:折半查找非递归

总结



一、线性表结构 两个类的定义

typedef struct//定义线性表数据项结构
{
	int key;//关键字域
	int otherinfo;
}ElemType;
typedef struct//定义一个线性表结构
{
	int length;//顺序表的长度
	ElemType* R;//顺序表的动态建立,R用于之后动态建立一块连续的存储空间,是建立的存储空间的基地址
}SeqList;

二、线性表的初始化以及根据输入的元素建立线性表

1.线性表的初始化,初始化一个空的线性表

为了使用bool函数,需要在头文件中加   #include<stdbool.h>

代码如下(示例):

//初始化线性表
bool InitList(SeqList& T)//&符号,是双向传递,引用
{
	T.R = (ElemType*)malloc(sizeof(ElemType) * MaxSize);//分配一块MaxSize这么大的,该类型的空间,返回基地址R
	if (!T.R)//检查是否成功给 线性表T分配空间 
	{
		printf("分配空间失败");
		return false;
	}
	T.length = 0;//令L.length=0 
	return true;
}

2.根据用户需求,向线性表中添加元素 

我们刚开始输入数据,对线性表中的空间进行赋值,是从1号位开始的,0号位我们用来存放哨兵

//根据输入的元素建立线性表
bool CreateList(SeqList& T)
{
	int n;
	printf("请输入您想建立的线性表中元素的个数:\n");
	scanf_s("%d", &n);
	printf("请依次输入元素:\n");
	for (int i = 1; i <= n; i++)
	{
		scanf_s("%d", &T.R[i].key);//赋值
		L.length++//!!!!!!!!这个一定要记住,第一次就是因为这个忘记,后面的功能都实现错误
	}
		
	return true;
}

三、顺序查找  Search1函数(没有设置哨兵,需要比较两次)

//顺序查找 (没有设立哨兵)
int Search1(SeqList T, int key)
{
	for (int i=1; i<=n; i++)
	{
		if (T.R[i].key == key)
			return i;
	}
	return 0;
}

四、顺序查找(设置哨兵,不用再比较是否会越界,只用比较一次)Search2函数

int Search2(SeqList T, int key) //顺序查找 (设置哨兵)
{
    //在顺序表ST中顺序查找其关键字等于key的数据元素。若找到,则函数值为
    //该元素在表中的位置,否则为0
    int i;
    T.R[0].key = key;                            //“哨兵”
    for (i =T.length; T.R[i].key != key; i--);   //从后往前找,因为我们设置的哨兵在第一个位置
                                                   //所以要从后往前找
    return i;
}

五、折半查找(非递归)Search3函数

//折半查找(非递归)
int Search3(SeqList T, int key)
{
	int low = 1;
	int high = T.length;

	while (low <= high)
	{
		int mid = (low + high) / 2;
			if (T.R[mid].key == key)
				return mid;
			else if (T.R[mid].key < key)
				low = mid + 1;
			else
				high = mid - 1;	
	}
}

六、折半查找(递归)Search4函数

//折半查找(递归)
int Search4(SeqList T, int key, int low, int high)
{
	//low = 1;
	//high = T.length;
	int mid = (low + high) / 2;
		if (T.R[mid].key == key)
			return mid;
		else if (T.R[mid].key < key)
			Search4(T, key, mid + 1, high);
		else
			Search4(T, key, low, mid-1);
}

七、显示输出函数  Show函数

void Show(int result, int key)
{
	if (result == 0)
		printf("没有找到该元素");
	else
		printf("找到元素%d,在第%d位", key, result);
}
/*这个result就是之前我们实现的4个查找函数中返回值i,因为我们刚开始输入数据,对线性表中的空间进行赋值,是从1号位开始的,0号位我们用来存放哨兵。所以最后返回的i就是元素所在的位置
如果i=0,这说明没有找到该元素,result=0*/

八、为了能在程序中一次实现以上函数,我们建立了一个Menu函数,根据用户选择,进行不同操作

真的很像我的大作业(傻掉)

void Menu() {
	printf("\n************菜单***********\n");
	printf("\n1.创建线性表;\n");
	printf("\n2.顺序查找(无哨兵);\n");
	printf("\n3.顺序查找(哨兵);\n");
	printf("\n4.折半查找(非递归);\n");
	printf("\n5.折半查找(递归);\n");
	printf("\n0.退出;\n");
	printf("\n***************************\n");
	printf("\n【请输入你的选择】\n>>>");
	printf("\n");
	printf("\n");
	printf("\n");
}

九、完整代码

因为我是在visual中运行,所以输入是scanf_s,如果uu们在自己的编译软件中运行,出现错误的话,把scanf_s  ------>scanf即可

#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>//如果想要使用bool型,则调用该头文件
#define MaxSize 10
typedef struct//定义线性表数据项结构
{
	int key;//关键字域
	int otherinfo;
}ElemType;
typedef struct//定义一个线性表结构
{
	int length;//顺序表的长度
	ElemType* R;//顺序表的动态建立,R用于之后动态建立一块连续的存储空间,是建立的存储空间的基地址
}SeqList;
//初始化线性表
bool InitList(SeqList& T)//&符号,是双向传递,引用
{
	T.R = (ElemType*)malloc(sizeof(ElemType) * MaxSize);//分配一块MaxSize这么大的,该类型的空间,返回基地址R
	if (!T.R)//检查是否成功给 线性表T分配空间 
	{
		printf("分配空间失败");
		return false;
	}
	T.length = 0;//令L.length=0 
	return true;
}
//根据输入的元素建立线性表
bool CreateList(SeqList& T)
{
	int n;
	printf("请输入您想建立的线性表中元素的个数:\n");
	scanf_s("%d", &n);
	printf("请依次输入元素:\n");
	for (int i = 1; i <= n; i++)
	{
		scanf_s("%d", &T.R[i].key);//赋值
		L.length++//!!!!!!!!这个一定要记住,第一次就是因为这个忘记,后面的功能都实现错误
	}
		
	return true;
}
//顺序查找 (没有设立哨兵)
int Search1(SeqList T, int key)
{
	for (int i=1; i<=n; i++)
	{
		if (T.R[i].key == key)
			return i;
	}
	return 0;
}
/*//顺序查找 (设立哨兵)
int Search2(SeqList T, int key)
{
	T.R[0].key = key;
	int i;
	for (i = T.length; T.R[i].key != key;i--);
	return i;
}*/
int Search2(SeqList T, int key) //顺序查找 (设立哨兵)
{
	//在顺序表ST中顺序查找其关键字等于key的数据元素。若找到,则函数值为
	//该元素在表中的位置,否则为0
	int i;
	T.R[0].key = key;                            //“哨兵”
	for (i =T.length; T.R[i].key != key; i--);   //从后往前找
	return i;
}// Search_Seq

//折半查找(非递归)
int Search3(SeqList T, int key)
{
	int low = 1;
	int high = T.length;

	while (low <= high)
	{
		int mid = (low + high) / 2;
			if (T.R[mid].key == key)
				return mid;
			else if (T.R[mid].key < key)
				low = mid + 1;
			else
				high = mid - 1;	
	}
}
//折半查找(递归)
int Search4(SeqList T, int key, int low, int high)
{
	//low = 1;
	//high = T.length;
	int mid = (low + high) / 2;
		if (T.R[mid].key == key)
			return mid;
		else if (T.R[mid].key < key)
			Search4(T, key, mid + 1, high);
		else
			Search4(T, key, low, mid-1);
}
void Show(int result, int key)
{
	if (result == 0)
		printf("没有找到该元素");
	else
		printf("找到元素%d,在第%d位", key, result);
}
void Menu() {
	printf("\n************菜单***********\n");
	printf("\n1.创建线性表;\n");
	printf("\n2.顺序查找(无哨兵);\n");
	printf("\n3.顺序查找(哨兵);\n");
	printf("\n4.折半查找(非递归);\n");
	printf("\n5.折半查找(递归);\n");
	printf("\n0.退出;\n");
	printf("\n***************************\n");
	printf("\n【请输入你的选择】\n>>>");
	printf("\n");
	printf("\n");
	printf("\n");
}

int main() {
	SeqList T;
	int key, result, user;
	while (true)
	{
		Menu();
		scanf_s("%d", &user);
		switch (user) {
		case 1: {
			if (InitList(T) && CreateList(T))
				printf("\n【创建成功……】\n");
			break;
		}
		case 2:
		{
			printf("\n-----------顺序查找无哨兵-----------\n");
			printf("\n【请输入要查找的关键字】\n>>>");
			//getchar();
			scanf_s("%d", &key);
			result = Search1(T, key);
			Show(result, key);
			printf("\n-------------------------------\n");
			break;
		}
		case 3:
		{
			printf("\n-----------顺序查找哨兵-----------\n");
			printf("\n【请输入要查找的关键字】\n>>>");
			//getchar();
			scanf_s("%d", &key);
			result = Search2(T, key);
			Show(result, key);
			printf("\n-------------------------------\n");
			break;
		}
		case 4: 
		{
			printf("\n-----------折半查找(非递归)-----------\n");
			printf("\n【请输入要查找的关键字】\n>>>");
			//getchar();
			scanf_s("%d", &key);
			result = Search3(T, key);
			Show(result, key);
			printf("\n---------------------------------------\n");
			break;
		}
		case 5: {
			printf("\n-----------折半查找(递归)-----------\n");
			printf("\n【请输入要查找的关键字】\n>>>");
			//getchar();
			scanf_s("%d", &key);
			result = Search4(T, key, 1, T.length);
			Show(result, key);
			printf("\n-------------------------------------\n");
			break;
		}
		case 0:default;
		}
	}
	return 0;
}




运行截图:

功能1创建: 

查找:线性表的C语言代码实现(顺序查找、折半查找)

功能2:顺序查找无哨兵

查找:线性表的C语言代码实现(顺序查找、折半查找)

功能3:顺序查找有哨兵

查找:线性表的C语言代码实现(顺序查找、折半查找)

 功能4:折半查找非递归

查找:线性表的C语言代码实现(顺序查找、折半查找)

  功能4:折半查找非递归

查找:线性表的C语言代码实现(顺序查找、折半查找)文章来源地址https://www.toymoban.com/news/detail-488823.html

到了这里,关于查找:线性表的C语言代码实现(顺序查找、折半查找)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

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

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

相关文章

  • 【数据结构】线性表(一)线性表的定义及其基本操作(顺序表插入、删除、查找、修改)

    目录 一、线性表 1. 线性表的定义 2. 线性表的要素 二、线性表的基本操作 三、线性表的顺序存储结构 1. 定义 2. 顺序表的操作       a. 插入操作 b. 删除操作 c. 查找操作 d. 修改操作 e. 代码实例          一个线性表是由零个或多个 具有相同类型的结点 组成的有序集合。

    2024年02月03日
    浏览(69)
  • 数据结构-线性表的顺序表基本操作代码实现(超级详细清晰 C++实现)

    顺序表是用一段 物理地址连续的存储单元 依次存储数据元素的线性结构,一般情况下采用数组存储。在数组上完成数据的增删查改。 顺序表: 可动态增长的数组,要求数据是连续存储的 特点: 随机访问 顺序既可以 静态分配 ,也可以 动态分配 。在静态分配时,由于数组

    2024年02月07日
    浏览(56)
  • 数据结构:线性表————顺序表的实现、项目和OJ题目(手把手教你写代码)

    🌈 个人主页: 小新_- 🎈个人座右铭:“成功者不是从不失败的人,而是从不放弃的人!”🎈 🎁欢迎各位→点赞👍 + 收藏⭐️ + 留言📝 🏆所属专栏:  话说那些与C++的爱恨情仇   欢迎订阅,持续更新中~~~                                           ✨让小新带着你

    2024年04月16日
    浏览(109)
  • 17-数据结构-查找-(顺序、折半、分块)

            简介:查找,顾名思义,是我们处理数据时常用的操作之一。大概就是我们从表格中去搜索我们想要的东西,这个表格,就是所谓的查找表(存储数据的表)。而我们怎么设计查找,才可以让计算机更快的去找到筛选我们所需要的信息呢,因此,关于怎么设计查找

    2024年02月09日
    浏览(58)
  • 头歌(C语言)-数据结构与算法-查找-第1关:实现折半查找

    任务描述 相关知识 编程要求 测试说明 任务描述 本关要求通过补全函数 BSL_FindKey 来实现在已排序的顺序表中查找关键码值为 key 的结点并返回该结点的编号。 相关知识 折半查找通常是针对顺序存储的线性表,线性表的结点按关键码从小到大排序,后面称之为折半查找的顺序

    2024年02月10日
    浏览(63)
  • C语言数据结构-----顺序表(多功能动态顺序表的代码实现)

    本篇讲述了顺序表的相关知识,以及动态顺序表的代码实现。 顺序表和链表一般情况下都会叫他们线性表。 线性表(linear list)是n个具有相同特性的数据元素的有限序列。线性表是一种在实际中广泛使 用的数据结构,常见的线性表:顺序表、链表、栈、队列、字符串… 线性

    2024年02月07日
    浏览(48)
  • 线性表的实现(C语言版)——详细代码

    文章目录 前言 一、线性表是什么? 二、实现步骤 1.引入头文件并定义一个宏常量 2.定义顺序表的结构 3.顺序表各种操作的实现(增删改查等) 4.主函数调用实现 5.完整代码 总结       今天对数据结构中的线性表进行了重新的梳理和复盘,有了许多收获,并花了一些时间在

    2024年02月08日
    浏览(40)
  • 【数据结构】顺序表的实现及基本操作完整代码(C语言实现)

    顺序表:逻辑上相邻的数据元素,其物理次序也是相邻的 这里之所以要把int分别创建新名字为SqlElemType和Status,是因为实际应用时数据的类型不一定是int型,这样设置方便修改元素类型,提高代码适用性。 LocateElem的时间复杂度为O(n) InsertSq的时间复杂度为O(n) DeleteSq的时间

    2024年04月12日
    浏览(50)
  • C++数据结构之查找——静态查找表(顺序查找、折半查找、分块查找 带有gif以及图示)

    目录 一、查找的相关概念介绍 1.查找表(Search Table) 概念 对查找表的操作 查找表的分类 2.(Key) 概念 3.查找(Searching) 概念 4.衡量查找算法的标准 1.时间复杂度 2.空间复杂度 3.平均查找长度(ASL) 二、静态查找表 1.顺序查找 算法思路 算法举例 算法性能分析 不等概率

    2024年02月03日
    浏览(44)
  • 数据结构-顺序表的基本实现(C语言,简单易懂,含全部代码)

    今天起开始编写数据结构中的各种数据结构及算法的实现,说到顺序表,我们首先得了解下线性表。 线性表(linear list)是n个具有相同特性的数据元素的有限序列。 线性表是一种在实际中广泛使用的数据结构,常见的线性表:顺序表、链表、栈、队列、字符串… 线性表在逻

    2023年04月08日
    浏览(41)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包