首页 > 编程语言 > 详细

《程序设计基础》实验题目1 二维数组 冒泡排序

时间:2018-12-11 01:01:51      阅读:408      评论:0      收藏:0      [点我收藏+]

题目:编写函数,对于给定的二维整型数组,首先对每行从小到大排序,之后对每列从小到大排序;反复执 行上述排序过程,直到没有变动为止。注:作为实参的二维整型数组,每行元素个数不低于 3 且每列 元素个数不低于 4

算法分析:

1.      为方便传递参数,将二维数组存储为结构体Matrix,含有分量二维数组nums,行数line,列数column

  否则传递数组时还要带着行列两个int变量。

  另外也可以使函数更加简洁

2.      将排序分为三个函数 sort(总排序),sortLine(行排序),sortColumn(列排序)

行排序:用冒泡排序对每行分别进行排序,并用have_change变量记录是否有数据交换,若没有说明所有的行已经排好序,返回have_change=0;有数据交换返回have_change=1。列排序同理。

sort函数调用行排序和列排序函数,当它们的返回值都为0时,所有行列都不再有变动,即排好序。

  编程习惯改良:

 

  1. .   .    变量的命名:之前我都是习惯用xxx__aaa的形式,虽然含义明显但是冗长难以一眼看懂。这次函数变量的命名能短则短,能看懂就好。也需要适当有一些注释。vs右键重命名非常方便.
  2.          git代码库很方便的创建分支和回滚。

  完整代码:

  

  1 #include<stdio.h>
  2 #define MAX_LEN 20 //定义随机生成的二维数组的最大列(行)数 
  3 //为方便传参,将二维数组封装成矩阵结构体,nums储存二维数组,line为行数,column为列数
  4 typedef struct myMatrix {
  5     int** nums;
  6     int line;
  7     int column;
  8 } Matrix;
  9 //二重循环打印数组
 10 void showMartix(Matrix* matrix) {
 11     int line = matrix->line;
 12     int column = matrix->column;
 13     for (int i = 0; i < line; i++) {
 14         for (int j = 0; j < column; j++) {
 15             printf("%3d ", matrix->nums[i][j]);
 16         }
 17         printf("\n");
 18     }
 19 }
 20 //交换s1,s2
 21 void exchangeInt(int* s1, int* s2) {
 22 
 23     int temp = *s1;
 24     *s1 = *s2;
 25     *s2 = temp;
 26 }
 27 //从键盘键入数组
 28 void initMatrix(Matrix* matrix) {
 29     int line, column;
 30     printf("please input line num and column num,intervaled by space:\n");
 31     scanf("%d %d", &line, &column);
 32     matrix->line = line; matrix->column = column;
 33     matrix->nums=(int**)malloc(sizeof(int*)*line);
 34     for (int i = 0; i < line; i++)
 35         *(matrix->nums + i) = malloc(sizeof(int)*column);
 36     printf("please input nums by line:\n");
 37     for (int i = 0; i < line; i++) {
 38         for (int j = 0; j < column; j++) {
 39             scanf("%d", &matrix->nums[i][j]);
 40         }
 41     }
 42 }
 43 //随机生成一个二维数组
 44 void RandomInitMatrix(Matrix* matrix) {
 45     srand((int)time(NULL));
 46     //随机生成行数、列数,最大为MAX_LEN
 47     int line=rand()% MAX_LEN, column=rand()% MAX_LEN;
 48     matrix->line = line; matrix->column = column;
 49     //申请空间,并为各个元素随机赋值
 50     matrix->nums = (int**)malloc(sizeof(int*)*line);
 51     for (int i = 0; i < line; i++)
 52         *(matrix->nums + i) = malloc(sizeof(int)*column);
 53     for (int i = 0; i < line; i++) {
 54         for (int j = 0; j < column; j++) {
 55             matrix->nums[i][j]=rand()%100;
 56         }
 57     }
 58 }    
 59 //对每行进行冒泡排序,返回是否有排序(0,1)
 60 int sortLine(Matrix* matrix) {
 61     //记录是否本次排序中发生了数据交换
 62     int have_change=0;
 63     //对每行进行循环
 64     for (int i = 0; i < matrix->line; i++) {
 65         //对当前行进行冒泡排序
 66         //bound为边界,初始为最右边,边界逐渐左移到0
 67         int bound = matrix->column;
 68         while (bound != 0) {
 69             //记录最后交换的位置
 70             int last_change = 0;
 71             for (int j = 0; j < bound-1; j++) {
 72                 //如果出现反序对就进行数据交换
 73                 if (matrix->nums[i][j] > matrix->nums[i][j + 1]) {
 74                     exchangeInt(&matrix->nums[i][j], &matrix->nums[i][j + 1]);
 75                     have_change = 1;
 76                     last_change = j+1;
 77                 }
 78             }
 79             //边界更新为最后交换的位置,此边界后没有反序对,即已经排好序
 80             bound = last_change;
 81         }
 82     }
 83     return have_change;
 84 }
 85 //对每列进行冒泡排序,返回是否有排序(0,1)
 86 int sortColumn(Matrix* matrix) {
 87     //具体算法与行排序相似,不再重复
 88     int have_change = 0;
 89     for (int i = 0; i < matrix->column; i++) {
 90         int bound = matrix->line;
 91         while (bound != 0) {
 92             int last_change = 0;
 93             for (int j = 0; j < bound - 1; j++) {
 94                 if (matrix->nums[j][i] > matrix->nums[j+1][i]) {
 95                     exchangeInt(&matrix->nums[j][i], &matrix->nums[j+1][i]);
 96                     have_change = 1;
 97                     last_change = j + 1;
 98                 }
 99             }
100             bound = last_change;
101         }
102     }
103     return have_change;
104 }
105 //对二维数组排序
106 void sort(Matrix* matrix) {
107     //对每行每列循环排序直到行排序和列排序都不再有改动
108     while (sortLine(matrix) != 0 && sortColumn(matrix) != 0) {
109     }
110 }
111 
112 
113 int main() {
114     Matrix m;
115     RandomInitMatrix(&m);//测试用的二维数组是随机生成的,如需键盘键入可使用initMarix函数
116     printf("\n random Matrix before sorting:\n");
117     showMartix(&m);
118     sort(&m);
119     printf("\n sorted:\n");
120     showMartix(&m);
121     free(m.nums);
122 }

 

The end

 

 

 

《程序设计基础》实验题目1 二维数组 冒泡排序

原文:https://www.cnblogs.com/maxzheng/p/c_exam1.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!