數(shù)據(jù)結(jié)構(gòu)與算法

1赋续、算法

算法：是指解題方案的準(zhǔn)確而完整的描述。

算法不等于程序另患，也不等計(jì)算機(jī)方法纽乱，程序的編制不可能優(yōu)于算法的設(shè)計(jì)。

算法的基本特征：是一組嚴(yán)謹(jǐn)?shù)囟x運(yùn)算順序的規(guī)則昆箕，每一個(gè)規(guī)則都是有效的鸦列，是明確的，此順序?qū)⒃谟邢薜拇螖?shù)下終止鹏倘。特征包括：

（1）可行性薯嗤；

（2）確定性，算法中每一步驟都必須有明確定義纤泵，不充許有模棱兩可的解釋骆姐，不允許有多義性；

（3）有窮性捏题，算法必須能在有限的時(shí)間內(nèi)做完诲锹，即能在執(zhí)行有限個(gè)步驟后終止，包括合理的執(zhí)行時(shí)間的含義涉馅；

（4）擁有足夠的情報(bào)归园。

算法的基本要素：一是對數(shù)據(jù)對象的運(yùn)算和操作；二是算法的控制結(jié)構(gòu)稚矿。

指令系統(tǒng)：一個(gè)計(jì)算機(jī)系統(tǒng)能執(zhí)行的所有指令的集合庸诱。

基本運(yùn)算和操作包括：算術(shù)運(yùn)算、邏輯運(yùn)算晤揣、關(guān)系運(yùn)算桥爽、數(shù)據(jù)傳輸。

算法的控制結(jié)構(gòu)：順序結(jié)構(gòu)昧识、選擇結(jié)構(gòu)钠四、循環(huán)結(jié)構(gòu)。

算法基本設(shè)計(jì)方法：列舉法跪楞、歸納法缀去、遞推、遞歸甸祭、減斗遞推技術(shù)缕碎、回溯法。

算法復(fù)雜度：算法時(shí)間復(fù)雜度和算法空間復(fù)雜度池户。

算法時(shí)間復(fù)雜度是指執(zhí)行算法所需要的計(jì)算工作量咏雌。

算法空間復(fù)雜度是指執(zhí)行這個(gè)算法所需要的內(nèi)存空間凡怎。

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

數(shù)據(jù)結(jié)構(gòu)研究的三個(gè)方面：

（1）數(shù)據(jù)集合中各數(shù)據(jù)元素之間所固有的邏輯關(guān)系赊抖，即數(shù)據(jù)的邏輯結(jié)構(gòu)统倒；

（2）在對數(shù)據(jù)進(jìn)行處理時(shí)，各數(shù)據(jù)元素在計(jì)算機(jī)中的存儲(chǔ)關(guān)系氛雪，即數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)檐薯；

（3）對各種數(shù)據(jù)結(jié)構(gòu)進(jìn)行的運(yùn)算。

數(shù)據(jù)結(jié)構(gòu)是指相互有關(guān)聯(lián)的數(shù)據(jù)元素的集合注暗。

數(shù)據(jù)的邏輯結(jié)構(gòu)包含：

（1）表示數(shù)據(jù)元素的信息；

（2）表示各數(shù)據(jù)元素之間的前后件關(guān)系墓猎。

數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)有順序捆昏、鏈接、索引等毙沾。

線性結(jié)構(gòu)條件：

（1）有且只有一個(gè)根結(jié)點(diǎn)骗卜；

（2）每一個(gè)結(jié)點(diǎn)最多有一個(gè)前件，也最多有一個(gè)后件左胞。

非線性結(jié)構(gòu)：不滿足線性結(jié)構(gòu)條件的數(shù)據(jù)結(jié)構(gòu)寇仓。

3、線性表及其順序存儲(chǔ)結(jié)構(gòu)

? ? ? ?線性表由一組數(shù)據(jù)元素構(gòu)成烤宙，數(shù)據(jù)元素的位置只取決于自己的序號遍烦，元素之間的相對位置是線性的。

? ? ? ?在復(fù)雜線性表中躺枕，由若干項(xiàng)數(shù)據(jù)元素組成的數(shù)據(jù)元素稱為記錄服猪，而由多個(gè)記錄構(gòu)成的線性表又稱為文件。

非空線性表的結(jié)構(gòu)特征：

（1）且只有一個(gè)根結(jié)點(diǎn)a1拐云，它無前件罢猪；

（2）有且只有一個(gè)終端結(jié)點(diǎn)an，它無后件叉瘩；

（3）除根結(jié)點(diǎn)與終端結(jié)點(diǎn)外膳帕，其他所有結(jié)點(diǎn)有且只有一個(gè)前件，也有且只有一個(gè)后件薇缅。結(jié)點(diǎn)個(gè)數(shù)n稱為線性表的長度危彩，當(dāng)n=0時(shí)，稱為空表泳桦。

線性表的順序存儲(chǔ)結(jié)構(gòu)具有以下兩個(gè)基本特點(diǎn)：

（1）線性表中所有元素的所占的存儲(chǔ)空間是連續(xù)的恬砂；

（2）線性表中各數(shù)據(jù)元素在存儲(chǔ)空間中是按邏輯順序依次存放的。

ai的存儲(chǔ)地址為：adr(ai)=adr(a1)+(i-1)k,蓬痒，adr(a1)為第一個(gè)元素的地址泻骤，k代表每個(gè)元素占的字節(jié)數(shù)漆羔。

順序表的運(yùn)算：插入、刪除狱掂。

4演痒、棧和隊(duì)列

棧是限定在一端進(jìn)行插入與刪除的線性表，允許插入與刪除的一端稱為棧頂趋惨，不允許插入與刪除的另一端稱為棧底鸟顺。

棧按照“先進(jìn)后出”（filo）或“后進(jìn)先出”（lifo）組織數(shù)據(jù)，棧具有記憶作用器虾。用top表示棧頂位置讯嫂，用bottom表示棧底。

棧的基本運(yùn)算：（1）插入元素稱為入棧運(yùn)算兆沙；（2）刪除元素稱為退棧運(yùn)算欧芽；（3）讀棧頂元素是將棧頂元素賦給一個(gè)指定的變量，此時(shí)指針無變化葛圃。

隊(duì)列是指允許在一端（隊(duì)尾）進(jìn)入插入千扔，而在另一端（隊(duì)頭）進(jìn)行刪除的線性表。rear指針指向隊(duì)尾库正，front指針指向隊(duì)頭曲楚。

隊(duì)列是“先進(jìn)行出”（fifo）或“后進(jìn)后出”（lilo）的線性表。

隊(duì)列運(yùn)算包括（1）入隊(duì)運(yùn)算：從隊(duì)尾插入一個(gè)元素褥符；（2）退隊(duì)運(yùn)算：從隊(duì)頭刪除一個(gè)元素龙誊。

循環(huán)隊(duì)列：s=0表示隊(duì)列空，s=1且front=rear表示隊(duì)列滿

5喷楣、線性鏈表

數(shù)據(jù)結(jié)構(gòu)中的每一個(gè)結(jié)點(diǎn)對應(yīng)于一個(gè)存儲(chǔ)單元载迄，這種存儲(chǔ)單元稱為存儲(chǔ)結(jié)點(diǎn)，簡稱結(jié)點(diǎn)抡蛙。

結(jié)點(diǎn)由兩部分組成：（1）用于存儲(chǔ)數(shù)據(jù)元素值护昧，稱為數(shù)據(jù)域；（2）用于存放指針粗截，稱為指針域惋耙，用于指向前一個(gè)或后一個(gè)結(jié)點(diǎn)。在鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)中熊昌，存儲(chǔ)數(shù)據(jù)結(jié)構(gòu)的存儲(chǔ)空間可以不連續(xù)绽榛，各數(shù)據(jù)結(jié)點(diǎn)的存儲(chǔ)順序與數(shù)據(jù)元素之間的邏輯關(guān)系可以不一致，而數(shù)據(jù)元素之間的邏輯關(guān)系是由指針域來確定的婿屹。

鏈?zhǔn)酱鎯?chǔ)方式即可用于表示線性結(jié)構(gòu)灭美，也可用于表示非線性結(jié)構(gòu)。

線性鏈表昂利，head稱為頭指針届腐，head=null（或0）稱為空表铁坎，如果是兩指針：左指針（llink）指向前件結(jié)點(diǎn)，右指針（rlink）指向后件結(jié)點(diǎn)犁苏。

線性鏈表的基本運(yùn)算：查找硬萍、插入、刪除围详。

6朴乖、樹與二叉樹

? ? ? ?樹是一種簡單的非線性結(jié)構(gòu)，所有元素之間具有明顯的層次特性助赞。

? ? ? ?在樹結(jié)構(gòu)中买羞，每一個(gè)結(jié)點(diǎn)只有一個(gè)前件，稱為父結(jié)點(diǎn)雹食，沒有前件的結(jié)點(diǎn)只有一個(gè)畜普，稱為樹的根結(jié)點(diǎn)，簡稱樹的根婉徘。每一個(gè)結(jié)點(diǎn)可以有多個(gè)后件，稱為該結(jié)點(diǎn)的子結(jié)點(diǎn)咐汞。沒有后件的結(jié)點(diǎn)稱為葉子結(jié)點(diǎn)盖呼。

? ? ? ?在樹結(jié)構(gòu)中，一個(gè)結(jié)點(diǎn)所擁有的后件的個(gè)數(shù)稱為該結(jié)點(diǎn)的度化撕，所有結(jié)點(diǎn)中最大的度稱為樹的度几晤。樹的最大層次稱為樹的深度。

二叉樹的特點(diǎn)：（1）非空二叉樹只有一個(gè)根結(jié)點(diǎn)植阴；（2）每一個(gè)結(jié)點(diǎn)最多有兩棵子樹蟹瘾，且分別稱為該結(jié)點(diǎn)的左子樹與右子樹。

二叉樹的基本性質(zhì)：

（1）在二叉樹的第k層上掠手，最多有2k-1(k≥1)個(gè)結(jié)點(diǎn)憾朴；

（2）深度為m的二叉樹最多有2m-1個(gè)結(jié)點(diǎn)；

（3）度為0的結(jié)點(diǎn)（即葉子結(jié)點(diǎn)）總是比度為2的結(jié)點(diǎn)多一個(gè)喷鸽；

（4）具有n個(gè)結(jié)點(diǎn)的二叉樹众雷，其深度至少為[log2n]+1,其中[log2n]表示取log2n的整數(shù)部分；

（5）具有n個(gè)結(jié)點(diǎn)的完全二叉樹的深度為[log2n]+1做祝；

（6）設(shè)完全二叉樹共有n個(gè)結(jié)點(diǎn)砾省。如果從根結(jié)點(diǎn)開始，按層序（每一層從左到右）用自然數(shù)1混槐，2编兄，….n給結(jié)點(diǎn)進(jìn)行編號（k=1,2….n），有以下結(jié)論：

①若k=1声登，則該結(jié)點(diǎn)為根結(jié)點(diǎn)狠鸳，它沒有父結(jié)點(diǎn)揣苏；若k>1，則該結(jié)點(diǎn)的父結(jié)點(diǎn)編號為int(k/2)碰煌；

②若2k≤n舒岸，則編號為k的結(jié)點(diǎn)的左子結(jié)點(diǎn)編號為2k；否則該結(jié)點(diǎn)無左子結(jié)點(diǎn)（也無右子結(jié)點(diǎn)）芦圾；

③若2k+1≤n蛾派，則編號為k的結(jié)點(diǎn)的右子結(jié)點(diǎn)編號為2k+1；否則該結(jié)點(diǎn)無右子結(jié)點(diǎn)个少。

滿二叉樹是指除最后一層外洪乍，每一層上的所有結(jié)點(diǎn)有兩個(gè)子結(jié)點(diǎn)，則k層上有2k-1個(gè)結(jié)點(diǎn)深度為m的滿二叉樹有2m-1個(gè)結(jié)點(diǎn)夜焦。

完全二叉樹是指除最后一層外壳澳，每一層上的結(jié)點(diǎn)數(shù)均達(dá)到最大值，在最后一層上只缺少右邊的若干結(jié)點(diǎn)茫经。

二叉樹存儲(chǔ)結(jié)構(gòu)采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)巷波，對于滿二叉樹與完全二叉樹可以按層序進(jìn)行順序存儲(chǔ)。

二叉樹的遍歷：

（1）前序遍歷（dlr）卸伞，首先訪問根結(jié)點(diǎn)抹镊，然后遍歷左子樹，最后遍歷右子樹荤傲；

（2）中序遍歷（ldr）垮耳，首先遍歷左子樹，然后訪問根結(jié)點(diǎn)遂黍，最后遍歷右子樹终佛；

（3）后序遍歷（lrd）首先遍歷左子樹，然后訪問遍歷右子樹雾家，最后訪問根結(jié)點(diǎn)铃彰。

7、查找技術(shù)

順序查找的使用情況：

（1）線性表為無序表芯咧；

（2）表采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)豌研。

二分法查找只適用于順序存儲(chǔ)的有序表，對于長度為n的有序線性表唬党，最壞情況只需比較log2n次鹃共。

8、排序技術(shù)

排序是指將一個(gè)無序序列整理成按值非遞減順序排列的有序序列驶拱。

交換類排序法：（1）冒泡排序法霜浴，需要比較的次數(shù)為n(n-1)/2； （2）快速排序法蓝纲。

插入類排序法：（1）簡單插入排序法阴孟，最壞情況需要n(n-1)/2次比較晌纫；（2）希爾排序法，最壞情況需要o(n1.5)次比較永丝。

選擇類排序法：（1）簡單選擇排序法,

最壞情況需要n(n-1)/2次比較锹漱；（2）堆排序法，最壞情況需要o(nlog2n)次比較慕嚷。

學(xué)計(jì)算機(jī)不易哥牍，此路應(yīng)攜手前行。

如果你也想學(xué)計(jì)算機(jī)編程的話喝检！

可以來我專欄推薦的C/C++編程學(xué)習(xí)基地嗅辣，【點(diǎn)擊進(jìn)入】！

還有免費(fèi)（零基礎(chǔ)教程挠说，項(xiàng)目實(shí)戰(zhàn)教學(xué)視頻）澡谭！? ?

涉及：游戲開發(fā)、課程設(shè)計(jì)损俭、常用軟件開發(fā)蛙奖、編程基礎(chǔ)知識、黑客等等...

和志同道合的小伙伴們一起學(xué)編程吧杆兵！