AI 助理
备案控制台
开发者社区 人工智能 文章 正文

数据结构---查找算法的实现

2023-07-22 68
版权
版权声明：
本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《 阿里云开发者社区用户服务协议》和 《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写 侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
简介： 数据结构---查找算法的实现

@[toc]

写在前面

  1. 本篇实现也全部通过动态内存实现

  2. 快速排序是通过递归或非递归实现的，其中对于单趟PartSort也有三种不同的算法，这三种不同的算法效率没有差异，通常是通过递归实现快速排序，非递归需要借助栈或队列，这里展示的是递归版、前后指针法实现快速排序，如果有其他需求可以看此文章自行寻找所需算法

数据结构---手撕图解排序(含动图演示)

查找算法的实现

题目描述

内容要求：

  1. 创建如下查找表：

学号 姓名 高等数学 C程序设计 数据结构
1301 白雪 88 92 89
1302 常亮 73 77 68
1303 冯玲 80 82 75
1304 李斌 90 89 90
1305 任芳 60 71 58
1306 史可 78 88 79
1307 吴伟 95 89 90
1308 杨宁 75 86 84
1309 张华 83 79 80
1310 郑新 58 62 60

  1. 使用顺序查找算法，从查找表中查找姓名为任芳和赵斌的学生。若查找成功，则给出该生相关信息，若查找不成功，则给出相应提示信息。

  2. 使用二分法查找算法，从查找表中查找数据结构成绩为68和90的学生。若查找成功，则给出该生相关信息，若查找不成功，则给出相应提示信息。

题目分析

手动输入数据法

#include<stdio.h>
#include<string.h>
#include<stdlib.h>


typedef struct
{
   
    int num;
    char name[50];
    int score_G;
    int score_C;
    int score_S;
}SLDataType;

typedef struct
{
   
    SLDataType* elem;
    int size;
    int capacity;
}SSTable;

void CheckCapacity(SSTable* ps)
{
   
    if (ps->capacity <= ps->size)
    {
   
        int newcapacity = ps->capacity * 2;
        SLDataType* tmp = (SLDataType*)realloc(ps->elem, sizeof(SLDataType) * newcapacity);
        if (tmp == NULL)
        {
   
            perror("realloc fail");
            return;
        }
        ps->capacity = newcapacity;
        ps->elem = tmp;
    }
}

void SeqListInit(SSTable* ps)
{
   
    ps->size = 0;
    ps->capacity = 8;
    ps->elem = (SLDataType*)malloc(ps->capacity * sizeof(SLDataType));
    if (ps->elem == NULL)
    {
   
        perror("malloc fail");
        return;
    }
}

void CreateList(SSTable* ps)
{
   
    printf("输入线性表的长度->");
    scanf("%d", &ps->size);
    CheckCapacity(ps);
    printf("请输入线性表的内容：");
    printf("\n学号  姓名  高等数学  C程序设计  数据结构\n");
    for (int i = 0; i < ps->size; i++)
    {
   
        scanf("%d", &ps->elem[i].num);
        scanf("%s", ps->elem[i].name);
        scanf("%d", &ps->elem[i].score_G);
        scanf("%d", &ps->elem[i].score_C);
        scanf("%d", &ps->elem[i].score_S);
    }
}

void Search_name(SSTable* ps)
{
   
    int i = 0;
    char name[50];
    printf("请输入要查找的姓名->");
    scanf("%s", name);
    for (i = 0; i < ps->size; i++)
    {
   
        if (strcmp(name, ps->elem[i].name) == 0)
        {
   
            printf("%d", ps->elem[i].num);
            printf("%5s", ps->elem[i].name);
            printf("%5d", ps->elem[i].score_G);
            printf("%5d", ps->elem[i].score_C);
            printf("%5d", ps->elem[i].score_S);
            break;
        }
        else
        {
   
            printf("无相关信息！");
        }
    }
}

void Search_score(SSTable* ps)
{
   
    int score_S;
    printf("\n请输入要查找的数据结构成绩：\n");
    scanf("%d", &score_S);
    int low = 0;
    int high = ps->size - 1;
    int mid = (low + high) / 2;
    while (low <= high)
    {
   
        mid = (low + high) / 2;

        if (score_S == ps->elem[mid].score_S)
        {
   
            printf("%4d", ps->elem[mid].num);
            printf("%5s", ps->elem[mid].name);
            printf("%5d", ps->elem[mid].score_G);
            printf("%5d", ps->elem[mid].score_C);
            printf("%5d", ps->elem[mid].score_S);
            break;
        }
        else if (score_S < ps->elem[mid].score_S)
        {
   
            high = mid - 1;
        }
        else
        {
   
            low = mid + 1;
        }

    }
    if (high < low)
    {
   
        printf("无相关信息！");
    }
}

void sort_score_S(SSTable* ps)
{
   
    int i, j;
    SLDataType temp;
    for (i = 0; i < ps->size - 1; i++)
    {
   
        for (j = 0; j < ps->size - 1 - i; j++)
        {
   
            if (ps->elem[j + 1].score_S > ps->elem[j].score_S)
            {
   
                temp = ps->elem[j + 1];
                ps->elem[j + 1] = ps->elem[j];
                ps->elem[j] = temp;
            }
        }
    }
    printf("\n将数据结构成绩按由小到大进行排序：\n");
    for (i = 0; i < ps->size; i++)
    {
   
        printf("%5d", ps->elem[i].num);
        printf("%5s", ps->elem[i].name);
        printf("%5d", ps->elem[i].score_G);
        printf("%5d", ps->elem[i].score_C);
        printf("%5d", ps->elem[i].score_S);
        printf("\n");
    }
}

void menu()
{
   
    printf("\n---------------1.按姓名查找---------------\n");
    printf("\n-----------2.按数据结构成绩查找------------\n");
    printf("\n---------------0.退出查找！---------------\n");
}

int main()
{
   
    SSTable s;
    SeqListInit(&s);
    int input = 0;
    menu();
    CreateList(&s);
    sort_score_S(&s);
    do
    {
   
        menu();
        scanf("%d", &input);
        switch (input)
        {
   
        case 1:
            Search_name(&s);
            break;
        case 2:
            Search_score(&s);
            break;
        case 0:
            break;
        default:
            printf("该关键字非法！");
            break;
        }
    } while (input);
    return 0;
}

直接读取文件写法

直接读取文件需要在根目录下加入test.txt
内容为表格内容

#include<stdio.h>
#include<string.h>
#include<stdlib.h>


typedef struct
{
   
    int num;
    char name[50];
    int score_G;
    int score_C;
    int score_S;
}SLDataType;

typedef struct
{
   
    SLDataType* elem;
    int size;
    int capacity;
}SSTable;

void CheckCapacity(SSTable* ps)
{
   
    if (ps->capacity <= ps->size)
    {
   
        int newcapacity = ps->capacity * 2;
        SLDataType* tmp = (SLDataType*)realloc(ps->elem, sizeof(SLDataType) * newcapacity);
        if (tmp == NULL)
        {
   
            perror("realloc fail");
            return;
        }
        ps->capacity = newcapacity;
        ps->elem = tmp;
    }
}

void SeqListInit(SSTable* ps)
{
   
    ps->size = 0;
    ps->capacity = 8;
    ps->elem = (SLDataType*)malloc(ps->capacity * sizeof(SLDataType));
    if (ps->elem == NULL)
    {
   
        perror("malloc fail");
        return;
    }
}

void CreateList(SSTable* ps)
{
   
    FILE* pf = fopen("data.txt", "r");
    if (pf == NULL)
    {
   
        perror("fopen fail");
        return;
    }
    ps->size = 10;
    CheckCapacity(ps);
    printf("\n学号  姓名  高等数学  C程序设计  数据结构\n");
    for (int i = 0; i < ps->size; i++)
    {
   
        fscanf(pf,"%d", &ps->elem[i].num);
        fscanf(pf,"%s", ps->elem[i].name);
        fscanf(pf,"%d", &ps->elem[i].score_G);
        fscanf(pf,"%d", &ps->elem[i].score_C);
        fscanf(pf,"%d", &ps->elem[i].score_S);
    }
}

void Search_name(SSTable* ps)
{
   
    int i = 0;
    char name[50];
    printf("请输入要查找的姓名->");
    scanf("%s", name);
    for (i = 0; i < ps->size; i++)
    {
   
        if (strcmp(name, ps->elem[i].name) == 0)
        {
   
            printf("%d", ps->elem[i].num);
            printf("%5s", ps->elem[i].name);
            printf("%5d", ps->elem[i].score_G);
            printf("%5d", ps->elem[i].score_C);
            printf("%5d", ps->elem[i].score_S);
            break;
        }
        else
        {
   
            printf("无相关信息！");
        }
    }
}

void Search_score(SSTable* ps)
{
   
    int score_S;
    printf("\n请输入要查找的数据结构成绩：\n");
    scanf("%d", &score_S);
    int low = 0;
    int high = ps->size - 1;
    int mid = (low + high) / 2;
    while (low <= high)
    {
   
        mid = (low + high) / 2;

        if (score_S == ps->elem[mid].score_S)
        {
   
            printf("%4d", ps->elem[mid].num);
            printf("%5s", ps->elem[mid].name);
            printf("%5d", ps->elem[mid].score_G);
            printf("%5d", ps->elem[mid].score_C);
            printf("%5d", ps->elem[mid].score_S);
            break;
        }
        else if (score_S < ps->elem[mid].score_S)
        {
   
            high = mid - 1;
        }
        else
        {
   
            low = mid + 1;
        }

    }
    if (high < low)
    {
   
        printf("无相关信息！");
    }
}

void sort_score_S(SSTable* ps)
{
   
    int i, j;
    SLDataType temp;
    for (i = 0; i < ps->size - 1; i++)
    {
   
        for (j = 0; j < ps->size - 1 - i; j++)
        {
   
            if (ps->elem[j].score_S > ps->elem[j+1].score_S)
            {
   
                temp = ps->elem[j+1];
                ps->elem[j+1] = ps->elem[j];
                ps->elem[j] = temp;
            }
        }
    }
    printf("\n将数据结构成绩按由小到大进行排序：\n");
    for (i = 0; i < ps->size; i++)
    {
   
        printf("%5d", ps->elem[i].num);
        printf("%10s", ps->elem[i].name);
        printf("%5d", ps->elem[i].score_G);
        printf("%5d", ps->elem[i].score_C);
        printf("%5d", ps->elem[i].score_S);
        printf("\n");
    }
}

void menu()
{
   
    printf("\n---------------1.按姓名查找---------------\n");
    printf("\n-----------2.按数据结构成绩查找------------\n");
    printf("\n---------------0.退出查找！---------------\n");
}

int main()
{
   
    SSTable s;
    SeqListInit(&s);
    int input = 0;
    menu();
    CreateList(&s);
    sort_score_S(&s);
    do
    {
   
        menu();
        scanf("%d", &input);
        switch (input)
        {
   
        case 1:
            Search_name(&s);
            break;
        case 2:
            Search_score(&s);
            break;
        case 0:
            break;
        default:
            printf("该关键字非法！");
            break;
        }
    } while (input);
    return 0;
}
文章标签：
算法
关键词：
数据结构算法
数据结构查找算法
海绵宝宝de派小星
目录
相关文章
反季雪
|
2月前
|
存储 算法
【数据结构和算法】--- 二叉树（4）--二叉树链式结构的实现（2）
【数据结构和算法】--- 二叉树（4）--二叉树链式结构的实现（2）
反季雪
22 0
aliyun6365824167
|
1天前
|
算法
【初阶数据结构】复杂度算法题篇
该方法基于如下的事实：当我们将数组的元素向右移动 k 次后，尾部 kmodn 个元素会移动至数组头部，其余元素向后移动 kmodn 个位置。
aliyun6365824167
9 1
AI之家
|
2天前
|
机器学习/深度学习 人工智能 算法
【人工智能】线性回归模型：数据结构、算法详解与人工智能应用，附代码实现
线性回归是一种预测性建模技术，它研究的是因变量（目标）和自变量（特征）之间的关系。这种关系可以表示为一个线性方程，其中因变量是自变量的线性组合。
AI之家
11 2
aliyun6365824167
|
1天前
|
算法
【初阶数据结构篇】二叉树算法题
二叉树是否对称，即左右子树是否对称.
aliyun6365824167
7 0
aliyun6365824167
|
1天前
|
算法 索引
【初阶数据结构篇】单链表算法题进阶
深拷贝应该正好由 n 个全新节点组成，其中每个新节点的值都设为其对应的原节点的值。
aliyun6365824167
7 0
aliyun6365824167
|
1天前
|
存储 算法
【初阶数据结构篇】顺序表和链表算法题
此题可以先找到中间节点，然后把后半部分逆置，最近前后两部分一一比对，如果节点的值全部相同，则即为回文。
aliyun6365824167
6 0
是基德吖
|
1月前
|
机器学习/深度学习 存储 算法
【数据结构】算法的复杂度
算法的时间复杂度和空间复杂度
是基德吖
38 1
【数据结构】算法的复杂度
你都不懂
|
27天前
|
搜索推荐 算法
【数据结构】排序算法——Lesson2
【7月更文挑战第24天】
你都不懂
14 3
william.zhang(张)
|
4天前
|
存储 缓存 算法
深入解析B树：数据结构、存储结构与算法优势
深入解析B树：数据结构、存储结构与算法优势
william.zhang(张)
5 0
众所周知
|
1月前
|
存储 算法 Python
“解锁Python高级数据结构新姿势：图的表示与遍历，让你的算法思维跃升新高度
【7月更文挑战第13天】Python中的图数据结构用于表示复杂关系，通过节点和边连接。常见的表示方法是邻接矩阵（适合稠密图）和邻接表（适合稀疏图）。图遍历包括DFS（深度优先搜索）和BFS（广度优先搜索）：DFS深入探索分支，BFS逐层访问邻居。掌握这些技巧对优化算法和解决实际问题至关重要。**
众所周知
21 1

热门文章

最新文章

  • 1
    数据结构之栈与队列
  • 2
    redis数据结构实现（一）
  • 3
    数据结构-第二章-单链表-带头节点实现各种基本功能
  • 4
    数据结构:树和二叉树定义和术语
  • 5
    Python实现双端队列数据结构及其基本方法
  • 6
    UVa 514 Rails(经典栈)
  • 7
    数据结构实践——队列数组
  • 8
    【Java数据结构学习笔记之一】线性表的存储结构及其代码实现
  • 9
    java-数据结构-续
  • 10
    数据结构-C语言递归实现树的前中后序遍历
  • 1
    操作数栈的字节码指令执行分析
    29
  • 2
    D1. Range Sorting (Easy Version)(单调栈+思维)
    26
  • 3
    InfluxDB数据模型与数据结构设计详解
    322
  • 4
    数据结构面试常见问题
    51
  • 5
    22个常用数据结构实现与原理分析
    41
  • 6
    数据结构——二叉树的遍历【前序、中序、后序】
    32
  • 7
    数据结构奇妙旅程之红黑树
    22
  • 8
    数据结构奇妙旅程之二叉平衡树进阶---AVL树
    18
  • 9
    数据结构奇妙旅程之二叉平衡树
    14
  • 10
    数据结构奇妙旅程之七大排序
    16

    • 相关课程

    更多
  • Go语言核心编程 - 数据结构和算法
  • 神经网络概览及算法详解
  • 相册服务中的故事生成算法介绍
  • 智能运维赛（复赛）：利用数据和算法，快速定位系统异常并进行根因分析
  • 智能创作赛（复赛）：相册应用中的视频故事生成算法介绍
  • 智能创作赛（初赛）：相册应用中的故事生成算法介绍

    • 相关电子书

    更多
  • 如何使用Tair增强数据结构构建丰富在线实时场景
  • Apache Flink 流式应用中状态的数据结构定义升级
  • 图解算法小抄

    • 相关实验场景

    更多
  • 使用Swing算法实现商品推荐
  • RSA密码算法设计与实现
  • 欧拉图的构造性证明与算法实现
  • 推荐系统入门之使用ALS算法实现打分预测
    • 下一篇
    通义千问API入门教程