-
程序設計 = 數(shù)據(jù)結(jié)構(gòu) + 算法
-
1.緒論
-
1.1基本概念和術(shù)語
-
1.1.1數(shù)據(jù)
數(shù)據(jù)：是描述客觀事物的符號，是計算機中可以操作的對象，是可以被計算機識別并輸入給計算機處理的符號集合。
我們這里說的數(shù)據(jù)，其實就是符號，而且這個符號必須包含以下兩個前提條件：
1.可以輸入到計算機中
2.可以被計算機程序處理 -
1.1.2 數(shù)據(jù)元素
數(shù)據(jù)元素：是組成數(shù)據(jù)的具有一定意義的基本單位，在計算機中通常會整體處理，也稱為記錄 -
1.1.3 數(shù)據(jù)項
數(shù)據(jù)元素是由若干個數(shù)據(jù)項組成，比如說人這個數(shù)據(jù)元素是由手腳眼口鼻等數(shù)據(jù)項組成，也可以由年齡，性別等數(shù)據(jù)項組成
數(shù)據(jù)項是數(shù)據(jù)不可分割的最小對象。雖然數(shù)據(jù)項是數(shù)據(jù)的最小單位，但是真正討論問題時，數(shù)據(jù)元素才是數(shù)據(jù)結(jié)構(gòu)中建立數(shù)據(jù)原型的著眼點 -
1.1.4 數(shù)據(jù)對象
數(shù)據(jù)對象：是性質(zhì)相同的數(shù)據(jù)元素的集合，是數(shù)據(jù)的子集
比如說一個數(shù)據(jù)對象，它擁有姓名，年齡，性別等相同的數(shù)據(jù)元素 -
1.1.5 數(shù)據(jù)結(jié)構(gòu)
結(jié)構(gòu)：簡單的理解就是關系。不同數(shù)據(jù)之間不是獨立的，而是存在特定的關系，我們將這些關系稱為結(jié)構(gòu)
數(shù)據(jù)結(jié)構(gòu)：相互之間存在一種或者幾種關系的數(shù)據(jù)元素的集合 -
1.2邏輯結(jié)構(gòu)與物理結(jié)構(gòu)
-
1.2.1邏輯結(jié)構(gòu)
邏輯結(jié)構(gòu)：指數(shù)據(jù)對象中數(shù)據(jù)元素之間的相互關系
1.集合結(jié)構(gòu)
集合結(jié)構(gòu)：集合結(jié)構(gòu)中的數(shù)據(jù)元素除了屬于同一集合外沒有其他的關系
2.線性結(jié)構(gòu)
線性結(jié)構(gòu)：線性結(jié)構(gòu)中的數(shù)據(jù)元素之間的關系都是一對一的關系
3.樹形結(jié)構(gòu)
樹形結(jié)構(gòu)：樹形結(jié)構(gòu)中的數(shù)據(jù)元素之間的關系存在一對多的層級關系
4.圖形結(jié)構(gòu)
圖形結(jié)構(gòu)：圖形結(jié)構(gòu)之間的數(shù)據(jù)元素之間的關系是多對多的關系 -
1.2.2 物理結(jié)構(gòu)
物理結(jié)構(gòu)是指數(shù)據(jù)的邏輯結(jié)構(gòu)在計算機中的存儲形式
1.順序存儲結(jié)構(gòu)
是把數(shù)據(jù)元素存放在地址連續(xù)的存儲單元內(nèi)，其數(shù)據(jù)間的邏輯關系與物理關系是一致的
數(shù)組就是這種，其實就是在內(nèi)存中開辟一段地址空間，然后按順序一個一個排隊，不許插隊，每個人占一段空間
2.鏈式存儲結(jié)構(gòu)
是把數(shù)據(jù)元素放在任意的存儲單元里，這組存儲單位可以是連續(xù)的，也可以是不連續(xù)的。
數(shù)據(jù)元素的存儲關系并不能反映其邏輯關系，因此需要一個指針來存放數(shù)據(jù)元素的地址，通過地址來找到數(shù)據(jù)元素的位置
邏輯結(jié)構(gòu)是面向問題的，物理結(jié)構(gòu)是面向計算機的，其基本的目標就是將數(shù)據(jù)及其邏輯關系存儲到計算機的內(nèi)存中
-
2.算法
-
2.1算法定義
算法是解決特定問題的求解步驟的描述，在計算機中表現(xiàn)為指令的有限數(shù)列，并且每條指令表示一個或多個操作
算法的定義中提到了指令，指令能被人或機器等計算裝置執(zhí)行，他可以是計算機指令，也可以是我們平時使用的語言文字
為了解決某個或者某類問題，需要把指令表示成一定的操作序列，操作序列包括一組操作，每一個操作完成特定的功能，這就是算法 -
2.2算法的特性
-
2.2.1輸入輸出
算法具有零個或者多個輸入，一般的算法都有多個輸入，零個輸入的算法比如說打印一個“HELLO WORLD!”
算法具有一個或者多個輸出，算法一定具有輸出，不然這個算法就沒有了存在的意義；輸出的形式可以的打印也可以是返回一個或者多個值。 -
2.2.2有窮性
指算法在執(zhí)行完有限的步驟后，自動結(jié)束而不會進行無限循環(huán)，并且每個步驟在可接受的時間內(nèi)完成。如果說一個算法可以完成，但是要花上數(shù)十年，這在數(shù)學上雖然是有窮的，但是這么久的算法也沒有其存在的意義
-
2.2.3確定性
算法的每一個步驟都具有確定的意義，不會出現(xiàn)二義性
-
2.2.4可行性
算法的每一個步驟都是可行的，每一步都是可以通過執(zhí)行有限次數(shù)完成的
-
2.3算法設計的要求
-
2.3.1正確性
算法的正確性是指沙發(fā)俺應該至少具有輸入、輸出和加工處理無歧義性、能正確反映問題的需求、能夠得到問題的正確答案
算法 -
2.3.2可讀性
算法設計的另一目的是為了便于閱讀、理解和交流
-
2.3.3健壯性
當輸入的數(shù)據(jù)不合法時，算法也能進行處理，我不是產(chǎn)生異?；蛘吣涿畹慕Y(jié)果
-
2.3.4時間效率高和存儲量低
-
2.4算法效率的度量方法
-
2.4.1事后統(tǒng)計方法
這種方法主要是通過設計好的測試程序和數(shù)據(jù)，利用計算機計時器對不同算法編譯的程序的運行時間進行比較，從而確定算法效率的高低
這種方法有很大缺陷，不用這種方法度量 -
2.4.2事前分析估算方法
在計算機編譯前，依據(jù)統(tǒng)計方法對算法進行估算
消耗的時間因素：
1.算法采用的策略、方法
2.編譯產(chǎn)生的代碼質(zhì)量
3.問題的輸入規(guī)模
4.機器執(zhí)行指令的速度 -
2.5算法時間復雜度
-
2.5.1算法時間復雜度定義
-
2.5.2常見的時間復雜度
image.png
image.png -
3 線性表
-
3.1 線性表的定義
零個或多個數(shù)據(jù)元素的有限序列。
線性表首先是一個序列，也就是元素之間是有順序的，每個元素只有一個前驅(qū)和后繼，當然第一個元素沒有前驅(qū)和最后一個元素沒有后繼
線性表中的元素是有限的，無限的數(shù)列只存在于數(shù)學模型中- 線性表元素個數(shù)n（n>=0）定義為線性表的長度，當n=0時，為空表
-
3.2 線性表的抽象數(shù)據(jù)類型
image.png -
3.3 線性表鏈式存儲結(jié)構(gòu)
對于數(shù)據(jù)Ai而言，不僅僅要存儲其本身的信息外，還需要存儲一個指示其直接后繼的信息（即其直接后繼的存儲位置）。
把存儲元素信息的域稱為數(shù)據(jù)域，把存儲直接后繼位置的域稱為指針域。指針域中存儲的信息稱作指針。這兩部分信息組成數(shù)據(jù)元素Ai的存儲映像，稱為結(jié)點（Node）
n個結(jié)點鏈結(jié)成一個鏈表，即為線性表的鏈式存儲結(jié)構(gòu)，因為此鏈表的結(jié)點只包含一個指針域，所以叫單鏈表。
image.png
對于線性表而言，總得有個頭有個尾，鏈表也是一樣。我們把鏈表中第一個結(jié)點的存儲位置叫做頭指針，整個鏈表的存取必須從頭指針開始進行；相應的，鏈表的最后一個節(jié)點指針為空（通常用NULL來表示）。
-
有時為了更加方便地對鏈表進行操作，會在單鏈表的第一個結(jié)點前附設一個結(jié)點，稱為頭結(jié)點。頭結(jié)點的數(shù)據(jù)域可以不存儲任何信息，或者可以存儲如線性表的長度等附加信息，頭結(jié)點的指針域存儲指向第一個結(jié)點的指針
image.png -
3.4 頭指針和頭結(jié)點的異同
頭指針：
1.頭指針是指鏈表指向頭一個結(jié)點的指針 ，若鏈表有頭結(jié)點，則是指向頭結(jié)點的指針
2.頭指針具有標識作用，所以常用頭指針冠以鏈表的名字
3.無論鏈表是否為空，頭指針均不為空。頭指針是鏈表的必要元素頭結(jié)點：
1.頭結(jié)點是為了操作的統(tǒng)一和方便而建立的，放在第一元素的結(jié)點之前，其數(shù)據(jù)域一般無意義（也可存放鏈表的長度）
2.有了頭結(jié)點，對于第一元素結(jié)點前插入結(jié)點和刪除第一節(jié)點，其操作與其他結(jié)點的操作就統(tǒng)一了
3.頭結(jié)點不一定是鏈表第一要素-
3.5 單鏈表的插入與刪除
-
插入步驟
image.png -
代碼實現(xiàn)
image.png -
刪除步驟
image.png -
代碼實現(xiàn)
image.png
-
-
3.6 單鏈表的整表創(chuàng)建
-
算法
image.png -
代碼
image.png
-
