1.1資料結構與演算法
藉助於計算機解決問題，首先需要了解所處理物件的性質和特點即所操作物件的資料結構，然後再設計解決問題的方法和步驟即設計一個合理的演算法，即通常所說的“程式=資料結構+演算法”。
1.1.1演算法的基本概念
“演算法”（Algorithm）一詞最早來自公元9世紀波斯數學家比阿勒·霍瓦里鬆的一本影響深遠的著作《代數對話錄》。20世紀的英國數學家圖靈提出了著名的圖靈論點，並抽象出了一臺機器，這臺機器被我們稱之為圖靈機。圖靈的思想對演算法的發展起到了重要的作用。一般來說，演算法是指完成一個任務或解決一個問題所需要的具體步驟和方法的描述。在這裡我們說的演算法是指計算機能執行的演算法。
1.演算法分類
計算機演算法可分為兩大類，一類是數值運算演算法，另一類是非數值運算演算法。數值運算演算法主要是求數值解，如求方程的解、求函式的定積分等，非數值運算的範圍則非常廣泛，如人事管理、圖書檢索等。
2.演算法特徵
一個科學的演算法必須具備以下特徵：
(1)有窮性：一個演算法必須保證執行有限步之後結束，而不能是無限的。這是顯而易見的。更進一步說，有窮性是指在合理的範圍內結束運算，如果一個演算法需計算機執行幾百年或更長時間才結束，這顯然是不合理的。
(2)確定性：演算法的每一步驟必須有確切的定義而不能模稜兩可，演算法中不能出現諸如“一個比較大的數”等模糊描述。
(3)有零個或多個輸入
(4)有一個或多個輸出。演算法的目的是為了解決問題,一個沒有輸出的演算法是不能解決任何問題因而它是沒有意義的.
(5)有效性。演算法中的每一個步驟都都應當能有效地執行，並得到確定的結果。例如，若n=0則執行m/n是無法有效執行的。
3.演算法表示
一個計算機演算法可以用自然語言、流程圖、N-S圖等來表示。
4.演算法分析
演算法分析的任務是對設計出的每一個具體的演算法，利用數學工具，討論各種複雜度，以探討某種具體演算法適用於哪類問題，或某類問題宜採用哪種演算法。
演算法的複雜度分時間複雜度和空間複雜度。
．時間複雜度：在執行演算法時所耗費的時間為f(n)(即 n的函式)。
．空間複雜度：實現演算法所佔用的空間為g(n)（也為n的函式）。
稱O(f(n))和O(g(n))為該演算法的複雜度。
1.1.2 資料結構的定義
資料結構是電腦科學與技術領域上廣泛被使用的術語。儘管它至今還未有一個被一致公認的定義，但其內容是大家一致公認的。它用來反映一個數據的內部構成，即一個數據由那些成分資料構成，以什麼方式構成，呈什麼結構。資料結構有邏輯上的資料結構和物理上的資料結構之分。邏輯上的資料結構反映成分資料之間的邏輯關係，而物理上的資料結構反映成分資料在計算機內部的儲存安排。資料結構是資料存在的形式。
資料結構是資訊的一種組織方式，其目的是為了提高演算法的效率，它通常與一組演算法的集合相對應，通過這組演算法集合可以對資料結構中的資料進行某種操作。
一般資料結構可採用下面兩類主要的儲存方式，大多數資料結構的儲存表示都採用其中的一類方式，或兩類方式的結合。
1. 順序儲存結構
這種儲存方式的主要用於線性資料結構，它把邏輯上相鄰的資料元素儲存在物理上相鄰的儲存單元內，結點之間的關係由儲存單元的鄰接關係來實現。
順序儲存結構的主要特點是：（1）結點中只有自身資訊域，沒有連線資訊域，因此儲存密度大，儲存空間利用率高；（2）可以通過計算直接確定資料結構中第i個結點的儲存地址Li，計算公式為Li=L0+(i-1)*m，其中L0為第一個結點的儲存地址，m為每個結點所佔用的儲存單元個數；（3）插入、刪除運算不便，會引起大量結點的移動。
2. 鏈式儲存結構
鏈式儲存結構就是在每個結點中至少包括一個指標域，用指標來體現資料元素之間邏輯上的聯絡。這種儲存結構可把邏輯上相鄰的兩個元素存放在物理上不相鄰的儲存單元中；還可以線上性編址的計算機儲存器中表示結點之間的非線性聯絡。
鏈式儲存結構的主要特點是：（1）結點中除自身外，還有表示連線資訊的指標域，因此比順序結構的儲存密度小，儲存空間利用率低；（2）邏輯上相鄰的結點物理上不必鄰接，可用於線性表、樹、圖等多種邏輯結構的儲存表示；（3）插入、刪除操作靈活方便，不必移動結點，只要改變結點中的指標即可。
除上述兩種主要儲存方式外，雜湊法也是線上性表和集合的儲存表示中常用的一種儲存方式。
1.1.3 線性表結構
1.線性表的定義
線性表（Linear List）是最常用並且最簡單的一種資料結構。它是由n（n≥0）個數據元素（結點）a1，a2，…，an組成的有限序列。
① 資料元素的個數n定義為表的長度（n=0時稱為空表）。
② 將非空的線性表（n＞0）記作：（a1，a2，…，an）
③ 資料元素ai（1≤i≤n）只是個抽象符號，其具體含義在不同情況下可以不同。
在一些比較複雜的`線性表中，一個數據元素可以由若干個資料項組成。在這種情況下，一般把資料元素稱為記錄，含有大量記錄的線性表也稱為檔案。
例1英文字母表（A，B，…，Z）是線性表，表中每個字母是一個數據元素（結點） 例2一副撲克牌的點數（2，3，…，10，J，Q，K，A）也是一個線性表，其中資料元素是每張牌的點數
2.線性表的儲存
線性表可採用順序方式儲存和鏈式方式儲存。在各種高階語言中的一維陣列就是用順序方式儲存的線性表，因此也常用一維陣列來稱呼順序表。下面主要討論的線性表物件是指順序表。
3.線性表的基本操作
線性表是一種相當靈活的資料結構，不僅對它的資料元素可以查詢訪問，它的長度也可以根據需要增大或縮小，即可對線性表進行插入和刪除資料元素運算。
常見的線性表的基本運算
(1) InitList（L）
構造一個空的線性表L，即表的初始化。
(2) ListLength（L）
求線性表L中的結點個數，即求表長。
(3) GetNode（L，i）
取線性表L中的第i個結點，這裡要求1≤i≤ListLength（L）
(4) LocateNode（L，x）
在L中查詢值為x 的結點，並返回該結點在L中的位置。若L中有多個結點的值和x 相同，則返回首次找到的結點位置；若L中沒有結點的值為x ，則返回一個特殊值表示查詢失敗。
(5) InsertList（L，x，i）
線上性表L的第i個位置上插入一個值為x 的新結點，使得原編號為i，i+1，…，n的結點變為編號為i+1，i+2，…，n+1的結點。這裡1≤i≤n+1，而n是原表L的長度。插入後，表L的長度加1。
(6) DeleteList（L，i）
刪除線性表L的第i個結點，使得原編號為i+1，i+2，…，n的結點變成編號為i，i+1，…，n-1的結點。這裡1≤i≤n，而n是原表L的長度。刪除後表L的長度減1。具體程式實現可參考本書C語言相關章節。
1.1.4棧與佇列結構
1.棧與佇列的定義
棧是一種限定僅在表的一端進行插入與刪除操作的線性表。允許進行插入與刪除操作的這一端稱為棧頂，而另一端稱為棧底，不含元素的空表稱為空棧，插入與刪除分別稱進棧與出棧。 由於插入與刪除只能在同一端進行，所以較先進入棧的元素，在進行出棧操作時，要比較後才能出棧。特別是，最先進棧者，最後才能出棧，而最晚進棧者，必最先出棧。因此，棧也稱作後進先出（Last In First Out）的線性表，簡稱LIFO表。
