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

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

2023-10-13 81
版权
版权声明：
本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《 阿里云开发者社区用户服务协议》和 《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写 侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
简介： 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派小星
目录
相关文章
RossyYan
|
1月前
|
搜索推荐 C++
【C++数据结构——内排序】快速排序（头歌实践教学平台习题）【合集】
快速排序是一种高效的排序算法，基于分治策略。它的主要思想是通过选择一个基准元素（pivot），将数组划分成两部分。一部分的元素都小于等于基准元素，另一部分的元素都大于等于基准元素。然后对这两部分分别进行排序，最终使整个数组有序。(第一行是元素个数，第二行是待排序的原始关键字数据。本关任务：实现快速排序算法。开始你的任务吧，祝你成功！
RossyYan
41 7
c的前世今生
|
2月前
|
存储 算法 程序员
C 语言递归算法：以简洁代码驾驭复杂逻辑
C语言递归算法简介：通过简洁的代码实现复杂的逻辑处理，递归函数自我调用解决分层问题，高效而优雅。适用于树形结构遍历、数学计算等领域。
c的前世今生
106 7
龙大吉
|
3月前
|
机器学习/深度学习 算法 数据挖掘
C语言在机器学习中的应用及其重要性。C语言以其高效性、灵活性和可移植性，适合开发高性能的机器学习算法，尤其在底层算法实现、嵌入式系统和高性能计算中表现突出
本文探讨了C语言在机器学习中的应用及其重要性。C语言以其高效性、灵活性和可移植性，适合开发高性能的机器学习算法，尤其在底层算法实现、嵌入式系统和高性能计算中表现突出。文章还介绍了C语言在知名机器学习库中的作用，以及与Python等语言结合使用的案例，展望了其未来发展的挑战与机遇。
龙大吉
78 1
龙大吉
|
3月前
|
存储 缓存 算法
C语言在实现高效算法方面的特点与优势，包括高效性、灵活性、可移植性和底层访问能力
本文探讨了C语言在实现高效算法方面的特点与优势，包括高效性、灵活性、可移植性和底层访问能力。文章还分析了数据结构的选择与优化、算法设计的优化策略、内存管理和代码优化技巧，并通过实际案例展示了C语言在排序和图遍历算法中的高效实现。
龙大吉
74 2
土木林森
|
3月前
|
算法 数据处理 C语言
C语言中的位运算技巧，涵盖基本概念、应用场景、实用技巧及示例代码，并讨论了位运算的性能优势及其与其他数据结构和算法的结合
本文深入解析了C语言中的位运算技巧，涵盖基本概念、应用场景、实用技巧及示例代码，并讨论了位运算的性能优势及其与其他数据结构和算法的结合，旨在帮助读者掌握这一高效的数据处理方法。
土木林森
94 1
土木林森
|
3月前
|
并行计算 算法 测试技术
C语言因高效灵活被广泛应用于软件开发。本文探讨了优化C语言程序性能的策略，涵盖算法优化、代码结构优化、内存管理优化、编译器优化、数据结构优化、并行计算优化及性能测试与分析七个方面
C语言因高效灵活被广泛应用于软件开发。本文探讨了优化C语言程序性能的策略，涵盖算法优化、代码结构优化、内存管理优化、编译器优化、数据结构优化、并行计算优化及性能测试与分析七个方面，旨在通过综合策略提升程序性能，满足实际需求。
土木林森
99 1
XIAZHI
|
3月前
|
存储 算法 编译器
数据结构实验之矩阵的运算器（二维数组）
本实验旨在通过团队合作，掌握数组和矩阵相关运算的代码实现，包括矩阵的加减、数乘、转置、乘法、n次方及行列式的计算。实验过程中，成员们需分工协作，解决编程难题，最终实现一个功能完备的矩阵计算器。通过本实验，不仅锻炼了编程能力，还加深了对数学概念的理解，同时培养了团队合作精神。
XIAZHI
88 4
XIAZHI
|
3月前
|
机器学习/深度学习 存储 算法
数据结构实验之二叉树实验基础
本实验旨在掌握二叉树的基本特性和遍历算法，包括先序、中序、后序的递归与非递归遍历方法。通过编程实践，加深对二叉树结构的理解，学习如何计算二叉树的深度、叶子节点数等属性。实验内容涉及创建二叉树、实现各种遍历算法及求解特定节点数量。
XIAZHI
128 4
XIAZHI
|
3月前
数据结构实验之串模式匹配问题
本实验旨在掌握串模式匹配技术，通过创建文本文件、实现单词计数与定位功能，最终构建一个包含文件建立、单词统计与定位、程序退出等选项的主菜单，以增强对字符串处理的理解与应用能力。
XIAZHI
81 4
XIAZHI
|
3月前
|
存储 人工智能 算法
数据结构实验之C 语言的函数数组指针结构体知识
本实验旨在复习C语言中的函数、数组、指针、结构体与共用体等核心概念，并通过具体编程任务加深理解。任务包括输出100以内所有素数、逆序排列一维数组、查找二维数组中的鞍点、利用指针输出二维数组元素，以及使用结构体和共用体处理教师与学生信息。每个任务不仅强化了基本语法的应用，还涉及到了算法逻辑的设计与优化。实验结果显示，学生能够有效掌握并运用这些知识完成指定任务。
XIAZHI
81 4

热门文章

最新文章

  • 1
    图解前向、反向传播算法，一看就懂！
  • 2
    利用SVM(支持向量机)分类算法对鸢尾花数据集进行分类
  • 3
    近端策略优化(PPO)算法的理论基础与PyTorch代码详解
  • 4
    基于FPGA的图像双线性插值算法verilog实现,包括tb测试文件和MATLAB辅助验证
  • 5
    通过算法备案之后就万事大吉了么？
  • 6
    Transformer打破三十年数学猜想！Meta研究者用AI给出反例，算法杀手攻克数学难题
  • 7
    使用贪心算法解决最小生成树问题
  • 8
    【算法合规新时代】企业如何把握“清朗·网络平台算法典型问题治理”专项行动？
  • 9
    Java线程调度揭秘：从算法到策略，让你面试稳赢！
  • 10
    单纯接入第三方模型就无需算法备案了么？
  • 1
    c语言及数据结构实现简单贪吃蛇小游戏
    28
  • 2
    ##########对C语言文件初步认识与简介#########
    23
  • 3
    【02】客户端服务端C语言-go语言-web端PHP语言整合内容发布-优雅草网络设备监控系统-2月12日优雅草简化Centos stream8安装zabbix7教程-本搭建教程非docker搭建教程-优雅草solution
    54
  • 4
    【01】客户端服务端C语言-go语言-web端PHP语言整合内容发布-优雅草网络设备监控系统-硬件设备实时监控系统运营版发布-本产品基于企业级开源项目Zabbix深度二开-分步骤实现预计10篇合集-自营版
    22
  • 5
    数据结构（C语言）之对归并排序的介绍与理解
    36
  • 6
    【C语言程序设计——函数】分数数列求和2（头歌实践教学平台习题）【合集】
    37
  • 7
    【C语言程序设计——函数】分数数列求和1（头歌实践教学平台习题）【合集】
    20
  • 8
    【C语言程序设计——函数】递归求斐波那契数列的前n项（头歌实践教学平台习题）【合集】
    66
  • 9
    【C语言程序设计——函数】回文数判定（头歌实践教学平台习题）【合集】
    52
  • 10
    【C语言程序设计——循环程序设计】求解最大公约数（头歌实践教学平台习题）【合集】
    77

    • 相关课程

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

    • 相关电子书

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

    • 相关实验场景

    更多
  • 使用Swing算法实现商品推荐
  • RSA密码算法设计与实现
  • RSA非对称加密算法
  • 欧拉图的构造性证明与算法实现
  • 推荐系统入门之使用ALS算法实现打分预测
    • 下一篇
    阿里云oss简介和如何对接使用