猪脚说第七期

猪脚说第七期

Diandian funny boy
  2023-07-14 20:46:14 2023-07-14 20:46:14 Created   2023-07-14 20:50:33 2023-07-14 20:50:33 Updated    2.9k Words  13 Mins  

老规矩：若针对这些题目，同学们有更好更简洁的方法，欢迎来找助教讨论，助教请喝奶茶😍😍。

连续线段

此题使用链表和数组的解法各有优劣。有些同学在写代码时容易默认输入的点是按x坐标顺序输入的，但其实不然，因此在后续for循环判断时第一层变量为i,第二层变量为j = i + 1，这样就忽略了可能在该线段之前的线段中存在相连的可能性。因此一种实用的做法为先对输入的所有点进行排序，这样在后续判断时也更有逻辑。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
#include <stdio.h>
#include <stdlib.h>
struct node{
    int x1;
    int x2;
    int y1;
    int y2;
}line[201];//所有线段的点都存储在结构体数组中
int cmp(const void * a, const void * b){
    struct node* e1 = (struct node *)a;
    struct node* e2 = (struct node *)b;
    if(e1->x1 > e2->x1)
        return 1;
    else if(e1->x1 < e2->x1)
        return -1;
    else
        return 0;
}
int main() {
    int x3=0, y3=0;//x3和y3存储当前需要判断是否能连接的点
    int i, j, n, count[201]={0}, ans=-1;
    scanf("%d", &n);
    for(i = 0; i < n; i++)
        scanf("%d %d %d %d", &line[i].x1, &line[i].y1, &line[i].x2, &line[i].y2);
    qsort(line, n, sizeof(struct node), cmp);//将输入的线段按照左端点横坐标排序
    for(i = 0; i < n; i++){
        x3 = line[i].x2;
        y3 = line[i].y2;
        for(j = i + 1; j < n; j++){
            if(line[j].x1 == x3 && line[j].y1 == y3){
                count[i]++;
                x3=line[j].x2;
                y3=line[j].y2;
            }
        }
    }//因为已经排好序，所以直接顺位判断是否能连接，能连接则count++
    j=0;
    for(i=0;i<n;i++){
        if(count[i]>ans){
            ans=count[i];
            j=i;
        }
    }//找到最大的count，该循环为经典的寻找最大值or最小值的方法
    printf("%d %d %d\n", ans+1, line[j].x1, line[j].y1);
    return 0;
}

空闲空间申请模拟（最佳适应）

该题的题面较长，大家一定要看清楚每一个要求，踩坑的地方包括但不限于：

1、找不到足够大的空闲快，则什么操作都不发生；

2、并不是简单地寻找到空间恰好相等的节点，而是遍历一圈找到满足要求的空间最小的节点进行操作；

3、在删除节点时如果使用free()函数，则一定要保证这个空间后续不会再被使用；

4、一定要注意！不能访问到空指针。形如if(p->length!=0 && p != NULL)的形式仍是不可以的，因为p如果是空指针，逻辑上if条件确实不会成立，但仍存在p->length!=0的判断，这样就访问到了空指针。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
#include <stdio.h>
#include <stdlib.h>
struct node{
    int address;
    int length;
    struct node *next;
}dot[512];
int main() {
    int i, j, n, op, min, flag;
    struct node *p, *q, *r, *r_be, *now;
    scanf("%d", &n);
    scanf("%d %d", &dot[0].address, &dot[0].length);
    for(i = 1; i < n; i++){
        scanf("%d %d", &dot[i].address, &dot[i].length);
        dot[i-1].next = (struct node*)malloc(sizeof(struct node));
        dot[i-1].next = &dot[i];
    }//每次输入的时候，让前一节点的next指向当前节点，因此需先输入第0个节点
    now = dot[n-1].next = &dot[0];//将物理意义上的最后一个节点与第一个节点相连
    q = &dot[n-1];
    while((scanf("%d", &op))!=EOF){
        r = (struct node*)malloc(sizeof(struct node));
        r_be = (struct node*)malloc(sizeof(struct node));
        if(op == -1)
            break;
        else{
            flag = 0;
            p = now;
            for(q = p; q->next != p; q = q->next);
            min = 999999;//“新的开始”，每次进循环为min赋初值为一个较大的数
            do{
                if(p->length>=op && p->length < min){
                    r = p;
                    r_be = q;
                    min = p->length;
                    flag = 1;
                }
                q = p;
                p = p->next;
            }while(p != now);//do-while循环结构可以有效循环遍历一圈，因为其先执行操作再判断
            if(flag == 1){
                if(r->length > op){
                    r->length -= op;
                    now = r;
                }
                else if(r->length == op){
                    r->length = 0;
                    if(r->next != r){
                        now = r->next;
                        r_be->next = r->next;
                    }
                    else{
                        now = NULL;
                    }//特判：如果当前只剩一个节点，则直接让这个节点为NULL
                }
            }
        }
    }
    p = now;
    do{
        if(p == NULL)
            break;//特判：如果当前节点已为空，相当于全部删除完，什么都不输出
        else{
            printf("%d %d\n", p->address, p->length);
            p = p->next;
        }
    }while(p != now);
    return 0;
}

多项式相乘

本题需要注意：

1、链表与数组均可解决此问题，各有优劣；

2、注意数据范围，应用long long存储指数和系数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
#include <stdio.h>
#include <stdlib.h>
struct duo{
    long long xi;
    long long zhi;
}a[81], b[81], ans[6561];
int cmp(const void *a, const void *b){
    struct duo* ia = (struct duo*)a;
    struct duo* ib = (struct duo*)b;
    if((ia->zhi < ib->zhi) || ((ia->zhi == ib->zhi) && (ia->xi > ib->xi)))
        return 1;
    else
        return -1;
}//按照指数从大到小排列，若指数相同，则系数从小到大排列
int main() {
    int i=0, j=0, k=0, i1, j1, k1;
    char c1, c2;
    while(1){
        scanf("%lld %lld", &a[i].xi, &a[i].zhi);
        c1 = getchar();
        i++;
        if(c1 == '\n')
            break;
    }//用此种方法可以实现换行时结束读入，且\n与\r\n都可，请大家自己思考为什么
    while(1){
        scanf("%lld %lld", &b[j].xi, &b[j].zhi);
        c2 = getchar();
        j++;
        if(c2 == '\n')
            break;
    }
    i1 = i;
    j1 = j;
    for(i = 0; i < i1; i++){
        for(j = 0; j < j1; j++){
            ans[k].xi = a[i].xi * b[j].xi;
            ans[k].zhi = a[i].zhi + b[j].zhi;
            k++;
        }
    }//多项式相乘法则
    k1 = k;
    qsort(ans, k1, sizeof(struct duo), cmp);//排序，排完序后肯定会有指数相同的相邻项
    for(i = 0; i < k1; i++){
        for(j = 1; (j < k1) && (i + j < k1); j++){
            if(ans[i+j].zhi == ans[i].zhi){
                ans[i].xi += ans[i+j].xi;
                ans[i+j].zhi = 0;
            }
            else
                break;
            }
    }//消除指数相同的项，系数全部相加
    for(i = 0; i < k1 - 1; i++){
        if(ans[i].zhi != 0)
            printf("%lld %lld ", ans[i].xi, ans[i].zhi);
    }
    printf("%lld %lld ", ans[k1-1].xi, ans[k1-1].zhi);//为防止全部都为0，最后必须输出一次
    return 0;
}

文件加密（环）

该题为本次作业的重重重灾区！问题主要出在：

1、对于输入的字符串没有预处理末尾的换行符，或者处理方式有问题，导致后面全部出错；

2、原密钥对应的最后一个字符的新密钥没有被赋值，导致最终密钥表缺失；

3、对链表的操作不熟悉，对于表头的使用、对于链表节点的插入、删除等操作出现问题；

4、使用野指针或访问空指针，定义局部指针时未初始化。

一些建议：

1、增加对链表的熟悉程度，插入、删除等操作可以自己总结成一个模版；

2、对于复杂的题目，模块化非常重要。自定义好各司其职的函数，main函数里保留逻辑部分；

3、调试方法与技巧！一定要善于使用printf函数进行打印调试。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
struct formation{
    char c;
    struct formation *link;
};
void del(char * b, char * c){
    int i=0, j=0, k=0;
    while(b[i] != '\0'){
        for(j = 0; j < k; j++){
            if(b[i]==c[j])
                break;
        }
        if(j==k)
            c[k++]=b[i];
        i++;
    }
}//对于输入的字符串b，删除其重复出现的字母，结果保存到c数组里
void sheet(char * b, char * c){
    char re[95]={0};
    int i, j, k=0, tmp[95]={0};
    del(b,c);
    j = (int)strlen(c);
    for(i = 0; i < j; i++)
        tmp[c[i]-' ']++;
    for(i = 0; i < 95; i++){
        if(tmp[i] == 0)
            re[k++] = i + ' ';
    }//将剩余的且未出现过的可见字符保存到re数组里
    strcat(c,re);//将re数组追加到c数组后，形成原密钥
}//对于输入的字符串b，形成原密钥c
void final(char * b){
    int i, j=0, k=0;
    struct formation *List = NULL, *p = NULL, *r = NULL;
    for (i = 0; i < 95; i++){
        r = (struct formation *)malloc(sizeof(struct formation));
        r->c = b[j++];
        if(List == NULL)
            List = p = r;
        else{
            p->link = r;
            p = p->link;
        }
    }
    p->link = List;//到此为止，循环链表已经建立
    r = p;
    p = p->link;
    k = p->c;
    while(p->link != p){
        r->link = p->link;
        j = p->c;
        free(p);
        p = (struct formation *)malloc(sizeof(struct formation));//free过后，记得再申请
        p = r->link;
        for(i = 1; i < j; i++, r=p, p=p->link);//只一条for语句，注意移动次数，便寻得所需节点
        b[j-32] = p->c;//建立该字符与原密钥的的字符的对应关系
    }
    b[p->c -32] = k;//最后剩下的字符的密文为原密钥的第一个字符
}//将原密钥b进行处理，形成密钥表，依旧保存到b中
int main() {
    char s[33]={0}, pre[95]={0}, c;
    FILE *in = fopen("in.txt", "r");
    FILE *out = fopen("in_crpyt.txt", "w");
    gets(s);
    sheet(s, pre);
    final(pre);//逻辑部分在main函数里实现，具体操作可适当封装成函数，这样调试起来也方便发现错误
    while ((c = fgetc(in)) != EOF){
        if(c>=32 && c<=126)
            fputc(pre[c-32], out);
        else
            fputc(c, out);
    }//注意不可见字符要原样输出！
    fclose(in);
    fclose(out);
    return 0;
}

词频统计（数组或链表实现）

本题使用数组或链表都是可以做的，但个人认为数组会更简洁。需要注意的是，题目中明确说明单词仅为有字母组成的字符序列，但并没有说单词与单词之间一定由空格隔开，不能只看样例而轻下论断，因此使用fscanf读取单词肯定是会出问题的。

一些建议：当明确地需要执行排序操作时，数组比链表更为简洁。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>
struct node{
    char word[51];
    int count;
}wordlist[512];
int cmp(const void * a, const void *b){
    struct node *e1 = (struct node*)a;
    struct node *e2 = (struct node*)b;
    return strcmp(e1->word,e2->word);
}
int main(){
    char table[5120]={0}, c;
    FILE *in = fopen("article.txt","r");
    int i=0, j, k, len, total=0;
    while((c = fgetc(in)) != EOF)
        table[i++] = c;//将文件中所有字符读进一个字符串数组
    len = i;
    for(i = 0; i < len;){
        if(!isalpha(table[i]))//如果不是字母
            i++;
        else{
            j = 0;//“新的开始”，每次需要加入新的单词时，给j赋初值为0
            while(isalpha(table[i])){
                if(islower(table[i]))//如果是小写字母
                    wordlist[total].word[j++] = table[i];
                else if(isupper(table[i]))//如果是大写字母
                    wordlist[total].word[j++] = table[i] + 32;
                i++;
            }
            wordlist[total].word[j] = '\0';//最后一定要加上'\0'
            wordlist[total].count = 1;//让该单词的出现次数为1
            for(k = 0; k < total; k++){
                if(strcmp(wordlist[k].word,wordlist[total].word) == 0){
                    wordlist[k].count++;
                    break;
                }
            }//立即在已有的字母表中查找，若存在，则total维持原值，且对应单词count++
            if(k == total)
                total++;//若该单词不存在于现有单词表中，total++，表示将其加入单词表
        }
    }
    qsort(wordlist, total, sizeof(struct node), cmp);//按照字典序排序
    for(i = 0; i < total; i++)
        printf("%s %d\n", wordlist[i].word, wordlist[i].count);
    fclose(in);
    return 0;
}

Author: diandian, Riccardo

  • Title: 猪脚说第七期
  • Author: Diandian
  • Created at : 2023-07-14 20:46:14
  • Updated at : 2023-07-14 20:50:33
  • Link: https://cutedian.github.io/2023/07/14/猪脚说第七期/
  • License: This work is licensed under CC BY-NC-SA 4.0.
推荐阅读
猪脚说第十五期 猪脚说第十五期 猪脚说第五期 猪脚说第五期 猪脚说第十二期 猪脚说第十二期
推荐阅读
猪脚说第十五期 猪脚说第十五期 猪脚说第五期 猪脚说第五期
Comments
On this page
猪脚说第七期
  1. 1. 连续线段
  2. 2. 空闲空间申请模拟（最佳适应）
  3. 3. 多项式相乘
  4. 4. 文件加密（环）
  5. 5. 词频统计（数组或链表实现）