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

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

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

@[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月前
|
存储 监控 安全
企业上网监控系统中红黑树数据结构的 Python 算法实现与应用研究
企业上网监控系统需高效处理海量数据，传统数据结构存在性能瓶颈。红黑树通过自平衡机制，确保查找、插入、删除操作的时间复杂度稳定在 O(log n)，适用于网络记录存储、设备信息维护及安全事件排序等场景。本文分析红黑树的理论基础、应用场景及 Python 实现，并探讨其在企业监控系统中的实践价值，提升系统性能与稳定性。
陌陌谣
59 1
陌陌谣
|
2月前
|
存储 监控 算法
基于跳表数据结构的企业局域网监控异常连接实时检测 C++ 算法研究
跳表（Skip List）是一种基于概率的数据结构，适用于企业局域网监控中海量连接记录的高效处理。其通过多层索引机制实现快速查找、插入和删除操作，时间复杂度为 $O(\log n)$，优于链表和平衡树。跳表在异常连接识别、黑名单管理和历史记录溯源等场景中表现出色，具备实现简单、支持范围查询等优势，是企业网络监控中动态数据管理的理想选择。
陌陌谣
61 0
土木林森
|
10月前
|
算法 数据处理 C语言
C语言中的位运算技巧，涵盖基本概念、应用场景、实用技巧及示例代码，并讨论了位运算的性能优势及其与其他数据结构和算法的结合
本文深入解析了C语言中的位运算技巧，涵盖基本概念、应用场景、实用技巧及示例代码，并讨论了位运算的性能优势及其与其他数据结构和算法的结合，旨在帮助读者掌握这一高效的数据处理方法。
土木林森
375 1
java冯坚持
|
11月前
|
存储 人工智能 算法
数据结构与算法细节篇之最短路径问题：Dijkstra和Floyd算法详细描述，java语言实现。
这篇文章详细介绍了Dijkstra和Floyd算法，这两种算法分别用于解决单源和多源最短路径问题，并且提供了Java语言的实现代码。
java冯坚持
559 3
数据结构与算法细节篇之最短路径问题：Dijkstra和Floyd算法详细描述，java语言实现。
Cyan_RA9
|
7月前
|
存储 机器学习/深度学习 算法
C 408—《数据结构》算法题基础篇—链表（下）
408考研——《数据结构》算法题基础篇之链表（下）。
Cyan_RA9
184 30
Cyan_RA9
|
7月前
|
存储 算法 C语言
C 408—《数据结构》算法题基础篇—链表（上）
408考研——《数据结构》算法题基础篇之链表（上）。
Cyan_RA9
285 25
Cyan_RA9
|
7月前
|
存储 人工智能 算法
C 408—《数据结构》算法题基础篇—数组（通俗易懂）
408考研——《数据结构》算法题基础篇之数组。(408算法题的入门)
Cyan_RA9
264 23
光明顶阳顶天
|
10月前
|
存储 算法 搜索推荐
Python 中数据结构和算法的关系
数据结构是算法的载体，算法是对数据结构的操作和运用。它们共同构成了计算机程序的核心，对于提高程序的质量和性能具有至关重要的作用
光明顶阳顶天
188 33
RossyYan
|
8月前
|
存储 算法 测试技术
【C++数据结构——树】二叉树的遍历算法（头歌教学实验平台习题） 【合集】
本任务旨在实现二叉树的遍历，包括先序、中序、后序和层次遍历。首先介绍了二叉树的基本概念与结构定义，并通过C++代码示例展示了如何定义二叉树节点及构建二叉树。接着详细讲解了四种遍历方法的递归实现逻辑，以及层次遍历中队列的应用。最后提供了测试用例和预期输出，确保代码正确性。通过这些内容，帮助读者理解并掌握二叉树遍历的核心思想与实现技巧。
RossyYan
253 3
德国都芳最好
|
10月前
|
数据采集 存储 算法
Python 中的数据结构和算法优化策略
Python中的数据结构和算法如何进行优化？
德国都芳最好
211 19

热门文章

最新文章

  • 1
    Redis数据库的五类核心数据结构详解
  • 2
    Redis核心数据结构与分布式锁实现详解
  • 3
    MySQL数据库索引的数据结构？
  • 4
    基于跳表数据结构的企业局域网监控异常连接实时检测 C++ 算法研究
  • 5
    企业上网监控系统中红黑树数据结构的 Python 算法实现与应用研究
  • 6
    公司员工泄密防护体系中跳表数据结构及其 Go 语言算法的应用研究
  • 7
    c++数据结构之顺序表
  • 8
    【算法与数据结构】关于代码运行时间复杂度的计算方法
  • 9
    【模板】栈
  • 10
    软考中的数据结构
  • 1
    【数据结构】遍历二叉树（递归思想）--＞赋源码
    106
  • 2
    【数据结构】二叉树顺序实现（大堆）--＞赋源码
    77
  • 3
    【数据结构】栈和队列--＞理解和实现（赋源码)
    67
  • 4
    【数据结构】双向带头（哨兵位）循环链表 —详细讲解（赋源码）
    173
  • 5
    【数据结构】单链表--＞详细讲解，后赋源码
    52
  • 6
    深入探索堆：Go语言中的高效数据结构
    143
  • 7
    揭秘MongoDB：这个神奇的建模技巧将如何彻底改变你的数据结构？
    95
  • 8
    PHP 数据结构的巅峰对决：在机器学习的舞台上，谁将主宰沉浮？
    85
  • 9
    揭秘C#.Net编程秘宝：结构体类型Struct，让你的数据结构秒变高效战斗机，编程界的新星就是你！
    419
  • 10
    栈溢出处理
    391

    • 相关课程

    更多
  • Go语言核心编程 - 数据结构和算法

    • 相关电子书

    更多
  • 如何使用Tair增强数据结构构建丰富在线实时场景
  • Apache Flink 流式应用中状态的数据结构定义升级
  • 低代码开发师（初级）实战教程
    • 下一篇
    蛋白质语言模型 ProGen：在实验室合成由 AI 预测的蛋白质