《妙趣横生的算法》(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

相关文章

Spring Security自定义身份认证的实现方法

《SpringSecurity自定义身份认证的实现方法》:本文主要介绍SpringSecurity自定义身份认证的实现方法,下面对SpringSecurity的这三种自定义身份认证进行详细讲解,... 目录1.内存身份认证(1)创建配置类(2)验证内存身份认证2.JDBC身份认证(1)数据准备 (2)配置依

利用python实现对excel文件进行加密

《利用python实现对excel文件进行加密》由于文件内容的私密性,需要对Excel文件进行加密,保护文件以免给第三方看到,本文将以Python语言为例,和大家讲讲如何对Excel文件进行加密,感兴... 目录前言方法一:使用pywin32库(仅限Windows)方法二:使用msoffcrypto-too

C#使用StackExchange.Redis实现分布式锁的两种方式介绍

《C#使用StackExchange.Redis实现分布式锁的两种方式介绍》分布式锁在集群的架构中发挥着重要的作用,:本文主要介绍C#使用StackExchange.Redis实现分布式锁的... 目录自定义分布式锁获取锁释放锁自动续期StackExchange.Redis分布式锁获取锁释放锁自动续期分布式

springboot使用Scheduling实现动态增删启停定时任务教程

《springboot使用Scheduling实现动态增删启停定时任务教程》:本文主要介绍springboot使用Scheduling实现动态增删启停定时任务教程,具有很好的参考价值,希望对大家有... 目录1、配置定时任务需要的线程池2、创建ScheduledFuture的包装类3、注册定时任务,增加、删

SpringBoot整合mybatisPlus实现批量插入并获取ID详解

《SpringBoot整合mybatisPlus实现批量插入并获取ID详解》这篇文章主要为大家详细介绍了SpringBoot如何整合mybatisPlus实现批量插入并获取ID,文中的示例代码讲解详细... 目录【1】saveBATch(一万条数据总耗时:2478ms)【2】集合方式foreach(一万条数

使用Python实现矢量路径的压缩、解压与可视化

《使用Python实现矢量路径的压缩、解压与可视化》在图形设计和Web开发中,矢量路径数据的高效存储与传输至关重要,本文将通过一个Python示例,展示如何将复杂的矢量路径命令序列压缩为JSON格式,... 目录引言核心功能概述1. 路径命令解析2. 路径数据压缩3. 路径数据解压4. 可视化代码实现详解1

python获取网页表格的多种方法汇总

《python获取网页表格的多种方法汇总》我们在网页上看到很多的表格,如果要获取里面的数据或者转化成其他格式,就需要将表格获取下来并进行整理,在Python中,获取网页表格的方法有多种,下面就跟随小编... 目录1. 使用Pandas的read_html2. 使用BeautifulSoup和pandas3.

PyQt6/PySide6中QTableView类的实现

《PyQt6/PySide6中QTableView类的实现》本文主要介绍了PyQt6/PySide6中QTableView类的实现,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学... 目录1. 基本概念2. 创建 QTableView 实例3. QTableView 的常用属性和方法

PyQt6/PySide6中QTreeView类的实现

《PyQt6/PySide6中QTreeView类的实现》QTreeView是PyQt6或PySide6库中用于显示分层数据的控件,本文主要介绍了PyQt6/PySide6中QTreeView类的实现... 目录1. 基本概念2. 创建 QTreeView 实例3. QTreeView 的常用属性和方法属性

Android使用ImageView.ScaleType实现图片的缩放与裁剪功能

《Android使用ImageView.ScaleType实现图片的缩放与裁剪功能》ImageView是最常用的控件之一,它用于展示各种类型的图片,为了能够根据需求调整图片的显示效果,Android提... 目录什么是 ImageView.ScaleType?FIT_XYFIT_STARTFIT_CENTE