數據結構與演算法基礎

㈠ 計算機應用基礎知識

2017計算機應用基礎知識

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表。

;

㈡ 數據結構有哪些基本演算法

一、排序演算法 1、有簡單排序（包括冒泡排序、插入排序、選擇排序） 2、快速排序，很常見的 3、堆排序， 4、歸並排序，最穩定的，即沒有太差的情況 二、搜索演算法 最基礎的有二分搜索演算法，最常見的搜索演算法，前提是序列已經有序 還有深度優先和廣度有限搜索；及使用剪枝，A*，hash表等方法對其進行優化。 三、當然，對於基本數據結構，棧，隊列，樹。都有一些基本的操作 例如，棧的pop，push，隊列的取隊頭，如隊；以及這些數據結構的具體實現，使用連續的存儲空間（數組），還是使用鏈表，兩種具體存儲方法下操作方式的具體實現也不一樣。 還有樹的操作，如先序遍歷，中序遍歷，後續遍歷。 當然，這些只是一些基本的針對數據結構的演算法。 而基本演算法的思想應該有：1、回溯2、遞歸3、貪心4、動態規劃5、分治有些數據結構教材沒有涉及基礎演算法，lz可以另外找一些基礎演算法書看一下。有興趣的可以上oj做題，呵呵。演算法真的要學起來那是挺費勁。

㈢ 數據結構與演算法基礎知識

1.數據結構的邏輯結構

(1)集合結構

(2)線性結構(存在唯一的第一個元素與唯一的最後一個元素)(eg: 線性表、隊列、棧、字元串、數組、鏈表)

(3)樹形結構(一對多)

(4)圖形結構(多對多)

2.數據結構的物理(存儲)結構

(1).順序存儲結構(插入與刪除低效因為要挪動其他元素的位置。但是遍歷簡單)

(2).鏈式存儲結構(插入與刪除高效，但是遍歷低效)

3.大O表示法(注意大O表示法表達的是最壞的情況)

規則：

(1)用常數1取代其他所有的常數(注意常數0也當1算)(3 -> 1, O(1))

(2) 只保留最高階項(n^3+2n^2+5 ->n^3, O(n^3))

(3) 若存在最高階，省略與其想成的常數(2n^3 -> n^3, O(n^3))

4. 時間復雜度類型

(1)常數階

(2)線性階

(3)平方階

(4)對數階

(5)立方階

(6)nlog階

(7)指數階(O(2^n)或O(n!), 往往會造成噩夢般的時間消耗)

5. 空間復雜度(用大O表示法求解改演算法的輔助空間即可，例如用於交換變數用的臨時變數的數量)

六. 順序存儲的線性表

線性表結構特點：

(1) 存在唯一一個的被稱作」第一個」的數據元素；

(2) 存在唯一一個的被稱作」第二個」的數據元素；

(3) 除了第一個元素以外，結構中的每個數據元素均有一個前驅；

(4) 除了最後一個元素以外，結構中的每個數據元素均有一個後繼。

七. 鏈式存儲的線性表(單鏈表)

首元結點是鏈表中第一個值域不為空的結點。

頭結點是一個值域為空且處於首位的結點。

首指針可指向首元結點也可指向頭結點，但是如果指向頭結點可以更加方便的處理單鏈表的插入和刪除問題，不用再對首位做額外判斷，並且指向頭節點的指針永遠不用變化。

*注意一下單鏈表的前插法和尾插法。尾插法更符合邏輯

㈣ 01 - 數據結構和演算法的認識

了解數據結構和演算法的一些基本概念，主要掌握時間復雜度的計算

數據結構是指所有數據元素以及數據元素之間的關系，可以看做是相互之間存在著某種特定關系的數據元素的集合，即可以把數據結構看成是 帶結構的數據元素的集合 。

數據的邏輯結構是從邏輯關繫上描述數據的，常常將數據的邏輯結構簡稱為數據結構。

集合：

樹形結構：

圖形結構：

邏輯結構在計算機中的存儲方式。依賴於計算機語言

順序存儲結構：

鏈式存儲結構：

索引存儲結構：

散列（哈希）存儲結構：

數據類型是一組性質相同的值的集合和定義在此集合上的一組操作的總稱，數據類型是數據結構在計算機的具體體現。

注意：

演算法是對特定問題求解步驟的一種描述

特性： 有窮性、確定性、可行性、有輸入、有輸出

演算法設計好後，還需要分析演算法的優劣，從兩方面考慮

一個演算法由控制結構和原操作構成，演算法的運算時間取決於兩者的綜合效果，演算法執行時間大致為基本運算時所需時間與運行次數的乘積。因此一個演算法的執行效率可以由其最基本的運算的執行次數來衡量。

計算公式： T(n)=O(f(n))

說明：

注意： O 的作用在於只求出T(n)的最高階項，忽略低階項和常數

O(1)
沒有進行循環的演算法中，基本運算次數與問題規模無關，所以是常數

對數階 O(log2n)
次數為x，而2的x次方等於n，那麼就是對數階

線性階 O(n)
只有一層循環

平方階 O(n^2)

立方階 O(n^3)
三層循環，肯定就是n^3了

排序：
O(1) < O(logn) < O(n) < O(nlogn) < O(n^2) < O(n^3) <O(2^n) < O(n!) < O(n^n)

也叫加權平均時間復雜度，將執行的概率也加入計算。

是一種特殊的加權平均時間復雜度，把耗時多的操作分攤到耗時低的操作。

這個時間復雜度 其實是O(1),而不是O(n)

演算法空間復雜度是指計算演算法所需的存儲空間， 其計算公式為S(n) = n(f(n))
所以在考察演算法的空間復雜度，主要考慮演算法執行所需要的臨時佔用的存儲空間大小的量度。

數組逆序,將一維v1.43數組a中的n個數逆序存放在原數組中.

復雜度計算:

說明：