導航:首頁 > 源碼編譯 > 數據結構演算法講解

數據結構演算法講解

發布時間:2023-06-05 10:09:57

㈠ 什麼是數據結構和演算法

數據結構,Data_Structure,其中D是數據元素的集合,R是該集合中所有元素之間的關系的有限集合。數據結構則是指相互之間存在一種或多種特定關系的數據元素的集合。通常情況下,精心選擇的數據結構可以帶來更高的運行或者存儲效率。數據結構往往同高效的檢索演算法和索引技術有關。

數據結構是計算機專業學生在大學期間都會學習的一門課程,但是由於課程偏理論,缺乏實際操作的學習體驗,而讓大家產生了一種「數據結構不重要,我只要學習了Java/C語言/Python同樣能敲代碼」的錯覺,但其實它是一門集技術性、理論性和實踐性於一體的課程。

演算法是某一系列運算步驟,它表達解決某一類計算問題的一般方法,對這類方法的任何一個輸入,它可以按步驟一步一步計算,最終產生一個輸出。

小碼哥的李明傑也說過所有的計算問題,都離不開要計算的對象或者要處理的信息,如何高效的把它們組織起來,就是數據結構關心的問題,所以演算法是離不開數據結構的,這就是數據與演算法。

㈡ 計算機考研:數據結構常用演算法解析(8)

第九章 查找
查找分成靜態查找和動態查找,靜態查找只是找,返回查找位置。而動態查找則不同,若查找成功,返回位置,若查找不成功,則要返回新記錄的插入位置。也就是說,靜態查找不改變查找表,而動態查找則會有插入操作,會改變查找表的。
不同的查找所採用的存儲結構也不同,靜態查找採用順序表,而動碼遲態查找由於經常變動,所以用二叉排序樹,二叉平衡樹、B-和B+。
靜態查找有,順序查找,折半查找,分塊查找(索引順序查找)
順序查找(Sequential Search)是最簡單的一種查找方法。
演算法思路
設給定值為k,在表(R1 R2……Rn)中,從Rn即最後一個元素開始,查找key=k的記錄。若存在一個記錄Ri(l≤i≤n)的key為k,則查找成功,返回記錄序號i;否則,查找失敗,返回0。
演算法描述
int sqsearch(sqlist r,keytype k) //對表r順序查找的演算法//
{ int i;
r.data[0].key=k; //k存入監視哨//
i=r.len; //取表長//
while(r.data[i].key!=k)
i--; //順序查找//
return(i);
}
演算法用了一點技巧:先將k存入監視哨,若對某個i(≠0)有r.data[i].key=k,則查找成功,返回i;若i從n遞減到1都無記錄的key為k,i再減1為0時,必有r.data[0].key=k,說明查找失敗,返回i=0。
平均查找成功長度ASL= ,而查找失敗時,查找次數等於n+l。
折半查找演算法及分析
當記錄的key按關系≤或≥有序時,不管是遞增的還是遞減的,只要有序且採用順序存儲。
演算法描述
int Binsearch(sqlist r,keytype k) //對有序表r折半查找的演算法//
{ int low,high,mid;
low=1;high=r.len; //上下界初值//
while(low<=high) //表空間存在時//
{ mid=(low+high)/2; //求當前mid//
if (k==r.data[mid].key)
return(mid); //查找成功,返回mid//
if (k
high=mid-1; //調整上界,向左部查找//
else
low=mid+1; //調整下界,向右部查找//
}
return(0); //low>high,查找失敗//
}
判定樹:用來描述二分查找過程的二叉樹。n個結點的判定樹的深度和n個結點的完全二叉樹深度相同= 。但判斷樹不一定是完全二叉樹,但他的葉子結點所在層次之差不超過1。所以,折半查找在查找成功時和給定值進行比笑困較的關鍵字個數至多為
ASL=
分塊查找演算法及分析
分塊查找(Blocking Search),又稱索引順序查找(Indexed Sequential Search),是順序查找方法的一種改進,目的也是為了提高查找效率。
1.分塊
設記錄表長為n,將表的n個記錄分成b= 個塊,每塊s個記錄(最後一塊記錄數可以少於s個),即:
且表分塊有序,即第i(1≤i≤b-1)塊所有記錄的key小於第i+1塊中記錄的key,但塊內記錄可以無序。
2.建立索引
每塊對應一索引項:
KeymaxLink
其中Keymax為該塊內記錄的最大key;link為該塊第一記錄的序號(或指針)。
3.演算法思路 分塊索碰模念引查找分兩步進行:
(1)由索引表確定待查找記錄所在的塊;(可以折半查找也可順序因為索引表有序)
(2)在塊內順序查找。(只能用順序查找,塊內是無序的)

考研有疑問、不知道如何總結考研考點內容、不清楚考研報名當地政策,點擊底部咨詢官網,免費領取復習資料:https://www.87dh.com/xl/

㈢ 一文帶你認識30個重要的數據結構和演算法

數組是最簡單也是最常見的數據結構。它們的特點是可以通過索引(位置)輕松訪問元素。

它們是做什麼用的?

想像一下有一排劇院椅。每把椅子都分配了一個位置(從左到右),因此每個觀眾都會從他將要坐的椅子上分配一個號碼。這是一個數組。將問題擴展到整個劇院(椅子的行和列),您將擁有一個二維數組(矩陣)。

特性

鏈表是線性數據結構,就像數組一樣。鏈表和數組的主要區別在於鏈表的元素不存儲在連續的內存位置。它由節點組成——實體存儲當前元素的值和下一個元素的地址引用。這樣,元素通過指針鏈接。

它們是做什麼用的?

鏈表的一個相關應用是瀏覽器的上一頁和下一頁的實現。雙鏈表是存儲用戶搜索顯示的頁面的完美數據結構。

特性

堆棧是一種抽象數據類型,它形式化了受限訪問集合的概念。該限制遵循 LIFO(後進先出)規則。因此,添加到堆棧中的最後一個元素是您從中刪除的第一個元素。

堆棧可以使用數組或鏈表來實現。

它們是做什麼用的?

現實生活中最常見的例子是在食堂中將盤子疊放在一起。位於頂部的板首先被移除。放置在最底部的盤子是在堆棧中保留時間最長的盤子。

堆棧最有用的一種情況是您需要獲取給定元素的相反順序。只需將它們全部推入堆棧,然後彈出它們。

另一個有趣的應用是有效括弧問題。給定一串括弧,您可以使用堆棧檢查它們是否匹配。

特性

隊列是受限訪問集合中的另一種數據類型,就像前面討論的堆棧一樣。主要區別在於隊列是按照FIFO(先進先出)模型組織的:隊列中第一個插入的元素是第一個被移除的元素。隊列可以使用固定長度的數組、循環數組或鏈表來實現。

它們是做什麼用的?

這種抽象數據類型 (ADT) 的最佳用途當然是模擬現實生活中的隊列。例如,在呼叫中心應用程序中,隊列用於保存等待從顧問那裡獲得幫助的客戶——這些客戶應該按照他們呼叫的順序獲得幫助。

一種特殊且非常重要的隊列類型是優先順序隊列。元素根據與它們關聯的「優先順序」被引入隊列:具有最高優先順序的元素首先被引入隊列。這個 ADT 在許多圖演算法(Dijkstra 演算法、BFS、Prim 演算法、霍夫曼編碼 )中是必不可少的。它是使用堆實現的。

另一種特殊類型的隊列是deque 隊列(雙關語它的發音是「deck」)。可以從隊列的兩端插入/刪除元素。

特性

Maps (dictionaries)是包含鍵集合和值集合的抽象數據類型。每個鍵都有一個與之關聯的值。

哈希表是一種特殊類型的映射。它使用散列函數生成一個散列碼,放入一個桶或槽數組:鍵被散列,結果散列指示值的存儲位置。

最常見的散列函數(在眾多散列函數中)是模常數函數。例如,如果常量是 6,則鍵 x 的值是x%6。

理想情況下,散列函數會將每個鍵分配給一個唯一的桶,但他們的大多數設計都採用了不完善的函數,這可能會導致具有相同生成值的鍵之間發生沖突。這種碰撞總是以某種方式適應的。

它們是做什麼用的?

Maps 最著名的應用是語言詞典。語言中的每個詞都為其指定了定義。它是使用有序映射實現的(其鍵按字母順序排列)。

通訊錄也是一張Map。每個名字都有一個分配給它的電話號碼。

另一個有用的應用是值的標准化。假設我們要為一天中的每一分鍾(24 小時 = 1440 分鍾)分配一個從 0 到 1439 的索引。哈希函數將為h(x) = x.小時*60+x.分鍾。

特性

術語:

因為maps 是使用自平衡紅黑樹實現的(文章後面會解釋),所以所有操作都在 O(log n) 內完成;所有哈希表操作都是常量。

圖是表示一對兩個集合的非線性數據結構:G={V, E},其中 V 是頂點(節點)的集合,而 E 是邊(箭頭)的集合。節點是由邊互連的值 - 描述兩個節點之間的依賴關系(有時與成本/距離相關聯)的線。

圖有兩種主要類型:有向圖和無向圖。在無向圖中,邊(x, y)在兩個方向上都可用:(x, y)和(y, x)。在有向圖中,邊(x, y)稱為箭頭,方向由其名稱中頂點的順序給出:箭頭(x, y)與箭頭(y, x) 不同。

它們是做什麼用的?

特性

圖論是一個廣闊的領域,但我們將重點介紹一些最知名的概念:

一棵樹是一個無向圖,在連通性方面最小(如果我們消除一條邊,圖將不再連接)和在無環方面最大(如果我們添加一條邊,圖將不再是無環的)。所以任何無環連通無向圖都是一棵樹,但為了簡單起見,我們將有根樹稱為樹。

根是一個固定節點,它確定樹中邊的方向,所以這就是一切「開始」的地方。葉子是樹的終端節點——這就是一切「結束」的地方。

一個頂點的孩子是它下面的事件頂點。一個頂點可以有多個子節點。一個頂點的父節點是它上面的事件頂點——它是唯一的。

它們是做什麼用的?

我們在任何需要描繪層次結構的時候都使用樹。我們自己的家譜樹就是一個完美的例子。你最古老的祖先是樹的根。最年輕的一代代表葉子的集合。

樹也可以代表你工作的公司中的上下級關系。這樣您就可以找出誰是您的上級以及您應該管理誰。

特性

二叉樹是一種特殊類型的樹:每個頂點最多可以有兩個子節點。在嚴格二叉樹中,除了葉子之外,每個節點都有兩個孩子。具有 n 層的完整二叉樹具有所有2ⁿ-1 個可能的節點。

二叉搜索樹是一棵二叉樹,其中節點的值屬於一個完全有序的集合——任何任意選擇的節點的值都大於左子樹中的所有值,而小於右子樹中的所有值。

它們是做什麼用的?

BT 的一項重要應用是邏輯表達式的表示和評估。每個表達式都可以分解為變數/常量和運算符。這種表達式書寫方法稱為逆波蘭表示法 (RPN)。這樣,它們就可以形成一個二叉樹,其中內部節點是運算符,葉子是變數/常量——它被稱為抽象語法樹(AST)。

BST 經常使用,因為它們可以快速搜索鍵屬性。AVL 樹、紅黑樹、有序集和映射是使用 BST 實現的。

特性

BST 有三種類型的 DFS 遍歷:

所有這些類型的樹都是自平衡二叉搜索樹。不同之處在於它們以對數時間平衡高度的方式。

AVL 樹在每次插入/刪除後都是自平衡的,因為節點的左子樹和右子樹的高度之間的模塊差異最大為 1。 AVL 以其發明者的名字命名:Adelson-Velsky 和 Landis。

在紅黑樹中,每個節點存儲一個額外的代表顏色的位,用於確保每次插入/刪除操作後的平衡。

在 Splay 樹中,最近訪問的節點可以快速再次訪問,因此任何操作的攤銷時間復雜度仍然是 O(log n)。

它們是做什麼用的?

AVL 似乎是資料庫理論中最好的數據結構。

RBT(紅黑樹) 用於組織可比較的數據片段,例如文本片段或數字。在 Java 8 版本中,HashMap 是使用 RBT 實現的。計算幾何和函數式編程中的數據結構也是用 RBT 構建的。

在 Windows NT 中(在虛擬內存、網路和文件系統代碼中),Splay 樹用於緩存、內存分配器、垃圾收集器、數據壓縮、繩索(替換用於長文本字元串的字元串)。

特性

最小堆是一棵二叉樹,其中每個節點的值都大於或等於其父節點的值:val[par[x]]

㈣ 計算機考研:數據結構常用演算法解析(3)

第三章
例如:Exp=a*b+(c-d/e)*f
若 Exp=a*b+(c-d/e)*f 則它的
前綴式為: +*ab*-c/def
中綴式為: a*b+c-d/e*f
後綴式為: ab*cde/-fx+
綜合比較它們之間的關系可得下列結論:
1.三式中的 「操作數之間的相對次序相同」;
(二叉樹的三種訪問次序中,葉子的相對訪問次序是相同的)
2.三式中的 「運算符之間的的相對次序不同」;
3.中綴式丟失了括弧信息,致使運算的次序不確定;
(而前綴和後綴運算只需要一個存儲操作數的棧,而中綴求值需要兩個棧,符號棧和操
作數棧)
4.前綴式的運算規則為:連續出現的兩個操作數和在它們之前且緊靠它們的運算符構成一個最小表達式;
5.後綴式的運算規則為:
·運算符在式中出現的順序恰為表達式的運算順序;
·每個運算符和在它之前出現且緊靠它的兩個操作數構成一個最小表達式;
6.中綴求值的運算規則:
如果是操作數直接入棧。
如果是運算符。這與當前棧頂比較。個如果比當前棧頂高,則入棧,如果低則說明當前棧頂是最高的必須把他先運算完了。用編譯原理的話就是說當前棧頂已經是最左素短語了)
其實中綴表達式直接求值和把中綴表達式轉化成後綴表達式在求值的過程驚人的相似,只不過是直接求值是求出來,而轉化成後綴是輸出來。
中綴表達式直接求值演算法:
OPNDType EvalueExpression()
{ //OPTR 和OPND分別為運算符棧和操作數棧
InitStack(OPTR);Push(OPTR,』#』);
InitStack(OPND);c=getchar();
While(c!=』#』|| GetTop(OPTR)!=』#』)
{
If(!IN(c,OP) ) //如果是操作數,直接入操作數棧
{ push(OPND,c);
c=getchar();
}
Else //如果是運算符,則與當前的棧頂比較
{
Switch(Precede(GetTop(OPTR),c))
{
Case 『<』: push(OPTR,c);//比當前棧頂高,這入棧
c=getchar();
break;
Case 』= 』:Pop(OPTR,x); //在我們設計的優棚肆枯先級表中,
c=getchar(); //只有』(』和』)』存在相等的情況,
break; //而在規約中間只存在『(』『)』
//所以我們直接把』(』彈出就可以了
Case 『>』: //比當前棧頂低,則要把棧頂先運算完(先規約)
pop(OPTR,theta); //把棧頂運算符彈出
Pop(OPND,b); //取出操作數,並且是前操作數雹搭
Pop(OPND,a); //在下面(棧的先進後出)
Push(OPND,Operate(a,theta,b)); //運算的結果入棧
//(他是其他運算符的操作數)
Break;
}//Switch
}//鏈洞else
}//whild
Return GetTop(OPND);//操作數棧中最後剩下的就是整個表達式的結果了。
}

考研有疑問、不知道如何總結考研考點內容、不清楚考研報名當地政策,點擊底部咨詢官網,免費領取復習資料:https://www.87dh.com/xl/

㈤ 計算機考研:數據結構常用演算法解析(7)

第七章:
對於無向圖,e的范圍是:
數據結構中所討論的圖都是簡單圖,任意兩結點間不會有雙重的邊。
對於有向圖,e的范圍是:
圖的各種存儲結構
鄰接矩陣很方便訪問任意兩點的邊,但是不方便計算其鄰接點。在深度和廣度遍歷中廣泛的需要求某點的鄰接點。所以鄰接矩陣只在Floyed和Prim和Dijstra中採用。
鄰接表能很方便的求某頂點的鄰接點,索引對於與遍歷有關的演算法大多都採用鄰接表。如深度、廣度、拓撲排序、關鍵路徑。但他也有不足的地方,就是不方便求入度或是那些薯早握點可以到他的操作。所以有人引進逆鄰接表。最後人們把這兩種表結合到一起就是十字鏈表和鄰接多重表。一個是存儲有向圖,另一個是存儲無向圖。
在十字鏈睜歷表和鄰接多重表很方便求鄰接點的操作和對應的逆操作。所以實際應用中,凡是能用鄰接表實現的一定能用十字鏈表和鄰接多重表實現。並且它們的存儲效率更高。
1.鄰接矩陣(有向圖和無向圖和網)又稱為數組表示法
typedef struct
{ vextype vexs[maxn]; ∥頂點存儲空間∥
adjtype A[maxn][maxn]; ∥鄰接矩陣∥
int vexnum,arcnum; //圖的頂點數和邊數
GraphKind Kind; //圖的類型
} mgraph;
2.鄰接表(有向圖和無向圖和網)
typedef struct node ∥邊
{ int adj; int w; ∥鄰接點、權∥
struct node *next; ∥指向下一弧或邊∥
}linknode;
typedef struct ∥頂點類型∥
{ vtype data; ∥頂點值域∥
linknode *farc; ∥指向與本頂點關聯的第一條弧或邊∥
}Vnode;
typedef struct
{
Vnode G[maxn]; ∥頂點表∥
int vexnum,arcnum;
GraphKind kind;
}ALGraph;
adjvexnextarcinfo
邊結點
datafirstarc
頂點結點
3.十字鏈表(有向圖和有向網)
headvextaivexhlinktlinkinfo
邊結點
datafirstinfirstout
頂點結點
4.鄰接多重表(無向圖)
markivexjvexilinkjlinkinfo
邊結點
datafirstedge
頂點結點
有向無環圖(DAG):是描述含有公共子式的表達式的有效工具。二叉樹也能表示表達式,但是利用有向無環圖可以實現對相同子式的共享,從而節省存儲空間。
頂點的度:
無向圖:某頂點V的度記為D(V),代表與V相關聯的邊的條數
有向圖:頂點V的度D(V)=ID(V)+OD(V)
強連通分量:在有向圖中,若圖中任意兩頂點間都存在路徑,則稱其是強連通圖。圖中極大 強連通子圖稱之為強連通分量
「極大」在這里指的是:往一個連通分量中再加入頂點和邊,就構不成原圖中的一個 連通子圖,即連通分量是一個最大集的連通子圖。有向圖的連通就是指該有向圖是強連通的。

考研有疑問、不知道如何總結考研考點內容、不清楚數慶考研報名當地政策,點擊底部咨詢官網,免費領取復習資料:https://www.87dh.com/xl/

㈥ PYTHON的數據結構和演算法介紹

當你聽到數據結構時,你會想到什麼?

數據結構是根據類型組織和分組數據的容器。它們基於可變性和順序而不同。可變性是指創建後改變對象的能力。我們有兩種類型的數據結構,內置數據結構和用戶定義的數據結構。

什麼是數據演算法-是由計算機執行的一系列步驟,接受輸入並將其轉換為目標輸出。

列表是用方括弧定義的,包含用逗號分隔的數據。該列表是可變的和有序的。它可以包含不同數據類型的混合。

months=['january','february','march','april','may','june','july','august','september','october','november','december']
print(months[0])#print the element with index 0
print(months[0:7])#all the elements from index 0 to 6
months[0]='birthday #exchange the value in index 0 with the word birthday

print(months)

元組是另一種容器。它是不可變有序元素序列的數據類型。不可變的,因為你不能從元組中添加和刪除元素,或者就地排序。

length, width, height =9,3,1 #We can assign multiple variables in one shot

print("The dimensions are {} * {} * {}".format(length, width, height))

一組

集合是唯一元素的可變且無序的集合。它可以讓我們快速地從列表中刪除重復項。

numbers=[1,2,3,4,6,3,3]

unique_nums = set(numbers)
print(unique_nums)

models ={'declan','gift','jabali','viola','kinya','nick',betty' }

print('davis' in models)#check if there is turner in the set models
models.add('davis')
print(model.pop())remove the last item#
字典

字典是可變和無序的數據結構。它允許存儲一對項目(即鍵和值)

下面的例子顯示了將容器包含到其他容器中來創建復合數據結構的可能性。

* 用戶定義的數據結構*

使用數組的堆棧堆棧是一種線性數據結構,其中元素按順序排列。它遵循L.I.F.O的機制,意思是後進先出。因此,最後插入的元素將作為第一個元素被刪除。這些操作是:

溢出情況——當我們試圖在一個已經有最大元素的堆棧中再放一個元素時,就會出現這種情況。

下溢情況——當我們試圖從一個空堆棧中刪除一個元素時,就會出現這種情況。

隊列是一種線性數據結構,其中的元素按順序排列。它遵循先進先出的F.I.F.O機制。

描述隊列特徵的方面

兩端:

前端-指向起始元素。

指向最後一個元素。

有兩種操作:

樹用於定義層次結構。它從根節點開始,再往下,最後的節點稱為子節點。

鏈表

它是具有一系列連接節點的線性數據。每個節點存儲數據並顯示到下一個節點的路由。它們用來實現撤銷功能和動態內存分配。

圖表

這是一種數據結構,它收集了具有連接到其他節點的數據的節點。

它包括:

演算法

在演算法方面,我不會講得太深,只是陳述方法和類型:

原文:https://www.tuicool.com/articles/hit/VRRvYr3

㈦ 計算機考研:數據結構常用演算法解析(4)

第四章
KMP演算法和樸素的匹配演算法的關鍵區別就是解決了主串指針i的回溯,原理如下:
設主串S[]和模式串T[],如比較到模式串的第j個字元。 當主串指針i和模式串指針j比較時 ,說明他們前面的所有字元都已經對應相等了。而
Next[j]=k的定義是T1T2…Tk-1==Tj-k+1Tj-k+2….Tj-1且k是最大了,沒有更長的了。
所以Si和Tj比較失敗時Si和Tk去比較。不可能有 這種匹配的成功,因為S2S3…..Si-1= =T2T3……Tj-1,而T2T3….Tj-1是不等於T1T2….Tj-2。除非next[j]=j-1;因為next定義的是最長的。所以任何挪動小於next[j]的串的匹配都是不能成功的。直到Tnext[j]和S[i]相比是才是最早有可能成功的。
Int KMP_Index(Sstring S,Sstring T,int pos)
{
i=pos;j=1;
while(i<=S[0]&&j<=T[0])
{
If(j=0||S[i]=T[j])//j=0表示模式串已經退到起點了說明在這個位置徹底不可能了,
{ ++i; ++j; } //i必須下移,j回到1開始
Else j=next[j];
}
If(j>T[0]) return i-T[0];
Else return 0;
}
求next[j]的方法和原理
設尺肆羨k=next[j];那麼T1T2…Tk-1= =Tj-k+1……Tj-2Tj-1;
若Tj= =Tk,那麼T1T2…Tk-1Tk= =Tj-k+1……Tj-2Tj-1Tj;
所以 next[j+1]=k+1=next[j]+1;且T1T2…Tk-1= =Tj-k+1……Tj-2Tj-1已經是
最長雹弊的序列,所以k+1也是next[j+1]最長的
若Tj不等於Tk,那麼就需要重找了。即…..Tj-1Tj ?,
T1T2….
所以next[j+1]首先=k=next[j]; 即…..Tj-1Tj ?,
T1T2…Tk-1.
若不相等,則next[j+1]=next[k]; 即…..Tj-1Tj ?,
T1T2….Tnext[k]-1
直到找到這樣的序列, 即…..Tj-1Tj ?,
T1T2 ...To
那麼,next[j+1]=next[next[j]]=next[next[next[j]]]…..=o+1;
Void get_next(Sstring T,int next[])
{
i=1; next[1]=0; j=0;//i表示當前求的next
While(i
{
if(j=0 | | T[i]=T[j])
{
++i;
++j;
next[i]=j;
}
Else j=next[j];
}
}
因為 next[ ] 在匹配過程中,若T[ j ]=T[ next[j] ];那麼當 S[i]不等於T[j],
S[ i]肯定也不等於T[k= next[j] ];
所以 S[i]應直接與T[next[k]]比較,而我們通陵拍過將next[j]修正
為nextval[j]=next[next[j]];這樣能使比較更少。
Void get_nextval(Sstring T,int nextval[])
{
i=1; nextval[1]=0; j=0;
while(i
{
if(j=0 || T[i]= T[j])
{
++i;
++j;
if(T[i]!=T[j])
nextval[i]=j;
else
nextval[i]=next[j];
}
else
j=nextval[j];
}
空格串是指__由空格字元(ASCII值32)所組成的字元串,其長度等於 空格個數____。
在模試匹配KMP演算法中所用失敗函數f的定義中,為何要求p1p2……pf(j)為p1p2……pj兩頭匹配的真子串?且為最大真子串?
失敗函數(即next)的值只取決於模式串自身,若第j個字元與主串第i個字元失配時,主串不回溯, 模式串用第k(即next[j])個字元與第i個相比,有『p1…pk-1』=『pj-k+1…pj-1』,為了不因模式串右移與主串第i個字元比較而丟失可能的匹配,對於上式中存在的多個k值,應取其中最大的一個。這樣,因j-k最小,即模式串向右滑動的位數最小,避免因右移造成的可能匹配的丟失。
第4章節有關數據結構演算法,上文中為大家作了分析,希望考生對於這些演算法能夠熟記於心,方便考試的應用和日後的實際操作,預祝大家都能夠取得好成績,加油!

更多詳情請點擊:計算機考研:數據結構常用演算法解析匯總

考研有疑問、不知道如何總結考研考點內容、不清楚考研報名當地政策,點擊底部咨詢官網,免費領取復習資料:https://www.87dh.com/xl/

閱讀全文

與數據結構演算法講解相關的資料

熱點內容
內核模塊調用命令 瀏覽:262
晴雅集哪個平台看 瀏覽:591
鍾真和徐錦江拍過的電影有哪些 瀏覽:757
vim命令找行 瀏覽:188
反編譯後的文件打不開 瀏覽:45
空調壓縮機哪裡有賣 瀏覽:99
java解析stringxml 瀏覽:493
島國片車牌咋用 瀏覽:77
韓國床戲電影推薦窗邊 瀏覽:915
照片壓縮軟體免費下載 瀏覽:922
weboffice怎麼解壓 瀏覽:323
安卓手機怎麼樣才能使用ios系統 瀏覽:502
如何在win10電腦安裝web伺服器 瀏覽:254
android監聽軟鍵盤收起 瀏覽:600
韓國著名女演員大尺度電影 瀏覽:38
有沒有胸大的電影 瀏覽:433
個人數據存放網和網路雲伺服器上 瀏覽:801
求免費網址 瀏覽:446
免費電影電影 瀏覽:182
紅帽8命令 瀏覽:792