赞
踩
目录
1.项目要求
2.定义模块函数
3.各模块函数实现
4.项目源代码
1.1 定义大小为 100 的整型数组,使用随机函数给数组元素赋值。
1.2 数组中的数值的范围为 0 - 100,数组中的元素不允许重复。
1.3 对数组中的元素使用冒泡排序进行排序。
2.1 主函数:main()
2.2 打印函数:Print_Ar()
2.3 初始化函数:Init_Ar()
2.4 冒泡排序函数:BubbleSort()
2.5 交换函数:Sweap_Int()
3.1 打印函数:Print_Ar()
①. 循环打印数组中的各元素,一行 10 个元素。
②. 源程序
/** 打印函数 */
void Print_Ar(int* br, int n)
{
assert(br != nullptr);
for (int i = 0; i < n; ++i)
{
printf("%4d ", br[i]);
if ((i + 1) % 10 == 0) // 一行打印 10 个元素
{
printf("\n");
}
}
printf("\n");
}
3.2 初始化函数:Init_Ar()
①. 思想:随机生成 100 个数值,数值范围为 0 - 100,存放到数组中。因调用查询函数进行查询是否有重复值,该算法时间复杂度较高,效率较低,故采用查表法。生成的数值即为表 table 的下标,表 table 初始值均为 0,如果当前下标表中没有存放数据,则将该随机数存放到数组中,然后将表中的 0 变为 1,说明已经存放数据。
②. 源程序
/** 初始化 生成随机数 */ void Init_Ar(int* br, int n) { assert(br != nullptr); /** 查表法 */ int i = 0; int table[ARSIZE + 1] = {}; // 新建表 table 范围 0 ... 100 表中数据均为为 0 while (i < n) { int tmp = rand() % RANDSIZE + 1; // 生成随机数 0 ... 100 if (table[tmp] == 0) // 如果当前下标表中没有存放数据 tmp 为 table 的下标 { br[i] = tmp; // 则将该随机数存放到数组中 ++i; table[tmp] = 1; // 将表中的 0 变为 1 说明已经存放数据 } } }
3.3 冒泡排序函数:BubbleSort()
①. 算法思想:冒泡排序 n 个元素比较 n - 1 趟,该趟中比较 n - i 次。若前面一个元素大于后面一个元素,则这两个元素进行交换。提前设标记 tag,如果需要交换则改变标记,如果不需要交换(即标记 tag 未改变),则退出当前循环,进行下一趟的比较,直到排序完成。
②. 源程序
/** 冒泡排序 */ void BubbleSort(int* br, int n) { assert(br != nullptr); // 断言机制 br 不为空 则继续执行下面代码 运行时检查 如果为假则不执行后面代码 for (int i = 1; i < n; ++i) // n 个数比较 n - 1 趟 { bool tag = true; // 标记 tag for (int j = 0; j < n - i; ++j) // 该趟中比较 n - i 次 { if (br[j] > br[j + 1]) // 若前面元素大于后面元素 则两两交换 { Sweap_Int(&br[j], &br[j + 1]); // 调用交换函数进行交换 tag = false; // 交换则改变标记 } } if (tag) // 如果不用交换(即标记 tag 未被改变)则退出当前循环 { break; } } }
3.4 交换函数:Sweap_Int()
①. 思想:交换函数进行交换,使用指针变量进行交换,调用交换函数时,改变指针所指向的值,可以实现交换。
②. 源程序
/** 交换函数 */
void Sweap_Int(int* ar, int* br)
{
assert(ar != nullptr && br != nullptr);
int tmp = *ar;
*ar = *br;
*br = tmp;
}
3.5 主函数:main()
/** 主函数 */
int main()
{
const int n = 100; // 常整型 只可读不可写
int ar[n] = {}; // 整型数组 ar 未初始化
Init_Ar(ar, n); // 调用初始化函数 生成随机数
printf("排序前:\n");
Print_Ar(ar, n);
BubbleSort(ar, n); // 调用排序函数 对生成的随机数进行排序
printf("排序后:\n");
Print_Ar(ar, n); // 调用打印函数 进行输出打印
return 0;
}
#include<stdio.h> #include<stdlib.h> #include<assert.h> /** * 要求: * 定义大小为 100 的整型数组 * 使用随机函数给数组元素赋值 数值范围为 0 - 100 不允许重复 * 并用冒泡排序进行排序 */ #define RANDSIZE 100 // 宏定义 随机数大小 100 #define ARSIZE 100 // 宏定义 数组大小 100 /** 交换函数 */ void Sweap_Int(int* ar, int* br) { assert(ar != nullptr && br != nullptr); int tmp = *ar; *ar = *br; *br = tmp; } /** 冒泡排序 */ void BubbleSort(int* br, int n) { assert(br != nullptr); // 断言机制 br 不为空 则继续执行下面代码 运行时检查 如果为假则不执行后面代码 for (int i = 1; i < n; ++i) // n 个数比较 n - 1 趟 { bool tag = true; // 标记 tag for (int j = 0; j < n - i; ++j) // 该趟中比较 n - i 次 { if (br[j] > br[j + 1]) // 若前面元素大于后面元素 则两两交换 { Sweap_Int(&br[j], &br[j + 1]); // 调用交换函数进行交换 tag = false; // 交换则改变标记 } } if (tag) // 如果不用交换(即标记 tag 未被改变)则退出当前循环 { break; } } } /** 查询函数 */ /** int FindValue(int* br, int n, int val) { assert(br != nullptr); int pos = -1; for (int i = 0; i < n; ++i) { if (br[i] == val) // 找到查询的值 { pos = i; // 当前下标 break; } } return pos; // 找到返回当前下标 没找到返回 -1 } */ /** 初始化 生成随机数 */ void Init_Ar(int* br, int n) { assert(br != nullptr); /** 代码改进 查表法 */ int i = 0; int table[ARSIZE + 1] = {}; // 新建表 table 范围 0 ... 100 表中数据均为为 0 while (i < n) { int tmp = rand() % RANDSIZE + 1; // 生成随机数 0 ... 100 if (table[tmp] == 0) // 如果当前下标表中没有存放数据 tmp 为 table 的下标 { br[i] = tmp; // 则将该随机数存放到数组中 ++i; table[tmp] = 1; // 将表中的 0 变为 1 说明已经存放数据 } } /** 时间复杂度较高 效率较低 int i = 0; while (i < n) { int tmp = rand() % RANDSIZE + 1; // 生成随机数 1 ... 100 //等价于 ==> *(br + i) = rand() % RANDSIZE + 1; if (FindValue(br, n, tmp) == -1) // 避免生成的随机数相同 没找到相同的值则将该值输入到数组里 { br[i] = tmp; ++i; } } */ } /** 打印函数 */ void Print_Ar(int* br, int n) { assert(br != nullptr); for (int i = 0; i < n; ++i) { printf("%4d ", br[i]); if ((i + 1) % 10 == 0) // 一行打印 10 个元素 { printf("\n"); } } printf("\n"); } /** 主函数 */ int main() { const int n = 100; // 常整型 只可读不可写 int ar[n] = {}; // 整型数组 ar 未初始化 Init_Ar(ar, n); // 调用初始化函数 生成随机数 printf("排序前:\n"); Print_Ar(ar, n); BubbleSort(ar, n); // 调用排序函数 对生成的随机数进行排序 printf("排序后:\n"); Print_Ar(ar, n); // 调用打印函数 进行输出打印 return 0; }
运行结果
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。