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

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

2023-10-13 56
版权
版权声明：
本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《 阿里云开发者社区用户服务协议》和 《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写 侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
简介： 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语言数据结构
数据结构快速排序
算法快速排序
海绵宝宝de派小星
目录
相关文章
weixin_836869520
|
3天前
|
搜索推荐 算法 Java
Java数据结构与算法：排序算法之快速排序
Java数据结构与算法：排序算法之快速排序
weixin_836869520
9 1
倔强的石头_
|
5天前
|
存储 缓存 前端开发
【数据结构/C语言】深入理解 双向链表
【数据结构/C语言】深入理解 双向链表
倔强的石头_
16 0
倔强的石头_
|
5天前
|
存储 算法 C语言
二分查找算法的概念、原理、效率以及使用C语言循环和数组的简单实现
二分查找算法的概念、原理、效率以及使用C语言循环和数组的简单实现
倔强的石头_
17 3
东方睿赢
|
9天前
|
搜索推荐 算法 Java
Java中的快速排序、归并排序和堆排序是常见的排序算法。
【6月更文挑战第21天】Java中的快速排序、归并排序和堆排序是常见的排序算法。快速排序采用分治，以基准元素划分数组并递归排序；归并排序同样分治，先分割再合并有序子数组；堆排序通过构建堆来排序，保持堆性质并交换堆顶元素。每种算法各有优劣：快排平均高效，最坏O(n²)；归并稳定O(n log n)但需额外空间；堆排序O(n log n)且原地排序，但不稳定。
东方睿赢
19 3
凯子坚持c
|
9天前
|
算法 C语言
C语言----判断n是否是2的次方数，利用到按位与&，算法n&(n-1)
C语言----判断n是否是2的次方数，利用到按位与&，算法n&(n-1)
凯子坚持c
11 2
龙大吉
|
15天前
|
机器学习/深度学习 算法 C语言
详细介绍递归算法在 C 语言中的应用，包括递归的基本概念、特点、实现方法以及实际应用案例
【6月更文挑战第15天】递归算法在C语言中是强大力量的体现，通过函数调用自身解决复杂问题。递归涉及基本概念如自调用、终止条件及栈空间管理。在C中实现递归需定义递归函数，分解问题并设定停止条件。阶乘和斐波那契数列是经典应用示例，展示了递归的优雅与效率。然而，递归可能导致栈溢出，需注意优化。学习递归深化了对“分而治之”策略的理解。**
龙大吉
30 7
陈佳烨
|
11天前
|
算法 Java C语言
Java中的算法与C语言中的函数
Java中的算法与C语言中的函数
陈佳烨
11 2
空白诗
|
13天前
|
算法 搜索推荐 JavaScript
算法学习：快速排序
算法学习：快速排序
空白诗
13 1
誓则盟约
|
19天前
|
算法
数据结构与算法-快速排序
数据结构与算法-快速排序
誓则盟约
9 1
米诺斯
|
3天前
|
存储 编译器 C语言
C语言的联合体：一种节省内存的数据结构
C语言的联合体：一种节省内存的数据结构
米诺斯
7 0

热门文章

最新文章

  • 1
    m基于LDPC编译码的matlab误码率仿真,对比SP,MS,NMS以及OMS四种译码算法
  • 2
    【AI 初识】人工智能中使用了哪些不同的搜索算法？
  • 3
    探索机器学习中的支持向量机（SVM）算法
  • 4
    通过Rust实现公司电脑监控软件的性能优化算法
  • 5
    论文介绍：进化算法优化模型融合策略
  • 6
    探索机器学习中的支持向量机算法
  • 7
    【AI 初识】描述遗传算法概念
  • 8
    Python遗传算法GA对长短期记忆LSTM深度学习模型超参数调优分析司机数据|附数据代码
  • 9
    LRU（Least Recently Used）算法是一种常用的计算机缓存替换算法
  • 10
    机器学习算法原理与应用：深入探索与实战
  • 1
    【算法与数据结构】深入解析二叉树（二）之堆结构实现
    31
  • 2
    ABAP 源代码如何创建嵌套的内表，即内表列数据结构又是内表
    36
  • 3
    Redis数据类型详解：选择合适的数据结构优化你的应用
    80
  • 4
    【算法与数据结构】二叉树（前中后）序遍历2
    25
  • 5
    【MongoDB】MongoDB 如何处理复杂的数据结构？
    43
  • 6
    【数据结构】排序算法
    35
  • 7
    【数据结构】C语言实现链队列(附完整运行代码)
    56
  • 8
    深入理解InnoDB索引数据结构和算法
    75
  • 9
    【数据结构】深入浅出理解链表中二级指针的应用
    45
  • 10
    【数据结构】线性表的链式存储结构
    29

    • 相关课程

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

    • 相关电子书

    更多
  • 数据+算法定义新世界
  • 袋鼠云基于实时计算的反黄牛算法
  • Alink：基于Apache Flink的算法平台

    • 相关实验场景

    更多
  • 推荐系统入门之使用ALS算法实现打分预测
  • 欧拉图的构造性证明与算法实现
  • RSA密码算法设计与实现
  • RSA非对称加密算法
  • 使用Swing算法实现商品推荐
    • 下一篇
    部署LAMP环境（Alibaba Cloud Linux 3）