第2章 经典入门

一 排序

例 2.1 排序

• 代码 2.1

  冒泡排序（时间复杂度 \(O(n^2)\)）

  #include <iostream>
  using std::cin; using std::cout; using std::endl;
  
  #include <vector>
  using std::vector;
  
  #include <algorithm>
  using std::swap;
  
  bool bubble(int lo, int hi, vector<int> &ivec) {
      bool sorted = true;     // 整体有序标志
      while (++lo < hi)       // 自左向右，逐一检查各对相邻元素
          if (ivec[lo - 1] > ivec[lo]) {  // 若逆序，则
              sorted = false; // 意味着尚未整体有序，并需要
              swap(ivec[lo - 1], ivec[lo]);   // 交换
          }
      return sorted;
  }
  
  void bubbleSort(int lo, int hi, vector<int> &ivec) {
      while (!bubble(lo, hi--, ivec));   // 逐趟做扫描交换，直至全序
  }
  
  int main() {
      int n;
      vector<int> ivec;
      cin >> n;
      while (n--) {
          int temp;
          cin >> temp;
          ivec.push_back(temp);
      }
      bubbleSort(0, ivec.size(), ivec);   // 对区间 [0, ivec.size()) 冒泡排序
      for (auto e : ivec)
          cout << e << " " << endl;
      return 0;
  }

  冒泡排序改进版：

  #include <iostream>
  using std::cin; using std::cout; using std::endl;
  
  #include <vector>
  using std::vector;
  
  #include <algorithm>
  using std::swap;
  
  bool bubble(int lo, int hi, vector<int> &ivec) {
      int last = lo;      // 最右侧的逆序对初始化为 [lo - 1, lo]
      while (++lo < hi)   // 自左向右，逐一检查各对相邻元素
          if (ivec[lo - 1] > ivec[lo]) {  // 若逆序，则
              last = lo;  // 更新最右侧逆序对位置记录，并
              swap(ivec[lo - 1], ivec[lo]);   // 交换
          }
      return last;
  }   // 前一版本中的逻辑型标志 sorted，改为秩 last
  
  void bubbleSort(int lo, int hi, vector<int> &ivec) {
      while (lo < (hi = bubble(lo, hi, ivec)));   // 逐趟做扫描交换，直至全序
  }
  
  int main() {
      int n;
      vector<int> ivec;
      cin >> n;
      while (n--) {
          int temp;
          cin >> temp;
          ivec.push_back(temp);
      }
      bubbleSort(0, ivec.size(), ivec);   // 对区间 [0, ivec.size()) 冒泡排序
      for (auto e : ivec)
          cout << e << " " << endl;
      return 0;
  }

• 代码 2.2

  快速排序（时间复杂度 \(O(nlogn)\)）

  #include <iostream>
  using std::cin; using std::cout; using std::endl;
  
  #include <vector>
  using std::vector;
  
  #include <algorithm>
  using std::sort;
  
  int main() {
      int n;
      vector<int> ivec;
      cin >> n;
      while (n--) {
          int temp;
          cin >> temp;
          ivec.push_back(temp);
      }
      sort(ivec.begin(), ivec.end());      // C++ sort 底层实现是快速排序
      // sort(ivec.begin(), ivec.end(), less<int>());      // 也可以自己指定第三个参数
      for (auto e : ivec)
          cout << e << " " << endl;
      return 0;
  }

  Standard library header

  也可以自定义 sort 的第三个参数

  比如将该例题降序排列：

  #include <iostream>
  using std::cin; using std::cout; using std::endl;
  
  #include <vector>
  using std::vector;
  
  #include <algorithm>
  using std::sort;
  
  #include <functional>
  using std::greater;
  
  bool cmp(int x, int y) {
      return x > y;
  }
  
  int main() {
      int n;
      vector<int> ivec;
      cin >> n;
      while (n--) {
          int temp;
          cin >> temp;
          ivec.push_back(temp);
      }
      // sort(ivec.begin(), ivec.end(), greater<int>());
      sort(ivec.begin(), ivec.end(), cmp);
      for (auto e : ivec)
          cout << e << " " << endl;
      return 0;
  }

  各种排序算法（选择排序+有序向量合并+归并排序+快速排序）

  template <typename T>
  Rank Vector<T>::max(Rank lo, Rank hi) {     // 在 [lo, hi] 内找出最大者
      Rank mx = hi;
      while (lo < hi--)   // 逆向扫描
          if (_elem[hi] > _elem[mx])  // 且严格比较
              mx = hi;    // 故能在 max 有多个时保证后者有先，进而保证 selectionSort 稳定
      return mx;
  }
  
  template <typename T>   // 向量选择排序
  void Vector<T>::selectionSort(Rank lo, Rank hi) {   // 0 <= lo < hi <= size
      cout << "\tSELECTIONsort [" << lo << ", " << hi << "]" << endl;
      while (lo < hi) {
          swap(_elem[max(lo, hi)], _elem[hi]);    // 将 [hi] 与 [lo, hi] 中的最大者交换
          --hi;
      }
  }
  
  template <typename T>   // 有序向量（区间）的归并
  void Vector<T>::merge(Rank lo, Rank mi, Rank hi) {  // 各自有序的子向量 [lo, mi) 和 [mi, hi)
      T* A = _elem + lo;  // 合并后的向量 A[0, hi - lo) = _elem[lo, hi)
      int lb = mi - lo; T* B = new T[lb];     // 前子向量B[0, lb) = _elem[lo, mi)
      for (Rank i = 0; i < lb; B[i] = A[i++]);    // 复制前子向量B[0, lb) = _elem[lo, mi)
      int lc = hi - mi; T* C = _elem + mi;    // 后子向量C[0, lc) = _elem[mi, hi)
      for (Rank i = 0, j = 0, k = 0; j < lb || k < lc; ) {    // B[j]和C[k]中小者转至A的末尾
          if (j < lb && (lc <= k || B[j] <= C[k])) A[i++] = B[j++];   // C[k]已无或不小
          if (k < lc && (lb <= j || C[k] < B[j])) A[i++] = C[k++];    // B[j]已无或更大
      }
      delete [] B;    // 释放临时空间B
  }
  
  template <typename T>   // 向量归并排序
  void Vector<T>::mergeSort(Rank lo, Rank hi) {   // 0 <= lo < hi <= size
      cout << "\tMERGEsort [" << lo << ", " << hi << ")\n";
      if (hi - lo < 2) return;    // 单元素区间自然有序，否则...
      int mi = (lo + hi) / 2;     // 以中点为界
      mergeSort(lo, mi); mergeSort(mi, hi);   // 分别排序
      merge(lo, mi, hi);          // 归并
  }
  
  template <typename T>   // 轴点构造算法：通过调整元素位置构造区间[lo, hi)的轴点，并返回其秩
  Rank Vector<T>::partition(Rank lo, Rank hi) {   // 版本A：基本形式
      swap(_elem[lo], _elem[lo + rand() % (hi - lo)]);    // 任选一个元素与首元素交换
      hi--;   // [lo, hi)
      T pivot = _elem[lo];    // 以首元素为候选轴点（经以上swap函数交换，等效于随机选取
      while (lo < hi) {   // 从向量的两端交替地向中间扫描
          while ((lo < hi) && (pivot <= _elem[hi]))   // 在不小于pivot的前提下
              hi--;   // 向左拓展右端子向量
          _elem[lo] = _elem[hi];  // 小于pivot者归入左侧子序列
          while ((lo < hi) && (_elem[lo] <= pivot))   // 在不大于pivot的前提下
              lo++;   // 向右拓展左端子序列
          _elem[hi] = _elem[lo];  // 大于pivot者归入右侧子序列
      }   // assert: lo == hi
      _elem[lo] = pivot;  // 将备份的轴点记录置于前、后子向量之间
      return lo;  // 返回轴点的秩
  }
  
  template <typename T>   // 向量快速排序
  void Vector<T>::quickSort(Rank lo, Rank hi) {   // 0 <= lo < hi <= size
      cout << "\tQUICKsort [" << lo << ", " << hi << ")\n";
      if (hi - lo < 2) return;    // 单个元素区间自然有序，否则...
      Rank mi = partition(lo, hi);    // 在[lo, hi)内构造轴点
      quickSort(lo, mi);  // 对前缀递归排序
      quickSort(mi + 1, hi);  // 对后缀递归排序
  }

例 2.2 成绩排序

• 代码 2.4

  #include <iostream>
  using std::cin; using std::cout; using std::endl;
  
  #include <vector>
  using std::vector;
  
  #include <algorithm>
  using std::sort;
  
  #include <string>
  using std::string;
  
  class Students {
  private:
      string _name;
      unsigned _age;
      unsigned _score;
  public:
      bool operator<(const Students &b) const;   // C++ 运算符重载
      void setName(string studentName) { _name = studentName; }
      string getName() { return _name; }
      void setAge(unsigned studentAge) { _age = studentAge; }
      unsigned getAge() { return _age; }
      void setScore(unsigned studentScore) { _score = studentScore; }
      unsigned getScore() { return _score; }
  };
  
  bool Students::operator<(const Students &b) const {
      if (_score != b._score)   // 若分数不相同则分数低者在前
          return _score < b._score;
      int tmp = _name.string::compare(b._name);
      if (!tmp)               // 若分数相同则名字字典序小者在前
          return tmp < 0;
      else                    // 若名字也相同则年龄小者在前
          return _age < b._age;
  }
  
  int main() {
      int n;
      cin >> n;
      // Create a vector of Students objects
      vector<Students> v;
      string name;
      unsigned age, score;
      Students *p;
      while (n--) {
          cin >> name >> age >> score;
          p = new Students;
          p->setName(name), p->setAge(age), p->setScore(score);
          v.push_back(*p);
      }
      sort (v.begin(), v.end());  // 使用类 Students 自定义的 < 重载运算符
      for (auto e : v)
          cout << e.getName() << " "
               << e.getAge() << " "
               << e.getScore() << endl;
      return 0;
  }

  std::string::compare() in C++

二 日期类问题

例 2.3 日期差值

• 代码 2.6

  #include <stdio.h>
  
  // 定义宏判断是否是闰年，方便计算每月天数
  #define ISYEAP(y) y % 100 != 0 && y % 4 == 0 || y % 400 == 0 ? 1 : 0
  
  int dayOfMonth[13][2] = {
          {0, 0}, {31, 31}, {28, 29}, {31, 31}, {30, 30}, {31, 31},
          {30, 30}, {31, 31}, {31, 31}, {30, 30}, {31, 31}, {30, 30}, {31, 31}
  };      // 预存每月的天数，注意二月配合宏定义做特殊处理
  struct Date {   // 日期类，方便日期的推移
      int Day, Month, Year;
      void nextDay();     // 计算下一天的日期
  };
  void Date::nextDay() {
      Day++;
      if (Day > dayOfMonth[Month][ISYEAP(Year)]) {    // 若日数超过了当月最大日数
          Day = 1;
          Month++;            // 进入下一月
          if (Month > 12) {   // 月数超过 12
              Month = 1;
              Year++;         // 进入下一年
          }
      }
  }
  int buf[3001][13][32];      // 保存预处理的天数
  int Abs(int x) {            // 求绝对值
      return x < 0 ? -x : x;
  }
  int main() {
      Date tmp;
      int cnt = 0;            // 天数计算
      tmp.Day = 1;
      tmp.Month = 1;
      tmp.Year = 0;           // 初始化日期类对象为 0 年 1 月 1 日
      while (tmp.Year != 3001) {      // 日期不超过 3000 年
          // 将该日期与 0 年 1 月 1 日的天数差保存起来
          buf[tmp.Year][tmp.Month][tmp.Day] = cnt;
          tmp.nextDay();      // 计算下一天日期
          // 计数器累加，每经过一天计数器即+1，代表与原点日期的间隔又增加一天
          cnt++;
      }
  
      int d1, m1, y1;
      int d2, m2, y2;
      while (scanf("%4d%2d%2d", &y1, &m1, &d1) != EOF) {
          scanf("%4d%2d%2d", &y2, &m2, &d2);      // 读入要计算的两个日期
          // 用预处理的数据计算两个日期差值，注意需对其求绝地值
          printf("%d\n", Abs(buf[y2][m2][d2] - buf[y1][m1][d1]) + 1);
      }
  
      return 0;
  }

  样例输入：

  20110412
  20110422

  样例输出：

  11

例 2.4 Day of week

• 代码 2.7

  #include <stdio.h>
  #include <cstring>  // using strcmp function
  
  // 定义宏判断是否是闰年，方便计算每月天数
  #define ISYEAP(y) y % 100 != 0 && y % 4 == 0 || y % 400 == 0 ? 1 : 0
  
  int dayOfMonth[13][2] = {
          {0, 0}, {31, 31}, {28, 29}, {31, 31}, {30, 30}, {31, 31},
          {30, 30}, {31, 31}, {31, 31}, {30, 30}, {31, 31}, {30, 30}, {31, 31}
  };      // 预存每月的天数，注意二月配合宏定义做特殊处理
  struct Date {   // 日期类，方便日期的推移
      int Day, Month, Year;
      void nextDay();     // 计算下一天的日期
  };
  void Date::nextDay() {
      Day++;
      if (Day > dayOfMonth[Month][ISYEAP(Year)]) {    // 若日数超过了当月最大日数
          Day = 1;
          Month++;            // 进入下一月
          if (Month > 12) {   // 月数超过 12
              Month = 1;
              Year++;         // 进入下一年
          }
      }
  }
  int buf[3001][13][32];      // 保存预处理的天数
  char monthOfName[13][20] = {    // 下标1～12对应月名
          "", "January", "February", "March", "April", "May", "June",
          "July", "August", "September", "October", "November", "December"
  };
  char weekName[7][20] = {        // 下标0～6对应周名
          "Sunday", "Monday", "Tuesday", "Wednesday",
          "Thursday", "Friday", "Saturday"
  };
  int main() {
      Date tmp;
      int cnt = 0;            // 天数计算
      tmp.Day = 1;
      tmp.Month = 1;
      tmp.Year = 0;           // 初始化日期类对象为 0 年 1 月 1 日
      while (tmp.Year != 3001) {      // 日期不超过 3000 年
          // 将该日期与 0 年 1 月 1 日的天数差保存起来
          buf[tmp.Year][tmp.Month][tmp.Day] = cnt;
          tmp.nextDay();      // 计算下一天日期
          // 计数器累加，每经过一天计数器即+1，代表与原点日期的间隔又增加一天
          cnt++;
      }
  
      int d, m, y;
      char s[20];
      while (scanf("%d%s%d", &d, s, &y) != EOF) {
          for (m = 1; m <= 12; m++) {
              if (strcmp(s, monthOfName[m]) == 0) {
                  break;  // 将输入字符串与月名比较得出月数
              }
          }
          // 计算给定日期与今日日期的天数间隔（注意可能为负）
          int days = buf[y][m][d] - buf[2019][12][6];
          // 今天（2019.12.06）为星期一，对应数组下标为 5，则计算 5 经过 days 天后的下标
          days += 5;
          // 将计算后得出的下标用 7 对其取模，并且保证其为非负数，则该下标即为答案所对应的下标，输出即可
          puts(weekName[(days % 7 + 7) % 7]);
      }
  
      return 0;
  }

  样例输入：

  1 December 2019 10 December 2019

  样例输出：

  Sunday
  Tuesday

三 Hash 的应用

例 2.5 统计相同成绩学生人数

• 代码 2.8

  #include <iostream>
  using std::cin; using std::cout; using std::endl;
  
  #include <map>
  using std::map;
  
  int main() {
      int n;
      while (cin >> n && n != 0) {    // 输入判断增加对 n 是否等于零进行判断
          map<unsigned, unsigned> score_count;
          unsigned score;
          // 不能写为 cin >> score && n--，否则循环结束时，&& 短路求值，cin >> score 得到 x 的值
          while (n-- && cin >> score)
              ++score_count[score];
          unsigned x;
          cin >> x;
          cout << score_count[x] << endl;
      }
  
      return 0;
  }

  样例输入：

  3
  80 60 90
  60
  2
  85 66
  0
  5
  60 75 90 55 75 75
  0

  样例输出：

  1
  0
  2

例 2.6 Sort

• 代码 2.9

  #include <iostream>
  using std::cin; using std::cout; using std::endl;
  
  #include <map>
  using std::map;
  
  #define OFFSET 500000   // 偏移量，用于补偿实际数字与数组下标之间偏移
  int main() {
      int n, m;
      cin >> n >> m;
      map<unsigned, unsigned> h;
      for (int i = 500000; i >= -500000; i--) {
          h[i + OFFSET] = 0;
      }   // 初始化，将每个数字都标记为未出现，即 0
      for (int i = 0; i < n; i++) {
          int x; cin >> x;
          ++h[x + OFFSET];   // 凡是出现过的数字，累计加 1
      }
      for (int i = 500000; i >= -500000; i--) {   // 输出前 m 大的数
          if (h[i + OFFSET]) {
              cout << i << " ";
              m--;
          }
          if (!m) {   // 若 m 个数已经输出完毕，则在输出的数字后面紧跟一个换行，并跳出循环
              cout << "\n";
              break;
          }
      }
  
      return 0;
  }

四 排版题

例 2.7 输出梯形

• 代码 2.10（规律性强，直接按规律输出）

  #include <iostream>
  using std::cin; using std::cout; using std::endl;
  
  int main() {
      // 每行 ' ' 和 '*' 总个数 s = h + 2 * (h - 1)
      // 第一行 '*' 有 h 个，以后每行 '*' 的个数较前一行加 2
      // 第一行 ' ' 有 s - h 个，以后每行 ' ' 的个数较前一行减 2
      // 总共输出 h 行
      int h;
      while (cin >> h) {
          int s = h + 2 * (h - 1);
          int row = h;
          for (int i = 0; i < row; i++) {     // 依次输出每行信息
              for (int j = 0; j < s; j++) {   // 依次输出每行当中的空格或星号
                  if (j < s - h - 2 * i)      // 输出空格
                      cout << " ";
                  else                        // 输出星号
                      cout << "*";
              }
              cout << endl;                   // 输出换行
          }
      }
  
      return 0;
  }

例 2.8 叠筐

• 代码 2.11（规律性不若，先排版后输出）

  #include <iostream>
  using std::cin; using std::cout;
  
  #define N 80
  int main() {
      int outPutBuf[N][N];    // 用于预排版的输出缓存
      char a, b;              // 输入的两个字符
      int n;                  // 叠筐大小
      bool firstCase = true;  // 是否为第一组数据标志，初始值为 true
      while (cin >> n >> a >> b) {
          if (firstCase == true) {    // 若是第一组数据
              firstCase = false;      // 将第一组数据标志记成 false
          } else                      // 否则输出换行
              cout << "\n";
          // i 表示每圈边长长度
          // j 的奇偶性确定每圈字符，以及用来辅助动态确定每圈左上角坐标
          for (int i = 1, j = 1; i <= n; i += 2, j++) {   // 从里到外
              int x = n / 2 + 1, y = x;
              x -= j - 1; y = x;              // 计算每个圈左上角点的坐标
              char c = j % 2 == 1 ? a : b;    // 计算当前圈的字符
              for (int k = 1; k <= i; k++) {  // 对当前圈进行赋值
                  outPutBuf[x + k - 1][y] = c;            // 左边赋值
                  outPutBuf[x][y + k - 1] = c;            // 上边赋值
                  outPutBuf[x + i - 1][y + k - 1] = c;    // 右边赋值
                  outPutBuf[x + k - 1][y + i - 1] = c;    // 下边赋值
              }
          }
          if (n != 1) {   // 注意，当 n 为 1 时，不需要此步骤
              outPutBuf[1][1] = ' ';
              outPutBuf[1][n] = ' ';
              outPutBuf[n][1] = ' ';
              outPutBuf[n][n] = ' ';      // 将四角置为空格
          }
          for (int i = 1; i <= n; i++) {  // 输出经过排版的在输出缓存中的数据
              for (int j = 1; j <= n; j++)
                  cout << (char)outPutBuf[i][j];
              cout << "\n";
          }
      }
  
      return 0;
  }

五 查找

例 2.9 找 x

• 代码 2.12

  #include <iostream>
  using std::cin; using std::cout; using std::endl;
  
  int main() {
      int n; cin >> n;
      int* A = new int[n];
      for (int i = 0; i < n; ++i) {
          int tmp; cin >> tmp;
          A[i] = tmp;
      }
      int x, ans = -1;    // 初始化答案为 -1，以期在找不到答案时能正确的输出 -1
      cin >> x;
      for (int j = 0; j < n; ++j) {   // 依次遍历数组元素
          if (x == A[j]) {    // 目标数字与数组元素依次比较
              ans = j;
              break;          // 找到答案后跳出
          }
      }
      cout << ans << endl;
      delete [] A;
  
      return 0;
  }

例 2.10 查找学生信息

• 代码 2.13

  #include <iostream>
  using std::cin; using std::cout;
  
  #include <string>
  using std::string;
  
  #include <algorithm>
  using std::sort;
  
  class Student {     // 用于表示学生个体的类
  private:
      string _no;     // 学号
      string _name;   // 姓名
      unsigned _age;  // 年龄
      string _sex;    // 性别
  public:
      void setNo(string no) { _no = no; }
      string getNo() { return _no; }
      void setName(string name) { _name = name; }
      string getName() { return _name; }
      void setSex(string sex) { _sex = sex; }
      string getSex() { return _sex; }
      void setAge(unsigned age) { _age = age; }
      unsigned getAge() { return _age; }
      bool operator<(const Student & b) const; // 重载小于运算符使其能使用 sort 函数排序
  };
  bool Student::operator<(const class Student & b) const {
      return _no.string::compare(b._no) < 0;
  }
  
  int main () {
      int n; cin >> n;
      Student* stu = new Student[n];
      for (int i = 0; i < n; ++i) {
          string no, name, sex;
          unsigned age;
          cin >> no >> name >> sex >> age;
          stu[i].setNo(no); stu[i].setName(name);
          stu[i].setSex(sex); stu[i].setAge(age);
      }   // 输入
      sort(stu, stu + n);     // 对数组排序使其按学号升序排列
      int m; cin >> m;        // 有 m 组询问
      while (m--) {   // while 循环保证查询次数 m
          int ans = -1;   // 目标元素下标，初始化为 -1
          string tmp;     // 待查找学号
          cin >> tmp;
          int hi = n, lo = 0;     // Student 对象数组 stu 的 [lo, hi) 区间二分查找 tmp
          while (lo < hi) {   // 每步迭代可能要做两次比较判断，有三个分支
              int mi = (lo + hi) >> 1;    // 以中点为轴点
              if (tmp < stu[mi].getNo())
                  hi = mi;    // 深入前半段 [lo, mi) 继续查找
              else if (stu[mi].getNo() < tmp)
                  lo = mi + 1;    // 深入后半段 (mi, hi) 继续查找
              else {
                  ans = mi;   // 在 mi 处命中
                  cout << stu[ans].getNo() << ' ' << stu[ans].getName() << ' '
                       << stu[ans].getSex() << ' ' << stu[ans].getAge() << "\n";
                  break;      // 查找成功则终止本轮查找
              }
          } // 成功查找可以提前终止
          if (ans == -1)      // 若查找失败
              cout << "No Answer!\n";
      }
  
      delete [] stu;
  
      return 0;
  }

六 贪心算法

例 2.11 FatMouse' Trade

• 代码 2.14

  #include <iostream>
  using std::cin; using std::cout; using std::endl;
  
  #include <algorithm>
  using std::sort;
  
  #include <iomanip>
  using std::fixed; using std::setprecision;
  
  struct goods {  // 表示可买物品的结构体
      double j;   // 该物品总重
      double f;   // 该物品总价值
      double s;   // 该物品性价比
      // 重载小于运算符，确保可用 sort 函数将数组按照性价比降序排列
      bool operator<(const goods &b) const {
          return s > b.s;
      }
  } buf[1000];
  
  int main() {
      double m;
      int n;
      while (cin >> m >> n) {
          if (m == -1 && n == -1)
              break;  // 当 m、n 为 -1 时，跳出循环，程序运行结束
          for (int i = 0; i < n; i++) {
              double j, f;
              cin >> buf[i].j >> buf[i].f;    // 输入
              buf[i].s = buf[i].j / buf[i].f; // 计算性价比
          }
          sort(buf, buf + n); // 使各物品按照性价比降序排列
          int idx = 0;    // 当前货物下标
          double ans = 0.0;   // 累加所能得到的总重量
          while (0 < m && idx < n) {  // 各类物品有剩余（idx < n）还有钱剩余（m > 0）时继续循环
              if (m > buf[idx].f) {   // 若能买下全部该种类物品
                  ans += buf[idx].j;
                  m -= buf[idx].f;
              } else {    // 若只能买下部分该物品
                  ans += m * buf[idx].j / buf[idx].f;
                  m = 0;
              }
              ++idx;  // 继续下一种类物品
          }
          cout << fixed << setprecision(3) << ans << endl;
      }
  
      return 0;
  }

  C++数字的输出处理问题(保留几位小数，或保留几位有效数字）

例 2.12 今年暑假不 AC

• 代码 2.15

  #include <iostream>
  using std::cin; using std::cout; using std::endl;
  
  #include <algorithm>
  using std::sort;
  
  struct program {    // 电视节目结构体
      int _startTime;  // 节目开始时间
      int _endTime;    // 节目结束时间
      // 重载小于号，保证 sort 函数能够按照结束时间升序排列
      bool operator<(const program &second) const {
          return _endTime < second._endTime;
      }
  };
  program buf[100];
  int main() {
      int n;
      while (cin >> n) {
          if (n == 0)
              break;
          for (int i = 0; i < n; i++) {   // 输入
              cin >> buf[i]._startTime >> buf[i]._endTime;
          }
          sort (buf, buf + n);    // 按照结束时间升序排列
          // 记录当前时间，初始化为 0；所求能看的节目个数，初始化为 0
          int currentTime = 0, ans = 0;
          for (int i = 0; i < n; i++) {   // 按照结束时间升序遍历所有节目
              // 若当前时间小于等于该节目开始时间，那么收看该在剩余节目里结束时间最早的节目
              if (currentTime <= buf[i]._startTime) {
                  currentTime = buf[i]._endTime;  // 当前时间变为该节目结束时间
                  ++ans;  // 又收看了一个节目
              }
          }
          cout << ans << endl;    // 输出
      }
  }

第 3 章 数据结构

一 栈的应用

例 3.1 括号匹配问题

• 代码 3.1

  #include <iostream>
  using std::cin; using std::cout; using std::endl;
  
  #include <stack>
  using std::stack;
  
  #include <string>
  using std::string;
  
  int main() {
      stack<int> S;   // 定义一个堆栈
      string str;     // 保存输入字符串
      while (cin >> str) {
          string ans(str.size(), ' ');    // 保存输出字符串，初始化为与输入等长的空字符串
          int i;
          for (i = 0; i < str.size(); i++) {    // 从左到右遍历输入字符串
              if (str[i] == '(') {     // 若遇到左括号
                  S.push(i);  // 将其下标放入堆栈中
                  // ans[i] += ' ';  // 暂且将对应的输出字符串位置字符改为空格
              } else if (str[i] == ')') {     // 若遇到右括号
                  if (S.empty() == false) {   // 若此时堆栈非空
                      S.pop();    // 栈顶位置左括号与其匹配，从栈中弹出该已经匹配的左括号下标
                  } else {    // 若堆栈为空，则无法找到左括号与其匹配，修改输出字符串该位为 '?'
                      ans[i] = '?';
                  }
              }
          }
          while (S.empty() == false) {    // 当字符串遍历完成后，尚留在堆栈中的左括号无法匹配
              ans[S.top()] = '$';     // 修改其在输出中的位置为 '$'
              S.pop();    // 弹出栈顶元素
          }
          cout << str << '\n' << ans << endl;    // 输出原字符串与答案字符串
      }
  
      return 0;
  }

例 3.2 简单计算器

• 代码 3.2

  #include <stack>
  #include <stdio.h>
  using namespace std;
  
  char str[220];  // 保存表达式字符串
  /*
   * 优先级矩阵,若mat[i][j] == 1，则表示i号运算符优先级大于j号
   * 运算符，运算符编码规则为+为1号，-为2号，*为3号，/为4号,我们
   * 人为添加在表达式首尾的标记运算符为0号
   */
  int mat[][5] = {
          1, 0, 0, 0, 0,
          1, 0, 0, 0, 0,
          1, 0, 0, 0, 0,
          1, 1, 1, 0, 0,
          1, 1, 1, 0, 0
  };
  stack<int> op;  // 运算符栈,保存运算符编号
  stack<double> in;   // 数字栈,运算结果可能存在浮点数,所以保存元素为double
  /*
   * 该函数获得表达式下一个元素,若函数运行结束时,引用变量reto为true,则表示该元
   * 素为一个运算符,其编号保存在引用变量retn中; 否则，表示该元素为一个数字，其
   * 值保存在引用变量retn中.引用变量i表示遍历到的字符串下标
   */
  void getOp(bool &reto, int &retn, int &i) {
      // 若此时遍历字符串第一个字符,且运算符栈为空,我们人为添加编号为0的标记字符
      if (i == 0 && op.empty() == true) {
          reto = true;    // 为运算符
          retn = 0;   // 编号为0
          return; // 返回
      }
      if (str[i] == 0) {  // 若此时遍历字符为空字符,则表示字符串已经被遍历完
          reto = true;    // 为运算符
          retn = 0;   // 编号为0的标记字符
          return; // 返回
      }
      if (str[i] >= '0' && str[i] <= '9') {   // 若当前字符为数字
          reto = false;   // 返回为数字
      } else {    // 否则
          reto = true;    // 返回为运算符
          if (str[i] == '+')          // 加号返回1
              retn = 1;
          else if (str[i] == '-')     // 减号返回2
              retn = 2;
          else if (str[i] == '*')     // 乘号返回3
              retn = 3;
          else if (str[i] == '/')     // 除号返回4
              retn = 4;
          i += 2;     // i递增，跳过该运算符和紧邻的空格字符
          return;     // 返回
      }
      retn = 0;   // 返回结果为数字
      // 若字符串未被遍历完,且下一个字符不是空格,则依次遍历其后数字,计算当前连续数字字符表示的数值
      for ( ; str[i] != ' ' && str[i] != 0; i++) {
          retn *= 10;
          retn += str[i] - '0';
      }
      if (str[i] == ' ')  // 若其后字符为空格,则表示字符串未被遍历完
          ++i;    // i递增.跳过该空格
      return;     // 返回
  }
  
  int main() {
      while (gets(str)) {     // 输入字符串,当其位于文件尾时,gets返回0
          if (str[0] == '0' && str[1] == 0) break;    // 若输入只有一个0,则退出
          bool retop; int retnum; // 定义函数所需的引用变量
          int idx = 0;    // 定义遍历到的字符串下标,初始值为0
          while (!op.empty()) op.pop();
          while (!in.empty()) in.pop();   // 清空数字栈,和运算符栈
          while (true) {  // 循环遍历表达式字符串
              getOp(retop, retnum, idx);  // 获取表达式中下一个元素
              if (retop == false) {   // 若该元素为数字
                  in.push((double)retnum);    // 将其压入数字栈中
              } else {    // 否则
                  // 若运算符堆栈为空或者当前遍历到的运算符优先级大于栈顶运算符,将该运
                  // 算符压入运算符堆栈
                  double tmp;
                  if (op.empty() == true || mat[retnum][op.top()] == 1) {
                      op.push(retnum);
                  } else {    // 否则
                      // 只要当前运算符优先级 小于栈顶元素运算符,则重复循环
                      while (mat[retnum][op.top()] == 0) {
                          int ret = op.top(); // 保存栈顶运算符
                          op.pop();   // 弹出
                          double b = in.top();
                          in.pop();
                          double a = in.top();
                          in.pop();   // 从数字堆栈栈顶弹出两个数字,依次保存在a、b中
                          if (ret == 1) tmp = a + b;
                          else if (ret == 2) tmp = a - b;
                          else if (ret == 3) tmp = a * b;
                          else tmp = a / b;
                          in.push(tmp);   // 将结果压回数字堆栈
                      }
                      op.push(retnum);    // 将当前运算符压入运算符堆栈
                  }
              }
              // 若运算符堆栈只有两个元素,且其栈顶元素为标记运算符,则表示表达式求值结束
              if (op.size() == 2 && op.top() == 0)
                  break;
          }
          printf("%.2f\n", in.top());     // 输出数字栈中唯一的数字,即为答案
      }
      return 0;
  }

二 哈夫曼树