零、緒論和IDE安裝

1.安裝IDE：clion或vs
新手不要直接在clion上寫代碼，要在強(qiáng)大的IDE(集成開發(fā)環(huán)境)中練習(xí)，能方便的找出低級錯誤。
在IDE上通過后，再把代碼復(fù)制到OJ中。

2.OJ的運(yùn)行原理：OJ不會直接評判代碼，而是用測試用例來測試你的輸出結(jié)果是否與它的答案相符。如此便能在某些情況下“作弊”。
若OJ中某個測試用例超時，可以提前準(zhǔn)備好答案，以便通過用例。例如，“打表”。

3.機(jī)試需要的函數(shù)：輸入(scanf 或 cin)、輸出(printf 或 cout)、讀取一行(fgets 或 cin.getline)
機(jī)試考察的數(shù)據(jù)結(jié)構(gòu)：數(shù)組、鏈表、二叉樹
機(jī)試需要的算法：枚舉、模擬、遞歸、分治、搜索

會50%、會70%和會90%都是零分。要會，就要100%會。要么滿分，要么零分！
練精一道題，勝于淺嘗輒止10道題！

int取值范圍

int的取值范圍為：-2³¹ -2³¹-1 ,即：-2147483648 - 2147483647
注意題目要求的n的范圍，判斷f(n)是否會超過int的取值范圍。若超過，則需要換成float或double或long long int或unsigned int。

常犯的編程小錯誤

1.問題：等價條件判斷是 == ，寫成了 =
情況：不好定位。段錯誤，且半天沒看出問題，邏輯都是對的。最后找助教才幫忙看出來，花了十幾分鐘。尷尬。
解決：遵守編程規(guī)范，在寫等價判斷時，值寫在左邊，變量寫在右邊。 這樣即使把==寫成了=，也會是編譯錯誤，直接報語法錯誤，好定位。

一、枚舉和模擬 (暴力求解)

(一) 枚舉

循環(huán) + if + printf

1.Reverse函數(shù) 求 反序數(shù)

int Reverse(int n){ //求反序數(shù)的Reverse函數(shù)int remain;//每次的余數(shù)int reverse = 0;while(n != 0){remain = n%10;n = n/10;reverse = reverse*10 + remain;}return reverse;
}

2.程序出錯的原因

前兩步統(tǒng)稱構(gòu)建(build)

1.編譯錯誤 (compile)：基本語法錯誤

1.定位第一個編譯錯誤，根據(jù)行號、列號、提示，去解決第一個編譯錯誤。
編譯錯誤只看第一個錯誤。因?yàn)榻鉀Q一個問題可能就會解決一片編譯錯誤。

2.鏈接錯誤 (link)：函數(shù)名寫錯了

編譯通過，說明基本的語法沒有錯誤。
鏈接錯誤，并不提示鏈接錯誤的位置。一般就是函數(shù)名字寫錯了。

3.運(yùn)行錯誤 (run)：結(jié)果與預(yù)期不符，斷點(diǎn)調(diào)試 [打斷點(diǎn)，看監(jiān)視]

運(yùn)行時錯誤，構(gòu)建(build)成功，即編譯、鏈接都通過，但結(jié)果與預(yù)期不符。
運(yùn)行錯誤也不會提示哪里有問題，這就需要通過打斷點(diǎn)來進(jìn)行斷點(diǎn)調(diào)試了。

3.編程規(guī)范

1.判斷時，固定值寫左邊

防止 if(n==0) 漏寫為 if(n=0)，導(dǎo)致死循環(huán)。而且這不是編譯錯誤，檢查不出來。
要寫成if(0 == n)，把固定值寫左邊。這樣，如果漏寫為 if( 0 =n)是不符合語法的，將錯誤提前到了編譯階段。
最簡單的錯誤就是編譯錯誤(語法錯誤)

2.不要省略大括號

雖然有些if里面只有一句話，可以省略花括號。但是對于企業(yè)級的項目來說，if里經(jīng)常可能會添加新語句，而忘記花括號。對于這種經(jīng)常變動的代碼，務(wù)必全都加上大括號(即使只有一行)，以防日后又增又刪的調(diào)試。
即使你自己注意到了，難免后續(xù)接手的程序員不會忘記if里又加了幾行時忘記使用花括號，而且這里加了沒有調(diào)試，最終bug，花了半天時間才找到是因?yàn)檫@里if忘記加花括號了。
同時，維護(hù)別人寫的代碼時也要注意，在向單行循環(huán)體里加語句時，檢查它是否有大括號。

4.命名規(guī)范

1.變量命名規(guī)范

①外層循環(huán)使用不常見的變量名，減少內(nèi)外層沖突的可能性

②類名的首字母大寫。（類包括struct、class）

(二) 模擬

Ⅰ.圖案問題：二維數(shù)組 + 找數(shù)字規(guī)律

1.不確定數(shù)量的輸入 while(scanf(“%d”,&n) != EOF){ }

//輸入n，然后輸入n個數(shù)
int n;
int arr[101];
while (scanf("%d",&n) != EOF){for(int i=0;i<n;++i){scanf("%d",&arr[i]);}
}

注意：輸入一串?dāng)?shù)據(jù)后，要先按Enter換行，再按Crtl+D。不換行則這一行數(shù)據(jù)沒有輸入緩沖區(qū)。

輸入EOF：
①clion/gcc/clung：crtl+d
②vs：crtl+c

2.作用域

放在花括號內(nèi)部的變量，生命周期只能在花括號里。
有時候有的變量需要設(shè)在全局，或者函數(shù)外部，才能被調(diào)用。

3.機(jī)試對字符串的處理

1.處理輸入、輸出：C風(fēng)格字符串(字符數(shù)組)：char str[1000]

C風(fēng)格的字符串，本質(zhì)是字符數(shù)組，以\0結(jié)尾。

char str[1000];//初始化
scanf("%s",str);//輸入(字符串的輸出不需要加&)
printf("%s\n",str);//輸出

易錯，%c注意要空格

2.處理更復(fù)雜問題：C++風(fēng)格字符串：string

#include <string>
using namespace std;

①初始化：string str1 = "hello";
②連接：str1 = str1 + "world";
③下標(biāo)訪問：str1[0] //為h
④求長度：str1.length()
⑤判斷相等：str1 == "hello"
⑥比較字典序：str1 > "abandon"
⑦從C++風(fēng)格字符串轉(zhuǎn)到C風(fēng)格字符串：str1.c_str()
⑧刪除最后一個字符：pop_back()

4.二維數(shù)組

char pat[80][80]={0};//定義二維數(shù)組并初始化，長度固定

5.OJ問題

Ⅱ.日期問題

1.閏年問題

bool isLeap = (year%400==0)  || (year%100!=0 && year%4==0);//true是閏年

2.用空間換時間

輔助數(shù)組

int mday[13] = {0,31,28,31,30,31,30,31,31,30,31,30,31};

3.打印日期用printf，比cout方便

%d：打印數(shù)字
%4d：打印數(shù)字，至少4個位置寬，不足則用空格填充
%04d：打印數(shù)字，至少4個位置寬，不足則用0填充

cout的運(yùn)行效率、格式控制，不如printf

4.map 映射

#include <map>
using namespace std;

map舉例：

#include <cstdio>
#include <string>
#include <map>
using namespace std;int main(){//鍵 key --> 值 value//<鍵的類型,值的類型>map<string,string> myMap = {{"Caixukun","ikun"},{"Wuyifan","meigeni"}};char str[1000];scanf("%s",&str);string name = str;printf("%s的粉絲被稱為%s",name.c_str(),myMap[name].c_str());
}

Ⅲ.其他模擬問題

1.剩余的樹
2.手機(jī)鍵盤

二、排序與查找

(一) 排序

1.sort函數(shù)：sort(first,last,comp)

C++引入了基于快速排序的排序函數(shù)：sort()
sort(first,last,comp)函數(shù)的三個參數(shù)：①first為待排序序列起始地址 ②last為結(jié)束地址 ③comp為排序方式，不填寫默認(rèn)為升序排序。

#include <algorithm>
using namespace std;

左閉右開 [arr,arr+n)，尾后

---

例1：對n個數(shù)進(jìn)行排序

樣例輸入：
4
1 4 3 2

樣例輸出：
1 2 3 4

#include <cstdio>
#include <algorithm>
using namespace std;int main(){int n;int arr[101];scanf("%d",&n);for(int i=0;i<n;++i){scanf("%d",&arr[i]);//&arr[i] 和 arr+i 等價}sort(arr,arr+n);//排序for(int i=0;i<n;++i){printf("%d ",arr[i]);}printf("\n");
}

---

2.C語言數(shù)組

1.arr[i]是元素
2.arr是0號元素的地址。arr+i是i號元素的地址。
即，C語言數(shù)組的數(shù)組名，可以當(dāng)?shù)刂?指針來使用。&arr[i] 和 arr+i 等價

3.設(shè)計排序的規(guī)則：設(shè)計比較和交換的條件

不發(fā)生交換，返回真

4.C++函數(shù)重載：同一個函數(shù)名，有不同的參數(shù)列表

比較的題目，重點(diǎn)就是設(shè)計bool comp(int lhs,int rhs)函數(shù)。//不發(fā)生交換時為真

5.機(jī)試考試最重要的事情：能把你曾經(jīng)做過的題目，滿分地做出來

最重要的不是把所有題目都寫了個差不多，沒用，差一點(diǎn)就是零分。要么滿分要么零分。
最重要的是，把你曾經(jīng)做過的題目，滿分地做出來。
泥鰍老師：你就算是天縱奇才，也不可能在機(jī)試的時候把你從來沒做過的題目做出來。就是一個熟練度的問題。

(二) 查找

1.順序查找(Liner Search)

順序查找的問題：效率不夠高。
n個元素，順序查找，時間復(fù)雜度為O(n2)。若數(shù)據(jù)量規(guī)模n在10⁵，則會OJ超時。需要采取一些策略降低時間復(fù)雜度。

時間復(fù)雜度、空間復(fù)雜度

0.O()計數(shù)法：忽略常系數(shù)、忽略低階項
1.時間復(fù)雜度：指令執(zhí)行次數(shù)
2.空間復(fù)雜度：額外內(nèi)存空間

2.二分查找(Binary Search)

要求先排序。數(shù)組有序后，才可使用二分查找。
基于比較的排序，時間復(fù)雜度最好為O(nlogn)

二分查找(需要排序)適用于：給定一份數(shù)據(jù)，要查很多次。
若每查一次，數(shù)據(jù)都改，那就用順序查找，不需要排序。

mid = (left + right)/2;
left = mid + 1;    /收縮區(qū)間，注意 +1 -1，避免二分查找死循環(huán)。
right = mid - 1;

3.用map解決查找問題

map的底層：二叉搜索樹(BST)。
①在Windows下，會進(jìn)一步優(yōu)化為：平衡二叉樹(AVL樹)
②在Linux下，會進(jìn)一步優(yōu)化為：紅黑樹

指針迭代器 iterator

findIndex.begin()：第一個元素的指針
findIndex.end()：最后一個元素的后面一個位置的指針，尾后指針
findIndex.find()：查找某個元素的指針

if(findIndex.find(findNum) == findIndex.end()) /說明沒有找到

三、字符串

C字符數(shù)組:char arr[100] —— 輸入輸出

1.字符數(shù)組
以 \0 作為正文結(jié)束的標(biāo)志，也占一個空間

2.輸入輸出效率
printf和scanf的效率要優(yōu)于cin和cout

3.讀取一整行
fgets(字符數(shù)組名,sizeof(字符數(shù)組名),stdin)
fgets最后會讀入換行符\n ，占一個空間（字符數(shù)組轉(zhuǎn)string后，考慮用pop_back()干掉回車）

4. getchar() 吃掉回車

C++字符串：string —— 其他復(fù)雜操作

1.頭文件

#include <string>
using namespace std;

2.獲取長度/大小：
string str;
str.length();
str.size();

printf("length of str = %u\n",str.size());

3.下標(biāo)訪問元素
str[i]（i從0開始）

for(unsigned int i = 0;i < str.size(); ++i){printf("%c\n",str[i]);
}

4.(字符串的)迭代器訪問元素

for(string::iterator it = str.beign(); it != str.end(); ++it){//++it 更改迭代器的指向，到下一個元素printf("%c\n", *it); // &取地址, *取內(nèi)容
}

5.連接：字符串連接/拼接
+ (只針對C++風(fēng)格字符串string類型，C風(fēng)格字符數(shù)組禁止相加)

string str = buf;
str = str + "world";

6.刪除 erase(下標(biāo))

str.erase(str.size()-1); //刪除最后一個元素，即\n

7.清空 clear()

str.clear();

8.查詢字符或字符子串的下標(biāo) .find(內(nèi)容)
①find("字符串")
②find(變量名)

9.取字串 .substr(起始下標(biāo)，長度)
若要切到尾為止，則只寫一個參數(shù)：起始下標(biāo)，不用寫長度。

10.刪除最后一個字符：pop_back()

四、線性數(shù)據(jù)結(jié)構(gòu)

1.當(dāng)定義的數(shù)組特別大，達(dá)到1千萬時，不能定義在函數(shù)內(nèi)部，會崩潰。棧比較小，但快。
要定義在全局位置，數(shù)據(jù)段中。
【局部大數(shù)組會崩潰，全局大數(shù)組不會崩潰】

2.標(biāo)準(zhǔn)模板庫STL

1.向量 vector

vector是動態(tài)數(shù)組，長度可改變。 vector<int> vec;//創(chuàng)建空向量，長度為0
普通靜態(tài)數(shù)組長度是固定不變的。int arr[100];//創(chuàng)建長度為100的靜態(tài)數(shù)組

1.頭文件

#include <vector>
using namespace std;

2.聲明向量

vector<int> vec;//長度為0

3.賦初值

vector<int> vec2 {1,2,3};

4.申請一定空間的向量，所有元素初值默認(rèn)為0

vector<int> vec3(10000);

※5.尾部插入：尾部擴(kuò)容 push_back(元素) 。效率最高，插入n個為O(n)，插入1個為O(1)。

vec.push_back(1);//vec[0]=1
vec.push_back(3);//vec[1]=3

※6.尾部刪除：彈出尾部元素 pop_back()

vec.pop_back();

※7.下標(biāo)訪問

vec[i] //下標(biāo)>=n時，數(shù)組越界

8.長度計算

vec.size();

9.兩種遍歷方法
①下標(biāo)遍歷

for(unsigned int i = 0; i < vec.size(); ++i){printf("vec[%d] = %d\n",i,vec[i]);
}

②迭代器遍歷

for(vector<int>::iterator it = vec.begin(); it != vec.end(); ++it){printf("vec[] = %d\n",*it);
}

10.隨機(jī)位置的插入：insert(位置，元素)

vector<int>::iterator it1 = vec.begin()+1;//迭代器指針指向vector的第二個位置
vec.insert(it1，3);//在vector第二個位置插入元素3

11.隨機(jī)位置的刪除：erase(位置);

vec.erase(vec.begin());//刪除vector的第一個位置的元素

12.vector的實(shí)現(xiàn)原理
(1)vector的組成、申請空間(堆上)
vector是類類型，包括size容量、capacity內(nèi)存大小、ptr首地址
首地址存放在棧上，但vector申請的內(nèi)存空間在堆區(qū)上，堆區(qū)比棧區(qū)大，因此vector可申請空間比靜態(tài)數(shù)組在棧上申請的空間可以大很多。【靜態(tài)數(shù)組 - 棧 - 小空間。 vector - 堆- 大空間】

(2)vector的擴(kuò)容機(jī)制

2.隊列 queue

隊列queue是受限制的線性表。只能在隊尾加入，從隊頭入隊。

1.頭文件

#include <queue>
using namespace std;queue<int> myQueue;

2.隊尾入隊 .push(變量名)

for(int i = 0;i <= 5;++i){myQueue.push(i);
}

3.隊頭出隊 .pop()
4.判空 .empty()
5.隊首元素 .front()

3.棧 stack

操作受限的線性表，只能一端進(jìn)出。
棧，禁止操作的一端稱為盲端。允許元素插入和刪除的一端稱為棧頂。

1.頭文件

#include <stack>
using namespace std;stack<typename> myStack//定義

2.方法
.size()：棧大小
.push()：壓棧，將元素加入棧中
.top()：獲取棧頂內(nèi)容
.pop()：彈棧
.empty()：判斷棧是否為空

3.棧的應(yīng)用
(1)逆序輸出
(2)括號匹配
(3)表達(dá)式求值

五、遞歸與分治

遞歸與分治的關(guān)系

分治是一種思想，分而治之；遞歸是一種實(shí)現(xiàn)方法，函數(shù)調(diào)用自己。
分治思想可用遞歸來實(shí)現(xiàn)，也可以用其他方法來實(shí)現(xiàn)。遞歸作為一種方法，不止可以用于實(shí)現(xiàn)遞歸思想，也可以用來實(shí)現(xiàn)其他思想。
但總的來說，一般都用遞歸方法來實(shí)現(xiàn)分治的思想。故兩者本不是同一緯度的概念，但是經(jīng)常放在一起談?wù)摗?/p>

常見的分治：求斐波那契數(shù)列、快速排序
常見的遞歸：求n的階乘

(一)、遞歸

從函數(shù)到遞歸

①大問題→小問題，等價條件
②確定最小問題，即遞歸出口

函數(shù)

C語言編寫的代碼，以函數(shù)定義為單位。

call：把PC移到被調(diào)函數(shù)
ret：把PC移回主調(diào)函數(shù)

遞歸

1.在函數(shù)定義中調(diào)用本函數(shù)，叫做遞歸。

2.遞歸關(guān)注的兩個點(diǎn)：
①大問題轉(zhuǎn)化為小問題：規(guī)模n→規(guī)模n-1
②最小問題：遞歸出口

---

例題1：n的階乘
例題2：漢諾塔

---

(二)、分治

①分解：大問題拆成小問題
②治理：找到等價條件，解決遞歸出口(最小問題)
③合并

---

例題1：斐波那契數(shù)列
例題網(wǎng)址：http://t.cn/Ai0K3tU5
題解：

#include <cstdio>int Fabonacci(int n){if(0==n || 1==n){return n;}else{return Fabonacci(n-1)+ Fabonacci(n-2);}
}int main(){int n;while(scanf("%d",&n) != EOF){//注意，輸入多個數(shù)據(jù)后，要先Enter換行，再按crtl+Dif(n>=0){printf("%d\n",Fabonacci(n));}else{printf("error: n must >= 0\n");}}
}

例題2：二叉樹
提交網(wǎng)址：http://t.cn/Ai0Ke6I0

#include <cstdio>int binaryTree(int m,int n){if(m>n){return 0;}else{return binaryTree(2*m,n) + binaryTree(2*m+1,n) + 1;}
}int main(){int m,n;while(scanf("%d %d",&m,&n) != EOF){if(m<=0 && n<=0){break;}printf("%d\n",binaryTree(m,n));}
}

---

六、非線性數(shù)據(jù)結(jié)構(gòu)

內(nèi)存空間

棧

棧幀。當(dāng)被調(diào)函數(shù)執(zhí)行結(jié)束，棧幀上的變量也會被自動回收。

堆 (自由存儲區(qū))

new出來的，不會自動銷毀。需要手動回收，否則會發(fā)生內(nèi)存泄漏。

指針和引用

指針（間接訪問 值傳遞）

1.* 取內(nèi)容(間接訪問)

2. &取地址

3.->運(yùn)算符
若p為指針，則(*p).member與p->member等價

引用（引用傳遞）

引用，&x,&y就是給變量x,y起了個別名，并沒有新開辟內(nèi)存存儲空間。這樣，被調(diào)函數(shù)的參數(shù)列表(int &x, int &y)就可以直接引用傳遞給主函數(shù)中的變量x,y。因?yàn)?amp;x &y與x y 享有同一個內(nèi)存地址，會直接修改。

---

C++的兩種傳遞方式：值傳遞、引用傳遞

例1：變量名-直接訪問-值傳遞：在被調(diào)函數(shù)中無法修改主調(diào)函數(shù)中參數(shù)的內(nèi)容。盡管變量名相同，但不是同一個地址

#include <cstdio>void swap1(int x,int y){int temp = x;x = y;y = temp;
}int main(){int x = 1 ,y = 2;swap1(x,y);
}

結(jié)果是，在swap1中x與y的值互換了，但main中的x與y的值不變。因?yàn)閟wap1中和main中的x、y的地址不同。

例2：指針-間接訪問-值傳遞
在被調(diào)函數(shù)里改變主調(diào)函數(shù)中變量的內(nèi)容：傳指針(間接訪問)
在普通函數(shù)中想要改變main函數(shù)中的值，要傳指針。值才能透出去。

#include <cstdio>void swap2(int *px,int *py){int temp = *px;*px = *py;*py = temp;
}int main(){int x = 1 ,y = 2;int *px = &x;int *py = &y;swap2(px,py);
}

例3：引用-引用傳遞
對比例1，只修改了被調(diào)函數(shù)的參數(shù)列表，將int x,int y改為 int &x,int &y

#include <cstdio>void swap3(int &x,int &y){ int temp = x;x = y;y = temp;
}int main(){int x = 1 ,y = 2;swap3(x,y);
}

---

1.二叉樹

二叉樹的遍歷

層次遍歷：隊列

遞歸遍歷：前中后序遍歷

重建二叉樹，并遍歷

---

例1：通過先序序列和中序序列建立二叉樹，再輸出后序遍歷序列（華科復(fù)試上機(jī)真題）
提交網(wǎng)址：http://t.cn/AiKgDfLU

#include <cstdio>
#include <string>
using namespace std;struct TreeNode{char data;TreeNode * leftChild;TreeNode * rightChild;
};TreeNode *rebuild(string preOrder,string inOrder){ //返回值為子樹根結(jié)點(diǎn)的地址if(preOrder.size() == 0){return NULL;}else{//從先序遍歷確定根char rootdata = preOrder[0];TreeNode *pNewNode = new TreeNode;//二叉樹結(jié)點(diǎn)指針pNewNode->data = rootdata;//用根位置切割中序int pos = inOrder.find(rootdata);//pos是根在中序序列中出現(xiàn)的下標(biāo)pNewNode->leftChild = rebuild(preOrder.substr(1,pos),inOrder.substr(0,pos));pNewNode->rightChild = rebuild(preOrder.substr(pos+1),inOrder.substr(pos+1));return pNewNode;}
}void PostOrder(TreeNode * root){if(root == NULL){return;}PostOrder(root->leftChild);PostOrder(root->rightChild);printf("%c",root->data);return;
}int main(){char preOrder[30];char inOrder[30];while(scanf("%s%s",preOrder,inOrder) != EOF){TreeNode * root = rebuild(preOrder,inOrder);PostOrder(root);printf("\n");}
}

例2：根據(jù)有#的先序遍歷序列，構(gòu)建二叉樹，并輸出中序遍歷序列 （清華復(fù)試上機(jī)真題）

哈哈哈

---

2.二叉排序樹 BST

二叉排序樹(二叉搜索樹，二叉查找樹 BST) 的建立

#include <cstdio>struct TreeNode{ //類類型/結(jié)構(gòu)體類型int data;  //數(shù)據(jù)域TreeNode * leftChild; //左孩子指針TreeNode * rightChild;//右孩子指針
};void insertBST(TreeNode * &root,int data){//根，數(shù)據(jù)域TreeNode *pNewNode = new TreeNode;//申請一個空結(jié)點(diǎn) pNewNodepNewNode->data = data;//主函數(shù)傳進(jìn)來的data，賦值給結(jié)點(diǎn)的數(shù)據(jù)域 pNewNode->datapNewNode->leftChild = NULL;//左孩子置為空pNewNode->rightChild = NULL;//右孩子置為空if(NULL == root){root = pNewNode; //若根結(jié)點(diǎn)為空，則讓當(dāng)前結(jié)點(diǎn)TreeNode * pNewNode 作為根結(jié)點(diǎn) TreeNode * root}else{TreeNode * pPre = root;TreeNode * pCur;while(true){if(data < pPre->data){//新數(shù)據(jù)比根結(jié)點(diǎn)小，作為左孩子pCur = pPre->leftChild;if( NULL == pCur ){//左孩子為空   //判斷條件是 == ，寫成一個 = 了pPre->leftChild = pNewNode;break;}else{//左孩子結(jié)點(diǎn)不為空pPre = pCur;//當(dāng)前結(jié)點(diǎn)作為新的根結(jié)點(diǎn)}}else{//新數(shù)據(jù)比根結(jié)點(diǎn)大，作為右孩子pCur = pPre->rightChild;if( NULL == pCur ){  //判斷條件是 == ，寫成一個 = 了pPre->rightChild = pNewNode;break;}else{pPre = pCur;}}}}
}int main(){TreeNode * root = NULL;int array[] = {2,3,5,1,4};for(int i = 0;i < 5; ++i){insertBST(root,array[i]);}}

---

例題1：華科 KY207 二叉排序樹
提交網(wǎng)址：http://t.cn/Ai9PAkkv

#include <cstdio>struct TreeNode{ //類類型/結(jié)構(gòu)體類型int data;  //數(shù)據(jù)域TreeNode * leftChild; //左孩子指針TreeNode * rightChild;//右孩子指針
};void insertBST(TreeNode * &root,int data){//根，數(shù)據(jù)域TreeNode *pNewNode = new TreeNode;//申請一個空結(jié)點(diǎn) pNewNodepNewNode->data = data;//主函數(shù)傳進(jìn)來的data，賦值給結(jié)點(diǎn)的數(shù)據(jù)域 pNewNode->datapNewNode->leftChild = NULL;//左孩子置為空pNewNode->rightChild = NULL;//右孩子置為空if(NULL == root){root = pNewNode; //若根結(jié)點(diǎn)為空，則讓當(dāng)前結(jié)點(diǎn)TreeNode * pNewNode 作為根結(jié)點(diǎn) TreeNode * rootprintf("-1\n");}else{TreeNode * pPre = root;TreeNode * pCur;while(true){if(data < pPre->data){//新數(shù)據(jù)比根結(jié)點(diǎn)小，作為左孩子pCur = pPre->leftChild;if( NULL == pCur ){//左孩子為空   //判斷條件是 == ，寫成一個 = 了pPre->leftChild = pNewNode;printf("%d\n",pPre->data);break;}else{//左孩子結(jié)點(diǎn)不為空pPre = pCur;//當(dāng)前結(jié)點(diǎn)作為新的根結(jié)點(diǎn)}}else{//新數(shù)據(jù)比根結(jié)點(diǎn)大，作為右孩子pCur = pPre->rightChild;if( NULL == pCur ){  //判斷條件是 == ，寫成一個 = 了pPre->rightChild = pNewNode;printf("%d\n",pPre->data);break;}else{pPre = pCur;//當(dāng)前結(jié)點(diǎn)作為新的根結(jié)點(diǎn)}}}}
}int main(){TreeNode * root = NULL;int n;scanf("%d",&n);for(int i = 0;i < n; ++i){int num;scanf("%d",&num);insertBST(root,num);}return 0;
}

例題2：浙大 判斷是否為同一個二叉搜索樹序列
提交網(wǎng)址：http://t.cn/Ai9PUJtK

在這里插入代碼片

---

3.優(yōu)先隊列 priority_queue（堆 heap）

堆

1.堆
優(yōu)先隊列不是隊列(queue)而是堆(heap)，是二叉堆(大根堆、小根堆)，結(jié)構(gòu)是完全二叉樹，用數(shù)組保存。

2.大根堆
優(yōu)先隊列默認(rèn)為大根堆。

priority_queue<typename>name;

3.小根堆 （重新定義優(yōu)先隊列）

priority_queue<typename,vector<typename>,greater<typename>>name

優(yōu)先隊列模板 STL-priority_queue

1.定義

#include <queue>
using namespace std;
priority_queue<typename>name;

2.狀態(tài)
①隊空：是否為空 empty()
②隊長：元素個數(shù) size()

3.增刪元素
①出隊：插入元素 push()
②入隊：刪除元素 pop()

4.元素訪問
隊首：只能訪問優(yōu)先級最高的元素 top()

優(yōu)先隊列的應(yīng)用

1.順序問題

運(yùn)算符重載

重載小于運(yùn)算符：operator <

2.哈夫曼樹

1.求WPL(帶權(quán)路徑和)
①構(gòu)建哈夫曼樹，再求WPL：已掌握
②迭代式求WPL

---

例題1：哈夫曼樹 (北郵復(fù)試上機(jī)真題)
提交網(wǎng)址：http://t.cn/AiCuGMki

#include <cstdio>
#include <queue>
using namespace std;int main(){priority_queue<int> pqueue;int n;scanf("%d",&n);for(int i = 0; i < n; ++i){int weight;scanf("%d",&weight);pqueue.push(-weight);}int res = 0; //存儲帶權(quán)路徑長度和的中間結(jié)果while(pqueue.size()>1){int leaf1 = pqueue.top();pqueue.pop();int leaf2 = pqueue.top();pqueue.pop();res += leaf1 + leaf2;pqueue.push(leaf1+leaf2);}printf("%d\n",-res);return 0;
}

---

4.散列表 map

映射 map

1.map底層：紅黑樹 (RBT∈BST)，
2.特點(diǎn)：所以map會自動排好序 (BST中序遍歷是升序序列)。
3.map查找：時間復(fù)雜度 O(logn) （和二分查找相同的時間復(fù)雜度，但比二分查找需要更多的空間）
4.操作

(1)頭文件

#include <map>
using namespace std;

定義

map<string,int> myMap;

初始化：

map<string,int> myMap = {{"Caixukun",1},{"Wuyifan",2},{"Liyifeng",3}
};

(2)插入鍵值對
①insert()方法

myMap.insert(pair<string,int>("Wuyifan",2));

②[]下標(biāo)訪問運(yùn)算符

myMap["Caixukun"] = 1;

刪除鍵值對：erase()

myMap.erase("Wuyifan");

讀取鍵對應(yīng)的值：

(3)判空：empty()
求長度(獲取鍵值對個數(shù))：size()

(4)map的遍歷：迭代器 iterator (迭代器是指向內(nèi)部元素的指針)
①定義迭代器：map<string,int>::iterator it;
②第一個成員的位置：.begin()
③尾后位置：.end()
④迭代器指針后移：++it ? (++it使得迭代器指針指向下一對鍵值對，unorder_map不支持此操作)
⑤鍵：it->first
⑥值：it->second

map<string,int>::iterator it;
for(it = myMap.begin();it != myMap.end();++it){printf("%s %d\n",it->first.c_str(),it->second);
}

(5)查找某個鍵是否存在：find()函數(shù)

---

例題1：查找學(xué)生信息 （清華大學(xué)復(fù)試上機(jī)題）
提交網(wǎng)址：http://t.cn/AiCuVIuY

#include <cstdio>
#include <string>
#include <map>
using namespace std;struct Student{string name;string gender;int age;
};int main(){int n;scanf("%d",&n);map<string,Student> InfoMap;for(int i = 0; i < n; ++i){char num[30];char name[30];char gender[30];int age;scanf("%s %s %s %d",num,name,gender,&age);//key stringstring numstr = num;//value StudentStudent student;student.name = name;student.gender = gender;student.age = age;InfoMap[numstr] = student;}int m;scanf("%d",&m);for(int i = 0; i < m; ++i){char num[30];scanf("%s",num);string numstr = num;if(InfoMap.find(numstr) != InfoMap.end()){//找到了printf("%s %s %s %d\n",numstr.c_str(),InfoMap[numstr].name.c_str(),InfoMap[numstr].gender.c_str(),InfoMap[numstr].age);}else{//學(xué)號沒找到printf("No Answer!\n");//這里漏加換行符\n，導(dǎo)致格式錯誤了好幾次。}}
}

例題2：魔咒詞典 （浙大上機(jī)復(fù)試真題）
提交網(wǎng)址：http://t.cn/AiCufczt

#include <cstdio>
#include <string>
#include <map>
using namespace std;//魔咒詞典  (采用 增量編輯法：即寫一部分，測試一部分)
int main(){map<string,string> dict;while(true){char line[200];fgets(line,200,stdin);//輸入一行string linestr = line;linestr.pop_back();//干掉回車，string最后一個字符為\nif("@END@" == linestr){break;}
//        printf("%s\n",linestr.c_str());int pos = linestr.find("]");string word = linestr.substr(0,pos+1);string info = linestr.substr(pos+2);
//        printf("word = %s, info = %s\n",word.c_str(),info.c_str());dict[word] = info;dict[info] = word;}int n;scanf("%d",&n);getchar();//吃掉回車 ※for(int i = 0 ; i < n; ++i){char line[200];fgets(line,200,stdin);string linestr = line;linestr.pop_back();if(dict.find(linestr) != dict.end()){//存在魔咒或功能if('[' == linestr[0]){//輸入魔咒，查找功能printf("%s\n",dict[linestr].c_str());}else{//輸入功能查找魔咒string charm = dict[linestr];//[xxxxxx],想辦法去掉[]string charm_sub = charm.substr(1,charm.size()-2);//取子串，去掉了[]printf("%s\n",charm_sub.c_str());}}else{//不存在該魔咒或功能printf("what?\n");}}
}

---

unorder_map

1.底層：HashTable 散列表
2.unorder_map查找：時間復(fù)雜度O(1)
3.特點(diǎn)：①空間特別大 ②無序，不能遍歷

七、搜索

搜索問題，就是帶有限制的枚舉問題。

BFS 廣度優(yōu)先搜索

BFS，Breadth First Search，廣度優(yōu)先搜索(寬度優(yōu)先搜索)。
為了求最優(yōu)解問題

---

例題1：Catch that Cow

例題2：Find the Multiple

---

打表

當(dāng)OJ時限很小，且輸入范圍有限（1≤n≤200）

---

還是上文例題2：Find the Multiple，用打表法解決

---

DFS 深度優(yōu)先搜索

DFS，Depth First Search，深度優(yōu)先搜索。
為了知道問題是否有解，例如找迷宮出口

---

例題1：A Knight’s Journey
例題2：Square

---

剪枝算法

在深度優(yōu)先遍歷搜索過程中，可以通過放棄對某些不可能產(chǎn)生結(jié)果的子集的搜索，達(dá)到提高效率的目的。這樣的技術(shù)稱為剪枝。