一馅袁、數(shù)據(jù)結(jié)構(gòu)

1、常見數(shù)據(jù)結(jié)構(gòu)：Array(數(shù)組)荒辕、Stack(棧)汗销、Queue(隊(duì)列)、LinkedList(鏈表)抵窒、Tree(樹)弛针、Hash（哈希表）、Heap(堆)估脆、Graph(圖)

2钦奋、各種數(shù)據(jù)結(jié)構(gòu)總結(jié)：

（1）、數(shù)組：

????優(yōu)點(diǎn)：插入數(shù)據(jù)快

????缺點(diǎn)：查找慢，刪除慢付材，大小固定朦拖，只能存儲單一元素

（2）、有序數(shù)組：

????優(yōu)點(diǎn)：比無序數(shù)組查詢快

????缺點(diǎn)：查找慢厌衔，刪除慢璧帝，大小固定，只能存儲單一元素

（3）富寿、棧：

????優(yōu)點(diǎn)：先進(jìn)后出

????缺點(diǎn)：存取很慢

（4）睬隶、隊(duì)列：

????優(yōu)點(diǎn)：先進(jìn)先出

????缺點(diǎn)：存取很慢

（5）、鏈表：

????優(yōu)點(diǎn)：插入快页徐，刪除快

????缺點(diǎn)：查找很慢

（6）苏潜、二叉樹：

????優(yōu)點(diǎn)：如果樹是平橫的，查找变勇、刪除恤左、插入都很快

????缺點(diǎn)：刪除算法復(fù)雜

（7）、紅黑樹：

????優(yōu)點(diǎn)：樹總是平衡的搀绣，查找飞袋、刪除、插入都很快

????缺點(diǎn)：算法復(fù)雜

（8）链患、2-3-4樹：

????優(yōu)點(diǎn)：樹總是平衡的肉康，類似的樹對磁盤存儲有效嫡霞，

????缺點(diǎn)：算法復(fù)雜

（9）坠非、哈希表：

????優(yōu)點(diǎn)：如果已知關(guān)鍵字則存取極快

????缺點(diǎn)：刪除數(shù)據(jù)慢兼蕊，不知道關(guān)鍵字則存取數(shù)據(jù)都很慢，對存儲空間使用不充分

（10）芯肤、堆：

????優(yōu)點(diǎn)：插入數(shù)據(jù)和刪除數(shù)據(jù)都快巷折，對最大項(xiàng)數(shù)據(jù)存取快

????缺點(diǎn)：對其它數(shù)據(jù)項(xiàng)存取慢

（11）、圖：

????優(yōu)點(diǎn)：對現(xiàn)實(shí)世界建模

????缺點(diǎn)：有些算法慢且復(fù)雜

二崖咨、算法

? ? 1、算法5個(gè)特征：

????（1）油吭、有窮性：對于任意一組合法輸入值击蹲，在執(zhí)行又窮步驟之后一定能結(jié)束，即：算法中的每個(gè)步驟都能在有限時(shí)間內(nèi)完成婉宰。

????（2）歌豺、確定性：在每種情況下所應(yīng)執(zhí)行的操作，在算法中都有確切的規(guī)定心包，使算法的執(zhí)行者或閱讀者都能明確其含義及如何執(zhí)行类咧。并且在任何條件下，算法都只有一條執(zhí)行路徑。

????（3）痕惋、可行性：算法中的所有操作都必須足夠基本区宇，都可以通過已經(jīng)實(shí)現(xiàn)的基本操作運(yùn)算有限次實(shí)現(xiàn)之。

????（4）值戳、有輸入：作為算法加工對象的量值议谷，通常體現(xiàn)在算法當(dāng)中的一組變量。有些輸入量需要在算法執(zhí)行的過程中輸入堕虹，而有的算法表面上可以沒有輸入卧晓，實(shí)際上已被嵌入算法之中。

????（5）赴捞、有輸出：它是一組與“輸入”有確定關(guān)系的量值逼裆，是算法進(jìn)行信息加工后得到的結(jié)果，這種確定關(guān)系即為算法功能赦政。

? ? 2波附、算法的設(shè)計(jì)原則：

? ? （1）、正確性：首先昼钻，算法應(yīng)當(dāng)滿足以特定的“規(guī)則說明”方式給出的需求掸屡。其次，對算法是否“正確”的理解可以有以下四個(gè)層次：

　　　　? 一然评、程序語法錯(cuò)誤仅财。

　　　　 二、程序?qū)τ趲捉M輸入數(shù)據(jù)能夠得出滿足需要的結(jié)果碗淌。

　　　　 三盏求、程序?qū)τ诰倪x擇的、典型亿眠、苛刻切帶有刁難性的幾組輸入數(shù)據(jù)能夠得出滿足要求的結(jié)果碎罚。

　　　　 四、程序?qū)τ谝磺泻戏ǖ妮斎霐?shù)據(jù)都能得到滿足要求的結(jié)果纳像。

? ? ? ? ? ? ? ?PS：通常以第 三 層意義的正確性作為衡量一個(gè)算法是否合格的標(biāo)準(zhǔn)荆烈。

????（2）、可讀性：算法為了人的閱讀與交流竟趾，其次才是計(jì)算機(jī)執(zhí)行憔购。因此算法應(yīng)該易于人的理解；另一方面岔帽，晦澀難懂的程序易于隱藏較多的錯(cuò)誤而難以調(diào)試玫鸟。

????（3）、健壯性：當(dāng)輸入的數(shù)據(jù)非法時(shí)犀勒，算法應(yīng)當(dāng)恰當(dāng)?shù)淖龀龇磻?yīng)或進(jìn)行相應(yīng)處理屎飘，而不是產(chǎn)生莫名其妙的輸出結(jié)果妥曲。并且，處理出錯(cuò)的方法不應(yīng)是中斷程序執(zhí)行钦购，而是應(yīng)當(dāng)返回一個(gè)表示錯(cuò)誤或錯(cuò)誤性質(zhì)的值檐盟，以便在更高的抽象層次上進(jìn)行處理。

????（4）肮雨、高效率且低存儲量需求：通常算法效率值得是算法執(zhí)行時(shí)間遵堵；存儲量是指算法執(zhí)行過程中所需要的最大存儲空間，兩者都與問題的規(guī)模有關(guān)