树

哈夫曼树

基本概念

给定N个权值作为N个叶子结点，构造一棵二叉树，若该树的带权路径长度达到最小，称这样的二叉树为最优二叉树，也称为哈夫曼树(Huffman Tree)。哈夫曼树是带权路径长度最短的树，权值较大的结点离根较近。

  • 带权路径长度：

    模板集合 - 图1

    哈夫曼编码

    注意考虑树只有一个点的情况 ```cpp

    include

    include

    include

    include

    include

    include

using namespace std;

const int N = 1010;

char s[N]; unordered_map rec; // 记录字母出现次数

int main() {

  1. #ifdef SUBMIT
  2. freopen("in.txt", "r", stdin);
  3. freopen("out.txt", "w", stdout);
  4. long _begin_time = clock();
  5. #endif
  7. while (scanf("%s", s), strcmp(s, "END") != 0) {
  8.     int len = strlen(s);
  9.     rec.clear();    // 记得清空
  10.     for (int i = 0; i < len; i++) {
  11.         rec[s[i]]++;
  12.     }
  14.     priority_queue<int, vector<int>, greater<int>> heap;    // 优先队列没有clear方法
  15.     for (auto it = rec.begin(); it != rec.end(); it++) {
  16.         heap.push(it->second);
  17.         // cout << (double)it->second / len << ' ';
  18.     }
  19.     // cout << endl;
  21.     int avg = 0;
  22.     if (heap.size() == 1) {    // 注意，只有一个点时，带权路径长度就是那个点的权值
  23.         avg = heap.top();
  24.     }
  25.     while (heap.size() > 1) {    // 至少有两个点才能合并
  26.         double a1 = heap.top(); heap.pop();
  27.         double a2 = heap.top(); heap.pop();
  28.         avg += a1 + a2;
  29.         heap.push(a1 + a2);
  30.     }
  31.     // cout << avg << endl;
  33.     int ori = len * 8;
  34.     printf("%d %d %.1lf\n", ori, avg, (double)ori / avg);
  35. }    
  37. #ifdef SUBMIT
  38. long _end_time = clock();
  39. printf("\n\ntime = %ld ms", _end_time - _begin_time);
  40. #endif
  42. return 0;

}

  1. <a name="IVH85"></a>
  2. ## [Trie字符串统计](https://www.acwing.com/problem/content/description/837/)
  3. ```cpp
  4. #include <iostream>
  6. using namespace std;
  8. const int N = 2e4 + 10;
  10. int son[N][26], cnt[N], idx;    // idx=0既是根结点，又代表没有孩子
  11. char s[N];
  13. void insert(char s[]) {
  14.     int p = 0;
  15.     for (int i = 0; s[i]; i++) {
  16.         int u = s[i] - 'a';
  17.         if (!son[p][u]) son[p][u] = ++idx;
  18.         p = son[p][u];
  19.     }
  21.     cnt[p]++;
  22. }
  24. int query(char s[]) {
  25.     int p = 0;
  26.     for (int i = 0; s[i]; i++) {
  27.         int u = s[i] - 'a';
  28.         if (!son[p][u]) return 0;
  29.         p = son[p][u];
  30.     }
  32.     return cnt[p];
  33. }
  35. int main() {
  36.     int n;
  37.     cin >> n;
  38.     while (n--) {
  39.         char op[2];
  40.         scanf("%s%s", op, s);
  41.         if (op[0] == 'I') {
  42.             insert(s);
  43.         }
  44.         else {
  45.             printf("%d\n", query(s));
  46.         }
  47.     }
  49.     return 0;
  50. }

图

Prim算法求最小生成树

时间复杂度是 O(n^2+m) n表示点数，m表示边数

  1. #include <iostream>
  2. #include <cstring>
  4. using namespace std;
  6. const int N = 510, INF = 0x3f3f3f3f;
  8. int g[N][N];
  9. int dist[N];
  10. bool st[N];
  11. int n, m;
  13. int prim() {
  14.     memset(dist, 0x3f, sizeof dist);
  16.     int ans = 0;
  17.     for (int i = 0; i < n; i++) {
  18.         int t  = -1;
  19.         for (int j = 1; j <= n; j++) {
  20.             if (!st[j] && (t == -1 || dist[j] < dist[t]))
  21.                 t = j;
  22.         }
  24.         if (i && dist[t] == INF) return INF;
  25.         if (i) ans += dist[t];    // 防止自环，先更新ans，再更新dist
  26.         st[t] = true;
  28.         for (int j = 1; j <= n; j++) dist[j] = min(dist[j], g[t][j]);
  29.     }
  31.     return ans;
  32. }
  34. int main() {
  35.     cin >> n >> m;
  37.     memset(g, 0x3f, sizeof g);
  38.     while (m--) {
  39.         int u, v, w;
  40.         cin >> u >> v >> w;
  41.         g[u][v] = g[v][u] = min(g[u][v], w);
  42.     }
  44.     int ans = prim();
  46.     if (ans == INF) puts("impossible");
  47.     else cout << ans;
  49.     return 0;
  50. }

Kruskal算法求最小生成树

时间复杂度是 O(mlogm), n表示点数，m表示边数

  1. #include <iostream>
  2. #include <algorithm>
  4. using namespace std;
  6. const int N = 2e5 + 10;
  8. int p[N];
  10. struct Edge {
  11.     int a, b, w;
  13.     bool operator< (const Edge &W) const {
  14.         return w < W.w;
  15.     } 
  16. }edges[N];
  18. int find(int x) {
  19.     if (x != p[x]) p[x] = find(p[x]);
  20.     return p[x];
  21. }
  23. int main() {
  24.     int n, m;
  25.     cin >> n >> m;
  26.     for (int i = 0; i < m; i++) {
  27.         scanf("%d%d%d", &edges[i].a, &edges[i].b, &edges[i].w);
  28.     }
  30.     sort(edges, edges + m);    // 将所有边按权值从小到大排序
  32.     for (int i = 1; i <= n; i++) p[i] = i;
  34.     int cnt = 0, ans = 0;
  35.     for (int i = 0; i < m; i++) {
  36.         int a = edges[i].a, b = edges[i].b, w = edges[i].w;
  38.         int fa = find(a), fb = find(b);
  39.         if (fa != fb) {    // 两个顶点不在一个连通块当中
  40.             p[fa] = fb;
  41.             cnt++;
  42.             ans += w;
  43.         }
  44.     }
  46.     if (cnt < n - 1) puts("impossible");    // 边的数量等于顶点数 - 1
  47.     else cout << ans;
  49.     return 0;
  50. }

Dijkstra求最短路-朴素

时间复杂度是 O(n^2+m), n表示点数，m表示边数

  1. #include <iostream>
  2. #include <cstring>
  4. using namespace std;
  6. const int N = 510;
  7. int g[N][N], dist[N];
  8. bool st[N];
  9. int n, m;
  11. int dijkstra(int p) {
  12.     memset(dist, 0x3f, sizeof dist);
  13.     dist[p] = 0;
  15.     for (int i = 0; i < n; i++) {
  16.         int t = -1;
  17.         for (int j = 1; j <= n; j++) {
  18.             if (!st[j] && (t == -1 || dist[j] < dist[t]))
  19.                 t = j;
  20.         }
  22.         st[t] = true;
  24.         for (int j = 1; j <= n; j++) 
  25.             dist[j] = min(dist[j], dist[t] + g[t][j]);
  26.     }
  28.     if (dist[n] == 0x3f3f3f3f) return -1;
  29.     return dist[n];
  30. }
  32. int main() {
  33.     cin >> n >> m;
  34.     memset(g, 0x3f, sizeof g);
  35.     while (m--) {
  36.         int x, y, z;
  37.         scanf("%d%d%d", &x, &y, &z);
  39.         g[x][y] = min(g[x][y], z);
  40.     }
  42.     cout << dijkstra(1);
  44.     return 0;
  45. }

Dijkstra求最短路-堆优化

时间复杂度O(mlogn)，n是点数，m是边数

  1. #include <iostream>
  2. #include <queue>
  3. #include <cstring>
  5. using namespace std;
  7. const int N = 1.5e5 + 10, INF = 0x3f3f3f3f;
  9. typedef pair<int, int> PII;
  11. int n, m;
  12. int h[N], e[N], ne[N], w[N], idx;
  13. int dist[N];
  14. bool st[N];
  15. priority_queue<PII, vector<PII>, greater<PII>> heap;
  17. void add(int a, int b, int c) {
  18.     w[idx] = c;
  19.     e[idx] = b;
  20.     ne[idx] = h[a];
  21.     h[a] = idx++;
  22. }
  24. int dijkstra() {
  25.     memset(dist, 0x3f, sizeof dist);
  26.     dist[1] = 0;
  27.     heap.push({0, 1});
  29.     while (!heap.empty()) {
  30.         auto p = heap.top(); heap.pop();
  31.         int ver = p.second, d = p.first;
  33.         if (st[ver]) continue;
  34.         st[ver] = true;
  36.         for (int i = h[ver]; i != -1; i = ne[i]) {
  37.             int j = e[i];
  38.             if (dist[ver] + w[i] < dist[j]) {
  39.                 dist[j] = dist[ver] + w[i];
  40.                 heap.push({dist[j], j});
  41.             }
  42.         }
  43.     }
  45.     if (dist[n] > INF / 2) return -1;
  46.     return dist[n];
  47. }
  49. int main() {
  50.     cin >> n >> m;
  52.     memset(h, -1, sizeof h);
  53.     while (m--) {
  54.         int x, y, z;
  55.         scanf("%d%d%d", &x, &y, &z);
  56.         add(x, y, z);
  57.     }
  59.     cout << dijkstra();
  61.     return 0;    
  62. }

Floyd求最短路

时间复杂度O(n^3)

  1. #include <iostream>
  2. #include <cstring>
  4. using namespace std;
  6. const int N = 210, INF = 0x3f3f3f3f;
  8. int g[N][N];
  10. int main() {
  11.     int n, m, k;
  12.     cin >> n >> m >> k;
  14.     for (int i = 1; i <= n; i++) {
  15.         for (int j = 1; j <= n; j++) {
  16.             if (i == j) g[i][j] = 0;
  17.             else g[i][j] = INF;
  18.         }
  19.     }
  21.     for (int i = 0; i < m; i++) {
  22.         int x, y, z;
  23.         scanf("%d%d%d", &x, &y, &z);
  24.         g[x][y] = min(g[x][y], z);
  25.     }
  27.     for (int k = 1; k <= n; k++) {
  28.         for (int i = 1; i <= n; i++) {
  29.             for (int j = 1; j <= n; j++) {
  30.                 g[i][j] = min(g[i][j], g[i][k] + g[k][j]);
  31.             }
  32.         }
  33.     }
  35.     while (k--) {
  36.         int i, j;
  37.         scanf("%d%d", &i, &j);
  38.         if (g[i][j] >= INF / 2) printf("impossible\n");    // 可能有负边
  39.         else printf("%d\n", g[i][j]);
  40.     }
  41. }

有向图的拓扑序列

  1. #include <iostream>
  2. #include <cstring>
  4. using namespace std;
  6. const int N = 1e5 + 10;
  8. int h[N], e[N], ne[N], idx;
  9. int d[N];
  10. int q[N], hh, tt = -1;
  11. int n, m;
  13. void add(int a, int b) {
  14.     d[b]++;
  15.     e[idx] = b;
  16.     ne[idx] = h[a];
  17.     h[a] = idx++;
  18. }
  20. bool toposort() {
  21.     for (int i = 1; i <= n; i++) {
  22.         if (!d[i]) {    // 入度为0的点
  23.             q[++tt] = i;
  24.         }    
  25.     }
  27.     while (hh <= tt) {
  28.         int p = q[hh++];
  29.         for (int i = h[p]; i != -1; i = ne[i]) {
  30.             int j = e[i];
  31.             if (--d[j] == 0) {
  32.                 q[++tt] = j;
  33.             }
  34.         }
  35.     }
  37.     return hh == n;    // 所有节点都入队
  38. }
  40. int main() {
  41.     cin >> n >> m;
  43.     memset(h, -1, sizeof h);
  44.     while (m--) {
  45.         int x, y;
  46.         scanf("%d%d", &x, &y);
  48.         add(x, y);
  49.     }
  51.     if (toposort()) {
  52.         for (int i = 0; i < n; i++) 
  53.             printf("%d ", q[i]);
  54.     }
  55.     else puts("-1");
  57.     return 0;
  58. }

哈希

字符串哈希

  1. #include <iostream>
  3. using namespace std;
  5. const int N = 1e5 + 10, P = 131;
  7. typedef unsigned long long ULL;
  9. char str[N];
  10. ULL h[N], p[N];
  12. ULL get(int l, int r) {
  13.     return h[r] - h[l - 1] * p[r - l + 1]; 
  14. }
  16. int main() {
  17.     int n, m;
  18.     cin >> n >> m;
  20.     scanf("%s", str + 1);
  22.     p[0] = 1;
  23.     for (int i = 1; i <= n; i++) {
  24.         h[i] = h[i - 1] * P + str[i];
  25.         p[i] = p[i - 1] * P;
  26.     }
  28.     while (m--) {
  29.         int l1, r1, l2, r2;
  30.         scanf("%d%d%d%d", &l1, &r1, &l2, &r2);
  32.         if (get(l1, r1) == get(l2, r2)) {
  33.             puts("Yes");
  34.         }
  35.         else puts("No");
  36.     }
  37. }

模拟散列表

  1. #include <iostream>
  2. #include <cstring>
  4. using namespace std;
  6. const int N = 100003, null = 0x3f3f3f3f;
  8. int h[N];
  10. int find(int a) {
  11.     int k = ((a % N) + N) % N;
  13.     while (h[k] != null && h[k] != a) {
  14.         k++;
  15.         if (k == N) k = 0;
  16.     }
  18.     return k;
  19. }
  21. int main() {
  22.     memset(h, 0x3f, sizeof h);
  24.     int n;
  25.     cin >> n;
  27.     while (n--) {
  28.         char op[2];
  29.         int x;
  31.         scanf("%s%d", op, &x);
  32.         if (op[0] == 'I') {
  33.             h[find(x)] = x;
  34.         }
  35.         else {
  36.             if (h[find(x)] != x) puts("No");
  37.             else puts("Yes");
  38.         }
  39.     }
  41.     return 0;
  42. }

堆

用数组实现一棵完全二叉树

堆排序

只实现插入+查询最小

  1. #include <iostream>
  3. using namespace std;
  5. const int N = 1e5 + 10;
  7. int h[N], hcnt;
  9. void down(int t) {
  10.     int p = t;
  11.     if (t * 2 <= hcnt && h[t * 2] < h[p]) p = t * 2;
  12.     if (t * 2 + 1 <= hcnt && h[t * 2 + 1] < h[p]) p = t * 2 + 1;
  14.     if (p != t) {
  15.         swap(h[p], h[t]);
  16.         down(p);
  17.     }
  18. }
  20. int main() {
  21.     int n, m;
  22.     cin >> n >> m;
  24.     hcnt = n;
  26.     for (int i = 1; i <= n; i++) {
  27.         scanf("%d", &h[i]);
  28.     }
  30.     for (int i = n / 2; i; i--) down(i);    // 建堆O(n)
  32.     while (m--) {
  33.         printf("%d ", h[1]);
  34.         h[1] = h[hcnt--];
  35.         down(1);
  36.     }
  38.     return 0;
  39. }

模拟堆

  1. #include <iostream>
  2. #include <cstring>
  4. using namespace std;
  6. const int N = 1e5 + 10;
  8. int h[N], hp[N], ph[N], hcnt, pcnt;
  10. void hswap(int a, int b) {    // 三种交换
  11.     swap(ph[hp[a]], ph[hp[b]]);
  12.     swap(hp[a], hp[b]);
  13.     swap(h[a], h[b]);
  14. }
  16. void up(int p) {
  17.     while (p / 2 && h[p] < h[p / 2]) {
  18.         hswap(p, p / 2);
  19.         p >>= 1;
  20.     }
  21. }
  23. void down(int p) {
  24.     int t = p;
  25.     if (p * 2 <= hcnt && h[p * 2] < h[t]) t = p * 2;
  26.     if (p * 2 + 1 <= hcnt && h[p * 2 + 1] < h[t]) t = p * 2 + 1;
  28.     if (t != p) {
  29.         hswap(t, p);
  30.         down(t);
  31.     }
  32. }
  34. int main() {
  35.     int n;
  36.     cin >> n;
  38.     while (n--) {
  39.         char op[5];
  40.         scanf("%s", op);
  41.         if (op[0] == 'I') {
  42.             int x;
  43.             scanf("%d", &x);
  44.             hcnt++, pcnt++;
  45.             h[hcnt] = x;
  46.             ph[pcnt] = hcnt, hp[hcnt] = pcnt;
  47.             up(hcnt);
  48.         }
  49.         else if (op[0] == 'P') {
  50.             printf("%d\n", h[1]);
  51.         }
  52.         else if (strcmp(op, "DM") == 0) {
  53.             hswap(1, hcnt);
  54.             --hcnt;
  55.             down(1);
  56.         }
  57.         else if (op[0] == 'D') {
  58.             int k;
  59.             scanf("%d", &k);
  60.             k = ph[k];
  61.             hswap(k, hcnt);
  62.             hcnt--;
  63.             up(k), down(k);
  64.         }
  65.         else if (op[0] == 'C') {
  66.             int k, x;
  67.             scanf("%d%d", &k, &x);
  69.             k = ph[k];
  70.             h[k] = x;
  71.             up(k), down(k);
  72.         }
  73.     }
  75.     return 0;
  76. }

链表

反转链表

非常值得借鉴的做法，遍历链表，将其存储到数组中进行各种处理

  1. #include <iostream>
  2. #include <vector>
  3. #include <algorithm>
  5. using namespace std;
  7. const int N = 1e5 + 10;
  9. int h, e[N], ne[N];
  10. vector<int> q;
  12. int main() {
  13.     int n, k;
  14.     cin >> h >> n >> k;
  16.     while (n--) {
  17.         int addr, d, next;
  18.         scanf("%d%d%d", &addr, &d, &next);
  19.         e[addr] = d, ne[addr] = next;
  20.     }
  22.     for (int i = h; i != -1; i = ne[i]) {
  23.         q.push_back(i);
  24.     }    
  26.     for (int i = 0; i + k - 1 < q.size(); i += k) {
  27.         reverse(q.begin() + i, q.begin() + i + k);
  28.     }
  30.     for (int i = 0; i < q.size(); i++) {
  31.         printf("%05d %d ", q[i], e[q[i]]);
  32.         if (i + 1 == q.size()) printf("-1\n");
  33.         else printf("%05d\n", q[i + 1]);
  34.     }
  36.     return 0;
  37. }

反转链表

传统的链表做法
非递归
时间复杂度O(n)，空间复杂度O(1)

  1. /**
  2.  * Definition for singly-linked list.
  3.  * struct ListNode {
  4.  *     int val;
  5.  *     ListNode *next;
  6.  *     ListNode(int x) : val(x), next(NULL) {}
  7.  * };
  8.  */
  9. class Solution {
  10. public:
  11.     ListNode* reverseList(ListNode* head) {
  12.         ListNode* h = new ListNode(0);
  13.         ListNode *p = head;
  14.         while (p) {
  15.             ListNode *q = p->next;
  16.             p->next = h->next;
  17.             h->next = p;
  18.             p = q;
  19.         }
  20.         return h->next;
  21.     }
  22. };

递归
时间复杂度O(n)，空间复杂度O(n)

  1. /**
  2.  * Definition for singly-linked list.
  3.  * struct ListNode {
  4.  *     int val;
  5.  *     ListNode *next;
  6.  *     ListNode(int x) : val(x), next(NULL) {}
  7.  * };
  8.  */
  9. class Solution {
  10. public:
  11.     ListNode* reverseList(ListNode* head) {
  12.         if (!head || !head->next) return head;
  13.         ListNode *p = reverseList(head->next);
  14.         head->next->next = head;
  15.         head->next = nullptr;
  16.         return p;
  17.     }
  18. };

第k大数

知识点

基于快排的快速选择算法，做法就是在基准值的位置放好之后，如果大于基准值的数的数量cnt>=k，就在左半段寻找第k大数，否则在右半段寻找第k-cnt大数。每次选择了左右之一继续，因此时间复杂度为模板集合 - 图2

模板

  1. // 快排模板
  2. void quick_sort(int q[], int l, int r) {
  3.     if (l >= r) return;
  5.     // 随机选取基准
  6.     int idx = l + rand() % (r - l + 1);
  7.     int x = q[idx];
  8.     int i = l - 1, j = r + 1;
  10.     while (i < j) {    //x左边的数<x，右边的数>x
  11.         while (q[++i] < x);
  12.         while (q[--j] > x);
  13.         if (i < j) swap(q[i], q[j]);
  14.     }
  16.     quick_sort(q, l, j);
  17.     quick_sort(q, j + 1, r);
  18. }
  20. // 快速选择
  21. void quick_select(int q[], int l, int r, int k) {
  22.     if (l >= r) return q[l];
  24.     int idx = l + rnad() % (r - l + 1);
  25.     int x = q[idx];
  26.     int i = l - 1, j = r + 1;
  28.     while (i < j) {
  29.         while (q[++i] < x);
  30.         while (q[--j] > x);
  31.         if (i < j) swap(q[i], q[j]);
  32.     }
  34.     int tmp = j - l + 1;
  35.     if (tmp < k) return quick_select(q, j + 1, r, k - tmp);
  36.     else return quick_select(q, l, j, k);
  37. }

字符串

strcpy和ctrncpy的实现

  1. int my_strcmp(const char *s1, const char *s2)
  2. {
  3.     while(*s1 && *s2 && *s1 == *s2)
  4.     {
  5.         s1++;
  6.         s2++;     
  7.     }
  9.     return *s1 - *s2;
  10. }
  12. int my_strncmp(const char *s1, const char *s2, size_t n) {
  13.     while (n--) {
  14.         if (*s1 && *s2 && *s1 == *s2) {
  15.             s1++;
  16.             s2++;
  17.         }
  18.         else return *s1 - *s2;
  19.     }
  21.     return 0;
  22. }

strcat和strncat的实现

注意，dest和src不能相同，可以考虑加上assert判断，但库函数不会有这个问题

  1. char *my_strcat(char *dest, const char *src)
  2. {
  3.     char *ret = dest;
  5.     while (*dest)
  6.         dest++;
  7.     while (*dest++ = *src++);
  9.     return ret;
  10. }
  12. char *my_strncat(char *dest, const char *src,int n)
  13. {
  14.     char *ret = dest;
  15.     while (*dest)
  16.         dest++;
  17.     while (n--)  //通过此次while循环，将第二个字符串前n的字符连接到第一个字符串上
  18.         *dest++ = *src++;
  19.     *dest = '\0';
  20.     return ret;
  21. }

动态规划

数字三角形

  1. #include <iostream>
  3. using namespace std;
  5. const int N = 510;
  7. int a[N][N];
  9. int main() {
  10.     int n;
  11.     cin >> n;
  13.     for (int i = 1; i <= n; i++) {
  14.         for (int j = 1; j <= i; j++) {
  15.             scanf("%d", &a[i][j]);
  16.         }
  17.     }
  19.     for (int i = n - 1; i >= 1; i--) {
  20.         for (int j = 1; j <= i; j++) {
  21.             a[i][j] += max(a[i + 1][j], a[i + 1][j + 1]);
  22.         }
  23.     }
  25.     cout << a[1][1];
  27.     return 0;
  28. }

文件操作

打开关闭

  1. #include <stdio.h>
  2. #include <stdlib.h>
  4. #define N 100
  6. int main() {
  7.     FILE *fp;
  8.     char str[N + 1];
  10.     //判断文件是否打开失败！
  11.     if ( (fp = fopen("d:\\demo.txt", "r")) == NULL ) {
  12.         puts("Fail to open file!");
  13.         exit(0);
  14.     }
  16.     //循环读取文件的每一行数据
  17.     while( fgets(str, N, fp) != NULL ) {
  18.         printf("%s", str);
  19.     }
  21.     //操作结束后关闭文件！
  22.     fclose(fp);
  24.     return 0;
  25. }
控制读写权限的字符串（必须指明）
打开方式 说明
“r” 以“只读”方式打开文件。只允许读取，不允许写入。文件必须存在，否则打开失败。
“w” 以“写入”方式打开文件。如果文件不存在，那么创建一个新文件；如果文件存在，那么清空文件内容（相当于删除原文件，再创建一个新文件）。
“a” 以“追加”方式打开文件。如果文件不存在，那么创建一个新文件；如果文件存在，那么将写入的数据追加到文件的末尾（文件原有的内容保留）。
“r+” 以“读写”方式打开文件。既可以读取也可以写入，也就是随意更新文件。文件必须存在，否则打开失败。
“w+” 以“写入/更新”方式打开文件，相当于w和r+叠加的效果。既可以读取也可以写入，也就是随意更新文件。如果文件不存在，那么创建一个新文件；如果文件存在，那么清空文件内容（相当于删除原文件，再创建一个新文件）。
“a+” 以“追加/更新”方式打开文件，相当于a和r+叠加的效果。既可以读取也可以写入，也就是随意更新文件。如果文件不存在，那么创建一个新文件；如果文件存在，那么将写入的数据追加到文件的末尾（文件原有的内容保留）。
控制读写方式的字符串（可以不写）
打开方式 说明
“t” 文本文件。如果不写，默认为"t"。
“b” 二进制文件。

读写

  • int fputc( int c, FILE *fp );
  • int fputs( const char s, FILE fp );
  • int fprintf(FILE fp,const char format, …)
  • int fgetc( FILE * fp );
  • char fgets( char buf, int n, FILE *fp );

  • int fscanf(FILE fp, const char format, …) ```cpp

    include

    int main() { FILE *fp = NULL;

    fp = fopen(“/tmp/test.txt”, “w+”); fprintf(fp, “This is testing for fprintf…\n”); // FILE放开头 fputs(“This is testing for fputs…\n”, fp); // FILE放最后 fclose(fp); }

include

int main() { FILE *fp = NULL; char buff[255];

fp = fopen(“/tmp/test.txt”, “r”); fscanf(fp, “%s”, buff); printf(“1: %s\n”, buff );

fgets(buff, 255, (FILE*)fp); printf(“2: %s\n”, buff );

fgets(buff, 255, (FILE*)fp); printf(“3: %s\n”, buff ); fclose(fp);

}

// 二进制IO（以数据块的形式读写文件） size_t fread(void ptr, size_t size_of_elements, size_t number_of_elements, FILE a_file); size_t fwrite(const void ptr, size_t size_of_elements, size_t number_of_elements, FILE a_file);

  1. <a name="331tq"></a>
  2. ## 大文件
  3. 首先把整个文件读进来
  4. ```cpp
  5. // define buffer
  6. FILE *fin=fopen("input.bin", "rb");
  7. fseek(fin, 0, SEEK_END);
  8. long f_length=ftell(fin);
  9. fseek(fin, 0, SEEK_SET);
  10. fread(buffer, 1, f_length, fin);

然后考虑分行，可以采用strtok函数

  1. #include <string.h>
  2. #include <stdio.h>
  4. int main () {
  5.    char str[80] = "This is\nwww.runoob.com\nwebsite";
  6.    const char s[2] = "\n";
  7.    char *token;
  9.    /* 获取第一个子字符串 */
  10.    token = strtok(str, s);
  12.    /* 继续获取其他的子字符串 */
  13.    while( token != NULL ) {
  14.       printf("%s\n", token);
  15.       token = strtok(NULL, s);
  16.    }
  18.    return(0);
  19. }