一元多项式的求导

P.S. 最后一项还是输出空格了，没做实验题要求的最后一项后不输出空格
解决方法很简单：最后输出一个\b就解决了，即回退一个字符。

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 <iostream>  
  
struct Node {  
    int data, pow;  
    struct Node* next;  
};  
int len = 0;  
  
void insert(struct Node** head, int data, int pow) {  
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));  
    newNode->data = data;  
    newNode->pow = pow;  
    newNode->next = NULL;  
    len ++;  
    if (*head == NULL) {  
        *head = newNode;  
    }  
    else {  
        struct Node* temp = *head;  
        while (temp->next != NULL) {  
            temp = temp->next;  
        }  
        temp->next = newNode;  
    }  
}  
  
void browse(struct Node* head) {  
    struct Node* temp = head;  
    while (temp != NULL) {  
        if(temp -> pow)  
            printf("%d %d ", (temp->data)*(temp->pow), (temp->pow)-1);  
        else if(len == 1){  
            printf("0 0");  
        }  
        temp = temp->next;  
    }  
    puts("");  
}  
  
int main() {  
    struct Node* head = NULL;  
    int x, y;  
    while(std :: cin >> x >> y){  
        insert(&head, x, y);  
    }  
    browse(head);  
    return 0;  
}

时间复杂度 O(n^2)，主要是尾插法的时间复杂度，但是够用

还原二叉树

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
#include <stdio.h>  
#include <stdlib.h>  
#include <string.h>  
  
struct Node {  
    char data;  
    struct Node *left, *right;  
};  
  
int get_index(char *str, int start, int end, char value) {  
    for (int i = start; i <= end; i++) {  
        if (str[i] == value) {  
            return i;  
        }  
    }  
    return -1;  
}  
int pre_index = 0;  
Node* build_tree(char *inorder, char *preorder, int in_start, int in_end) {  
  
    if (in_start > in_end) {  
        return NULL;  
    }  
  
    Node *node = (Node*)malloc(sizeof(Node));  
    node->data = preorder[pre_index++];  
    node->left = node->right = NULL;  
  
    if (in_start == in_end) {  
        return node;  
    }  
  
    int in_index = get_index(inorder, in_start, in_end, node->data);  
    node->left = build_tree(inorder, preorder, in_start, in_index - 1);  
    node->right = build_tree(inorder, preorder, in_index + 1, in_end);  
    return node;  
}  
  
int max(int a, int b) {  
    return (a > b) ? a : b;  
}  
  
int depth(Node *node) {  
    if (node == NULL) {  
        return 0;  
    } else {  
        return max(depth(node->left), depth(node->right)) + 1;  
    }  
}  
  
int count(Node *node) {  
    if (node == NULL) {  
        return 0;  
    }
    else if (node->left == NULL && node->right == NULL) {  
        return 1;  
    }     
    else {  
        return count(node->left) + count(node->right);  
    }  
}  
  
int main() {  
    char inorder[256] = {0};char preorder[256]={0};  
    scanf("%s", preorder);  
    scanf("%s", inorder);  
    Node *root = build_tree(inorder, preorder, 0, strlen(inorder)-1);  
  
    printf("%d\n", depth(root));  
    printf("%d\n", count(root));  
  
    return 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
69
70
#include <stdio.h>  
#include <stdlib.h>  
#include <string.h>  
  
#define MAXN 105  
  
struct Edge {  
    int to, weight;  
    Edge* next;  
};  
  
struct qNode{  
    int point, length;  
};  
  
  
Edge* head[MAXN];  
int visited[MAXN];  
int n, m, ans;  
  
void addEdge(int u, int v, int w){  
    Edge* edge = (Edge*) malloc(sizeof(Edge));  
    edge->to = v;  
    edge->weight = w;  
    edge->next = head[u];  
    head[u] = edge;  
}  
  
void bfs(int start) {  
    qNode queue[MAXN];int front = 0, tail = 0;  
    queue[tail++] = {start, 0};  
    visited[start] = 1;  
    ans++;  
        while (front != tail) {  
        int u = queue[front].point;  
        int len = queue[front++].length;  
        for (Edge* e = head[u]; e != NULL; e = e->next) {  
            int v = e->to;  
            if (!visited[v] && len < 6) {  
                visited[v] = 1;  
                queue[tail++] = {v, len + 1};  
                ans++;  
            }  
        }  
    }  
}  
  
void work(){  
    for(int i = 1; i <= n ; i++){  
        memset(visited, 0, sizeof(visited));  
        ans = 0;  
        bfs(i);  
        printf("%d: %.2f%%\n", i, 100.0*ans/n );  
    }  
}  
  
int main() {  
    scanf("%d%d", &n, &m);  
    for (int i = 0; i < MAXN; ++i) {  
        head[i] = NULL;  
    }  
    for (int i = 0; i < m; ++i) {  
        int u, v;  
        scanf("%d %d", &u, &v);  
        addEdge(u, v, 1);  
        addEdge(v, u, 1);     
    }  
    work();  
    return 0;  
}

简单的BFS遍历

倒排索引表

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
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
#include <stdio.h>  
#include <stdlib.h>  
#include <string.h>  
#include <ctype.h>  
  
#define MAXTable 500009  
  
  
struct WList{  
    int len;  
    struct WList *next;  
};  
  
struct FList{  
    int num;  
    struct FList *next;  
};  
  
struct Hash{  
    char vocabulary[15];  
    int num;  
    FList *idx;  
};  
  
struct HashTable{  
    int TableSize;  
    struct Hash *words;  
};  
  
HashTable* tableinit(int TableSize){  
    HashTable *H = (HashTable*)malloc(sizeof(HashTable));  
    H->TableSize = TableSize;  
    H->words = (Hash*)calloc(H->TableSize, sizeof(struct Hash));  
    return H;  
}  
  
WList* fileinit(int Size){  
    WList *F = (WList*)calloc(Size, sizeof(FList));  
    return F;  
}  
  
int getword(char Word[]){  
    char c;  
    int p = 0;  
    c = getchar();  
    while (!isalpha(c) && (c != '#'))  
        c = getchar();  
    if (c == '#')  
        return 0;  
    while (isalpha(c) && (p < 10)){  
        Word[p++] = tolower(c);  
        c = getchar();  
    }  
    while (isalpha(c))  
        c = getchar();  
    if (p < 3)  
        return getword(Word);  
    else{  
        Word[p] = '\0';  
        return 1;  
    }  
}  
  
int gethash(char key[],int p){  
    unsigned int h = 0;  
    int len = (int)strlen(key);  
    for(int i = 0 ;i < len ; ++i)  
        h = (h * 33) + (key[i] - 'a');  
    return h % p;  
}  
  
int findos(char key[], HashTable *H){  
    int pos = gethash(key, H->TableSize);  
    while (H->words[pos].num && strcmp(H->words[pos].vocabulary, key)){  
        pos++;  
        if (pos == H->TableSize) pos = 0;  
    }  
    return pos;  
}  
  
int insert(int num, char key[], HashTable *h){  
    FList *f;  
    int pos = findos(key, h);  
    if (h->words[pos].num != num){  
        if (!h->words[pos].num)  
            strcpy(h->words[pos].vocabulary, key);  
        h->words[pos].num = num;  
        f = (FList*)malloc(sizeof(FList));  
        f->num = num;  
        f->next = h->words[pos].idx;  
        h->words[pos].idx = f;  
        return pos;  
    }  
    else  
        return -1;  
}  
  
void fileindex(WList *file, int num, int pos){  
    WList *w;  
    if (pos < 0)  
        return;  
    w = (WList*)malloc(sizeof(WList));  
    w->len = pos;  
    w->next = file[num-1].next;  
    file[num-1].next = w;  
    file[num-1].len++;  
}  
  
double work(WList *File, int F1, int F2, HashTable *H){  
    int temp;  
    WList *W;  
    FList *F;  
    if (File[F1-1].len > File[F2-1].len){  
        temp = F1;  
        F1 = F2;  
        F2 = temp;  
    }  
    temp = 0;  
    W = File[F1-1].next;  
    while (W) {  
        F = H->words[W->len].idx;  
        while (F) {  
            if (F->num == F2)  
                break;  
            F = F->next;  
        }  
        if (F)  
            temp++;  
        W = W->next;  
    }  
    return ((double)(temp * 100)/ (double)(File[F1 - 1].len + File[F2 - 1].len - temp));  
}  
  
int main(){  
    int n, m, f1, f2;  
    char word[15];  
    HashTable *H;  
    WList *File;  
    scanf("%d", &n);  
    File = fileinit(n);  
    H = tableinit(MAXTable);  
    for (int i = 0; i < n; i++)  
        while(getword(word))  
            fileindex(File, i + 1, insert(i+1, word, H));  
    scanf("%d", &m);  
    for (int i = 0 ; i < m; i++){  
        scanf("%d%d", &f1, &f2);  
        printf("%.1f%%\n", work(File, f1, f2, H));  
    }  
    return 0;  
}

纯纯牛马码农题，思路清晰度要求很高，最后想明白也就这么回事。

模拟 Excel 排序

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
#include <iostream>  
#include <cstdio>  
  
using namespace std;  
  
struct Student{  
    string number, name;  
    int grade;  
} stu[100005];  
  
  
bool cmp1(Student a, Student b){  
    return a.number < b.number;  
}  
  
bool cmp2(Student a, Student b){  
    if(a.name == b.name) return a.number < b.number;  
    return a.name < b.name;  
}  
  
bool cmp3(Student a, Student b){  
    if(a.grade == b.grade) return a.number < b.number;  
    return a.grade < b.grade;  
}  
  
typedef bool (*Operation)(Student,Student);  
  
void quick_sort(Student s[], int l, int r, Operation cmp){  
    if (l < r)  
    {  
        while (i < j)  
        {  
            while(i < j && cmp(s[j], x)) // 从右向左找第一个小于x的数  
                j--;              
            if(i < j)   s[i++] = s[j];  
            while(i < j && !cmp(s[i], x)) // 从左向右找第一个大于等于x的数  
                i++;              
            if(i < j)   s[j--] = s[i];  
        }  
        s[i] = x;  
        quick_sort(s, l, i - 1, cmp); // 递归调用 
    }  
}  
  
int main(){  
    int n, op; cin >> n >> op;  
    for(int i = 1 ; i <= n ; i++)  
        cin >> stu[i].number >> stu[i].name >> stu[i].grade;  
    if(op == 1) quick_sort(stu , 1, n , cmp1);  
    if(op == 2) quick_sort(stu , 1, n , cmp2);  
    if(op == 3) quick_sort(stu , 1, n , cmp3);  
    for(int i = n ; i >= 1 ; i--){  
        cout << stu[i].number << " " << stu[i].name << " " << stu[i].grade << endl;  
    }  
    return 0;  
}

评价是函数指针很好用，可以大大缩减代码的行数，并且可以方便的扩展。
估计老师不让使用sort函数，因此手写快排。至于老师如果说排序题不让用数组，一定要用链表，我只能说这很难评，也很遗憾。
但是快排是不稳定的排序方式，在作业题目稀疏矩阵转置中无法使用，建议在这题中采用mergesort

顺便由于从自己代码编辑器 Ctrl V 的原因，格式可能有点问题，多多担待。