526互联

西农OJ 2021阶段二考试

发布时间 2023-08-20 16:22:20作者: OrzMiku

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 函数中传入. 根据奇数偶数行进行区别.
    • 建议先找到最大值[/最小值], 交换. 再找到最小值[/最大值], 交换.

函数原型

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);
}