第一章 數(shù)據(jù)結(jié)構(gòu)與算法
算法---是一組嚴(yán)謹(jǐn)?shù)囟x運(yùn)算順序的規(guī)則
算法的基本要素---一是對(duì)數(shù)據(jù)對(duì)象的運(yùn)算和操作，二是算法的控制結(jié)構(gòu)
算法設(shè)計(jì)基本方法---列舉法、歸納法、遞推、遞歸、減半遞推
算法的復(fù)雜度---包括時(shí)間復(fù)雜度和空間復(fù)雜度
時(shí)間復(fù)雜度---執(zhí)行算法所需的計(jì)算工作量
空間復(fù)雜度---執(zhí)行算法所需的內(nèi)存空間
數(shù)據(jù)結(jié)構(gòu)---相互有關(guān)聯(lián)的數(shù)據(jù)元素的集合。如春、夏、秋、冬；18、11、35、23、16。。。；父親、兒子、女兒等都是數(shù)據(jù)元素。
前件---數(shù)據(jù)元素之間的關(guān)系，如父親是兒子和女兒的前件
后件---如兒子是父親的后件
結(jié)構(gòu)---指數(shù)據(jù)元素之間的前后件關(guān)系
數(shù)據(jù)的邏輯結(jié)構(gòu)—是指反映數(shù)據(jù)元素之間邏輯關(guān)系，而與它們?cè)谟?jì)算機(jī)中的存儲(chǔ)位置無(wú)關(guān)
數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)（物理結(jié)構(gòu)）---數(shù)據(jù)的邏輯結(jié)構(gòu)在計(jì)算機(jī)存儲(chǔ)空間中的存放形式，數(shù)據(jù)元素在計(jì)算機(jī)存儲(chǔ)空間的位置關(guān)系可能與邏輯關(guān)系不同。
根據(jù)數(shù)據(jù)結(jié)構(gòu)中各數(shù)據(jù)元素之間前后件關(guān)系的復(fù)雜程度，可將數(shù)據(jù)結(jié)構(gòu)分兩類---線性結(jié)構(gòu)與非線性結(jié)構(gòu)
線性結(jié)構(gòu)（線性表）---滿足下列兩個(gè)條件（1）有且只有一個(gè)根結(jié)點(diǎn)（2）每一個(gè)結(jié)點(diǎn)最多有一個(gè)前件和后件。則稱該數(shù)據(jù)結(jié)構(gòu)為線性結(jié)構(gòu)，否則為非線性結(jié)構(gòu)。
線性表是最簡(jiǎn)單、最常用的一種數(shù)據(jù)結(jié)構(gòu)，其數(shù)據(jù)元素之間的相對(duì)位置是線性的，其存儲(chǔ)方式為順序存儲(chǔ)的，如數(shù)組
棧---是限定在一端進(jìn)行插入與刪除的線性表，一端封閉，另一端開口，其操作原則是“先進(jìn)后出”，棧的運(yùn)算有入棧、退棧、讀棧頂元素
隊(duì)列---是指在一端進(jìn)行插入（稱為隊(duì)尾）而在另一端進(jìn)行刪除（稱為隊(duì)頭）的線性表，其操作規(guī)則是“先進(jìn)先出”，其運(yùn)算有入隊(duì)和退隊(duì)。
樹---是一種簡(jiǎn)單的非線性結(jié)構(gòu)，而且是層次結(jié)構(gòu)，是倒立的大樹，有根結(jié)點(diǎn)、父結(jié)點(diǎn)、子結(jié)點(diǎn)、葉子結(jié)點(diǎn)。根結(jié)點(diǎn)在第一層，一個(gè)結(jié)點(diǎn)所擁有的后件的個(gè)數(shù)稱為該結(jié)點(diǎn)的度，所有結(jié)點(diǎn)中的度稱為 樹的度，樹的層次稱為樹的深度。
二叉樹---（1）非空二叉樹只有一個(gè)根結(jié)點(diǎn)（2）每一個(gè)結(jié)點(diǎn)最多有兩棵子樹（左子樹和右子樹），其存儲(chǔ)結(jié)構(gòu)為鏈?zhǔn)健?BR> 二叉樹性質(zhì)---（1）K層上最多有2（K-1）個(gè)結(jié)點(diǎn)（2）深度為m的二叉樹最多有2m-1個(gè)結(jié)點(diǎn)
（3）度為0的結(jié)點(diǎn)（葉子結(jié)點(diǎn)）比度為2的結(jié)點(diǎn)多一個(gè)（4）具有n個(gè)結(jié)點(diǎn)的二叉樹，其深度至少為[Log2n]+1，其中[Log2n]表示對(duì)Log2n取整
滿二叉樹---除最后一層外，其余層的結(jié)點(diǎn)都有兩個(gè)子結(jié)點(diǎn)
完全二叉樹---除最后一層外，每一層上的結(jié)點(diǎn)數(shù)均達(dá)到值，在最后一層上只缺少右邊的若干結(jié)點(diǎn)，葉子結(jié)點(diǎn)只可能在層次的兩層上出現(xiàn)。滿二叉樹是完全二叉樹，而完全二叉樹不是滿二叉樹。完全二叉樹有兩個(gè)性質(zhì)：（1）具有n個(gè)結(jié)點(diǎn)的完全二叉樹的深度為[Log2n]+1（2）
二叉樹遍歷---不重復(fù)地訪問各個(gè)結(jié)點(diǎn)。分為前序遍歷(DLR-根左右)、中序遍歷(LDR-左根右)和后序遍歷（LRD-左右根）
查找技術(shù)---順序查找——對(duì)于長(zhǎng)度為n的有序線性表，查找時(shí)需要比較n次
二分法查找——對(duì)于長(zhǎng)度為n的有序線性表，查找時(shí)需要比較log2n次
排序技術(shù)---假設(shè)線性表的長(zhǎng)度為n，則冒泡排序和簡(jiǎn)單插入排序的比較次數(shù)（時(shí)間復(fù)雜度）為n(n-1)/2;希爾排序的比較次數(shù)為O(n1.5);簡(jiǎn)單選擇排序的比較次數(shù)為n(n-1)/2;堆排序的比較次數(shù)為O(nlog2n).
習(xí)題1
算法的時(shí)間復(fù)雜度是指（ ），算法的空間復(fù)雜度是指（ ）；
隊(duì)列是（先進(jìn)先出），棧是（先進(jìn)后出）；
下列二叉樹的遍歷結(jié)果：前序遍歷（ABDECF）、中序遍歷（DBEAFC）、后續(xù)遍歷（DEBFCA）；
在深度為5的滿二叉樹中，葉子結(jié)點(diǎn)的個(gè)數(shù)為（16）；設(shè)樹T的度為4，其中度為1，2，3；
線性表、棧、隊(duì)列、線性鏈表是（線性結(jié)構(gòu)），樹是（非線性結(jié)構(gòu)）；數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)是指（ ）；，4的結(jié)點(diǎn)的個(gè)數(shù)分別為4，2，1，1。則T中的葉子結(jié)點(diǎn)的個(gè)數(shù)為（8）；對(duì)于長(zhǎng)度為n的有序線性表，順序查找次數(shù)為（n）,二分法查找次數(shù)為（log2n）；一棵完全二叉樹共有700個(gè)結(jié)點(diǎn)，則在該二叉樹中有（350）個(gè)葉子結(jié)點(diǎn)；一棵二叉樹的中序遍歷結(jié)果為DBEAFC，前序遍歷結(jié)果為ABDECF，則后續(xù)遍歷結(jié)果為（DEBFCA）；冒泡排序的時(shí)間復(fù)雜度為（n(n-1)/2）;在一個(gè)容量為15的循環(huán)隊(duì)列中，若頭指針front=6,尾指針rear=9,則該循環(huán)隊(duì)列中共有（3）元素；
算法---是一組嚴(yán)謹(jǐn)?shù)囟x運(yùn)算順序的規(guī)則
算法的基本要素---一是對(duì)數(shù)據(jù)對(duì)象的運(yùn)算和操作，二是算法的控制結(jié)構(gòu)
算法設(shè)計(jì)基本方法---列舉法、歸納法、遞推、遞歸、減半遞推
算法的復(fù)雜度---包括時(shí)間復(fù)雜度和空間復(fù)雜度
時(shí)間復(fù)雜度---執(zhí)行算法所需的計(jì)算工作量
空間復(fù)雜度---執(zhí)行算法所需的內(nèi)存空間
數(shù)據(jù)結(jié)構(gòu)---相互有關(guān)聯(lián)的數(shù)據(jù)元素的集合。如春、夏、秋、冬；18、11、35、23、16。。。；父親、兒子、女兒等都是數(shù)據(jù)元素。
前件---數(shù)據(jù)元素之間的關(guān)系，如父親是兒子和女兒的前件
后件---如兒子是父親的后件
結(jié)構(gòu)---指數(shù)據(jù)元素之間的前后件關(guān)系
數(shù)據(jù)的邏輯結(jié)構(gòu)—是指反映數(shù)據(jù)元素之間邏輯關(guān)系，而與它們?cè)谟?jì)算機(jī)中的存儲(chǔ)位置無(wú)關(guān)
數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)（物理結(jié)構(gòu)）---數(shù)據(jù)的邏輯結(jié)構(gòu)在計(jì)算機(jī)存儲(chǔ)空間中的存放形式，數(shù)據(jù)元素在計(jì)算機(jī)存儲(chǔ)空間的位置關(guān)系可能與邏輯關(guān)系不同。
根據(jù)數(shù)據(jù)結(jié)構(gòu)中各數(shù)據(jù)元素之間前后件關(guān)系的復(fù)雜程度，可將數(shù)據(jù)結(jié)構(gòu)分兩類---線性結(jié)構(gòu)與非線性結(jié)構(gòu)
線性結(jié)構(gòu)（線性表）---滿足下列兩個(gè)條件（1）有且只有一個(gè)根結(jié)點(diǎn)（2）每一個(gè)結(jié)點(diǎn)最多有一個(gè)前件和后件。則稱該數(shù)據(jù)結(jié)構(gòu)為線性結(jié)構(gòu)，否則為非線性結(jié)構(gòu)。
線性表是最簡(jiǎn)單、最常用的一種數(shù)據(jù)結(jié)構(gòu)，其數(shù)據(jù)元素之間的相對(duì)位置是線性的，其存儲(chǔ)方式為順序存儲(chǔ)的，如數(shù)組
棧---是限定在一端進(jìn)行插入與刪除的線性表，一端封閉，另一端開口，其操作原則是“先進(jìn)后出”，棧的運(yùn)算有入棧、退棧、讀棧頂元素
隊(duì)列---是指在一端進(jìn)行插入（稱為隊(duì)尾）而在另一端進(jìn)行刪除（稱為隊(duì)頭）的線性表，其操作規(guī)則是“先進(jìn)先出”，其運(yùn)算有入隊(duì)和退隊(duì)。
樹---是一種簡(jiǎn)單的非線性結(jié)構(gòu)，而且是層次結(jié)構(gòu)，是倒立的大樹，有根結(jié)點(diǎn)、父結(jié)點(diǎn)、子結(jié)點(diǎn)、葉子結(jié)點(diǎn)。根結(jié)點(diǎn)在第一層，一個(gè)結(jié)點(diǎn)所擁有的后件的個(gè)數(shù)稱為該結(jié)點(diǎn)的度，所有結(jié)點(diǎn)中的度稱為 樹的度，樹的層次稱為樹的深度。
二叉樹---（1）非空二叉樹只有一個(gè)根結(jié)點(diǎn)（2）每一個(gè)結(jié)點(diǎn)最多有兩棵子樹（左子樹和右子樹），其存儲(chǔ)結(jié)構(gòu)為鏈?zhǔn)健?BR> 二叉樹性質(zhì)---（1）K層上最多有2（K-1）個(gè)結(jié)點(diǎn)（2）深度為m的二叉樹最多有2m-1個(gè)結(jié)點(diǎn)
（3）度為0的結(jié)點(diǎn)（葉子結(jié)點(diǎn)）比度為2的結(jié)點(diǎn)多一個(gè)（4）具有n個(gè)結(jié)點(diǎn)的二叉樹，其深度至少為[Log2n]+1，其中[Log2n]表示對(duì)Log2n取整
滿二叉樹---除最后一層外，其余層的結(jié)點(diǎn)都有兩個(gè)子結(jié)點(diǎn)
完全二叉樹---除最后一層外，每一層上的結(jié)點(diǎn)數(shù)均達(dá)到值，在最后一層上只缺少右邊的若干結(jié)點(diǎn)，葉子結(jié)點(diǎn)只可能在層次的兩層上出現(xiàn)。滿二叉樹是完全二叉樹，而完全二叉樹不是滿二叉樹。完全二叉樹有兩個(gè)性質(zhì)：（1）具有n個(gè)結(jié)點(diǎn)的完全二叉樹的深度為[Log2n]+1（2）
二叉樹遍歷---不重復(fù)地訪問各個(gè)結(jié)點(diǎn)。分為前序遍歷(DLR-根左右)、中序遍歷(LDR-左根右)和后序遍歷（LRD-左右根）
查找技術(shù)---順序查找——對(duì)于長(zhǎng)度為n的有序線性表，查找時(shí)需要比較n次
二分法查找——對(duì)于長(zhǎng)度為n的有序線性表，查找時(shí)需要比較log2n次
排序技術(shù)---假設(shè)線性表的長(zhǎng)度為n，則冒泡排序和簡(jiǎn)單插入排序的比較次數(shù)（時(shí)間復(fù)雜度）為n(n-1)/2;希爾排序的比較次數(shù)為O(n1.5);簡(jiǎn)單選擇排序的比較次數(shù)為n(n-1)/2;堆排序的比較次數(shù)為O(nlog2n).
習(xí)題1
算法的時(shí)間復(fù)雜度是指（ ），算法的空間復(fù)雜度是指（ ）；
隊(duì)列是（先進(jìn)先出），棧是（先進(jìn)后出）；
下列二叉樹的遍歷結(jié)果：前序遍歷（ABDECF）、中序遍歷（DBEAFC）、后續(xù)遍歷（DEBFCA）；
在深度為5的滿二叉樹中，葉子結(jié)點(diǎn)的個(gè)數(shù)為（16）；設(shè)樹T的度為4，其中度為1，2，3；
線性表、棧、隊(duì)列、線性鏈表是（線性結(jié)構(gòu)），樹是（非線性結(jié)構(gòu)）；數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)是指（ ）；，4的結(jié)點(diǎn)的個(gè)數(shù)分別為4，2，1，1。則T中的葉子結(jié)點(diǎn)的個(gè)數(shù)為（8）；對(duì)于長(zhǎng)度為n的有序線性表，順序查找次數(shù)為（n）,二分法查找次數(shù)為（log2n）；一棵完全二叉樹共有700個(gè)結(jié)點(diǎn)，則在該二叉樹中有（350）個(gè)葉子結(jié)點(diǎn)；一棵二叉樹的中序遍歷結(jié)果為DBEAFC，前序遍歷結(jié)果為ABDECF，則后續(xù)遍歷結(jié)果為（DEBFCA）；冒泡排序的時(shí)間復(fù)雜度為（n(n-1)/2）;在一個(gè)容量為15的循環(huán)隊(duì)列中，若頭指針front=6,尾指針rear=9,則該循環(huán)隊(duì)列中共有（3）元素；