前言

該學(xué)習(xí)參考的書籍為《大話數(shù)據(jù)結(jié)構(gòu)》寇僧，需要一定的數(shù)學(xué)底子和編程思維助析，一個(gè)真正的程序員怎么能不懂?dāng)?shù)據(jù)結(jié)構(gòu)和算法仍劈，既然自己的發(fā)展方向是技術(shù)装悲，那就只能堅(jiān)持昏鹃！

數(shù)據(jù)結(jié)構(gòu)的基本概念

• 數(shù)據(jù)結(jié)構(gòu)是相互間存在一種或多種特定關(guān)系得數(shù)據(jù)元素的集合

• 數(shù)據(jù)結(jié)構(gòu)是一門研究非數(shù)值計(jì)算的程序設(shè)計(jì)問題中的操作對(duì)象，以及它們之間的關(guān)系和操作等相關(guān)問題的學(xué)科

• 數(shù)據(jù)是描述客觀事物的符號(hào)诀诊，是計(jì)算機(jī)中可以操作的對(duì)象洞渤，是能被計(jì)算機(jī)識(shí)別，并輸入給計(jì)算機(jī)處理的符號(hào)集合

• 數(shù)據(jù)元素是組成數(shù)據(jù)的属瓣、有一定意義的基本單位载迄，在計(jì)算機(jī)中通常作為整體處理讯柔，也被稱為記錄，一個(gè)數(shù)據(jù)元素可以由若干個(gè)數(shù)據(jù)項(xiàng)組成护昧，數(shù)據(jù)項(xiàng)是數(shù)據(jù)不可分割的最小單位

• 數(shù)據(jù)對(duì)象是性質(zhì)相同的數(shù)據(jù)元素的集合魂迄，是數(shù)據(jù)的子集

• 結(jié)構(gòu)是指各個(gè)組成部分相互搭配和排列的方式，簡單理解就是關(guān)系惋耙，在現(xiàn)實(shí)世界中捣炬，不同的數(shù)據(jù)元素之間不是獨(dú)立的，而是存在特定的關(guān)系绽榛，我們將這些關(guān)系稱為結(jié)構(gòu)

數(shù)據(jù)結(jié)構(gòu)的分類

按照視點(diǎn)的不同湿酸，數(shù)據(jù)結(jié)構(gòu)分為邏輯結(jié)構(gòu)和物理結(jié)構(gòu)

• 邏輯結(jié)構(gòu)分為四種
  1、集合結(jié)構(gòu)：集合結(jié)構(gòu)中的數(shù)據(jù)元素除了同屬于一個(gè)集合外灭美，它們之間沒有其他關(guān)系
  2推溃、線性結(jié)構(gòu)：線性結(jié)構(gòu)中的數(shù)據(jù)元素是一對(duì)一的關(guān)系
  3、樹形結(jié)構(gòu)：樹形結(jié)構(gòu)中的數(shù)據(jù)元素之間存在一種一對(duì)多的層次關(guān)系
  4届腐、圖形結(jié)構(gòu)：圖形結(jié)構(gòu)的數(shù)據(jù)元素是多對(duì)多的關(guān)系

• 物理結(jié)構(gòu)铁坎，是指數(shù)據(jù)的邏輯結(jié)構(gòu)在計(jì)算機(jī)中的存儲(chǔ)形式，也叫存儲(chǔ)結(jié)構(gòu)梯捕，分為兩種：
  1厢呵、順序存儲(chǔ)結(jié)構(gòu)：是把數(shù)據(jù)元素存放在地址連續(xù)的存儲(chǔ)單元里，其數(shù)據(jù)間的邏輯關(guān)系和物理關(guān)系是一致的
  2傀顾、鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)：是把數(shù)據(jù)元素存放在任意的存儲(chǔ)單元里襟铭，這組存儲(chǔ)單元可以是連續(xù)的，也可以是不連續(xù)的短曾。數(shù)據(jù)元素的存儲(chǔ)關(guān)系并不能反映其邏輯關(guān)系寒砖，因此需要用一個(gè)指針存放數(shù)據(jù)元素的地址，這樣通過地址就可以找到相關(guān)聯(lián)數(shù)據(jù)元素的位置

邏輯結(jié)構(gòu)是面向問題的嫉拐，而物理結(jié)構(gòu)是面向計(jì)算機(jī)的哩都，其基本的目標(biāo)就是將數(shù)據(jù)及其邏輯關(guān)系存儲(chǔ)到計(jì)算機(jī)的內(nèi)存中

• 數(shù)據(jù)類型是指一組性質(zhì)相同的值的集合及定義在此集合上的一些操作的總稱
• 抽象是指抽取出事物具有的普遍性的本質(zhì)，它是抽出問題的特征而忽略非本質(zhì)的細(xì)節(jié)婉徘，是對(duì)具體事物的一個(gè)概括漠嵌，抽象是一種思考問題的方式，它隱藏了繁雜的細(xì)節(jié)盖呼，只保留實(shí)現(xiàn)目標(biāo)所必須的信息
• 抽象數(shù)據(jù)類型是指一個(gè)數(shù)學(xué)模型及定義在該模型上的一組操作儒鹿，體現(xiàn)了程序設(shè)計(jì)中問題分解、抽象和信息隱藏的特性

算法的基本概念

算法是解決特定問題求解步驟的描述几晤，在計(jì)算機(jī)中表現(xiàn)為指令的有限序列约炎，并且每條指令表示一個(gè)或多個(gè)操作

• 算法具有五個(gè)基本特性：輸入、輸出、有窮性圾浅、確定性和可行性
  1掠手、輸入輸出：算法具有零個(gè)或多個(gè)輸入，一個(gè)或多個(gè)輸出
  2狸捕、有窮性：算法在執(zhí)行有限的步驟后喷鸽，自動(dòng)結(jié)束而不會(huì)出現(xiàn)無限循環(huán)，并且每一個(gè)步驟在可接受的時(shí)間內(nèi)完成
  3府寒、確定性：算法的每一步驟都具有確定的含義魁衙，不會(huì)出現(xiàn)二義性
  4、可行性：算法的每一步都必須是可行的株搔，也就是說剖淀，每一步都能夠通過執(zhí)行有限次數(shù)完成

• 算法設(shè)計(jì)要求：正確性、可讀性纤房、健壯性纵隔、時(shí)間效率高和存儲(chǔ)量低
  1、正確性：算法的正確性是指算法至少應(yīng)該具有輸入炮姨、輸出和加工處理無歧義性捌刮，能正確反映問題的需求，能夠得到問題的正確答案舒岸，正確性有以下四個(gè)層次
  （1）無語法錯(cuò)誤
  （2）對(duì)于合法的輸入數(shù)據(jù)能夠產(chǎn)生滿足要求的輸出結(jié)果
  （3）對(duì)于非法的輸入數(shù)據(jù)能夠得出滿足規(guī)格說明的結(jié)果
  （4）對(duì)于精心選擇的绅作、甚至是刁難的測試數(shù)據(jù)都有滿足要求的輸出結(jié)果

通常把（3）作為正確性標(biāo)準(zhǔn)，（4）實(shí)現(xiàn)成本太高

2蛾派、可讀性：算法設(shè)計(jì)的另一個(gè)目的是為了便于閱讀俄认、理解和交流
3、健壯性：當(dāng)輸入數(shù)據(jù)不合法時(shí)洪乍，算法也能做出相關(guān)處理眯杏，而不是產(chǎn)生異常或莫名其妙的結(jié)果
4壳澳、時(shí)間效率高和存儲(chǔ)量低：指執(zhí)行時(shí)間短岂贩、占用內(nèi)存和外部硬盤存儲(chǔ)空間少

算法效率的度量方法

算法效率的度量方法，通常說的是執(zhí)行時(shí)間的度量巷波，有事后統(tǒng)計(jì)方法和事前分析估算方法

• 事后統(tǒng)計(jì)方法：這種方法主要是通過設(shè)計(jì)好的測試程序和數(shù)據(jù)萎津，利用計(jì)算機(jī)計(jì)時(shí)器對(duì)不同算法編制的程序的運(yùn)行時(shí)間進(jìn)行比較，從而確定算法效率的高低抹镊，但這種方法有很大缺陷姜性，是不推薦的，至于它的缺點(diǎn)有以下：
  1髓考、需要根據(jù)算法編寫測試程序，如果算法不好弃酌，測試程序就白寫了
  2氨菇、時(shí)間比較依賴硬件儡炼、軟件等各種因素，無法橫向比較
  3查蓉、算法的測試數(shù)據(jù)設(shè)計(jì)困難乌询，什么樣的數(shù)據(jù)才能保證結(jié)果客觀難以界定

• 事前分析估算方法：在計(jì)算機(jī)程序編制前，依據(jù)統(tǒng)計(jì)方法對(duì)算法進(jìn)行估算豌研。高級(jí)編程語言編寫的程序在計(jì)算機(jī)上運(yùn)行時(shí)所消耗的和時(shí)間取決于以下因素：
  1妹田、算法采用的策略、方法
  2鹃共、編譯產(chǎn)生的代碼質(zhì)量
  3鬼佣、問題的輸入規(guī)模
  4、機(jī)器執(zhí)行指令的速度

其中拋開硬件和軟件的因素霜浴，程序運(yùn)行時(shí)間依賴于（1）（2）

測定運(yùn)行時(shí)間

測定運(yùn)行時(shí)間最可靠的方法就是計(jì)算對(duì)運(yùn)行時(shí)間有消耗的基本操作的執(zhí)行次數(shù)晶衷，運(yùn)行時(shí)間與這個(gè)計(jì)算成正比。分析算法的運(yùn)行時(shí)間時(shí)阴孟，重要的是把基本操作的數(shù)量與輸入規(guī)模關(guān)聯(lián)起來晌纫，即基本操作的數(shù)量必須表示成輸入規(guī)模的函數(shù)

• 函數(shù)的漸近增長：給定兩個(gè)函數(shù)f(n)和g(n)，如果存在一個(gè)整數(shù)N永丝，使得對(duì)于所有的n>N锹漱，f(n)總是比g(n)大，那么我們說f(n)的增長漸近快于g(n)慕嚷，算法的優(yōu)劣要根據(jù)輸入規(guī)模做綜合考量

• 判斷一個(gè)算法的效率時(shí)哥牍，函數(shù)中的常數(shù)和其他次要項(xiàng)常常可以忽略闯冷，而更應(yīng)該關(guān)注主項(xiàng)（最高階項(xiàng)）的階數(shù)砂心，也就是函數(shù)中的常數(shù)可以忽略

• 算法時(shí)間復(fù)雜度：在進(jìn)行算法分析時(shí)，語句總的執(zhí)行次數(shù)T(n)是關(guān)于問題規(guī)模n的函數(shù)蛇耀，進(jìn)而分析T(n)隨n變化情況并確定T(n)的數(shù)量級(jí)辩诞。算法的時(shí)間復(fù)雜度，也就是算法的時(shí)間量度纺涤，記作T(n)=O(f(n))译暂。它表示隨問題規(guī)模n的增大，算法執(zhí)行時(shí)間的增長率和f(n)的增長率相同撩炊，稱作算法的漸近時(shí)間復(fù)雜度外永，簡稱為時(shí)間復(fù)雜度。其中f(n)是問題規(guī)模n的某個(gè)函數(shù)拧咳，這種記法也稱為大O記法伯顶，一般情況下，隨著n增大，T(n)增長最慢的算法為最優(yōu)算法祭衩。

• 推導(dǎo)大O階的方法
  1灶体、用常數(shù)1取代運(yùn)行時(shí)間中的所有加法常數(shù)
  2、在修改后的運(yùn)行次數(shù)函數(shù)中掐暮，只保留最高階項(xiàng)
  3蝎抽、如果最高階項(xiàng)存在且系數(shù)不是1，則去除與這個(gè)項(xiàng)相乘的系數(shù)

常數(shù)階路克，表示為O(1)樟结，執(zhí)行時(shí)間恒定與輸入規(guī)模無關(guān)，對(duì)于分支結(jié)構(gòu)if...else精算，無論真假瓢宦，執(zhí)行的次數(shù)都是恒定的，也是O(1)
線性階殖妇，表示為O(n)刁笙，分析循環(huán)結(jié)構(gòu)的運(yùn)行情況
對(duì)數(shù)階，表示為O(logn)