第1章資料結構與演算法
1.1 演算法的複雜度
1. 演算法的基本概念
利用計算機演算法為計算機解題的過程實際上是在實施某種演算法。
（1）演算法的基本特徵
演算法一般具有4個基本特徵：可行性、確定性、有窮性、擁有足夠的情報。
（2）演算法的基本運算和操作
演算法的基本運算和操作包括：算術運算、邏輯運算、關係運算、資料傳輸。
（3）演算法的3種基本控制結構
演算法的3種基本控制結構是：順序結構、選擇結構、迴圈結構。
（4）演算法基本設計方法
演算法基本設計方法：列舉法、歸納法、遞推、遞迴、減半遞推技術、回溯法。
（5）指令系統
所謂指令系統指的是乙個計算機系統能執行的所有指令的集合。
2. 演算法複雜度
演算法複雜度包括時間複雜度和空間複雜度。注意兩者的區別，無混淆，見表1-1。
1.2 資料結構
1.2.1 邏輯結構和儲存結構
1. 資料結構的基本概念
（1）資料結構
指相互有關聯的資料元素的集合。
（2）資料結構研究的3個方面
① 資料集合中各資料元素之間所固有的邏輯關係，即資料的邏輯結構；
② 在對資料進行處理時，各資料元素在計算機中的儲存關係，即資料的儲存結構；
③ 對各種資料結構進行的運算。
2. 邏輯結構
資料的邏輯結構是對資料元素之間的邏輯關係的描述，它可以用乙個資料元素的集合和定義在此集合中的若干關係來表示。資料的邏輯結構有兩個要素：一是資料元素的集合，通常記為d；二是d上的關係，它反映了資料元素之間的前後件關係，通常記為r。
乙個資料結構可以表示成：b=(d,r)
其中，b表示資料結構。為了反映d中各資料元素之間的前後件關係，一般用二元組來表示。
例如，如果把一年四季看作乙個資料結構，則可表示成：b =(d,r)
d =r =3. 儲存結構
資料的邏輯結構在計算機儲存空間中的存放形式稱為資料的儲存結構（也稱資料的物理結構）。
由於資料元素在計算機儲存空間中的位置關係可能與邏輯關係不同，因此，為了表示存放在計算機儲存空間中的各資料元素之間的邏輯關係（即前後件關係），在資料的儲存結構中，不僅要存放各資料元素的資訊，還需要存放各資料元素之間的前後件關係的資訊。
一種資料的邏輯結構根據需要可以表示成多種儲存結構，常用的儲存結構有順序、鏈結等儲存結構。
順序儲存方式主要用於線性的資料結構，它把邏輯上相鄰的資料元素儲存在物理上相鄰的儲存單元裡，結點之間的關係由儲存單元的鄰接關係來體現。
鏈式儲存結構就是在每個結點中至少包含乙個指標域，用指標來體現資料元素之間邏輯上的聯絡。
1.2.2 線性結構和非線性結構
根據資料結構中各資料元素之間前後件關係的複雜程度，一般將資料結構分為兩大型別：線性結構與非線性結構。
（1）如果乙個非空的資料結構滿足下列兩個條件：
① 有且只有乙個根結點；
② 每乙個結點最多有乙個前件，也最多有乙個後件。
則稱該資料結構為線性結構。線性結構又稱線性表。在乙個線性結構中插入或刪除任何乙個結點後還應是線性結構。棧、佇列、串等都為線性結構。
如果乙個資料結構不是線性結構，則稱之為非線性結構。陣列、廣義表、樹和圖等資料結構都是非線性結構。
（2）線性表的順序儲存結構具有以下兩個基本特點：
① 線性表中所有元素所佔的儲存空間是連續的；
② 線性表中各資料元素在儲存空間中是按邏輯順序依次存放的。
元素ai的儲存位址為：adr(ai)=adr(a1)+(i-1)k，adr(a1)為第乙個元素的位址，k代表每個元素佔的位元組數。
（3）順序表的運算有查詢、插入、刪除3種。
1.3 棧
1. 棧的基本概念
棧（stack）是一種特殊的線性表，是限定只在一端進行插入與刪除的線性表。
在棧中，一端是封閉的，既不允許進行插入元素，也不允許刪除元素；另一端是開口的，允許插入和刪除元素。通常稱插入、刪除的這一端為棧頂，另一端為棧底。當表中沒有元素時稱為空棧。
棧頂元素總是最後被插入的元素，從而也是最先被刪除的元素；棧底元素總是最先被插入的元素，從而也是最後才能被刪除的元素。
棧是按照「先進後出」或「後進先出」的原則組織資料的。例如，槍械的子彈匣就可以用來形象的表示棧結構。子彈匣的一端是完全封閉的，最後被壓入彈匣的子彈總是最先被彈出，而最先被壓入的子彈最後才能被彈出。
2. 棧的順序儲存及其運算
棧的基本運算有3種：入棧、退棧與讀棧頂元素。
① 入棧運算：在棧頂位置插入乙個新元素；
② 退棧運算：取出棧頂元素並賦給乙個指定的變數；
③ 讀棧頂元素：將棧頂元素賦給乙個指定的變數。
1.4 佇列
1. 佇列的基本概念
佇列是只允許在一端進行刪除，在另一端進行插入的順序表，通常將允許刪除的這一端稱為隊頭，允許插入的這一端稱為隊尾。當表中沒有元素時稱為空佇列。
佇列的修改是依照先進先出的原則進行的，因此佇列也稱為先進先出的線性表，或者後進後出的線性表。例如：火車進遂道，最先進遂道的是火車頭，最後是火車尾，而火車出遂道的時候也是火車頭先出，最後出的是火車尾。
若有佇列：
q =(q1,q2,…,qn)
那麼，q1為隊頭元素（排頭元素），qn為隊尾元素。佇列中的元素是按照q1，q2，…，qn的順序進入的，退出佇列也只能按照這個次序依次退出，即只有在q1，q2，…，qn-1都退隊之後，qn才能退出佇列。因最先進入佇列的元素將最先出隊，所以佇列具有先進先出的特性，體現「先來先服務」的原則。
隊頭元素q1是最先被插入的元素，也是最先被刪除的元素。隊尾元素qn是最後被插入的元素，也是最後被刪除的元素。因此，與棧相反，佇列又稱為「先進先出」（first in first out，簡稱fifo） 或「後進後出」（last in last out，簡稱lilo）的線性表。
2. 佇列運算
入隊運算是往佇列隊尾插入乙個資料元素；退隊運算是從佇列的隊頭刪除乙個資料元素。
佇列的順序儲存結構一般採用佇列迴圈的形式。迴圈佇列s=0表示佇列空；
1.5 鍊錶
在鏈式儲存方式中，要求每個結點由兩部分組成：一部分用於存放資料元素值，稱為資料域；另一部分用於存放指標，稱為指標域。其中指標用於指向該結點的前乙個或後乙個結點（即前件或後件）。
鏈式儲存方式既可用於表示線性結構，也可用於表示非線性結構。
（1）線性鍊錶
線性表的鏈式儲存結構稱為線性鍊錶。
在某些應用中，對線性鍊錶中的每個結點設定兩個指標，乙個稱為左指標，用以指向其前件結點；另乙個稱為右指標，用以指向其後件結點。這樣的表稱為雙向鍊錶。
**性煉表中，各資料元素結點的儲存空間可以是不連續的，且各資料元素的儲存順序與邏輯順序可以不一致。**性煉表中進行插入與刪除，不需要移動鍊錶中的元素。
線性單鏈表中，head稱為頭指標，head=null（或0）稱為空表。
如果是雙項鍊表的兩指標：左指標（llink）指向前件結點，右指標（rlink）指向後件結點。
線性鍊錶的基本運算：查詢、插入、刪除。
（2）帶鏈的棧
棧也是線性表，也可以採用鏈式儲存結構。帶鏈的棧可以用來收集計算機儲存空間中所有空閒的儲存結點，這種帶鏈的棧稱為可利用棧。
1.6 二叉樹
1.6.1 二叉樹概念及其基本性質
1. 二叉樹及其基本概念
二叉樹是一種很有用的非線性結構，具有以下兩個特點：
① 非空二叉樹只有乙個根結點；
② 每乙個結點最多有兩棵子樹，且分別稱為該結點的左子樹和右子樹。
在二叉樹中，每乙個結點的度最大為2，即所有子樹（左子樹或右子樹）也均為二叉樹。另外，二叉樹中的每個結點的子樹被明顯地分為左子樹和右子樹。
在二叉樹中，乙個結點可以只有左子樹而沒有右子樹，也可以只有右子樹而沒有左子樹。當乙個結點既沒有左子樹也沒有右子樹時，該結點即為葉子結點。
例如，乙個家族中的族譜關係如圖1-1所示：
a有後代b，c；b有後代d，e；c有後代f。
典型的二叉樹如圖1-1所示：
詳細講解二叉樹的基本概念，見表1-2。
圖1-1 二叉樹圖
2. 二叉樹基本性質
二叉樹具有以下幾個性質：
性質1：在二叉樹的第k層上，最多有2k-1（k≥1）個結點。
性質2：深度為m的二叉樹最多有2m-1個結點。
性質3：在任意一棵二叉樹中，度為0的結點（即葉子結點）總是比度為2的結點多乙個。
性質4：具有n個結點的二叉樹，其深度至少為[log2n]+1，其中[log2n]表示取log2n的整數部分。
3. 滿二叉樹與完全二叉樹
滿二叉樹是指這樣的一種二叉樹：除最後一層外，每一層上的所有結點都有兩個子結點。在滿二叉樹中，每一層上的結點數都達到最大值，即在滿二叉樹的第k層上有2k-1個結點，且深度為m的滿二叉樹有2m-1個結點。
完全二叉樹是指這樣的二叉樹：除最後一層外，每一層上的結點數均達到最大值；在最後一層上只缺少右邊的若干結點。
對於完全二叉樹來說，葉子結點只可能在層次最大的兩層上出現：對於任何乙個結點，若其右分支下的子孫結點的最大層次為p，則其左分支下的子孫結點的最大層次或為p，或為p+1。
完全二叉樹具有以下兩個性質：
性質1：具有n個結點的完全二叉樹的深度為[log2n]+1。
性質2：設完全二叉樹共有n個結點。如果從根結點開始，按層次（每一層從左到右）用自然數1，2，……，n給結點進行編號，則對於編號為k（k=1，2，……，n）的結點有以下結論：
① 若k=1，則該結點為根結點，它沒有父結點；若k>1，則該結點的父結點編號為int（k/2）；
② 若2k≤n，則編號為k的結點的左子結點編號為2k；否則該結點無左子結點（顯然也沒有右子結點）；
③ 若2k+1≤n，則編號為k的結點的右子結點編號為2k+1；否則該結點無右子結點。
1.6.2 二叉樹的遍歷
在遍歷二叉樹的過程中，一般先遍歷左子樹，再遍歷右子樹。在先左後右的原則下，根據訪問根結點的次序，二叉樹的遍歷分為三類：前序遍歷、中序遍歷和後序遍歷。
（1）前序遍歷
先訪問根結點，然後遍歷左子樹，最後遍歷右子樹；並且在遍歷左、右子樹時，仍需先訪問根結點，然後遍歷左子樹，最後遍歷右子樹。例如，對圖1-1中的二叉樹進行前序遍歷的結果（或稱為該二叉樹的前序序列）為：a，b，d，e，c，f。
計算機二級公共基礎知識 全
1.1 演算法 考點1 演算法的基本概念 計算機解題的過程實際上是在實施某種演算法，這種演算法稱為計算機演算法。演算法 algorithm 是一組嚴謹地定義運算順序的規則，並且每乙個規則都是有效的，同時是明確的 此順序將在有限的次數後終止。演算法是對特定問題求解步驟的一種描述，它是指令的有限序列，其...
計算機二級C公共基礎知識總結
第一章資料結構與演算法 1.1 演算法 演算法 是一組有窮指令集，是解題方 而完整的描述。通俗地說，演算法就是計算機解題的過程。演算法不等於程式，也不等於計算方法，程式的編制不可能優於演算法的設計。演算法是一組嚴謹地定義運算順序的規則，每乙個規則都是有效的，且是明確的，此順序將在有限的次數下終止。所...
全國計算機等級考試二級公共基礎知識
第1章資料結構與演算法 經過對部分考生的調查以及對近年真題的總結分析，筆試部分經常考查的是演算法複雜度 資料結構的概念 棧 二叉樹的遍歷 二分法查詢，讀者應對此部分進行重點學習。詳細重點學習知識點 1 演算法的概念 演算法時間複雜度及空間複雜度的概念 2 資料結構的定義 資料邏輯結構及物理結構的定義...