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

C语言---数据结构实验---查找算法的实现---实现给定数组的快速排序

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

写在前面

  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;
}

实现给定数组的快速排序

题目描述

内容要求：

  1. 以菜单的形式作为用户界面，接收待排序的输入序列，使用快速排序的方法对输入序列进行快速排序。
  2. 测试数据：
    80，43，18，21，30，13，52，51，75

题目分析

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

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

#include <stdio.h>
#include <stdlib.h>
void PrintArrey(int* a, int n)
{
  for (int i = 0; i < n; i++)
  {
    printf("%d ", a[i]);
  }
  printf("\n");
}
void Swap(int* a, int* b)
{
  int tmp = *a;
  *a = *b;
  *b = tmp;
}
int PartSort(int* a, int left, int right)
{
  int cur = left + 1;
  int prev = left;
  int keyi = left;
  while (cur <= right)
  {
    if (a[cur] < a[keyi])
    {
      ++prev;
      Swap(&a[prev], &a[cur]);
    }
    cur++;
  }
  Swap(&a[prev], &a[keyi]);
  return prev;
}
void QuickSort(int* a, int begin, int end)
{
  if (begin >= end)
  {
    return;
  }
  int keyi = PartSort(a, begin, end);
  QuickSort(a, begin, keyi - 1);
  QuickSort(a, keyi + 1, end);
}
void menu()
{
  printf("*****************************\n");
  printf("********* 1. Sort **********\n");
  printf("********* 0. exit  **********\n");
  printf("*****************************\n");
}
void CheckCapacity(int* a, int num, int* capacity)
{
  if (num > *capacity)
  {
    int* tmp = (int*)realloc(a, sizeof(int) * num);
    if (tmp == NULL)
    {
      perror("realloc fail");
      return;
    }
    a = tmp;
    *capacity = num;
  }
  else
  {
    return;
  }
}
void Sort()
{
  int capacity = 10;
  int* a = (int*)malloc(sizeof(int) * capacity);
  if (a == NULL)
  {
    perror("malloc fail");
    return;
  }
  int num;
  printf("输入要输入元素的个数->");
  scanf("%d", &num);
  CheckCapacity(a, num, &capacity);
  printf("输入对应个数的元素->");
  for (int i = 0; i < num; i++)
  {
    scanf("%d", &a[i]);
  }
  QuickSort(a, 0, num - 1);
  printf("排序完成:\n");
  PrintArrey(a, num);
  free(a);
  a = NULL;
}
int main()
{
  int input = 0;
  do
  {
    menu();
    scanf("%d", &input);
    switch (input)
    {
    case 1:
      Sort();
      break;
    case 0:
      break;
    default:
      printf("输入错误 重新输入\n");
    }
  } while (input);
}


文章标签：
算法
C语言
关键词：
数据结构算法
C语言数组
C语言数据结构
数据结构快速排序
C语言算法
海绵宝宝de派小星
目录
相关文章
陌陌谣
|
2月前
|
存储 监控 安全
企业上网监控系统中红黑树数据结构的 Python 算法实现与应用研究
企业上网监控系统需高效处理海量数据，传统数据结构存在性能瓶颈。红黑树通过自平衡机制，确保查找、插入、删除操作的时间复杂度稳定在 O(log n)，适用于网络记录存储、设备信息维护及安全事件排序等场景。本文分析红黑树的理论基础、应用场景及 Python 实现，并探讨其在企业监控系统中的实践价值，提升系统性能与稳定性。
陌陌谣
59 1
陌陌谣
|
2月前
|
存储 监控 算法
基于跳表数据结构的企业局域网监控异常连接实时检测 C++ 算法研究
跳表（Skip List）是一种基于概率的数据结构，适用于企业局域网监控中海量连接记录的高效处理。其通过多层索引机制实现快速查找、插入和删除操作，时间复杂度为 $O(\log n)$，优于链表和平衡树。跳表在异常连接识别、黑名单管理和历史记录溯源等场景中表现出色，具备实现简单、支持范围查询等优势，是企业网络监控中动态数据管理的理想选择。
陌陌谣
61 0
土木林森
|
10月前
|
算法 数据处理 C语言
C语言中的位运算技巧，涵盖基本概念、应用场景、实用技巧及示例代码，并讨论了位运算的性能优势及其与其他数据结构和算法的结合
本文深入解析了C语言中的位运算技巧，涵盖基本概念、应用场景、实用技巧及示例代码，并讨论了位运算的性能优势及其与其他数据结构和算法的结合，旨在帮助读者掌握这一高效的数据处理方法。
土木林森
375 1
哈基米编译器
|
5月前
|
算法 搜索推荐
快速排序-数据结构与算法
快速排序（Quick Sort）是一种基于分治法的高效排序算法。其核心思想是通过选择基准（pivot），将数组划分为左右两部分，使得左侧元素均小于基准，右侧元素均大于基准，然后递归地对左右两部分进行排序。时间复杂度平均为 O(n log n)，最坏情况下为 O(n²)（如数组已有序）。空间复杂度为 O(1)，属于原地排序，但稳定性不佳。 实现步骤包括编写 `partition` 核心逻辑、递归调用的 `quickSort` 和辅助函数 `swap`。优化方法有随机化基准和三数取中法，以减少最坏情况的发生。
哈基米编译器
268 13
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
羑悻的小杀马特
|
7月前
|
定位技术 C语言
c语言及数据结构实现简单贪吃蛇小游戏
c语言及数据结构实现简单贪吃蛇小游戏
羑悻的小杀马特
188 13
程序员Feri
|
7月前
|
存储 人工智能 程序员
一文彻底搞明白C语言的数组
本文详细介绍了C语言中的数组，包括定义、初始化（静态与动态）、存储方式、访问方法及常用操作，如遍历、修改元素和作为函数参数传递。数组是C语言中最基本的数据结构之一，掌握它对编程至关重要。下篇将介绍二维数组，敬请期待！
程序员Feri
300 0
一文彻底搞明白C语言的数组
羑悻的小杀马特
|
8月前
|
搜索推荐 C语言
数据结构（C语言）之对归并排序的介绍与理解
归并排序是一种基于分治策略的排序算法，通过递归将数组不断分割为子数组，直到每个子数组仅剩一个元素，再逐步合并这些有序的子数组以得到最终的有序数组。递归版本中，每次分割区间为[left, mid]和[mid+1, right]，确保每两个区间内数据有序后进行合并。非递归版本则通过逐步增加gap值（初始为1），先对单个元素排序，再逐步扩大到更大的区间进行合并，直至整个数组有序。归并排序的时间复杂度为O(n*logn)，空间复杂度为O(n)，且具有稳定性，适用于普通排序及大文件排序场景。
羑悻的小杀马特
115 13

热门文章

最新文章

  • 1
    近端策略优化算法PPO的核心概念和PyTorch实现详解
  • 2
    MARS算法理论和Python代码实现：用分段回归解决非线性时间序列预测问题
  • 3
    【无人机】基于灰狼优化算法的无人机路径规划问题研究（Matlab代码实现）
  • 4
    使用变动和观察（Perturb and Observe）最大功率点跟踪（MPPT）算法控制升压变换器的MOSFET/IGBT（开关），以从光伏阵列中提取最大功率（Simulink仿真实现）
  • 5
    【车间调度】基于GA、PSO、SA、ACO、TS优化算法的车间调度比较研究（Matlab代码实现）
  • 6
    【无人机编队】基于非支配排序遗传算法II NSGA-II高效可行的无人机离线集群仿真研究（Matlab代码实现）
  • 7
    【23年新算法】基于鱼鹰算法OOA-Transformer-BiLSTM多特征分类预测附Matlab代码 （多输入单输出）（Matlab代码实现）
  • 8
    【优化调度】基于matlab粒子群算法求解水火电经济调度优化问题研究（Matlab代码实现）
  • 9
    基于PSO粒子群优化的XGBoost时间序列预测算法matlab仿真
  • 10
    离散粒子群算法（DPSO）的原理与MATLAB实现
  • 1
    小米教你：2GB内存搞定20亿数据的高效算法
    308
  • 2
    【博士每天一篇文献-综述】基于脑启发的连续学习算法有哪些？附思维导图
    243
  • 3
    【博士每天一篇文献-算法】Machine Unlearning via Representation Forgetting With Parameter Self-Sharing
    248
  • 4
    【博士每天一篇文献-算法】Zero-Shot Machine Unlearning
    224
  • 5
    【博士每天一篇文献-算法】Optimal resilience of modular interacting networks
    94
  • 6
    【博士每天一篇文献-算法】CircuitNet：A Generic Neural Network to Realize Universal Circuit Motif Modeling
    135
  • 7
    【博士每天一篇文献-算法】Memory augmented echo state network for time series prediction
    126
  • 8
    【博士每天一篇论文-算法】Continual Learning Through Synaptic Intelligence，SI算法
    584
  • 9
    【博士每天一篇论文-算法】Overview of Echo State Networks using Different Reservoirs and Activation Functions
    85
  • 10
    RetinaNet算法1
    178

    • 相关课程

    更多
  • 智能创作赛（初赛）：相册应用中的故事生成算法介绍
  • 相册服务中的故事生成算法介绍
  • Go语言核心编程 - 数据结构和算法
  • 你的第一门C语言课
  • C语言学习教程
  • 神经网络概览及算法详解

    • 相关电子书

    更多
  • 【云栖精选7月刊】抛开晦涩的算法、模型，让我们来谈谈互联网架构
  • 聚星台—客户运营核心大数据 与算法技术
  • Apache Flink 流式应用中状态的数据结构定义升级
    • 下一篇
    蛋白质语言模型 ProGen：在实验室合成由 AI 预测的蛋白质