第一章資料結構與演算法
1.1 演算法
1．1．1演算法：是指解題方****而完整的描述。
規定了解決某類問題所需的操作語句以及執行順序使其能通過有限的指令語句，在一定時間內解決問題
演算法不等於程式，也不等計算機方法，程式的編制不可能優於演算法的設計。
演算法的基本特徵：是一組嚴謹地定義運算順序的規則，每乙個規則都是有效的，是明確的，此順序將在有限的次數下終止。
1．演算法特徵包括：
（1）可行性；
（2）確定性，演算法中每一步驟都必須有明確定義，不允許有模稜兩可的解釋，不允許有多義性；
（3）有窮性，演算法必須能在有限的時間內做完，即能在執行有限的步驟後終止，包括合理的執行時間的含義；
（4）擁有足夠的情報。
2．演算法的基本要素：
一是對資料物件的運算和操作；二是演算法的控制結構
通常，計算機可以以執行的基本操作是以指令的形式描述的。乙個計算機系統能執行的所有指令的集合，稱為計算機系統的指令系統。
（1）計算機系統中的基本運算和操作包括：
算術運算
邏輯運算 not and or
關係運算 < > ! =
資料傳輸賦值輸入與輸出
（2）演算法的控制結構：順序結構、選擇結構、迴圈結構。
3．演算法基本設計方法：
列舉法 （列舉所有解決方案）
歸納法（特殊一般）
遞推 （已知未知）
遞迴 （逐層分解）
減半遞推
「減半」是指將問題的規模減半，而問題的性質不為，所謂「遞推」是指重複「減半」的過程
回溯法找出乙個解決問題的線索，然後沿著這個線索逐步多次「探、試」
1．1．2演算法複雜度
演算法時間複雜度和演算法空間複雜度（乙個演算法所要付出的代價）是衡理演算法好壞的。
1．演算法時間複雜度
演算法時間複雜度是指執行演算法所需要的計算工作量。（既演算法的運算次數）
含義：演算法執行過程中所需要的基本運算次數
影響計算工作量的主要因素：
一、基本運算次數
二、問題與規模
1.2 資料結構的基本基本概念
資料： 在電腦科學中指所有能輸入到計算機中的並被電腦程式處理的符號的總稱
資料元素：資料的基本單位，在電腦程式中通常作為乙個整體進行考慮和處理。
資料結構：是相互之間存在一種或多種特定關係的資料元素的集合
資料結構研究的三個方面：
（1）資料集合中各資料元素之間所固有的邏輯關係，即資料的邏輯結構；
（2）在對資料進行處理時，各資料元素在計算機中的儲存關係，即資料的儲存結構；
（3）對各種資料結構進行的運算。
資料結構是指相互有關聯的資料元素的集合。
即：一般來說，人們不會同時處理特徵完全不同且互相之間沒有任何關係的各類資料元素，對於具有不同特徵的資料元素總是分別進行處理。
1．資料的邏輯結構包含：
（1）表示資料元素的資訊；
（2）表示各資料元素之間的前後件關係。
其中資料元素之間的前後件關係是指它們的邏輯關係，與它們在計算機中的儲存位置無關。
2．資料的儲存結構：p12
乙個資料結構中的各資料元素在計算機儲存空間中的位置關係與邏輯關係有可能不同
資料的儲存結構指資料的邏輯結構在計算機儲存空間中的存放形式。
由於資料元素在計算機儲存空間中的位置關係可能與邏輯關係不同，因此，為了表示存放在計算機儲存空間中的各元素之間的邏輯關係（即前後件關係），在資料儲存結構中，不僅要儲存各資料元素的資訊，還需要存放各資料元素之間的前後件關係的資訊。
邏輯結構與物理結構的關係
a．一種邏輯結構可以用不同的物理結構來實現
b．.邏輯結構決定了演算法的設計
c．物理結構決定了演算法的實現
1．2．2 資料結構的圖形表示：
1．2．3 線性結構與非線性結構
如果乙個非空的資料結構滿足下列兩個條件
有且只有乙個根結點
每乙個結點最多有乙個前件，也最多有乙個後件
則稱該資料結構為線性結構，線性結構也稱為線性表
特別需要說明的是，在乙個線性結構中插入或刪除任何乙個結點後還應是線性結構。
如果乙個資料結構不是線性結構，則稱為非線性結構。
資料的儲存結構有順序、鏈結、索引等。
對於同乙個邏輯結構來說，採用不同的儲存結構，其資料處理的效率是不同的。
線性結構條件：
（1）有且只有乙個根結點；
（2）每乙個結點最多有乙個前件，也最多有乙個後件。
非線性結構：不滿足線性結構條件的資料結構。
1．3 線性表及其順序儲存結構
線性表由一組資料元素構成，資料元素的位置只取決於自己的序號，元素之間的相對位置是線性的。
在複雜線性表中，由若干項資料元素組成的資料元素稱為記錄，而由多個記錄構成的線性表又稱為檔案。
1．3．1非空線性表的結構特徵：p16
（1）且只有乙個根結點a1，它無前件；
（2）有且只有乙個終端結點an，它無後件；
（3）除根結點與終端結點外，其他所有結點有且只有乙個前件，也有且只有乙個後件。結點個數n稱為線性表的長度，當n=0時，稱為空表。
1．3．2線性表的順序儲存結構具有以下兩個基本特點：
（1）線性表中所有元素的所佔的儲存空間是連續的；
（2）線性表中各資料元素在儲存空間中是按邏輯順序依次存放的。
ai的儲存位址為：adr(ai)=adr(a1)+(i-1)k,，adr(a1)為第乙個元素的位址，k代表每個元素佔的位元組數。
由此可以看出，**性表的順序結構中，其前後件兩個元素在儲存空間中是緊鄰的，且前件元素一定儲存在後件元素的前面。
在程式語言中，通常定義乙個一維陣列來表示線性表的順序儲存空間。
順序表的運算：插入、刪除。 （詳見17--18頁）
畫圖來理解
1．4 棧和佇列
1．4．1棧及其基本運算
1．什麼是棧
棧是限定在一端進行插入與刪除的線性表，允許插入與刪除的一端稱為棧頂，不允許插入與刪除的另一端稱為棧底。
棧按照「先進後出」（filo）或「後進先出」（lifo）組織資料，棧具有記憶作用。用top表示棧頂位置，用bottom表示棧底。
2．棧的順序儲存與棧的基本運算：
（1）插入元素稱為入棧運算；
（2）刪除元素稱為退棧運算；
（3）讀棧頂元素是將棧頂元素賦給乙個指定的變數，此時指標無變化。
1．4．2佇列及其基本運算
1．什麼是佇列
佇列是指允許在一端（隊尾）進入插入，而在另一端（隊頭）進行刪除的線性表。rear指標指向隊尾，front指標指向隊頭。
佇列是「先進先出」（fifo）或「後進後出」（lilo）的線性表。
2．迴圈佇列運算包括
（1）入隊運算：從隊尾插入乙個元素；
（2）退隊運算：從隊頭刪除乙個元素。
迴圈佇列：s=0表示佇列空，s=1且front=rear表示佇列滿
1．5 線性鍊錶 p24
對於大的線性表或者變動頻繁的線性表不宜用順序儲存，應該用鏈式儲存。
在鏈式儲存結構中的每乙個結點對應於乙個儲存單元，這種儲存單元稱為儲存結點，簡稱結點。
結點由兩部分組成：（1）用於儲存資料元素值，稱為資料域；（2）用於存放指標，稱為指標域，用於指向前乙個或後乙個結點。
鏈式儲存方式的特點：
☆在鏈式儲存結構中，儲存資料結構的儲存空間可以不連續，
☆各資料結點的儲存順序與資料元素之間的邏輯關係可以不一致，而資料元素之間的邏輯關係是由指標域來確定的。
☆鏈式儲存方式即可用於表示線性結構，也可用於表示非線性結構。
1．線性鍊錶
為了適應線性表的儲存結構，計算機儲存空間被劃分為乙個乙個小塊，每乙個小塊佔若干位元組，通常稱這些小塊為儲存結點。
儲存結點=資料域（資料元素本身） +指標域（資料元素之間的前後邏輯關係）
**性煉表中，用乙個專門的指標head指向線性鍊錶中的第乙個資料元素的結點（即存放線性表中第乙個資料元素的儲存結點的序號）稱為頭指標，
頭指標：**性煉表中，頭指標（head）很關鍵，不得丟失。
最後乙個結點的指標域：線性鍊錶的最乙個結點的指標域為空（用null或0來表示）
空表的定義：當head=null（或0）稱為空表。
單鏈表的缺點：只能找到後不能找到前件。
2．雙向鍊錶
為了克服單鏈表的缺點，把每個結點修改為由三部分組
雙向鍊錶克服了單向鍊錶的只能找到後件不能找到前件的缺陷。
如果是兩指標：左指標（llink）指向前件結點，右指標（rlink）指向後件結點。
2．帶鏈的棧
在實際應用中，帶鏈的棧可以用來收集計算機儲存空間中所有空閒的儲存結點。這種帶鏈的棧稱為可利用棧
當計算機系統需要儲存結點時，退棧。當計算機系統釋放儲存結點時，入棧
3．迴圈鍊錶
單鏈表的運算必須對於空表和對第乙個結點的處理必須單獨考慮，為了克服這個缺點，提出了迴圈鍊錶的概念。
迴圈鍊錶與單鏈表的主要區別：第一，在迴圈鍊錶中增加了表頭結點，其資料域為任意或根據需要來設定，指標域為指向線性表的第乙個元素的結點。第二，迴圈鍊錶中的最後乙個結點的指標不為空，而是指向表頭的結點。
1．6 樹與二叉樹 p31
1.6.1樹的基本概念
樹是一種簡單的非線性結構，所有元素之間具有明顯的層次特性。
在樹結構中，每乙個結點只有乙個前件，稱為父結點，
沒有前件的結點只有乙個，稱為樹的根結點，簡稱樹的根。
每乙個結點可以有多個後件，稱為該結點的子結點。沒有後件的結點稱為葉子結點。
在樹結構中，乙個結點所擁有的後件的個數稱為該結點的度，
所有結點中最大的度稱為樹的度。樹的最大層次稱為樹的深度。
二叉樹的特點：（1）非空二叉樹只有乙個根結點；（2）每乙個結點最多有兩棵子樹，且分別稱為該結點的左子樹與右子樹。
二叉樹的基本性質：
（1）在二叉樹的第k層上，最多有2k-1(k≥1)個結點；
（2）深度為m的二叉樹最多有2m-1個結點；
（3）度為0的結點（即葉子結點）總是比度為2的結點多乙個；
（4）具有n個結點的二叉樹，其深度至少為[log2n]+1,其中[log2n]表示取log2n的整數部分；
（5）具有n個結點的完全二叉樹的深度為[log2n]+1；
（6）設完全二叉樹共有n個結點。如果從根結點開始，按層序（每一層從左到右）用自然數1，2，….n給結點進行編號（k=1,2….n），有以下結論：
①若k=1，則該結點為根結點，它沒有父結點；若k>1，則該結點的父結點編號為int(k/2)；
②若2k≤n，則編號為k的結點的左子結點編號為2k；否則該結點無左子結點（也無右子結點）；
③若2k+1≤n，則編號為k的結點的右子結點編號為2k+1；否則該結點無右子結點。
二級公共基礎知識總結
第一章資料結構與演算法 1.1 演算法 演算法 是一組有窮指令集，是解題方 而完整的描述。通俗地說，演算法就是計算機解題的過程。演算法不等於程式，也不等於計算方法，程式的編制不可能優於演算法的設計。演算法是一組嚴謹地定義運算順序的規則，每乙個規則都是有效的，且是明確的，此順序將在有限的次數下終止。所...
二級公共基礎知識總結
線性表由一組資料元素構成，資料元素的位置只取決於自己的序號，元素之間的相對位置是線性的。在複雜線性表中，由若干項資料元素組成的資料元素稱為記錄，而由多個記錄構成的線性表又稱為檔案。非空線性表的結構特徵 1 且只有乙個根結點a1，它無前件 2 有且只有乙個終端結點an，它無後件 3 除根結點與終端結點...
二級公共基礎知識考試大綱
基本要求 1.掌握演算法的基本概念。2.掌握基本資料結構及其操作。3.掌握基本排序和查詢演算法。4.掌握逐步求精的結構化程式設計方法。5.掌握軟體工程的基本方法，具有初步應用相關技術進行軟體開發的能力。6.掌握資料庫的基本知識，了解關聯式資料庫的設計。考試內容 一 基本資料結構與演算法 1.演算法的...