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

简介: 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);
}


相关文章
|
15天前
|
C语言
【数据结构】栈和队列(c语言实现)(附源码)
本文介绍了栈和队列两种数据结构。栈是一种只能在一端进行插入和删除操作的线性表,遵循“先进后出”原则;队列则在一端插入、另一端删除,遵循“先进先出”原则。文章详细讲解了栈和队列的结构定义、方法声明及实现,并提供了完整的代码示例。栈和队列在实际应用中非常广泛,如二叉树的层序遍历和快速排序的非递归实现等。
90 9
|
8天前
|
搜索推荐 C语言
【排序算法】快速排序升级版--三路快排详解 + 实现(c语言)
本文介绍了快速排序的升级版——三路快排。传统快速排序在处理大量相同元素时效率较低,而三路快排通过将数组分为三部分(小于、等于、大于基准值)来优化这一问题。文章详细讲解了三路快排的实现步骤,并提供了完整的代码示例。
32 4
|
29天前
|
存储 算法 C语言
通义灵码在考研C语言和数据结构中的应用实践 1-5
通义灵码在考研C语言和数据结构中的应用实践,体验通义灵码的强大思路。《趣学C语言和数据结构100例》精选了五个经典问题及其解决方案,包括求最大公约数和最小公倍数、统计字符类型、求特殊数列和、计算阶乘和双阶乘、以及求斐波那契数列的前20项和。通过这些实例,帮助读者掌握C语言的基本语法和常用算法,提升编程能力。
60 4
|
19天前
|
存储 算法 数据管理
C语言算法复杂度
【10月更文挑战第20天】
C语言算法复杂度
|
14天前
|
存储 搜索推荐 算法
【数据结构】树型结构详解 + 堆的实现(c语言)(附源码)
本文介绍了树和二叉树的基本概念及结构,重点讲解了堆这一重要的数据结构。堆是一种特殊的完全二叉树,常用于实现优先队列和高效的排序算法(如堆排序)。文章详细描述了堆的性质、存储方式及其实现方法,包括插入、删除和取堆顶数据等操作的具体实现。通过这些内容,读者可以全面了解堆的原理和应用。
57 16
|
10天前
|
搜索推荐 算法 C语言
【排序算法】八大排序(上)(c语言实现)(附源码)
本文介绍了四种常见的排序算法:冒泡排序、选择排序、插入排序和希尔排序。通过具体的代码实现和测试数据,详细解释了每种算法的工作原理和性能特点。冒泡排序通过不断交换相邻元素来排序,选择排序通过选择最小元素进行交换,插入排序通过逐步插入元素到已排序部分,而希尔排序则是插入排序的改进版,通过预排序使数据更接近有序,从而提高效率。文章最后总结了这四种算法的空间和时间复杂度,以及它们的稳定性。
51 8
|
10天前
|
搜索推荐 算法 C语言
【排序算法】八大排序(下)(c语言实现)(附源码)
本文继续学习并实现了八大排序算法中的后四种:堆排序、快速排序、归并排序和计数排序。详细介绍了每种排序算法的原理、步骤和代码实现,并通过测试数据展示了它们的性能表现。堆排序利用堆的特性进行排序,快速排序通过递归和多种划分方法实现高效排序,归并排序通过分治法将问题分解后再合并,计数排序则通过统计每个元素的出现次数实现非比较排序。最后,文章还对比了这些排序算法在处理一百万个整形数据时的运行时间,帮助读者了解不同算法的优劣。
39 7
|
14天前
|
C语言
【数据结构】二叉树(c语言)(附源码)
本文介绍了如何使用链式结构实现二叉树的基本功能,包括前序、中序、后序和层序遍历,统计节点个数和树的高度,查找节点,判断是否为完全二叉树,以及销毁二叉树。通过手动创建一棵二叉树,详细讲解了每个功能的实现方法和代码示例,帮助读者深入理解递归和数据结构的应用。
63 8
|
17天前
|
存储 C语言
【数据结构】手把手教你单链表(c语言)(附源码)
本文介绍了单链表的基本概念、结构定义及其实现方法。单链表是一种内存地址不连续但逻辑顺序连续的数据结构,每个节点包含数据域和指针域。文章详细讲解了单链表的常见操作,如头插、尾插、头删、尾删、查找、指定位置插入和删除等,并提供了完整的C语言代码示例。通过学习单链表,可以更好地理解数据结构的底层逻辑,提高编程能力。
44 4
|
18天前
|
存储 C语言
【数据结构】顺序表(c语言实现)(附源码)
本文介绍了线性表和顺序表的基本概念及其实现。线性表是一种有限序列,常见的线性表有顺序表、链表、栈、队列等。顺序表是一种基于连续内存地址存储数据的数据结构,其底层逻辑是数组。文章详细讲解了静态顺序表和动态顺序表的区别,并重点介绍了动态顺序表的实现,包括初始化、销毁、打印、增删查改等操作。最后,文章总结了顺序表的时间复杂度和局限性,并预告了后续关于链表的内容。
50 3