目录
一、线性表结构 两个类的定义
二、线性表的初始化以及根据输入的元素建立线性表
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创建:
功能2:顺序查找无哨兵
功能3:顺序查找有哨兵
功能4:折半查找非递归
文章来源:https://www.toymoban.com/news/detail-488823.html
功能4:折半查找非递归
文章来源地址https://www.toymoban.com/news/detail-488823.html
到了这里,关于查找:线性表的C语言代码实现(顺序查找、折半查找)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!