第一章資料結構與演算法
1.1 演算法
1、是指解題方****而完整的描述。換句話說，演算法是對特定問題求解步驟的一種描述。
*：演算法不等於程式，也不等於計算方法。程式的編制不可能優於演算法的設計。
2、演算法的基本特徵
（1）可行性。針對實際問題而設計的演算法，執行後能夠得到滿意的結果。
（2）確定性。每一條指令的含義明確，無二義性。並且在任何條件下，演算法只有唯一的一條執行路徑，即相同的輸入只能得出相同的輸出。
（3）有窮性。演算法必須在有限的時間內完成。有兩重含義，一是演算法中的操作步驟為有限個，二是每個步驟都能在有限時間內完成。
（4）擁有足夠的情報。演算法中各種運算總是要施加到各個運算物件上，而這些運算物件又可能具有某種初始狀態，這就是演算法執行的起點或依據。因此，乙個演算法執行的結果總是與輸入的初始資料有關，不同的輸入將會有不同的結果輸出。
當輸入不夠或輸入錯誤時，演算法將無法執行或執行有錯。一般說來，當演算法擁有足夠的情報時，此演算法才是有效的；而當提供的情報不夠時，演算法可能無效。
*：綜上所述，所謂演算法，是一組嚴謹地定義運算順序的規則，並且每乙個規則都是有效的，且是明確的，此順序將在有限的次數下終止。
3、演算法複雜度主要包括時間複雜度和空間複雜度。
（1）演算法是指執行演算法所需要的計算工作量，可以用執行演算法的過程中所需基本運算的執行次數來度量。
（2）演算法是指執行這個演算法所需要的記憶體空間。
1.2 資料結構的基本概念
1、是指相互有關聯的資料元素的集合。
2、資料結構主要研究和討論以下三個方面的問題：
（1）資料集合中各資料元素之間所固有的邏輯關係，即資料的邏輯結構。
資料的邏輯結構包含：1）表示資料元素的資訊；2）表示各資料元素之間的前後件關係。
（2）在對資料進行處理時，各資料元素在計算機中的儲存關係，即資料的儲存結構。
資料的儲存結構有順序、鏈結、索引等。
1）順序儲存。它是把邏輯上相鄰的結點儲存在物理位置相鄰的儲存單元裡，結點間的邏輯關係由儲存單元的鄰接關係來體現。由此得到的儲存表示稱為順序儲存結構。
2）鏈結儲存。它不要求邏輯上相鄰的結點在物理位置上亦相鄰，結點間的邏輯關係是由附加的指標字段表示的。由此得到的儲存表示稱為鏈式儲存結構。
3）索引儲存：除建立儲存結點資訊外，還建立附加的索引表來標識結點的位址。
*：資料的邏輯結構反映資料元素之間的邏輯關係，資料的儲存結構（也稱資料的物理結構）是資料的邏輯結構在計算機儲存空間中的存放形式。同一種邏輯結構的資料可以採用不同的儲存結構，但影響資料處理效率。
（3）對各種資料結構進行的運算。
3、資料結構的圖形表示
乙個資料結構除了用二元關係表示外，還可以直觀地用圖形表示。在資料結構的圖形表示中，對於資料集合d中的每乙個資料元素用中間標有元素值的方框表示，一般稱之為資料結點，並簡稱為結點；為了進一步表示各資料元素之間的前後件關係，對於關係r中的每乙個二元組，用一條有向線段從前件結點指向後件結點。
4、資料結構分為兩大型別：線性結構和非線性結構。
（1）（非空的資料結構）條件：1）有且只有乙個根結點；2）每乙個結點最多有乙個前件，也最多有乙個後件。
*：常見的線性結構有線性表、棧、佇列和線性鍊錶等。
（2）：不滿足線性結構條件的資料結構。
*：常見的非線性結構有樹、二叉樹和圖等。
1.3 線性表及其順序儲存結構
1、由一組資料元素構成，資料元素的位置只取決於自己的序號，元素之間的相對位置是線性的。線性表是由n(n≥0)個資料元素組成的乙個有限序列，表中的每乙個資料元素，除了第乙個外，有且只有乙個前件，除了最後乙個外，有且只有乙個後件。線性表中資料元素的個數稱為線性表的長度。
線性表可以為空表。
*：線性表是一種儲存結構，它的儲存方式：順序和鏈式。
2、線性表的順序儲存結構具有兩個基本特點：（1）線性表中所有元素所佔的儲存空間是連續的；（2）線性表中各資料元素在儲存空間中是按邏輯順序依次存放的。
*：由此可以看出，**性表的順序儲存結構中，其前後件兩個元素在儲存空間中是緊鄰的，且前件元素一定儲存在後件元素的前面，可以通過計算機直接確定第i個結點的儲存位址。
3、順序表的插入、刪除運算（學吧學吧獨家稿件）
（1）順序表的插入運算：在一般情況下，要在第i（1≤i≤n）個元素之前插入乙個新元素時，首先要從最後乙個（即第n個）元素開始，直到第i個元素之間共n-i+1個元素依次向後移動乙個位置，移動結束後，第i個位置就被空出，然後將新元素插入到第i項。插入結束後，線性表的長度就增加了1。
*：順性表的插入運算時需要移動元素，在等概率情況下，平均需要移動n/2個元素。
（2）順序表的刪除運算：在一般情況下，要刪除第i（1≤i≤n）個元素時，則要從第i+1個元素開始，直到第n個元素之間共n-i個元素依次向前移動乙個位置。刪除結束後，線性表的長度就減小了1。
*：進行順性表的刪除運算時也需要移動元素，在等概率情況下，平均需要移動（n-1）/2個元素。插入、刪除運算不方便。
1.4 棧和佇列
1、棧及其基本運算
是限定在一端進行插入與刪除運算的線性表。
在棧中，允許插入與刪除的一端稱為棧頂，不允許插入與刪除的另一端稱為棧底。棧頂元素總是最後被插入的元素，棧底元素總是最先被插入的元素。即棧是按照「先進後出」或「後進先出」的原則組織資料的。
棧具有記憶作用。
棧的基本運算：1）插入元素稱為入棧運算；2）刪除元素稱為退棧運算；3）讀棧頂元素是將棧頂元素賦給乙個指定的變數，此時指標無變化。
棧的儲存方式和線性表類似，也有兩種，即順序棧和鏈式棧。
2、佇列及其基本運算
是指允許在一端（隊尾）進入插入，而在另一端（隊頭）進行刪除的線性表。尾指標（rear）指向隊尾元素，頭指標（front）指向排頭元素的前乙個位置（隊頭）。
佇列是「先進先出」或「後進後出」的線性表。
佇列運算包括：1）入隊運算：從隊尾插入乙個元素；2）退隊運算：從隊頭刪除乙個元素。
迴圈佇列及其運算：所謂迴圈佇列，就是將佇列儲存空間的最後乙個位置繞到第乙個位置，形成邏輯上的環狀空間，供佇列迴圈使用。在迴圈佇列中，用隊尾指標rear指向佇列中的隊尾元素，用排頭指標front指向排頭元素的前乙個位置，因此，從頭指標front指向的後乙個位置直到隊尾指標rear指向的位置之間，所有的元素均為佇列中的元素。
*：迴圈佇列中元素的個數=rear-front。
1.5 線性鍊錶（學吧學吧獨家稿件）
1、線性表順序儲存的缺點（學吧學吧獨家稿件）：（1）插入或刪除的運算效率很低。在順序儲存的線性表中，插入或刪除資料元素時需要移動大量的資料元素；（2）線性表的順序儲存結構下，線性表的儲存空間不便於擴充；（3）線性表的順序儲存結構不便於對儲存空間的動態分配。
2、線性鍊錶：線性表的鏈式儲存結構稱為線性鍊錶，是一種物理儲存單元上非連續、非順序的儲存結構，資料元素的邏輯順序是通過鍊錶中的指標鏈結來實現的。因此，在鏈式儲存方式中，每個結點由兩部分組成：
一部分用於存放資料元素的值，稱為資料域；另一部分用於存放指標，稱為指標域，用於指向該結點的前乙個或後乙個結點（即前件或後件），如下圖所示：
線性鍊錶分為單鏈表、雙向鍊錶和迴圈鍊錶三種型別。
在單鏈表中，每乙個結點只有乙個指標域，由這個指標只能找到其後件結點，而不能找到其前件結點。因此，在某些應用中，對於線性鍊錶中的每個結點設定兩個指標，乙個稱為左指標，指向其前件結點；另乙個稱為右指標，指向其後件結點，這種鍊錶稱為雙向鍊錶，如下圖所示：
3、線性鍊錶的基本運算
（1）**性煉表中包含指定元素的結點之前插入乙個新元素。
*：**性煉表中插入元素時，不需要移動資料元素，只需要修改相關結點指標即可，也不會出現「上溢」現象（學吧學吧獨家稿件）。
（2）**性煉表中刪除包含指定元素的結點。
*：**性煉表中刪除元素時，也不需要移動資料元素，只需要修改相關結點指標即可。
（3）將兩個線性鍊錶按要求合併成乙個線性鍊錶。
（4）將乙個線性鍊錶按要求進行分解。
（5）逆轉線性鍊錶。
（6）複製線性鍊錶。
（7）線性鍊錶的排序。
（8）線性鍊錶的查詢。
*：線性鍊錶不能隨機訪問。
4、迴圈鍊錶及其基本運算
**性煉表中，其插入與刪除的運算雖然比較方便，但還存在乙個問題，在運算過程中對於空表和對第乙個結點的處理必須單獨考慮，使空表與非空表的運算不統一。為了克服線性鍊錶的這個缺點，可以採用另一種鏈結方式，即迴圈鍊錶。
與前面所討論的線性鍊錶相比，迴圈鍊錶具有以下兩個特點：1）在鍊錶中增加了乙個表頭結點，其資料域為任意或者根據需要來設定，指標域指向線性表的第乙個元素的結點，而迴圈鍊錶的頭指標指向表頭結點；2）迴圈鍊錶中最後乙個結點的指標域不是空，而是指向表頭結點。即在迴圈鍊錶中，所有結點的指標構成了乙個環狀鏈。
下圖a是乙個非空的迴圈鍊錶，圖b是乙個空的迴圈鍊錶：
迴圈鍊錶的優點主要體現在兩個方面：一是在迴圈鍊錶中，只要指出表中任何乙個結點的位置，就可以從它出發訪問到表中其他所有的結點，而線性單鏈表做不到這一點；二是由於在迴圈鍊錶中設定了乙個表頭結點，在任何情況下，迴圈鍊錶中至少有乙個結點存在，從而使空表與非空表的運算統一。
*：迴圈鍊錶是在單鏈表的基礎上增加了乙個表頭結點，其插入和刪除運算與單鏈表相同。但它可以從任一結點出發來訪問表中其他所有結點，並實現空表與非空表的運算的統一。
1.6 樹與二叉樹（學吧學吧獨家稿件）
1、樹的基本概念
是一種簡單的非線性結構。在樹這種資料結構中，所有資料元素之間的關係具有明顯的層次特性。
在樹結構中，每乙個結點只有乙個前件，稱為。沒有前件的結點只有乙個，稱為樹的根結點，簡稱樹的根。每乙個結點可以有多個後件，稱為該結點的。沒有後件的結點稱為。
在樹結構中，乙個結點所擁有的後件的個數稱為該，所有結點中最大的度稱為。樹的最大層次稱為。
計算機二級C語言考試小竅門
鑑於大家很急切的想知道計算機二級c語言程式設計題怎麼得分，我百忙之中抽出點時間來給大家簡單解說下。首先，我先給大家解釋下程式設計題那傳說中神秘的機改試卷是如何完成的。在程式設計題 也就是最後乙個24分的大題 中，會有乙個獨立於其他題目的資料夾，裡面的檔案大致有一些亂七八糟的檔案什麼的。關鍵的是，裡面...
計算機二級C語言複習
第一部分 c語言知識複習資料 第一章 c語言基本知識 考點1 c程式 用c語言編寫的程式稱為c語言源程式，源程式檔案的字尾名為 c 源程式經編譯後生成字尾名為 obj 的目標檔案，再把目標檔案與各種庫函式連線起來，生成 exe 可執行檔案。c語言有三種基本結構 順序結構 選擇結構 迴圈結構。考點2 ...
計算機等級考試二級C語言模擬試題
2010年9月計算機等級考試二級c語言模擬試題 三 1 筆試部分 一 選擇題 1.對下面程式描述正確的一項是 每行程式前面的數字表示行號 main int i for i 0 i 3 i scanf d a i for i 1 i 3 i a 0 a 0 a i printf f n a 0 a.沒...