圖片發(fā)自簡書App

這是自己當(dāng)年復(fù)習(xí)java時(shí)候留下的披诗，所有的編程類的都要考闲延。沒有多少自己的東西，都是書上自己覺得重要的地方告丢，最后考的基本上都在里面吧枪蘑。如果想拿優(yōu)（90分以上），這部分必須拿分（其他部分不能丟分）岖免。最好看一下網(wǎng)上的一些模擬題或者真題岳颇，好像都是考那幾個(gè)點(diǎn)。有些地方?jīng)]寫全颅湘，反正都在書上话侧。

1. 算法基本特征：
   • 可行性：每個(gè)步驟能夠?qū)崿F(xiàn)；結(jié)果能達(dá)到預(yù)期闯参；
   • 確定性
   • 有窮性
   • 擁有足夠多的情報(bào)
2. 算法設(shè)計(jì)基本方法
   • 列舉法
   • 歸納法
   • 遞推
   • 遞歸
     • 自己調(diào)用自己的過程稱為遞歸調(diào)用過程
   • 減半遞推技術(shù)
     • 二分法求方程實(shí)根
   • 回溯法
3. 算法的復(fù)雜程度
   • 算法時(shí)間復(fù)雜度：算法的工作量與算法所執(zhí)行的基本運(yùn)算次數(shù)以及問題的規(guī)模有關(guān)瞻鹏，而有時(shí)算法所執(zhí)行的基本運(yùn)算次數(shù)與特定的輸入有關(guān)
     • 平均性態(tài)：各種特定輸入下基本運(yùn)算次數(shù)的加權(quán)平均值悲立。A(n)
     • 最壞情況復(fù)雜性：在規(guī)模為n時(shí)，算法所執(zhí)行的基本運(yùn)算的最大次數(shù)新博。W(n)薪夕。比A(n)更具有實(shí)用價(jià)值。
   • 算法的空間復(fù)雜度：執(zhí)行這個(gè)算法所需要的內(nèi)存空間叭披。
4. 數(shù)據(jù)結(jié)構(gòu)：
   • 數(shù)據(jù)結(jié)構(gòu)是指反應(yīng)數(shù)據(jù)元素之間關(guān)系的數(shù)據(jù)元素集合的表示寥殖。
   • 數(shù)據(jù)處理：是指對數(shù)據(jù)集合中的各元素以各種方式進(jìn)行運(yùn)算，包括插入涩蜘、刪除嚼贡、查找、更改等同诫，也包括對數(shù)據(jù)元素進(jìn)行分析粤策。
   • 前后件關(guān)系是數(shù)據(jù)元素之間的一個(gè)基本關(guān)系，數(shù)據(jù)元素之間的任何關(guān)系都可以用前后件關(guān)系來描述误窖。
5. 數(shù)據(jù)的邏輯結(jié)構(gòu)：
   • 一個(gè)數(shù)據(jù)結(jié)構(gòu)應(yīng)該包括：
     • 表示數(shù)據(jù)元素的信息
     • 表示各元素之間的前后件關(guān)系
       其中叮盘，數(shù)據(jù)元素之間的前后件關(guān)系是指它們的邏輯關(guān)系，與它們在計(jì)算機(jī)中的存儲(chǔ)位置無關(guān)
   • B=（D霹俺，R） data柔吼，relation
6. 數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)
   • 數(shù)據(jù)的邏輯結(jié)構(gòu)在計(jì)算機(jī)存儲(chǔ)空間中的存放形式稱為數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)
   • 常用的存儲(chǔ)結(jié)構(gòu)：順序、鏈接丙唧、索引
7. 線性結(jié)構(gòu)與非線性結(jié)構(gòu)
   • 如果在一個(gè)數(shù)據(jù)結(jié)構(gòu)中一個(gè)元素都沒有愈魏，則稱該數(shù)據(jù)結(jié)構(gòu)為空的數(shù)據(jù)結(jié)構(gòu)
   • 線性結(jié)構(gòu)（線性表）：
     • 有且只有一個(gè)根結(jié)點(diǎn)
     • 每一個(gè)結(jié)點(diǎn)最多有一個(gè)前件，也最多有一個(gè)后件
     • 在一個(gè)線性結(jié)構(gòu)中插入或刪除任何一個(gè)結(jié)點(diǎn)后還應(yīng)是線性結(jié)構(gòu)
   • 非線性結(jié)構(gòu)：不是線性就是非線性
   • 一個(gè)空的數(shù)據(jù)結(jié)構(gòu)是線性還是非線性根據(jù)具體情況確定想际，如果對該數(shù)據(jù)結(jié)構(gòu)的運(yùn)算是按線性結(jié)構(gòu)規(guī)則處理的則屬于線性結(jié)構(gòu)培漏，否則屬于非線性結(jié)構(gòu)。
8. 線性表及其順序存儲(chǔ)結(jié)構(gòu)
   • 線性表是由n個(gè)數(shù)據(jù)元素組成的一個(gè)有限序列胡本，表中的每一個(gè)元素牌柄，除了第一個(gè)以外，有且只有一個(gè)前件侧甫，除了最后一個(gè)外珊佣，有且只有一個(gè)后件。
   • 矩陣也是一個(gè)線性表
   • 復(fù)雜線性表中披粟，由若干數(shù)據(jù)項(xiàng)組成的數(shù)據(jù)元素稱為記錄咒锻，由多個(gè)紀(jì)錄構(gòu)成的線性表又稱為文件。
   • 線性表的順序存儲(chǔ)結(jié)構(gòu)：
     • 線性表中所有元素所占的存儲(chǔ)空間是連續(xù)的僻爽。
     • 線性表中個(gè)數(shù)據(jù)元素在存儲(chǔ)空間中是按邏輯順序依次存放的。
   • 順序表的插入運(yùn)算：效率低贾惦，可能發(fā)生“上溢”錯(cuò)誤
   • 順序表的刪除運(yùn)算：效率低胸梆，可能發(fā)生“下溢”錯(cuò)誤
9. 棧和隊(duì)列
   • 棧：限定在一端進(jìn)行插入和刪除的線性表
     • 在順序存儲(chǔ)結(jié)構(gòu)下敦捧，對棧的插入與刪除時(shí)不需要移動(dòng)表中其他數(shù)據(jù)元素的
     • 允許插入與刪除的一端稱為棧頂，不允許插入和刪除的一端稱為棧底
     • 先進(jìn)后出碰镜、后進(jìn)先出（FILO兢卵、LIFO），棧具有記憶功能
     • 通常用指針top來指示棧頂?shù)奈恢眯饔保弥羔榖ottom指向棧底
     • 在棧中插入一個(gè)元素稱為入棧運(yùn)算秽荤，刪除一個(gè)元素稱為退棧運(yùn)算
     • 棧的順序存儲(chǔ)及運(yùn)算
       • 入棧運(yùn)算
       • 退棧運(yùn)算
       • 讀棧頂元素
   • 隊(duì)列：指允許在一端進(jìn)行插入，而在另外一端進(jìn)行刪除的線性表
     • 允許插入的一端稱為隊(duì)尾柠横，通常用一個(gè)尾指針（rear）指向隊(duì)尾元素窃款；允許刪除的一端稱為排頭（隊(duì)頭），通常用排頭指針（front）指向排頭元素的前一個(gè)位置牍氛。
     • 先進(jìn)先出晨继、后進(jìn)后出（FIFO、LILO）
     • 在隊(duì)尾插入一個(gè)元素稱為入隊(duì)運(yùn)算搬俊，從排頭刪除一個(gè)元素稱為退隊(duì)運(yùn)算紊扬。
     • 循環(huán)隊(duì)列：實(shí)際應(yīng)用中，隊(duì)列的順序存儲(chǔ)結(jié)構(gòu)一般采用循環(huán)隊(duì)列的形式唉擂。Front=rear時(shí)餐屎，隊(duì)列要么為空，要么為滿玩祟，所以要加一個(gè)標(biāo)志s腹缩，s=0為空，1為非空卵凑。
10. 線性鏈表
    • 鏈?zhǔn)酱鎯?chǔ)方式中庆聘，要求每個(gè)結(jié)點(diǎn)由兩部分組成：一部分用于存放數(shù)據(jù)元素值，稱為數(shù)據(jù)域勺卢，另一部分用于存放指針伙判，稱為指針域。其中指針用于指向該結(jié)點(diǎn)的前一個(gè)或后一個(gè)結(jié)點(diǎn)黑忱。
    • 線性表的鏈?zhǔn)酱鎯?chǔ)方式稱為線性鏈表：指針域用于存放指向下一個(gè)元素的存儲(chǔ)序號宴抚。
    • 雙向鏈表：一個(gè)左指針（Llink）指向前件結(jié)點(diǎn)，一個(gè)右（Rlink）指針指向后件結(jié)點(diǎn)甫煞。
    • 帶鏈的棧：
    • 帶棧的隊(duì)列：
    • 循環(huán)鏈表：增加一個(gè)表頭結(jié)點(diǎn)菇曲，最后一個(gè)結(jié)點(diǎn)的指針域不為空，而是指向表頭結(jié)點(diǎn)抚吠。
      • 只要指出表中任意結(jié)點(diǎn)位置常潮，就可以從它出發(fā)訪問到表中其他所有的結(jié)點(diǎn)，線性單鏈表做不到楷力。
      • 由于設(shè)置表頭結(jié)點(diǎn)喊式，因此孵户，在任何情況下循環(huán)鏈表中至少有一個(gè)結(jié)點(diǎn)，使空表與非空表運(yùn)算統(tǒng)一岔留。
11. 樹與二叉樹：
    • 樹中夏哭，每一個(gè)結(jié)點(diǎn)只有一個(gè)前件，稱為父結(jié)點(diǎn)献联，每一個(gè)節(jié)點(diǎn)可以有多個(gè)后件竖配，稱為子結(jié)點(diǎn)，沒有后件的結(jié)點(diǎn)稱為葉子結(jié)點(diǎn)里逆。一個(gè)結(jié)點(diǎn)所擁有的后件個(gè)數(shù)稱為該結(jié)點(diǎn)的度进胯，在樹中，所有結(jié)點(diǎn)中最大的度稱為樹的度运悲；在樹中龄减，所有節(jié)點(diǎn)的度之和再加一為樹的結(jié)點(diǎn)數(shù)。樹的最大層數(shù)稱為樹的深度班眯。
    • 二叉樹基本性質(zhì)：
      • 性質(zhì)一
      • 性質(zhì)二
      • 性質(zhì)三：在任意一顆二叉樹中希停，度為零的結(jié)點(diǎn)總是比度為2的結(jié)點(diǎn)多一個(gè)
      • 性質(zhì)四：
    • 滿二叉樹：每一層上的結(jié)點(diǎn)數(shù)都達(dá)到最大值
    • 完全二叉樹：除最后一層外，每一層上的結(jié)點(diǎn)數(shù)均達(dá)到最大值署隘，在最后一層上只缺少右邊的若干結(jié)點(diǎn)宠能。
      • 性質(zhì)五
      • 性質(zhì)六
    • 二叉樹存儲(chǔ)結(jié)構(gòu)：在計(jì)算機(jī)中，二叉樹通常采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)磁餐，對于滿二叉樹和完全二叉樹來說违崇，可以按層序進(jìn)行順序存儲(chǔ)。
    • 二叉樹的遍歷：
      • 前序遍歷（DLR）：根節(jié)點(diǎn)诊霹、左子樹羞延、右子樹
      • 中序遍歷（LDR）：左子樹、根節(jié)點(diǎn)脾还、右子樹
      • 后序遍歷（LRD）：左子樹伴箩、右子樹、根節(jié)點(diǎn)
      • 如果知道了前序序列和中序序列或者知道了中序序列和后序序列可以唯一地恢復(fù)該二叉樹鄙漏，但是知道了前序序列和后序序列嗤谚，不能唯一地恢復(fù)該二叉樹。
12. 查找技術(shù)：
    • 順序查找：對于大的線性表效率低怔蚌，但是對于無序表和鏈表只能用順序查找巩步。
    • 二分法查找：只適用于順序存儲(chǔ)的有序表
13. 排序技術(shù)：
    • 交換類排序方式：
      • 冒泡排序：最壞——n（n-1）/2
      • 快速排序：最壞——n（n-1）/2一般比冒泡要好
    • 插入類排序：
      • 簡單插入排序：最壞——n（n-1）/2效率與冒泡相同
      • 希爾排序：最壞效率與所選取增量有關(guān)
    • 選擇類排序：
      • 簡單選擇排序法：最壞——n（n-1）/2
      • 堆排序法：最壞——nlog2n，對于較小規(guī)模不適用桦踊，對于較大規(guī)模線性表很有效椅野。

OK，第一章是一些數(shù)據(jù)結(jié)構(gòu)什么的東西，基礎(chǔ)的基礎(chǔ)竟闪，計(jì)算機(jī)專業(yè)的應(yīng)該都沒問題声离，自學(xué)的話也應(yīng)該了解，畢竟這東西太基礎(chǔ)了瘫怜，也很重要。其實(shí)這一本書一個(gè)星期就沒問題了本刽，最主要的是了解還有理解鲸湃。在onenote上的筆記，轉(zhuǎn)markdown有點(diǎn)子寓，下面是onenote的鏈接暗挑，不知道能不能用。

ontenote鏈接