1.本周學習總結

1.思維導圖

2.對查找運算的認識及學習體會

查找的PTA題目集比前面樹和圖的更好做，他對編程的要求不是那么高，只要掌握幾種查找的思想，然后利用遞歸一直找下去就好，代碼量上面減少很多。而且，越學習到后面，發現容器越好用，比如編程第一題，就利用map容器來解決賬號存在問題，非常方便。通過PTA練習，我對map容器的了解也越來越多，這次在賬號與密碼配對上又運用到了。map中的find函數定位數據出現的位置，它返回一個迭代器，當數據出現時，它返回數據所在位置的迭代器；如果map中沒有要查找的數據，它返回的迭代器等于end函數返回的迭代器，這樣就實現查找目的。還有就是map<int, int>的元素是key-value對，而first和second分別對應key和value，it->first返回當前元素的關鍵字，it->second返回當前元素的值，查找密碼對不對就用到了這個知識點。

2.PTA實驗作業

2.1.題目1：二叉搜索樹的操作集

• 函數Insert將X插入二叉搜索樹BST并返回結果樹的根結點指針；
• 函數Delete將X從二叉搜索樹BST中刪除，并返回結果樹的根結點指針；如果X不在樹中，則打印一行Not Found并返回原樹的根結點指針；
• 函數Find在二叉搜索樹BST中找到X，返回該結點的指針；如果找不到則返回空指針；
• 函數FindMin返回二叉搜索樹BST中最小元結點的指針；
• 函數FindMax返回二叉搜索樹BST中最大元結點的指針。

輸入樣例：
10
5 8 6 2 4 1 0 10 9 7
5
6 3 10 0 5
5
5 7 0 10 3

輸出樣例：
Preorder: 5 2 1 0 4 8 6 7 10 9
6 is found
3 is not found
10 is found
10 is the largest key
0 is found
0 is the smallest key
5 is found
Not Found
Inorder: 1 2 4 6 8 9

2.1.1設計思路

• 插入函數

if（空樹）
    新建葉子節點，并將X的值存入
else
    if（X<當前遍歷節點的值）
        遞歸遍歷左子樹
    else
        遞歸遍歷右子樹

• 刪除函數

- if（空樹或者遍歷完都沒找到）
    輸出Not Found
- else if（X<當前節點的值）
    遞歸遍歷左子樹
- else if（X>當前節點的值）
    遞歸遍歷右子樹
- else（相等也就是找到了要刪除的節點）
    - if（該節點有兩個子樹）
        定義變量tmp接收查找最大值函數返回的值
        將左子樹的最大節點作為新的父親節點
        調整左子樹孩子間關系
    - else（有一個或沒有子樹）
        tmp暫存該節點的值
        - if（左孩子為空）
            將右孩子作為父親節點
        - else
            將左孩子作為父親節點
        free（tmp）釋放該節點
return 根節點

• 查找函數

- if（空樹或找到節點）return 根節點BST
- else
    - if（節點值>X）遞歸遍歷左子樹
    - else 遞歸遍歷右子樹

• 找最大值函數

- if（樹不空）
    while循環遍歷找到最右邊節點
    根據二叉搜索樹特點，此節點是最大的
返回 BST

• 找最小值函數

與找最大值函數方法一樣，遍歷找到最左邊節點即為最小值

輸入樣例：
10
5 8 6 2 4 1 0 10 9 7
5
6 3 10 0 5
5
5 7 0 10 3
輸出樣例：
Preorder: 5 2 1 0 4 8 6 7 10 9
6 is found
3 is not found
10 is found
10 is the largest key
0 is found
0 is the smallest key
5 is found
Not Found
Inorder: 1 2 4 6 8 9

2.1.2代碼截圖

• 插入函數

• 刪除函數

• 查找函數

• 找最大值函數

• 找最小值函數

2.1.3本題PTA提交列表說明

2.2 題目2：是否二叉搜索樹

2.2.1設計思路

判斷是不是二叉搜索樹首先想到了老師說的用中序遍歷的方法，如果他是遞增數列，那么就是一棵二叉搜索樹
利用中序遍歷思想首先有個問題要解決，就是這么存儲遍歷的節點值的問題，使得他可以和前一個比較
第一個想到的是數組，但發現這是一個函數題，不能自己隨便定義，后面查資料發現可以把數組定義寫在函數外面作為全局變量】
如下代碼：
定義數字a【100】存儲樹節點的值
定義IsBST函數利用遞歸中序遍歷判斷是不是二叉搜索樹
    if（樹不空）
        遞歸遍歷左子樹
        將節點的值存入數組a，變量 i 記錄數組長度
        遞歸遍歷右子樹
    end if
    for循環遍歷數組 a 
        if（數組后面的值大于他前面的值）
            return false
    循環完后沒問題就return true

另外一種思路就是不開數組，定義一個中間變量temp，邊遍歷邊比較
temp一開始給它一個初值為負無窮
- IsBST遞歸遍歷左子樹
讓所遍歷的節點值和temp比較
- if（節點值>temp）//符合要求
    temp保存該節點的值
- else
    return false
- IsBST遞歸遍歷右子樹

2.2.2代碼截圖

2.2.3本題PTA提交列表說明

2.3 題目3：QQ帳戶的申請與登陸

輸入格式:
輸入首先給出一個正整數N（≤100000）隨后給出N行指令。每行指令的格式為：“命令符（空格）QQ號碼（空格）密碼”。其中命令符為“N”（代表New）時表示要新申請一個QQ號，后面是新帳戶的號碼和密碼；
命令符為“L”（代表Login）時表示是老帳戶登陸，后面是登陸信息。QQ號碼為一個不超過10位、但大于1000（據說QQ老總的號碼是1001）的整數。密碼為不小于6位、不超過16位、且不包含空格的字符串。

輸出格式:
針對每條指令，給出相應的信息：
1）若新申請帳戶成功，則輸出“New: OK”；
2）若新申請的號碼已經存在，則輸出“ERROR: Exist”；
3）若老帳戶登陸成功，則輸出“Login: OK”；
4）若老帳戶QQ號碼不存在，則輸出“ERROR: Not Exist”；
5）若老帳戶密碼錯誤，則輸出“ERROR: Wrong PW”。

輸入樣例:
5
L 1234567890 myQQ@qq.com
N 1234567890 myQQ@qq.com
N 1234567890 myQQ@qq.com
L 1234567890 myQQ@qq
L 1234567890 myQQ@qq.com

輸出樣例:
ERROR: Not Exist
New: OK
ERROR: Exist
ERROR: Wrong PW
Login: OK

2.3.1設計思路

定義map容器存放賬號和密碼
- 主函數
登入類型，賬號和密碼定義為string類型，一開始我在想空格讀進去不就一整串了嗎，后面查一下發現c++中string一般遇到空格就結束
for循環輸入并判斷合不合法

- 判斷合法性函數
定義字符串str并初值為N
- if（type為N）//注冊
    - if（未找到該賬號）
        該賬號對應的密碼為password
        輸出New：OK
    - else該賬號已存在
        輸出ERROR：Exist
- else//登入
    - if（未找到賬號）
        輸出ERROR:Not Exist
    - else//判斷密碼正不正確
        - if（該賬號對應的密碼為輸入的password）
            輸出Login：OK
        - else 輸出ERROR：WrongPW

2.3.2代碼截圖

• 主函數
  

• 判斷函數
  
  

2.3.3本題PTA提交列表說明

• Q1：主函數中加上insert函數會出現如下錯誤
  
  
• A1：查了一下就是叫你不要畫蛇添足寫這句的意思，噗。。。

2.4題目4：航空公司VIP客戶查詢

現給定某航空公司全體會員的飛行記錄，要求實現根據身份證號碼快速查詢會員里程積分的功能。
輸入格式:
輸入首先給出兩個正整數N（≤100000）和K（≤500）。其中K是最低里程，即為照顧乘坐短程航班的會員,航空公司還會將航程低于K公里的航班也按K公里累積。隨后N行，每行給出一條飛行記錄。飛行記錄的輸入格式為：18位身份證號碼（空格）飛行里程。其中身份證號碼由17位數字加最后一位校驗碼組成，校驗碼的取值范圍為0~9和x共11個符號；飛行里程單位為公里，是(0, 15 000]區間內的整數。然后給出一個正整數M（≤100000）隨后給出M行查詢人的身份證號碼。
輸出格式:
對每個查詢人，給出其當前的里程累積值。如果該人不是會員，則輸出No Info。每個查詢結果占一行。
輸入樣例:
4 500
330106199010080419 499
110108198403100012 15000
120104195510156021 800
330106199010080419 1
4
120104195510156021
110108198403100012
330106199010080419
33010619901008041x
輸出樣例:
800
15000
1000
No Info

2.4.1設計思路

定義容器map，這題主要是身份證號那里，用整形存儲肯定查找時間復雜度巨大，所以巧妙運用了字符類型，同時也簡化了查找
IdNumber為char類型，distance為long long類型
- for循環輸入航班信息
    - if（里程<最小里程）distance賦值為最小里程k
    - if（未找到該身份證）//第一次坐飛機
       將distance作為idNumber的value
    - else//第二次乘坐
        - 對應idNumber的value加上distance
end for
- for循環讀入身份證信息
    - if（為找到該身份證）
        輸出“No Info”
    - else
        輸出對應idNumber下的value

2.4.2代碼截圖

2.4.3本題PTA提交列表說明

3.閱讀代碼

3.1 題目：打印學生選課清單

3.2 解題思路

此題是將字符型課程類型轉換為數字型，定義容器存放學生個數
核心算法思路：
- for循環輸入數據
    int h=shu(name);//將名字轉換成數字存在h中
    stu[h].push_back(id)//將書號放于名字對應的堆里面，構成一個數組棧
- for循環遍歷查找數據
    將前來查找學生的名字換成數字h
    利用sort函數對數字h里面的課程從小到大進行排序
    s=學生h的課程數，此處直接調用庫函數size（）即可
    后面就可以進行輸出操作了

3.3 代碼截圖

3.4 學習體會

這題主要巧在利用容器解決查找問題。題目要求的是輸出每個前來查詢學生選的課程數，那么就順著題目思路來，將課程劃分到每一個學生后面，這樣查找的時候，直接輸入學生名字就可以輸出對應的課程。此處還有一個就是sort排序函數，原來我只知道他適用于數組，用法為sort（數組名，長度），看完這題發現還可以寫成sort（begin，end），其實思想是一樣的，就是寫法不同。看一些大佬寫的代碼，總能發現一些有意思的東西，代碼簡短然后會有一些沒見過的代碼，學習后到后發現還蠻好用的，學無止境！