程序设计基础

函数指针数组

函数指针数组，也叫函数跳转表

void (*pf[2])(int*,int) = {bubble1, bubble2};

定义函数指针变量，在函数参数中使用函数指针与此同理

void (*pf)(int*,int);

二进制文件的读取

包含头文件 #include <fstream>
文件变量

ifstream fin;
ofstream fout;

以二进制方式打开文件

fin.open("input.wav",ios::binary);
fout.open("output.wav",ios::binary);

可以在构造时传入文件名和是否二进制

fin.close();
fout.close();

读取文件头需要预先知道文件头结构，比如 WAV 的文件头：

struct WAVHeader {  
    char riff[4]; // "RIFF"  
    uint32_t size; // file size - 8  
    char wave[4]; // "WAVE"  
    char fmt[4]; // "fmt "  
    uint32_t fmt_size; // 16  
    uint16_t audio_fmt; // 1 (PCM)  
    uint16_t channels; // 1  
    uint32_t sample_rate;  
    uint32_t byte_rate;  
    uint16_t block_align;  
    uint16_t bits_per_sample; // 16  
    char data[4]; // "data"  
    uint32_t data_size; // following data bytes  
};

定义一个 WAVHeader 类型的变量
WAVHeader w_head;

fin.read((char *)&w_head, sizeof(w_head));

其中 &w 传入数据块的首地址，第二个参数传入数据块的大小
写入也是同理，先定义好数据变量，再通过以下方式写入：

fout.write((char *)&w_head, sizeof(w_head));

为了更标准的写法，可以用 reinterpret_cast<char*>(&f) 代替 (char*)&f
知道文件头以后就可以根据文件头中的数据大小读取数据本体

short *pdata = new short[w_head->data_size/sizeof(short)];
fin.read((char*)pdata,w_head->datasize);

全排列函数

next_permutation(arr.begin(),arr.end());

生成基于字典序的下一个全排列，如果不存在则生成字典序最小的全排列，并返回 false，正常则返回 true

对 map 排序的技巧

map<string,int> M;
vector<pair<string, int>> A(M.begin(), M.end());

sort(A.begin(), A.end(), cmp);
for (auto& it : A) {
    cout << it.first << " " << it.second << endl;
}

需要排序后结果时，先存到以 pair 为元素的 vector 里，再用 sort 排序，注意仍然需要自己写比较函数 cmp

cin.ignore() 的注意事项

cin.ignore(); // 有的时候有问题
cin.ignore(numeric_limits<streamsize>::max(), '\n'); // 需要用这个

经典模板代码

八皇后问题

#include <iostream>
#include <vector>
using namespace std;

const int N = 8;    // 皇后数量（可改成任意 n）

vector<int> queens(N);      // queens[row] = col，表示第 row 行皇后放在 col 列
bool colUsed[N];            // 标记列是否被占用
bool diag1Used[2 * N];      // 主对角线（row - col + N）
bool diag2Used[2 * N];      // 副对角线（row + col）

// 打印一个解
void printSolution() {
    for (int r = 0; r < N; ++r) {
        for (int c = 0; c < N; ++c) {
            if (queens[r] == c) cout << "Q ";
            else cout << ". ";
        }
        cout << "\n";
    }
    cout << "-------------------\n";
}

// 回溯放置第 row 行的皇后
void backtrack(int row) {
    if (row == N) {
        printSolution();   // 找到一个完整解
        return;
    }

    for (int col = 0; col < N; ++col) {
        // 检查是否冲突
        if (colUsed[col]) continue;
        if (diag1Used[row - col + N]) continue;
        if (diag2Used[row + col]) continue;

        // 做选择
        queens[row] = col;
        colUsed[col] = diag1Used[row - col + N] = diag2Used[row + col] = true;

        backtrack(row + 1);      // 递归下一行

        // 撤销选择
        colUsed[col] = diag1Used[row - col + N] = diag2Used[row + col] = false;
    }
}

int main() {
    backtrack(0);
    return 0;
}