西农OJ 2021阶段二考试
Problem A 用一维动态数组实现杨辉三角形
unsigned int *createline(unsigned int *p, int line){
unsigned int * thisline = p+line*(line-1)/2; /* 指向当前行的首地址*/
unsigned int * brforeline = p+(line-1)*(line-2)/2; /* 指向前一行的首地址*/
/* 第一个和最后一个为1 */
*thisline = 1;
*(thisline+line-1) = 1;
/* 计算中间的部分 */
int i;
for(i = 1; i < line-1; i++){
*(thisline+i) = *(brforeline+i-1)+*(brforeline+i);
}
/* 返回当前行首地址 */
return thisline;
}
Problem B 二维数组调整
首先观察函数原型
int Find_Min(int *, int n); // 返回最小值下标
int Find_Max(int *, int n); // 返回最大值下标
void Adjust_Arr(int **, int, int); // 调整数组
void Swap(int *, int, int (*)(int *, int), int (*)(int *, int)); // 交换最大和最小值(参数表: 数组,数组规模,两个函数指针[传Find_Min和Find_Max])
其中Find_Min和Find_Max已经写好了,只需要写Adjust_Arr和Swap函数
Adjust_Arr函数
函数分析
编写
Adjust_Arr函数，对动态二维数组中的每一行做数据位置调整。将偶数行(行号从0开始，并计作偶数行）中最大元素与最前一个元素做交换，最小元素与最后一个元素做交换，使偶数行中最大元素在最前，最小元素在最后；将奇数行中最小元素与最前一个元素做交换，最大元素与最后一个元素做交换，使奇数行中最小元素在最前，最大元素在最后。
提取重要信息:
-
行号从0开始，并计作偶数行
-
使偶数行中最大元素在最前，最小元素在最后
-
使奇数行中最小元素在最前，最大元素在最后
函数原型
void Adjust_Arr(int **p, int m, int n);
- p 是二维数组的首地址
- m 为行数
- n 为列数
函数设计
- 设计循环, 循环每一行
- 奇数偶数行判断
- 使用
Swap()交换,Swap()中传入Find_Min()和Find_Max()( 或Find_Max()和Find_Min(), 这个要根据奇数偶数行进行区别 )
代码
void Adjust_Arr(int **p, int m, int n){
int i;
for(i = 0; i < m; i++){
if(i % 2 == 0){
/*
偶数行
Find1 = Find_Max
Find2 = Find_Min
*/
Swap(*(p+i),n,&Find_Max,&Find_Min);
}else{
/*
奇数行
Find1 = Find_Min
Find2 = Find_Max
*/
Swap(*(p+i),n,&Find_Min,&Find_Max);
}
}
}
Swap函数
函数分析
题目中没有这个函数的具体说明, 需要自己设计. 根据目前 Adjust_Arr函数的设计, 需要在 Swap 中实现以下功能:
- 使用函数传入的
Find1()和Find2()找下标- 两个Find具体是哪个, 在
Adjust_Arr函数中传入. 根据奇数偶数行进行区别. - 建议先找到最大值[/最小值], 交换. 再找到最小值[/最大值], 交换.
- 两个Find具体是哪个, 在
函数原型
void Swap(int *p, int n, int (*Find1)(int *, int), int (*Find2)(int *, int));
- p 是一维数组的首地址
- n 为数组规模
- 两个函数指针参数, 这里规定传入
代码
void Swap(int *p, int n, int (*Find1)(int *, int), int (*Find2)(int *, int)){
/*
两次交换
第一次是 [最大/最小] 与第一个元素交换
第二次是 [最小/最大] 与最后一个元素交换
*/
int index = Find1(p,n);
int temp = *p;
*p = *(p+index);
*(p+index) = temp;
index = Find2(p,n);
temp = *(p+n-1);
*(p+n-1) = *(p+index);
*(p+index) = temp;
}
其他
如果没看懂题目给的 Swap 函数原型, 可以自己写别的 Swap 函数. 题目只是说提交Adjust_Arr()及其调用的除Find_Min()和Find_Max()之外的函数代码。
（甚至可以不用写这个 Swap 函数， 只要把Adjust_Arr()写对即可）
Problem C 三维点通用排序 [未解决]
selection_sort 函数
函数分析
对三位点, 按照[x/y/z], [升序/降序] 排序
函数原型
void selection_sort(Point *a, int n, char mode, AXIS ch)；
- a 要排序的三维点数组
- n 数组规模
- mode 排序模式[升序D/降序A]
- ch 按[x/y/z]排序
代码
没写出来 TvT
应该是排序方法的问题, 还有归并和快速排序没试
这是OJ的错误提示(选择排序)
========[11.out]=========
Your:
5 4 1
9 3 2
2 7 4
7 8 5
2 3 6
1 5 6
5 6 8
4 8 9
---------------------
Right:
5 4 1
9 3 2
2 7 4
7 8 5
1 5 6
2 3 6
5 6 8
4 8 9
====================
这是OJ的错误提示(冒泡排序)
========[3.out]=========
Your:
-2 0 0
0 1 2
1 2 3
3 2 1
4 6 5
---------------------
Right:
-2 0 0
0 1 2
3 2 1
1 2 3
4 6 5
====================
下面代码用的选择排序, 理论上是正确的, 但OJ会判错, 可以参考.
void selection_sort(Point *a, int n, char mode, AXIS ch){
CallBack Compare = setmode(mode);
int isSwap = 0; /* 是否需要交换 */
int i,j;
for(j = 0; j < n; j++){
for(i = j+1; i < n; i++){
/* 判断是否需要交换 */
if(ch == XAXIS){
isSwap = !Compare((a+j)->x,(a+i)->x);
}else if(ch == YAXIS){
isSwap = !Compare((a+j)->y,(a+i)->y);
}else{
isSwap = !Compare((a+j)->z,(a+i)->z);
}
/* 交换 */
if(isSwap){
Point temp;
temp = *(a+j);
*(a+j) = *(a+i);
*(a+i) = temp;
}
}
}
}
下面代码用的冒泡排序, 理论上是正确的, 但OJ会判错, 可以参考.
void selection_sort(Point *a, int n, char mode, AXIS ch){
CallBack Compare = setmode(mode);
int isSwap = 0; /* 是否需要交换 */
int i,j;
for(j = 0; j < n-1; j++){
for(i = 0; i < n-1-j; i++){
/* 判断是否需要交换 */
if(ch == XAXIS){
isSwap = !Compare((a+i)->x,(a+i+1)->x);
}else if(ch == YAXIS){
isSwap = !Compare((a+i)->y,(a+i+1)->y);
}else{
isSwap = !Compare((a+i)->z,(a+i+1)->z);
}
/* 交换 */
if(isSwap){
Point temp;
temp = *(a+i);
*(a+i) = *(a+i+1);
*(a+i+1) = temp;
}
}
}
}
下面这个代码我没看见要用回调函数. 可以参考.
void selection_sort(Point *a, int n, char mode, AXIS ch){
int isSwap = 0; /* 是否需要交换 */
int i,j;
for(j = 0; j < n-1; j++){
for(i = 0; i < n-1-j; i++){
/* 先按降序判断是否需要交换 */
if(ch == XAXIS){
isSwap = !compareA((a+i)->x,(a+i+1)->x);
}else if(ch == YAXIS){
isSwap = !compareA((a+i)->y,(a+i+1)->y);
}else{
isSwap = !compareA((a+i)->z,(a+i+1)->z);
}
if(mode == 'D'){
/* 如果是mode是升序,则取反 */
isSwap = !isSwap;
}
/* 交换 */
if(isSwap){
Point temp;
temp = *(a+i);
*(a+i) = *(a+i+1);
*(a+i+1) = temp;
}
}
}
}
Problem D 表情串转换
int convert(char *dst, char mode){
if(mode == 's'){
dst[0] = '^';
dst[1] = '_';
dst[2] = '^';
}else if(mode == 'f'){
dst[0] = '@';
dst[1] = '_';
dst[2] = '@';
}else if(mode == 'c'){
dst[0] = 'T';
dst[1] = '_';
dst[2] = 'T';
}else if(mode == 'z'){
dst[0] = '^';
dst[1] = '_';
dst[2] = '~';
}
}
int ConvertEmoji(char **dst, const char *src){
/* 计算新字符串的大小 */
int newLength = strlen(src);
int i,j;
for(i = 0; i < strlen(src); i++){
if(src[i] == '/'){
if(src[i+1] == 's') newLength++;
if(src[i+1] == 'f') newLength++;
if(src[i+1] == 'c') newLength++;
if(src[i+1] == 'z') newLength++;
}
}
/* 给新字符串分配空间 */
*dst = (char*)malloc(sizeof(char)*(newLength+1));
/* 转化, i 表示原字符串的索引, j 表示新字符串的索引 */
for(i = 0, j = 0; j < newLength; j++, i++){
(*dst)[j] = src[i];
if(src[i] == '/'){
if(src[i+1]=='s')
{
convert(&(*dst)[j],'s');
i += 1;
j += 2;
}
else if(src[i+1]=='f')
{
convert(&(*dst)[j],'f');
i += 1;
j += 2;
}
else if(src[i+1]=='c')
{
convert(&(*dst)[j],'c');
i += 1;
j += 2;
}
else if(src[i+1]=='z')
{
convert(&(*dst)[j],'z');
i += 1;
j += 2;
}
}
}
if(newLength == 1) newLength = 0;
return newLength;
}
Problem E 学生信息组合排序
int ReadFile(PStudent a, int start, int end)
{
FILE *fp;
PStudent t = (PStudent) malloc(start * sizeof(Student));
int i = 0, len;
fp = fopen(FileName, "r");
while (i < start) {
fread(t, sizeof(Student), 1, fp);
i++;
}
len = fread(a, sizeof(Student), end - start + 1, fp);
fclose(fp);
return len;
}
void Print(PStudent a, int len)
{
int i;
/* 请不要修改输出格式相关的内容 */
printf(" 学号 | 姓名 | 身份证 | 成绩 |排名\n");
printf("----------------------------------------------------\n");
for (i = 0; i < len; i++)
printf("%10s|%-8s|%18s|%6.2f|%3d\n", a[i].Sno, a[i].Name,
a[i].Id, a[i].Score, a[i].Ranking);
printf("----------------------------------------------------\n");
}
int Compare(const void *a, const void *b){
PStudent StuA = (Student*)a;
PStudent StuB = (Student*)b;
if(StuA->Score != StuB->Score){
return StuA->Score>StuB->Score?-1:1;
}else{
int i;
for(i = 6; i <= 13; i++){
if(StuA->Id[i] != StuB->Id[i]){
return StuA->Id[i]<StuB->Id[i]?-1:1;
}
}
}
}
void OrderStu(PStudent stu_array, int len){
qsort(stu_array, len, sizeof(Student), Compare);
}