《妙趣横生的算法》(C语言实现)-第2章 常用的查找与排序方法

2023-12-24 12:36

本文主要是介绍《妙趣横生的算法》(C语言实现)-第2章 常用的查找与排序方法,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

【实例2-1】一个结构体数组中存放的是学生记录,每条记录包括:学号、姓名、成绩。编写一个程序,要求输出1001编号同学的具体信息。

// 2-1 2023年12月23日18点05分-18点14分 
typedef struct student{ // 定义学生结构体类型 int id; // 学生编号char name[10]; // 学生姓名float score; // 学生成绩 
}Student;
int search(Student stu[], int n, int key)
{for (int i = 0; i < n; ++i) {if (stu[i].id == key) // 查找成功 return i;}return -1; // 查找失败 
}
# include <stdio.h>
int main()
{Student stu[4] = {{1004, "TOM", 100}, {1002, "LILY", 95}, {1001, "ANN", 93}, {1003, "LUCY", 98}}; // 初始化结构体数组// 顺序查找1001编号同学的具体信息int addr; // 要查找的记录的地址addr = search(stu, 4, 1001); printf("Student ID:   %d\n", stu[addr].id); // 输出查找到的记录的信息printf("Student name: %s\n", stu[addr].name); printf("Student score: %f\n", stu[addr].score);return 0;
} 

总结:顺序查找的优点在于简单直观,对于被查找的记录在文件中的排列顺序没有限制,因此比较适合顺序文件的查找。同时这种查找思想也适合于对顺序表数据结构和链表数据结构中的元素进行查找。它的缺点在于平均查找长度过大,查找效率低。逐个依次查找。
【实例2-2】折半查找数组中的元素。

// 2-2 2023年12月23日18点28分-
# include <stdio.h>
int bin_search(int A[], int n, int key)
{int low = 0, high = n - 1, mid;while (low <= high) {mid = (low + high) / 2; // 设置mid的值 if (A[mid] == key) {return mid; // 查找成功,返回mid}if (A[mid] < key) { low = mid + 1; // 在后半序列中查找 }if (A[mid] > key) {high = mid - 1; // 在前半序列中查找 }}return -1; // 查找失败,返回-1 
}
int main()
{int A[10] = {2, 3, 5, 7, 8, 10, 12, 15, 19, 21};printf("The contents of the array A[10] are\n");for (int i = 0; i < 10; ++i)printf("%d ", A[i]); // 显示数组A中的内容int n;printf("\nPlease input a integer for search\n");scanf("%d", & n); // 输入待查找的元素int addr = bin_search(A, 10, n); // 折半查找,返回该元素在数组中的下标if (-1 != addr)printf("%d is at the %dth unit in array A\n", n, addr + 1); // 查找成功 elseprintf("There is no %d in array A\n", n); // 查找失败 return 0;
}

总结:折半查找要考虑清楚上下界,是左闭右闭区间还是左闭右开区间。这和循环的终止条件有关。
【实例2-3】编写一个C程序,实现直接插入排序,要求从大到小排序,并输出排序后的数列元素。

// 2-3 2023年12月23日18点59分-19点09分 
void insertsort(int A[], int n)
{for (int i = 1; i < n; ++i) {int tmp = A[i]; // 将A[i]保存在临时变量tmp中int j = i - 1;while (j >= 0 && tmp > A[j]) { // 找到tmp的插入位置 A[j + 1] = A[j--]; // 将A[j]后移,再将j减1 }A[j + 1] = tmp; // 将元素tmp插入到指定位置,第i趟排序完成 }
}
# include <stdio.h> 
int main()
{int a[] = {-111, 2, 5, 6, 3, 7, 8, 0, 9, 12, 1}; // 初始化序列 printf("The original data array is\n");for (int i = 0; i < sizeof(a) / sizeof(int); ++i)printf("%d ", a[i]); // 显示原序列之中的元素 insertsort(a, sizeof(a) / sizeof(int)); // 插入排序 printf("\nThe result of insertion sorting for the array is\n");for (int i = 0; i < sizeof(a) / sizeof(int); ++i)printf("%d ", a[i]);return 0;
}

总结:插入排序,一个包含n个元素的序列,需要(n-1)趟排序,就可以使得这个序列有序。因为如果只包含一个元素肯定有序,如果包含两个及以上元素,那么就需要比较(n-1)次。
【实例2-4】编程实现选择排序,要求从大到小排序,并输出序列。

// 2-4 2023年12月23日19点22分-19点34分 
void selectionsort(int A[], int n) // 选择排序 
{for (int i = 0; i < n - 1; ++i) {int max = i;for (int j = i + 1; j < n; ++j) { // 在后(n-i)个元素中找到最大的元素位置 if (A[j] > A[max]) {max = j; // 用max记录下最大元素的位置 }}if (max != i) { // 如果最大的元素不位于后(n-i)个元素第1个 int tmp = A[max]; // 元素的交换 A[max] = A[i];A[i] = tmp;}}
} 
# include <stdio.h>
int main()
{int a[] = {-111, 2, 5, 6, 3, 7, 8, 0, 9, 12, 1}; // 初始化序列 printf("The original data array is\n");for (int i = 0; i < sizeof(a) / sizeof(int); ++i) {printf("%d ", a[i]); // 显示原序列的元素 }selectionsort(a, sizeof(a) / sizeof(int)); // 执行选择排序 printf("\nThe result of selection sort for the array is\n");for (int i = 0; i < sizeof(a) / sizeof(int); ++i) {printf("%d ", a[i]); // 输出排序后的结果 }return 0;
}

总结:选择排序,一个包含n个元素的序列需要(n-1)趟排序。每次找最小或者最大的元素放在前面位置。
【实例2-5】编写程序实现冒泡排序,要求从大到小排序并输出元素。

// 2-5 2023年12月23日19点42分-19点47分 
//void bubblesort(int A[], int n) // 冒泡排序 
//{
//    for (int i = n - 1; i > 0; --i) {
//        for (int j = 0; j < i; ++j) {
//            if (A[j] < A[j + 1]) {
//                int tmp = A[j];
//                A[j] = A[j + 1];
//                A[j + 1] = tmp;
//            }
//        }
//    }
//} 
void bubblesort(int A[], int n) // 改进的冒泡排序 
{int flg = 1;for (int i = n - 1; i > 0 && flg == 1; --i) {flg = 0;for (int j = 0; j < i; ++j) {if (A[j] < A[j + 1]) {int tmp = A[j];A[j] = A[j + 1];A[j + 1] = tmp;flg = 1; // 发生数据交换flg置1 }}}
} 
# include <stdio.h>
int main()
{int a[] = {-111, 2, 5, 6, 3, 7, 8, 0, 9, 12, 1}; // 初始化序列 printf("The original data array is\n");for (int i = 0; i < sizeof(a) / sizeof(int); ++i)printf("%d ", a[i]); // 显示原序列 bubblesort(a, sizeof(a) / sizeof(int)); // 执行冒泡排序 printf("\nThe result of bubble sort of this array is\n");for (int i = 0; i < sizeof(a) / sizeof(int); ++i)printf("%d ", a[i]); // 输出排序后的结果 return 0;
}

总结:冒泡排序,一个包含n个元素的序列需要(n-1)趟排序。每次确定了一个最大元素,冒泡冒出来的。改进后的冒泡排序算法可以减少排序时的比较次数,提高冒泡排序的效率。
【实例2-6】编写程序实现希尔排序。

// 2-6 2023年12月23日20点01分-20点10分
void shellsort(int A[], int n) // 希尔排序 
{int gap = n;int flg, j;while (gap > 1) {gap /= 2; // 增量缩小,每次减半do { // 子序列应用冒泡排序 flg = 0;for (int i = 1; i <= n - gap; ++i) {j = i + gap;if (A[i] < A[j]) {int tmp = A[i];A[i] = A[j];A[j] = tmp;flg = 1;}} } while (flg != 0); } 
} 
# include <stdio.h>
int main()
{int a[] = {-111, 2, 5, 6, 3, 7, 8, 0, 9, 12, 1}; // 初始化序列 printf("The original data array is\n");for (int i = 0; i < 10; ++i)printf("%d ", a[i+1]); // 显示原序列 shellsort(a, 10); // 执行希尔排序 printf("\nThe result of bubble sort of this array is\n");for (int i = 0; i < 10; ++i)printf("%d ", a[i+1]); // 输出排序后的结果 return 0;
}

【实例2-7】快速排序。

// 2-7 2023年12月23日20点13分-20点21分 
void swap(int * a, int * b) // 序列中元素位置的交换 
{int tmp = * a;* a = * b;* b = tmp;
}
void quicksort(int A[], int s, int t)
{if (s < t) {int i = s, j = t + 1;while (1) {do {++i;} while (!(A[s] >= A[i] || i == t)); // 重复执行++i操作do {--j;} while (!(A[s] <= A[j] || j == s)); // 重复执行--j操作if (i < j)swap(& A[i], & A[j]); // 交换位置elsebreak; }swap(& A[s], & A[j]); // 交换基准元素与A[j]的位置 quicksort(A, s, j - 1); // 递归排序基准元素前面的子序列 quicksort(A, j + 1, t); // 递归排序基准元素后面的子序列 }
}
# include <stdio.h>
int main()
{int a[] = {2, 5, 6, 3, 7, 8, 0, 9, 12, 1}; // 初始化序列 printf("The original data array is\n");for (int i = 0; i < sizeof(a) / sizeof(int); ++i) {printf("%d ", a[i]); // 显示原序列的元素 }quicksort(a, 0, sizeof(a) / sizeof(int) - 1); // 执行快速排序 printf("\nThe result of selection sort for the array is\n");for (int i = 0; i < sizeof(a) / sizeof(int); ++i) {printf("%d ", a[i]); // 输出排序后的结果 }return 0;
}

总结:这个程序有问题,尚在寻找中。

这篇关于《妙趣横生的算法》(C语言实现)-第2章 常用的查找与排序方法的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/531795

相关文章

SpringBoot3实现Gzip压缩优化的技术指南

《SpringBoot3实现Gzip压缩优化的技术指南》随着Web应用的用户量和数据量增加,网络带宽和页面加载速度逐渐成为瓶颈,为了减少数据传输量,提高用户体验,我们可以使用Gzip压缩HTTP响应,... 目录1、简述2、配置2.1 添加依赖2.2 配置 Gzip 压缩3、服务端应用4、前端应用4.1 N

Linux换行符的使用方法详解

《Linux换行符的使用方法详解》本文介绍了Linux中常用的换行符LF及其在文件中的表示,展示了如何使用sed命令替换换行符,并列举了与换行符处理相关的Linux命令,通过代码讲解的非常详细,需要的... 目录简介检测文件中的换行符使用 cat -A 查看换行符使用 od -c 检查字符换行符格式转换将

SpringBoot实现数据库读写分离的3种方法小结

《SpringBoot实现数据库读写分离的3种方法小结》为了提高系统的读写性能和可用性,读写分离是一种经典的数据库架构模式,在SpringBoot应用中,有多种方式可以实现数据库读写分离,本文将介绍三... 目录一、数据库读写分离概述二、方案一:基于AbstractRoutingDataSource实现动态

Python FastAPI+Celery+RabbitMQ实现分布式图片水印处理系统

《PythonFastAPI+Celery+RabbitMQ实现分布式图片水印处理系统》这篇文章主要为大家详细介绍了PythonFastAPI如何结合Celery以及RabbitMQ实现简单的分布式... 实现思路FastAPI 服务器Celery 任务队列RabbitMQ 作为消息代理定时任务处理完整

Java枚举类实现Key-Value映射的多种实现方式

《Java枚举类实现Key-Value映射的多种实现方式》在Java开发中,枚举(Enum)是一种特殊的类,本文将详细介绍Java枚举类实现key-value映射的多种方式,有需要的小伙伴可以根据需要... 目录前言一、基础实现方式1.1 为枚举添加属性和构造方法二、http://www.cppcns.co

使用Python实现快速搭建本地HTTP服务器

《使用Python实现快速搭建本地HTTP服务器》:本文主要介绍如何使用Python快速搭建本地HTTP服务器,轻松实现一键HTTP文件共享,同时结合二维码技术,让访问更简单,感兴趣的小伙伴可以了... 目录1. 概述2. 快速搭建 HTTP 文件共享服务2.1 核心思路2.2 代码实现2.3 代码解读3.

Java中的String.valueOf()和toString()方法区别小结

《Java中的String.valueOf()和toString()方法区别小结》字符串操作是开发者日常编程任务中不可或缺的一部分,转换为字符串是一种常见需求,其中最常见的就是String.value... 目录String.valueOf()方法方法定义方法实现使用示例使用场景toString()方法方法

Java中List的contains()方法的使用小结

《Java中List的contains()方法的使用小结》List的contains()方法用于检查列表中是否包含指定的元素,借助equals()方法进行判断,下面就来介绍Java中List的c... 目录详细展开1. 方法签名2. 工作原理3. 使用示例4. 注意事项总结结论:List 的 contain

MySQL双主搭建+keepalived高可用的实现

《MySQL双主搭建+keepalived高可用的实现》本文主要介绍了MySQL双主搭建+keepalived高可用的实现,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,... 目录一、测试环境准备二、主从搭建1.创建复制用户2.创建复制关系3.开启复制,确认复制是否成功4.同

Java实现文件图片的预览和下载功能

《Java实现文件图片的预览和下载功能》这篇文章主要为大家详细介绍了如何使用Java实现文件图片的预览和下载功能,文中的示例代码讲解详细,感兴趣的小伙伴可以跟随小编一起学习一下... Java实现文件(图片)的预览和下载 @ApiOperation("访问文件") @GetMapping("