数据结构与算法绪论
一. 數(shù)據(jù)結(jié)構(gòu)相關(guān)概念
- 1.數(shù)據(jù)：
用于描述客觀事物的數(shù)值、字符，以及一切可以輸入到計(jì)算機(jī)中的并由計(jì)算機(jī)程序加以處理的符號(hào)的集合。 - 2.數(shù)據(jù)元素：
數(shù)據(jù)的基本單位，通常作為一個(gè)整體進(jìn)行考慮和處理 - 3.數(shù)據(jù)項(xiàng)：
是數(shù)據(jù)的不可分割的最小單位，一個(gè)數(shù)據(jù)元素可由若干個(gè)數(shù)據(jù)項(xiàng)組成 - 4.數(shù)據(jù)對(duì)象：
性質(zhì)相同的元素的集合叫做數(shù)據(jù)對(duì)象
二.邏輯結(jié)構(gòu)
- 1.概念：數(shù)據(jù)結(jié)構(gòu)中描述的是數(shù)據(jù)元素之間的抽象關(guān)系(邏輯關(guān)系)，稱為邏輯結(jié)構(gòu)
- 2.線性結(jié)構(gòu)：線性結(jié)構(gòu)中數(shù)據(jù)元素之間是一對(duì)一的關(guān)系（線性表、數(shù)組、隊(duì)列、雙隊(duì)列、棧、串）
- 3.非線性結(jié)構(gòu)：
樹：樹形結(jié)構(gòu)中的數(shù)據(jù)元素之間存在一對(duì)多的層次關(guān)系
圖：數(shù)據(jù)元素是多對(duì)多的關(guān)系
多維數(shù)組： - 4.集合：集合結(jié)構(gòu)中的數(shù)據(jù)元素除了同屬于一個(gè)集合外，它們之間沒有其它關(guān)系 集合：集合結(jié)構(gòu)中的數(shù)據(jù)元素除了同屬于一個(gè)集合外，它們之間沒有其它關(guān)系
三.物理結(jié)構(gòu)
數(shù)據(jù)結(jié)構(gòu)在計(jì)算機(jī)中的表示(又稱映像，也稱物理結(jié)構(gòu))，存儲(chǔ)結(jié)構(gòu)主要分為順序存儲(chǔ)（線性表）、鏈?zhǔn)酱鎯?chǔ)（鏈?zhǔn)奖?#xff09;、索引存儲(chǔ)和散列(哈希)存儲(chǔ)。
- 1.順序存儲(chǔ)結(jié)構(gòu):借助數(shù)據(jù)元素之間的相對(duì)位置來表示元素之間的邏輯結(jié)構(gòu).（vector動(dòng)態(tài)數(shù)組、 deque雙端隊(duì)列、stack棧容器、queue隊(duì)列容器）
- 2.鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu):借助數(shù)據(jù)元素之間的元素的指針表示數(shù)組元素的邏輯結(jié)構(gòu).
- 3.散列存儲(chǔ)結(jié)構(gòu):順序存儲(chǔ)+算列.（哈希表）
- 4.索引存儲(chǔ)結(jié)構(gòu):順序存儲(chǔ)+索引.
四.數(shù)據(jù)運(yùn)算
- 1.插入
- 2.修改
- 3.刪除
- 4.查找
靜態(tài)查找：對(duì)查找表只作查找操作的查找表
動(dòng)態(tài)查找：查找過程中同時(shí)插入表中不含的元素，或者 刪除查找表中已有的元素的操作的查找表
順序查找：順序查找又稱線性查找，是最基本的查找方法之一。順序查找既 適用于順序表，也適用于鏈表。
二分法（折半）查找：是一種效率較高的查找方法，但前提是表中元素必須 按關(guān)鍵字有序（按關(guān)鍵字遞增或遞減）排列。
分塊查找：塊內(nèi)無序、塊間有序、如何分塊 效率最高
動(dòng)態(tài)查找表：二叉排序樹查找。
哈希表：哈希函數(shù)構(gòu)造：直接定址法、除留余數(shù)法、平方取中法，隨機(jī)數(shù)法，數(shù)字分析法。
五.排序
1.直接插入排序：
- 每次將一個(gè)待排序的數(shù)據(jù)元素，插入到前面已經(jīng)排好序的數(shù)列中的適當(dāng)位置，使數(shù)列依然有序；直到待排序數(shù)據(jù)元素全部插入完為止。
2.希爾排序：
- 基本思想：先將整個(gè)待排序記錄序列分成為若干個(gè)子序列分別進(jìn)行直接插入排序，待整個(gè)序列中的記錄 基本有序 時(shí)在對(duì)全體序列進(jìn)行一次直接插入排序，子序列的構(gòu)成不是簡(jiǎn)單的逐段分割，而是將像個(gè)某個(gè)增量的記錄組成一個(gè)子序列。
3.冒泡排序：
- 也稱冒泡法，每相鄰兩個(gè)記錄關(guān)鍵字比大小,大的記錄往下沉（也可以小的往上浮）。每一遍把最后一個(gè)下沉的位置記下，下一遍只需檢查比較到此為止；到所有記錄都不發(fā)生下沉?xí)r，整個(gè)過程結(jié)束（每交換一次，記錄減少一個(gè)反序數(shù)。
4.快速排序：
- 在當(dāng)前無序區(qū)R【1…H】中任取一個(gè)數(shù)據(jù)元素作為比較的"基準(zhǔn)"(不妨記為X)，用此基準(zhǔn)將當(dāng)前無序區(qū)劃分為左右兩個(gè)較小的無序區(qū)：R【1…I-1】和R【I+1…】，且左邊的無序子區(qū)中數(shù)據(jù)元素均小于等于基準(zhǔn)元素，右邊的無序子區(qū)中數(shù)據(jù)元素均大于等于基準(zhǔn)元素，而基準(zhǔn)X則位于最終排序的位置上，即R【1…I-1】≤X.Key≤R【I+1…H】(1≤I≤H)，當(dāng)R【1…I-1】和R【I+1…H】均非空時(shí)，分別對(duì)它們進(jìn)行上述的劃分過程，直至所有無序子區(qū)中的數(shù)據(jù)元素均已排序?yàn)橹埂?/li>
5.簡(jiǎn)單選擇排序：
- 每一趟從待排序的數(shù)據(jù)元素中選出最小（或最大）的一個(gè)元素，順序放在已排好序的數(shù)列的最后，直到全部待排序的數(shù)據(jù)元素排完。
6.堆排序：
- 堆排序是一樹形選擇排序，在排序過程中，將R[1…N]看成是一顆完全二叉樹的順序存儲(chǔ)結(jié)構(gòu)，利用完全二叉樹中雙親結(jié)點(diǎn)和孩子結(jié)點(diǎn)之間的內(nèi)在關(guān)系來選擇最小的元素。
7.二路歸并排序
8.基數(shù)排序
各排序算法比較：
六.算法
1.特性
- 有窮性：
算法的執(zhí)行步驟、時(shí)間、都是有限的。不會(huì)無休止的一直執(zhí)行下去。 - 確切性：
算法的每一步都必須有明確的定義和描述。 - 輸入：
一個(gè)算法應(yīng)該有相應(yīng)的輸入條件，就像我們小時(shí)候做的應(yīng)用題，已知什么什么。來求某個(gè)結(jié)果，已知部分便是輸入條件。 - 輸出：
算法必須有明確的結(jié)果輸出。沒有結(jié)果，那這個(gè)算法是沒有任何意義的。 - 可行性：
算法的步驟必須是可行的，無法執(zhí)行的則沒有意義，也解決不了任何問題
2.算法的分類
-按照算法的應(yīng)用來分：
算法可以分為基本算法、幾何算法、加密/解密算法、查找算法、圖標(biāo)數(shù)據(jù)分析算法等。
- 按照算法的思路來分：
算法可以分為遞推算法、遞歸算法、窮舉算法、分治算法、概率算法等。
3.重點(diǎn)介紹算法基本思路
- 窮舉算法思想：
- 根據(jù)題目的部分條件確定范圍，并在次范圍內(nèi)對(duì)所有情況逐一窮盡驗(yàn)證，直到找到那個(gè)最符合的解。如循環(huán)遍歷找解。
- 遞推算法思想：
- 遞推算法是一種理性思維模式的代表，根據(jù)已有的數(shù)據(jù)和關(guān)系，逐步推導(dǎo)而得到結(jié)果，通常是根據(jù)前面的一些項(xiàng)得到后面的一些項(xiàng)。如斐波那契數(shù)列。
- 遞歸算法思想：
- 1.直接遞歸 ，在方法中調(diào)用自身。
- 2.間接遞歸，間接的調(diào)用一個(gè)方法。比如方法a調(diào)用方法b，方法b又調(diào)用方法a。
- 遞歸方法在編寫時(shí)，要注意使用if語句來在某些情況下強(qiáng)制退出遞歸返回結(jié)果。否則，會(huì)形成死循環(huán)。無法結(jié)束，當(dāng)然也無法得到實(shí)際問題的解
使用遞歸，可以是代碼更簡(jiǎn)潔清晰，可讀性更好。如八皇后問題、漢諾塔問題，階乘計(jì)算。 - 分治算法思想:
- 基本思想是將一個(gè)計(jì)算復(fù)雜的問題分為規(guī)模較小，計(jì)算簡(jiǎn)單的小問題求解，然后綜合各個(gè)小問題，從而得到最終答案。例如我們常說的合并排序、二分法查找、堆排序、快速排序等。
- 概率算法思想:
- 概率算法依照概率統(tǒng)計(jì)的思路來求解問題，其往往不能得到問題的精確解，但是在數(shù)值計(jì)算領(lǐng)域得到了廣泛的應(yīng)用。因?yàn)楹芏鄶?shù)學(xué)問題，往往需要通過數(shù)值計(jì)算來求解近似值。數(shù)值概率算法;
蒙特卡羅(Monte Carlo)算法;拉斯維加斯(Las Vegas)算法;舍伍德(Sherwood)算法;
總結(jié)
- 上一篇： 发个红包封面
- 下一篇： 互联网晚报 | 8月12日 星期四 |