代碼準(zhǔn)備: 歸并排序 歸并排序(Merging Sort) 就是利用歸并的思想實(shí)現(xiàn)排序方法. 它的原理是假設(shè)初始序列含有n個(gè)記錄,則可以看成n個(gè)有序的子序列. 每個(gè)子序列的?...
代碼準(zhǔn)備: 歸并排序 歸并排序(Merging Sort) 就是利用歸并的思想實(shí)現(xiàn)排序方法. 它的原理是假設(shè)初始序列含有n個(gè)記錄,則可以看成n個(gè)有序的子序列. 每個(gè)子序列的?...
排序可以分為2類: 內(nèi)排序:是在排序整個(gè)過(guò)程中,待排序的所有記錄全部被放置在內(nèi)存中; 外排序:由于排序的記錄個(gè)數(shù)太多,不能同時(shí)放置在內(nèi)存,整個(gè)排序過(guò)程需要在內(nèi)外存之間多次交換...
平衡?叉樹(shù)(Self-Balancing Binary Search Tree 或 Height-Balanced Binary Search Tree),是一 種二叉排序樹(shù)...
一般的二叉樹(shù)結(jié)構(gòu)中會(huì)存在一些個(gè)別結(jié)點(diǎn)上的左指針或者右指針為空的情況,這種情況下就會(huì)存在浪費(fèi)空間的情況存在,如下圖: 我們可以利用這些空閑的結(jié)點(diǎn)來(lái)進(jìn)行線索話,將空出來(lái)的左指針指...
查找表操作方式分為靜態(tài)查找和動(dòng)態(tài)查找。靜態(tài)查找表(Static Search Table): 只作查找操作的查找表; 1.查詢某個(gè)”特定的”數(shù)據(jù)元素是否在查找表中; 檢索某個(gè)...
1、拓?fù)渑判?有?個(gè)表示工程的有向圖中, ?頂點(diǎn)表示活動(dòng), 用弧表示活動(dòng)之間的優(yōu)先關(guān)系,這樣有向圖為頂點(diǎn)表示活動(dòng)的網(wǎng). 我們稱為AOV網(wǎng)(Activity On Vertex...
最短路徑顧名思義就是兩個(gè)點(diǎn)之間所需花費(fèi)最短的那個(gè)路徑。在算法中計(jì)算最短路徑有兩個(gè)比較著名的算法:Dijkstra算法和Floyd算法 1、Dijkstra算法 Dijkstr...
連通圖的?生成樹(shù)定義: 所謂?一個(gè)連通圖的?生成樹(shù)是?一個(gè)極?小的連通?子圖,它含有圖中全部的n個(gè)頂點(diǎn),但只?足以構(gòu)成?一顆樹(shù)的n-1條邊.定義解讀: 滿?足以下3個(gè)條件則為...
圖的遍歷可以分為:深度優(yōu)先遍歷和廣度優(yōu)先遍歷 一、深度優(yōu)先遍歷 深度優(yōu)先遍歷的實(shí)現(xiàn)思路 將圖的頂點(diǎn)和邊信息輸?入到圖結(jié)構(gòu)中; 創(chuàng)建?一個(gè)visited 數(shù)組,?用來(lái)標(biāo)識(shí)頂點(diǎn)是...
一、圖的一些定義 圖:頂點(diǎn)的有窮非空集合和頂點(diǎn)之間邊的集合組成,通常表示為G=(V,E),其中G表示一個(gè)圖,V是圖G中的頂點(diǎn)的非空集合,E是圖G的邊的集合。 無(wú)向圖 & ?無(wú)...
一、關(guān)于二叉樹(shù)一些的概念 1.1樹(shù)的相關(guān)概念 高度:指節(jié)點(diǎn)到葉子節(jié)點(diǎn)的最長(zhǎng)邊數(shù) 深度:指根節(jié)點(diǎn)到節(jié)點(diǎn)的邊數(shù) 層:根節(jié)點(diǎn)的層定義為1,根節(jié)點(diǎn)的字節(jié)點(diǎn)為2,以此類推 1.2二叉樹(shù)...
題目: 有一個(gè)主串S = {a, b, c, a, c, a, b, d, c}, 模式串T 式串在主串中第一次出現(xiàn)的位置;提示: 不需要考慮字符串大小寫(xiě)問(wèn)題, 字符均為小寫(xiě)...
今天學(xué)習(xí)字符串匹配問(wèn)題的算法題目的BF算法和RK算法。題目:有一個(gè)主串S = {a, b, c, a, c, a, b, d, c}, 模式串T = { a, b, d } ...
一、前言 1.做算法題的方法: 充分閱讀題目.了解題目背后的關(guān)鍵意思; 分析題目,涉及到哪些數(shù)據(jù)結(jié)構(gòu),對(duì)問(wèn)題進(jìn)行分類. 到底屬于鏈表問(wèn)題, 棧思想問(wèn)題, 字符串問(wèn)題,二叉樹(shù)問(wèn)...
隊(duì)列 與棧不同,他就是現(xiàn)實(shí)中排隊(duì)一樣,講究先來(lái)后到,即 先進(jìn)先出。 我們也可以使用順序存儲(chǔ)和鏈?zhǔn)酱鎯?chǔ)來(lái)實(shí)現(xiàn)隊(duì)列。 一、順序存儲(chǔ)循環(huán)隊(duì)列 為了防止假溢出現(xiàn)象,在設(shè)計(jì)隊(duì)列的時(shí)候需...
1、棧的結(jié)構(gòu) 棧結(jié)構(gòu)遵循先進(jìn)后出的原則,進(jìn)棧和出棧都從棧頂進(jìn)行操作;我們可以用順序存儲(chǔ)和鏈?zhǔn)酱鎯?chǔ)兩種方式來(lái)實(shí)現(xiàn)棧。 2、順序存儲(chǔ)實(shí)現(xiàn)棧 2.1代碼準(zhǔn)備 2.2 構(gòu)建一個(gè)空棧 ...
題目一、 將2個(gè)遞增的有序鏈表合并為一個(gè)有序鏈表; 要求結(jié)果鏈表仍然使用兩個(gè)鏈表的存儲(chǔ)空間,不另外占用其他的存儲(chǔ)空間. 表中不允許有重復(fù)的數(shù)據(jù); 算法思想:(1)假設(shè)待合并的...
1.雙向鏈表 雙向鏈表的節(jié)點(diǎn)分為3個(gè)部分:前驅(qū)指針域、數(shù)據(jù)域和后繼指針域,可以用下圖表示: 前驅(qū)指針域:用于存儲(chǔ)該節(jié)點(diǎn)上一個(gè)節(jié)點(diǎn)的存儲(chǔ)地址; 數(shù)據(jù)域:用于存儲(chǔ)該節(jié)點(diǎn)的數(shù)據(jù) 后...
1. 單向循環(huán)列表 單向循環(huán)鏈表最后一個(gè)結(jié)點(diǎn)是重新指向它的第一個(gè)首元結(jié)點(diǎn)的位置;可以用下圖來(lái)表示: 2. 單向循環(huán)列表代碼實(shí)現(xiàn) 2.1 代碼準(zhǔn)備 2.2 創(chuàng)建循環(huán)列表 創(chuàng)建循...
一、基礎(chǔ)知識(shí) 數(shù)據(jù)結(jié)構(gòu)常用術(shù)語(yǔ):數(shù)據(jù)結(jié)構(gòu)中最基本的5個(gè)概念: 數(shù)據(jù),數(shù)據(jù)元素,數(shù)據(jù)項(xiàng),數(shù)據(jù)對(duì)象,數(shù)據(jù)結(jié)構(gòu);數(shù)據(jù)結(jié)構(gòu)@2x.png 1.1 數(shù)據(jù)數(shù)據(jù): “是描述客觀事物的符號(hào),...