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

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

2023-10-13 67
版权
版权声明：
本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《 阿里云开发者社区用户服务协议》和 《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写 侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
简介： 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语言数据结构
数据结构算法
C语言实验
海绵宝宝de派小星
目录
相关文章
java冯坚持
|
16天前
|
存储 人工智能 算法
数据结构与算法细节篇之最短路径问题：Dijkstra和Floyd算法详细描述，java语言实现。
这篇文章详细介绍了Dijkstra和Floyd算法，这两种算法分别用于解决单源和多源最短路径问题，并且提供了Java语言的实现代码。
java冯坚持
49 3
数据结构与算法细节篇之最短路径问题：Dijkstra和Floyd算法详细描述，java语言实现。
aliyun3611036241
|
11天前
|
存储 算法 C语言
通义灵码在考研C语言和数据结构中的应用实践 1-5
通义灵码在考研C语言和数据结构中的应用实践，体验通义灵码的强大思路。《趣学C语言和数据结构100例》精选了五个经典问题及其解决方案，包括求最大公约数和最小公倍数、统计字符类型、求特殊数列和、计算阶乘和双阶乘、以及求斐波那契数列的前20项和。通过这些实例，帮助读者掌握C语言的基本语法和常用算法，提升编程能力。
aliyun3611036241
49 4
ephemerals__
|
9天前
|
存储 编译器 C语言
【c语言】数组
本文介绍了数组的基本概念及一维和二维数组的创建、初始化、使用方法及其在内存中的存储形式。一维数组通过下标访问元素，支持初始化和动态输入输出。二维数组则通过行和列的下标访问元素，同样支持初始化和动态输入输出。此外，还简要介绍了C99标准中的变长数组，允许在运行时根据变量创建数组，但不能初始化。
ephemerals__
24 6
龙大吉
|
12天前
|
存储 算法 Java
Set接口及其主要实现类（如HashSet、TreeSet）如何通过特定数据结构和算法确保元素唯一性
Java Set因其“无重复”特性在集合框架中独树一帜。本文解析了Set接口及其主要实现类（如HashSet、TreeSet）如何通过特定数据结构和算法确保元素唯一性，并提供了最佳实践建议，包括选择合适的Set实现类和正确实现自定义对象的hashCode()与equals()方法。
龙大吉
29 4
c的前世今生
|
12天前
|
存储 算法 C语言
C语言：什么是指针数组，它有什么用
指针数组是C语言中一种特殊的数据结构，每个元素都是一个指针。它用于存储多个内存地址，方便对多个变量或数组进行操作，常用于字符串处理、动态内存分配等场景。
c的前世今生
20 3
c的前世今生
|
18天前
|
存储 人工智能 BI
C语言：数组的分类
C语言中的数组分为一维数组、多维数组和字符串数组。一维数组是最基本的形式，用于存储一系列相同类型的元素；多维数组则可以看作是一维数组的数组，常用于矩阵运算等场景；字符串数组则是以字符为元素的一维数组，专门用于处理文本数据。
c的前世今生
28 9
aliyun3611036241
|
11天前
|
存储 算法 C语言
【趣学C语言和数据结构100例】
《趣学C语言和数据结构100例》精选5个编程问题，涵盖求最大公约数与最小公倍数、字符统计、特殊序列求和及阶乘计算等，通过实例讲解C语言基础与算法思维，适合初学者实践学习。
aliyun3611036241
59 1
c的前世今生
|
16天前
|
存储 C语言
C语言：一维数组的不初始化、部分初始化、完全初始化的不同点
C语言中一维数组的初始化有三种情况：不初始化时，数组元素的值是随机的；部分初始化时，未指定的元素会被自动赋值为0；完全初始化时，所有元素都被赋予了初始值。
c的前世今生
19 2
白子寰
|
19天前
|
C语言
大学生期末C语言实验（学生成绩和鞍点）
大学生期末C语言实验（学生成绩和鞍点）
白子寰
105 0
大学生期末C语言实验（学生成绩和鞍点）
白子寰
|
19天前
|
C语言 C++
保姆式教学C语言——数组
保姆式教学C语言——数组
白子寰
15 0
保姆式教学C语言——数组

热门文章

最新文章

  • 1
    C语言编程入门之--第四章C语言基本数据类型
  • 2
    【C语言】学习笔记4——数组
  • 3
    C语言OJ项目参考(1034) 求值
  • 4
    C# Json处理日期和Table
  • 5
    C语言中的逗号操作符
  • 6
    c语言中常见错误总结
  • 7
    【C语言进阶】文件操作（一）
  • 8
    你应该知道的C语言干货(7)（对数组类指针的区别解析和使用）
  • 9
    【C语言进阶】最常用的库函数大全——从入门到精通 上
  • 10
    C语言数组和函数
  • 1
    【MongoDB】MongoDB 如何处理复杂的数据结构？
    128
  • 2
    【数据结构】排序算法
    45
  • 3
    【数据结构】C语言实现链队列(附完整运行代码)
    120
  • 4
    深入理解InnoDB索引数据结构和算法
    310
  • 5
    【数据结构】深入浅出理解链表中二级指针的应用
    98
  • 6
    【数据结构】线性表的链式存储结构
    64
  • 7
    【数据结构】C语言实现顺序表万字详解(附完整运行代码)
    147
  • 8
    【Redis技术进阶之路】「底层源码解析」揭秘高效存储模型与数据结构底层实现（字典）（二）
    112
  • 9
    作者推荐 |【Redis技术进阶之路】「原理系列开篇」揭秘高效存储模型与数据结构底层实现（SDS）（三）
    76
  • 10
    金石推荐 | 【算法数据结构专题】「延时队列算法」史上手把手教你针对层级时间轮（TimingWheel）实现延时队列的开发实战落地（下）（一）
    125

    • 相关课程

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

    • 相关电子书

    更多
  • 【云栖精选7月刊】抛开晦涩的算法、模型，让我们来谈谈互联网架构
  • 聚星台—客户运营核心大数据 与算法技术
  • Apache Flink 流式应用中状态的数据结构定义升级

    • 相关实验场景

    更多
  • 推荐系统入门之使用ALS算法实现打分预测
  • 欧拉图的构造性证明与算法实现
  • RSA密码算法设计与实现
  • RSA非对称加密算法
  • 使用Swing算法实现商品推荐
    • 下一篇
    在 BatchCompute 上玩转 Blender 渲染