本文關(guān)鍵詞：數(shù)據(jù)結(jié)構(gòu)，由筆耕文化傳播整理發(fā)布。

一步一步寫算法（之 算法總結(jié)）

【 聲明：版權(quán)所有，歡迎轉(zhuǎn)載，請(qǐng)勿用于商業(yè)用途。  聯(lián)系信箱：feixiaoxing @163.com】     自10月初編寫算法系列的博客以來(lái)，陸陸續(xù)續(xù)以來(lái)寫了幾十篇。按照計(jì)劃，還有三個(gè)部分的內(nèi)容沒(méi)有介紹，主要是（Dijkstra算法、二叉平衡樹、紅黑樹）。這部分會(huì)在后面的博客補(bǔ)充完整。這里主要是做一個(gè)總結(jié)，有興趣的朋友可以好好看看，歡迎大家提出寶貴意見(jiàn)。     （1）...

一步一步寫算法（之 最大公約數(shù)、最小公倍數(shù)）

【 聲明：版權(quán)所有，歡迎轉(zhuǎn)載，請(qǐng)勿用于商業(yè)用途。  聯(lián)系信箱：feixiaoxing @163.com】     求解最小公倍數(shù)和最大公約數(shù)是我們開始編程的時(shí)候經(jīng)常需要練習(xí)的題目。從題面上看，好像我們需要求解的是兩個(gè)題目，但其實(shí)就是一個(gè)題目。那就是求最大公約數(shù)？為什么呢？我們可以假想這兩個(gè)數(shù)m和n，假設(shè)m和n的最大公約數(shù)是a。那么我們可以這樣寫：     m = b *a；...

一步一步寫算法（之 可變參數(shù)）

【 聲明：版權(quán)所有，歡迎轉(zhuǎn)載，請(qǐng)勿用于商業(yè)用途。  聯(lián)系信箱：feixiaoxing @163.com】     可變參數(shù)是C語(yǔ)言編程的一個(gè)特色。在我們一般編程中，函數(shù)的參數(shù)個(gè)數(shù)都是確定的，事先定下來(lái)的。然而就有那么一部分函數(shù)，它的個(gè)數(shù)是不確定的，長(zhǎng)度也不一定，這中間有什么秘密嗎？     其實(shí)，我們可以回憶一下哪些函數(shù)是可變參數(shù)的函數(shù)？其實(shí)也就是sprintf、printf這樣的函數(shù)...

一步一步寫算法（之 A*算法）

【 聲明：版權(quán)所有，歡迎轉(zhuǎn)載，請(qǐng)勿用于商業(yè)用途。  聯(lián)系信箱：feixiaoxing @163.com】     在前面的博客當(dāng)中，其實(shí)我們已經(jīng)討論過(guò)尋路的算法。不過(guò)，當(dāng)時(shí)的示例圖中，可選的路徑是唯一的。我們挑選一個(gè)算法，就是說(shuō)要把這個(gè)唯一的路徑選出來(lái)，怎么選呢？當(dāng)時(shí)我們就是采用窮盡遞歸的算法。然而，今天的情形有點(diǎn)不太一樣了。在什么地方呢？那就是今天的路徑有n條，這條路徑都可以達(dá)到目的地...

一步一步寫算法（之克魯斯卡爾算法 下）

【 聲明：版權(quán)所有，歡迎轉(zhuǎn)載，請(qǐng)勿用于商業(yè)用途。  聯(lián)系信箱：feixiaoxing @163.com】     前面在討論克魯斯卡爾的算法的時(shí)候，我們分析了算法的基本過(guò)程、基本數(shù)據(jù)結(jié)構(gòu)和算法中需要解決的三個(gè)問(wèn)題（排序、判斷、合并）。今天，我們繼續(xù)完成剩下部分的內(nèi)容。合并函數(shù)中，我們調(diào)用了兩個(gè)基本函數(shù)，find_tree_by_index和delete_mini_tree_from_gr...

一步一步寫算法（之克魯斯卡爾算法 中）

【 聲明：版權(quán)所有，歡迎轉(zhuǎn)載，請(qǐng)勿用于商業(yè)用途。  聯(lián)系信箱：feixiaoxing @163.com】     前面說(shuō)到，克魯斯卡爾的算法是按照各個(gè)line的權(quán)重依次進(jìn)行添加的，那么這就涉及到一個(gè)權(quán)重的排序問(wèn)題。怎么排序呢？可以采用最簡(jiǎn)單的冒泡排序算法�？墒沁@里排序的是數(shù)據(jù)結(jié)構(gòu)，怎么辦呢？那就只好采用通用排序算法了。 void bubble_sort(void* array[],...

一步一步寫算法（之克魯斯卡爾算法 上）

【 聲明：版權(quán)所有，歡迎轉(zhuǎn)載，請(qǐng)勿用于商業(yè)用途。  聯(lián)系信箱：feixiaoxing @163.com】     克魯斯卡爾算法是計(jì)算最小生成樹的一種算法。和prim算法（上，中，下）按照節(jié)點(diǎn)進(jìn)行查找的方法不一樣，克魯斯卡爾算法是按照具體的線段進(jìn)行的�，F(xiàn)在我們假設(shè)一個(gè)圖有m個(gè)節(jié)點(diǎn)，n條邊。首先，我們需要把m個(gè)節(jié)點(diǎn)看成m個(gè)獨(dú)立的生成樹，并且把n條邊按照從小到大的數(shù)據(jù)進(jìn)行排列。在n條邊中，我...

一步一步寫算法（之 回?cái)?shù)）

【 聲明：版權(quán)所有，歡迎轉(zhuǎn)載，請(qǐng)勿用于商業(yè)用途。  聯(lián)系信箱：feixiaoxing @163.com】     回?cái)?shù)的概念比較好玩，就是說(shuō)有這么一個(gè)字符串str， 長(zhǎng)度為n， 現(xiàn)在index開始從0->index/2遍歷，那么str[index] = str[n-1-index]，那么這種數(shù)據(jù)就是我們通常說(shuō)的回?cái)?shù)。比如說(shuō)a = “a”是回?cái)?shù)， a = “aba”是回?cái)?shù)， a = "st...

一步一步寫算法（之哈夫曼樹 下）

【 聲明：版權(quán)所有，歡迎轉(zhuǎn)載，請(qǐng)勿用于商業(yè)用途。  聯(lián)系信箱：feixiaoxing @163.com】     前面說(shuō)到了哈夫曼樹的創(chuàng)建，那下面一個(gè)重要的環(huán)節(jié)就是哈夫曼樹的排序問(wèn)題。但是由于排序的內(nèi)容是數(shù)據(jù)結(jié)構(gòu)，因此形式上說(shuō)，我們需要采用通用數(shù)據(jù)排序算法，這在我之前的博客里面已經(jīng)涉及到了（通用算法設(shè)計(jì)）。所以，我們所要做的就是編寫compare和swap兩個(gè)函數(shù)。通用冒泡代碼如下所示，...

一步一步寫算法（之哈夫曼樹 上）

【 聲明：版權(quán)所有，歡迎轉(zhuǎn)載，請(qǐng)勿用于商業(yè)用途。  聯(lián)系信箱：feixiaoxing @163.com】       在數(shù)據(jù)傳輸?shù)倪^(guò)程當(dāng)中，我們總是希望用盡可能少的帶寬傳輸更多的數(shù)據(jù)，哈夫曼就是其中的一種較少帶寬傳輸?shù)姆椒�。哈夫曼的基本思想不�?fù)雜，那就是對(duì)于出現(xiàn)頻率高的數(shù)據(jù)用短字節(jié)表示，對(duì)于頻率比較低得數(shù)據(jù)用長(zhǎng)字節(jié)表示。     比如說(shuō)，現(xiàn)在有4個(gè)數(shù)據(jù)需要傳輸，分別為A、B、C、D，所...

一步一步寫算法（之通用數(shù)據(jù)結(jié)構(gòu)）

【 聲明：版權(quán)所有，歡迎轉(zhuǎn)載，請(qǐng)勿用于商業(yè)用途。  聯(lián)系信箱：feixiaoxing @163.com】     上一篇博客介紹了通用算法，那么有了這個(gè)基礎(chǔ)我們可以繼續(xù)分析通用數(shù)據(jù)結(jié)構(gòu)了。我們知道在c++里面，既有數(shù)據(jù)又有函數(shù)，所以一個(gè)class就能干很多事情。舉一個(gè)簡(jiǎn)單的例子來(lái)說(shuō)，我們可以編寫一個(gè)數(shù)據(jù)的class計(jì)算類。 class calculate{ int m; int...

一步一步寫算法（之通用算法的編寫）

【 聲明：版權(quán)所有，歡迎轉(zhuǎn)載，請(qǐng)勿用于商業(yè)用途。  聯(lián)系信箱：feixiaoxing @163.com】     前面我們寫過(guò)各種各樣的算法，什么排序、查找、二叉樹、隊(duì)列、堆棧等等。但是我們?cè)诰帉戇@些代碼的時(shí)候卻都有一個(gè)缺點(diǎn)，不知道大家發(fā)現(xiàn)了沒(méi)有？那就是這些算法中使用的數(shù)據(jù)結(jié)構(gòu)都是簡(jiǎn)單的int數(shù)據(jù)。所以，如果排序的是int，那么用起來(lái)沒(méi)有什么問(wèn)題。關(guān)鍵就是萬(wàn)一是其他的數(shù)據(jù)類型，那我們應(yīng)該...

一步一步寫算法（之鏈表重合）

【 聲明：版權(quán)所有，歡迎轉(zhuǎn)載，請(qǐng)勿用于商業(yè)用途。  聯(lián)系信箱：feixiaoxing @163.com】     鏈表重合是一個(gè)好玩的問(wèn)題。原題目是這樣的：有兩個(gè)鏈表，那么如何判斷這兩個(gè)鏈表是不是重合的？至于這個(gè)鏈表在什么時(shí)候重合的，這不重要，關(guān)鍵是判斷這個(gè)鏈表究竟有沒(méi)有重合。究竟有什么方法呢？     最簡(jiǎn)單的方法就是查看兩者有沒(méi)有共同點(diǎn)。那么依次判斷就行了。 int find...

一步一步寫算法（之尋找丟失的數(shù)）

【 聲明：版權(quán)所有，歡迎轉(zhuǎn)載，請(qǐng)勿用于商業(yè)用途。  聯(lián)系信箱：feixiaoxing @163.com】     假設(shè)我們有一個(gè)1億個(gè)數(shù)據(jù)，其中數(shù)據(jù)的范圍是0~1億，也就是100M的數(shù)據(jù)。但是這個(gè)數(shù)組中丟了一些數(shù)據(jù)，比如說(shuō)少了5啊，少了10啊，那么有什么辦法可以把這些丟失的數(shù)據(jù)找回來(lái)呢？這個(gè)題目不難，但是它可以幫助我們拓展思路，不斷提高算法的運(yùn)行效率。     對(duì)于這個(gè)問(wèn)題，我們一個(gè)最...

一步一步寫算法（之prim算法 下）

【 聲明：版權(quán)所有，歡迎轉(zhuǎn)載，請(qǐng)勿用于商業(yè)用途。  聯(lián)系信箱：feixiaoxing @163.com】     前兩篇博客我們討論了prim最小生成樹的算法，熟悉了基本的流程。基本上來(lái)說(shuō)，我們是按照自上而下的順序來(lái)編寫代碼的。首先我們搭建一個(gè)架構(gòu)，然后一步一步完成其中的每一個(gè)子功能，這樣最后構(gòu)成一個(gè)完成prim算法計(jì)算過(guò)程。     f）將DIR_LINE隊(duì)列中不符合的數(shù)據(jù)刪...

一步一步寫算法（之prim算法 中）

【 聲明：版權(quán)所有，歡迎轉(zhuǎn)載，請(qǐng)勿用于商業(yè)用途。  聯(lián)系信箱：feixiaoxing @163.com】     C）編寫最小生成樹，涉及創(chuàng)建、挑選和添加過(guò)程 MINI_GENERATE_TREE* get_mini_tree_from_graph(GRAPH* pGraph) { MINI_GENERATE_TREE* pMiniTree; DIR_LINE pDirLine...

一步一步寫算法（之prim算法 上）

【 聲明：版權(quán)所有，歡迎轉(zhuǎn)載，請(qǐng)勿用于商業(yè)用途。  聯(lián)系信箱：feixiaoxing @163.com】     前面我們討論了圖的創(chuàng)建、添加、刪除和保存等問(wèn)題。今天我們將繼續(xù)討論圖的一些其他問(wèn)題，比如說(shuō)如何在圖的環(huán)境下構(gòu)建最小生成樹。為什么要構(gòu)建最小生成樹呢？其實(shí)原理很簡(jiǎn)單。打個(gè)比方，現(xiàn)在某一個(gè)鄉(xiāng)鎮(zhèn)有n個(gè)村，那么這n個(gè)村肯定是聯(lián)通的。現(xiàn)在我們打算在各個(gè)村之間搭建網(wǎng)線，實(shí)現(xiàn)村村通的工程。...

一步一步寫算法（之函數(shù)堆棧顯示）

【 聲明：版權(quán)所有，歡迎轉(zhuǎn)載，請(qǐng)勿用于商業(yè)用途。  聯(lián)系信箱：feixiaoxing @163.com 】     在繼續(xù)圖的討論之前，我們今天開個(gè)小差，討論一下函數(shù)堆棧的基本原理。有過(guò)編程經(jīng)驗(yàn)的朋友都知道，堆棧調(diào)試是我們?cè)诔绦蜷_發(fā)中經(jīng)常應(yīng)用的一個(gè)功能。那么大家有沒(méi)有想過(guò)，函數(shù)堆棧是怎么開始的啊？其實(shí)我們可以自己寫一個(gè)函數(shù)堆棧輸出函數(shù)分析一下。     因?yàn)橐话銇?lái)說(shuō)，函數(shù)的壓棧過(guò)程是這...

一步一步寫算法（之圖的保存）

【 聲明：版權(quán)所有，歡迎轉(zhuǎn)載，請(qǐng)勿用于商業(yè)用途。  聯(lián)系信箱：feixiaoxing @163.com】     前面的幾篇博客，我們對(duì)圖進(jìn)行基本定義，同時(shí)介紹了圖的創(chuàng)建、圖的添加和刪除等。今天，我們聊一聊圖是怎么在存儲(chǔ)在外設(shè)中的。這些外接設(shè)備可以是各種類型的，比如說(shuō)，可以是硬盤、sd卡、網(wǎng)絡(luò)硬盤等等。本質(zhì)上說(shuō)，我們今天討論的主題就是怎么把圖的數(shù)據(jù)永久地保留在本地。并且，如果需要加載這些...

一步一步寫算法（之圖添加和刪除）

【 聲明：版權(quán)所有，歡迎轉(zhuǎn)載，請(qǐng)勿用于商業(yè)用途。  聯(lián)系信箱：feixiaoxing @163.com】     前面我們談到的圖的數(shù)據(jù)結(jié)構(gòu)、圖的創(chuàng)建，今天我們就來(lái)說(shuō)一說(shuō)如何在圖中添加和刪除邊。邊的添加和刪除并不復(fù)雜，但是關(guān)鍵有一點(diǎn)需要記住，那就是一定要在小函數(shù)的基礎(chǔ)之上構(gòu)建大函數(shù)，否則很容易出現(xiàn)錯(cuò)誤。     一、邊的創(chuàng)建     邊的創(chuàng)建一般來(lái)說(shuō)可以分為下面以下幾個(gè)步驟：...

一步一步寫算法（之圖創(chuàng)建）

【 聲明：版權(quán)所有，歡迎轉(zhuǎn)載，請(qǐng)勿用于商業(yè)用途。  聯(lián)系信箱：feixiaoxing @163.com】     前面我們討論過(guò)圖的基本結(jié)構(gòu)是什么樣的。它可以是矩陣類型的、數(shù)組類型的，當(dāng)然也可以使指針類型的。當(dāng)然，就我個(gè)人而言，比較習(xí)慣使用的結(jié)構(gòu)還是鏈表指針類型的。本質(zhì)上，一幅圖就是由很多節(jié)點(diǎn)構(gòu)成的，每一個(gè)節(jié)點(diǎn)上面有很多的分支，僅此而已。為此，我們又對(duì)原來(lái)的結(jié)構(gòu)做了小的改變： ty...

一步一步寫算法（之圖結(jié)構(gòu)）

【 聲明：版權(quán)所有，歡迎轉(zhuǎn)載，請(qǐng)勿用于商業(yè)用途。  聯(lián)系信箱：feixiaoxing @163.com】      圖是數(shù)據(jù)結(jié)構(gòu)里面的重要一章。通過(guò)圖，我們可以判斷兩個(gè)點(diǎn)之間是不是具有連通性；通過(guò)圖，我們還可以計(jì)算兩個(gè)點(diǎn)之間的最小距離是多少；通過(guò)圖，我們還可以根據(jù)不同的要求，尋找不同的合適路徑。當(dāng)然，有的時(shí)候?yàn)榱擞?jì)算的需要，我們還需要從圖中抽象出最小生成樹，這樣在遍歷計(jì)算的時(shí)候就不需要持...

一步一步寫算法（之“數(shù)星星”）

【 聲明：版權(quán)所有，歡迎轉(zhuǎn)載，請(qǐng)勿用于商業(yè)用途。  聯(lián)系信箱：feixiaoxing @163.com】       學(xué)過(guò)編程的朋友都知道，當(dāng)初為了學(xué)習(xí)編程語(yǔ)言中的各種語(yǔ)法結(jié)構(gòu)，我們要試著解決各種各樣奇怪的題目。其中“數(shù)星星”就似乎其中的一種。什么是“數(shù)星星”呢？就是打印各種形狀的“*”，正三角、倒三角、菱形等等。本篇博客純粹為了紀(jì)念我們逝去的歲月。     a）正三角 void st...

一步一步寫算法（之字符串查找 下篇）

【 聲明：版權(quán)所有，歡迎轉(zhuǎn)載，請(qǐng)勿用于商業(yè)用途。  聯(lián)系信箱：feixiaoxing @163.com】     前面我們談到了KMP算法，但是講的還不是很詳細(xì)。今天我們可以把這個(gè)問(wèn)題講的稍微詳細(xì)一點(diǎn)。假設(shè)在字符串A中尋找字符串B，其中字符串B的長(zhǎng)度為n，字符串A的長(zhǎng)度遠(yuǎn)大于n，在此我們先忽略。     假設(shè)現(xiàn)在開始在字符串A中查找，并且假設(shè)雙方在第p個(gè)字符的時(shí)候發(fā)現(xiàn)查找出錯(cuò)了，也就是...

一步一步寫算法（之字符串查找 中篇）

【 聲明：版權(quán)所有，歡迎轉(zhuǎn)載，請(qǐng)勿用于商業(yè)用途。  聯(lián)系信箱：feixiaoxing @163.com】     昨天我們編寫了簡(jiǎn)單的字符查找函數(shù)。雖然比較簡(jiǎn)單，但是也算能用。然而，經(jīng)過(guò)我們仔細(xì)分析研究一下，這么一個(gè)簡(jiǎn)單的函數(shù)還是有改進(jìn)的空間的。在什么地方改進(jìn)呢？大家可以慢慢往下看。     下面的代碼是優(yōu)化前的代碼，現(xiàn)在再貼一次，這樣分析起來(lái)也方便些： char* strstr...

一步一步寫算法（之字符串查找 上篇）

【 聲明：版權(quán)所有，歡迎轉(zhuǎn)載，請(qǐng)勿用于商業(yè)用途。  聯(lián)系信箱：feixiaoxing @163.com】     字符串運(yùn)算是我們開發(fā)軟件的基本功，其中比較常用的功能有字符串長(zhǎng)度的求解、字符串的比較、字符串的拷貝、字符串的upper等等。另外一個(gè)經(jīng)常使用但是卻被我們忽視的功能就是字符串的查找。word里面有字符串查找、notepad里面有字符串查找、winxp里面也有系統(tǒng)自帶的字符串的查...

一步一步寫算法（之鏈表排序）

【 聲明：版權(quán)所有，歡迎轉(zhuǎn)載，請(qǐng)勿用于商業(yè)用途。  聯(lián)系信箱：feixiaoxing @163.com】     相比較線性表的排序而言，鏈表排序的內(nèi)容稍微麻煩一點(diǎn)。一方面，你要考慮數(shù)據(jù)插入的步驟；另外一方面你也要對(duì)指針有所顧慮。要是有一步的內(nèi)容錯(cuò)了，那么操作系統(tǒng)會(huì)馬上給你彈出一個(gè)exception。就鏈表的特殊性而言，適合于鏈表的排序有哪些呢？     （1）插入排序    （適合）...

一步一步寫算法（之哈希二叉樹）

【 聲明：版權(quán)所有，歡迎轉(zhuǎn)載，請(qǐng)勿用于商業(yè)用途。  聯(lián)系信箱：feixiaoxing @163.com】     用過(guò)平衡二叉樹的朋友都清楚，平衡二叉樹的最大優(yōu)點(diǎn)就是排序。不管是在數(shù)據(jù)插入的時(shí)候還是在數(shù)據(jù)刪除的時(shí)候，我們都要考慮到數(shù)據(jù)的排序情況。但是和數(shù)據(jù)的添加、刪除一樣重要的，還有數(shù)據(jù)的查詢。很不幸，平衡二叉樹經(jīng)常由于節(jié)點(diǎn)的添加和刪除，數(shù)據(jù)的查詢效率會(huì)變得非常低下。朋友們可以看看下面這...

一步一步寫算法（之二叉樹深度遍歷）

【 聲明：版權(quán)所有，歡迎轉(zhuǎn)載，請(qǐng)勿用于商業(yè)用途。  聯(lián)系信箱：feixiaoxing @163.com】    深度遍歷是軟件開發(fā)中經(jīng)常遇到的遍歷方法。常用的遍歷方法主要有下面三種：（1）前序遍歷；（2）中序遍歷；（3）后序遍歷。按照遞歸的方法，這三種遍歷的方法其實(shí)都不困難，前序遍歷就是根-左-右，中序遍歷就是左-根-右，后續(xù)遍歷就是左-右-根。代碼實(shí)現(xiàn)起來(lái)也不復(fù)雜。    1）前序遍歷void...

一步一步寫算法（之二叉樹廣度遍歷）

【 聲明：版權(quán)所有，歡迎轉(zhuǎn)載，請(qǐng)勿用于商業(yè)用途。  聯(lián)系信箱：feixiaoxing @163.com】     在二叉樹的遍歷當(dāng)中，有一種遍歷方法是不常見(jiàn)的，那就是廣度遍歷。和其他三種遍歷方法不同，二叉樹的廣度遍歷需要額外的數(shù)據(jù)結(jié)構(gòu)來(lái)幫助一下？什么數(shù)據(jù)結(jié)構(gòu)呢？那就是隊(duì)列。因?yàn)殛?duì)列具有先進(jìn)先出的特點(diǎn)，這個(gè)特點(diǎn)要求我們?cè)诒闅v新的一層數(shù)據(jù)之前，必須對(duì)上一次的數(shù)據(jù)全部遍歷結(jié)束。暫時(shí)還沒(méi)有掌握隊(duì)...

一步一步寫算法（之尋路）

【 聲明：版權(quán)所有，歡迎轉(zhuǎn)載，請(qǐng)勿用于商業(yè)用途。  聯(lián)系信箱：feixiaoxing @163.com】     尋路是游戲設(shè)計(jì)中需要使用到一種功能，那么我們?cè)趺礃右砸粋�(gè)點(diǎn)作為起始點(diǎn)，快速地尋找到目標(biāo)點(diǎn)呢？其實(shí)尋路的方法不難。一種簡(jiǎn)單有效的方法就是回溯法。如果我們從一個(gè)點(diǎn)出發(fā)，那么這個(gè)點(diǎn)周圍肯定有若干條路，只要有一條路存在，我們就一直走下去，直到發(fā)現(xiàn)沒(méi)有路走為止；要是發(fā)現(xiàn)路走不下去了怎么...

一步一步寫算法（之排序二叉樹的保存和加載）

【 聲明：版權(quán)所有，歡迎轉(zhuǎn)載，請(qǐng)勿用于商業(yè)用途。  聯(lián)系信箱：feixiaoxing @163.com】     排序二叉樹是我們開發(fā)中經(jīng)常使用到的一種數(shù)據(jù)結(jié)構(gòu)，它具有較好的插入、刪除、查找特性。但是由于二叉樹的指針較多，所以相比較其他的數(shù)據(jù)結(jié)構(gòu)而言，二叉樹來(lái)得比較麻煩些。但是也不是沒(méi)有辦法，下面介紹一下我個(gè)人常用的方法。     我們知道，如果一個(gè)二叉樹是一個(gè)滿樹的話，那么二叉樹的節(jié)...

一步一步寫算法（之排序二叉樹線索化）

【 聲明：版權(quán)所有，歡迎轉(zhuǎn)載，請(qǐng)勿用于商業(yè)用途。  聯(lián)系信箱：feixiaoxing @163.com】     前面我們談到了排序二叉樹，還沒(méi)有熟悉的同學(xué)可以看一下這個(gè)，二叉樹基本操作、二叉樹插入、二叉樹刪除1、刪除2、刪除3。但是排序二叉樹也不是沒(méi)有缺點(diǎn)，比如說(shuō)，如果我們想在排序二叉樹中刪除一段數(shù)據(jù)的節(jié)點(diǎn)怎么辦呢？按照現(xiàn)在的結(jié)構(gòu)，我們只能一個(gè)一個(gè)數(shù)據(jù)查找驗(yàn)證，首先看看在不在排序二叉樹...

一步一步寫算法（之hash表）

【 聲明：版權(quán)所有，歡迎轉(zhuǎn)載，請(qǐng)勿用于商業(yè)用途。  聯(lián)系信箱：feixiaoxing @163.com】     hash表，有時(shí)候也被稱為散列表。個(gè)人認(rèn)為，hash表是介于鏈表和二叉樹之間的一種中間結(jié)構(gòu)。鏈表使用十分方便，但是數(shù)據(jù)查找十分麻煩；二叉樹中的數(shù)據(jù)嚴(yán)格有序，...

一步一步寫算法（之挑選最大的n個(gè)數(shù)）

【 聲明：版權(quán)所有，歡迎轉(zhuǎn)載，請(qǐng)勿用于商業(yè)用途。  聯(lián)系信箱：feixiaoxing @163.com】    從一堆數(shù)據(jù)中挑選n個(gè)最大的數(shù)，這個(gè)問(wèn)題是網(wǎng)上流傳的比較廣的幾個(gè)問(wèn)題之一。具體來(lái)說(shuō)，它的意思就是：假設(shè)我們有100個(gè)數(shù)據(jù)，我們需要挑選出最大的n個(gè)數(shù)據(jù)(n     在前面的博客當(dāng)中，我們實(shí)現(xiàn)的排序算法有下面幾種：    （1） 冒泡排序、插入排序、希爾排序    （2） 快速排序    （...

一步一步寫算法（之八皇后）

【 聲明：版權(quán)所有，歡迎轉(zhuǎn)載，請(qǐng)勿用于商業(yè)用途。  聯(lián)系信箱：feixiaoxing @163.com】    八皇后是一道很具典型性的題目。它的基本要求是這樣的：在一個(gè)8*8的矩陣上面放置8個(gè)物體，一個(gè)矩陣點(diǎn)只允許放置一個(gè)物體，任意兩個(gè)點(diǎn)不能在一行上，也不能在一列上，不能在一條左斜線上，當(dāng)然也不能在一條右斜線上。    初看到這道題目，大家的第一印象是遍歷，但是經(jīng)過(guò)實(shí)踐之后發(fā)現(xiàn)遍歷其實(shí)不好寫，而...

一步一步寫算法（之?dāng)?shù)據(jù)選擇）

【 聲明：版權(quán)所有，歡迎轉(zhuǎn)載，請(qǐng)勿用于商業(yè)用途。  聯(lián)系信箱：feixiaoxing @163.com】     在數(shù)學(xué)中，有一些數(shù)據(jù)選擇的內(nèi)容。舉個(gè)例子來(lái)說(shuō)，有這樣一組數(shù)據(jù)：1、2、3、4�，F(xiàn)在我們打算從中挑選出1個(gè)數(shù)據(jù)，那么有幾種選擇呢？結(jié)果應(yīng)該是1、2、3、4；那么如果挑...

一步一步寫算法（之基數(shù)排序）

【 聲明：版權(quán)所有，歡迎轉(zhuǎn)載，請(qǐng)勿用于商業(yè)用途。  聯(lián)系信箱：feixiaoxing @163.com】     基數(shù)排序是另外一種比較有特色的排序方式，它是怎么排序的呢？我們可以按照下面的一組數(shù)字做出說(shuō)明：12、 104、 13、 7、 9     （1）按個(gè)位...

一步一步寫算法（之選擇排序）

【 聲明：版權(quán)所有，歡迎轉(zhuǎn)載，請(qǐng)勿用于商業(yè)用途。  聯(lián)系信箱：feixiaoxing @163.com】     選擇排序是和冒泡排序差不多的一種排序。和冒泡排序交換相連數(shù)據(jù)不一樣的是，選擇排序只有在確定了最小的數(shù)據(jù)之后，才會(huì)發(fā)生交換。怎么交換呢？我們可以以下面一組數(shù)據(jù)...

一步一步寫算法（之單詞統(tǒng)計(jì)）

【 聲明：版權(quán)所有，歡迎轉(zhuǎn)載，請(qǐng)勿用于商業(yè)用途。  聯(lián)系信箱：feixiaoxing @163.com】     在面試環(huán)節(jié)中，有一道題目也是考官們中意的一道題目：如果統(tǒng)計(jì)一段由字符和和空格組成的字符串中有多少個(gè)單詞？     其實(shí)，之所以問(wèn)這個(gè)題目，考官的目的就是想...

一步一步寫算法（之爬樓梯）

【 聲明：版權(quán)所有，歡迎轉(zhuǎn)載，請(qǐng)勿用于商業(yè)用途。  聯(lián)系信箱：feixiaoxing @163.com】     前兩天上網(wǎng)的時(shí)候看到一個(gè)特別有意思的題目，在這里和朋友們分享一下：     有一個(gè)人準(zhǔn)備開始爬樓梯，假設(shè)樓梯有n個(gè)，這個(gè)人只允許一次爬一個(gè)樓梯或者一次爬兩...

一步一步寫算法（之排序二叉樹刪除-3）

【 聲明：版權(quán)所有，歡迎轉(zhuǎn)載，請(qǐng)勿用于商業(yè)用途。  聯(lián)系信箱：feixiaoxing @163.com】     3 普通節(jié)點(diǎn)的刪除     3.1 刪除的節(jié)點(diǎn)沒(méi)有左子樹，也沒(méi)有右子樹      測(cè)試用例1： 刪除節(jié)點(diǎn)6 /* * * 10 ======> 10 * / \...

一步一步寫算法（之排序二叉樹刪除-2）

【 聲明：版權(quán)所有，歡迎轉(zhuǎn)載，請(qǐng)勿用于商業(yè)用途。  聯(lián)系信箱：feixiaoxing @163.com】     2.4 刪除節(jié)點(diǎn)的左右子樹都存在，此時(shí)又會(huì)分成兩種情形     1）左節(jié)點(diǎn)是當(dāng)前左子樹的最大節(jié)點(diǎn)，此時(shí)只需要用左節(jié)點(diǎn)代替根節(jié)點(diǎn)即可 /* * * 10 ======> 6 * /...

一步一步寫算法（之排序二叉樹刪除-1）

【 聲明：版權(quán)所有，歡迎轉(zhuǎn)載，請(qǐng)勿用于商業(yè)用途。  聯(lián)系信箱：feixiaoxing @163.com】     相比較節(jié)點(diǎn)的添加，平衡二叉樹的刪除要復(fù)雜一些。因?yàn)樵趧h除的過(guò)程中，你要考慮到不同的情況，針對(duì)每一種不同的情況，你要有針對(duì)性的反應(yīng)和調(diào)整。所以在代碼編寫的過(guò)程中，我們可以一邊寫代碼，一邊寫測(cè)試用例。編寫測(cè)試用例不光可以驗(yàn)證我們編寫的代碼是否正確，還能不斷提高我們開發(fā)代碼的自信心...

一步一步寫算法（之排序二叉樹插入）

【 聲明：版權(quán)所有，歡迎轉(zhuǎn)載，請(qǐng)勿用于商業(yè)用途。  聯(lián)系信箱：feixiaoxing @163.com】     二叉樹的節(jié)點(diǎn)插入比較簡(jiǎn)單。一般來(lái)說(shuō)，二叉樹的插入主要分為以下兩個(gè)步驟：     1） 對(duì)當(dāng)前的參數(shù)進(jìn)行判斷，因?yàn)樾枰紤]到頭結(jié)點(diǎn)，所以我們使用了指針的指針...

一步一步寫算法（之排序二叉樹）

【 聲明：版權(quán)所有，歡迎轉(zhuǎn)載，請(qǐng)勿用于商業(yè)用途。  聯(lián)系信箱：feixiaoxing @163.com】     前面我們講過(guò)雙向鏈表的數(shù)據(jù)結(jié)構(gòu)。每一個(gè)循環(huán)節(jié)點(diǎn)有兩個(gè)指針，一個(gè)指向前面一個(gè)節(jié)點(diǎn)，一個(gè)指向后繼節(jié)點(diǎn)，這樣所有的節(jié)點(diǎn)像一顆顆珍珠一樣被一根線穿在了一起。然而今天...

一步一步寫算法（之洗牌算法）

【 聲明：版權(quán)所有，，歡迎轉(zhuǎn)載，請(qǐng)勿用于商業(yè)用途。  聯(lián)系信箱：feixiaoxing @163.com】     撲克牌洗牌是我們生活中比較喜歡玩的一個(gè)游戲。那么我們有沒(méi)有什么辦法自己設(shè)計(jì)一個(gè)撲克牌洗牌的方法呢？在c運(yùn)行庫(kù)當(dāng)中有一個(gè)隨機(jī)函數(shù)rand，它可以生成0~327...

一步一步寫算法（之n！中末尾零的個(gè)數(shù)統(tǒng)計(jì)）

【 聲明：版權(quán)所有，歡迎轉(zhuǎn)載，請(qǐng)勿用于商業(yè)用途。  聯(lián)系信箱：feixiaoxing @163.com】     在很多面試的題目中，求n！結(jié)果中零的個(gè)數(shù)也是經(jīng)常遇到的一道題目。那么這道題目的解決方法究竟是什么呢？我愿意在此和大家分享一下我自己的一些看法，有不同見(jiàn)解的朋...

一步一步寫算法（之大數(shù)計(jì)算）

【 聲明：版權(quán)所有，歡迎轉(zhuǎn)載，請(qǐng)勿用于商業(yè)用途。  聯(lián)系信箱：feixiaoxing @163.com】     我們知道在x86的32位cpu上面，int表示32位，如果核算成整數(shù)的話，大約是40多億。同樣，如果在64位cpu上面，能表示的最大整數(shù)就是64位二進(jìn)制，表...

一步一步寫算法（之鏈表逆轉(zhuǎn)）

【 聲明：版權(quán)所有，歡迎轉(zhuǎn)載，請(qǐng)勿用于商業(yè)用途。  聯(lián)系信箱：feixiaoxing @163.com】     鏈表逆轉(zhuǎn)是面試環(huán)境中經(jīng)常遇到的一道題目，也是我們?cè)趯?shí)際開發(fā)中可能會(huì)遇到的開發(fā)需求。和線性逆轉(zhuǎn)不一樣，單向鏈表的節(jié)點(diǎn)需要一個(gè)一個(gè)進(jìn)行處理。為了顯示兩者之間的區(qū)...

一步一步寫算法（之循環(huán)單向鏈表）

【 聲明：版權(quán)所有，歡迎轉(zhuǎn)載，請(qǐng)勿用于商業(yè)用途。  聯(lián)系信箱：feixiaoxing @163.com】     前面的博客中，我們?cè)?jīng)有一篇專門講到單向鏈表的內(nèi)容。那么今天討論的鏈表和上次討論的鏈表有什么不同呢？重點(diǎn)就在這個(gè)"循環(huán)"上面。有了循環(huán)，意味著我們可以從任何一個(gè)鏈表節(jié)點(diǎn)開始工作，可以把root定在任何鏈表節(jié)點(diǎn)上面，可以從任意一個(gè)鏈表節(jié)點(diǎn)訪問(wèn)數(shù)據(jù)，這就是循環(huán)的優(yōu)勢(shì)。...

一步一步寫算法（之雙向鏈表）

【 聲明：版權(quán)所有，歡迎轉(zhuǎn)載，請(qǐng)勿用于商業(yè)用途。  聯(lián)系信箱：feixiaoxing @163.com】     前面的博客我們介紹了單向鏈表。那么我們今天介紹的雙向鏈表，顧名思義，就是數(shù)據(jù)本身具備了左邊和右邊的雙向指針。雙向鏈表相比較單向鏈表，主要有下面幾個(gè)特點(diǎn)：     （1）在數(shù)據(jù)結(jié)構(gòu)中具有雙向指針     （2）插入數(shù)據(jù)的時(shí)候需要考慮前后的方向的操作     （3）同樣，刪...

一步一步寫算法（之單向鏈表）

【 聲明：版權(quán)所有，歡迎轉(zhuǎn)載，請(qǐng)勿用于商業(yè)用途。  聯(lián)系信箱：feixiaoxing @163.com】     有的時(shí)候，處于內(nèi)存中的數(shù)據(jù)并不是連續(xù)的。那么這時(shí)候，我們就需要在數(shù)據(jù)結(jié)構(gòu)中添加一個(gè)屬性，這個(gè)屬性會(huì)記錄下面一個(gè)數(shù)據(jù)的地址。有了這個(gè)地址之后，所有的數(shù)據(jù)就像一...

一步一步寫算法（之線性堆棧）

【 聲明：版權(quán)所有，歡迎轉(zhuǎn)載，請(qǐng)勿用于商業(yè)用途。  聯(lián)系信箱：feixiaoxing @163.com】   前面我們講到了隊(duì)列，今天我們接著討論另外一種數(shù)據(jù)結(jié)構(gòu)：堆棧。堆棧幾乎是程序設(shè)計(jì)的命脈，沒(méi)有堆棧就沒(méi)有函數(shù)調(diào)用，當(dāng)然也就沒(méi)有軟件設(shè)計(jì)。那么堆棧有什么特殊的屬性呢？其實(shí)，堆棧的屬性主要表現(xiàn)在下面兩個(gè)方面：    （1）堆棧的數(shù)據(jù)是先入后出    （2）堆棧的長(zhǎng)度取決于棧頂?shù)母叨?#160;   那么，作...

一步一步寫算法（之線性隊(duì)列）

【 聲明：版權(quán)所有，歡迎轉(zhuǎn)載，請(qǐng)勿用于商業(yè)用途。  聯(lián)系信箱：feixiaoxing @163.com】    這里的線性結(jié)構(gòu)實(shí)際上指的就是連續(xù)內(nèi)存的意思，只不過(guò)使用“線性”這個(gè)詞顯得比較專業(yè)而已。前面一篇博客介紹了現(xiàn)象結(jié)構(gòu)的處理方法，那么在這個(gè)基礎(chǔ)之上我們是不是添加一些屬性形成一種新的數(shù)據(jù)結(jié)構(gòu)類型呢？答案是肯定的，隊(duì)列便是其中的一種。    隊(duì)列的性質(zhì)很簡(jiǎn)單：    （1）隊(duì)列有頭部和尾部...

一步一步寫算法（之線性結(jié)構(gòu)的處理）

【 聲明：版權(quán)所有，歡迎轉(zhuǎn)載，請(qǐng)勿用于商業(yè)用途。  聯(lián)系信箱：feixiaoxing @163.com】     我們知道，在內(nèi)存中的空間都是連續(xù)的。也就是說(shuō)，0x00000001下面的地址必然是0x00000002。所以，空間上是不會(huì)出現(xiàn)地址的突變的。那什么數(shù)據(jù)結(jié)構(gòu)類...

一步一步寫算法（之堆排序）

【 聲明：版權(quán)所有，歡迎轉(zhuǎn)載，請(qǐng)勿用于商業(yè)用途。  聯(lián)系信箱：feixiaoxing @163.com】     堆排序是另外一種常用的遞歸排序。因?yàn)槎雅判蛴兄鴥?yōu)秀的排序性能，所以在軟件設(shè)計(jì)中也經(jīng)常使用。堆排序有著屬于自己的特殊性質(zhì)，和二叉平衡樹基本是一致的。打一個(gè)比方說(shuō)，處于大堆中的每一個(gè)數(shù)據(jù)都必須滿足這樣一個(gè)特性：     （1）每一個(gè)array[n] 不小于array[2*n]...

一步一步寫算法（之合并排序）

【 聲明：版權(quán)所有，歡迎轉(zhuǎn)載，請(qǐng)勿用于商業(yè)用途。  聯(lián)系信箱：feixiaoxing @163.com】     前面一篇博客提到的快速排序是排序算法中的一種經(jīng)典算法。和快速排序一樣，合并排序是另外一種經(jīng)常使用的排序算法。那么合并排序算法有什么不同呢？關(guān)鍵之處就體現(xiàn)在這...

一步一步寫算法（之快速排序）

【 聲明：版權(quán)所有，歡迎轉(zhuǎn)載，請(qǐng)勿用于商業(yè)用途。  聯(lián)系信箱：feixiaoxing @163.com】     快速排序是編程中經(jīng)常使用到的一種排序方法�？墒呛芏嗯笥褜�(duì)快速排序有畏難情緒，認(rèn)為快速排序使用到了遞歸，是一種非常復(fù)雜的程序，其實(shí)未必如此。只要我們使用好了方...

一步一步寫算法（之非遞歸排序）

【 聲明：版權(quán)所有，歡迎轉(zhuǎn)載，請(qǐng)勿用于商業(yè)用途。  聯(lián)系信箱：feixiaoxing @163.com】        在上面一篇博客當(dāng)中，我們發(fā)現(xiàn)普通查找和排序查找的性能差別很大。作為一個(gè)100萬(wàn)的數(shù)據(jù)，如果使用普通的查找方法，那么每一個(gè)數(shù)據(jù)查找平均下來(lái)就要幾十萬(wàn)次，那么二分法的查找呢，20多次就可以搞定。這中間的差別是非常明顯的。既然排序有這么好的效果，那么這篇博客中，我們就對(duì)排序算做一個(gè)...

一步一步寫算法（之查找）

【 聲明：版權(quán)所有，歡迎轉(zhuǎn)載，請(qǐng)勿用于商業(yè)用途。  聯(lián)系信箱：feixiaoxing @163.com】    無(wú)論是數(shù)據(jù)庫(kù)，還是普通的ERP系統(tǒng)，查找功能數(shù)據(jù)處理的一個(gè)基本功能。數(shù)據(jù)查找并不復(fù)雜，但是如何實(shí)現(xiàn)數(shù)據(jù)又快又好地查找呢？前人在實(shí)踐中積累的一些方法，值得我們好好學(xué)些一下。我們假定查找的數(shù)據(jù)唯一存在，數(shù)組中沒(méi)有重復(fù)的數(shù)據(jù)存在。    （1） 普通的數(shù)據(jù)查找    設(shè)想有一個(gè)1M的數(shù)據(jù)，我們...

一步一步寫算法（之內(nèi)存）

【 聲明：版權(quán)所有，歡迎轉(zhuǎn)載，請(qǐng)勿用于商業(yè)用途。  聯(lián)系信箱：feixiaoxing @163.com】     內(nèi)存是程序運(yùn)行的基礎(chǔ)。所有正在運(yùn)行的代碼都保存在內(nèi)存里面。內(nèi)存需要處理各種各樣的數(shù)據(jù)，包括鍵盤的數(shù)據(jù)、鼠標(biāo)的數(shù)據(jù)、usb的數(shù)據(jù)、串口的數(shù)據(jù)、攝像頭的數(shù)據(jù)，那...

一步一步寫算法（之遞歸和堆棧）

【 聲明：版權(quán)所有，歡迎轉(zhuǎn)載，請(qǐng)勿用于商業(yè)用途。  聯(lián)系信箱：feixiaoxing @163.com】    看過(guò)我前面博客的朋友都清楚，函數(shù)調(diào)用主要依靠ebp和esp的堆�；�(dòng)來(lái)實(shí)現(xiàn)的。那么遞歸呢，最主要的特色就是函數(shù)自己調(diào)用自己。如果一個(gè)函數(shù)調(diào)用的是自己本身，那么這個(gè)函數(shù)就是遞歸函數(shù)。    我們可以看一下普通函數(shù)的調(diào)用怎么樣的。試想如果函數(shù)A調(diào)用了函數(shù)B，函數(shù)B又調(diào)用了函數(shù)C，那么在堆棧中...

一步一步寫算法（之循環(huán)和遞歸）

【 聲明：版權(quán)所有，歡迎轉(zhuǎn)載，請(qǐng)勿用于商業(yè)用途。  聯(lián)系信箱：feixiaoxing @163.com】     其實(shí)編程的朋友知道，不管學(xué)什么語(yǔ)言，循環(huán)和遞歸是兩個(gè)必須學(xué)習(xí)的內(nèi)容。當(dāng)然，如果循環(huán)還好理解一點(diǎn)，那么遞歸卻沒(méi)有那么簡(jiǎn)單。我們?cè)?jīng)對(duì)遞歸諱莫如深，但是我想告訴...

一步一步寫算法（開篇）

【 聲明：版權(quán)所有，歡迎轉(zhuǎn)載，請(qǐng)勿用于商業(yè)用途。  聯(lián)系信箱：feixiaoxing @163.com】    算法是計(jì)算機(jī)的生命。沒(méi)有算法，就沒(méi)有軟件，計(jì)算機(jī)也就成了一個(gè)冰冷的機(jī)器，沒(méi)有什么實(shí)用價(jià)值。很多人認(rèn)為，算法是數(shù)學(xué)的內(nèi)容，學(xué)起來(lái)特別麻煩。我們不能認(rèn)為這種觀點(diǎn)是錯(cuò)誤的。但是我們也知道，軟件是一種復(fù)合的技術(shù)，如果一個(gè)人只知道算法，但是不能用編程語(yǔ)言很好地實(shí)現(xiàn)，那么再優(yōu)秀的算法也不能發(fā)揮作用。...

  本文關(guān)鍵詞：數(shù)據(jù)結(jié)構(gòu)，由筆耕文化傳播整理發(fā)布。

本文編號(hào)：65563