一、內容要點
（一）演算法
1．演算法的基本概念
演算法是指解題方****而完整的描述。即是一組嚴謹地定義運算順序的規則，並且每乙個規則都是有效的，且是明確的，沒有二義性，同時該規則將在有限次運算後可終止。
1）演算法的基本特徵
（1）可行性
由於演算法的設計是為了在某乙個特定的計算工具上解決某乙個實際的問題而設計的，因此，它總是受到計算工具的限制，使執行產生偏差。
如：計算機的數值有效位是有限的，當大數和小數進行運算時，往往會因為有效位數的影響而使小數丟失，因此，在演算法設計時，應該考慮到這一點。
（2）確定性
演算法的設計必須是每乙個步驟都有明確的定義，不允許有模糊的解釋，也不能有多義性。
例如，乙個實際的問題，小寶和萍萍共有12個蘋果，小寶比萍萍多4個，請問小寶和萍萍各有幾個蘋果？這個問題，我們可以立乙個方程組x+y=12和x-y=4來求解，要求x和y的值，公式是正確的，但如何讓計算能夠進行計算，我們的演算法不能把公式直接輸進去，而應該設計出解題的步驟和過程。
即設計的演算法是計算工具所能夠正常解決問題的過程。
（3）有窮性
演算法的有窮性，即在一定的時間是能夠完成的，即演算法應該在計算有限個步驟後能夠正常結束。
例如，在數學中的無窮級數，在計算機中只能求有限項，即計算的過程是有窮的。
（4）擁有足夠的情報
演算法的執行與輸入的資料和提供的初始條件相關，不同的輸入或初始條件會有不同的輸出結果，提供準確的初始條件和資料，才能使演算法正確執行。
2）演算法的基本要素
一是資料物件的運算和操作，二是演算法的控制結構。
（1）演算法中對資料的運算和操作
演算法實際上是按解題要求從環境能進行的所有操作中選擇合適的操作所組成的一組指令序列。即演算法是計算機所能夠處理的操作所組成的指令序列。
（2）演算法的控制結構
演算法的功能不僅取決於所選用的操作，而且還與各操作之間的順序有關。
在演算法中，操作的執行順序又稱演算法的控制結構，一般的演算法控制結構有三種：順序結構、選擇結構和迴圈結構。
在演算法描述是，有相關的工具對這三種結構進行描述，常用的描述工具有：流程圖、n-s結構圖和演算法描述語言等。
3）演算法設計的基本方法
為用計算機解決實際問題而設計的演算法，即是計算機演算法。
通常的演算法設計有如下幾種：
（1）列舉法
列舉法的基本思想是，根據提出的問題，列舉出所有可能的情況，並用問題中給定的條件檢驗哪些是滿足條件的，哪些是不滿足條件的。列舉法通常用於解決「是否存在」或「有哪些可能」等問題。
例如，我國古代的趣味數學題：「百錢買百雞」、「雞兔同籠」等，均可採用列舉法進行解決。
使用列舉法時，要對問題進行詳細的分析，將與問題有關的知識條理化、完備化、系統化，從中找出規律。
（2）歸納法
歸納法的基本思想是，通過列舉少量的特殊情況，經過分析，最後找出一般的關係。歸納是一種抽象，即從特殊現象中找出一般規律。但由於在歸納法中不可能對所有的情況進行列舉，因此，該方法得到的結論只是一種猜測，還需要進行證明。
（3）遞推
遞推，即是從已知的初始條件出發，逐次推出所要求的各個中間環節和最後結果。其中初始條件或問題本身已經給定，或是通過對問題的分析與化簡而確定。
遞推的本質也是一種歸納，遞推關係式通常是歸納的結果。
例如，裴波那契數列，是採用遞推的方法解決問題的。
（4）遞迴
在解決一些複雜問題時，為了降低問題的複雜程式，通常是將問題逐層分解，最後歸結為一些最簡單的問題。這種將問題逐層分解的過程，並沒有對問題進行求解，而只是當解決了最後的問題那些最簡單的問題後，再沿著原來分解的逆過程逐步進行綜合，這就是遞迴的方法。
遞迴分為直接遞迴和間接遞迴兩種方法。如果乙個演算法直接呼叫自己，稱為直接遞迴呼叫；如果乙個演算法a呼叫另乙個演算法b，而演算法b又呼叫演算法a，則此種遞迴稱為間接遞迴呼叫。
（5）減半遞推技術
減半遞推即將問題的規模減半，然後，重複相同的遞推操作。
例如，一元二次方程的求解。
（6）回溯法
有些實際的問題很難歸納出一組簡單的遞推公式或直觀的求解步驟，也不能使用無限的列舉。對於這類問題，只能採用試探的方法，通過對問題的分析，找出解決問題的線索，然後沿著這個線索進行試探，如果試探成功，就得到問題的解，如果不成功，再逐步回退，換別的路線進行試探。這種方法，即稱為回溯法。
如人工智慧中的機械人下棋。
2．演算法複雜度
演算法的複雜度包括時間複雜度和空間複雜度。
1）時間複雜度
即實現該演算法需要的計算工作量。演算法的工作量用演算法所執行的基本運算次數來計算。
同乙個問題規模下，如果演算法執行所需要的基本次數取決於某一特定輸入時，可以用以下兩種方法來分析演算法的工作量：
演算法工作量=f(n)
（1）平均性態
用各種特定輸入下的基本運算次數的加權平均值來度量演算法的工作量。
設x是某個可能輸入中的某個特定輸入，p(x)是x出現的概率，t(x)是演算法在輸入為x時所執行的基本運算次數，則演算法的平均性態定義為：
dn表示當規模為n時，演算法執行時所有可能輸入的集合。
（2）最壞情況複雜度
指在規模為n時，演算法所執行的基本運算的最大次數。它定義為：
例如，在具有n個元素的數列中搜尋乙個數x。
平均性態：
即該數在數列中任何位置出現的數列是相同的，也有可能不存在，存在的概率為q。
如果有一半的機會存在，則概率q為1/2，平均性態：
如果查詢的元素一定在數列中，則每個數存在的概率即為1，則平均性態為：
最壞情況分析：即要查詢的元素x在數列的最後或不在數列中，顯然，它的最壞情況複雜度為：
2）演算法的空間複雜度
指要執行該演算法所需要的記憶體空間。演算法所占用的記憶體空間包括演算法程式所佔的空間、輸入的初始資料所佔的儲存空間以及演算法執行過程中所需要的額外空間，如執行過程中工作單元以及某種資料結構所需要的附加儲存空間等。
（二）資料結構的基本概念
1．概念
資料結構是指相互有關聯的資料元素的集合。它包括以下兩個方面：
表示資料元素的資訊
表示各資料之間的前後件關係
1）資料的邏輯結構
是指反映資料元素之間的邏輯關係的資料結構。
資料的邏輯結構有兩個要素：
資料元素的集合，記作d
資料之間的前後件關係，記作r
則資料結構b=（d，r）
2）資料的儲存結構
資料的邏輯結構在計算機儲存空間中的存放形式稱為資料的儲存結構，或資料的物理結構。
即資料儲存時，不僅要存放資料元素的資訊，而且要儲存資料元素之間的前後件關係的資訊。
通常的資料儲存結構有順序、鏈結、索引等儲存結構。
2．資料結構的圖形表示
資料結構的圖形表示有兩個元素：
中間標有元素值的方框表示資料元素，稱為資料結點
用有向線段表示資料元素之間的前後件關係，即有向線段從前件結點指向後件結點
注意：在結構圖中，沒有前件的結點稱為根結點，沒有後件的結點稱為終端結點，也稱葉子結點。
3．線性結構與非線性結構
如果乙個資料元素都沒有，該資料結構稱為空資料結構；在空資料結構中插入乙個新的元素後資料結構變為非空資料結構；將資料結構中的所有元素均刪除，則該資料結構變成空資料結構。
如果乙個非空的資料結構滿足如下條件，則該資料結構為線性結構：
有且只有乙個根結點
每乙個結點最多只有乙個前件，也最多只有乙個後件
線性結構又稱線性表。
注意：**性結構表中插入或刪除元素，該線性表仍然應滿足線性結構。
如果乙個資料結構不滿足線性結構，則稱為非線性結構。
（三）線性表及其順序儲存結構
1．基本概念
線性表是最常用的資料結構，它由一組資料元素組成。
注意：這裡的資料元素是乙個廣義的資料元素，並不僅僅是指乙個資料。如，矩陣、學生記錄表等。
非空線性表的結構特徵：
有且只有乙個根結點，它無前件
有且只有乙個終端結點，它無後件
除根結點和終端結點之外，所有的結點有且只有乙個前件和乙個後件。線性表中結點的個數稱為結點的長度n。當n=0時，稱為空表。
2．順序儲存結構
順序儲存結構的特點：
線性表中所有的元素所佔的儲存空間是連續的
線性表中各資料元素在儲存空間中是按邏輯順序依次存放的
通常，順序儲存結構中，線性表中每乙個資料元素在計算機儲存空間中的儲存位址由該元素**性表中的位置序號唯一確定。
線性表的順序儲存結構下的基本運算：
在指定位置插入乙個元素
刪除線性表中的指定元素
查詢某個或某些特定的元素
線性表的排序
按要求將乙個線性表拆分為多個線性表
將多個線性表合併為乙個線性表
複製線性表
逆轉乙個線性表
3．線性表的基本操作
1）順序表的插入運算
在順序儲存結構的線性表中插入乙個元素。
注意：找到插入位置後，將插入位置開始的所有元素從最後乙個元素開始順序後移。另外，在定義線性表時，一定要定義足夠的空間，否則，將不允許插入元素。
2）順序表的刪除運算
在順序在儲存結構的線性表中刪除乙個元素。
注意：找到刪除的資料元素後，從該元素位置開始，將後面的元素一一向前移動，在移動完成後，線性表的長度減1
（四）棧和佇列
1．棧及其基本運算
1）棧棧是一種特殊的線性表，它是限定在一端進行插入和刪除的線性表。它的插入和刪除只能在表的一端進行，而另一端是封閉的，不允許進行插入和刪除操作。
在棧中，允許插入和刪除操作一端稱為棧頂，不允許插入和刪除操作的一端則稱為棧底。棧頂的元素總是最後被插入的元素，也是最先被刪除的元素。它遵循的原則是：先進後出或後進先出。
堆疊指標總是指向棧頂元素的。
2）棧的順序儲存及其運算
在棧的順序儲存空間s（1：m）中，s（bottom）通常為棧底元素，s（top）為棧頂元素。top=0表示棧空；top=m表示棧滿。
1）入棧運算
演算法與資料結構第一章概論筆記
1.演算法時間複雜度 當問題規模n趨向無窮大時，時間複雜度t n 的數量級 階 稱為演算法的時間複雜度 t n o f n 簡稱為時間複雜度，不作特別說明下，我們討論的時間複雜度是最壞情況下的時間複雜度。2.氣泡排序另一種寫法 void bubblesort int a,int n i lastex...
演算法與資料結構學習指導第一章
主要內容 1 資料結構的研究目的和研究內容 2 資料結構中的幾個重要概念和術語 3 演算法設計的基本要求以及演算法複雜度的分析和計算方法 教學目標 1 了解資料結構的研究目的和研究內容 2 掌握資料結構中的重要概念和術語 3 掌握演算法設計的基本要求以及演算法複雜度的分析和計算方法 所需課時 2次課...
資料結構第一章習題
第一章習題 一 單項選擇題1.資料結構是一門研究非數值計算的程式設計問題中計算機的 以及它們之間的 和運算等的學科。a 操作物件 b 計算方法 c 邏輯儲存 d 資料映象 a 結構 b 關係 c 運算 d 演算法2.演算法分析的目的是 演算法分析的兩個主要方面是 a 找出資料結構的合理性 b 研究演...